Three-Round Public-Coin Bounded-Auxiliary-Input Zero-Knowledge Arguments of Knowledge

This paper investigates the exact round complexity of public-coin (bounded-auxiliary-input) zero-knowledge arguments of knowledge (ZKAOK). It is well-known that Barak’s non-black-box ZK [FOCS 01], which can be adapted to a ZKAOK, is the first one achieving constant-round, public-coin and strict-polynomial-time simulation properties, and admitting a 6-round implementation shown by Ostrovsky and Visconti [ECCC 12]. This achieves the best exact round complexity for public-coin ZKAOK ever known, to the best of our knowledge. As for a specific case of bounded-auxiliary-input verifiers, i.e. the auxiliary inputs are of bounded-size, no previous works explicitly considered to improve the general result on the exact round number of public-coin ZKAOK in this case. It is also noticeable that when ignoring the argument of knowledge property, Barak et al. [JCSS 06] showed based on two-round public-coin universal arguments which admit a candidate construction of the two-round variant of Micali’s CS-proof, there exists a two-round public-coin plain/bounded-auxiliary-input ZK argument.