The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for space-bounded computation uses a seed of length $O(logn·log(nw/\epsilon )+logd)$ to fool ordered branching programs of length n, width w, and alphabet size d to within ...$$${}^{\mathrm{}}$$$$\stackrel{}{}$$$$$\begin{array}{c}\hfill \mathrm{}\left(,,,,,\left(,,,,,\right),,,,,,\left(,,\right),,,\right)\end{array}$$$$$\mathrm{}$$\left(,,,,,\right)$$\mathrm{}\left(,,,,,,,,,,\right)$$\mathrm{}$$\mathrm{}$$\mathrm{}\left(,,,,,,,,,,,,\mathrm{},,,\right)$${}^{\mathrm{}\mathrm{}}$

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation. Our first contribution is a derandomization of bounded-space machines from ...

Two fundamental properties of quantum states that quantum information theory explores are pseudorandomness and provability of destruction. We introduce the notion of quantum pseudorandom states with proofs of destruction (PRSPD) that combines both ...

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : F_q^r → F_qⁿ to an element sampled uniformly at random from a k-dimensional variety V ⊆ F_q^r. ...

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length n and width w in space Õ(logn+√logn·logw). In particular, we obtain an almost optimal space Õ(logn) derandomization of programs up to ...

We present a procedure for efficiently sampling colors in the CONGEST model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to sample up to Θ ( log ⁡ n ) semi-random colors unused by ...

• Ultrafast distributed coloring is possible even with bandwidth constraints.
• ...

Many automatic sequences, such as the Thue-Morse sequence or the Rudin-Shapiro sequence, have some desirable features of pseudorandomness such as a large linear complexity and a small well-distribution measure. However, they also have some ...

The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for space-bounded computation uses a seed of length $O(logn·log(nw/\epsilon )+logd)$ to fool ordered branching programs of length n, width w, and alphabet size d to within ...$$${}^{\mathrm{}}$$$$\stackrel{}{}$$$

Arbiter based Physical Unclonable Function (sometimes called Physically Unclonable Function, or in short PUF) is a hardware based pseudorandom bit generator. The pseudorandomness in the output bits depends on device specific parameters. For ...

Automatic sequences are not suitable sequences for cryptographic applications since both their subword complexity and their expansion complexity are small, and their correlation measure of order 2 is large. These sequences are highly predictable ...

For a test T ⊆ {0, 1}ⁿ, define k^*(T) to be the maximum k such that there exists a k-wise uniform distribution over {0, 1}ⁿ whose support is a subset of T.

For H_t = {x ∈ {0, 1}ⁿ : | ∑_ix_i − n/2| ≤ t}, we prove k^*(H_t) = Θ (t²/n + 1).

For S_{m, c} = {x ∈ {0, 1}^...

We consider the so-called Encrypted Davies---Meyer (EDM) construction, which turns a permutation P on $$\{0,1\}^n$${0,1}n into a function from $$\{0,1\}^n$${0,1}n to $$\{0,1\}^n$${0,1}n defined as $$P(P(x)\oplus x)$$P(P(x)?x). A similar construction ...

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to ...

A sampling procedure for a distribution P over {0, 1}^ℓ is a function C: {0, 1}ⁿ → {0, 1}^ℓ such that the distribution C(U_n) (obtained by applying C on the uniform distribution U_n) is the “desired distribution” P. Let n > r ≥ ℓ = n^Ω(1). An ϵ-nb-PRG (...

We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. While in the definition of expanders it is ...

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We ...

Pseudorandom binary sequences play a crucial role in cryptography. The classical approach to pseudorandomness of binary sequences is based on computational complexity. This approach has certain weak points thus in the last two decades a new, more ...

Given an input x and a search problem F, local computation algorithms (LCAs) implement access to specified locations of y in a legal output y ź F ( x ) , using polylogarithmic time and space. Parnas and Ron 27 and Mansour et al. 19 showed how to convert ...

We propose a new model of weak random sources which we call sumset sources. A sumset source X is the sum of C independent sources, with each source on n bits source having min-entropy k. We show that extractors for this class of sources can be used to ...

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-...