0
$\begingroup$

Usually a Pseudo Random Generator is supposed to be IND-CPA secure.

But apparently, it is not in some cases such as the following:

  • A PseudoRandom Generator $G$ has expansion factor $n + 2$.

  • Encrypt $m \space \in \{0,1\} ^ {n+2}$

  • Choose a random value $v \leftarrow \{0,1\}^n$

  • Then send $(v, G(v) \oplus m)$

The question is why is it not IND-CPA secure and also not IND-EAV secure?

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Sorry, this is probably me, but doesn't have a PRG just have a single input: the seed? I presume we are talking about some stream cipher or PRF here? Otherwise, how can IND-CPA even apply? $\endgroup$ – Maarten - reinstate Monica♦ Sep 1 at 12:18
  • 5
    $\begingroup$ IND-CPA is a property of encryption schemes, not of PRGs. $\endgroup$ – fkraiem Sep 1 at 23:11
  • $\begingroup$ @MaartenBodewes Acronym mix-up? A PRG (which is different from a PRNG) uses a key and one other input. $\endgroup$ – Future Security Sep 3 at 0:38
  • $\begingroup$ OK, in that case Wikipedia on PRG seems way off. That might be just Wikipedia though. Alternatively, the cipher based on the PRG called $G$ may not be IND-CPA secure? In that case, what happens if $n=0$ or $n=1$? $\endgroup$ – Maarten - reinstate Monica♦ Sep 3 at 1:39
2
$\begingroup$

As was noted before in the comments, IND-CPA is a propery of encryption schemes and not PRGs.

Furthermore, there is no such thing as nondeterministic PRGs, it is completely opposed to its purpose and the definition of PRG does not allow that.

a PRG is supposed to generate $l(n)$ "pseudo random" bits given $n$ "truly random" bits (sampled from the uniform distribution). If a PRG could generate random bits, it could just generate $l(n)$ truly random bits and return them as its output, disregarding its input.

Regarding your question, it seems to me that you have not understood it correctly.

I think the question describes an encryption scheme, using some pseudo-random generator $G$. The encryption works as follows: upon receiving a message $m$ a random vector $v$ is drawn and the ciphertext is $c := (c1, c2) = (v, G(m) \oplus v)$

Why is it not IND-EAV secure? well, the encryption doesn't even use a key. As $G$ is a "public" function, an adversary could simply recover $m := G(c1) \oplus c2$ and the scheme is broken.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.