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.

REFERENCES

• 1: Bellare, M., Garay, J. A., and Rabin, T. 1998. Fast batch verification for modular exponentiation and digital signatures. In EUROCRYPT '98. Lecture Notes in Computer Science, vol. 1403. Springer-Verlag, Berlin. 236--250.
• 2: Colin Boyd , Chris Pavlovski, Attacking and Repairing Batch Verification Schemes, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.58-71, December 03-07, 2000
• 3: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 4: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 5: Amos Fiat, Batch RSA, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.175-185, August 20-24, 1989
• 6: Pierre-Alain Fouque , Guillaume Poupard , Jacques Stern, Sharing Decryption in the Context of Voting or Lotteries, Proceedings of the 4th International Conference on Financial Cryptography, p.90-104, February 20-24, 2000
• 7: Philippe Golle , Sheng Zhong , Dan Boneh , Markus Jakobsson , Ari Juels, Optimistic Mixing for Exit-Polls, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.451-465, December 01-05, 2002
• 8: Jens Groth, A Verifiable Secret Shuffle of Homomorphic Encryptions, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.145-160, January 06-08, 2003
• 9: Louis C. Guillou , Jean-Jacques Quisquater, A "Paradoxical" Indentity-Based Signature Scheme Resulting from Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.216-231, August 21-25, 1988
• 10: Harn, L. 1998. Batch verifying multiple DSA-type digital signatures. In Elecrronics Letters, 34, 9, 870--871.
• 11: Fumitaka Hoshino , Masayuki Abe , Tetsutaro Kobayashi, Lenient/Strict Batch Verification in Several Groups, Proceedings of the 4th International Conference on Information Security, p.81-94, October 01-03, 2001
• 12: Markus Jakobsson , Ari Juels , Ronald L. Rivest, Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, Proceedings of the 11th USENIX Security Symposium, p.339-353, August 05-09, 2002
• 13: Markus Jakobsson , Ari Juels, An optimally robust hybrid mix network, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.284-292, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384046]
• 14: Pedersen, T. P. 1991. A threshold cryptosystem without a trusted party. In EUROCRYPT '91. Springer-Verlag, Berlin. 522--526. Lecture Notes in Computer Science 547.
• 15: Pedersen, T. P. 1992. Distributed provers and verifiable secret sharing based on the discrete logarithm problem. Ph.D. thesis, Computer Science Department, Aarhus University, Aarhus, Denmark.
• 16: Peng, K., Boyd, C., Dawson, E., and Viswanathan, K. 2004. A correct, private and efficient mix network. In 2004 International Workshop on Practice and Theory in Public Key Cryptography. Lecture Notes in Computer Science, vol. 2947. Springer-Verlag, Berlin. 439--454.
• 17: Sako, K. and Killian, J. 1995. Receipt-free mix-type voting scheme---a practical solution to the implementation of a voting booth. In EUROCRYPT '95. Lecture Notes in Computer Science, vol. 921. Springer-Verlag, Berlin. 393--403.
• 18: Shoup, V. 1999. Practical threshold signature. In IBM Research Report. IBM. IBM Research Report RZ 3121.

INDEX TERMS

General Terms:
Security, Verification

Keywords:
Batch proof and verification of reencryption, batch proof and verification of decryption, mix network