­Sin Kim

M.S. Student at CCRL, Hanyang University

[LatticA @LatticAwaLLLnut]

We’d like to share our team’s latest progress on fully homomorphic encryption (FHE) once again!

https://t.co/srZe2VyfEX

Every time we wrote a paper on FHE, we struggled with error analysis of the GINX-type approach. Each paper presented seemingly plausible formulas, but none of them had ever been properly verified.

When we actually built and ran a simulator ourselves, we realized something surprising: not a single one of them was correct. No one had actually simulated the real errors and checked whether the formulas matched reality.

In particular, whether decryption works correctly is not just a matter of saying, “Oops, sorry, we were wrong.” A number of papers have shown that information from decryption failures can be exploited to recover the secret key in homomorphic encryption schemes (see IND-CPAD).

Therefore, we present an error simulator that can precisely measure the errors arising in blind rotation.
We hope this simulator will contribute to the homomorphic encryption community by enabling accurate error analysis and allowing schemes to be compared fairly within a precise and consistent framework.

A paper, led by @thegimsin (with @Isley1249, @Scarrots93 , and @DJShin73) is currently being prepared for submission to arXiv. We’ll be back with another post as soon as it’s publicly available!

A. FHE schemes that use FFT are not covered. Because they introduce additional floating-point errors, we were not able to provide a rigorous model for those cases.

B. According to our forthcoming paper, it is also possible to reduce the error probability to 2^{-128} or even 2^{-256}.

C. Key switching is not yet included. The blind rotation analysis alone required 60 pages… (The deeper we dug, the more nontrivial formula terms kept appearing. It was almost maddening.)