Does the adversary know the random seed s? If he does not, isn't one possible construction simply the random seed itself? if the output needs to be bigger than random seed s cant I just add a hardcore bit to the random seed s? Also, regardless of the number of leading bits of the output that are revealed (even n-1 where n is length of output), will the output be computationally indistinguishable from a truly random string?
2 Answers
$\begingroup$
$\endgroup$
5
Does the adversary know the random seed s?
No. Let $G$ be an arbitrary PRG. Given the seed $s$ and a string $y$, it is trivial to check whether $y = G(s)$, thus the output of a PRG cannot be indistinguishable from random if the seed is known. Therefore, this definition would be uninstantiable and thus not useful.
If he does not, isn't one possible construction simply the random seed itself?
A family of functions $G : \{0,1\}^{i(\lambda)} \to \{0,1\}^{o(\lambda)}$ needs to have two properties to be called a PRG.
- It needs to be expanding, i.e. it must hold that $o(\lambda)>i(\lambda)$.
- It must hold that or a uniformly chosen seed $s\gets\{0,1\}^{i(\lambda)}$, the value $G(s)$ is computationally indistinguishable from a uniformly chosen string $y \gets \{0,1\}^{o(\lambda)}$.
The PRG you are suggesting is the identity function, which does indeed fulfill property 2 from, above, but not property 1.
if the output needs to be bigger than random seed s cant I just add a hardcore bit to the random seed s?
Well, the identity function does not have any hardcore predicates, so this does not work.
Also, regardless of the number of leading bits of the output that are revealed (even n-1 where n is length of output), will the output be computationally indistinguishable from a truly random string?
By definition of a secure PRG, the entire output is computationally indistinguishable from a truly random string. So by a trivial reduction, so is any prefix of the output.
-
$\begingroup$ Thank you so much! What is a prefix of the seed is revealed? Will that always result in a non-secure prg? $\endgroup$– DanielJun 9, 2020 at 15:11
-
$\begingroup$ Would it be possible to give an example of a conjectured prg? I cant think of one and have looked everywhere on the internet. Also, does the adversary know the prg function? $\endgroup$– DanielJun 9, 2020 at 15:12
-
$\begingroup$ You can come up with contrived examples of PRGs where leaking a prefix of the seed does not break security. E.g. you can construct a PRG that simply ignores the prefix. Then, leaking it makes no difference. For more meaningful examples you would need to look for some kind of leakage resilience. $\endgroup$– MaeherJun 9, 2020 at 16:29
-
$\begingroup$ What kind of example are you looking for? Practical examples are a secure stream cipher, such as AES in CTR mode or ChaCha20. Theoretically the question is which assumptions you are willing to make. There's the famous HILL construction from any one-way function. From OWP there's a much simpler construction using Goldreich-Levin's hardcore predicate. $\endgroup$– MaeherJun 9, 2020 at 16:36
-
$\begingroup$
$\endgroup$
1
If the output needs to be bigger than random seed $s$ [...]
The output does need to be bigger than the seed.
[...] can't I just add a hardcore bit to the random seed $s$?
This is similar to the construction in Theorem 7.19 in Katz and Lindell's textbook (2nd ed., p. 258):
Theorem 7.19: Let $f$ be a one-way permutation with hard-core predicate $\mathsf{hc}$. Then algorithm $G$ defined by $G(s) = f(s) \mathbin\| \mathsf{hc}(s)$ is a pseudorandom generator with expansion factor $\ell(n) = n + 1$.
But note that this talks of the hardcore bit $\mathsf{hc}$ of a one-way permutation $f$. What you're actually proposing is this:
$$ G'(s) = s \mathbin\| \mathsf{hc}(s) $$
...which is trivially distinguishable because your output discloses $s$ itself and therefore the adversary can just trivially compute $\mathsf{hc}(s)$. That's precisely the role that the one-way permutation $f$ plays—it conceals the seed $s$.
answered Jun 9, 2020 at 22:45
-
$\begingroup$ Thank you! Would the prg in 7.19 be indistinguishable if the first x bits of the seed were leaked? also, does the prg function? does he know that g'(s) = s|| hc(s) $\endgroup$– DanielJun 10, 2020 at 16:36