Advancements in Multi-Key Homomorphic Encryption Using TFHE

Revolutionary research has led to the development of Multi-Key Homomorphic Encryption (MKHE) from TFHE, enabling secure and efficient computations on encrypted data. This technology offers advantages such as dynamic operability, stronger security, and minimized interaction, making it an ideal solution for secure computations in various settings. The history, design, and benefits of MKHE are explored, showcasing its potential in secure multiparty computation protocols.

• Homomorphic Encryption
• Multi-Key Encryption
• TFHE
• Secure Computation
• Cryptography

vover Follow

Uploaded on Sep 15, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Multi-key Homomorphic Encryption from TFHE Hao Chen, Yongsoo Song (Microsoft Research) Ilaria Chillotti (Cosic, KU Leuven) ASIACRYPT 2019 December 11, 2019 Kobe, Japan

2. Homomorphic Encryption (HE) ? ? ? ?? + ? eval Decryption ?? + ?

3. Multi-key Homomorphic Encryption (MKHE) ?? + ? ? ? ? ?? + ?

4. Building (2-round) MPC protocol from MKHE (MW 16) Local KeyGen & Encryption & Distributed decryption! ? ?? + ? ? ?

5. Advantages of (MPC from) MKHE Homomorphic Encryption (HE) Trusted party (semi-honest) Distributed authority (stronger notion of security) Reusable, Less-interactive (Fully) Dynamic Nothing about other parties needs to be known for ahead of setup or encryption. Any operation on any ciphertexts at anytime Computation Cost: GC/SS < HE < MKHE Non-reusable, Communication expensive How much exactly? Garbled Circuit, Secret Sharing

6. History of MKHE NTRU L pez-Alt et al. (STOC 12) Our Results GSW Clear-McGoldrick (Crypto 15) Mukherjee-Wichs (EC 16) Peikert-Shiehian (TCC 16) 1. Design efficient MKHE from TFHE Boolean gate & Bootstrapping First (PoC) implementation of MKHE LWE 2. Two Methods for MK External Products (RLWE-RGSW) Improved version of previous method [MW16,BP16] New approach with better storage, complexity, noise growth Brakerski-Perlman (Crypto 16) This work: MK-TFHE (AC 19) Ring LWE (packing) Chen-Zhang-Wang (TCC 17) Chen-Dai-Kim-Song (CCS 19)

7. Overview of TFHE: Fast FHE over the Torus ?[?] (??+ 1), ? = [?] (??+ 1) Torus: ? = (??? 1), ? = LWE secret ? 0,1?, LWE ciphertext ?,? ??+1 s.t. ? + ?,? ? 4 (??? 1). RLWE secret ? ?, RLWE ciphertext ?0,?1 ?2 ?1 ?0 Gadget vector ? = (? 1, ,? ). Gadget decomposition ? 1:? ? ? (?1, ,? ) s.t. ? ?1? 1+ + ? ? ??? 1 . 1 1 ? ? ?* ?? ?1 ? ? ? ? RGSW ciphertext ?0,?1 ?2 2

8. Overview of TFHE: External (Internal) Product : RLWE (RGSW) RGSW RLWE (RGSW) ??,?? ?? ?? = ? 1?? ?? = = = = ?? = RGSW.Enc(?) Err ?? ?? ? Err ?? + ? 1?? Err(??)

9. Overview of TFHE: MUX Gate (aka choice ftn) MUX : (RLWE, RLWE) RGSW RLWE ??0,??1,?? ??0+ (??1 ??0) ?? ?? = RGSW.Enc(?), ? = 0 ?? 1. ?? = MUX(??0,??1,??) encrypts the same plaintext as ??? Err ?? Err ??? + ? 1??1 ??0 Err(??) * borrowed from Ilaria s slide

10. Overview of TFHE: Gate Bootstrapping LWE.Enc(?0) LWE.Enc(?1) Linear Transformation // LWE secret ? 0,1? // ? + ?,? LWE.Enc ? = (?,?) ? = ????(?0,?1) ? 2 (??? 1) ACC RLWE.Enc ?? for ? = 1 to ? ACC ??? // compute RLWE.Enc ??+ ?,? // bootstrapping key BK?= RGSW.Enc(?[?]) Accumulator ACC,?? ? ACC ,BK? Extraction & Key Switching LWE.Enc ?

11. MK TFHE: Setup LWE secret ?? 0,1?, MK-LWE ciphertext ?,?1,?2, ,?? ???+1 s.t. ? + ???,?? ? 4 (??? 1). ?0 ?1 ?? RLWE secret ?? ?, MK-RLWE ciphertext ?0,?1, ,?? ??+1 RGSW ciphertext ?0,?1, ,?? ?(?+1) (?+1) 1 1 ? ? ? ?* ?1 ?1 ?2 ?2 ? ? ? ?0 ?1 ?2 ? ? ?

12. MK TFHE: Our Hope LWE.Enc(?0) LWE.Enc(?1) Linear Transformation // LWE secret ? 0,1? // ? + ?,? LWE.Enc ? = (?,?) ? = ????(?0,?1) ? 2 (??? 1) ACC RLWE.Enc ?? for ? = 1 to ? ACC ??? // compute RLWE.Enc ??+ ?,? // bootstrapping key BK?= RGSW.Enc(?[?]) Accumulator ACC,?? ? ACC ,BK? Extraction & Key Switching LWE.Enc ?

13. MK TFHE: Our Hope MKLWE.Enc(?0) MKLWE.Enc(?1) Linear Transformation // LWE secrets ?? 0,1? // ? + ?1,?1 + + ??,?? MKLWE.Enc ? = (?,?1,?2, ??) ? = ????(?0,?1) ? 2 (??? 1) ACC MKRLWE.Enc ?? for ? = 1 to ? for ? = 1 to ? ACC ??? // compute MKRLWE.Enc ??+ ??? ??[?] // bootstrapping key BK?,?= MKRGSW.Enc(??[?]) Accumulator ACC,???? ACC ,BK?,? Q. Who can generate Boot Key? How? Extraction & Multi Key Switching Q. How to design a new External Product between a single-key & MK-RLWE ciphertexts? MKLWE.Enc ?

14. MK TFHE: External Product (Setup) Common Reference String (CRS): ?0 ? Party ? generates and broadcasts ??= ?? ?0+ ?? (??? 1). ? ? 2 Uni-encryption : ?? ? ??,??= ??,0??,1 ??= ?? ?0+ ?? ? + ??,1 (??? 1) for some small ?? ??,0= ?? ??,1+ ?? ? + ??,2 (??? 1) for random ??,1 Remark: ?? ?? ???? ?0+ ???? ? ?? ??+ ???? ? (??? 1).

15. MK TFHE: External Product (First Method) Improvement of GSW ciphertext extension [MW 16] Uni-encryption : ?? ? ??,??= ??,0??,1 ??= ?? ?0+ ?? ? + ??,1 (??? 1) ??,0= ?? ??,1+ ?? ? + ??,2 (??? 1) Remark: ?? ?? ?? ??+ ???? ? Given uni-encryption ??,?? of ?? and public keys ??, For each ?, generate ???? = ?? ?? (which satisfies ??+ ?? ?? ?? ??) Then, return the MK RGSW encryption of ?? (??= ??1 , ,??[?] in MK TFHE) ?-th col ? ? 2 ?? + ?0 ? ?0 ? ?1 ?? ?1 ? ?? ? ?? ?? 1. Expensive (internal product) 2. Noise growth: ?? [??|??] = ?? (?? ??)

16. MK TFHE: External Product (Second Method) New approach without GSW extension Change the order of computation (same function/plaintext, different circuit) Given uni-encryption ??,?? of ??, public keys ??, and MKRLWE ?? = (?0,?1, ,??), For each ?, compute ?? (which satisfies ?0 Then, aggregate (? + 1) triples = ?? ?? and ?0 + ?? = ?? ?? ?? ,?? ??+ ?? ?? ?? ???? as desired) 1. More efficient (external product) 2. Noise growth: ?? ?? ?? versus ?? (?? ??) 3. Less Storage (no pre-computation of bootstrapping key)

17. MK TFHE: Implementation MKLWE.Enc(?0) MKLWE.Enc(?1) Linear Transformation Built on top of the TFHE library Available on GitHub: https://github.com/ilachill/MK-TFHE MKLWE.Enc ? = (?,?1,?2, ??) ? = ????(?0,?1) ACC MKRLWE.Enc ?? for ? = 1 to ? for ? = 1 to ? ACC ??? Accumulator // External product (Second Method) ACC,???? ACC ,BK?,? Extraction & Multi Key Switching MKLWE.Enc ?

18. MK TFHE: Parameter LWE RLWE (RGSW) Parameter Sets Decomp Decomp n Noise Std N Noise Std Base Deg Base Deg 29 Set 1 3 22 3.72 10 9 28 3.05 10 5 560 1024 Set 2 8 4 26 Set 3 5 About 110 bits of security according to the LWE estimator

19. MK TFHE: Experimental Results Parameter Sets Fresh Ciphertext Multi-Key Ciphertext # of parties NAND + Boot Set 1 2 4.38 KB 0.27 s 2 4.38 KB 0.43 s Set 2 4 8.77 KB 1.45 s 2.19 KB 2 4.38 KB 0.50 s Set 3 4 8.77 KB 1.90 s 8 17.32 KB 7.16 s Core i7-4910MQ at 2.90GHz laptop, running on a single thread