Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Pseudo-randomness

Publication Info: the paper is not published nor submitted elsewhere

Date: received 8 Nov 2009, last revised 9 Nov 2009

Contact author: robert rolland at acrypta fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20091112:042241 (All versions of this report)

Short URL: ia.cr/2009/548

Discussion forum: Show discussion | Start new discussion