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)


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.


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.


  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.CrossRefGoogle Scholar
  2. 2.
    O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, 1986.CrossRefMathSciNetGoogle Scholar
  3. 3.
    O. Goldreich, N. Nisan, and A. Wigderson. On yao’s xor-lemma., 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.CrossRefMathSciNetGoogle Scholar
  5. 5.
    R. Impagliazzo. Hard core distributions for somewhat hard problems., 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.zbMATHCrossRefMathSciNetGoogle Scholar
  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.zbMATHCrossRefMathSciNetGoogle Scholar
  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.zbMATHCrossRefMathSciNetGoogle Scholar
  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

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Steven Myers
    • 1
  1. 1.Department of Computer ScienceUniversity of TorontoTorontoCanada

Personalised recommendations