On the portability of generalized Schnorr proofs. (English) Zbl 1239.94039
Joux, Antoine (ed.), Advances in cryptology – EUROCRYPT 2009. 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26–30, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-01000-2/pbk). Lecture Notes in Computer Science 5479, 425-442 (2009).
Summary: The notion of Zero Knowledge Proofs (of knowledge) (ZKP) is central to cryptography; it provides a set of security properties that proved indispensable in concrete protocol design. These properties are defined for any given input and also for any auxiliary verifier private state, as they are aimed at any use of the protocol as a subroutine in a bigger application. Many times, however, moving the theoretical notion to practical designs has been quite problematic. This is due to the fact that the most efficient protocols fail to provide the above ZKP properties for all possible inputs and verifier states. This situation has created various problems to protocol designers who have often either introduced imperfect protocols with mistakes or with lack of security arguments, or they have been forced to use much less efficient protocols in order to achieve the required properties. In this work we address this issue by introducing the notion of “protocol portability”, a property that identifies input and verifier state distributions under which a protocol becomes a ZKP when called as a subroutine in a sequential execution of a larger application. We then concentrate on the very efficient and heavily employed “Generalized Schnorr Proofs” (GSP) and identify the portability of such protocols. We also point to previous protocol weaknesses and errors that have been made in numerous applications throughout the years, due to employment of GSP instances while lacking the notion of portability (primarily in the case of unknown order groups). This demonstrates that cryptographic application designers who care about efficiency need to consider our notion carefully. We provide a compact specification language for GSP protocols that protocol designers can employ. Our specification language is consistent with the ad-hoc notation that is currently widely used and it offers automatic derivation of the proof protocol while dictating its portability (i.e., the proper initial state and inputs) and its security guarantees. Finally, as a second alternative to designers wishing to use GSPs, we present a modification of GSP protocols that is unconditionally portable (i.e., ZKP) and is still quite efficient. Our constructions are the first such protocols proven secure in the standard model (as opposed to the random oracle model).
For the entire collection see [Zbl 1161.94003].
For the entire collection see [Zbl 1161.94003].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Ateniese, G., Camenisch, J.L., Joye, M., Tsudik, G.: A Practical and Provably Secure Coalition-Resistant Group Signature Scheme. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, p. 255. Springer, Heidelberg (2000) · Zbl 0995.94544 · doi:10.1007/3-540-44598-6_16 |
| [2] | Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: Remarks on ”analysis of one popular group signature scheme” in asiacrypt 2006. Cryptology ePrint Archive, Report 2006/464 (2006), http://eprint.iacr.org/ · Zbl 1171.94337 |
| [3] | Ateniese, G., Song, D.X., Tsudik, G.: Quasi-efficient revocation in group signatures. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 183–197. Springer, Heidelberg (2003) · Zbl 1275.94037 · doi:10.1007/3-540-36504-4_14 |
| [4] | Bangerter, E.: On Efficient Zero-Knowledge Proofs of Knowledge. PhD thesis, Ruhr U. Bochum (2005) · Zbl 1081.94015 |
| [5] | Bangerter, E., Camenisch, J.L., Maurer, U.M.: Efficient proofs of knowledge of discrete logarithms and representations in groups with hidden order. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 154–171. Springer, Heidelberg (2005), http://www.zurich.ibm.com/ /jca/papers/bacama05.pdf · Zbl 1081.94015 · doi:10.1007/978-3-540-30580-4_11 |
| [6] | 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) · Zbl 0823.94016 · doi:10.1007/3-540-48071-4_28 |
| [7] | Boudot, F.: Efficient Proofs that a Committed Number Lies in an Interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000) · Zbl 1082.94534 · doi:10.1007/3-540-45539-6_31 |
| [8] | Bresson, E., Stern, J.: Efficient revocation in group signatures. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 190–206. Springer, Heidelberg (2001) · Zbl 0993.94553 · doi:10.1007/3-540-44586-2_15 |
| [9] | Brickell, E., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Proc. 11th ACM Conference on Computer and Communications Security, pp. 225–234. ACM Press, New York (2004) |
| [10] | Bussard, L., Molva, R., Roudier, Y.: History-Based Signature or How to Trust Anonymous Documents. In: Jensen, C., Poslad, S., Dimitrakos, T. (eds.) iTrust 2004. LNCS, vol. 2995, pp. 78–92. Springer, Heidelberg (2004) · Zbl 1126.68642 · doi:10.1007/978-3-540-24747-0_7 |
| [11] | Bussard, L., Roudier, Y., Molva, R.: Untraceable secret credentials: Trust establishment with privacy. In: PerCom Workshops, pp. 122–126. IEEE Computer Society, Los Alamitos (2004) |
| [12] | Camenisch, J., Kiayias, A., Yung, M.: On the portability of generalized schnorr proofs. Technical report, Cryptology ePrint Archive (2009) · Zbl 1239.94039 |
| [13] | Camenisch, J.L., Shoup, V.: Practical Verifiable Encryption and Decryption of Discrete Logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003) · Zbl 1122.94357 · doi:10.1007/978-3-540-45146-4_8 |
| [14] | Camenisch, J.L., Stadler, M.A.: Efficient Group Signature Schemes for Large Groups. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 410–424. Springer, Heidelberg (1997) · Zbl 0882.94018 · doi:10.1007/BFb0052252 |
| [15] | Camenisch, J.L.: Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zürich, Diss. ETH No. 12520. Hartung Gorre Verlag, Konstanz (1998) |
| [16] | Cao, Z.: Analysis of One Popular Group Signature Scheme. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 460–466. Springer, Heidelberg (2006) · Zbl 1172.94610 · doi:10.1007/11935230_30 |
| [17] | Chan, A.H., Frankel, Y., Tsiounis, Y.: Easy Come - Easy Go Divisible Cash. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 561–575. Springer, Heidelberg (1998) · Zbl 0929.68063 · doi:10.1007/BFb0054154 |
| [18] | Chan, A.H., Frankel, Y., Tsiounis, Y.: Easy come - easy go divisible cash. GTE Technical Report (1998), http://www.ccs.neu.edu/home/yiannis/pubs.html · Zbl 0929.68063 |
| [19] | Cramer, R., Shoup, V.: Signature schemes based on the strong rsa assumption. ACM Trans. Inf. Syst. Secur. 3(3), 161–185 (2000) · doi:10.1145/357830.357847 |
| [20] | Damgård, I.B.: Efficient concurrent zero-knowledge in the auxiliary string model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 418–430. Springer, Heidelberg (2000) · Zbl 1082.94539 · doi:10.1007/3-540-45539-6_30 |
| [21] | Damgård, I.B., Fujisaki, E.: A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125–142. Springer, Heidelberg (2002) · Zbl 1065.94545 · doi:10.1007/3-540-36178-2_8 |
| [22] | 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) · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12 |
| [23] | Fujisaki, E., Okamoto, T.: Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997) · Zbl 0880.94007 · doi:10.1007/BFb0052225 |
| [24] | Furukawa, J., Yonezawa, S.: Group Signatures with Separate and Distributed Authorities. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 77–90. Springer, Heidelberg (2005) · Zbl 1116.94321 · doi:10.1007/978-3-540-30598-9_6 |
| [25] | Gaud, M., Traoré, J.: On the Anonymity of Fair Offline E-cash Systems. In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 34–50. Springer, Heidelberg (2003) · doi:10.1007/978-3-540-45126-6_3 |
| [26] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 218–229. ACM Press, New York (1987) · doi:10.1145/28395.28420 |
| [27] | Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (1999) · Zbl 1030.94503 |
| [28] | Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012 |
| [29] | Kunz-Jacques, S., Martinet, G., Poupard, G., Stern, J.: Cryptanalysis of an Efficient Proof of Knowledge of Discrete Logarithm. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 27–43. Springer, Heidelberg (2006) · Zbl 1151.94529 · doi:10.1007/11745853_3 |
| [30] | Van Le, T., Nguyen, K.Q., Varadharajan, V.: How to Prove That a Committed Number Is Prime. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 208–218. Springer, Heidelberg (1999) · Zbl 0996.11076 · doi:10.1007/978-3-540-48000-6_17 |
| [31] | Lysyanskaya, A., Ramzan, Z.: Group Blind Digital Signatures: A Scalable Solution to Electronic Cash. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 184–197. Springer, Heidelberg (1998) · doi:10.1007/BFb0055483 |
| [32] | MacKenzie, P.D., Reiter, M.K.: Two-party generation of DSA signatures. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 137–154. Springer, Heidelberg (2001) · Zbl 1002.94527 · doi:10.1007/3-540-44647-8_8 |
| [33] | Mykletun, E., Narasimha, M., Tsudik, G.: Signature Bouquets: Immutability for Aggregated/Condensed Signatures. In: Samarati, P., Ryan, P.Y.A., Gollmann, D., Molva, R. (eds.) ESORICS 2004. LNCS, vol. 3193, pp. 160–176. Springer, Heidelberg (2004) · doi:10.1007/978-3-540-30108-0_10 |
| [34] | Nakanishi, T., Shiota, M., Sugiyama, Y.: An Efficient Online Electronic Cash with Unlinkable Exact Payments. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 367–378. Springer, Heidelberg (2004) · Zbl 1109.68479 · doi:10.1007/978-3-540-30144-8_31 |
| [35] | Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), 361–396 (2000) · Zbl 1025.94015 · doi:10.1007/s001450010003 |
| [36] | De Santis, A., Micali, S., Persiano, G.: Noninteractive Zero-Knowledge Proof Systems. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 52–72. Springer, Heidelberg (1988) · Zbl 0645.68100 · doi:10.1007/3-540-48184-2_5 |
| [37] | Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4(3), 161–174 (1991) · Zbl 0743.68058 · doi:10.1007/BF00196725 |
| [38] | Song, D.X.: Practical forward secure group signature schemes. In: Proc. 8th ACM Conference on Computer and Communications Security, pp. 225–234. ACM press, New York (2001) |
| [39] | Susilo, W., Mu, Y.: On the Security of Nominative Signatures. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 329–335. Springer, Heidelberg (2005) · Zbl 1127.94373 · doi:10.1007/11506157_28 |
| [40] | Tang, C., Liu, Z., Wang, M.: A verifiable secret sharing scheme with statistical zero-knowledge. Cryptology ePrint Archive, Report 2003/222 (2003), http://eprint.iacr.org/ |
| [41] | Tsang, P.P., Wei, V.K.: Short Linkable Ring Signatures for E-Voting, E-Cash and Attestation. In: Deng, R.H., Bao, F., Pang, H., Zhou, J. (eds.) ISPEC 2005. LNCS, vol. 3439, pp. 48–60. Springer, Heidelberg (2005) · Zbl 1118.68486 · doi:10.1007/978-3-540-31979-5_5 |
| [42] | 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) · Zbl 1113.94326 · doi:10.1007/978-3-540-30556-9_30 |
| [43] | Wei, V.K.: Tracing-by-linking group signatures. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 149–163. Springer, Heidelberg (2005) · doi:10.1007/11556992_11 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
