×

One-time signatures and chameleon hash functions. (English) Zbl 1293.94090

Biryukov, Alex (ed.) et al., Selected areas in cryptography. 17th international workshop, SAC 2010, Waterloo, Ontario, Canada, August 12–13, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-19573-0/pbk). Lecture Notes in Computer Science 6544, 302-319 (2011).
Summary: In this work we show a general construction for transforming any chameleon hash function to a strongly unforgeable one-time signature scheme. Combined with the result of M. Bellare and T. Ristov [Advances in cryptology – ASIACRYPT 2008, Lect. Notes Comput. Sci. 5350, 125–142 (2008; Zbl 1206.94053)], this also implies a general construction of strongly unforgeable one-time signatures from \(\Sigma\)-protocols in the standard model.
Our results explain and unify several works in the literature which either use chameleon hash functions or one-time signatures, by showing that several of the constructions in the former category can be interpreted as efficient instantiations of those in the latter. They also imply that any “noticeable” improvement to the efficiency of constructions for chameleon hash functions leads to similar improvements for one-time signatures. This makes such improvements challenging since efficiency of one-time signatures has been studied extensively.
We further demonstrate the usefulness of our general construction by studying and optimizing specific instantiations based on the hardness of factoring, the discrete-log problem, and the worst-case lattice-based assumptions. Some of these signature schemes match or improve the efficiency of the best previous constructions or relax the underlying hardness assumptions. Two of the schemes have very fast signing (no exponentiations) which makes them attractive in scenarios where the signer has limited computational resources.
For the entire collection see [Zbl 1208.94008].

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Citations:

Zbl 1206.94053
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abe, M., Cui, Y., Imai, H., Kiltz, E.: Efficient hybrid encryption from ID-based encryption. Designs, Codes and Cryptography 54(3), 205–240 (2010) · Zbl 1197.94171 · doi:10.1007/s10623-009-9320-0
[2] Ateniese, G., de Medeiros, B.: Identity-based chameleon hash and applications. In: Juels, A. (ed.) FC 2004. LNCS, vol. 3110, pp. 164–180. Springer, Heidelberg (2004) · Zbl 1105.94302 · doi:10.1007/978-3-540-27809-2_19
[3] Bellare, M., Ristov, T.: Hash functions from sigma protocols and improvements to VSH. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 125–142. Springer, Heidelberg (2008) · Zbl 1206.94053 · doi:10.1007/978-3-540-89255-7_9
[4] Bellare, M., Rogaway, P.: Collision-resistant hashing: Towards making UOWHFs practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 470–484. Springer, Heidelberg (1997) · Zbl 0882.94015 · doi:10.1007/BFb0052256
[5] Bellare, M., Shoup, S.: Two-tier signatures, strongly unforgeable signatures, and fiat-shamir without random oracles. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 201–216. Springer, Heidelberg (2007) · Zbl 1127.94019 · doi:10.1007/978-3-540-71677-8_14
[6] Bleichenbacher, D., Maurer, U.M.: On the efficiency of one-time digital signatures. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 145–158. Springer, Heidelberg (1996) · Zbl 1007.94546 · doi:10.1007/BFb0034843
[7] Bleumer, G., Pfitzmann, B., Waidner, M.: A Remark on Signature Scheme Where Forgery Can Be Proved. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 441–445. Springer, Heidelberg (1991) · Zbl 0825.94177 · doi:10.1007/3-540-46877-3_39
[8] Boneh, D., Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. SIAM Journal on Computing 36(5), 915–942 (2006) · Zbl 1138.94010
[9] Boneh, D., Katz, J.: Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 87–103. Springer, Heidelberg (2005) · Zbl 1079.94535 · doi:10.1007/978-3-540-30574-3_8
[10] Boneh, D., Shen, E., Waters, B.: Strongly unforgeable signatures based on computational diffie-hellman. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 229–240. Springer, Heidelberg (2006) · Zbl 1151.94485 · doi:10.1007/11745853_15
[11] Boyen, X.: Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 499–517. Springer, Heidelberg (2010) · Zbl 1281.94074 · doi:10.1007/978-3-642-13013-7_29
[12] Brakerski, Z., Kalai, Y.T.: A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model, http://eprint.iacr.org/2010/086.pdf
[13] Brassard, G., Chaum, D., Crépeau, C.C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences 37(2), 156–189 (1988) · Zbl 0656.68109 · doi:10.1016/0022-0000(88)90005-0
[14] Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004) · Zbl 1122.94358 · doi:10.1007/978-3-540-24676-3_13
[15] Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai Trees, or How to Delegate a Lattice Basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010) · Zbl 1280.94043 · doi:10.1007/978-3-642-13190-5_27
[16] Dahmen, E., Krauß, C.: Short hash-based signatures for wireless sensor networks. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 463–476. Springer, Heidelberg (2009) · Zbl 1287.94109 · doi:10.1007/978-3-642-10433-6_31
[17] Dodis, Y., Katz, J.: Chosen-ciphertext security of multiple encryption. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 188–209. Springer, Heidelberg (2005) · Zbl 1079.94545 · doi:10.1007/978-3-540-30576-7_11
[18] Even, S., Goldreich, O., Micali, S.: Online/offline signatures. Journal of Cryptology (1996) · Zbl 0844.94011
[19] 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
[20] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM Press, New York (May 2008) · Zbl 1231.68124
[21] Goldreich, O.: Two remarks concerning the goldwasser-micali-rivest signature scheme. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 104–110. Springer, Heidelberg (1987) · Zbl 0635.94010 · doi:10.1007/3-540-47721-7_8
[22] Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17(2), 281–308 (1988) · Zbl 0644.94012 · doi:10.1137/0217017
[23] Groth, J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006) · Zbl 1172.94615 · doi:10.1007/11935230_29
[24] Guillou, L.C., Quisquater, J.-J.: A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123–128. Springer, Heidelberg (1988) · doi:10.1007/3-540-45961-8_11
[25] Hohenberger, S., Waters, B.: Short and stateless signatures from the RSA assumption. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 654–670. Springer, Heidelberg (2009) · Zbl 1252.94074 · doi:10.1007/978-3-642-03356-8_38
[26] Huang, Q., Wong, D.S., Zhao, Y.: Generic transformation to strongly unforgeable signatures. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 1–17. Springer, Heidelberg (2007) · Zbl 1214.94066 · doi:10.1007/978-3-540-72738-5_1
[27] Krawczyk, H., Rabin, T.: Chameleon signatures. In: ISOC Network and Distributed System Security Symposium – NDSS 2000. The Internet Society, San Diego (February 2000)
[28] Lamport, L.: Constructing digital signatures from a one-way function. Technical Report SRI-CSL-98, SRI International Computer Science Laboratory (October 1979)
[29] Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 37–54. Springer, Heidelberg (2008) · Zbl 1162.94389 · doi:10.1007/978-3-540-78524-8_3
[30] Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990) · doi:10.1007/0-387-34805-0_21
[31] Micali, S., Shamir, A.: An improvement of the fiat-shamir identification and signature scheme. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 244–247. Springer, Heidelberg (1990) · doi:10.1007/0-387-34799-2_18
[32] Okamoto, T.: Provably secure and practical identification schemes and corresponding signature schemes. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 31–53. Springer, Heidelberg (1993) · Zbl 0809.94008 · doi:10.1007/3-540-48071-4_3
[33] Pedersen, T.P., Pfitzmann, B.: Fail-stop signatures. SIAM Journal on Computing 26, 291–330 (1997) · Zbl 0868.94022 · doi:10.1137/S009753979324557X
[34] Peikert, C.: Bonsai trees (or, arboriculture in lattice-based cryptography). Cryptology ePrint Archive, Report 2009/359 (2009), http://eprint.iacr.org/
[35] Perrig, A.: The BiBa one-time signature and broadcast authentication protocol. In: ACM CCS 2001: 8th Conference on Computer and Communications Security, pp. 28–37. ACM Press, New York (November 2001)
[36] Safavi-Naini, R., Susilo, W.: Threshold fail-stop signature schemes based on discrete logarithm and factorization. In: Pieprzyk, J., Okamoto, E., Seberry, J. (eds.) ISW 2000. LNCS, vol. 1975, pp. 292–307. Springer, Heidelberg (2000) · Zbl 1044.68615 · doi:10.1007/3-540-44456-4_22
[37] Schmidt-Samoa, K.: Factorization-based fail-stop signatures revisited. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 118–131. Springer, Heidelberg (2004) · Zbl 1109.68485 · doi:10.1007/978-3-540-30191-2_10
[38] Schnorr, C.-P.: Efficient signature generation by smart cards. Journal of Cryptology 4(3), 161–174 (1991) · Zbl 0743.68058 · doi:10.1007/BF00196725
[39] Shamir, A., Tauman, Y.: Improved online/Offline signature schemes. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 355–367. Springer, Heidelberg (2001) · Zbl 1003.94533 · doi:10.1007/3-540-44647-8_21
[40] Steinfeld, R., Pieprzyk, J., Wang, H.: How to strengthen any weakly unforgeable signature into a strongly unforgeable signature. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 357–371. Springer, Heidelberg (2006) · Zbl 1177.94191 · doi:10.1007/11967668_23
[41] Susilo, W., Safavi-Naini, R.: An efficient fail-stop signature scheme based on factorization. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 62–74. Springer, Heidelberg (2003) · Zbl 1031.94540 · doi:10.1007/3-540-36552-4_5
[42] van Heyst, E., Pedersen, T.P.: How to make efficient fail-stop signatures. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 366–377. Springer, Heidelberg (1993) · Zbl 0797.68051 · doi:10.1007/3-540-47555-9_30
[43] Zaverucha, G.M., Stinson, D.R.: Short one-time signatures. Cryptology ePrint Archive, Report 2010/446 (2010), http://eprint.iacr.org/
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.