-1
$\begingroup$

Can there exist a pseduorandom generator, $G(x)$, with input length $|x|=n$ and output length $|G(x)|=2n$, where $\leq n$ bits of $G(x)$ are equal to 1 for every possible input $x$? (I.e. no more than $n$ of the $2n$ output bits are 1 for every $G(x)$)

Such a PRG would have to meet the typical criteria for being a PRG, that is, being: 1) poly-time computable, 2) have expansion factor $\ell(n) = 2n > n$, and 3) for every PPT distinguisher $D$, $|Pr[D(G(s))=1]-Pr[D(r)=1]| \leq negl(n)$

Improve this question
$\endgroup$
2
  • $\begingroup$ What if the current output would be an even number of bits and $n$ bits are indeed set to 1? $\endgroup$ – Maarten Bodewes♦ Oct 12 '18 at 0:10
  • $\begingroup$ Well, what is the probability that at most $n$ bits of a random $2n$-bit string will be $1$? That's the sort of thing that's taught in elementary probability courses... $\endgroup$ – fkraiem Oct 12 '18 at 17:24
4
$\begingroup$

Usually, a PRG should be indistinguishable from a random generator. When a random generator produces $2n$ random bits, there should be more than $n$ bits equal to 1 about half of the time. Thus, your PRG would seem non random quite fast: a random generator would have probability only one in a billion to make more zeros than ones 30 times in a row, but your PRG will succeed every time.

That being said, you can also say: I want a PRG that is indistinguishable from a random source that outputs only sequences of $2n$ bits with no more than $n$ ones, but samples with uniform probability within these sequences. That kind of PRG is fairly easy to make. Take a one-way function $F$ that takes as input a sequence of arbitrary length, and outputs $2n$ bits (consider SHAKE, for instance). Then define $G(x)$ by computing $F(x||1)$, $F(x||2)$, $F(x||3)$... until you get an output with at most $n$ ones; this output is then your $G(x)$. If $F$ is a good PRG itself, then that $G$ will match your requirements.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Will that $G$ really still be a PRG though? I think you could still create an adversary with better than negligible advantage in distinguishing that $G$ from random function, by the logic of your first paragraph, therefore the $G$ you suggested would not actually be a PRG $\endgroup$ – jessli Oct 12 '18 at 1:38
  • $\begingroup$ I think there is a difference between a generator that is online and one that simply generates a predefined number of bits. And if you know anything in advance about the output then clearly it is not random; I presume that Thomas considered this known. $\endgroup$ – Maarten Bodewes♦ Oct 12 '18 at 2:18
  • $\begingroup$ @MaartenBodewes right, but by the definition that a PRG must be 1) poly-time computable 2) have some expansion factor $\ell(n)>n$ and 3) for every PPT distinguisher $D$, the probability that $D$ accepts given output from $G$ minus probability $D$ accepts on uniformly random output is negligible, I'd say that no PRG could exist that meets those criteria with output where less than or equal to half the bits are 1, because there DOES exist a PPT distinguisher for any such $G$ $\endgroup$ – jessli Oct 12 '18 at 16:19
  • $\begingroup$ usually? This is very dangerous for cryptography. $\endgroup$ – kelalaka Oct 12 '18 at 16:54

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.