Batch zero-knowledge proof and verification and its applications

Abstract

The batch verification technique of Bellare et al. is extended to verification of several frequently employed zero-knowledge proofs. The new techniques are correct, sound, efficient, and can be widely applied. Specific applications are discussed in detail, including batch ZK proof and verification of validity of encryption (or reencryption) and batch ZK proof and verification of validity of decryption. Considerable efficiency improvements are gained in these two applications without compromising security. As a result, efficiency of the practical cryptographic systems (such as mix networks) based on these two applications is dramatically improved.