{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T23:14:39Z","timestamp":1763507679960,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319260587"},{"type":"electronic","value":"9783319260594"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-26059-4_24","type":"book-chapter","created":{"date-parts":[[2015,11,27]],"date-time":"2015-11-27T16:59:56Z","timestamp":1448643596000},"page":"435-454","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Black-Box Separations of Hash-and-Sign Signatures in the Non-Programmable Random Oracle Model"],"prefix":"10.1007","author":[{"given":"Zongyang","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sherman S. M.","family":"Chow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Goichiro","family":"Hanaoka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenfu","family":"Cao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunlei","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,28]]},"reference":[{"key":"24_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-642-41227-1_5","volume-title":"Provable Security","author":"P Ananth","year":"2013","unstructured":"Ananth, P., Bhaskar, R.: Non observability in the random oracle model. In: Susilo, W., Reyhanitabar, R. (eds.) ProvSec 2013. LNCS, vol. 8209, pp. 86\u2013103. Springer, Heidelberg (2013)"},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s00145-002-0120-1","volume":"16","author":"M Bellare","year":"2003","unstructured":"Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSA-inversion problems and the security of Chaum\u2019s blind signature scheme. J. Cryptol. 16(3), 185\u2013215 (2003)","journal-title":"J. Cryptol."},{"key":"24_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-34961-4_21","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"M Bellare","year":"2012","unstructured":"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\u2013348. Springer, Heidelberg (2012)"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"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\u201373. ACM (1993)","DOI":"10.1145\/168588.168596"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/BFb0053428","volume-title":"Advances in Cryptology - EUROCRYPT \u201994","author":"M Bellare","year":"1995","unstructured":"Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92\u2013111. Springer, Heidelberg (1995)"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2015.05.026","volume":"592","author":"R Bhattacharyya","year":"2015","unstructured":"Bhattacharyya, R., Mukherjee, P.: Non-adaptive programmability of random oracle. Theoret. Comput. Sci. 592, 97\u2013114 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-28628-8_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"D Boneh","year":"2004","unstructured":"Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41\u201355. Springer, Heidelberg (2004)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-44647-8_13","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"D Boneh","year":"2001","unstructured":"Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213\u2013229. Springer, Heidelberg (2001)"},{"issue":"3","key":"24_CR9","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/S0097539701398521","volume":"32","author":"D Boneh","year":"2003","unstructured":"Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586\u2013615 (2003)","journal-title":"SIAM J. Comput."},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/978-3-319-08344-5_18","volume-title":"Information Security and Privacy","author":"Y Chen","year":"2014","unstructured":"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\u2013289. Springer, Heidelberg (2014)"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/978-3-642-40041-4_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"J-S Coron","year":"2013","unstructured":"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\u2013493. Springer, Heidelberg (2013)"},{"issue":"1","key":"24_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1587\/transfun.E92.A.53","volume":"92","author":"Y Cui","year":"2009","unstructured":"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\u201366 (2009)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"A Fiat","year":"1987","unstructured":"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\u2013194. Springer, Heidelberg (1987)"},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-642-38348-9_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"M Fischlin","year":"2013","unstructured":"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\u2013460. Springer, Heidelberg (2013)"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-642-17373-8_18","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"M Fischlin","year":"2010","unstructured":"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\u2013320. Springer, Heidelberg (2010)"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1007\/978-3-662-45611-8_27","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"N Fleischhacker","year":"2014","unstructured":"Fleischhacker, N., Jager, T., Schr\u00f6der, D.: On tight security proofs for schnorr signatures. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 512\u2013531. Springer, Heidelberg (2014)"},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-642-40041-4_28","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"ESV Freire","year":"2013","unstructured":"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\u2013530. Springer, Heidelberg (2013)"},{"key":"24_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/3-540-48405-1_34","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"E Fujisaki","year":"1999","unstructured":"Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537\u2013554. Springer, Heidelberg (1999)"},{"key":"24_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-23318-5_1","volume-title":"Information Security","author":"M Fukumitsu","year":"2015","unstructured":"Fukumitsu, M., Hasegawa, S.: Black-box separations on fiat-shamir-type signatures in the non-programmable random oracle model. In: L\u00f3pez, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 3\u201320. Springer, Heidelberg (2015)"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/11523468_64","volume-title":"Automata, Languages and Programming","author":"D Galindo","year":"2005","unstructured":"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\u2013802. Springer, Heidelberg (2005)"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-38348-9_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"S Garg","year":"2013","unstructured":"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\u201317. Springer, Heidelberg (2013)"},{"issue":"4","key":"24_CR22","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00145-007-0549-3","volume":"20","author":"EJ Goh","year":"2007","unstructured":"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\u2013514 (2007)","journal-title":"J. Cryptol."},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS, pp. 102\u2013113. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"24_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-45708-9_8","volume-title":"Advances in Cryptology - CRYPTO 2002","author":"JB Nielsen","year":"2002","unstructured":"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\u2013126. Springer, Heidelberg (2002)"},{"key":"24_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/11596219_22","volume-title":"Progress in Cryptology - INDOCRYPT 2005","author":"M Nishioka","year":"2005","unstructured":"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\u2013282. Springer, Heidelberg (2005)"},{"issue":"2","key":"24_CR26","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10623-009-9278-y","volume":"52","author":"KG Paterson","year":"2009","unstructured":"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\u2013241 (2009)","journal-title":"Des. Codes Crypt."},{"issue":"3","key":"24_CR27","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s001450010003","volume":"13","author":"D Pointcheval","year":"2000","unstructured":"Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361\u2013396 (2000)","journal-title":"J. Cryptol."},{"key":"24_CR28","unstructured":"Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: The 2000 Symposium on Cryptography and Information Security, vol. 45, pp. 26\u201328, Japan (2000)"},{"key":"24_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/0-387-34805-0_22","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"C-P Schnorr","year":"1990","unstructured":"Schnorr, C.-P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239\u2013252. Springer, Heidelberg (1990)"},{"key":"24_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-642-29011-4_33","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"Y Seurin","year":"2012","unstructured":"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\u2013571. Springer, Heidelberg (2012)"},{"key":"24_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","volume-title":"Advances in Cryptology - EUROCRYPT \u201997","author":"V Shoup","year":"1997","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256\u2013266. Springer, Heidelberg (1997)"},{"key":"24_CR32","unstructured":"Shoup, V.: A proposal for an ISO standard for public key encryption. In: Cryptology ePrint Archive, Report 2001\/112 (2001). http:\/\/eprint.iacr.org\/"},{"key":"24_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-642-10366-7_25","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"H Wee","year":"2009","unstructured":"Wee, H.: Zero knowledge in the random oracle model, revisited. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 417\u2013434. Springer, Heidelberg (2009)"},{"issue":"2","key":"24_CR34","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1109\/TIFS.2012.2232653","volume":"8","author":"ACC Yao","year":"2013","unstructured":"Yao, A.C.C., Zhao, Y.: Online\/offline signatures for low-power devices. IEEE Trans. Inf. Forensics Secur. 8(2), 283\u2013294 (2013)","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"24_CR35","series-title":"Lecture Notes in Computer Science","first-page":"366","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"J Zhang","year":"2014","unstructured":"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\u2013385. Springer, Heidelberg (2014)"},{"key":"24_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/11599548_3","volume-title":"Information Security and Cryptology","author":"R Zhang","year":"2005","unstructured":"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\u201341. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Provable Security"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26059-4_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T15:44:00Z","timestamp":1748706240000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26059-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319260587","9783319260594"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26059-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 November 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}