A NOTE ON YAO'S THEOREM ABOUT PSEUDORANDOM GENERATORS

Stéphane BALLET; Robert ROLLAND

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: 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},
      url = {https://eprint.iacr.org/2009/548}
}