# Are parts of a pseudorandom string also a pseudorandom string?

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!

• 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) – SEJPM Dec 9 '15 at 21:03

## 2 Answers

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.

• 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. – Lemon Dec 10 '15 at 7:08
• 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. – Lemon Dec 10 '15 at 7:09
• @Lemon Yes, you are absolutely on the right track. See also my update. – hakoja Dec 10 '15 at 9:27

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.