Building PRFs from PRPs

C. Hall, D. Wagner, J. Kelsey, and B. Schneier

Advances in Cryptology---Crypto 98 Proceedings, 1998, pp. 370-389.

ABSTRACT: We evaluate constructions for building pseudo-random functions (PRFs) from pseudo-random permutations (PRPs). We present two constructions: a slower construction that preserves the security of the PRP and a faster construction that has less security. One application of our construction is to build a wider block cipher given a block cipher as a building tool. We do not require any additional construction—e.g. pseudo-random number generators—to create the wider block cipher. The security of the resulting cipher will be as strong as the original block cipher.

Keywords. Pseudo-random permutations, pseudo-random functions, concrete security, block ciphers, cipher feedback mode.

[full text – PDF (Acrobat)] [full text – Postscript]

Categories: Cipher Design

Sidebar photo of Bruce Schneier by Joe MacInnis.