Practical construction and analysis of pseudo-randomness primitives
2008 (English)In: Journal of Cryptology, ISSN 0933-2790, E-ISSN 1432-1378, Vol. 21, no 1, 1-26 p.Article in journal (Refereed) Published
We give a careful, fixed-size parameter analysis of a standard (Blum and Micali in SIAM J. Comput. 13( 4): 850-864, 1984; Goldreich and Levin in Proceedings of 21st ACM Symposium on Theory of Computing, pp. 25-32, 1989) way to form a pseudo-random generator from a one-way function and then pseudo-random functions from said generator (Goldreich et al. in J. Assoc. Comput. Mach. 33( 4): 792-807, 1986) While the analysis is done in the model of exact security, we improve known bounds also asymptotically when many bits are output each round and we find all auxiliary parameters efficiently, giving a uniform result. These optimizations makes the analysis effective even for security parameters/key-sizes supported by typical block ciphers and hash functions. This enables us to construct very practical pseudo-random generators with strong properties based on plausible assumptions.
Place, publisher, year, edition, pages
2008. Vol. 21, no 1, 1-26 p.
hard core function, one-way function, pseudo random generator, exact, security
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-17289DOI: 10.1007/s00145-007-9009-3ISI: 000252826900001ScopusID: 2-s2.0-38849092133OAI: oai:DiVA.org:kth-17289DiVA: diva2:335332
QC 201005252010-08-052010-08-052012-09-25Bibliographically approved