{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:09:10Z","timestamp":1743073750336,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":41,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819609468"},{"type":"electronic","value":"9789819609475"}],"license":[{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-0947-5_3","type":"book-chapter","created":{"date-parts":[[2024,12,8]],"date-time":"2024-12-08T04:27:36Z","timestamp":1733632056000},"page":"65-93","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalized Hybrid Search with\u00a0Applications to\u00a0Blockchains and\u00a0Hash Function Security"],"prefix":"10.1007","author":[{"given":"Alexandru","family":"Cojocaru","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Garay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,9]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz. Post-quantum security of the even-mansour cipher. In Advances in Cryptology \u2013 EUROCRYPT 2022, pages 458\u2013487. Springer, 2022.","DOI":"10.1007\/978-3-031-07082-2_17"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Advances in Cryptology \u2013 CRYPTO 2019, pages 269\u2013295. Springer, 2019.","DOI":"10.1007\/978-3-030-26951-7_10"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-secure message authentication via blind-unforgeability. In Advances in Cryptology \u2013 EUROCRYPT 2020. Springer, 2020.","DOI":"10.1007\/978-3-030-45727-3_27"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 474\u2013483. IEEE, 2014.","DOI":"10.1109\/FOCS.2014.57"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Charles\u00a0H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510\u20131523, 1997.","DOI":"10.1137\/S0097539796300933"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Dan Boneh, \u00d6zg\u00fcr Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Advances in Cryptology \u2013 ASIACRYPT 2011, pages 41\u201369. Springer, 2011.","DOI":"10.1007\/978-3-642-25385-0_3"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM conference on Computer and Communications Security, pages 62\u201373, 1993.","DOI":"10.1145\/168588.168596"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In Advances in Cryptology\u2013EUROCRYPT 1994, pages 92\u2013111. Springer, 1994.","DOI":"10.1007\/BFb0053428"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Mihir Bellare and Phillip Rogaway. The exact security of digital signatures-how to sign with rsa and rabin. In Advances in Cryptology\u2013Eurocrypt 1996, pages 399\u2013416. Springer, 1996.","DOI":"10.1007\/3-540-68339-9_34"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Advances in Cryptology \u2013 CRYPTO 2013, pages 361\u2013379. Springer, 2013.","DOI":"10.1007\/978-3-642-40084-1_21"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. The complexity of nisq, 2022.","DOI":"10.1038\/s41467-023-41217-6"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. On the need for large quantum depth. J. ACM, 70(1), jan 2023.","DOI":"10.1145\/3570637"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"C\u00e9line Chevalier, Ehsan Ebrahimi, and Quoc-Huy Vu. On security notions for encryption in a quantum world. In Progress in Cryptology \u2013 INDOCRYPT 2022, pages 592\u2013613. Springer, 2023.","DOI":"10.1007\/978-3-031-22912-1_26"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"944","DOI":"10.22331\/q-2023-03-09-944","volume":"7","author":"Alexandru Cojocaru","year":"2023","unstructured":"Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, and Petros Wallden. Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin\u2019s Post-Quantum Security. Quantum, 7:944, 2023.","journal-title":"Quantum"},{"key":"3_CR15","unstructured":"Alexandru Cojocaru, Juan Garay, and Fang Song. Generalized hybrid search and applications. Cryptology ePrint Archive, Paper 2023\/798, 2023."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 889-901, New York, NY, USA, 2020. Association for Computing Machinery.","DOI":"10.1145\/3357713.3384269"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. Succinct arguments in the quantum random oracle model. In 17th International Theory of Cryptography Conference \u2013 TCC 2019, pages 1\u201329. Springer, 2019.","DOI":"10.1007\/978-3-030-36033-7_1"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Jelle Don, Serge Fehr, and Yu-Hsuan Huang. Adaptive versus static multi-oracle algorithms, and quantum security of a split-key prf. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography, pages 33\u201351, Cham, 2022. Springer Nature Switzerland.","DOI":"10.1007\/978-3-031-22318-1_2"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Security of the Fiat-Shamir transformation in the quantum random-oracle model. In Advances in Cryptology \u2013 CRYPTO 2019, pages 356\u2013383. Springer, 2019.","DOI":"10.1007\/978-3-030-26951-7_13"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Online-extractability in the quantum random-oracle model. In Advances in Cryptology \u2013 EUROCRYPT 2022, pages 677\u2013706. Springer, 2022.","DOI":"10.1007\/978-3-031-07082-2_24"},{"issue":"5","key":"3_CR21","doi-asserted-by":"publisher","first-page":"533","DOI":"10.26421\/QIC9.5-6-12","volume":"9","author":"C\u0103t\u0103lin Dohotaru","year":"2009","unstructured":"C\u0103t\u0103lin Dohotaru and Peter H\u00f8yer. Exact quantum lower bound for grover\u2019s problem. Quantum Information & Computation, 9(5):533\u2013540, 2009.","journal-title":"Quantum Information & Computation"},{"key":"3_CR22","unstructured":"Edward Eaton and Fang Song. Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography \u2013 TQC 2015, volume\u00a044 of Leibniz International Proceedings in Informatics (LIPIcs), pages 147\u2013162. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2015."},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Edward Eaton and Fang Song. A note on the instantiability of the quantum random oracle. In International Conference on Post-Quantum Cryptography, pages 503\u2013523. Springer, 2020.","DOI":"10.1007\/978-3-030-44223-1_27"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology, 26(1):80\u2013101, 2013. Preliminary version in CRYPTO 1999.","DOI":"10.1007\/s00145-011-9114-1"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. RSA-OAEP is secure under the rsa assumption. Journal of Cryptology, 17(2):81\u2013104, 2004. Preliminary version in CRYPTO 2001.","DOI":"10.1007\/s00145-002-0204-y"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Lov\u00a0K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212\u2013219. ACM, 1996.","DOI":"10.1145\/237814.237866"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Dennis Hofheinz, Kathrin H\u00f6velmanns, and Eike Kiltz. A modular analysis of the fujisaki-okamoto transformation. In 15th International Theory of Cryptography Conference \u2013 TCC 2017, pages 341\u2013371. Springer, 2017.","DOI":"10.1007\/978-3-319-70500-2_12"},{"key":"3_CR28","unstructured":"Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. Quantum-classical tradeoffs in the random oracle model. CoRR, abs\/2211.12954, 2022."},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Andreas H\u00fclsing, Joost Rijneveld, and Fang Song. Mitigating multi-target attacks in hash-based signatures. In 19th IACR International Conference on Public-Key Cryptography \u2014 PKC 2016, pages 387\u2013416. Springer, 2016.","DOI":"10.1007\/978-3-662-49384-7_15"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Joseph Jaeger, Fang Song, and Stefano Tessaro. Quantum key-length extension. In 19th International Theory of Cryptography Conference \u2013 TCC 2021, pages 209\u2013239. Springer, 2021.","DOI":"10.1007\/978-3-030-90459-3_8"},{"key":"3_CR31","doi-asserted-by":"crossref","unstructured":"Hidenori Kuwakado and Masakatu Morii. Quantum distinguisher between the 3-round feistel cipher and the random permutation. In 2010 IEEE International Symposium on Information Theory, pages 2682\u20132685. IEEE, 2010.","DOI":"10.1109\/ISIT.2010.5513654"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"John Preskill","year":"2018","unstructured":"John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018.","journal-title":"Quantum"},{"key":"3_CR33","unstructured":"Ansis Rosmanis. Hybrid quantum-classical search algorithms. arXiv preprint arXiv:2202.11443, 2022."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Victor Shoup. OAEP reconsidered. In Advances in Cryptology\u2013CRYPTO 2001, pages 239\u2013259. Springer, 2001.","DOI":"10.1007\/3-540-44647-8_15"},{"key":"3_CR35","unstructured":"Xiaoming Sun and Yufan Zheng. Hybrid decision trees: Longer quantum time is strictly more powerful, 2019."},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Dominique Unruh. Non-interactive zero-knowledge proofs in the quantum random oracle model. In Advances in Cryptology \u2013 EUROCRYPT 2015, pages 755\u2013784. Springer, 2015.","DOI":"10.1007\/978-3-662-46803-6_25"},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"Takashi Yamakawa and Mark Zhandry. Classical vs quantum random oracles. In Advances in Cryptology \u2013 EUROCRYPT 2021, pages 568\u2013597. Springer, 2021.","DOI":"10.1007\/978-3-030-77886-6_20"},{"issue":"4","key":"3_CR38","doi-asserted-by":"publisher","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","volume":"60","author":"Christof Zalka","year":"1999","unstructured":"Christof Zalka. Grover\u2019s quantum searching algorithm is optimal. Physical Review A, 60(4):2746, 1999.","journal-title":"Physical Review A"},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"Mark Zhandry. Secure identity-based encryption in the quantum random oracle model. International Journal of Quantum Information, 13(04):1550014, 2015. Preliminary version in IACR CRYPTO 2012.","DOI":"10.1142\/S0219749915500148"},{"key":"3_CR40","doi-asserted-by":"crossref","unstructured":"Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Advances in Cryptology \u2013 CRYPTO 2019, pages 239\u2013268. Springer, 2019.","DOI":"10.1007\/978-3-030-26951-7_9"},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"Mark Zhandry. How to construct quantum random functions. Journal of the ACM (JACM), 68(5):1\u201343, 2021. Preliminary version in FOCS 2012.","DOI":"10.1145\/3450745"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-0947-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,8]],"date-time":"2024-12-08T05:02:39Z","timestamp":1733634159000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-0947-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,9]]},"ISBN":["9789819609468","9789819609475"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-0947-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,12,9]]},"assertion":[{"value":"9 December 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ASIACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Theory and Application of Cryptology and Information Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kolkata","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 December 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 December 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"asiacrypt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/asiacrypt.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}