DDH ⇒ PRF (Naor–Reingold)

Fully-black-box reduction · standard model · NR97 · security loss: factor $n$ over the DDH advantage: one hybrid per input bit

Statement

If DDH is hard for $\mathsf{GrGen}$, the Naor–Reingold function is a PRF: over $(\mathbb{G},g,p)\leftarrow \mathsf{GrGen}(1^{\lambda })$ with key $(a_0,a_1,\dots ,a_n)\stackrel{\$}{\leftarrow }[p{]}^{n+1}$, it maps $x\in \{0,1{\}}^n$ to $g^{a_0{\prod }_{i:x_i=1}{a}_i}\in \mathbb{G}$ — NR97.

Sketch

Hybrid $i$ answers $x$ with $g^{R_i(x_1\cdots x_i){\prod }_{j>i,x_j=1}{a}_j}$ for a random function $R_i$ on $\{0,1{\}}^i$, so hybrid $0$ is the Naor–Reingold function and hybrid $n$ a random function. A distinguisher between hybrids $i$ and $i+1$ tells polynomially many DDH tuples sharing the exponent $a_{i+1}$ from random ones, and random self-reducibility derives such tuples from a single DDH instance with no further multiplicative loss.

\begin{algorithm}
\algname{Algorithm}
\caption{$\KeyGen(1^\secpar)$}
\begin{algorithmic}
\State $(\GG, g, p) \gets \GrGen(1^\secpar)$
\State $(a_0, a_1, \ldots, a_n) \getsr [p]^{n+1}$
\Return $k \gets (\GG, g, p, a_0, \ldots, a_n)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Eval(k, x)$}
\begin{algorithmic}
\Return $g^{a_0 \prod_{i : x_i = 1} a_i}$
\Comment{$\calD = \bits^n$, $\calR = \GG$}
\end{algorithmic}
\end{algorithm}