Report

Andrej Bogdanov Chinese University of Hong Kong ON THE PROVABLE SECURITY OF HOMOMORPHIC ENCRYPTION based on joint work with Chin Ho Lee Northeastern Unversity Bertinoro Summer School | July 2014 Public-key bit encryption b Alice EncPK(b) PK EncPK(b) Bob SK PK DecSK( b ) message indistinguishability (PK, EncPK(0)) and (PK, EncPK(1)) are computationally indistinguishable El Gamal encryption g, h in some large cyclic group PK = ( g, h ) such that gSK = h EncPK(b) = ( gr, 2bhr ) where r random DecSK(x, y) = b such that xSK = 2b y Homomorphism of encryptions EncPK(b) = ( gr, 2bhr ) strongly homomorphic EncPK(b) EncPK(b’) and EncPK(b + b’) are identically distributed weakly homomorphic DecSK(EncPK(b) EncPK(b’)) = b + b’ Does P ≠ NP imply cryptography? requires average-case hardness of distinguishing encryptions provided SAT is worst-case hard Cryptography from lattices If short vectors in certain lattices are worst-case hard to find, then we have... one-way functions Ajtai but we can find them public-key encryption in NP ∩ coNP Ajtai-Dwork “somewhat” homomorphic encryption Regev, Peikert, Gentry, Brakerski and Vaikutanathan, ... Reductions How to prove message indistinguishability? ? x SAT q1 a1 q2 a2 YES/NO (PK, EncPK(b)) distinguisher biased towards b From reductions to proof systems L R distinguisher verifier prover randomness for R transcript is it correct? for every query (PK, C) answer b are they correct? randomness r s.t. EncPK(b, r) = C OK Brassard From reductions to proof systems Conclusion A reduction from L to distinguishing Enc implies that L is in NP ∩ coNP Yes, but under implicit assumption that queries always have a unique answer Goldreich and Goldwasser Brassard’s assumption for every PK what if EncPK(1) EncPK(0) query EncPK(1) EncPK(0) EncPK(1) EncPK(0) Restricting the reduction For general encryptions, best we can say If reduction is nonadaptive then L is in AM ∩ coAM Feigenbaum and Fortnow, B. and Trevisan, Akavia Goldreich Goldwasser and Moshkovitz Our result Let f be a “polynomially sensitive” function If Enc has weak homomorphic evaluator for f, then L is in AM ∩ coAM Reduction can be adaptive, queries arbitrary If reduction has constant query complexity, then L is in statistical zeroknowledge Sensitivity of functions f: 0 1100 1 0110 0 1 0101 sens0 f(0100) = 2 sens0 f = maxx sens0 f(x) 0100 f: {0, 1}n → {0, 1} is polynomially sensitive if sens0 f, sens1 f are at least nW(1) previous works Arbitrary encryptions, nonadaptive reductions Homomorphic encryptions, arbitrary reductions SAT SZK P Homomorphic encryptions, reductions of constant query complexity Rerandomization The ability to map a ciphertext into an i.i.d ciphertext without knowing the secret key El Gamal example PK = ( g, h ) such that gSK = h C = ( gr, 2bhr ) RerPK(C) = C ∙ ( gr’, hr’ ) is i.i.d with C Enc(1) Enc(1) Enc(1) Enc(b) Enc(0) Enc(0) Rer Enc(0) Rerandomization from evaluation H Enc(b) strong homomorphic evaluator for majority Enc(0) Enc(0) Enc(0) Enc(0) Rerandomization from evaluation H To H, Enc(0) indistinguishable from Enc(0) so output of H must forget most of Enc(0) Rerandomization from evaluation Lemma If H is a strong homomorphic evaluator for majority on k bits, then (Enc(b), Rer(Enc(b)) is √c/k-close to a pair of independent encryptions of b. We prove a weaker version for weak homomorphic evaluators and any sensitive f. Distinguishing rerandomizations Encryption can be broken using rerandomization and an SZK oracle Rer( Enc(b) ) vs. Enc(0) If b = 0, they are statistically close If b = 1, they must be statistically far so they can be distinguished in SZK The rest of the proof Since we can decrypt in SZK, L can be solved with reduction + SZK oracle So L is in BPPSZK ⊆ AM ⋂ coAM Mahmoody and Xiao For weak homomorphism and general f, not sure if true; we give new proof system Quality of rerandomization Lemma If H is a homomorphic evaluator for majority on k bits, then (Enc(b), Rer(Enc(b)) is √c/k-close to a pair of independent encryptions of b. For strong homomorphic evaluation, we can make this exponentially small. H Enc(b) Enc(1) Enc(b) Enc(0) Improving the rerandomization Algorithm: Apply H iteratively t times. Enc(1) H Enc(b) Enc(0) H Enc(b) H H H Enc(b) Enc(1) Enc(0) Enc(0) Enc(1) Enc(0) Enc(0) Enc(1) Enc(1) Enc(1) Enc(b) Enc(0) Analysis H Enc(1) H H H Enc(1) Enc(1) Enc(0) Enc(0) Enc(1) Enc(0) Enc(0) Enc(1) Enc(1) Enc(1) Enc(1) Enc(0) Analysis Analysis If we recurse t times, original Enc(b) could be any one of 2t inputs Applying lemma, distinguishing advantage drops to O(√c/2t) Value of t is determined by quality of H Statistical distance between output of H and actual encryption Rerandomization theorem f : any function except for AND, OR, NOT Assume f has strong homomorphic evaluator with quality 2-h then there is a rerandomization with statistical error 2-W(h).