DLOG + KEA3 ⇒ Three-message ZK arguments for NP

Standard model · BP04

Statement

Let $\mathsf{GrGen}$ output a prime-order group in which the discrete logarithm is hard and the KEA3 knowledge-of-exponent assumption holds. In such a group, the protocol of Hada and Tanaka, with a bug that made it unsound removed, is a three-message zero-knowledge argument for $\mathbf{NP}$ with negligible soundness error — BP04. HT98 had claimed the result under KEA1 and KEA2, and KEA2 is false — BP04. The simulator extracts through the knowledge assumption, so it is not black-box, and the protocol gets around the three-message bound for black-box simulation (Three-message black-box ZK ⊆ BPP) — GK96a.

Notes

• The extraction condition of KEA3 alone holds trivially in a group with easy discrete logarithms, so the definition of KEA3 includes hardness of the discrete logarithm for the same group generator — standard.
• Under assumptions on program obfuscation, three-message private-coin zero-knowledge proofs, sound against unbounded provers, for $\mathbf{NP}$ do not exist even with non-black-box simulation — FGJ18.