Fully Homomorphic Encryption: Foundations and Applications
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.
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
MIT 6.875 Foundations of Cryptography Lecture 20
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 ?. ? ??? ??,? .
Homomorphic Encryption: Correctness ???(??,???? ??,?,???(?)) = ?(?). ?(?) ? ??? ??? ? ? ????( ,?, )
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.
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.
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
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.
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.
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.
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.
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) ?
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 ?????
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 ?
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.
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}
??? ? = ? 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 ??????
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
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 !
Bootstrapping: How But the evaluator/cloud does not have SK! Best Possible Noise Reduction = Decryption! m Noiseless ciphertext ???( ,??) Very Noisy ciphertext SK Decryption Circuit
Bootstrapping, Concretely Next Best = Homomorphic Decryption! * Assume server knows ek =EncSK(SK). (OK assuming the scheme is circular secure ) EncSK(m) ???( ,??) EncSK(SK)
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)
Wrap Up: Bootstrapping Function f Assume Circular Security: Evaluation key is EncSK(SK) g
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
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)
Major Open Problem Is circular security necessary? (or) Fully Homomorphic Encryption from LWE
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?
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)
Unresolved Issue 2: Malicious Client Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Idea: Use zero knowledge proofs.
Unresolved Issue 3: Malicious Cloud Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Idea: Succinct Interactive Proofs . [Kilian92]
HOMOMORPHIC ENCRYPTION IN PRACTICE Many Open Source Libraries. PALISADE SEAL HELib HEEAN
