The pseudorandomness tag has no wiki summary.
0
votes
0answers
76 views
Breaking secure pseudorandom generators by assuming BPP != P
Suppose we find some problem X that is in BPP but not in P. Also, suppose we have access to a random oracle R. Do X and R allow us to break any claimed secure pseudo-random number generator?
(Note ...
8
votes
1answer
184 views
Is deterministic pseudorandomness possibly stronger than randomness in parallel?
Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
15
votes
3answers
311 views
What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?
I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : ...
7
votes
2answers
387 views
Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time
I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography.
Show that no ...
16
votes
2answers
701 views
Are theoretically sound pseudorandom generators used in practice?
As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
9
votes
0answers
140 views
Pseudorandom object yielding shrinkage in $\ell_p$ norm?
Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then ...
4
votes
1answer
182 views
Pseudo-Random Function families whose instances have full domain
The GGM construction gives (PRF) pseudo-random function families
whose instance's input's are binary strings of a single length.
I've convinced myself that one could get a PRF family whose instances ...
0
votes
1answer
199 views
Non-computable=>normal?
If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite ...
14
votes
0answers
194 views
Problem-Dependent Derandomization
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be ...
19
votes
3answers
543 views
From Extractors to Pseudorandom Generators?
Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions:
http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf
Is there a ...
2
votes
1answer
317 views
Expanded use of an LFSR?
We want an algorithm for the following task:
We are given $n$ and $i$ and we want to check if an $n$-bit LFSR with the sub-register exactly $n/2$ and an interval of $i$ "works". We say an interval ...
10
votes
0answers
317 views
Expectation of Gowers norm
This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem:
Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow ...
2
votes
4answers
391 views
Algorithmic distinctions between random and pseudorandom.
Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:
$f(r(),r()) = 1$ almost always.
...
1
vote
3answers
380 views
Simple question about pseudorandom generator
I am stuck on the following question related to pseudorandom generator and any help would be appreciated.
Let $G:\{0,1\}^k \to \{0,1\}^{k+1}$ be a pseudorandom generator. Define ...
6
votes
0answers
150 views
Distributions over circuits and N-to-N vs N-to-1 circuits
This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
19
votes
2answers
471 views
Explicit balanced matrix
Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?
Or probably it is ...
12
votes
3answers
400 views
Surveys on pseudo-random number generator design?
I am interested in generation of pseudo-random numbers for cryptography. Besides Chapter 5 of Menezes/Oorschot/Vanstone; Chapter 8 of Stinson; and Chapter 3 of Goldreich, where else could I find more? ...
16
votes
1answer
371 views
Fooling arbitrary symmetric functions
A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every ...
