Homomorphic Encryption Overview
Homomorphic encryption allows computation on encrypted data without revealing the underlying information. It enables secure delegation of data processing to a server while maintaining privacy. The process involves key generation, encryption, decryption, and evaluation of functions on encrypted data. Security is achieved through semantic security, correctness, and compactness principles. Analogy with a jewelry store illustrates the concept of processing data without direct access. Different levels of homomorphic encryption include Somewhat Homomorphic Encryption (SWHE) and Fully Homomorphic Encryption (FHE). The paradox of cloud storage and encrypted files is addressed through semantic security considerations.
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
Homomorphic Encryption (Part I): SWHE Shai Halevi * Many slides taken from Craig Gentry May 18, 2015 Simons Institute, Cryptography Boot Camp
Computing on Encrypted Data Can we delegate the processing of data, without giving away access to it.
Encrypted Cloud Computing The special sauce! For security parameter , Eval s running should be Time(f) poly( ) Run I want 1) the cloud to process my data 2) even though it is encrypted. Eval[ f, Encpk(x) ] = Encpk[f(x)] Encpk(x) function f Server (Cloud) This could be encrypted too. Alice Delegation: Should cost less for Alice to encrypt x and decrypt f(x) than to compute f(x) herself. (Input: data x, secret key sk) f(x) Encpk[f(x)]
Homomorphic Encryption (HE) Procedures: KeyGen, Encrypt, Decrypt, Eval Semantic Security: same as for basic encryption Correctness: For any function f in supported family F: c1 Encpk(m1) ct Encpk(mt) c* Evalpk(f, c1, , ct) Decsk(c*) = f(m1, , mt) Compactness: complexity of decrypting c* does not depend on complexity of f
An Analogy: Alices Jewelry Store Alice wants workers to assemble raw materials into jewelry But Alice is worried about theft: She wants workers to process raw materials without having access. Alice puts raw materials in locked glovebox. Workers assemble jewelry inside glovebox, using the gloves. Alice unlocks box to get results .
Homomorphic Encryption Somewhat means it works for some functions f f Enc[x] Somewhat Homomorphic Encryption (SWHE): Eval Enc[f(x)] Pre-2009 schemes were somewhat homomorphic.
Homomorphic Encryption Fully means it works for all functions f f Enc[x] Fully Homomorphic Encryption (FHE) [RAD78, Gen09]: Eval Enc[f(x)]
HE Security: A Paradox? Cloud stores my encrypted files: pk, Encpk(f1), , Encpk(fn). Later, I want f3, but want to hide 3 from cloud. I send Encpk (3) to the cloud. Cloud runs Evalpk (F, Encpk(3), Encpk(f1), , Encpk(fn)), where F(n, {files}) is the function that outputs the nth file. It sends me the (encrypted) file f3. Paradox?: Can t the cloud see it is sending the 3rd encrypted file? By comparing the stored value Encpk(f3) to the ciphertext it sends? Resolution of paradox: Semantic security implies: Many encryptions of f3, Hard to tell when two ciphertexts encrypt the same thing.
Some Properties Chosen-ciphertext security: HE is malleable by design, standard CCA security cannot be achieved Can get CCA1other security notions (e.g. homomorphic sigs) Multi-hop: Can we apply Eval to evaluated ciphertexts? Usually yes, but not inherently so Function privacy: Does Evalpk(f, ) hide f? Even from an adversary that has the secret key? This can be arranged Malicious security: What if pk, c are malformed?
Secret-key vs. Public-key HE A helpful aside: for homomorphic encryption, public-key and secret-key are essentially the same Theorem [R11]: There is an easy black-box transformation from secret-key HE to public-key HE Public key: random bits and their encryptions ?1,?1, , ? ,? , ??= ?????(??) is chosen larger than the cipehrtext-size, |??| To Encrypt a bit ?, choose a random bit-string ? such that ????= ?, output ? = ??=1??= ???( ????) ?? =
Transforming HE from SK to PK ?? = ?,? , ??= ?????(??) ? = |??| Enc(?): choose random ? 0,1 s.t. ?,? = ? output ? = ??=1??= ??? Correctness: immediate from additive homomorphism Security: The transformation ? ? is lossy If the ?? s were encryptions of zero then secrecy of ? would follow from leakage resilience of inner-product By security of the underlying secret-key scheme, adversary cannot tell if the ?? s are encryptions of zero ?,?
FHE Doesnt Do Obfuscation Obfuscation: I give the cloud an encrypted program Enc(P). For any input x, cloud can compute Enc(P)(x) = P(x). Cloud learns nothing about P, except {xi,P(xi)}. Difference between obfuscation and FHE: In FHE, cloud computes Enc(P(x)), and it can t decrypt to get P(x). Barak et al: On the (Im)possibility of Obfuscating Programs Certain types of obfuscation are impossible. Garg et al: Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits Certain types of obfuscation seem possible (we have schemes).
FHE Doesnt Do RAM Circuits vs. RAMs: Circuits are powerful: Circuit-size TM complexity. But random-access machines compute some functions much faster than a TM or circuit (Binary search) Can t do random access on encrypted data without leaking some information (not surprising) What we can do: Oblivious RAM: But this is a very interactive protocol between client and server where server can t tell what client is computing Use Obfuscation to do ORAM: Intuitively, obfuscation allows addresses in memory to be revealed noninteractively .
FHE Doesnt Do Multi-Key Multi-Key FHE Different clients encrypt data under different FHE keys ci Encpki(mi) Later, cloud combines data encrypted under different keys to get c* Eval(pk1, pkt,f,c1, ct). Can decrypt c* to f(m1, ,mt) by pooling sk1, sk FHE doesn t do this automatically . But there are some schemes that do this
Constructing SWHE How to compute on encrypted data? Express functions to compute as a binary circuit with +, That s always possible Design a bit-encryption scheme that supports addition, multiplication of encrypted bits That s the hard part 1. 2.
A Toy HE Scheme (from American Scientist magazine) Encryption: Double the plaintext. x 2x Decryption: Halve the ciphertext. x x/2
About Homomorphism Name inspired by ring-homomorphism Ring of ciphertexts Ring of plaintexts Enc Commutative Diagram +, , Ring of ciphertexts Ring of plaintexts Enc
About Homomorphism Name inspired by ring-homomorphism Ring of ciphertexts Ring of plaintexts Enc Homomorphism should not be taken too literally Else zero-encryptions form a linear subspace (ideal) Is it possible to hide such an ideal? Some attempts (e.g. Polly Cracker), but broken
Noisy Ciphertexts Each ciphertext has some noise that hides the message. Think: hidden error correcting codes If error is small, Alice can use knowledge of hidden code to remove the noise. If noise is large, decryption is hopeless even for Alice.
Example: SWHE over the Integers Main Idea Encryptions of 0 are something small and even modulo a secret integer. Secret key: large odd integer n Public key: integers ??= ??? + 2?? ? , ?? ? These are encryptions of 0 Encrypt: Subset-sum of ?? s, then add ? {0,1} ? = ? ???= ??? ? + 2 ???+ ? Decrypt: ? ??? ? = 2? + ?, LBS is message ? ADD, MULT: sum/product over the integers
Security of SWHE with Integers Reduction: If approximate gcd problem is hard, then the scheme is semantically secure. Approximate GCD Problem: Given many ??= ??? + ?? (approx multiples of ?), find ?.
The Noise Problem ADD: c = c1+c2. Noise of c is [c mod n] = [c1mod n] + [c2mod n] Unless this sum is bigger than n (decryption error). MULT: c = c1 c2. Noise [c mod n] is product of noises, unless product > ?. ?1? + ?1 ?2? + ?2 = ?1?2? + ?1?2+ ?2?1? + ?1?2 Function ?: ? = ?(?1, ,??). Noise [? mod ?] = f([?? mod ?]?) i.e., ? applied to noises. Rough approximation: Noise magnitude increases exponentially with degree of ?.
The Noise Problem Hurts Efficiency. Why? Ciphertexts must be large to let noise room to grow . Noise grows exponentially with degree. Bit-length of noise grows linearly with degree. Ciphertext size grows linearly with degree.
Somewhat Homomorphic Encryption Based on LWE Focusing on the Gentry-Sahai-Waters scheme. (Brakerski and Vaikuntanathan were the first to construct HE based on LWE.)
Regevs Encryption Scheme KeyGen(1?): Choose secret key ? = 1,?? ?? Public key: ? ?? ? ? ? random except ? ?? small Encrypt(?,? {0,1}): For random ? 0,1? output ? ?,0, ,0 ? 2+ ? ? Decrypt(?,?): Compute ?,? = ? ? 2+ ? ? ? = ? ? ?,? 2+ small (mod q) Recover ? as MSB ?
Properties of Regevs Scheme Vectors: Ciphertext ? and secret-key ? are vectors over ??, the1st entry in t is 1 Small dot-product: If ? encrypts ? under ? then ?,? ?= ? ? 2+small Ciphertexts are pseudorandom: Under the hardness of decision-LWE, ciphertext are indistinguishable from uniform vectors over ?? To an attacker who doesn t know the secret key
Homomorphic ADD in Regev Additive Homomorphism: Add ciphertexts ?= ?? ? 2+ smalli then If ??,? ?= ?1+ ?2 ? 2+small ?1+ ?2,? (if original small s were small enough)
Homomorphic MULT in Regev Mulitplicative homomorphism: multiply cipehrtexts? How do you multiply vectors? Tensor product? For ? = ?1, ,??,? = (?1, ,??), the tensor is ? ? = (?1?1, ,????) Fact: ?? ??,? ? = ??,? ??,? (mixed prod.) ?? ?? can be seen as encrypting ?1 ?2 under ? ? Efficiency problem: MULT squares the dimension Brakerski and Vaikuntanathan made this work Turn ciphertexts into matrices? Use matrix product
Matrix Version (1st try) ? KeyGen: As before, secret key ? = 1,? ?? ? ? Encrypt(? {0,1}): Choose ?0 ?? Rows are Regev-encryption of 0, ?0 ? =small Output C = ? ? + ?0 (? is the identity) Security: ?0 is pseudorandom (hence also ?) Decryptt(C): Compute ? = ? ??= ? ? + ?0 ? = ? ? +small Output 0 if ? is small, 1 if ? is close to ? Secret key ? is approximate eigenvector of ? Message ? is the corresponding eighenvalue
Homomorphism in Error-Free Setting Ciphertext Matrix Message Eigenvalue Secret Key Eigenvector If ?? ? = ?? ? ??? ? Then ?1+ ?2 ? = ?1+ ?2 ? (??? ?) And ?1 ?2 ? = ?1 ?2 ? (??? ?)
Homomorphism with Error (1st try) ?? ? = ?? ? + ?? (??? ?) for ? = 1,2 Addition: ?1+ ?2 ? = ?1+ ?2 ? + (?1+ ?2) Multiplication: ? = ?1 ?2 ? ? = ?1 ?2 ? = ?1 ?2 ? + ?? = ?2 ?1 ? + ?1 ?? = ?2 ?1 ? + ?1 + ?1 ?? = ?1 ?2 ? + ?2 ??+ ?1 ?? (??? ?) New Noise
Controlling the Noise New Noise ? ? = ?1 ?2 ? + ?2 ??+ ?1 ?? Keep messages ? small: Easy! Restrict messages to {0,1} and use NAND gates Keep ciphertext entries small: Can we flatten the product matrix ? to make its entries small?
Gadget for Flattening ? ? with associated ? ? ?? Use Gadget Matrix ? ?? inverse transformation ? 1:?? Used for lattice trapdoors [A99, ,MP12] ? ? ? ?: For any ? ?? ? 1? ?? ? 1? ? = ? ? ? is small
Example of a Gadget Matrix ? 1? breaks each entry in C to its bits 7 2 4 5 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 4 2 1 1 3 4 2 1 0 0 0 ? has powers of two, G =
Modified Matrix Encryption ? ? such that + ? Encryption of ? is a matrix ? ?? ? ? = ? (? ?) ? Easy to modify Enc to get this form Set ? = ? ? + ?0 rather than ? = ? ? + ?0 Security follows from LWE as before Additive homomorphism works just as before
Homomorphic Multiplication ?? ? = ?? ? + ?? for ? = 1,2 (? = ? ?) Set ? = ? 1(?1) ?2 = ? 1?1 ?2 ? = ? 1?1 ?2 ? + ?2 = ?2 ? 1?1 ? ? + ? 1?1 ?? = ?2 ?1 ? + ? 1?1 ?? ? ?
Homomorphic Multiplication ?? ? = ?? ? + ?? for ? = 1,2 (? = ? ?) Set ? = ? 1(?1) ?2 = ? 1?1 ?2 ? = ? 1?1 ?2 ? + ?2 = ?2 ? 1?1 ? ? + ? 1?1 ?? = ?2 ?1 ? + ? 1?1 ?? = ?2 ?1 ? + ?? + ? 1?1 ?? = ?1?2 ? + ?2 ??+ ? 1?1 ?? ? ? (??? ?) small New Noise
Summary of GSW Encryption of ? is ? ? = ? ? + ? (? = ? ?) Additive homomorphism: ?+= ?1+ ?2 New noise is ?+ ??+ ?? 2 max( ??) Multiplicative homomorphism: ? = ? 1(?1) ?2 New noise is ? ?2 ??+ ? ?? ? + 1 max(|??|) Somewhat homomorphic: can evaluate circuits with log?+1? levels
