New answers tagged

2

In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$. In the worst case, you want the circuit to succeed ...


2

Intuitively, pseudorandom functions are functions that look random. A linear function $f$ satisfies $$ f(x+y) = f(x)+f(y) $$ for all $x,y$, which is highly unlikely for a random function. Similarly, an affine function $f$ satisfies $$ f(x+y) - f(x+z) = f(y) - f(z) $$ for all $x,y,z$, which is highly unlikely for a random function.


1

Theorem 1 in [Nisan Wigderson 1988] implies: For any function $l\le s(l)\le 2^l$, the following are equivalent: For some $c>0$, there exists a quick PRG $G: l\to s(l^c)$. For some $c>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$. Although their definition of (quick) PRG and hardness are slightly different from yours, I think the ...


1

Yes - this is a consequence of the Law of Large Numbers. https://en.wikipedia.org/wiki/Law_of_large_numbers Yes - it still holds for pseudorandom number generators if they are any good. Seed each PRNG independently.


0

I produced now a simple overview of most of the known RNG's, with its speed and quality, based on improved dieharder tests. https://rurban.github.io/dieharder/QUALITY.html For TestU01 and PractRand results see the linked https://github.com/lemire/testingRNG overview, but yields the same results. You just need to wait days for the same results. Best and ...


0

If you choose $G$ from the uniform random distribution on $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it is random.


Top 50 recent answers are included