Abstract
In this paper we will solve two open problems concerning pseudorandom permutations generators.
-
1.
We will see that it is possible to obtain a pseudorandom permutation generator with only three rounds of DES - like permutation and a single pseudorandom function. This will solve an open problem of [6].
-
2.
We will see that it is possible to obtain a super pseudorandom permutation generator with a single pseudorandom function. This will solve an open problem of [5]. For this we will use only four rounds of DES — like permutation.
For example, we will see that if ζ denotes the rotation of one bit, ψ(f, f, f o ζ o f) is a pseudorandom function generator. And ψ(f, f, f, f o ζ o f) is a super pseudorandom function generator.
Here the number of rounds used is optimal. It should be noted that here we introduce an important new idea in that we do not use a composition of f, i times, but f o ζ o f for the last round, where ζ is a fixed and public function.
Chapter PDF
Similar content being viewed by others
References
M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal and Computing, 17(2): 373–386, April 1988.
J. Patarin, New results on pseudorandom permutation generators based on the DES Scheme, Abstracts of Crypto’91, p. 7–2, 7–7.
J. Patarin, Etude des générateurs de permutations basés sut le schéma du DES, Thèse, November 1991, INRIA, Domaine de Voluceau, Le Chesnay, France.
J. Pieprzyk, How to construct pseudorandom permutations from Single Pseudorandom Functions, EUROCRYPT’90, Århus, Denmark, May 1990.
B. Sadeghiyan and J. Pieprzyk, On necessary and sufficient conditions for the construction of super pseudorandom permutations, Abstracts of Asiacrypt’91, November 1991, p. 117–123.
Y. Zheng, T. Matsumoto and H. Imai, Impossibility and optimality results on constructing pseudorandom permutations, Abstract of EUROCRYPT’89, Houthalen, Belgium, April 1989, p. 412–421.
L. J. Paige, Complete Mappings of finite groups, J. Math. 1, 111–116, 1951.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patarin, J. (1993). How to Construct Pseudorandom and Super Pseudorandom Permutations from One Single Pseudorandom Function. In: Rueppel, R.A. (eds) Advances in Cryptology — EUROCRYPT’ 92. EUROCRYPT 1992. Lecture Notes in Computer Science, vol 658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47555-9_22
Download citation
DOI: https://doi.org/10.1007/3-540-47555-9_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56413-3
Online ISBN: 978-3-540-47555-2
eBook Packages: Springer Book Archive