PRGLecture 4Introducing Hybrid Arguments. One-Way Permutations and Hardcore Predicates1Computational IndistinguishabilityTwo distribution ensembles {Xk}k and {X’k}k are called computationally indistinguishable if negligible ν(k) such that ΔPPT(Xk,X’k) ≤ ν(k)ΔPPT(Xk,X’k) := max PPT D ( Prx←Xk[D(x)=1] - Prx←X’k[D(x)=1] )(Dropped the absolute value sign, w.l.o.g)Recall 2Computational SecurityMulti-message shared-key encryptionEquivalent Security definitions: Computational Secrecy, SIM-CPA security, IND-CPA securityPseudorandomness Generator (PRG)So that we can build “stream ciphers” (to encrypt a stream of data, using just one short shared key)PRG with fixed stretch: Gk: {0,1}k → {0,1}n(k), n(k) > kIND-PRG: PPT adversary can’t distinguish between a sample from {Gk(x)}x←{0,1}k and from {0,1}n(k)NBU-PRG: PPT adversary can’t predict ith bit of a sample from its first (i-1) bits (i=0 to n-1)Recall 3IND-PRG and NBU-PRG are equivalentEasy to see that if G satisfies IND-PRG security, then it satisfies NBU-PRG security (Exercise)Converse: NBU-PRG is enough to imply IND-PRG!Predicting some bit from its prefix is a “complete attack!”Introducing the “Hybrid argument”4NBU-PRG IND-PRGSuppose G: {0,1}k → {0,1}n is an NBU-PRGWant to prove that the following distributions are indistinguishableH(0) = Random = {r1,r2, ... rn} r←{0,1}nH(n) = G(random) = {y1,y2, ... yn} x←{0,1}k; (y1...yn) := G(x)Consider a series of “hybrid” distributionsH(i) = {y1,y2, ... yi, ri+1, ... rn} x←{0,1}k; (y1...yn) := G(x); r←{0,1}nWill show: G NBU-PRG secure H(i) ≈ H(i+1)Then show that (bounded) transitivity holds for ≈ so that H(0) ≈ H(n)5NBU-PRG IND-PRG“Hybrid” distributions, for i = 0 to nH(i) = {y1,y2, ... yi, ri+1, ... rn} x←{0,1}k; (y1...yn) := G(x); r←{0,1}nH(0) = Random; H(n) = G(random)To prove: G NBU-PRG secure H(i) ≈ H(i+1)An adversary A for ε-distinguishing H(i) and H(i+1) (for any i) implies a next-bit predictor A* (for that i) with advantage ε6NBU-PRG IND-PRGGiven a PPT adversary A for distinguishing H(i) and H(i+1) to create a next-bit predictor A* with comparable advantage and running timeSay A s.t. Prh←H(i+1)[A(h)=1] - Prh←H(i)[A(h)=1] = εConsider A*: on input (y1 ... yi)set h := (y1 ... yi ri ri+2 ... rn) where rj’s are random bitsRun A on input hIf A outputs 1: output prediction riElse: output prediction 1-riA* has advantage ε (Exercise)Probability also over A’s coin-tosses7NBU-PRG IND-PRG“Hybrid” distributions, for i = 0 to nH(i) = {y1,y2, ... yi, ri+1, ... rn} x←{0,1}k; (y1...yn) := G(x); r←{0,1}nH(0) = Random; H(n) = G(random)To prove: G NBU-PRG secure H(i) ≈ H(i+1)An adversary A for ε-distinguishing H(i) and H(i+1) (for any i) implies a next-bit predictor A* (for that i) with advantage ε✔G NBU-PRG secure next-bit predictor can have only negligible advantage. So ε is negligible. (For every PPT A.)So H(i) ≈ H(i+1)8Hybrid Argument“Hybrid” distributions, for i = 0 to nH(0) = Random; H(n) = G(random); H(i) ≈ H(i+1)Can we conclude H(0) ≈ H(n) ?Yes, when n(k) is polynomialPrx←H(0)[D(x)=1] - Prx←H(n)[D(x)=1] = Σi Prx←H(i)[D(x)=1] - Prx←H(i+1)[D(x)=1] ≤ Σi νi(k) = ν(k)Hence if G is NBU-PRG then G is IND-PRGSum of polynomially many negligible functions is negligible9Hybrid ArgumentTo argue two distributions X and Y (ensembles, of course) are (computationally) indistinguishableSet up hybrids so that Extreme hybrids coincide with X and YAdjacent hybrids differ in a simple way: need to be able to show them indistinguishable from each otherEnsure total number of hybrids is polynomialUseful also for distributions generated by complex systemsHybrids by modifying the system one part at a time10Constructing a PRG Stretch of a PRG = |output| - |seed| (i.e. n(k) - k)Construct a PRG with one-bit stretchWill use the NBU-PRG definitionGo from one-bit stretch PRG to multiple-bit stretch PRGWill use the IND-PRG definitionGkk1Rk11Constructing a PRG Given PRG G(s). Let G(s) = G1(s)G2(s) with |G2(s)| = |s|Let G’(s) = G1(s) G1(G2(s)) ... G1(G2i(s)) ... G2t(s)Claim: G’(s) is a PRG (with stretch t times that of G)Proof: Hybrid argument!What are the hybrids?Increasing the StretchG G G G...GRkGkk1Rk12Constructing a PRG Hybrid i: first i bits and seed for i+1st G truly randomH(0) is G’(s); H(n) is truly randomReduction: If A can distinguish between adjacent hybrids with advantage ε, then show an A* which can distinguish between output of G and random≈Increasing the StretchR1RkG G...R1R1G G...R1R1R1RkGRkGkk1Rk13Constructing a PRG GMUXRkR1RkG G...R1R1Increasing the Stretchb’bA*AWhen b=0, A given ith hybrid, else i+1stAdvantage of A* = Advantage of A14Constructing a PRG Stretch of a PRG = |output| - |seed| (i.e. n(k) - k)Construct a PRG with one-bit stretchWill use the NBU-PRG definitionGo from one-bit stretch PRG to multiple-bit stretch PRGWill use the IND-PRG definitionGkk1Rk✔15First k bits, output the seed? (For 0-stretch this works.)Observation: seed must be hiddenIn fact, that output is in the range of PRG must be hiddenIf truly random, in that range with at most half probabilitySuppose first k bits a permutation f of the seed sThe last bit B(s) must be hard to predict from the permutation f(s)The permutation f must be hard to invertConstructing a PRG One-bit Stretch PRG16One-Way PermutationThe permutation f must be hard to invertPPT adversary can invert f (on a random point) with at most negligible probability f must be an easy to compute permutationf: {0,1}k → {0,1}k is a one-way permutation (OWP) iff a permutationf polynomial time computableFor all PPT adversary, probability of success in the OWP experiment is negligiblex←{0,1}kx’ = x?f(x)x’Yes/No17One-Way PermutationDo OWPs exist?If P = NP, then no OWP!NP problem: find a “witness” that satisfies an easy to verify relation(Really only need to see if witness exists; but that can be used to find the witness too.)Given z, find x s.t. f(x)=z: Easy to verify relation between x and zIf P = NP, witness can be found in polynomial timex←{0,1}kx’ = x?f(x)x’Yes/No18One-Way PermutationDo OWPs exist?Even if P ≠ NP, and inverting f not in P, f may not be a OWPNot in P: May be hard to invert f in a small fraction of the spaceBut we need almost-always hardness!But several candidates availableTill date no efficient algorithm to invert them with significant probabilityExamples
View Full Document
Unlocking...