Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Correct the likely-incorrect noise propagation model for CGGI #297

Open
j2kun opened this issue Nov 29, 2023 · 0 comments
Open

Correct the likely-incorrect noise propagation model for CGGI #297

j2kun opened this issue Nov 29, 2023 · 0 comments
Labels
analysis Issues related to analysis passes dialect: cggi Issues about the CGGI dialect

Comments

@j2kun
Copy link
Collaborator

j2kun commented Nov 29, 2023

I did a best-effort implementation in #275, but got lost in the array of papers that have slightly different formulas for slightly different versions of the CGGI bootstrap.

The noise model has two parts where the current implementation is likely wrong:

  • The noise output by a bootstrap, as computed based on the various CGGI and LWE parameters
  • The max allowable noise, based on the LWE parameters

Also, pending #296 the noise validation check is effectively trivial anyway, because trivial encryptions are noiseless. So this depends on #296 being implemented.

Some options to rectify this include:

  • Getting help from CGGI experts over at Zama
  • Finding the place in the tfhe-rs codebase where they compute these formulas (though from what I could tell, they use a nominal baseline, so the exact formula for the max, which I couldn't find, would be different).

Another twist is that, while the current implementation picks a single formula for the noise after a bootstrap, the actual formula depends on which variant of bootstrap one is performing. E.g., doing key switch before or after the blind rotate, or using the BMMV trick (Bourse-Minelli-Minihold-Paillier: https://eprint.iacr.org/2017/1114).

We could lower these high-level bootstrap ops to the constituent pieces and then apply the noise propagation at that level. E.g., noise propagated by key switch only, then noise propagated by blind rotate only, etc. But we don't have that layer of granularity yet. It seems reasonable to pick a "worst case" noise model (taken over all implementations of bootstrap in targeted backends) for the high-level bootstrap API, so that it can be exported to any CGGI library backend, and revisit this when there's a lower level ready to use instead and we want to start lowering directly to hardware.

@j2kun j2kun added analysis Issues related to analysis passes dialect: cggi Issues about the CGGI dialect labels Nov 29, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
analysis Issues related to analysis passes dialect: cggi Issues about the CGGI dialect
Projects
None yet
Development

No branches or pull requests

1 participant