21

There are two aspect that need to be mentioned. The first is the general idea of defining a PRG by having its output look different than uniform to small circuits. This idea goes back to Yao and is really the strongest possible definition you can ask for when aiming explicitly at pseudo-randomness for computationally-bounded observers. The second ...


13

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first") ...


13

Salil Vadhan wrote to me that the answer to my question is known, and PRGs are equivalent to extractors. Quoting him: "See Proposition 21 and the discussion following it in my survey http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (There's a typo - "black-box hardness amplifier" should be "black-box PRG construction") It says extractors are ...


13

This is a beautiful research question with several facets to it, and there are different ways of formalizing the question depending on whether by extractor you mean seeded extractor or seedless extractor and whether by PRG you mean PRG for Boolean circuits or a more specialized family (e.g., epsilon-biased spaces). Here's a few informal thoughts off the top ...


13

The notion of "theoretically sound" pseudorandom generators is not really well defined. After all, no pseudorandom generator has a proof of security. I don't know that we can say that a pseudorandom generator based on the hardness of factoring large integers is "more secure" than, say, using AES as a pseudorandom generator. (In fact, there is a sense that it ...


11

I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$. Let $a_1, \dots, a_k, b_1, \dots, b_k\in_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W_1,\dots, W_n$ of the form $c_1 \cdot c_2\cdot \dots \cdot c_k$ ...


11

If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support. Theorem. Let $H(Y)$ be the Shannon entropy of $Y$ and let $F \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$. Proof. Consider the collision ...


10

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known. But if $d$ is very small, say a constant, then you can do better and achieve logarithmic seed length -- I think, this is something I thought about years ago but never wrote down. The trick is to use ...


9

You seem to be confusing theory with practice. A theoretically sound pseudorandom generator is a bad fit for practical use for several reasons: It's probably very inefficient. The security proof is only asymptotic, and so for the particular security parameter used, the pseudorandom generator may be easy to break. All security proofs are conditional, so in ...


8

There is a nice paper of Chris Umans on the analogue of this question for dispersers: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf He shows that dispersers that have a polynomial-time reconstruction procedure, but not necessarily the local decoding property, imply the existence of hitting set generators. Here is another way to view it: Extractors ...


8

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior. Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (...


8

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case. Unfortunately, as you will see,...


7

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\...


7

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "indistinguishability", do not seem to be equivalent for deterministic adversaries. (If they were, we would have complexity class separations.) Here are three references; I'm ...


7

A good reference is Code-Based Game-Playing Proofs and the Security of Triple Encryption by Bellare & Rogaway. The statement that you are asking about is called the PRF/PRP switching lemma. This paper goes into significant detail about "standard" proofs of this lemma and the subtleties therein. It uses the switching lemma as an illustrative example to ...


7

I can give several answers to your question. Algorithmic randomness. When should we call a sequence $x_1,\ldots,x_n$ of bits random? A priori, all sequences have the same probability, so it's not clear on what grounds we should single out one sequence or another as not being random. This is partly a philosophical question, but "applied philosophy" has given ...


6

The meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.


6

No, the string need not be normal. Take any uncomputable sequence and add two 0s between each term; now there are too many 0s for the sequence to be normal but it's still uncomputable.


4

I am by no means an expert on this, but a key component of the definition of pseudorandomness (as opposed to attempts to define randomness) is that the goal of something "pseudorandom" is to fool a circuit. In other words, the motivation is to think of the pseudorandom string being supplied to the circuit instead of the truly random string. In that sense, ...


4

@mikero mentioned Bellare & Rogaway's paper, which gives a full proof. It's a rather advanced one, which is hard to digest. I suggest reading section 5.1 of Victor Shoup's Sequences of Games: A Tool for Taming Complexity in Security Proofs, which, IMHO, is a much easier read. The basic idea is a to show a sequence of 3 games: In game 0, adversary A is ...


4

Mihai Pătraşcu explained on his blog how to strengthen the variance bound of Chebyshev by looking at higher moments. He references "Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al. You also might be interested in "Concentration of Measure for the Analysis of Randomized Algorithms" by Dubhashi and Panconesi.


4

They are the same: BPNC = DBPNC. Say a BPNC machine is given as input a DBPNC program to simulate. Execute the program in lock step. First assume that the indices between different steps are distinct, so that we do not need to remember old random bits. At each step, each processor asks for a random bit at a specific index into the shared stream. Compute ...


4

Although the previous answers are fairly comprehensive, let me just add that there are notions of time-bounded Kolmogorov complexity which can apply in your situation. For example, $K^t(x)$ is the length of the shortest program that produces $x$ within time $t(|x|)$. So, for example, a pseudorandom number generator that takes time $n^3$ could still produce ...


4

Yes. The following paper presents a candidate for a PRF that is implementable in $NC^1$, whose security is based on a lattice assumption (hardness of LWE): Abhishek Banerjee, Chris Peikert, Alon Rosen. Pseudorandom Functions and Lattices. EUROCRYPT 2012. It also has some discussion of related literature that might be helpful. Also, here are two trivial ...


4

Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions: Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$. Such functions are known to exist; see, e.g., Chapter 6....


3

Yes, we can always say that $X$ has pseudoentropy at least $H(X)$. You can take $Y$ to be a completely separate, independent random variable that has the same distribution as $X$. Then $X$ and $Y$ are computationally indistinguishable (indeed they are "completely" indistinguishable): $\Pr[A(X) = 1] = \Pr[A(Y) = 1]$ for all algorithms $A$. Instead of ...


3

I have figured out that the answer to this question is yes. The proof goes via sandwiching polynomials. It's a simple modification of a proof in [GMRTV12] $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)


3

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions. In Dwork's lecture notes as well, the condition required is that the expansion be $C/\delta$ for some constant $C$ (looking at a points in distance c is ...


2

Hopefully, I can expand just a little on Suresh's response. First, I don't think that the strictness of the inequality is needed in your $(*)$, and I am also not sure why $1/n$ is needed, and not $1/2n$ or something else. However, practically, I think 1/n is enough to get some interesting theoretical results. But then you almost certainly want to assert ...


2

Take any distribution $D$ on $\{0,1\}^n$. Sample $k(n)$ points $x_1, \cdots, x_{k(n)}$ independently from $D$ and let $\tilde D$ be the uniform distribution that gives a random $x_i$. Then, if $k(n)$ is super-polynomially large e.g. $k=n^{\log n}$, you cannot distinguish $D$ and $\tilde D$ using only $\mathrm{poly}(n)$ samples. Hence $D$ is computationally ...


Only top voted, non community-wiki answers of a minimum length are eligible