Anzeige
Erschienen in:
01.12.2011
A note on Yao’s theorem about pseudo-random generators
Erschienen in: Cryptography and Communications | Ausgabe 4/2011
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Yao’s theorem gives an equivalence between the indistinguishability of a pseudo-random generator and the unpredictability of the next bit from an asymptotic point of view. In this paper we present with detailed proofs, modified versions of Yao’s theorem which can be of interest for the study of practical cryptographic primitives. In particular we consider non-asymptotic versions. We study the case of one pseudo-random generator, then the case of a family of pseudo-random generators with the same fixed length and finally we consider the asymptotic case. We compute in each case the cost of the reduction (in the sense of complexity theory) between the two algorithms.