nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Improving Signature Schemes with Tight Security Reductions

verfasst von : Tiong-Sik Ng, Syh-Yuan Tan, Ji-Jian Chin

Erschienen in: Information Security Practice and Experience

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In 2003, Katz and Wang proposed the claw-free trapdoor full domain hash (CFT-FDH) which achieves a tight security for FDH signature schemes using the bit selector technique. However, it is noted that the CFT-FDH is not backward compatible with its original FDH counterpart, since the selected bit is hashed with the message, modifying the structure of the original signature. In this paper, we take a step further to propose a general framework that is able to achieve backward compatibility while maintaining the tight reduction of FDH signatures using the properties of trapdoor samplable relations and also Katz-Wang’s bit selector technique.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel White-Box Implementation of the KMAC Message Authentication Code

Nächstes Kapitel Improved Digital Signatures Based on Elliptic Curve Endomorphism Rings

It is worth mentioning that the co-CDH problem is a Type-3 Pairing counterpart to the CDH problem which is based on the Type-1 Pairing [11].

We denote this hard problem as the co-DBDH problem as the Type-3 Pairing version of the DBDH problem, to distinguish between the DBDH problem which is based on the Type-1 Pairing. It is noted that in a work by Vercauteren [41], the co-DBDH problem itself is denoted as the DBDH problem, which covers the specification of both Type-1 and Type-3 pairings.

The signer may enclose the bit r alongside \(\sigma \) to avoid confusion during verification where two different signatures for a message (i.e. \(r \in \{0,1\}\)) may exist at once, as stated in [31].

Different from Katz-Wang’s work in [31], \(\mathcal {A}\) is not able to query for the value of r considering it is not a portion of the hash input.

Abdalla, M., An, J.H., Bellare, M., Namprempre, C.: From identification to signatures via the fiat-shamir transform: minimizing assumptions for security and forward-security. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 418–433. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_28CrossRef

Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28CrossRefMATH

An, J.H., Dodis, Y., Rabin, T.: On the security of joint signature and encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83–107. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_6CrossRef

Bao, F., Deng, R.H., Zhu, H.F.: Variations of Diffie-Hellman problem. In: Qing, S., Gollmann, D., Zhou, J. (eds.) ICICS 2003. LNCS, vol. 2836, pp. 301–312. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39927-8_28CrossRef

Bresson, E., Lakhnech, Y., Mazaré, L., Warinschi, B.: A generalization of DDH with applications to protocol analysis and computational soundness. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 482–499. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_27CrossRef

Beth, T.: Efficient zero-knowledge identification scheme for smart cards. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 77–84. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-45961-8_7CrossRef

Boneh, D., Franklin, M.B.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_13CrossRef

Bellare, M., Fischlin, M., Goldwasser, S., Micali, S.: Identification protocols secure against reset attacks. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 495–511. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_30CrossRef

Boyen, X., Li, Q.: Towards Tightly Secure Short Signature and IBE. IACR Cryptology ePrint Archive – Report 2016/498, pp. 514–532 (2001)

10.

Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_30CrossRef

11.

Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 411–422. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_37CrossRef

12.

Bellare, M., Namprempre, C., Neven, G.: Security proofs for identity-based identification and signature schemes. J. Cryptol. 22(1), 1–61 (2009)MathSciNetCrossRef

13.

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security – ACM CCS 1993, pp. 62–73. ACM (1993)

14.

Bellare, M., Rogaway, P.: The exact security of digital signatures-how to sign with RSA and rabin. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_34CrossRef

15.

Choon, J.C., Hee Cheon, J.: An identity-based signature from gap Diffie-Hellman groups. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 18–30. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_2CrossRef

16.

Chaum, D.: Zero-knowledge undeniable signatures (extended abstract). In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 458–464. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46877-3_41CrossRef

17.

Coron, J.-S.: On the exact security of full domain hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_14CrossRef

18.

Coron, J.-S.: Optimal security proofs for PSS and other signature schemes. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 272–287. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_18CrossRef

19.

Coron, J.S.: A variant of Boneh-Franklin IBE with a tight reduction in the random oracle model. Des. Codes Crypt. 50(1), 115–133 (2009)MathSciNetCrossRef

20.

Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur. (TISSEC) 3(3), 161–185 (2000)CrossRef

21.

Kerry, C.F., Director, C.R.: FIPS PUB 186–4 federal information processing standards publication digital signature standard (DSS). FIPS Publication (2013)

22.

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_2CrossRef

23.

Guo, F., Chen, R., Susilo, W., Lai, J., Yang, G., Mu, Y.: Optimal security reductions for unique signatures: bypassing impossibilities with a counterexample. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 517–547. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_18CrossRef

24.

Goh, E.-J., Jarecki, S.: A signature scheme as secure as the Diffie-Hellman problem. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 401–415. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_25CrossRef

25.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRef

26.

Guillou, L.C., Quisquater, J.-J.: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123–128. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-45961-8_11CrossRef

27.

Huang, J., Huang, Q., Pan, C.: A black-box construction of strongly unforgeable signature schemes in the bounded leakage model. In: Chen, L., Han, J. (eds.) ProvSec 2016. LNCS, vol. 10005, pp. 320–339. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47422-9_19CrossRef

28.

Katz, J.: Full-domain hash (and related) signature schemes. In: Katz, J. (ed.) Digital Signatures, pp. 143–153. Springer, Boston (2010). https://doi.org/10.1007/978-0-387-27712-7_7CrossRefMATH

29.

Koblitz, N., Menezes, A.J.: The random oracle model: a twenty-year retrospective. Des. Codes Crypt. 77(2–3), 587–610 (2015)MathSciNetCrossRef

30.

Kiltz, E., Masny, D., Pan, J.: Optimal security proofs for signatures from identification schemes. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 33–61. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_2CrossRef

31.

Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: ACM CCS 2003, pp. 155–164 (2003)

32.

Lacharité, M.S.: Security of BLS and BGLS signatures in a multi-user setting. In: Advances in Cryptology 2016, vol. 2 – ARCTICCRYPT 2016, pp. 244–261 (2016)

33.

Lynn, B.: On the implementation of pairing-based cryptosystems. Doctoral dissertation, Stanford University (2007)

34.

Katz, J., Menezes, A., Van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)MATH

35.

Morita, H., Schuldt, J.C.N., Matsuda, T., Hanaoka, G., Iwata, T.: On the security of the schnorr signature scheme and DSA against related-key attacks. In: Kwon, S., Yun, A. (eds.) ICISC 2015. LNCS, vol. 9558, pp. 20–35. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30840-1_2CrossRefMATH

36.

Barker, E., Barker, W., Burr, W., Polk, W., Smid, M.: Recommendation for key management-part 1: general (revised). NIST Special Publication (2006)

37.

Ng, T.-S., Tan, S.-Y., Chin, J.-J.: A variant of BLS signature scheme with tight security reduction. In: Hu, J., Khalil, I., Tari, Z., Wen, S. (eds.) MONAMI 2017. LNICST, vol. 235, pp. 150–163. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-90775-8_13CrossRef

38.

Ogata, W., Kurosawa, K., Heng, S.-H.: The security of the FDH variant of chaum’s undeniable signature scheme. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 328–345. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30580-4_23CrossRef

39.

Pereira, G.C., Simplício, M.A., Naehrig, M., Barreto, P.S.: A family of implementation-friendly BN elliptic curves. J. Syst. Softw. 84(8), 1319–1326 (2011)CrossRef

40.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRef

41.

Vercauteren, F.: Final report on main computational assumptions in cryptography. European Network of Excellence in Cryptography II (2013)

Titel: Improving Signature Schemes with Tight Security Reductions
verfasst von: Tiong-Sik Ng
Syh-Yuan Tan
Ji-Jian Chin
Verlag: Springer International Publishing
Buch: Information Security Practice and Experience
Print ISBN: 978-3-030-34338-5

Electronic ISBN: 978-3-030-34339-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-34339-2_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"