# Information Security and Cryptography Research Group

## Basing PRFs on Constant-Query Weak PRFs: Minimizing Assumptions for Efficient Symmetric Cryptography

### Ueli Maurer and Stefano Tessaro

Advances in Cryptology — ASIACRYPT 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 5350, pp. 161–178, Dec 2008.

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.

## BibTeX Citation

@inproceedings{MauTes08,
author       = {Ueli Maurer and Stefano Tessaro},
title        = {Basing {PRF}s on Constant-Query Weak {PRF}s: Minimizing Assumptions for Efficient Symmetric Cryptography},
editor       = {Josef Pieprzyk},
booktitle    = {Advances in Cryptology --- ASIACRYPT 2008},
pages        = 161--178,
series       = {Lecture Notes in Computer Science},
volume       = 5350,
year         = 2008,
month        = 12,
publisher    = {Springer-Verlag},
}