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 .

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).

Navigate

Let F be a field. Recall that if f(T) and g(T) are polynomials in F[T] such that

Let F be a random variable with the Fn,m distribution and G be a random variable

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let F be a pseudorandom function and G be a psuedrandom generator with expansion

Question

Explanation / Answer

Related Questions

Navigate