EUROCRYPT 2001: Advances in Cryptology — EUROCRYPT 2001 pp 358-372

# Efficient Amplification of the Security of Weak Pseudo-random Function Generators

• Steven Myers
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)

## Abstract

We show that given a PRFG (pseudo-random function generator) G which is $$\frac{1} {c} -$$ partially secure, the construction $$\frac{1} {c} -$$ $$\frac{1} {c} -$$ produces a strongly secure PRFG, where g i G and r i are strings of random bits. Thus we present the first “natural” construction of a (totally secure) PRFG from a partially secure PRFG. Using results of Luby and Rackoff, this result also demonstrates how to “naturally” construct a PRPG from partially secure PRPG.

## Keywords

Random String Data Encryption Standard Oracle Query Permutation Generator Decision Circuit
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
W. Aiello, M. Bellare, G. Di Crescenzo, and R. Vekatesan. Security amplification by composition: The case of doubly-iterated, ideal ciphers. In H. Krawczyk, editor, Advances in Cryptology-Crypto 98, volume 1462 of LNCS, pages 390–407. Springer-Verlag, 1998.
2. 2.
O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, 1986.
3. 3.
O. Goldreich, N. Nisan, and A. Wigderson. On yao’s xor-lemma. http://theory.lcs.mit.edu/~oded/, 1995.
4. 4.
J. Hastad, R. Impagliazzo, L.A. Levin, and M. Luby. Construction of pseudorandom generator from any one-way function. Accepted to the SIAM Journal of Computing, 28(4):1364–1396, 1998.
5. 5.
R. Impagliazzo. Hard core distributions for somewhat hard problems. http://www-cse.ucsd.edu/~russell/, 1994.
6. 6.
J. Kilian and P. Rogaway. How to protect DES against exhaustive key search. In N. Koblitz, editor, Advances in Cryptology-Crypto 96, volume 1109 of LNCS, pages 252–267. Springer-Verlag, 1996.Google Scholar
7. 7.
L.A. Levin. One-way functions and pseudorandom generators. Combinatorica, 7(4):357–363, 1987.
8. 8.
M. Luby and C. Rackoff. Pseudo-random permutation generators and cryptographic composition. In Proceedings of the 18th Annual Symposium on Theory of Computing, pages 353–363. ACM, 1986.Google Scholar
9. 9.
M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17:373–386, 1988.
10. 10.
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.Google Scholar
11. 11.
Steven Myers. On the Development of Pseudo-Random Function Generators and Block-Ciphers using the XOR and Composition Operators. M.Sc. Thesis. University of Toronto, Canada, 1999.Google Scholar
12. 12.
Moni Naor and Omer Reingold. On the construction of pseudo-random permutations: Luby-Rackoff revisited. Journal of Cryptology, 12(1):29–66, 1999.
13. 13.
Andrew Yao. Theory and applications of trapdoor functions (extended abstract). In Proceedings of the 23rd Symposium on Foundations of Computer Science, pages 80–91. IEEE, 1982.Google Scholar