Hard-Core Bits for Proofs of Knowledge

For various well-known proofs of knowledge, we address the problem of how much information a cheating polynomial-time verifier can learn about individual bits of the prover's secret key. Specifically, under the widely believed assumption that the Schnorr identification protocol is witness hiding, no polynomial-time verifier can distinguish the O(log k) most significant bits of the prover's secret key from equally many flips of an unbiased coin, where k is the security parameter that determines the key length. For a minor variation of Schnorr's protocol, not only the O(log k) most significant bits are hidden but also O(log k) bits that are close to the least significant bits. Similarly, the O(log k) least significant bits of the secret key of the prover in the Guillou-Quisquater identification protocol are unapproximable. All our results hold in the strongest conceivable attack scenario, in that verifiers may engage in arbitrarily many protocol executions and choose new challenges in a..