nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Black-Box Separations of Hash-and-Sign Signatures in the Non-Programmable Random Oracle Model

verfasst von : Zongyang Zhang, Yu Chen, Sherman S. M. Chow, Goichiro Hanaoka, Zhenfu Cao, Yunlei Zhao

Erschienen in: Provable Security

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

A popular methodology of designing cryptosystems with practical efficiency is to give a security proof in the random oracle (RO) model. The work of Fischlin and Fleischhacker (Eurocrypt ’13) investigated the case of Schnorr signature (and generally, Fiat-Shamir signatures) and showed the reliance of RO model is inherent.

We generalize their results to a large class of “malleable” hash-and-sign signatures, where one can efficiently “maul”any two valid signatures between two signature instances with different public keys if it can get the difference between the secret keys. We follow the technique of Fischlin and Fleischhacker to show that the security of malleable hash-and-sign signature cannot be reduced to its related hard cryptographic problem without programming the RO. Our proof assumes the hardness of a one-more cryptographic problem (depending on the signature instantiation). Our result applies to single-instance black-box reductions, subsuming those reductions used in existing proofs.

Our framework not only encompasses Fiat-Shamir signatures as special cases, but also covers \(\Gamma \)-signature (Yao and Zhao, IEEE Transactions on Information Forensics and Security ’13), and other schemes which implicitly used malleable hash-and-sign signatures, including Boneh-Franklin identity-based encryption, and Sakai-Ohgishi-Kasahara non-interactive identity-based key exchange.

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 Tighter Security for Efficient Lattice Cryptography via the Rényi Divergence of Optimized Orders

Nächstes Kapitel Rethinking Privacy for Extended Sanitizable Signatures and a Black-Box Construction of Strongly Private Schemes

In the generic group model [31], the underlying group is considered as a generic one, where an adversary only has access to random encodings of group elements, and the operation on group elements is done in a black-box way. The problem \((\mathrm {P}_1,\mathrm {P}_2)\) requires the existence of a \(\mathrm {P}_2\) solution oracle, which in essence contradicts the idea of the generic group since one can know the relation between two random encodings. Though it is possible to model this \(\mathrm {P}_2\) oracle in the generic group model, it is hard to argue that the encodings do not leak too much useful information to an adversary.

We remark that a previous version of this work actually predates [10].

We use an inner algorithm \(\mathsf {SInner}\) to clarify that the input of \(\mathsf {H}\) does not include the public key. For brevity, we allow \(\mathsf {H}\) to use whole r. In explicit constructions, \(\mathsf {H}\) might only use part of the randomness r. In this case, \(\mathsf {H}\) just neglects the rest part of r.

This implies that each public key is corresponding to only one secret key.

Recall that \(\mathsf{SS}\) is malleable, according to Definition 8, the homomorphism \(\psi (\cdot )\) is computable with a \(\mathrm {P}_2\) solving oracle. Moreover, a problem \(\mathrm {P}_1\) instance can also be correctly solved by using at most one query to a \(\mathrm {P}_2\) solving oracle (with the help of reduction \(\mathcal {T}\)).

Ananth, P., Bhaskar, R.: Non observability in the random oracle model. In: Susilo, W., Reyhanitabar, R. (eds.) ProvSec 2013. LNCS, vol. 8209, pp. 86–103. Springer, Heidelberg (2013) CrossRef

Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. J. Cryptol. 16(3), 185–215 (2003)MathSciNetCrossRefMATH

Bellare, M., Paterson, K.G., Thomson, S.: RKA security beyond the linear barrier: IBE, encryption and signatures. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 331–348. Springer, Heidelberg (2012) CrossRef

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) ACM CCS, pp. 62–73. ACM (1993)

Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995) CrossRef

Bhattacharyya, R., Mukherjee, P.: Non-adaptive programmability of random oracle. Theoret. Comput. Sci. 592, 97–114 (2015)MathSciNetCrossRef

Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004) CrossRef

Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001) CrossRef

Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)MathSciNetCrossRefMATH

10.

Chen, Y., Huang, Q., Zhang, Z.: Sakai-ohgishi-kasahara identity-based non-interactive key exchange scheme, revisited. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 274–289. Springer, Heidelberg (2014)

11.

Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013) CrossRef

12.

Cui, Y., Fujisaki, E., Hanaoka, G., Imai, H., Zhang, R.: Formal security treatments for IBE-to-signature transformation: relations among security notions. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 92(1), 53–66 (2009)CrossRef

13.

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) CrossRef

14.

Fischlin, M., Fleischhacker, N.: Limitations of the meta-reduction technique: the case of schnorr signatures. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 444–460. Springer, Heidelberg (2013) CrossRef

15.

Fischlin, M., Lehmann, A., Ristenpart, T., Shrimpton, T., Stam, M., Tessaro, S.: Random oracles with(out) programmability. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 303–320. Springer, Heidelberg (2010) CrossRef

16.

Fleischhacker, N., Jager, T., Schröder, D.: On tight security proofs for schnorr signatures. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 512–531. Springer, Heidelberg (2014)

17.

Freire, E.S.V., Hofheinz, D., Paterson, K.G., Striecks, C.: Programmable hash functions in the multilinear setting. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 513–530. Springer, Heidelberg (2013) CrossRef

18.

Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999) CrossRef

19.

Fukumitsu, M., Hasegawa, S.: Black-box separations on fiat-shamir-type signatures in the non-programmable random oracle model. In: López, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 3–20. Springer, Heidelberg (2015) CrossRef

20.

Galindo, D.: Boneh-franklin identity based encryption revisited. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 791–802. Springer, Heidelberg (2005) CrossRef

21.

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013) CrossRef

22.

Goh, E.J., Jarecki, S., Katz, J., Wang, N.: Efficient signature schemes with tight reductions to the Diffie-Hellman problems. J. Cryptol. 20(4), 493–514 (2007)MathSciNetCrossRefMATH

23.

Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS, pp. 102–113. IEEE Computer Society (2003)

24.

Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111–126. Springer, Heidelberg (2002) CrossRef

25.

Nishioka, M.: Reconsideration on the security of the boneh-franklin identity-based encryption scheme. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 270–282. Springer, Heidelberg (2005) CrossRef

26.

Paterson, K.G., Srinivasan, S.: On the relations between non-interactive key distribution, identity-based encryption and trapdoor discrete log groups. Des. Codes Crypt. 52(2), 219–241 (2009)MathSciNetCrossRefMATH

27.

Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000)CrossRefMATH

28.

Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: The 2000 Symposium on Cryptography and Information Security, vol. 45, pp. 26–28, Japan (2000)

29.

Schnorr, C.-P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)

30.

Seurin, Y.: On the exact security of schnorr-type signatures in the random oracle model. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 554–571. Springer, Heidelberg (2012) CrossRef

31.

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997) CrossRef

32.

Shoup, V.: A proposal for an ISO standard for public key encryption. In: Cryptology ePrint Archive, Report 2001/112 (2001). http://eprint.iacr.org/

33.

Wee, H.: Zero knowledge in the random oracle model, revisited. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 417–434. Springer, Heidelberg (2009) CrossRef

34.

Yao, A.C.C., Zhao, Y.: Online/offline signatures for low-power devices. IEEE Trans. Inf. Forensics Secur. 8(2), 283–294 (2013)CrossRef

35.

Zhang, J., Zhang, Z., Chen, Y., Guo, Y., Zhang, Z.: Black-box separations for one-more (Static) CDH and its generalization. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 366–385. Springer, Heidelberg (2014)

36.

Zhang, R., Imai, H.: Improvements on security proofs of some identity based encryption schemes. In: Feng, D., Lin, D., Yung, M. (eds.) CISC 2005. LNCS, vol. 3822, pp. 28–41. Springer, Heidelberg (2005) CrossRef

Titel: Black-Box Separations of Hash-and-Sign Signatures in the Non-Programmable Random Oracle Model
verfasst von: Zongyang Zhang
Yu Chen
Sherman S. M. Chow
Goichiro Hanaoka
Zhenfu Cao
Yunlei Zhao
Verlag: Springer International Publishing
Buch: Provable Security
Print ISBN: 978-3-319-26058-7

Electronic ISBN: 978-3-319-26059-4

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-26059-4_24

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"