New version page

BU CS 937 - Fully Homomorphic Encryption - Part II

Documents in this Course
Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

6.889: New Developments in Cryptography February 15, 2011Fully Homomorphic Encryption - Part IIInstructor: Boaz Barak Scribe: Elette Boyle1OverviewWe continue our discussion on the fully homomorphic encrypt i on s cheme of van Dijk, Gentry, Halevi,and Vaikuntanathan [vDGHV10]. Last week we constructed a weakly homomorphic encryptionscheme such that for any pair of properly generated ciphertext s c ← Enc(b),c�← Enc(b�), the sumor product of c, c�yields a value that decrypts to the sum (resp, product) of the origin al underlyingplaintexts. That is, Dec(Add(c, c�)) = b ⊕ b�and Dec(Mult(c, c�)) = b · b�. However, the schemesuffered from two proble ms: 1) the cipertext formed as the output of th e Add or Mult operationdoes not have the same distr i b ut i on as a ciphertext properly generated via the Enc algorithm, and2) if we try to perform too many Add and Mult operations, we are no longer guaranteed decryptionto th e correct value (indeed, in the scheme, the noise in the ciphertext grows larger in each operationand will eventually lead to a nonempty intersection of the set of encryptions of 0 and 1).As we discussed last week, these two problems will be solved if we can construct the followingtwo operations:• ReRand(X): takes as input any encryption of a bit b wit h noise ≤ 2n0.4(for example, in ourscheme this includes the bit b itself!) and outputs a ciphertext with noise ≤ 2n0.5with t hecorrect distribution ReRand(X) ≈sEnc2n0.5(b).• Clean(X): takes as inpu t a ciphertext with noise ≤ 2n0.9and outputs a ciphertext for thesame message with noise ≤ 2n0.3. That is, it reduces the noise of the ciphertext.Further, when combined with the original scheme, these operations will ac t ual l y give us a fullyhomomorphic en cr y pt i on scheme, by cleaning and rerandomizing the resulting ciphertext afterevery operation.We showed how to do ReRand last week. Today, our focus will be on the more complicatedoperation: Clean.2ReviewfromlastweekWe briefly review some information from last lecture. For formal defini t i ons and discu ssi on s ofthese items, we refer the reader to the p r ece di n g set of scribe notes.2.1 Notation1. We use lowercase letters (such as t) for valu es that are polynomial in the security parametern, and capital lett er s (such as N, P , Q, and R) for large numbers that h ave poly(n) digits(and hence are exponential in the security parameter n).2. ZN: We denote by ZNthe set {0,...,N − 1} and by Z∗Nthe set {X ∈ ZN: gcd(X, N)=1}.3-13. P(C): For a circuit C,wedefineP(C) to be the polynomial Zm→ Z that C computes.4. |f|M: For a polynomial f : Zm→ Z and M ≥ 0, we define |f|Mto be the maximum valueattained by f over all possible inputs of size ≤ M:|f|M= maxx1,...,xm|xi|≤M|f(x1,...,xm)|.5. EEN,P(b): We denote by EEN,P(b)={X : X = RP +2E + b (mod N),R∈ ZQ,E∈ [−E, +E]}the set of possible encryptions of b with parameter E, public parameter N, and secret key P .2.2 The weakly homomorphic schemeThe weakly homomorphic scheme (Gen, Enc, Dec, Add, Mult) is defined as follows.Key Generation: Draw a random n-bit prime P and a rand om n4-bit prime Q.SetN = PQ,keep P as the secret key, and publish N as a public parameter.Encryption: For b ∈{0, 1},weletEncN,P(b)=Enc2√nN,P(b), where EncEN,P(b) is the distributiondefined as follows: choose R ←RZQand E ←R[−E, +E], and out put X = RP +2E + b(mod N).Decryption: To decrypt X, output X −�X/P � P (mod 2). ( W he re �x� denotes the integer closestto x.) In ot h er words, find the nearest multiple of P to X, subtract it away to get the noise,and then the parity of the noise i s the decrypted bit.Addition: Given ciphertexts X, X�, output AddN(X, X�)=X + X�(mod N).Multiplication: Given ciphertexts X, X�, output MultN(X, X�)=X · X�(mod N).We refer the reader to last week’s notes for a proof of semantic security of the scheme based onthe Learning Divi sor with Noise assumpti on (in addition to the definition of this assumption), andproof that the scheme satisfies a “noisy” h omomor ph i sm property.3 Bootstrapping to a Fully Homomorphic Scheme3.1 Clean and ReRand operationsAs we discussed, to make the scheme fully homomorphic, it will suffice to add the following twooperations.• Clean(X) will take as i n pu t a ciphertext in E2n0.9(b) and output a ci ph er t ex t in E2n0.3(b).That is, it reduces the noise of the cipher t ex t .• ReRand(X) will take as input a ciph er t ex t in E2n0.4(b) and output a ciphertext that distributedstatistically close to the uniform distribution over E2√n(b), that is, ReRand(X) ≈sEnc(b).3-2Fully homomorphic en cr y pt ion Together Cle a n and ReRand imply a fully homomorphic en-cryption scheme: we just change the definition of Mult and Add to apply Clean and ReRand asfollows:• Add(X, X�)=ReRand(Clean(X + X�(mod N))).• Mult(X, X�)=ReRand(Clean(X · X�(mod N))).Note that in an actual implementation, we can increase efficiency by performing several additionsand multiplications back-to-back, running a Clean only when the noise gets too large. The ReRandoperation also only needs to be run a single time at the very end of the calculation.3.2 Teaser: L uca s ’s TheoremWe will use the following result later in the proof of correctness of Clean. To simplify the discussion,we present the proof now and simply make reference to i t later.Theorem 3.1 (Lucas). If a =�aipiand b =�bipifor some integer p and ai,bi∈ [0,p) ∩ Z,then�ab�≡��aibi�(mod p).Proof. We show the claim by equ at in g the coefficient of xbin the following two expansions of theformal polynomial (x + 1)a(mod p):�k�ak�xk=(x + 1)a=(x + 1)�iaipi=�i(x + 1)aipi≡�i(xpi+ 1)ai(mod p).On the left-hand side, the coeffici ent of xbis simply�ab�. On the right-hand side, since each ai<p,the only way to form xbis to take the xbipiterm from the ith factor (xpi+ 1)ai. The coefficient ofxbipiin the it h factor is precisely�aibi�. Thus, the coefficient of xbin the entire right-hand expansionwill be�i�aibi�, as desired.3.3 Getting Clean using “wishful thinki ng”Last week we started discussin g how one could go about implementing the Cle a n functionality.Obtaining Clean appears to be very challenging, because, up until this point, any operation thatwe per for me d on ciphertext s (such as adding, multiplying, or re-randomizing) only increased thenoise. In fact, it seems somewhat counterintuitive that we could decrease the


View Full Document
Download Fully Homomorphic Encryption - Part II
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Fully Homomorphic Encryption - Part II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Fully Homomorphic Encryption - Part II 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?