Let F be a pseudorandom function and G be a psuedrandom generator with expansion
ID: 3722873 • Letter: L
Question
Let F be a pseudorandom function and G be a psuedrandom generator with expansion factor 1(n) n +1. For each of the following encryption schemes, state whether the scheme has indistinguishable encryptions in the presence of an eavesdropper and whether it is CPA-secure. (In each case, the shared key is a uniform k E 0, 1]".) Explain your answer (a) To encrypt m E {0, 1)"+1, choose uniform r {0, 1)" and output the ciphertext(r, G(r)m). (b) To encrypt m E {0, 1}2n, output the ciphertext m D Fk(On). (c) To encrypt m E 10, 1^2n, parse m as m1| m2 with m1- m2|, then choose uniform r 10,1)" and send r, mi F. (r), m2Fe(r + 1).Explanation / Answer
As per your requirement the below one is solution please follow it
Random key k <- {0,1}n and message m<- {0,1}n+1 <- {0,1}l(n)
(a) Here G(k)= Fk(0k)||Fk(1k) is the pseudorandom generator.
To see this, Let D be the PPT distinguishing algorithm,
Assume that algorithm A attacking the pseudorandom function F:
i) A(1n) has access to an oracle O.
ii) It queries r1=O(0n) and r2=O(1n), runs D(r1||r2).
A runs in polynomial time, When O=Fk for some k, then r1||r2=G(k).
So Prk<-{0,1}n[AFk(.)(1n)=1]=Prk<-{0,1}n[D(G(k))=1].
When O is random function then r1||r2 is uniformly distributed. thus,
Pf<-Randn->n[Af(.)(1n)=1]=Prr<-{0,1}2n[D(r)=1].
Since Fis a pseudorandom function, Prk<-{0,1}n[AFk(.)(1n)=1]=Prf<-Randn->n[Af(.)(1n)=1] must be negligible.
(b) Here G(k)= k||Fk(0k) is not a pseudorandom generator and an attack D.
Given r of length 2n, parse it as two n-bit strings k||t. Output 1 if Fs(0n)=t.
This attack runs in polynomial time.
Prk<-{0,1}n[D(G(k))=1]
On the other hand, if r=k||t is random then the probability is equal to Fs(0n)=t is exactly 2-n and so
Prk<-{0,1}n[D(r)=1] = 2-n . This attack succeeds with non negligible probability 1-2-n .
(c) Fk1(x)=Fk(x) and Fki(x)=Fk(Fki-1(x)) for i>1.
Here for a fixed polynomial p, pseudogenerator G(k,x)=Fk1(x)||.....||Fk(i-1)(x).
Assume that algorithm A attacking the pseudorandom function F:
i) A(1n) has access to an oracle O.
ii) A chooses x<- {0,1}n and queries r1=O(x), r2=O(r1),........,rp=O(rp-1). It runs D(r1||....rp).
When O=Fk for some k, then r1||....||rp =G(k,x) and therefore Prk<-{0,1}n[AFk(.)(1n)=1]=Prk,x<-{0,1}n[D(G(k,x))=1].
Pr[i!=j:ri=rj]<=p(n)2/2n is negligible. Prk,x<-{0,1}n[D(G(k,x))=1]<= negl'(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.