Paper 2009/548 Original: eprint.iacr.org/2009/548 ↗
A NOTE ON YAO'S THEOREM ABOUT PSEUDORANDOM GENERATORS
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- Category
- Foundations
- Publication info
- Preprint.
- History
- 2009-11-12: last updated
- 2009-11-12: published
- Short URL
- https://ia.cr/2009/548
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}