Add costs for RLWE operations performed in over a large key basis degree
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
Pre-filing issue for https://github.com/google/heir/pull/1016
The optimization problem in that PR just minimizes the total number of relin ops (with a hard-bound on the maximum key basis size allowed in the program). We could relax this by having a cost per (operation, degree) tuple, and charging the solver for doing ops with a larger key basis. It's not clear how much this could improve efficiency/noise growth, but some papers (like Blatt-Gusev-Polyakov-Rohloff-Vaikuntanathan 2019 https://eprint.iacr.org/2019/223) mention that they might NEVER do relinearization.
It's also not clear to what extent various libraries we export to would support high-basis-degree ops.
But to implement this feature, we would mainly need a way to estimate costs of the ops, and the changes to the ILP would be relatively small.
Contributor guide
Assessment
This issue has not been assessed yet.