Fhe-Compiler-Sok-Notes

Gartner projects that “by 2025, at least 20% of companies will have a budget for projects that include fully homomorphic encryption.”

Looks like I made the right move!

History

1. First-gen: Gentry initial & improved scheme, bootstrapping, etc.
   • 30mins to multiply two numbers.
2. Second-gen: BGV / BFV, use leveled HE (choose params large enough to finish the entire computation) instead of bootstrapping. Also SIMD-style batching.
   • Also CKKS, while not technically FHE since the operations are approximate, is very efficient for computations on fixed-point numbers.
3. Third-gen: GSW, CGGI, back to bootstrapping instead of leveling & batching, but with much faster bootstrapping (0.1s rather than several minutes).
   • Third to second gen is a tradeoff between latency and throughput.

Challenges

• Achieving state-of-the-art requires high familiarity with existing schemes
• Different programming paradigm
  • data-independent programs
  • efficency often requires complex vectorization
• Unlike in simple PKC where we can just use a single, known secure elliptic curve, FHE has computation-dependent parameters.
  • Lowering $q$ gives better time complexity and security, but finding the lowest $q$ that correctly decrypts remains an open challenge.
  • Worst-case analyses often result in parameters that are too large to be practical (that's why SEAL uses heuristics).
• Properly encoding into plaintext space $R_t$ is nontrivial.
• Data-independent computation is not intuitive for general software engineers used to relying on e.g. if/then/else branches.
  • Computation is instead conceptualized as a circuit where the execution follows the same steps no matter the data.
• SIMD batching is incredibly important for state of the art performance, but for general computations, it is a very complex technique that requires expertise in the application and scheme tradeoffs.
• Ciphertext maintence, e.g. relinearization, mod-switching, bootstrapping, etc., are done by the developer. Optimizing this requires expertise.
  • A favorable aspect of CGGI is that it does bootstrapping on each operation, so this choice is no longer on the developer.
  • There are various tools for automating this maintenance, but most are naive and not very efficient.

Experiments

Surprising results:

1. Why is the ML so performant? I thought this was out of reach, even with state of the art.
2. Why is the cardio app run time so much worse than the neural network? Is it simply analyzing more data, or do circuit encodings of if branches perform that much worse than matrix multiplications?
3. Holy crap at the difference between batching and not batching in SEAL! Are we batching in Sunscreen?

Conclusions

As a very rough heuristic, computations that take more than a few hundred milliseconds without FHE are unlikely to be practical once translated into FHE as of today

But this depends on the application; if computation can happen "offline" e.g. long running statistical analysis, it may be more feasible.

Complexity of application $\ne$ complexity of FHE implementation.

Performance may depend greatly on the implementation's ability to encode into a vectorized setting.