Abstract
We evaluate constructions for building pseudo-random functions (PRFs) from pseudo-random permutations (PRPs). We present two constructions: a slower construction which preserves the security of the PRP and a faster construction which 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 constructions—e.g. pseudo-random generators—to create the wider block cipher. The security of the resulting cipher will be as strong as the original block cipher.
The full paper is available at http://www.counterpane.com/publish-1998.html.
Chapter PDF
Keywords
References
W. Aiello, R. Venkatesan, “Foiling birthday attacks in length doubling transformations,” Advances in Cryptology — EUROCRYPT '96 Proceedings, Springer-Verlag, pp. 307–320.
M. Bellare, R. Canetti, H. Krawczyk, “Pseudorandom Functions Revisited: The Cascade Construction and its Concrete Security,” Proceedings of the 37th Symposium on Foundations of Computer Science, IEEE, 1996.
M. Bellare, A. Desai, E. Jokipii, P. Rogaway, “A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation,” Full version, Extended abstract in Proceedings of 38th Annual Symposium on Foundations of Computer Science (FOCS 97), IEEE, 1997.
M. Bellare, R. Guérin, P. Rogaway, “XOR MACs: New methods for message authentication using finite pseudorandom functions,” Advances in Cryptology—CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp 15–28.
M. Bellare, J. Kilian, P. Rogaway, “The security of cipher block chaining,” Advances in Cryptology—CRYPTO '94 Proceedings, Springer-Verlag, 1994.
M. Billare, T. Krovetz, P. Rogaway, “Luby-Rackoff Backwards: Increasing Security by Making Block Ciphers Non-Invertible (Extended Abstract),” Advances in Cryptology—EUROCRYPT '98 Proceedings, Springer-Verlag, 1998.
M. Blum, S. Micali, “How to Generate Cryptographically Strong Sequences of Pseudo-random Bits,” SIAM J. Comput., 13 (Nov. 1984), pp. 850–864.
D. Coppersmith, “Luby-Rackoff: Four rounds is not enough,” IBM Research Report, RC 20674 (12/24/96), Mathematics.
O. Goldreich, S. Goldwasser, S. Micali, “How to Construct Random Functions,” Journal of the ACM, Vol. 33, No. 4, October 1986, pp. 792–807.
M. Luby, C. Rackoff, “How to Construct Pseudorandom Permutations from Pseudorandom Functions,” SIAM J. Comput., Vol. 17, No. 2, April 1988, pp. 373–386.
M. Luby, Pseudorandomness and Cryptographic Applications, Princeton University Press, 1996.
S. Lucks, “Faster Ruby-Lackoff Ciphers,” Proceedings of Third Fast Software Encryption Workshop, Springer-Verlag, pp. 189–203.
U.M. Maurer, “A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators,” Advances in Cryptology—EUROCRYPT '92 Proceedings, Springer-Verlag, 1992, pp. 239–255.
S.M. Matyas, C.H. Meyeter, J. Oseas, “Generating strong one-way functions with cryptographic algorithm,” IBM Technical Disclosure Bulletin, 27 (1985), 5658–5659.
M. Naor, O. Reingold, “On the construction of pseudo-random permutations: Luby-Rackoff revisited.,” preliminary version, http://www.wisdom.veizmann.ac.il/Papers/trs/CS96-10/abstract.html
J. Pieprzyk, “How to Construct Pseudorandom Permutations from Single Pseudorandom Functions,” Advances in Cryptology—EUROCRYPT '90, Springer-Verlag, pp. 140–150.
J. Patarin, “Etude des gńŕateurs de permutations basés sure le Schéma du D.E.S.,” Ph. D. Thesis, INRIA, Domaine de Voluceau, Le Chesnay, France, 1991.
J. Patarin, “New Results on Pseudorandom Permutation Generators Based on the DES Scheme,” Advances in Cryptology—CRYPTO '91 Proceedings, Springer-Verlag, pp. 301–312.
J. Patarin, “How to Consruct Pseudorandom and Super Pseudorandom Permutations from One Single Pseudorandom Function,” Advances in Cryptology—EUROCRYPT '92 Proceedings, Springer-Verlag, pp. 256–266.
J. Patarin, “Improved Security Bounds for Pseudorandom Permutations,” Proceedings of the Fourth ACM Conference on Computer and Communications Security, April 1–4, 1997, pp. 142–150.
J. Patarin, “About Feistel Schemes with Six (or More) Rounds,” Proceedings of the Fifth Fast Software Encryption Workshop, LNCS 1372, Springer, 1998, pp. 103–121.
B. Preneel, P. van Oorschot, “MDx MAC and building fast MACs from hash functions,” Advances in Cryptology—CRYPTO '95 Proceedings, LNCS 1070, Springer-Verlag, 1996.
B. Sadeghiyan, J. Pieprzyk, “On Necessary and Sufficient Conditions for the Construction of Super Pseudorandom Permutations,” Advances in Cryptology—ASIACRYPT '91, Springer-Verlag, pp. 194–209.
B. Sadeghiyan, J. Pieprzyk, “A Construction for Super Pseudorandom Permutations from A Single Pseudorandom Function,” Advances in Cryptology—EUROCRYPT '92, Springer-Verlag, pp. 267–284.
A.C. Yao, “Theory and Applications of Trapdoor Functions,” Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1982, pp. 80–91.
, Y. Zheng, T. Matsumoto, H. Imai, “On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypothesis,” Advances in Cryptology—CRYPTO '89 Proceedings, Springer-Verlag, pp. 461–480.
Y. Zheng, T. Matsumoto, H. Imai, “Impossibility and Optimality Results on Constructing Pseudorandom Permutations,” Advances in Cryptology—EUROCRYPT '89, Springer-Verlag, pp. 412–421.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hall, C., Wagner, D., Kelsey, J., Schneier, B. (1998). Building PRFs from PRPs. In: Krawczyk, H. (eds) Advances in Cryptology — CRYPTO '98. CRYPTO 1998. Lecture Notes in Computer Science, vol 1462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055742
Download citation
DOI: https://doi.org/10.1007/BFb0055742
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64892-5
Online ISBN: 978-3-540-68462-6
eBook Packages: Springer Book Archive