Analyzing the HB and HB+ protocols in the “large error” case

HB and HB+ are two shared-key, unidirectional authentication protocols whose extremelylow computational cost makes them potentially well-suited for severely resource-constrained
devices. Security of these protocols is based on the conjectured hardness of learning parity
with noise; that is, learning a secret s given “noisy” dot products of s that are incorrect with
probability ε.
Although the problem of learning parity with noise is meaningful for any constant ε < 1/2,
existing proofs of security for HB and HB+ only imply security when ε < 1/4. In this note, we
show how to extend these proofs to the case of arbitrary ε < 1/2.