{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T10:34:45Z","timestamp":1763202885783},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:00:00Z","timestamp":1719878400000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e4t der Bundeswehr M\u00fcnchen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Chameleon-hash functions, introduced by Krawczyk and Rabin (NDSS\u201900), are trapdoor collision-resistant hash functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be found efficiently. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications, ranging from editable blockchains to advanced signature and encryption schemes. We observe that, in latter applications, various different notions of collision-resistance are used, and it is not always clear if the respective notion really covers what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and by means of selected applications discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature (which we call full collision-resistance). Finally, we present a surprisingly simple, and efficient, black-box construction of chameleon-hash functions achieving this strong notion of full collision-resistance.\n<\/jats:p>","DOI":"10.1007\/s00145-024-09510-9","type":"journal-article","created":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T21:03:36Z","timestamp":1719954216000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Bringing Order to Chaos: The Case of Collision-Resistant Chameleon-Hashes"],"prefix":"10.1007","volume":"37","author":[{"given":"David","family":"Derler","sequence":"first","affiliation":[]},{"given":"Kai","family":"Samelin","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Slamanig","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"9510_CR1","doi-asserted-by":"crossref","unstructured":"M. Abe, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Tagged one-time signatures: Tight security and optimal tag size, in PKC. (2013), pp. 312\u2013331","DOI":"10.1007\/978-3-642-36362-7_20"},{"key":"9510_CR2","doi-asserted-by":"crossref","unstructured":"S. Alsouri, \u00d6. Dagdelen, S. Katzenbeisser, Group-based attestation: Enhancing privacy and management in remote attestation, in Trust. (2010), pp. 63\u201377","DOI":"10.1007\/978-3-642-13869-0_5"},{"key":"9510_CR3","unstructured":"D.F. Aranha, C.P.L. Gouv\u00eaa, T. Markmann, R.S. Wahby, K. Liao, RELIC is an Efficient LIbrary for Cryptography. https:\/\/github.com\/relic-toolkit\/relic"},{"key":"9510_CR4","doi-asserted-by":"crossref","unstructured":"G. Ateniese, D.H. Chou, B. de\u00a0Medeiros, G. Tsudik, Sanitizable signatures, in ESORICS. (2005), pp. 159\u2013177","DOI":"10.1007\/11555827_10"},{"key":"9510_CR5","doi-asserted-by":"crossref","unstructured":"G. Ateniese, B. Magri, D. Venturi, E.R. Andrade, Redactable blockchain - or - rewriting history in bitcoin and friends, in EuroS &P. (2017), pp. 111\u2013126","DOI":"10.1109\/EuroSP.2017.37"},{"key":"9510_CR6","doi-asserted-by":"crossref","unstructured":"G. Ateniese, B. de\u00a0Medeiros, Identity-based chameleon hash and applications, In FC. (2004), pp. 164\u2013180","DOI":"10.1007\/978-3-540-27809-2_19"},{"key":"9510_CR7","doi-asserted-by":"crossref","unstructured":"G. Ateniese, B. de\u00a0Medeiros, On the key exposure problem in chameleon hashes, in SCN. (2004), pp. 165\u2013179","DOI":"10.1007\/978-3-540-30598-9_12"},{"key":"9510_CR8","doi-asserted-by":"crossref","unstructured":"F. Bao, R.H. Deng, X. Ding, J. Lai, Y. Zhao, Hierarchical identity-based chameleon hash and its applications, in ACNS. (2011), pp. 201\u2013219","DOI":"10.1007\/978-3-642-21554-4_12"},{"key":"9510_CR9","doi-asserted-by":"crossref","unstructured":"M. Bellare, A. Boldyreva, S. Micali, Public-key encryption in a multi-user setting: Security proofs and improvements, in Eurocrypt. (2000), pp. 259\u2013274","DOI":"10.1007\/3-540-45539-6_18"},{"key":"9510_CR10","doi-asserted-by":"crossref","unstructured":"M. Bellare, C. Namprempre, D. Pointcheval, M. Semanko, The one-more-rsa-inversion problems and the security of chaum\u2019s blind signature scheme. J. Cryptol. 16(3), 185\u2013215 (2003)","DOI":"10.1007\/s00145-002-0120-1"},{"key":"9510_CR11","doi-asserted-by":"crossref","unstructured":"M. Bellare, T. Ristov, Hash functions from sigma protocols and improvements to VSH, in Asiacrypt. (2008), pp. 125\u2013142","DOI":"10.1007\/978-3-540-89255-7_9"},{"key":"9510_CR12","doi-asserted-by":"crossref","unstructured":"M. Bellare, T. Ristov, A characterization of chameleon hash functions and new, efficient designs. J. Cryptol. 27(4), 799\u2013823 (2014)","DOI":"10.1007\/s00145-013-9155-8"},{"key":"9510_CR13","unstructured":"M. Bellare, D. Riepel, L. Shea, Highly-effective backdoors for hash functions and beyond. Cryptology ePrint Archive, Paper 2024\/536 (2024). https:\/\/eprint.iacr.org\/2024\/536"},{"key":"9510_CR14","doi-asserted-by":"crossref","unstructured":"O. Blazy, S.A. Kakvi, E. Kiltz, J. Pan, Tightly-secure signatures from chameleon hash functions, in PKC. (2015), pp. 256\u2013279","DOI":"10.1007\/978-3-662-46447-2_12"},{"key":"9510_CR15","doi-asserted-by":"crossref","unstructured":"D. Boneh, B. Lynn, H. Shacham, Short signatures from the weil pairing, in C. Boyd, editors, Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings. Lecture Notes in Computer Science, vol. 2248 (Springer, 2001), pp. 514\u2013532","DOI":"10.1007\/3-540-45682-1_30"},{"key":"9510_CR16","doi-asserted-by":"crossref","unstructured":"G. Brassard, D. Chaum, C. Cr\u00e9peau, Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156\u2013189 (1988)","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"9510_CR17","doi-asserted-by":"crossref","unstructured":"C. Brzuska, M. Fischlin, T. Freudenreich, A. Lehmann, M. Page, J. Schelbert, D. Schr\u00f6der, F. Volk, Security of sanitizable signatures revisited, in PKC. (2009), pp. 317\u2013336","DOI":"10.1007\/978-3-642-00468-1_18"},{"key":"9510_CR18","doi-asserted-by":"crossref","unstructured":"J. Camenisch, D. Derler, S. Krenn, H.C. P\u00f6hls, K. Samelin, D. Slamanig, Chameleon-hashes with ephemeral trapdoors - and applications to invisible sanitizable signatures, in PKC. (2017), pp. 152\u2013182","DOI":"10.1007\/978-3-662-54388-7_6"},{"key":"9510_CR19","doi-asserted-by":"crossref","unstructured":"D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, Bonsai trees, or how to delegate a lattice basis, in Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco \/ French Riviera, May 30 - June 3, 2010. Proceedings. (2010), pp. 523\u2013552","DOI":"10.1007\/978-3-642-13190-5_27"},{"key":"9510_CR20","doi-asserted-by":"crossref","unstructured":"X. Chen, F. Zhang, K. Kim, Chameleon hashing without key exposure, in ISC. (2004), pp. 87\u201398","DOI":"10.1007\/978-3-540-30144-8_8"},{"key":"9510_CR21","doi-asserted-by":"crossref","unstructured":"X. Chen, F. Zhang, W. Susilo, Y. Mu, Efficient generic on-line\/off-line signatures without key exposure, in ACNS. (2007), pp. 18\u201330","DOI":"10.1007\/978-3-540-72738-5_2"},{"key":"9510_CR22","doi-asserted-by":"crossref","unstructured":"J. Choi, S. Jung, A handover authentication using credentials based on chameleon hashing. IEEE Commun. Lett. 14(1), 54\u201356 (2010)","DOI":"10.1109\/LCOMM.2010.01.091607"},{"key":"9510_CR23","unstructured":"A. Cingolani, Bitcoin as an Ideal Redactable Transaction Ledger. Master\u2019s thesis, Sapienza University of Rome (2020)"},{"key":"9510_CR24","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. Damg\u00e5rd, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in Crypto. (1994), pp. 174\u2013187","DOI":"10.1007\/3-540-48658-5_19"},{"key":"9510_CR25","doi-asserted-by":"crossref","unstructured":"R. Cramer, V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in Crypto. (1998), pp. 13\u201325","DOI":"10.1007\/BFb0055717"},{"key":"9510_CR26","doi-asserted-by":"crossref","unstructured":"D. Derler, K. Samelin, D. Slamanig, C. Striecks, Fine-grained and controlled rewriting in blockchains: Chameleon-hashing gone attribute-based, in NDSS (2019)","DOI":"10.14722\/ndss.2019.23066"},{"key":"9510_CR27","doi-asserted-by":"crossref","unstructured":"D. Derler, D. Slamanig, Key-homomorphic signatures: definitions and applications to multiparty signatures and non-interactive zero-knowledge. Des. Codes Cryptogr. 87(6), 1373\u20131413 (2019)","DOI":"10.1007\/s10623-018-0535-9"},{"key":"9510_CR28","doi-asserted-by":"crossref","unstructured":"D. Derler, S. Krenn, K. Samelin, D. Slamanig, Fully collision-resistant chameleon-hashes from simpler and post-quantum assumptions, in C. Galdi, V. Kolesnikov, editors, Security and Cryptography for Networks - 12th International Conference, SCN 2020, Amalfi, Italy, September 14-16, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12238 (Springer, 2020), pp. 427\u2013447","DOI":"10.1007\/978-3-030-57990-6_21"},{"key":"9510_CR29","doi-asserted-by":"crossref","unstructured":"D. Derler, K. Samelin, D. Slamanig, Bringing order to chaos: The case of collision-resistant chameleon-hashes, in A. Kiayias, M. Kohlweiss, P. Wallden, V. Zikas, editors, Public-Key Cryptography - PKC 2020. (2020), pp. 462\u2013492","DOI":"10.1007\/978-3-030-45374-9_16"},{"key":"9510_CR30","doi-asserted-by":"crossref","unstructured":"D. Derler, D. Slamanig, Highly-efficient fully-anonymous dynamic group signatures, in AsiaCCS. (2018), pp. 551\u2013565","DOI":"10.1145\/3196494.3196507"},{"key":"9510_CR31","doi-asserted-by":"crossref","unstructured":"D. Deuber, B. Magri, S.A.K. Thyagarajan Redactable blockchain in the permissionless setting, in IEEE S &P. (2019), pp. 124\u2013138","DOI":"10.1109\/SP.2019.00039"},{"key":"9510_CR32","doi-asserted-by":"crossref","unstructured":"Y. Dodis, K. Haralambiev, A. L\u00f3pez-Alt, D. Wichs Efficient public-key cryptography in the presence of key leakage, in Asiacrypt. (2010), pp. 613\u2013631","DOI":"10.1007\/978-3-642-17373-8_35"},{"key":"9510_CR33","doi-asserted-by":"crossref","unstructured":"S. Even, O. Goldreich, S. Micali, On-line\/off-line digital signatures. J. Cryptol. 9(1), 35\u201367 (1996)","DOI":"10.1007\/BF02254791"},{"key":"9510_CR34","doi-asserted-by":"crossref","unstructured":"S. Even, O. Goldreich, S. Micali, On-line\/off-line digital schemes, in G. Brassard, editors , Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. Lecture Notes in Computer Science, vol. 435 (Springer, 1989), pp. 263\u2013275","DOI":"10.1007\/0-387-34805-0_24"},{"key":"9510_CR35","doi-asserted-by":"crossref","unstructured":"S. Faust, M. Kohlweiss, G.A. Marson, D. Venturi, On the non-malleability of the fiat-shamir transform, in Indocrypt. (2012), pp. 60\u201379","DOI":"10.1007\/978-3-642-34931-7_5"},{"key":"9510_CR36","doi-asserted-by":"crossref","unstructured":"A. Fiat, A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, in Crypto. (1986), pp. 186\u2013194","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9510_CR37","doi-asserted-by":"crossref","unstructured":"T.E. Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in Crypto. (1984), pp. 10\u201318","DOI":"10.1007\/3-540-39568-7_2"},{"key":"9510_CR38","doi-asserted-by":"crossref","unstructured":"J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in Asiacrypt. (2006), pp. 444\u2013459","DOI":"10.1007\/11935230_29"},{"key":"9510_CR39","doi-asserted-by":"crossref","unstructured":"J. Groth, Efficient fully structure-preserving signatures for large messages, in Asiacrypt. (2015), pp. 239\u2013259","DOI":"10.1007\/978-3-662-48797-6_11"},{"key":"9510_CR40","doi-asserted-by":"crossref","unstructured":"J. Groth, A. Sahai, Efficient non-interactive proof systems for bilinear groups, in Eurocrypt. (2008), pp. 415\u2013432","DOI":"10.1007\/978-3-540-78967-3_24"},{"key":"9510_CR41","doi-asserted-by":"crossref","unstructured":"S. Guo, D. Zeng, Y. Xiang, Chameleon hashing for secure and privacy-preserving vehicular communications. IEEE Trans. Parallel Distrib. Syst. 25(11) (2014)","DOI":"10.1109\/TPDS.2013.277"},{"key":"9510_CR42","doi-asserted-by":"crossref","unstructured":"S. Hada, T. Tanaka, On the existence of 3-round zero-knowledge protocols, in Crypto. (1998), pp. 408\u2013423","DOI":"10.1007\/BFb0055744"},{"key":"9510_CR43","doi-asserted-by":"crossref","unstructured":"S. Hohenberger, B. Waters, Short and stateless signatures from the RSA assumption, in Crypto. (2009), pp. 654\u2013670","DOI":"10.1007\/978-3-642-03356-8_38"},{"key":"9510_CR44","doi-asserted-by":"publisher","unstructured":"J. Jancar, V. Sedlacek, P. Svenda, M. S\u00fds, Minerva: The curse of ECDSA nonces systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2020(4), 281\u2013308 (2020). https:\/\/doi.org\/10.13154\/tches.v2020.i4.281-308","DOI":"10.13154\/tches.v2020.i4.281-308"},{"key":"9510_CR45","doi-asserted-by":"crossref","unstructured":"M. Khalili, M. Dakhilalian, W. Susilo, Efficient chameleon hash functions in the enhanced collision resistant model. Inf. Sci. 510, 155\u2013164 (2020)","DOI":"10.1016\/j.ins.2019.09.001"},{"key":"9510_CR46","unstructured":"H. Krawczyk, T. Rabin, Chameleon signatures, in NDSS. (2000), pp. 143\u2013154"},{"key":"9510_CR47","unstructured":"Y. Li, S. Liu, Tagged chameleon hash from lattices and application to redactable blockchain. Cryptology ePrint Archive, Paper 2023\/774 (to appear at PKC 2024) (2023). https:\/\/eprint.iacr.org\/2023\/774"},{"key":"9510_CR48","doi-asserted-by":"crossref","unstructured":"R. Matzutt, J. Hiller, M. Henze, J.H. Ziegeldorf, D. M\u00fcllmann, O. Hohlfeld, K. Wehrle, A quantitative analysis of the impact of arbitrary blockchain content on bitcoin, in FC. (2018), pp. 420\u2013438","DOI":"10.1007\/978-3-662-58387-6_23"},{"key":"9510_CR49","doi-asserted-by":"crossref","unstructured":"P. Mohassel, One-time signatures and chameleon hash functions, in SAC. (2010), pp. 302\u2013319","DOI":"10.1007\/978-3-642-19574-7_21"},{"key":"9510_CR50","doi-asserted-by":"crossref","unstructured":"T.P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in Crypto. (1991), pp. 129\u2013140","DOI":"10.1007\/3-540-46766-1_9"},{"key":"9510_CR51","doi-asserted-by":"crossref","unstructured":"K. Samelin, D. Slamanig, Policy-based sanitizable signatures, in CT-RSA. (2020), pp. 538\u2013563","DOI":"10.1007\/978-3-030-40186-3_23"},{"key":"9510_CR52","doi-asserted-by":"crossref","unstructured":"A. Shamir, Y. Tauman, Improved online\/offline signature schemes, in Crypto. (2001), pp. 355\u2013367","DOI":"10.1007\/3-540-44647-8_21"},{"key":"9510_CR53","doi-asserted-by":"crossref","unstructured":"R. Steinfeld, L. Bull, H. Wang, J. Pieprzyk, Universal designated-verifier signatures, in Asiacrypt. (2003), pp. 523\u2013542","DOI":"10.1007\/978-3-540-40061-5_33"},{"key":"9510_CR54","doi-asserted-by":"crossref","unstructured":"R. Steinfeld, H. Wang, J. Pieprzyk, Efficient extension of standard schnorr\/rsa signatures into universal designated-verifier signatures, in PKC. (2004), pp. 86\u2013100","DOI":"10.1007\/978-3-540-24632-9_7"},{"key":"9510_CR55","doi-asserted-by":"crossref","unstructured":"G. Tziakouris, Cryptocurrencies - A forensic challenge or opportunity for law enforcement? an INTERPOL perspective. IEEE S &P 16(4) (2018)","DOI":"10.1109\/MSP.2018.3111243"},{"key":"9510_CR56","doi-asserted-by":"publisher","unstructured":"R.S. Wahby, D. Boneh, Fast and simple constant-time hashing to the BLS12-381 elliptic curve. IACR Trans. Cryptogr. Hardw. Embed. Syst. 20(4), 154\u2013179 (2019). https:\/\/doi.org\/10.13154\/tches.v2019.i4.154-179","DOI":"10.13154\/tches.v2019.i4.154-179"},{"key":"9510_CR57","doi-asserted-by":"crossref","unstructured":"R. Zhang, Tweaking TBE\/IBE to PKE transforms with chameleon hash functions, in ACNS. (2007), pp. 323\u2013339","DOI":"10.1007\/978-3-540-72738-5_21"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09510-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09510-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09510-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T10:05:10Z","timestamp":1722333910000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09510-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["9510"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09510-9","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"18 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"29"}}