×

Concurrent signature without random oracles. (English) Zbl 1303.94112

Summary: A concurrent signature provides an efficient way to exchange digital signatures between parties in a fair manner. Since its introduction in Eurocrypt 2004, removing the random oracle heuristic in the security analysis of a concurrent signature scheme has become an open problem, and the security of all the existing provably secure schemes could have only been done in the random oracle model, while it has been known that the security in the random oracle model may not be guaranteed when the underlying random oracles are replaced by real-life hash functions. In this paper, we solve this open problem by proposing a new concurrent signature scheme, which allows us to prove its security without random oracles. The security model we consider in this paper also slightly differs from previous works. Signatures before revealing the keystone are strongly ambiguous (or anonymous) in the sense that everyone is able to produce signatures that are indistinguishable from those generated honestly by the parties involved in the exchange, while signatures after revealing the keystone remain unforgeable without sacrificing the fairness property. In the multi-user setting and without random oracles, we prove the security of our scheme based on the intractability of Computational Diffie-Hellman (CDH) problem and collision resistance of hash functions.

MSC:

94A62 Authentication, digital signatures and secret sharing

Software:

Keccak
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abe, M.; Ohkubo, M.; Suzuki, K., 1-Out-of-n signatures from a variety of keys, (ASIACRYPT 2002. ASIACRYPT 2002, LNCS, vol. 2501 (2002), Springer), 415-432 · Zbl 1065.94560
[2] Asokan, N.; Shoup, V.; Waidner, M., Optimistic fair exchange of signatures, (EUROCRYPT 1998. EUROCRYPT 1998, LNCS, vol. 1403 (1998), Springer), 591-606 · Zbl 0929.68064
[3] Bellare, M.; Goldreich, O., On defining proofs of knowledge, (CRYPTO 1992. CRYPTO 1992, LNCS, vol. 740 (1992), Springer), 390-420 · Zbl 0823.94016
[4] Bellare, M.; Rogaway, P., Random oracles are practical: a paradigm for designing efficient protocols, (CCS 1993 (1993), ACM Press), 62-73
[5] Bertoni, G.; Daemen, J.; Peeters, M.; Assche, G. V., Keccak, (EUROCRYPT 2013. EUROCRYPT 2013, LNCS, vol. 7881 (2013), Springer), 313-314 · Zbl 1306.94028
[6] Canetti, R.; Goldreich, O.; Halevi, S., The random oracle methodology, revisited, (STOC 1998 (1998), ACM Press), 209-218 · Zbl 1027.68603
[7] Chang, S.; Wong, D. S.; Mu, Y.; Zhang, Z., Certificateless threshold ring signature, Inform. Sci., 179, 20, 3685-3696 (2009) · Zbl 1170.94327
[8] Chen, L.; Kudla, C.; Paterson, K., Concurrent signatures, (EUROCRYPT 2004. EUROCRYPT 2004, LNCS, vol. 3027 (2004), Springer), 287-305 · Zbl 1122.94412
[9] Chow, S.; Susilo, W., Generic construction of identity-based perfect concurrent signatures, (ICICS 2005. ICICS 2005, LNCS, vol. 3783 (2005), Springer), 194-206 · Zbl 1122.94413
[10] Cramer, R.; Damgard, I.; Schoenmakers, B., Proofs of partial knowledge and simplified design of witness hiding protocols, (CRYPTO 1994. CRYPTO 1994, LNCS, vol. 839 (1994), Springer), 174-187 · Zbl 0939.94546
[11] Damgard, I., A design principle for hash functions, (CRYPTO 1989. CRYPTO 1989, LNCS, vol. 435 (1989), Springer), 416-427
[12] Damgard, I., On \(Σ\)-protocols (2010)
[13] Even, S.; Goldreich, O.; Lempel, A., A randomized protocol for signing contracts, Commun. ACM, 28, 6, 637-647 (1985) · Zbl 0538.94011
[14] Feige, U.; Shamir, A., Witness indistinguishable and witness hiding protocols, (STOC 1990 (1990), ACM Press), 416-426
[15] Garay, J.; Pomerance, C., Timed fair exchange of standard signatures: [extended abstract], (FC 2003. FC 2003, LNCS, vol. 2742 (2003), Springer), 190-207 · Zbl 1274.94068
[16] Huang, Q.; Wong, D. S.; Susilo, W., Group-oriented fair exchange of signatures, Inform. Sci., 181, 16, 3267-3283 (2011) · Zbl 1242.94037
[17] Huang, Q.; Wong, D. S.; Susilo, W., The construction of ambiguous optimistic fair exchange from designated confirmer signature without random oracles, Inform. Sci., 228, 222-238 (2013) · Zbl 1293.94102
[18] Huang, Q.; Yang, G.; Wong, D. S.; Susilo, W., Ambiguous optimistic fair exchange, (ASIACRYPT 2008. ASIACRYPT 2008, LNCS, vol. 5350 (2008), Springer), 74-89 · Zbl 1206.94075
[19] Hwang, J. Y.; Lee, S.; Chung, B.; Cho, H. S.; Nyang, D., Group signatures with controllable linkability for dynamic membership, Inform. Sci., 222, 761-778 (2013) · Zbl 1293.94103
[20] Laguillaumie, F.; Vergnaud, D., Time-selective convertible undeniable signatures with short conversion receipts, Inform. Sci., 180, 12, 2458-2475 (2010) · Zbl 1191.94105
[21] Li, J.; Kim, K., Hidden attribute-based signatures without anonymity revocation, Inform. Sci., 180, 9, 1681-1689 (2010) · Zbl 1191.94106
[22] Li, Y.; He, D.; Lu, X., Accountability of perfect concurrent signature (2008), Cryptology ePrint archive: report 2008/301
[23] Merkle, R., One way hash functions and DES, (CRYPTO 1989. CRYPTO 1989, LNCS, vol. 435 (1989), Springer), 428-446
[24] Nguyen, K., Asymmetric concurrent signatures, (ICICS 2005. ICICS 2005, LNCS, vol. 3783 (2005), Springer), 181-193 · Zbl 1122.94437
[25] Pointcheval, D.; Stern, J., Security arguments for digital signatures and blind signatures, J. Cryptology, 13, 3, 361-396 (2000) · Zbl 1025.94015
[26] Schnorr, C. P., Efficient signature generation for smart cards, J. Cryptology, 4, 3, 239-252 (1991) · Zbl 0743.68058
[27] Stevens, M.; Lenstra, A.; Weger, B., Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities, (EUROCRYPT 2007. EUROCRYPT 2007, LNCS, vol. 4586 (2007), Springer), 338-354 · Zbl 1141.94374
[28] Stevens, M.; Sotirov, A.; Appelbaum, J.; Lenstra, A.; Molnar, D.; Osvik, D. A.; Weger, B., Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, (CRYPTO 2009. CRYPTO 2009, LNCS, vol. 5677 (2009), Springer), 55-69 · Zbl 1252.94098
[29] Susilo, W.; Au, M. H.; Wang, Y.; Wong, D. S., Fairness in concurrent signatures revisited, (ACISP 2013. ACISP 2013, LNCS, vol. 7959 (2013), Springer), 318-329 · Zbl 1316.94104
[30] Susilo, W.; Mu, Y.; Zhang, F., Perfect concurrent signatures schemes, (ICICS 2004. ICICS 2004, LNCS, vol. 3269 (2004), Springer), 14-26 · Zbl 1109.68487
[31] Tan, X.; Huang, Q.; Wong, D. S., Extending concurrent signature to multiple parties, Theoret. Comput. Sci., 548, 54-67 (2014) · Zbl 1360.94334
[32] Tonien, D.; Susilo, W.; Safavi-Naini, R., Multi-party concurrent signatures, (ISC 2006. ISC 2006, LNCS, vol. 4176 (2006), Springer), 131-145 · Zbl 1156.94423
[33] Wang, G.; Bao, F.; Zhou, J., The fairness of perfect concurrent signatures, (ICICS 2006. ICICS 2006, LNCS, vol. 4307 (2006), Springer), 435-451
[34] Wang, X. Y.; Yin, Y. Q.; Yu, H. B., Finding collisions in the full SHA-1, (CRYPTO 2005. CRYPTO 2005, LNCS, vol. 3621 (2005), Springer), 17-36 · Zbl 1145.94454
[35] Wang, X. Y.; Yu, H. B., How to break MD5 and other hash functions, (EUROCRYPT 2005. EUROCRYPT 2005, LNCS, vol. 3494 (2005), Springer), 19-35 · Zbl 1137.94359
[36] Waters, B., Efficient identity-based encryption without random oracles, (EUROCRYPT 2005. EUROCRYPT 2005, LNCS, vol. 3494 (2005), Springer), 114-127 · Zbl 1137.94360
[37] Yu, J.; Hao, R.; Kong, F.; Cheng, X.; Fan, J.; Chen, Y., Forward-secure identity-based signature: security notions and construction, Inform. Sci., 181, 3, 648-660 (2011) · Zbl 1204.94094
[38] Yuan, H.; Zhang, F.; Huang, X.; Mu, Y.; Susilo, W.; Zhang, L., Certificateless threshold signature scheme from bilinear maps, Inform. Sci., 180, 23, 4714-4728 (2010) · Zbl 1208.94062
[39] Yuen, T. H.; Wong, D. S.; Susilo, W.; Huang, Q., Concurrent signatures with fully negotiable binding control, (ProvSec 2011. ProvSec 2011, LNCS, vol. 6980 (2011), Springer), 170-187 · Zbl 1298.94126
[40] Zhao, W.; Ye, D., Certificateless undeniable signatures from bilinear maps, Inform. Sci., 199, 204-215 (2012) · Zbl 1248.94100
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.