Nearly one-sided tests and the Goldreich-Levin predicate
2004 (English)In: Journal of Cryptology, ISSN 0933-2790, E-ISSN 1432-1378, Vol. 17, no 3, 209-229 p.Article in journal (Refereed) Published
We study statistical tests with binary output that rarely outputs one, which we call nearly one-sided statistical tests. We provide an efficient reduction establishing improved security for the Goldreich-Levin hard-core bit against nearly one-sided tests. The analysis is extended to prove the security of the Blum-Micali pseudo-random generator combined with the Goldreich-Levin bit. Finally, some applications where nearly one-sided tests occur naturally are discussed.
Place, publisher, year, edition, pages
2004. Vol. 17, no 3, 209-229 p.
nearly one-sided statistical test, Goldreich-Levin predicate, pseudorandom generator, provable security, list decoding of Hadamard code
IdentifiersURN: urn:nbn:se:kth:diva-44865DOI: 10.1007/s00145-003-0141-4ISI: 000222469900002ScopusID: 2-s2.0-4344609701OAI: oai:DiVA.org:kth-44865DiVA: diva2:451529
QC 201110262011-10-262011-10-252011-10-26Bibliographically approved