Lecture 15

Random Function

$F:\{0,1\}^n\to \{0,1\}^n$

For each $x\in \{0,1\}^n$, there are $2^n$ possible values for $F(x)$.

pick $y=F(x)\gets \{0,1\}^n$ independently at random. ($n$ bits)

This generates $n\cdot 2^n$ random bits to specify $F$.

Equivalent description of $F$

# initialized empty list L
L=collections.defaultdict(int)
# initialize n bits constant
n=10
def F(x):
    """ simulation of random function
    param:
        x: n bits
    return:
        y: n bits
    """
    if L[x] is not None:
        return L[x]
    else:
        # y is a random n-bit string
        y=random.randbits(n)
        L[x]=y
        return y

However, this is not a good random function since two communicator may not agree on the same $F$.

Pseudorandom Function

$f:\{0,1\}^n\to \{0,1\}^n$

Oracle Access (for function $g$)

$O_g$ is a p.p.t. that given $x\in \{0,1\}^n$ outputs $g(x)$.

The distinguisher $D$ is given oracle access to $O_g$ and outputs $1$ if $g$ is random and $0$ otherwise. It can make polynomially many queries.

Oracle indistinguishability

$\{F_n\}$ and $\{G_n\}$ are sequence of distribution on functions

that are computationally indistinguishable

if for all p.p.t. $D$ (with oracle access to $F_n$ and $G_n$),

where $\epsilon(n)$ is negligible.

Under this property, we still have:

• Closure properties. under efficient procedures.
• Prediction lemma.
• Hybrid lemma.

Pseudorandom Function Family

Definition: $\{f_s:\{0,1\}^\{0.1\}^{|S|}\to \{0,1\}^P$ $t_0s\in \{0,1\}^n\}$ is a pseudorandom function family if $\{f_s\}_{s\in \{0,1\}^n}$ are oracle indistinguishable.

• It is easy to compute for every $x\in \{0,1\}^{|S|}$.
• $\{s \gets\{0,1\}^n\}_n\approx \{F\gets RF_n,F\}$ is indistinguishable from the uniform distribution over $\{0,1\}^P$.
  • $R$ is truly random function.

Example:

For $s\in \{0,1\}^n$, define $f_s:\overline{x}\mapsto s\cdot \overline{s}$.

$\mathcal{D}$ gives oracle access to $g(0^n)=\overline{y_0}$, $g(1^n)=\overline{y_1}$. If $\overline{y_0}+\overline{y_1}=1^n$, then $\mathcal{D}$ outputs $1$ otherwise $0$.

def O_g(x):
    pass
 
def D():
    # bit_stream(0,n) is a n-bit string of 0s
    y0=O_g(bit_stream(0,n))
    y1=O_g(bit_stream(1,n))
    if y0+y1==bit_stream(1,n):
        return 1
    else:
        return 0

If $g=f_s$, then $D$ returns $\overline{s}+\overline{s}+1^n =1^n$.

Theorem PRG exists then PRF family exists.

Proof:

Let $g:\{0,1\}^n\to \{0,1\}^{2n}$ be a PRG.

Then we choose a random $s\in \{0,1\}^n$ (initial seed) and define $\overline{x}\gets \{0,1\}^n$, $\overline{x}=x_1\cdots x_n$.

s=random.randbits(n)
 
#????
 
def g(x):
    if x[0]==0:
        return g(f_s(x[1:]))
    else:
        return g(f_s(x[1:]))
 
def f_s(x):
    return g(x)
 

Suppose $g:\{0,1\}^3\to \{0,1\}^6$ is a PRG.

Suppose the initial seed is $011$, then the constructed function tree goes as follows:

Example:

Assume that $D$ distinguishes $f_s$ and $F\gets RF_n$ with non-negligible probability.

By hybrid argument, there exists a hybrid $H_i$ such that $D$ distinguishes $H_i$ and $H_{i+1}$ with non-negligible probability.

For $H_0$,

EOP