3
$\begingroup$

I am working on an exercise that encrypts a message using only the first $n$ bits of a pseudorandom generator's output $G(k)$, i.e. $F_k(m) := G(k)_{0...n−1} \oplus m$.

$k$ is chosen uniformly at random and $k, m \in \{0, 1\}^n$. My task is to decide whether an encryption scheme based on $F_k$ can be secure against a ciphertext-only attack, a CPA attack and whether it's indistinguishable.

My idea was that, if $G(k)_{0...n−1}$ is still a pseudorandom string, the exercise reduces to the case of using the whole output of $G(k)$. Then the scheme would be secure against a ciphertext-only attack and indistinguishable, but not secure against CPA attacks since it's a deterministic scheme.

My problem is that I couldn't find out, whether $G(k)_{0...n−1}$ can be treated exactly like the entire output of $G(k)$. Furthermore, I am not sure whether my intuition about solving the exercise is right. I would appreciate any hints!

$\endgroup$
  • 1
    $\begingroup$ Why shouldn't it be a pseudo-random string? If it actually weren't pseudo random the generator could be broken even if you didn't truncate (cause the string would still be used) $\endgroup$ – SEJPM Dec 9 '15 at 21:03
1
$\begingroup$

You ask many questions and it is not clear to me exactly what you would like to have answered. In particular, what do you mean by:

My problem is that I couldn't find out, whether $G(k)_{0...n−1}$ can be treated exactly like $G_k$.

What is $G_k$ supposed to mean here? The full output of $G(k)$? What is your definition of "treated exactly like"?

In any case, the $n$ first bits of a secure PRG are of course also pseudorandom, but $F_k$ is not an IND-CPA secure scheme as you rightly point out. Nor is it a PRF (pseudorandom function). Can you see why? Hint: start by making a query to $F_k(\cdot)$ on the message $0^n$, next query it on some other message $m \neq 0^n$. What can you say about the relation between $F_k(0)$ and $F_k(m)$? Would you expect this to hold for a randomly drawn function $f \colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^n$?

Update based on comment

So basically you want to show the following statement: "$G(k)$ is secure PRG $\implies G(k)_{0\dotsc n-1}$ is a secure PRG". In crypto we typically prove these kinds of statements by proving the equivalent contraspositive statement: "$G(k)_{0\dotsc n-1}$ is not a secure PRG $\implies G(k)$ is not a secure PRG". In this case this is very straightforward. So suppose there exists some (hypothetical) distinguisher $D$ against $G(k)_{0\dotsc n-1}$. Then suppose you are given a string $x$ of length $|G(k)|$ and challenged to tell whether $x$ is a random string or produced by $G(k)$. What do you do? Well, simply chop of the $n$ first bits of $x$, say $x'$, and feed this to $D$. Note that $D$ tries to tell whether it was given a random string of length $n$ or $G(k)_{0\dotsc n-1}$. What you do now is simply output whatever guess $D$ makes. If $x$ was a random string of length $|G(k)|$, then $x'$ is a random string of length $n$. While if $x = G(k)$, then $x' = G(k)_{0\dotsc n-1}$. Hence, the probability that we are able to distinguish $G(k)$ from a random string is exactly the probability that $D$ is able to distinguish $G(k)_{0 \dotsc n-1}$ from a random string. Thus, if $D$ is successful, we are successful.

$\endgroup$
  • $\begingroup$ Sorry, that was a spelling mistake. G(k) indeed denotes the full output of G(k). Regarding "treated exactly like": If $G(k)_{0..n-1}$ was still a pseudorandom string, the scheme would correspond to the "private-key encryption scheme for any generator" described by Lindell&Katz. Then I could show that the scheme has indistinguishable encryptions in the presence of an eavesdropper by means of a reduction and that it is not CPA secure since G(k) is deterministic. $\endgroup$ – Lemon Dec 10 '15 at 7:08
  • $\begingroup$ I also expect it to be secure regarding ciphertext-only attacks since that's an inherent property of pseudorandomness. Am I on the right track now? Regarding your PRF hint: I am afraid we didn't talk about PSF yet. $\endgroup$ – Lemon Dec 10 '15 at 7:09
  • $\begingroup$ @Lemon Yes, you are absolutely on the right track. See also my update. $\endgroup$ – hakoja Dec 10 '15 at 9:27
4
$\begingroup$

If you have a stream, $s$, of $n$ bits that is computationally indistinguishable from random, then any truncation of that $n$ bit string must also be indistinguishable from random.

The proof of this is straightforward. If $s$ was computationally indistinguishable from random, but some truncation of $s$ was not then we could distinguish the larger sequence from random by enumerating all possible truncations of $s$ and testing them against the distinguisher.

If the distinguisher identifies that any truncation is not random, then this demonstrates $s$ is not random. It acts as a distinguisher on $s$. Obviously, that is a contradiction.

$\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.