# Tag Info

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 ...

18

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$. The idea is that you can think of a randomized ...

16

Check Chapter 7 of Salil Vadhan's monograph. Corollary 7.64 is Impagliazzo and Wigderson's result.

16

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and Kabanets show that PIT in P would imply some circuit lower bounds. So circuit lower bounds are the only reason (but a pretty good one) that we believe P = BPP.

15

1) What is meant by necessary is that one way to generate a $k$-wise independent distribution is to break the input in blocks of $k+1$ bits, and let the $(k+1)$th bit of each block be the parity of the other $k$ bits in the block. Obviously this distribution can be broken just by computing parity on $k$ bits. The result you claim follows from the fact that ...

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 ...

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 ...

12

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in a graph. There is a randomized poly-time algorithm to approximate these numbers within a (1+eps) factor, whereas the best deterministic algorithms achieve only ...

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

I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$. (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one. Of course, the running time of ...

9

There are many types of cryptanalytic attacks: Linear approximations, Algebraic attacks, Time-memory-data-tradeoff attacks, fault attacks. For example you can read the survey: "Algebraic Attacks On Stream Ciphers (Survey)" Abstract: Most stream ciphers based on linear feedback shift registers (LFSR) are vulnerable to recent algebraic attacks. In this ...

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

Polylog independence may not be the only way to fool $AC^{0}$ circuits. To illustrate this example, consider the class of linear polynomials. Any zero set of a linear polynomial is $(n-1)$-wise independent but of course this doesn't fool linear polynomials. Hence, $(n-1)$-wise independent distributions do not fool this class. This of course doesn't mean that ...

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 ...

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 ...

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

My half-baked idea was a little too ambitious. I'm including it below for reference, but the distance condition I specified is not actually sufficient to guarantee large girth. There are arbitrarily large highly symmetric surface maps with large girth, but published existence proofs are largely based on group theory rather than topology or geometry per se. ...

4

You can determine the period reasonably easily if you know the factorization of $M$ as $pq$, the factorization of $(p-1)\cdot (q-1)$ and the factorization of $\ell-1$ for any prime $\ell$ that divides $(p-1)\cdot (q-1)$. This requires two steps, first find the order of $x_0$ modulo $M$. Since this divides $(p-1)\cdot (q-1)$ whose factorization is known, ...

4

Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this classical paper by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L_1$ distance.

3

Given that you said it would be enough for the sequence to be unpredictable, here is a very simple solution. The $i$th value in the sequence is given by $$x_i = 2^{128} i + y_i$$ where $y_i$ is any pseudorandom sequence where you can efficiently find the $i$th value ($y_i$) and where each $y_i$ is 128 bits wide (i.e., $0 \le y_i < 2^{128}$). For ...

3

Katz and Lindell were recommending against using LFSRs by themselves as pseudorandom generators. However, it might be possible to construct a pseudorandom generator using an LFSR in conjunction with other mechanisms. (In particular, PRGs based on LFSRs must include some non-linear component.)

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

There is now a jump function for SFMT (a fast Mersenne Twister implementation). This allows me to initialise 1000 MTs so that there is no cycle overlap. And SFMT should be faster than MTGP. Almost perfect for my purposes.

2

I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy. Description of the scheme. Thinking as an algorithm, the scheme is the following. It has two parameters, an integer $n$, and a bound $m$, $0 \leq n < m$, with the invariant that $n$ was drawn uniformly at ...

1

something close to what you are requesting seems to be proven in Thm 2.10 p6 of these lecture notes by O'Donnell, Lecture 16: Nisan’s PRG for small space but it does not cite the original ref for the proof. a simple statement of the theorem in terms of FSMs is not given in this ref but is translatable. (volunteers?) in the theorem $M^n$ is a transition ...

1

Regarding question A, it is possible to adapt the PRNG to yield uniformly distributed numbers using this. However, the range of this new uniform generator has size smaller than $K$, unless the PRNG is itself uniform. The number of possible outcomes of this new generator will depend on the min-entropy of the original generator. To get some intuition on why ...

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