28.4k views
0 votes
True/False

1) Let f be an arbitrary function, publicly known and documented. Let s be a uniform, secret seed of length n-bit. Is G(s)= s||f(s) a pseudorandom generator (PRG)?
2) Let G be a PRG. H(s)= G(s)||G(s). Is H a PRG?
3) CPA security implies that it should be hard to determine the key from seeing the encryption of chosen plaintexts.
I would appreciate if anyone who gives me all three true/false solutions!:)

User StefanBob
by
7.8k points

1 Answer

2 votes
1) False. The construction G(s) = s||f(s) is not a pseudorandom generator (PRG) in all cases. The reason is that if an adversary knows and has access to the public function f, they can simply compute f(s) for any seed s and distinguish the output of G(s) from a truly random output.

2) True. Since G is a pseudorandom generator and H is constructed by concatenating two instances of G(s), H(s) = G(s)||G(s) will also be a pseudorandom generator. This is because the output of H(s) will be indistinguishable from a truly random string, assuming G(s) is secure.

3) True. The CPA (chosen-plaintext attack) security requirement for an encryption scheme is that an attacker should not be able to determine the key used for encryption by simply observing the encryption of chosen plaintexts. In other words, the encryption scheme should provide semantic security, protecting the confidentiality of the key even when an adversary has access to the encryption oracle and can obtain ciphertexts for arbitrary plaintexts of their choice.
User Georgette
by
8.6k points