Nearly One-Sided Tests and the Goldreich-Levin Predicate

摘要

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.