Paper 2009/548

A NOTE ON YAO'S THEOREM ABOUT PSEUDORANDOM GENERATORS

Stéphane BALLET and Robert ROLLAND

Abstract

The Yao's theorem gives an equivalence between the indistinguishability of a pseudorandom generator and the impredictability of the next bit from an asymptotic point of view. We present in this paper, with detailed proofs, some modified versions of the Yao's theorem which can be of interest for the study of practical systems. We study the case of one pseudorandom generator, then the case of a family of pseudorandom generators having the same fixed length and last an asymptotical version of the previous result. We compute in each case the cost of the reduction between the two algorithms.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. the paper is not published nor submitted elsewhere
Keywords
Pseudo-randomness
Contact author(s)
robert rolland @ acrypta fr
History
2009-11-12: received
Short URL
https://ia.cr/2009/548
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/548,
      author = {Stéphane BALLET and Robert ROLLAND},
      title = {A NOTE ON YAO'S THEOREM ABOUT PSEUDORANDOM GENERATORS},
      howpublished = {Cryptology ePrint Archive, Paper 2009/548},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/548}},
      url = {https://eprint.iacr.org/2009/548}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.