Spookily Homomorphic Encryption Explained

Spookily Homomorphic Encryption, as presented by Daniel Wichs based on joint works with other researchers, explores concepts like Fully Homomorphic Encryption (FHE) and Multi-Key FHE. It delves into the why, what, and how of FHE, with a focus on distributed decryption and achieving non-local relationships. The presentation discusses background information on Multi-Key FHE, construction from hard problems over ideal lattices, and the significance of distributed decryption in applications.

• Homomorphic Encryption
• FHE
• Distributed Decryption
• Cryptography
• Daniel Wichs

jpatni Follow

Uploaded on Sep 28, 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. Spookily Homomorphic Encryption Spookily Homomorphic Encryption Daniel Wichs (Northeastern & NTT Research) Based on joint works with: (1) Pratyay Mukherjee [EUROCRYPT 2016] (2) Yevgeniy Dodis, Shai Halevi, Ron Rothblum [CRYPTO 2016]

2. Fully Homomorphic Encryption (FHE) Multi-Key FHE Spooky FHE 2. Why? 1. What? 3. How?

3. Fully Homomorphic Encryption (FHE) [RAD78,Gentry09, ] ??,?? ? ? ?????(?) ? = ???? (?,?) ?????? = ?(?) ?

4. Multi-Key FHE ??1,??1 ?1 ?????1(?1) ?1 ??2,??2 ? = ? ?2 ?????2(?2) ???? (?,?1,?2,?3) ?2 ??????? = ?(?) ??3,??3 ?3 ?????3(?3) ?3

5. Multi-Key FHE ??1,??1 ?1 ?????1(?1) ?1 ??2,??2 ? = ? ?2 ?????2(?2) ???? (?,?1,?2,?3) ?2 ?????1,??2,??3? = ?(?) ??3,??3 ?3 ?????3(?3) ?3

6. Multi-Key FHE ??1,??1 ?1 ?????1(?1) ?1 ??2,??2 ? = ? ?2 ?????2(?2) ???? (?,?1,?2,?3) ?2 ?????1,??2,??3? = ?(?) ??3,??3 ?3 ?????3(?3) Distributed decryption ?1 ?2 ?3 ?(?) ?3

7. Background on Multi-Key FHE Proposed by [LopezAlt-Tromer-Vaikunatnathan 12] construction based on hard problems over ideal lattices no distributed decryption Construction from LWE [Clear-McGoldrick 15] complicated construction, no distributed decryption This talk [Mukherjee-W 16]: simplified construction from LWE distributed decryption (crucial in applications)

8. Spooky FHE ??1,??1 ?1 ?????1(?1) ? 1 ?????1? 1 = ?1 ?1 ??2,??2 ? 2 ???? ?2 ?????2(?2) ?????2? 2 = ?2 ?2 ? 3 ??3,??3 ?3 ?????3(?3) ?????3? 3 = ?3 ?3

9. Spooky FHE ???? ?????1?1, ,??????(??) ?????1?1, ,??????(??) What relationship between ?1, ,?? and ?1, ,?? can we achieve? No Signaling : (Semantic Security) For all ? ? distribution of {??:? ?} cannot depend on {?? ? ?}. Yes Local : (with standard FHE) Can choose ?1, ,?? and ensure that ?1= ?1?1, ,??= ??(??) Can we achieve relationships which are not local (nor signaling)? [DLN+04] e.g., ?1 ?2= ?1 ?2

10. Physical Analogy No Signaling : Faster than light communication impossible ?1 ?1 Yes Local Some none-local relationships achievable using quantum entanglement. ?2 ?2 Spooky!

11. Physical Analogy Physical Setting Cryptographic Setting How are messages separated? Placed far apart Encryption under different keys Violate principle that information cannot travel faster than light Violate semantic security Signaling strategies Realization of no- signaling strategies Via quantum entanglement ? Spooky Encryption

12. Spooky FHE ???? ?????1?1, ,??????(??) ?????1?1, ,??????(??) This talk [Dodis-Halevi-Rothblum-W 16]: Can achieve large class of spooky relationships under LWE. Additive Functions Sharing (AFS) spooky FHE: For any function ?, can ensure ??= ?(?1, ,??) Implies multi-key FHE with distributed decryption.

13. Fully Homomorphic Encryption (FHE) Multi-Key FHE Spooky FHE 1. What? 2. Why? 3. How? 2-round multiparty computation function secret sharing counterexamples

14. Multi-Party Computation Round complexity? f(x1, ,xn) Goal: Correctness: Everyone computes f(x1, ,xn) Security: Nothing else revealed

15. 2-Round MPC from Multi-Key FHE Each party i chooses pki, ski broadcasts Encpki(xi). All parties run eval to get c* = Encpk1, ,pkn( f(x1, ,xn) ). Parties run a distributed decryption to recover y = f(x1, ,xn). With AFS-spooky encryption, parties have an additive secret sharing of f(x1, ,xn) at the end of the first round.

16. Fully Homomorphic Encryption (FHE) Multi-Key FHE Spooky FHE 1. What? 2. Why? 3. How? FHE [GSW13] Multi-Key FHE [MW16] Spooky FHE [DHRW16]

17. GSW FHE : Keys Can be a common public parameter ? Public Key: ? = ? ? ? ? = ?? + ? ? Secret Key: ? = ( ?,?) ? Key Property:?? = ? ?(small)

18. GSW FHE: Encryption ?????(?): encryption of bit ? under ?? = ? ? = ?? + ?? ? {0,1}m x m is random ? ? ? ?is a public gadget matrix ctext property: ??= ?? + ??? ???

19. GSW FHE: Encryption ?????(?): encryption of bit ? under ?? = ? ? = ?? + ?? ? {0,1}m x m is random Security: (?,?? + ??) (?,?? + ??) (?,? ) Leftover Hash Lemma LWE assumption

20. The GSW FHE: Evaluation Assume C1, C2encrypt bits x1, x2 respectively: tCi=xitG + ei xitG Addition:C+ = C1 + C2 tC+= t(C1 + C2) (x1 + x2)tG Multiplication:?

21. The GSW FHE: Evaluation Assume C1, C2encrypt bits x1, x2 respectively: tCi=xitG + ei xitG Addition:C+ = C1 + C2 tC+= t(C1 + C2) (x1 + x2)tG Multiplication:Cx = C1 G-1( C2 ) tCx= (x1tG + e) G-1( C2 ) x1t C2 x1x2tG G-1 is a function s.t. GG-1(C)=C and G-1(C) is small.

22. Homomorphic Circuit Evaluation Noise grows during homomorphic evaluation Depth ? Efficiency degrades with ? Can fix this with bootstrapping [G09]

23. Multi-Key Version of GSW Scenario: parties 1, ,N have independent GSW key pairs common public parameter common public parameter B B A1 = A2 = b1 = s1B+e1 b2 = s2B+e2 t1 = (-s1, 1) : t1 A1 0 t2 = (-s2, 1) : t2 A2 0

24. Multi-Key Version of GSW Scenario: parties 1, ,N have independent GSW key pairs Party i has secret key ?? ? Expanded secret key ? = (??, ,??) ? ?. ??. Goal: Convert party i ctext into expanded multi-key ctext. Party i ctext is ? ? Expanded ctext is ? ? ? ? : ??? ????. ?? ??: ? ? ? ? ? ? 0 for expanded gadget matrix ? = . 0 ? Perform homomorphic GSW operations on expanded ciphertexts. Let s do this for N=2 parties , everything extends naturally.

25. Ciphertext Expansion B B A1 = A2 = b1 = s1B+e1 b2 = s2B+e2 t1 = (-s1, 1) : t1 A1 0 t2 = (-s2, 1) : t2 A2 0 Party 1 encryption of x is: C = A1R + xG plus helper info (TBD). t1 C xt1G. t2C = t2(A1R + xG) = (-s2B + b1)R + xt2G (b1 - b2)R + xt2G Expanded ciphertext: ? = ? ? ? ? = [????,???? + (b1 - b2)R + t1D] Use helper info to find unmask term D such that t1D (b2 - b1)R ? ? where D is a unmask term (TBD).

26. Ciphertext Expansion B B A1 = A2 = b1 = s1B+e1 b2 = s2B+e2 t1 = (-s1, 1) : t1 A1 0 t2 = (-s2, 1) : t2 A2 0 Goal: Given helper info and b2 find unmask term D s.t. t1D (b2 - b1)R. Solution: helper info: GSW encryptions of each R[i,j] under A1 Ci,j : t1Ci,j R[i,j] t1 G unmask term: Given b1, b2can homomorphically compute D : t1D (b2 - b1)R

27. Distributed Decryption ??. Expanded secret key ?= (??, ,??) ? Expanded ctext is ? ? Compress: ? = ? ? ?(w) : w = (0, ,0,[q/2])T ? < ?, ?> = ? ? ? ?(w) ? < ?,?> ?[q/2] ?? ??: ? ? ? ? ? ??. Distributed decryption: each party outputs partial decryption ?? = <??,??> Output Round( ??) c1 ? = nN cN

28. Multi-Key Spooky In multi-key GSW FHE: Single-key ctext is ? Dec?? = ROUND(< ?,? >) = ? Multi-key ctext is: ? = (??, ,??) Dec ? ? = ROUND( < ??,??>) = ? In spooky encryption, we want: Dec??(??) = ROUND(< ??,??>) =?. Holds for N=2: If ROUND( ??) = ? then ROUND(??) = ? (w.o.p.) 0 -q/4 q/4 Proof: q/2

29. Spooky FHE: 2 to N parties Have: Enc??1(?1), , Enc???(??) Want: Enc??1(?1), , Enc???(??) s.t. ??= ?(?1, ,??) Idea follows [GMW] MPC: Invariant for each wire of circuit that takes value ? have: Enc??1(?1), , Enc???(??) s.t. ??= ? For addition gate, use single-key homomorphism. For multiplication gate, rely on 2-party spooky operations. Have: Enc??1(?1), , Enc???(??) s.t. ??= ? Enc??1(?1), , Enc???(??) s.t. ??= ? For each i,j, create Enc???(?? ?), Enc???(?? ?) s.t. ?? ?+ ?? ? = ???? For each i, create Enc???(??) = Enc???( ?? ?+ ?? ?)

30. Epilogue Can we do 2-round MPC without multi-key FHE? Yes. Can do it from 2-round OT, even without a CRS. [Garg-Srinivasan18, Benhamouda-Lin 18] Multikey FHE in the Plain Model (from NTRU+LWE) [Ananth-Jain-Jin-Malavolta 20] Open questions: Multi-Key FHE in the plain mode from LWE ? Non-compact Multi-Key FHE from (e.g.) DDH? Eval complexity << |circuit size| N2 ? Spooky-Free Homomorphic Encryption?

31. Thank you

32. Putting it all together Each party i chooses pki, ski broadcasts ci = Encpki(xi). All parties run a multi-key FHE eval to get c* = Encpk1, ,pkn( f(x1, ,xn) ). Parties run a distributed decryption to recover y = f(x1, ,xn). Secure for all-but-one corruption. Proving security for arbitrary corruptions requires some more work. Need NIZKs for malicious security (but no coin flipping). Questions: Can we get rid of the CRS in honest-but-curious setting? Can we get 2 or even 3 rounds under different/weaker assumptions?

33. The GSW FHE: Key Generation m B Public Key: A = ? ? n ? b = sB+e ? Secret Key: t = (-s,1) ? Remember:tA 0

34. The GSW FHE: Encryption Encpk(x): encryption of bit x under pk=A C = AR + xG R {0,1}m x m is random G ? ? ?is a public gadget matrix Remember: tC xtG

35. Gadget Matrix G G [Micciancio-Peikert 12] ? ? Gadget matrix G ? There is an efficiently computable function G-1( ) such that: G-1: ? for all C : GG-1(C) = C ? ? 0,1? ? Implementation: G-1is the bit decomp function Gconsists of powers-of-2

36. The GSW FHE: Evaluation Assume C1, C2encrypt bits x1, x2 respectively: tCi xitG Addition:C+ = C1 + C2 tC+= t(C1 + C2) (x1 + x2)tG Multiplication:Cx = C1 G-1( C2 ) tCx= (x1tG + e) G-1( C2 ) x1t C2 x1x2tG

37. The GSW FHE: Evaluation Assume C1, C2encrypt bits x1, x2 respectively: tCi=xitG + ei xitG Addition:C+ = C1 + C2 tC+= t(C1 + C2) (x1 + x2)tG Multiplication:Cx = C1 G-1( C2 ) tCx= (x1tG + e) G-1( C2 ) x1t C2 x1x2tG G-1 is a function s.t. GG-1(C)=C and G-1(C) is small.