]> 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 ith 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(i), where F K(i) is indistinguishable from a random function, that is, given any x 1 ,...,x m,F K(x 1 ),...,F K(x m), no adversary can predict F K(x m+1 ) for any x m+1

Definition: a function f:{0,1 } n×{0,1 } s{0,1 } m is a (t,ε,q)-PRF if

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

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

Pr K{0,1 } s[A f K]Pr f[A f]<ε

where ={f:{0,1 } n{0,1 } m} 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(M)=F K(R)M,R (roughly speaking, if F is a PRF, then E is semantically secure). They are also can be used as MAC's: MAC K(M)=F K(M).

Goldreich-Goldwasser-Micali

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

F K(x 1 ...x n)=G x n(G x n1 (...(G x 2 (G x 1 (K))...))

Theorem: If G is a (t,ε)-PRNG then F is a (tcn,εqn,q)-PRF for some constant c.

The proof on this page.

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 K=(K 0 ,...,K n) q n+1 , and for X{0,1 } n, define

F K(X)=F K(x 1 ...x n)=g K 0 i=1 nK i x i

The running time is roughly two exponentiations.

Theorem: If G satisfies the (t,ε)-DDH assumption then F is a (tcn,εQn,Q)-PRF for some constant c.

A Parallel PRF

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

When S is a synthesizer, F 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 (MAC,MACverify) such that

  • MAC K(M):{0,1 } m×{0,1 } s{0,1 } T is an "efficient" algorithm, where the tag length Tn.

  • MACverify(M,T,K) is an "efficient" predicate.

The MAC algorithm may be randomized.

Security: A MAC is (t,ε,q)-secure if no t-time algorithm can succeed with probability more than ε 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{0,1 } s.

  2. The adversary asks for the MACs of messages M i for 1 iq.

  3. The adversary sends M,T where MM i for any 1 iq and wins if MACverify(M,T,K) is true.

The MAC is (t,ε,q)-secure if for all t-time adversaries A we have Pr[Awins]<ε.

It is easily seen that if F is a (t,ε,q)-PRF then F is also a (t,ε+1 /2 T,q)-MAC.

Thus PRF's imply (deterministic) MAC's, but the converse is not true. For example, if F is a (t,ε,q)-PRF then MAC K(M)=F K(M)1 is a (t,ε+1 /2 T,q)-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:{0,1 } n×{0,1 } s{0,1 } T is a (t,ε,q)-unpredictable function if

  1. Given K{0,1 } s, f K(x) can be "efficiently" computed.

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

Pr K{0,1 } s[A f K=(M,Tag),f K(M)=Tag]<ε

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 K,R=F K(X),R{0,1 }.

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

CBCF(M)=F K(...F K(F K(F K(M 1 )M 2 )M 3 )...)

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

Let F:{0,1 } n×{0,1 } s{0,1 } T be a (t,ε,q)-PRF. Then CBCF(M 1 ,...,M b) is a (t,ε+q 2 b 2 /2 n1 ,q/b)-PRF.

Intuitively, CBC-F is secure if b2 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:{0,1 } n×{0,1 } s{0,1 } T be a (t,ε,q)-UF, and let H:{0,1 } *{0,1 } n be a collision-resistant hash function. Then

HMAC K(M)=F K(H(M))

is a (t,ε,q)-UF.

Theorem 2: Let f:{0,1 } n×{0,1 } s{0,1 } T be a (t,ε,q)-PRF, and let H={h K:{0,1 } N{0,1 } n be a family of hash functions such that for all xy{0,1 } N, we have Pr hH[h(x)=h(y)]<ε. Then

HF K 1 ,K 2 (M)=f K 1 (h K 2 (M))

is a (t,ε+ε,q)-MAC.

Theorem 3: Let f:{0,1 } n×{0,1 } s{0,1 } T be a (t,ε,q)-PRF, and let H={h K:{0,1 } N{0,1 } n be a family of hash functions such that for all x,y{0,1 } N and for all r0,1 T, we have Pr hH[h(x)h(y)=r]<ε. Then

CWH K 1 ,K 2 (M)=[h K 2 (M)f K 1 (R),R],R{0,1 } n

is a (t,ε+ε,q)-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) PRF®, R].