Generate random bits

Random bit generator is usually a physical device. Usually, $P r (X = 1) = p$ ; from this, easily get random generator with $P r (X = 1) = 1 / 2$ : flip every alternate bit. Flippling every t-th bit, get Pr(X = 1) = 1/t.

2-wise independent bits generation

$2^{b} - 1$ 2-ind bits $Y_{i}$ from b ind bits $X_{i}$ : For each subset, $Y_{i} = \oplus X_{i}$ . In GF(p), p 2-ind elements from 2 ind elements: $Y_{i} = (X_{1} + i X_{2}) \mod p$ for every i in GF(p). 2-universal ( $P r (h (x) = h (x^{'})) \leq n^{- 1}$ ) hash function family: H has $h : U \to V; | V | = n; a, b \in G F (p), a \neq 0$ ; $h_{a, b} (x) = ((b + x a) \mod p) \mod n$ . If a can be 0, strongly 2-universal ( $P r (h (x) = y, h (x^{'}) = y^{'}) = n^{- 2}$ ).

Pseudorandom generator G

Based on operational meaning of randomness: Better than early definitions, which were based on statistical properties of bit string.

$G : {0, 1}^{l} \to {0, 1}^{n}$ , computable in time $2^{O (l)}$ , is an $(ϵ, s (n))$ pseudorandom generator if $\forall$ ckts c of size s(n) [strength parameter], Indistinguishability / unpredictability property holds: $P r_{y \in {0, 1}^{n}} [c (y) = 1] - P r_{x \in {0, 1}^{l}} [c (G (x)) = 1] \leq ϵ$ [error parameter].

Distinguishers c usually try to learn from string and guess if G generated it. For example of distinguisher, see colt ref.

Notion similar to PFF: If ye pick y, you’ve picked random functions f; if ye pick x, you’ve picked a subset of pseudorandom functions.

Hard function f

f is (a(n), s(n)) hard if $\forall$ ckts of size $\leq s (n)$ , \ $P r_{y \in {0, 1}^{n}} [c (y) = f (y)] \leq 2^{- 1} + a (n)$ . (a(n), s(n), D) hardness: a generalized notion: take Pr wrt D.

Worst case hardness: $a (n) = 2^{- 1} + 2^{- n}$ : otherwise, c can memorize +ve inputs.

Any pseudorandom generator is also hard. \why

Any hard function is also a pseudorandom generator. \why

Hard core function f

f is (a(n), s(n), M) hard core wrt \ measure M (defining distribution $D_{M}$ ) if f is $(a (n), s (n), D_{M})$ hard.

If f is hard wrt distribution D which is uniform over set S, it is (a(n), s(n), S) hard core. Then S is a (a(n), s(n), f) hard core set. If (a(n), s(n), M) hard, then (a(n), s(n), S) hard for S of a certain size.

(Impagliazzo): If f is (a(n), s(n), U) hard, it is $(b (n), b (n)^{2} a (n)^{2}, M)$ hard core where $D_{M}$ is close to U: if not hard core, could smoothly boost the good guessing ckt to get a ckt which violates hardness.

BBS pseudorandom generator

(Blum, Blum, Shub). Input: N=pq: p, q are primes $= 2 \mod 4$ ; Initial seed $s_{0}$ of n bits. Output: A stream of poly(n) bits which look random. $s_{i} = s_{i - 1}^{2} \mod N = s_{0}^{2^{i}} \mod N$ ; ith bit output: $b_{i} := L S B (s_{i})$ .

If factoring is hard, you cannot distinguish between a truly random m bit string and an m bit string obtained by choosing $s_{0}$ at random and running BBS gen. \why

Pseudo random function family (PFF)

Function family F

Set of polynomial sized boolean circuits with input length n, of size $O (e^{n})$ with samplable index set I; $\exists$ alg A to input $i \in I$ , return $f_{i} \in F$ , simulate its input/ output behavior by accepting x and returning $f_{i} (x)$ in poly time.

Distinguisher D

Any Poly time alg; inputs function f: black box access to it; outputs 1 if it thinks f is random.

Indistinguishability

Let f be truly random function. F is PFF if for every D, $P r_{f \in r a n d} (D^{f} = 1) - P r_{i \in_{U} I} (D^{f_{i}} = 1) < O (e^{- n})$ .

Existance

Goldwasser, Goldreich, Micali (GGM): If one way functions exist (if factoring is hard), then PFF’s exist.

\tbc