ABSTRACT
FHEW and TFHE are fully homomorphic encryption (FHE) cryptosystems that can evaluate arbitrary Boolean circuits on encrypted data by bootstrapping after each gate evaluation. The FHEW cryptosystem was originally designed based on standard (Ring, circular secure) LWE assumptions, and its initial implementation was able to run bootstrapping in less than 1 second. The TFHE cryptosystem used somewhat stronger assumptions, such as (Ring, circular secure) LWE over the torus with binary secret distribution, and applied several other optimizations to reduce the bootstrapping runtime to less than 0.1 second. Up to now, the gap between the underlying security assumptions prevented a fair comparison of the cryptosystems for the same security settings.
We present a unified framework that includes the original and extended variants of both FHEW and TFHE cryptosystems, and implement it in the open-source PALISADE lattice cryptography library using modular arithmetic. Our analysis shows that the main distinction between the cryptosystems is the bootstrapping procedure used: Alperin-Sherif--Peikert (AP) for FHEW vs. Gama--Izabachene--Nguyen--Xie (GINX) for TFHE. All other algorithmic optimizations in TFHE equally apply to both cryptosystems. The GINX bootstrapping method makes essential the use of binary secrets, and cannot be directly applied to other secret distributions. In the process of comparing the two schemes, we present a simple, lightweight method to extend GINX bootstrapping (e.g., as employed by TFHE) to ternary uniform and Gaussian secret distributions, which are included in the HE community security standard. Our comparison of the AP and GINX bootstrapping methods for different secret distributions suggests that the TFHE/GINX cryptosystem provides better performance for binary and ternary secrets while FHEW/AP is faster for Gaussian secrets. We make a recommendation to consider the variants of FHEW and TFHE cryptosystems based on ternary and Gaussian secrets for standardization by the HE community.
- 2020. PALISADE Lattice Cryptography Library (release 1.10.3). https://palisade- crypto.org/.Google Scholar
- Martin Albrecht, Melissa Chase, Hao Chen, and et al. 2018. Homomorphic Encryp- tion Security Standard. Technical Report. Homomorphic Encryption.org, Toronto, Canada.Google Scholar
- Martin Albrecht, Samuel Scott, and Rachel Player. 2015. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology 9, 3 (10 2015), 169--203. https://doi.org/10.1515/jmc-2015-0016Google ScholarCross Ref
- Jacob Alperin-Sheriff and Chris Peikert. 2014. Faster Bootstrapping with Polyno- mial Error. In CRYPTO 2014 (Lecture Notes in Computer Science, Vol. 8616). 297--314. https://doi.org/10.1007/978-3-662-44371-2_17Google Scholar
- Sebastian Angel, Hao Chen, Kim Laine, and Srinath T. V. Setty. 2018. PIR with Compressed Queries and Amortized Query Processing. In 2018 IEEE Symposium on Security and Privacy. 962--979. https://doi.org/10.1109/SP.2018.00062Google Scholar
- Jean-François Biasse and Luis Ruiz. 2015. FHEW with Efficient Multibit Boot- strapping. In LATINCRYPT 2015 (Lecture Notes in Computer Science, Vol. 9230). 119--135. https://doi.org/10.1007/978-3-319-22174-8_7 Google ScholarDigital Library
- Marcelo Blatt, Alexander Gusev, Yuriy Polyakov, and Shafi Goldwasser. 2020. Secure large-scale genome-wide association studies using homomorphic encryp- tion. Proceedings of the National Academy of Sciences 117, 21 (2020), 11608--11613. https://doi.org/10.1073/pnas.1918257117Google ScholarCross Ref
- Guillaume Bonnoron, Léo Ducas, and Max Fillinger. 2018. Large FHE Gates from Tensored Homomorphic Accumulator. In AFRICACRYPT 2018 (Lecture Notes in Computer Science, Vol. 10831). 217--251.Google ScholarCross Ref
- Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) Fully Homomorphic Encryption without Bootstrapping. TOCT 6, 3 (2014), 13:1--13:36. Google ScholarDigital Library
- Zvika Brakerski and Vinod Vaikuntanathan. 2014. Lattice-based FHE as secure as PKE. In ITCS'14. 1--12. https://doi.org/10.1145/2554797.2554799 Google ScholarDigital Library
- Hao Chen, Kim Laine, and Peter Rindal. 2017. Fast Private Set Intersection from Homomorphic Encryption. In CCS 2017. ACM, 1243--1255. Google ScholarDigital Library
- Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. 2017. Homomorphic Encryption for Arithmetic of Approximate Numbers. In ASIACRYPT (1) (Lecture Notes in Computer Science, Vol. 10624). Springer, 409--437.Google Scholar
- Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2016. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In ASIACRYPT (1) (Lecture Notes in Computer Science, Vol. 10031). 3--33.Google Scholar
- Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2017. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE. In ASIACRYPT 2017 (Lecture Notes in Computer Science, Vol. 10624). 377--408. https://doi.org/10.1007/978-3-319-70694-8_14Google Scholar
- Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. August 2016. TFHE: Fast Fully Homomorphic Encryption Library. https://tfhe.github.io/tfhe/.Google Scholar
- Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. TFHE: Fast Fully Homomorphic Encryption Over the Torus. Journal of Cryptology 33 (2020), 34--91. https://doi.org/10.1007/s00145-019-09319-xGoogle ScholarDigital Library
- Benjamin R. Curtis and Rachel Player. 2019. On the Feasibility and Impact of Standardising Sparse-Secret LWE Parameter Sets for Homomorphic Encryption. In WAHC'19. 1--10. https://doi.org/10.1145/3338469.3358940 Google ScholarDigital Library
- Léo Ducas and Daniele Micciancio. 2015. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In EUROCRYPT (1) (Lecture Notes in Computer Science, Vol. 9056). Springer, 617--640.Google Scholar
- Leo Ducas and Daniele Micciancio. May 2017. FHEW: A Fully Homomorphic Encryption library. https://github.com/lducas/FHEW.Google Scholar
- Thomas Espitau, Antoine Joux, and Natalia Kharchenko. 2020. On a hybrid approach to solve binary-LWE. Cryptology ePrint Archive, Report 2020/515.Google Scholar
- Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive 2012 (2012), 144.Google Scholar
- Nicolas Gama, Malika Izabachène, Phong Q. Nguyen, and Xiang Xie. 2016. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems. In EUROCRYPT 2016 (Lecture Notes in Computer Science, Vol. 9666). 528--558. https://doi.org/10.1007/978-3-662-49896-5_19Google ScholarCross Ref
- Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In STOC. ACM, 169--178. Google ScholarDigital Library
- Craig Gentry, Shai Halevi, and Nigel P. Smart. 2012. Fully Homomorphic Encryp- tion with Polylog Overhead. In EUROCRYPT (Lecture Notes in Computer Science, Vol. 7237). Springer, 465--482. Google ScholarDigital Library
- Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryp- tion from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO (1) (Lecture Notes in Computer Science, Vol. 8042). Springer, 75--92.Google Scholar
- Shai Halevi and Victor Shoup. 2013. Design and Implementation of a Homomorphic-Encryption Library. https://shaih.github.io/pubs/he-library.pdf.Google Scholar
- Shai Halevi and Victor Shoup. 2015. Bootstrapping for HElib. In EUROCRYPT 2015 (Lecture Notes in Computer Science, Vol. 9056). 641--670.Google Scholar
- Kyoohyung Han, Seungwan Hong, Jung Hee Cheon, and Daejun Park. 2019. Logistic Regression on Homomorphic Encrypted Data at Scale. In AAAI 2019. 9466--9471. https://doi.org/10.1609/aaai.v33i01.33019466Google ScholarDigital Library
- Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. On Ideal Lattices and Learning with Errors over Rings. J. ACM 60, 6 (2013), 43:1--43:35. https: //doi.org/10.1145/2535925 Google ScholarDigital Library
- Daniele Micciancio. 2018. On the Hardness of Learning With Errors with Binary Secrets. Theory Comput. 14, 1 (2018), 1--17.Google ScholarCross Ref
- Daniele Micciancio. 2019. Fully Homomorphic Encryption from the ground up. (2019). https://youtu.be/TySXpV86958x Invited Talk, Eurocrypt 2019.Google Scholar
- Daniele Micciancio and Chris Peikert. 2013. Hardness of SIS and LWE with Small Parameters. In CRYPTO (1) (Lecture Notes in Computer Science, Vol. 8042). 21--39.Google Scholar
- Daniele Micciancio and Jessica Sorrell. 2018. Ring Packing and Amortized FHEW Bootstrapping. In ICALP 2018 (LIPIcs, Vol. 107). 100:1--100:14.Google Scholar
- Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 6 (2009), 34:1--34:40. Google ScholarDigital Library
- SEAL 2020. Microsoft SEAL (release 3.5). https://github.com/Microsoft/SEAL. Microsoft Research, Redmond, WA.Google Scholar
- Nigel P. Smart and Frederik Vercauteren. 2014. Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71, 1 (2014), 57--81. Google ScholarDigital Library
- Yongha Son and Jung Hee Cheon. 2019. Revisiting the Hybrid Attack on Sparse Secret LWE and Application to HE Parameters. In WAHC'19. 11--20 Google ScholarDigital Library
Index Terms
- Bootstrapping in FHEW-like Cryptosystems
Recommendations
OpenFHE: Open-Source Fully Homomorphic Encryption Library
WAHC'22: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic CryptographyFully Homomorphic Encryption (FHE) is a powerful cryptographic primitive that enables performing computations over encrypted data without having access to the secret key. We introduce OpenFHE, a new open-source FHE software library that incorporates ...
(Leveled) fully homomorphic encryption without bootstrapping
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science ConferenceWe present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic ...
Batched Fully Dynamic Multi-key FHE from FHEW-Like Cryptosystems
Provable and Practical SecurityAbstractMulti-key fully homomorphic encryption (MKFHE) schemes support arbitrary computations on data encrypted by different keys. Especially, in the fully dynamic setting, any ciphertexts can be computed at any time while maintaining the compactness. In ...
Comments