{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:29:30Z","timestamp":1740180570207,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T00:00:00Z","timestamp":1734220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T00:00:00Z","timestamp":1734220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172405"],"award-info":[{"award-number":["62172405"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"Abstract<\/jats:title>The semi-classical One-Way to Hiding (SC-O2H) lemma given by Ambainis et al. (CRYPTO 2019) is a crucial technique to solve the reprogramming problem in the quantum random oracle model (QROM), which can lead to quadratically better bounds for many cases involving guessing games. To achieve tighter bounds, Bindel et al. (TCC, 2019) introduced the double-sided One-Way to Hiding (DS-O2H) lemma, which avoids the loss of query times suffered by the SC-O2H lemma. However, the potential of the DS-O2H lemma to provide better bounds for guessing games has not been considered by far. In this paper, a new double-sided O2H lemma is proposed. By using it, we for the first time give fully tight bounds for several cases involving guessing games. In summary, we show the following results in the QROM: (i) The hardness of inverting a random oracle with the leakage of a one-way injective function can be tightly reduced to the hardness of inverting the involved one-way injective function. (ii) Duman et al. (PKC 2023) introduced the randomness recoverability and defined two transformations $$\\textsf {ACWC}_0$$<\/jats:tex-math>\n \n ACWC<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\textsf {ACWC}$$<\/jats:tex-math>\n ACWC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> relative to random oracles. For $$\\textsf {ACWC}_0$$<\/jats:tex-math>\n \n ACWC<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we prove that its security can be tightly reduced to the security of the underlying public key encryption (PKE) scheme with the randomness recoverability. For $$\\textsf {ACWC}$$<\/jats:tex-math>\n ACWC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we design a variant $$\\textsf {ACWC}_1$$<\/jats:tex-math>\n \n ACWC<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and prove that its security can be tightly reduced to the security of the underlying PKE scheme with the unique randomness recoverability (a property slightly stronger than randomness recoverability). (iii) The security of the modular Fujisaki-Okamoto () transformation introduced by Hofheinz et al. (TCC 2017), can be tightly reduced to the security of the underlying PKE scheme with the unique randomness recoverability. Additionally, assuming the underlying PKE scheme is unique randomness recoverable, we prove the security of -like transformations \n\"Image missing\"\n(TCC, 2017) in the QROM, and as far as we know, our proof is tighter than the currently best proof.<\/jats:p>","DOI":"10.1186\/s42400-024-00228-6","type":"journal-article","created":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T02:01:41Z","timestamp":1734228101000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Double-sided: tight proofs for guessing games in the quantum random oracle model"],"prefix":"10.1186","volume":"7","author":[{"given":"Jiawei","family":"Bao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiangxia","family":"Ge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Xue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,15]]},"reference":[{"key":"228_CR1","doi-asserted-by":"publisher","unstructured":"Ambainis A, Hamburg M, Unruh D (2019) Quantum security proofs using semi-classical oracles, pp 269\u2013295. https:\/\/doi.org\/10.1007\/978-3-030-26951-7_10","DOI":"10.1007\/978-3-030-26951-7_10"},{"key":"228_CR2","doi-asserted-by":"publisher","unstructured":"Bellare M, Rogaway P (1993) Random oracles are practical: A paradigm for designing efficient protocols. ACM, 62\u201373 https:\/\/doi.org\/10.1145\/168588.168596","DOI":"10.1145\/168588.168596"},{"key":"228_CR3","doi-asserted-by":"publisher","unstructured":"Bindel N, Hamburg M, H\u00f6velmanns K, H\u00fclsing A, Persichetti E (2019) Tighter proofs of CCA security in the quantum random oracle model. In: Theory of Cryptography Conference, pp 61\u201390. https:\/\/doi.org\/10.1007\/978-3-030-36033-7_3","DOI":"10.1007\/978-3-030-36033-7_3"},{"key":"228_CR4","doi-asserted-by":"publisher","unstructured":"Boneh D, Dagdelen \u00d6, Fischlin M, Lehmann A, Schaffner C, Zhandry M (2011) Random oracles in a quantum world. In: Advances in Cryptology - ASIACRYPT 2011 - 17th international conference on the theory and application of cryptology and information security, Seoul, South Korea, December 4-8, 2011. Proceedings, pp 41\u201369 . https:\/\/doi.org\/10.1007\/978-3-642-25385-0_3","DOI":"10.1007\/978-3-642-25385-0_3"},{"key":"228_CR5","unstructured":"Czajkowski J, Majenz C, Schaffner C, Zur S (2019) Quantum lazy sampling and game-playing proofs for quantum indifferentiability. IACR Cryptol. ePrint Arch., 428"},{"key":"228_CR6","doi-asserted-by":"publisher","unstructured":"Don J, Fehr S, Majenz C, Schaffner C (2022) Online-extractability in the quantum random-oracle model. In: Advances in Cryptology - EUROCRYPT 2022 - 41st annual international conference on the theory and applications of cryptographic techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III, pp. 677\u2013706. https:\/\/doi.org\/10.1007\/978-3-031-07082-2_24","DOI":"10.1007\/978-3-031-07082-2_24"},{"key":"228_CR7","doi-asserted-by":"publisher","unstructured":"Duman J, H\u00f6velmanns K, Kiltz E, Lyubashevsky V, Seiler G, Unruh D (2023) A thorough treatment of highly-efficient NTRU instantiations. In: Public-Key Cryptography - PKC 2023 - 26th IACR international conference on practice and theory of public-key cryptography, Atlanta, GA, USA, May 7-10, 2023, Proceedings, Part I, pp 65\u201394. https:\/\/doi.org\/10.1007\/978-3-031-31368-4_3","DOI":"10.1007\/978-3-031-31368-4_3"},{"key":"228_CR8","doi-asserted-by":"publisher","unstructured":"Ge J, Shan T, Xue R (2023) Tighter qcca-secure key encapsulation mechanism with explicit rejection in the quantum random oracle model. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd annual international cryptology conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V, pp. 292\u2013324. https:\/\/doi.org\/10.1007\/978-3-031-38554-4_10","DOI":"10.1007\/978-3-031-38554-4_10"},{"key":"228_CR9","doi-asserted-by":"publisher","unstructured":"Hofheinz D, H\u00f6velmanns K, Kiltz E (2017) A modular analysis of the fujisaki-okamoto transformation. In: theory of cryptography conference, pp 341\u2013371. https:\/\/doi.org\/10.1007\/978-3-319-70500-2_12","DOI":"10.1007\/978-3-319-70500-2_12"},{"key":"228_CR10","doi-asserted-by":"crossref","unstructured":"H\u00f6velmanns K, Majenz C (2023) A note on failing gracefully: Completing the picture for explicitly rejecting fujisaki-okamoto transforms using worst-case correctness. IACR Cryptol. ePrint Arch., 1811","DOI":"10.1007\/978-3-031-62746-0_11"},{"key":"228_CR11","doi-asserted-by":"publisher","unstructured":"Jiang H, Zhang Z, Chen L, Wang H, Ma Z (2018) Ind-cca-secure key encapsulation mechanism in the quantum random oracle model, revisited. In: Advances in Cryptology - CRYPTO 2018 - 38th annual international cryptology conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, pp. 96\u2013125. https:\/\/doi.org\/10.1007\/978-3-319-96878-0_4","DOI":"10.1007\/978-3-319-96878-0_4"},{"key":"228_CR12","doi-asserted-by":"publisher","unstructured":"Katsumata S, Kwiatkowski K, Pintore F, Prest T (2020) Scalable ciphertext compression techniques for post-quantum kems and their applications. In: Advances in Cryptology - ASIACRYPT 2020 - 26th international conference on the theory and application of cryptology and information security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part I, pp. 289\u2013320. https:\/\/doi.org\/10.1007\/978-3-030-64837-4_10","DOI":"10.1007\/978-3-030-64837-4_10"},{"key":"228_CR13","doi-asserted-by":"publisher","first-page":"4760","DOI":"10.1109\/TIFS.2023.3299172","volume":"18","author":"J Kim","year":"2023","unstructured":"Kim J, Park JH (2023) NTRU++: compact construction of NTRU using simple encoding method. IEEE Trans Inf Forensics Secur 18:4760\u20134774. https:\/\/doi.org\/10.1109\/TIFS.2023.3299172","journal-title":"IEEE Trans Inf Forensics Secur"},{"key":"228_CR14","doi-asserted-by":"publisher","unstructured":"Kuchta V, Sakzad A, Stehl\u00e9 D, Steinfeld R, Sun S (2020) Measure-rewind-measure: Tighter quantum random oracle model proofs for one-way to hiding and CCA security. In: Advances in Cryptology - EUROCRYPT 2020 - 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, pp. 703\u2013728. https:\/\/doi.org\/10.1007\/978-3-030-45727-3_24","DOI":"10.1007\/978-3-030-45727-3_24"},{"key":"228_CR15","doi-asserted-by":"publisher","unstructured":"Liu X, Wang M (2021) Qcca-secure generic key encapsulation mechanism with tighter security in the quantum random oracle model. In: Public-Key Cryptography - PKC 2021 - 24th IACR international conference on practice and theory of public key cryptography, virtual event, May 10-13, 2021, Proceedings, Part I, pp 3\u201326. https:\/\/doi.org\/10.1007\/978-3-030-75245-3_1","DOI":"10.1007\/978-3-030-75245-3_1"},{"key":"228_CR16","unstructured":"Nielsen MA, Chuang IL (2016) Quantum Computation and Quantum Information (10th Anniversary Edition)"},{"key":"228_CR17","unstructured":"Shoup V (2004) Sequences of games: a tool for taming complexity in security proofs. IACR Cryptol. ePrint Arch., 332"},{"issue":"6","key":"228_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/2817206","volume":"62","author":"D Unruh","year":"2015","unstructured":"Unruh D (2015) Revocable quantum timed-release encryption. J ACM 62(6):49\u201314976. https:\/\/doi.org\/10.1145\/2817206","journal-title":"J ACM"},{"key":"228_CR19","doi-asserted-by":"publisher","unstructured":"Xagawa K, Yamakawa T (2019) (tightly) qcca-secure key-encapsulation mechanism in the quantum random oracle model. In: Post-Quantum Cryptography - 10th international conference, PQCrypto 2019, Chongqing, China, May 8-10, 2019 Revised Selected Papers, pp. 249\u2013268. https:\/\/doi.org\/10.1007\/978-3-030-25510-7_14","DOI":"10.1007\/978-3-030-25510-7_14"},{"key":"228_CR20","doi-asserted-by":"publisher","unstructured":"Zhandry M (2012) How to construct quantum random functions. In: 53rd annual IEEE symposium on foundations of computer science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 679\u2013687. https:\/\/doi.org\/10.1109\/FOCS.2012.37","DOI":"10.1109\/FOCS.2012.37"},{"key":"228_CR21","doi-asserted-by":"publisher","unstructured":"Zhandry M (2012) Secure identity-based encryption in the quantum random oracle model. In: Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, pp. 758\u2013775. https:\/\/doi.org\/10.1007\/978-3-642-32009-5_44","DOI":"10.1007\/978-3-642-32009-5_44"},{"key":"228_CR22","doi-asserted-by":"publisher","unstructured":"Zhandry M (2019) How to record quantum queries, and applications to quantum indifferentiability. In: advances in cryptology - CRYPTO 2019 - 39th annual international cryptology conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II, pp. 239\u2013268. https:\/\/doi.org\/10.1007\/978-3-030-26951-7_9","DOI":"10.1007\/978-3-030-26951-7_9"},{"key":"228_CR23","doi-asserted-by":"crossref","unstructured":"Zhang J, Feng D, Yan D (2023) NEV: faster and smaller NTRU encryption using vector decoding. IACR Cryptol. ePrint Arch., 1298","DOI":"10.1007\/978-981-99-8739-9_6"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00228-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-024-00228-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00228-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T03:01:24Z","timestamp":1734231684000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-024-00228-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,15]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["228"],"URL":"https:\/\/doi.org\/10.1186\/s42400-024-00228-6","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2024,12,15]]},"assertion":[{"value":"11 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"66"}}