# Basing {PRF}s on Constant-Query Weak {PRF}s: Minimizing Assumptions for Efficient Symmetric Cryptography

## Ueli Maurer and Stefano Tessaro

```
```Although it is well known that all basic private-key cryptographic
primitives can be built from one-way functions, finding weak assumptions
from which practical implementations of such primitives exist remains a
challenging task. Towards this goal, this paper introduces the notion of
a * constant-query weak PRF*}, a function with a secret key which is
computationally indistinguishable from a truly random function when
evaluated at a * constant*} number $s$ of known random inputs, where
$s$ can be as small as two.

We provide iterated constructions of (arbitrary-input-length) PRFs from
constant-query weak PRFs that even improve the efficiency of previous
constructions based on the stronger assumption of a weak PRF (where
polynomially many evaluations are allowed).

One of our constructions directly provides a new mode of operation using
a constant-query weak PRF for IND-CPA symmetric encryption which is
essentially as efficient as conventional PRF-based counter-mode
encryption.

Furthermore, our constructions yield efficient modes of operation for
keying hash functions (such as MD5 and SHA-1) to obtain iterated PRFs
(and hence MACs) which rely solely on the assumption that the underlying
compression function is a constant-query weak PRF, which is the weakest
assumption ever considered in this context.