]> Cryptography - Pseudo-Random Functions

Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With PRNG's they could proceed as follows. They both seed a PRNG with the shared secret. Bob picks sends Alice some random number $i$, and Alice proves she knows the share secret by responding with the $i$th random number generated by the PRNG.

But this solution requires state, and they both have to compute $i$ random numbers. Instead, we would like "random access" to the sequence. This is the intuition behind pseudo-random functions: Bob gives alice some random $i$, and Alice returns ${F}_{K}\left(i\right)$, where ${F}_{K}\left(i\right)$ is indistinguishable from a random function, that is, given any ${x}_{1},...,{x}_{m},{F}_{K}\left({x}_{1}\right),...,{F}_{K}\left({x}_{m}\right)$, no adversary can predict ${F}_{K}\left({x}_{m+1}\right)$ for any ${x}_{m+1}$

Definition: a function $f:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{m}$ is a $\left(t,\epsilon ,q\right)$-PRF if

• Given a key $K\in \left\{0,1{\right\}}^{s}$ and an input $X\in \left\{0,1{\right\}}^{n}$ there is an "efficient" algorithm to compute ${F}_{K}\left(X\right)=F\left(X,K\right)$.

• For any $t$-time oracle algorithm $A$, we have

$\mid {\mathrm{Pr}}_{K←\left\{0,1{\right\}}^{s}}\left[{A}^{{f}_{K}}\right]-{\mathrm{Pr}}_{f\in ℱ}\left[{A}^{f}\right]\mid <\epsilon$

where $ℱ=\left\{f:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{m}\right\}$ and $A$ makes at most $q$ queries to the oracle.

PRF's can also be used for symmetric encryption: pick random $R$, then output ${E}_{K}\left(M\right)=⟨{F}_{K}\left(R\right)\oplus M,R⟩$ (roughly speaking, if $F$ is a PRF, then $E$ is semantically secure). They are also can be used as MAC's: ${\mathrm{MAC}}_{K}\left(M\right)={F}_{K}\left(M\right)$.

## Goldreich-Goldwasser-Micali

PRNG's can be used to construct PRF's [GGM'84]. Let $G:\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{2s}$ be a PRNG. Define ${G}_{0},{G}_{1}$ to be the left and right halves of $G$, so that $G\left(X\right)={G}_{0}\left(X\right)\mid \mid {G}_{1}\left(X\right)$. For any $K\in \left\{0,1{\right\}}^{s}$, define ${F}_{K}:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{s}$ by

${F}_{K}\left({x}_{1}...{x}_{n}\right)={G}_{{x}_{n}}\left({G}_{{x}_{n-1}}\left(...\left({G}_{{x}_{2}}\left({G}_{{x}_{1}}\left(K\right)\right)...\right)\right)$

Theorem: If $G$ is a $\left(t,\epsilon \right)$-PRNG then $F$ is a $\left(t-\mathrm{cn},\epsilon qn,q\right)$-PRF for some constant $c$.

## A Number Theoretic PRF

It is possible to construct a PRF based on the DDH assumption [NR'96]. Let $G$ be a cyclic group of prime order $q$ generated by $g$. Then a key has the form $\stackrel{‾}{K}=\left({K}_{0},...,{K}_{n}\right)\in {ℤ}_{q}^{n+1}$, and for $X\in \left\{0,1{\right\}}^{n}$, define

${F}_{K}\left(X\right)={F}_{K}\left({x}_{1}...{x}_{n}\right)={g}^{{K}_{0}\prod _{i=1}^{n}{K}_{i}^{{x}_{i}}}$

The running time is roughly two exponentiations.

Theorem: If $G$ satisfies the $\left(t,\epsilon \right)$-DDH assumption then $F$ is a $\left(t-\mathrm{cn},\epsilon Qn,Q\right)$-PRF for some constant $c$.

## A Parallel PRF

The following construction [NR'95] can be evaluated efficiently in parallel. The seed is $\left[{a}_{1,0},{a}_{1,1},...,{a}_{n,0},{a}_{n,1}\in \left\{0,1{\right\}}^{s}\right]$. Then to compute ${F}^{\mathrm{NR}}\left({x}_{1}...{x}_{n}\right)$, start with ${a}_{1,{x}_{1}}{a}_{2,{x}_{2}}...{a}_{n,{x}_{n}}$, and squish pairs of strings together using $S:\left\{0,1{\right\}}^{s}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{s}$. Then take the $n/2$ outputs and squish them in pairs again. Then repeat the process until there is one string in $\left\{0,1{\right\}}^{s}$ left.

When $S$ is a synthesizer, ${F}^{\mathrm{NR}}$ is a PRF. It turns out trapdoor permutations imply synthesizers. An open problem is to construct a parallel PRF from one-way permutations.

## PRF's as MAC's

Recall a MAC is a pair of algorithms $\left(\mathrm{MAC},\mathrm{MAC}-\mathrm{verify}\right)$ such that

• ${\mathrm{MAC}}_{K}\left(M\right):\left\{0,1{\right\}}^{m}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{T}$ is an "efficient" algorithm, where the tag length $T\ll n$.

• $\mathrm{MAC}-\mathrm{verify}\left(M,T,K\right)$ is an "efficient" predicate.

The $\mathrm{MAC}$ algorithm may be randomized.

Security: A MAC is $\left(t,\epsilon ,q\right)$-secure if no $t$-time algorithm can succeed with probability more than $\epsilon$ in existentially forging a MAC with a $q$-chosen message attack. In more detail, consider the following game:

1. The challenger picks a random $K←\left\{0,1{\right\}}^{s}$.

2. The adversary asks for the MACs of messages ${M}_{i}$ for $1\le i\le q$.

3. The adversary sends $⟨M,T⟩$ where $M\ne {M}_{i}$ for any $1\le i\le q$ and wins if $\mathrm{MAC}-\mathrm{verify}\left(M,T,K\right)$ is true.

The MAC is $\left(t,\epsilon ,q\right)$-secure if for all $t$-time adversaries $A$ we have $\mathrm{Pr}\left[A\mathrm{wins}\right]<\epsilon$.

It is easily seen that if $F$ is a $\left(t,\epsilon ,q\right)$-PRF then $F$ is also a $\left(t,\epsilon +1/{2}^{T},q\right)$-MAC.

Thus PRF's imply (deterministic) MAC's, but the converse is not true. For example, if $F$ is a $\left(t,\epsilon ,q\right)$-PRF then ${\mathrm{MAC}}_{K}\left(M\right)={F}_{K}\left(M\right)\mid \mid 1$ is a $\left(t,\epsilon +1/{2}^{T},q\right)$-MAC but not a PRF. In some sense, PRF's are overkill for MAC's. This motivates the following definition.

## Unpredictable Functions

A function $f:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{T}$ is a $\left(t,\epsilon ,q\right)$-unpredictable function if

1. Given $K\in \left\{0,1{\right\}}^{s}$, ${f}_{K}\left(x\right)$ can be "efficiently" computed.

2. For all $t$-time algorithms $A$ that make at most $q$ queries to $f$,

${\mathrm{Pr}}_{K←\left\{0,1{\right\}}^{s}}\left[{A}^{{f}_{K}}=\left(M,\mathrm{Tag}\right),{f}_{K}\left(M\right)=\mathrm{Tag}\right]<\epsilon$

where $A$ did not query the oracle at $M$.

Every PRF is an UF, but not conversely. However, PRF's can be constructed from UF's via the Goldreich-Levin method: $F{\prime }_{K,R}=⟨{F}_{K}\left(X\right),R⟩\in \left\{0,1\right\}$.

## Enlarging the domain of PRF's

Recall that CBC-F for a keyed function $F$ on a message $M$ is defined as follows. Break $M$ into blocks ${M}_{i}$. Then

$\mathrm{CBC}-F\left(M\right)={F}_{K}\left(...{F}_{K}\left({F}_{K}\left({F}_{K}\left({M}_{1}\right)\oplus {M}_{2}\right)\oplus {M}_{3}\right)...\right)$

Theorem: [BRK'92] (Security of CBC-MAC)

Let $F:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{T}$ be a $\left(t,\epsilon ,q\right)$-PRF. Then $\mathrm{CBC}-F\left({M}_{1},...,{M}_{b}\right)$ is a $\left(t,\epsilon +{q}^{2}{b}^{2}/{2}^{n-1},q/b\right)$-PRF.

Intuitively, CBC-F is secure if $b\ll {2}^{n/2}/q$. For larger $b$ there is a known attack (birthday attack).

## Enlarging the domain of UF's

We present three methods for doing this.

Theorem 1: Let $F:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{T}$ be a $\left(t,\epsilon ,q\right)$-UF, and let $H:\left\{0,1{\right\}}^{*}\to \left\{0,1{\right\}}^{n}$ be a collision-resistant hash function. Then

${\mathrm{HMAC}}_{K}\left(M\right)={F}_{K}\left(H\left(M\right)\right)$

is a $\left(t,\epsilon ,q\right)$-UF.

Theorem 2: Let $f:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{T}$ be a $\left(t,\epsilon ,q\right)$-PRF, and let $H=\left\{{h}_{K}:\left\{0,1{\right\}}^{N}\to \left\{0,1{\right\}}^{n}$ be a family of hash functions such that for all $x\ne y\in \left\{0,1{\right\}}^{N}$, we have ${\mathrm{Pr}}_{h←H}\left[h\left(x\right)=h\left(y\right)\right]<\epsilon \prime$. Then

${\mathrm{HF}}_{{K}_{1},{K}_{2}}\left(M\right)={f}_{{K}_{1}}\left({h}_{{K}_{2}}\left(M\right)\right)$

is a $\left(t,\epsilon +\epsilon \prime ,q\right)$-MAC.

Theorem 3: Let $f:\left\{0,1{\right\}}^{n}×\left\{0,1{\right\}}^{s}\to \left\{0,1{\right\}}^{T}$ be a $\left(t,\epsilon ,q\right)$-PRF, and let $H=\left\{{h}_{K}:\left\{0,1{\right\}}^{N}\to \left\{0,1{\right\}}^{n}$ be a family of hash functions such that for all $x,y\in \left\{0,1{\right\}}^{N}$ and for all $r\in {0,1}^{T}$, we have ${\mathrm{Pr}}_{h←H}\left[h\left(x\right)\oplus h\left(y\right)=r\right]<\epsilon \prime$. Then

${\mathrm{CWH}}_{{K}_{1},{K}_{2}}\left(M\right)=\left[{h}_{{K}_{2}}\left(M\right)\oplus {f}_{{K}_{1}}\left(R\right),R\right],R←\left\{0,1{\right\}}^{n}$

is a $\left(t,\epsilon +\epsilon \prime ,q\right)$-MAC.

Note the last theorem involves a nondeterministic MAC. In short, for a secure MAC, we can do PRF(UHF), or UF(CRHF) (so weaken the requirements on one function but strengthen the requirements on the other), or [UHF(M) $\oplus$ PRF®, R].