google / google/heir

Use level-saving plaintext ciphertext multiplication

Open
#3,257 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
MLIR
Stars
906
Forks
171
Avg merge
4d 12h
Merged PRs (30d)
32

Description

I was looking at poly approximation lowerings. By default, they use chebyshev paterson stockmeyer with degree 5 polynomials, which should end up using a computation with 3 multiplicative depth. But the lowering consumes multiplicative depth 6 because of the plaintext coefficient multiplications.

Instead, you could use a level-saving trick by encoding the plaintext with the auxiliary modulus P and then rescale without consuming a q in the chain. You can do this in Lattigo, but I'm not totally sure how to configure this in the mgmt passes.

This issue will investigate the possibility of doing this.

Contributor guide

Open the contributing guide

Research direction

Start by reading the poly approximation lowerings and the management passes that configure Chebyshev–Paterson–Stockmeyer polynomials. Compare how plaintext coefficient multiplications are represented with the level-saving approach described for Lattigo. Done means establishing whether the lowering can avoid the extra multiplicative depth and documenting or implementing the required pass configuration.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, cryptography
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.