skip to main content
article

Batch zero-knowledge proof and verification and its applications

Published: 01 May 2007 Publication History

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]
Boyd, C. and Pavlovski, C. 2000. Attacking and repairing batch verification schemes. In ASIACRYPT '00. Lecture Notes in Computer Science, vol. 1976. Springer-Verlag, Berlin. 58--71.
[3]
Chaum, D. 1981. Untraceable electronic mail, return address and digital pseudonym. Communications of the ACM, 24, 2, 84--88.
[4]
Chaum, D. and Pedersen, T. P. 1992. Wallet databases with observers. In CRYPTO '92. Lecture Notes in Computer Science, vol. 740. Springer-Verlag, Berlin. 89--105.
[5]
Fiat, A. 1989. Batch RSA. In CRYPTO '89. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, Berlin. 175--185.
[6]
Fouque, P.-A., Poupard, G., and Stern, J. 2000. Sharing decryption in the context of voting or lotteries. In Financial Cryptography 2000. vol. 1962. Springer-Verlag, Berlin. 90--104. Lecture Notes in Computer Science.
[7]
Golle, P., Zhong, S., Boneh, D., Jakobsson, M., and Juels, A. 2002. Optimistic mixing for exit-polls. In ASIACRYPT '02. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, Berlin. 451--465.
[8]
Groth, J. 2003. A verifiable secret shuffle of homomorphic encryptions. In Public Key Cryptography 2003. Lecture Notes in Computer Science, vol. 2567. Springer-Verlag, Berlin. 145--160.
[9]
Guillou, L. C. and Quisquater, J. J. 1989. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. In CRYPTO '88, S. Goldwasser, Ed. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, Berlin. 216--231.
[10]
Harn, L. 1998. Batch verifying multiple DSA-type digital signatures. In Elecrronics Letters, 34, 9, 870--871.
[11]
Hoshino, F., Abe, M., and Kobayashi, T. 2001. Lenient/Strict batch verification in several groups. In Information Security, 4th International Conference, ISC 2001. Lecture Notes in Computer Science, vol. 2200. Springer-Verlag, Berlin. 81--94.
[12]
Jakobsson, M., Juels, A., and Rivest, R. L. 2002. Making mix nets robust for electronic voting by randomized partial checking. In Proceedings of the 11th USENIX Security Symposium, San Francisco, CA. (Aug. 5--9), 2002. USENIX. 339--353.
[13]
Juels, A. and Jakobsson, M. 2001. An optimally robust hybrid mix network. In Proc. of the 20th annual ACM Symposium on Principles of Distributed Computation. ACM, New York. 284--292.
[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.

Cited By

View all
  • (2023)Research on security access authentication mechanism of intelligent sensor based on non-interactive zero-knowledge proof methodJournal of Computational Methods in Sciences and Engineering10.3233/JCM-226750(1-9)Online publication date: 11-May-2023
  • (2023)Electronic Voting Privacy Protection Scheme Based on Double Signature in Consortium BlockchainArtificial Intelligence Security and Privacy10.1007/978-981-99-9785-5_38(548-562)Online publication date: 3-Dec-2023
  • (2022)Privacy-preserving Byzantine-robust federated learningComputer Standards & Interfaces10.1016/j.csi.2021.10356180:COnline publication date: 23-Apr-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Information and System Security
ACM Transactions on Information and System Security  Volume 10, Issue 2
May 2007
144 pages
ISSN:1094-9224
EISSN:1557-7406
DOI:10.1145/1237500
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2007
Published in TISSEC Volume 10, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Batch proof and verification of reencryption
  2. batch proof and verification of decryption
  3. mix network

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)38
  • Downloads (Last 6 weeks)4
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Research on security access authentication mechanism of intelligent sensor based on non-interactive zero-knowledge proof methodJournal of Computational Methods in Sciences and Engineering10.3233/JCM-226750(1-9)Online publication date: 11-May-2023
  • (2023)Electronic Voting Privacy Protection Scheme Based on Double Signature in Consortium BlockchainArtificial Intelligence Security and Privacy10.1007/978-981-99-9785-5_38(548-562)Online publication date: 3-Dec-2023
  • (2022)Privacy-preserving Byzantine-robust federated learningComputer Standards & Interfaces10.1016/j.csi.2021.10356180:COnline publication date: 23-Apr-2022
  • (2022)Verifiable Decryption in the HeadInformation Security and Privacy10.1007/978-3-031-22301-3_18(355-374)Online publication date: 28-Nov-2022
  • (2021)Non-interactive zero-knowledge proof scheme from RLWE-based key exchangePLOS ONE10.1371/journal.pone.025637216:8(e0256372)Online publication date: 20-Aug-2021
  • (2021)PriScore: Blockchain-Based Self-Tallying Election System Supporting Score VotingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2021.310849416(4705-4720)Online publication date: 1-Jan-2021
  • (2021)A Novel Proof of Shuffle: Exponentially Secure Cut-and-ChooseInformation Security and Privacy10.1007/978-3-030-90567-5_15(293-308)Online publication date: 1-Dec-2021
  • (2019)There Are 10 Types of Vectors (and Polynomials)Proceedings of the 18th ACM Workshop on Privacy in the Electronic Society10.1145/3338498.3358640(37-49)Online publication date: 11-Nov-2019
  • (2019)Efficient Zero-Knowledge Arguments in the Discrete Log Setting, RevisitedProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security10.1145/3319535.3354251(2093-2110)Online publication date: 6-Nov-2019
  • (2019)An Improved Non-Interactive Zero-Knowledge Range Proof for Decentralized Applications2019 IEEE International Conference on Decentralized Applications and Infrastructures (DAPPCON)10.1109/DAPPCON.2019.00025(129-134)Online publication date: Apr-2019
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media