Abstract
This paper examines “batch zero-knowledge” protocols for communication- and computation-efficient proofs of propositions composed of many simple predicates. We focus specifically on batch protocols that use Cramer, Damgård, and Schoenmakers’ proofs of partial knowledge framework (Crypto 1994) to prove propositions that may be true even when some of their input predicates are false. Our main result is a novel system for batch zero-knowledge arguments of knowledge and equality of k-out-of-n discrete logarithms. Along the way, we propose the first general definition for batch zero-knowledge proofs and we revisit Peng and Bao’s batch zero-knowledge proofs of knowledge and equality of one-out-of-n discrete logarithms (Inscrypt 2008). Our analysis of the latter protocol uncovers a critical flaw in the security proof, and we present a practical lattice-based attack to exploit it.
An extended version of this paper is available [23].
Chapter PDF
Similar content being viewed by others
References
Araujo, R., Foulle, S., Traoré, J.: A practical and secure coercion-resistant scheme for remote elections. In: Frontiers of Electronic Voting, Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol. 7311 (July 2007)
Au, M.H., Tsang, P.P., Kapadia, A.: PEREA: Practical TTP-free revocation of repeatedly misbehaving anonymous users. ACM Transactions on Information and System Security 14(4), Article No. 29 (2011)
Au, M.H., Kapadia, A., Susilo, W.: BLACR: TTP-free blacklistable anonymous credentials with reputation. In: Proceedings of NDSS 2012, San Diego, CA, USA (February 2012)
Bellare, M., Garay, J.A., Rabin, T.: Batch verification with applications to cryptography and checking. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 170–191. Springer, Heidelberg (1998)
Bellare, M., Garay, J.A., Rabin, T.: Fast batch verification for modular exponentiation and digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236–250. Springer, Heidelberg (1998)
Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993)
Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology 21(2), 149–177 (2008)
Brands, S., Demuynck, L., De Decker, B.: A practical system for globally revoking the unlinkable pseudonyms of unknown users. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 400–415. Springer, Heidelberg (2007)
Cachin, C.: Efficient private bidding and auctions with an oblivious third party. In: Proceedings of CCS 1999, Singapore, pp. 120–127 (November 1999)
Catalano, D., Fiore, D., Messina, M.: Zero-knowledge sets with short proofs. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 433–450. Springer, Heidelberg (2008)
Clark, J., Hengartner, U.: Selections: Internet voting with over-the-shoulder coercion-resistance. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 47–61. Springer, Heidelberg (2012)
Cramer, R., Damgård, I., Schoenmakers, B.: Proof of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Fürer, M.: Faster integer multiplication. SIAM Journal on Computing 39(3), 979–1005 (2009)
Gennaro, R., Leigh, D., Sundaram, R., Yerazunis, W.S.: Batching schnorr identification scheme with applications to privacy-preserving authorization and low-bandwidth communication devices. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 276–292. Springer, Heidelberg (2004)
Goldberg, I.: Improving the robustness of private information retrieval. In: Proceedings of IEEE S&P 2007, Oakland, CA, USA, pp. 131–148 (May 2007)
Goldreich, O.: A note on computational indistinguishability. Information Processing Letters 34(6), 277–281 (1990)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or languages in NP have zero-knowledge proof systems. Journal of the ACM 38(3), 691–729 (1991)
Goldreich, O., Sahai, A., Vadhan, S.P.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: Proceedings of STOC 1998, Dallas, TX, USA, pp. 399–408 (1998)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems (extended abstract). In: Proceedings of STOC 1985, Providence, RI, USA, pp. 291–304 (May 1985)
Groth, J.: A verifiable secret shuffle of homomorphic encryptions. Journal of Cryptology 23(4), 546–579 (2010)
Henry, R., Goldberg, I.: All-but-k mercurial commitments and their applications. Technical Report CACR 2012-26, University of Waterloo, Waterloo, ON, Canada (November 2012)
Henry, R., Goldberg, I.: Batch proofs of partial knowledge. Technical Report CACR 2013-08, University of Waterloo, Waterloo, ON, Canada (February 2013)
Henry, R., Olumofin, F.G., Goldberg, I.: Practical PIR for electronic commerce. In: Proceedings of CCS 2011, Chicago, IL, USA, pp. 677–690 (October 2011)
Juels, A., Catalano, D., Jakobsson, M.: Coercion-resistant electronic elections. In: Proceedings of WPES 2005, Alexandria, VA, USA, pp. 61–70 (November 2005)
Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177–194. Springer, Heidelberg (2010)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982)
Peng, K., Bao, F.: Batch ZK proof and verification of OR logic. In: Yung, M., Liu, P., Lin, D. (eds.) Inscrypt 2008. LNCS, vol. 5487, pp. 141–156. Springer, Heidelberg (2009)
Peng, K., Bao, F.: Batch range proof for practical small ranges. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 114–130. Springer, Heidelberg (2010)
Peng, K., Boyd, C., Dawson, E.: Batch zero-knowledge proof and verification and its applications. ACM Transactions on Information and System Security 10(2), Article No. 6 (2007)
Sako, K., Kilian, J.: Receipt-free mix-type voting scheme. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 393–403. Springer, Heidelberg (1995)
Spycher, O., Koenig, R.E., Haenni, R., Schläpfer, M.: A new approach towards coercion-resistant remote e-voting in linear time. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 182–189. Springer, Heidelberg (2012)
Tsang, P.P., Au, M.H., Kapadia, A., Smith, S.W.: BLAC: Revoking repeatedly misbehaving anonymous users without relying on TTPs. ACM Transactions on Information and Systems Security 13(4), Article No. 39 (2010)
Tsang, P.P., Wei, V.K., Chan, T.K., Au, M.H., Liu, J.K., Wong, D.S.: Separable linkable threshold ring signatures. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 384–398. Springer, Heidelberg (2004)
Weber, S.G., Araujo, R., Buchmann, J.: On coercion-resistant electronic elections with linear work. In: Proceedings of ARES 2007, Vienna, Austria, pp. 908–916 (April 2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Henry, R., Goldberg, I. (2013). Batch Proofs of Partial Knowledge. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds) Applied Cryptography and Network Security. ACNS 2013. Lecture Notes in Computer Science, vol 7954. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38980-1_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-38980-1_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38979-5
Online ISBN: 978-3-642-38980-1
eBook Packages: Computer ScienceComputer Science (R0)