Fully Homomorphic Encryption: Foundations and Applications

Slide Note
Embed
Share

Fully Homomorphic Encryption (FHE) allows computations on encrypted data without decrypting, enabling secure outsourcing of computations to untrusted servers. FHE involves key generation, encryption, homomorphic evaluation, and decryption processes. It ensures correctness, security, and compactness while enabling computation of arbitrary functions using Boolean circuits with XOR and AND gates on encrypted data. Bootstrapping further enhances FHE capabilities.


Uploaded on Jul 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.

E N D

Presentation Transcript


  1. MIT 6.875 Foundations of Cryptography Lecture 20

  2. Fully Homomorphic Encryption

  3. Homomorphic Encryption: Syntax (can be either secret-key or public-key enc) 4-tuple of PPT algorithms (???,???,???,????) s.t. ??,?? ??? 1?. PPT Key generation algorithm generates a secret key as well as a (public) evaluation key. Encryption algorithm uses the secret key to encrypt message ?. ? ??? ??,? . Homomorphic evaluation algorithm uses the evaluation key to produce an evaluated ciphertext ? . ? ???? ??,?,? . Decryption algorithm uses the secret key to decrypt ciphertext ?. ? ??? ??,? .

  4. Homomorphic Encryption: Correctness ???(??,???? ??,?,???(?)) = ?(?). ?(?) ? ??? ??? ? ? ????( ,?, )

  5. Homomorphic Encryption: Security Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Security against the curious cloud = standard IND- security of secret-key encryption Key Point: Eval is an entirely public algorithm with public inputs.

  6. Homomorphic Encryption: Compactness Fully Homomorphic Encryption: The size (bit-length) of the evaluated ciphertext and the runtime of the decryption is independent of the complexity of the evaluated function. A Relaxation (Leveled Homomorphic Encryption): The size (bit-length) of the evaluated ciphertext and the runtime of the decryption depends on the depth of the evaluated circuit.

  7. Big Picture: Two Steps to FHE Leveled Secret-key Homomorphic Encryption: Evaluate circuits of a-priori bounded depth d you give me a depth bound d, I will give you a homomorphic scheme that handles depth-d circuits Bootstrapping Theorem: From circular secure Leveled FHE to Pure FHE (at the cost of an additional assumption) I will give you homomorphic scheme that handles circuits of ANY size/depth

  8. How to Compute Arbitrary Functions For us, programs = functions = Boolean circuits with XOR (+ ??? 2) and AND ( ??? 2) gates. ???((?1+ ?2)?3?4) X ???(?3?4) ???(?1+ ?2) X + ???(?3) ???(?4) ???(?1) ???(?2) Takeaway: If you can compute XOR and AND on encrypted bits, you can compute everything.

  9. New (Secret-key) Encryption: Take 1 Private key: a vector s ?? ? Private-key Encryption of a bit ? {?,?}: ? ??+ ? ? C = (? is random (n+1) X n matrix) Decryption: [s || -1] C = m [s || -1] (mod q) Message = Eigenvalue Ciphertext matrix = Eigenvector Priv key INSECURE! Easy to solve linear equations.

  10. New (Secret-key) Encryption: Take 1 t . C = m . t (mod q) t = [s || -1] Homomorphic addition: C1+ C2 t is an eigenvector of C1+C2 with eigenvalue m1+m2 Homomorphic multiplication: C1C2 t is an eigenvector of C1C2 with eigenvalue m1m2 Proof: t . C1 C2= =(m1. t) . C2= = m1. m2 . t But, remember, the scheme is insecure? Key idea: fix insecurity while retaining homomorphism.

  11. New (Secret-key) Encryption: Take 2 Private key: a vector s ?? ? Private-key Encryption of a bit ? {?,?}: ? (? is random (n+1) X n matrix) C = ?? + ?+ ? ? Decryption: [s || -1] C m [s || -1] (mod q) Message = Approx Ciphertext matrix Priv key = Approx Eigenvector Eigenvalue CPA-secure by LWE.

  12. New (Secret-key) Encryption: Take 2 t . C = m . t + e (mod q) t = [s || -1] Homomorphic addition: C1+ C2 = ??1+ ??2 ? (?1+ ?2) = ?1 ? + ?1+ ?2 ? + ?2 Noise grows a little = (?1+?2) ? + ( ?1+ ?2) (?1+?2) ?

  13. New (Secret-key) Encryption: Take 2 t . C = m . t + e (mod q) t = [s || -1] Homomorphic multiplication: C1C2 Can also use ?2?1 ? (?1 ?2) = ?1 ? + ?1?2 = ?1 ??2+ ?1?2 = ?1?2 ? + ?2 + ?1?2 Noise grows. Need ?? to be small! How?! = ?1?2 ? + ?1 ?2+ ?1?2 ?????

  14. Aside: Binary Decomposition Break each entry in ? into its binary representation 0 1 1 0 0 1 1 0 1 1 0 0 ? =3 5 4 (??? 8) ???? ? = (??? 8) 1 Small entries like we wanted! Consider the reverse operation: ? log? 4 2 1 0 0 0 0 0 0 4 2 1 ???? ? = ? ? ? = ? ? ? 1(?) ? Denote: ? 1?which has small entries ?

  15. New (Secret-key) Encryption: Take 3 Private key: a vector s ?? ? Private-key Encryption of a bit ? {?,?}: ? (? is random (n+1) X n log q matrix) C = ?? + ?+ ? ? Decryption: [s || -1] C m [s || -1] G (mod q) Message = Approx Ciphertext matrix Priv key = Approx Eigenvector Eigenvalue Still CPA-secure by LWE.

  16. New (Secret-key) Encryption: Take 3 t . C = m . t. G + e (mod q) t = [s || -1] ?????= ?1 ? 1(?2) Homomorphic multiplication: ? ?1 ? 1?2 = ( ?1+ ?1 ? ?) ? 1?2 = ?1 ? 1?2 + ?1 ? ? ? 1?2 = ?1 ? 1?2 + ?1 ? ?2 = ?1 ? 1?2 + ?1 ( ?2+ ?2 ? ?) = ?1 ? 1?2 + ?1 ?2 + ?1?2 ? ? ????? ????? ? log ? ?1 + ?1 ?2 ? log ? + 1 max{ ?1, ?2}

  17. ??? ? = ? log ? Homomorphic Circuit Evaluation Noise grows during homomorphic eval Depth ? ??????? ??????? ? + 1? ?0 ???0 Decryptable if ? ???0. (for security: ? 2?) So this can support ? ??.?? ??+1 (? + 1) ?? ?????? ?0 ??????

  18. Big Picture: Two Steps to FHE Leveled Secret-key Homomorphic Encryption: Evaluate circuits of a-priori bounded depth d you give me a depth bound d, I will give you a homomorphic scheme that handles depth-d circuits Bootstrapping Theorem: From circular secure Leveled FHE to Pure FHE (at the cost of an additional assumption) I will give you homomorphic scheme that handles circuits of ANY size/depth

  19. From Leveled to Fully Homomorphic Input: x Function: f Enc(sk,x) ? Client Server (the Cloud) The cloud keeps homomorphically computing, but after a certain depth, the ciphertext is too noisy to be useful. What to do? Idea: Bootstrapping !

  20. Bootstrapping: How But the evaluator/cloud does not have SK! Best Possible Noise Reduction = Decryption! m Noiseless ciphertext ???( ,??) Very Noisy ciphertext SK Decryption Circuit

  21. Bootstrapping, Concretely Next Best = Homomorphic Decryption! * Assume server knows ek =EncSK(SK). (OK assuming the scheme is circular secure ) EncSK(m) ???( ,??) EncSK(SK)

  22. Bootstrapping, Concretely Next Best = Homomorphic Decryption! * Assume server knows ek =EncSK(SK). (OK assuming the scheme is circular secure ) Bdec Independent of Binput EncSK(m) Noise = Bdec Noise = Binput ???( ,??) EncSK(SK)

  23. Wrap Up: Bootstrapping Function f Assume Circular Security: Evaluation key is EncSK(SK) g

  24. Wrap Up: Bootstrapping Function f Assume Circular Security: Evaluation key is EncSK(SK) g Each Gate g Gadget G: g(a,b) g a b g(a,b) g ???( ,??) ???( ,??) a b sk sk

  25. Wrap Up: Bootstrapping Function f Assume Circular Security: Evaluation key is EncSK(SK) g Each Gate g Gadget G: Enc(g(a,b)) g a b g(a,b) g ???( ,??) ???( ,??) a b Enc(sk) Enc(sk)

  26. Major Open Problem Is circular security necessary? (or) Fully Homomorphic Encryption from LWE

  27. Unresolved Issue 1: Function Privacy Input: x Function: f Enc(sk,x) Enc(sk, f(x)) ? Client Server (the Cloud) Security against the curious cloud = standard IND- security of secret-key encryption Security against a curious user?

  28. Unresolved Issue 1: Function Privacy Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Function Privacy: Enc(f(x)) reveals no more information (about f) than f(x). Function privacy via noise-flooding (on the board)

  29. Unresolved Issue 2: Malicious Client Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Idea: Use zero knowledge proofs.

  30. Unresolved Issue 3: Malicious Cloud Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Idea: Succinct Interactive Proofs . [Kilian92]

  31. HOMOMORPHIC ENCRYPTION IN PRACTICE Many Open Source Libraries. PALISADE SEAL HELib HEEAN

Related


More Related Content