google / google/heir

Add costs for RLWE operations performed in over a large key basis degree

Open
#1,018 1 comment 0 reactions 0 assignees View on GitHub
newcomer project
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.