Conditional Entropy-Preserving Pseudorandom Generators from One-Way Functions #
This module formalizes conditional entropy-preserving pseudorandom generators
($\mu$-condEP-PRGs) and their construction from one-way functions following
Y. Liu and R. Pass, On One-Way Functions and Kolmogorov Complexity. All section,
definition, theorem, lemma, and page locators follow the full version arXiv:2009.11514v1
(and ECCC TR20-052): Section 5 (Definition 5.1, §5.1, p. 11; Lemma 5.1, §5.3, p. 14; Lemma 5.2,
§5.3, p. 15; Theorem 5.5, §5.3, p. 15) and Appendix A (pp. 21–24). Note that in
arXiv:2009.11514v1, Theorem and Definition share one section counter while Lemma and
Fact share a separate section counter.
Main definitions #
Cslib.Crypto.CondEPPRG: $(\mu, \gamma)$-conditional entropy-preserving pseudorandom generator with entropy-loss constant $\alpha$ (Liu and Pass, Definition 5.1, §5.1, p. 11 of arXiv:2009.11514v1).Cslib.Crypto.regularityBucket: regularity buckets partitioning $\{0, 1\}^n$ by logarithmic preimage fiber size $\lfloor \log_2 |f^{-1}(f(x))| \rfloor \in \{0, \dots, n\}$ (Liu and Pass, Lemma 5.2, §5.3, p. 15 of arXiv:2009.11514v1).
Main results #
Cslib.Crypto.exists_regularity_bucket: for everyf : BitString n → Image, some regularity bucket $S_{n, r}$ has cardinality at least $2^n / (n + 1)$ and every $x \in S_{n, r}$ has fiber cardinality in $[2^r, 2^{r + 1})$ (Liu and Pass, Lemma 5.2 and Claim 3, §5.3, p. 15 of arXiv:2009.11514v1).Cslib.Crypto.OneWay.exists_condEPPRG: every one-way function yields a $(1 / n^\delta, \gamma)$-condEP-PRG for any prescribed stretch factor $\gamma$ and polynomial security exponent $\delta$ (Liu and Pass, Theorem 5.5, §5.3, p. 15 of arXiv:2009.11514v1).
References #
- Y. Liu and R. Pass, On One-Way Functions and Kolmogorov Complexity,
full version
arXiv:2009.11514v1(Section 5 and Appendix A).
Definition 5.1: Conditional entropy-preserving PRG #
Liu and Pass, Definition 5.1, §5.1, p. 11 of arXiv:2009.11514v1: Conditional entropy-preserving pseudorandom generator ($\mu$-condEP-PRG). A deterministic polynomial-time function $G : \{0, 1\}^* \to \{0, 1\}^*$ is a $(\mu, \gamma)$-condEP-PRG with entropy-loss constant $\alpha$ if:
- $G$ is computable in polynomial time (
ComputableInPolyTime G encBits encBits), - $G$ stretches every $n$-bit seed $z \in \{0, 1\}^n$ to length $n + \gamma \lfloor \log_2 n \rfloor$,
- there exists a sequence of nonempty conditioning events $E_n \subseteq \{0, 1\}^n$ such that:
- (Conditional pseudorandomness): For every strict PPT distinguisher $\mathcal{A}$, eventually in $n$, the distinguishing advantage between $G(U_n \mid E_n)$ and $U_{n + \gamma \lfloor \log_2 n \rfloor}$ is at most $\mu(n)$,
- (Conditional entropy preservation): Eventually in $n$, the Shannon entropy of $G(U_n \mid E_n)$ is at least $n - \alpha \lfloor \log_2 n \rfloor$.
Instances For
Lemma 5.2: Regularity bucket pigeonhole #
The $r$-th regularity bucket $S_{n, r} = \{x \in \mathrm{BitString}\; n : \lfloor \log_2 |f^{-1}(f(x))| \rfloor = r\}$ (Liu and Pass, Proof of Lemma 5.2, §5.3, p. 15 of arXiv:2009.11514v1).
Instances For
Every input $x$ in regularityBucket f r has fiber cardinality in $[2^r, 2^{r + 1})$.
regularityBucket f r is a union of full fibers of f: if $f(x') = f(x)$, then
$x' \in S_{n, r} \iff x \in S_{n, r}$.
Liu and Pass, Lemma 5.2 and Claim 3, §5.3, p. 15 of arXiv:2009.11514v1: Existence of a dense regularity bucket. For every $n$ and every function $f : \mathrm{BitString}\; n \to \mathrm{Image}$, there exists a regularity index $r \in \mathrm{Fin}\; (n + 1)$ such that the bucket $S_{n, r}$ has cardinality at least $2^n / (n + 1)$ (i.e. $2^n \le (n + 1) \cdot |S_{n, r}|$), is nonempty, and every $x \in S_{n, r}$ has fiber size in $[2^r, 2^{r + 1})$.
Fiber resampling and regularity bucket mass bounds #
Resampling a preimage uniformly from the fiber of an element drawn uniformly from a
nonempty regularity bucket recovers uniformOfFinset (regularityBucket f r) hS.
Averaging any real-valued function over x₀ ← uniformOfFinset (regularityBucket f r) and
x ← uniformOfFintype {x // f x = f x₀} equals its average over x ← uniformOfFinset.
Pointwise image probability bound when $x$ is drawn uniformly from a dense regularity bucket $S_{n, r}$ with $2^n \le (n + 1) \cdot |S_{n, r}|$.
Trivial inverter and regularity deficit bound #
For any one-way function $g$ with fixed output length imgLen and any sequence of dense
regularity indices $r(k)$, for every constant $D \in \mathbb{N}$ we eventually have
$r(k) + D \lfloor \log_2 k \rfloor \le k$.
Generator parameters and deterministic construction #
Seed packing and conditioning events $E_n$ #
Leftover hash statistical distance and conditional entropy preservation #
Goldreich–Levin hybrid reduction and PPT inverter #
Theorem 5.5: Existence of a conditional entropy-preserving PRG from any OWF #
Liu and Pass, Theorem 5.5, §5.3, p. 15 of arXiv:2009.11514v1: Every one-way function yields a conditional entropy-preserving pseudorandom generator. For every one-way function $f : \{0, 1\}^* \to \{0, 1\}^*$ and every prescribed polynomial security exponent $\delta \in \mathbb{N}$ and stretch constant $\gamma \in \mathbb{N}$, there exist a deterministic polynomial-time generator $G : \{0, 1\}^* \to \{0, 1\}^*$ and an entropy-loss constant $\alpha \in \mathbb{N}$ such that $G$ is a $(1 / n^\delta, \gamma)$-condEP-PRG with entropy loss $\alpha$.