{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T10:44:51Z","timestamp":1786963491668,"version":"3.56.0"},"reference-count":17,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,3,5]]},"abstract":"<jats:p>There has been a recent interest in proposing quantum protocols whose security   relies on weaker computational assumptions than their classical counterparts.   Importantly to our work, it has been recently shown that public-key encryption   (PKE) from one-way functions (OWF) is possible if we consider quantum public   keys.   Notice that we do not expect classical PKE from OWF given the impossibility   results of Impagliazzo and Rudich (STOC'89).<\/jats:p>\n                  <jats:p>However, the distribution of quantum public keys is a challenging task.   Therefore, the main question that motivates our work is if quantum PKE from   OWF is possible if we have classical public keys.   Such protocols are impossible if ciphertexts are also classical, given the   impossibility result of Austrin et al.(CRYPTO'22) of quantum enhanced   key-agreement (KA) with classical communication.<\/jats:p>\n                  <jats:p>In this paper, we focus on black-box separation for PKE with classical public   key and quantum ciphertext from OWF under the polynomial compatibility   conjecture, first introduced in Austrin et al..   More precisely, we show the separation when the decryption algorithm of the   PKE does not query the OWF.   We prove our result by extending the techniques of Austrin et al.   and we show an attack for KA in an extended classical communication model   where the last message in the protocol can be a quantum state.<\/jats:p>","DOI":"10.62056\/ahvr-11zn4","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T15:27:10Z","timestamp":1712676430000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-6394-9387","authenticated-orcid":false,"given":"Samuel","family":"Bouaziz\u2013Ermann","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05krcen59","id-type":"ROR","asserted-by":"publisher"}],"name":"Sorbonne Universit\u00e9, CNRS, LIP6","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7374-7082","authenticated-orcid":false,"given":"Alex","family":"Grilo","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05krcen59","id-type":"ROR","asserted-by":"publisher"}],"name":"Sorbonne Universit\u00e9, CNRS, LIP6","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2113-3967","authenticated-orcid":false,"given":"Damien","family":"Vergnaud","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05krcen59","id-type":"ROR","asserted-by":"publisher"}],"name":"Sorbonne Universit\u00e9, CNRS, LIP6","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4916-6798","authenticated-orcid":false,"given":"Quoc-Huy","family":"Vu","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02setav13","id-type":"ROR","asserted-by":"publisher"}],"name":"L\u00e9onard de Vinci P\u00f4le Universitaire, Research Center","place":["Paris La D\u00e9fense, 92 916, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:Wiesner83","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/1008908.1008920","article-title":"Conjugate coding","volume":"15","author":"Stephen Wiesner","year":"1983","journal-title":"SIGACT News"},{"key":"ref2:BB84","first-page":"8","article-title":"Quantum cryptography: Public key distribution and\n                   coin tossing","volume-title":"IEEE International Conference on Computers, Systems\n                   and Signal Processing","volume":"175","author":"Charles H. Bennett","year":"1984"},{"key":"ref3:EC:GLSV21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-030-77886-6_18","article-title":"Oblivious Transfer Is in MiniQCrypt","volume-title":"EUROCRYPT\u00a02021, Part\u00a0II","volume":"12697","author":"Alex B. Grilo","year":"2021"},{"key":"ref4:C:BCKM21a","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-030-84242-0_15","article-title":"On the Round Complexity of Secure Quantum\n                   Computation","volume-title":"CRYPTO\u00a02021, Part\u00a0I","volume":"12825","author":"James Bartusek","year":"2021"},{"key":"ref5:C:AnaQiaYue22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-031-15802-5_8","article-title":"Cryptography from Pseudorandom Quantum States","volume-title":"CRYPTO\u00a02022, Part\u00a0I","volume":"13507","author":"Prabhanjan Ananth","year":"2022"},{"key":"ref6:Kre21","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2021.2","article-title":"Quantum Pseudorandomness and Classical Complexity","volume-title":"16th Conference on the Theory of Quantum Computation,\n                   Communication and Cryptography, TQC 2021, July 5-8,\n                   2021, Virtual Conference","volume":"197","author":"William Kretschmer","year":"2021"},{"key":"ref7:STOC:KQST23","series-title":"STOC 2023","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1589","DOI":"10.1145\/3564246.3585225","article-title":"Quantum Cryptography in Algorithmica","volume-title":"Proceedings of the 55th Annual ACM Symposium on\n                   Theory of Computing","author":"William Kretschmer","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450399135"},{"key":"ref8:STOC:ImpRud89","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/73007.73012","article-title":"Limits on the Provable Consequences of One-Way\n                   Permutations","volume-title":"21st ACM STOC","author":"Russell Impagliazzo","year":"1989"},{"key":"ref9:C:ACCFLM22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-031-15979-4_6","article-title":"On the Impossibility of Key Agreements from Quantum\n                   Random Oracles","volume-title":"CRYPTO\u00a02022, Part\u00a0II","volume":"13508","author":"Per Austrin","year":"2022"},{"key":"ref10:Coladangelo23","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2302.12821","article-title":"Quantum trapdoor functions from classical one-way\n                   functions","volume":"abs\/2302.12821","author":"Andrea Coladangelo","year":"2023","journal-title":"CoRR"},{"key":"ref11:BGHMSVW23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-031-48624-1_8","article-title":"Public-Key Encryption with\u00a0Quantum Keys","volume-title":"Theory of Cryptography","author":"Khashayar Barooti","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031486241"},{"key":"ref12:KMNY23","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.01800","article-title":"Quantum Public-Key Encryption with Tamper-Resilient\n                   Public Keys from One-Way Functions","author":"Fuyuki Kitagawa","year":"2023"},{"key":"ref13:EPRINT:MorYam22c","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2210.03394","article-title":"One-Wayness in Quantum Cryptography","author":"Tomoyuki Morimae","year":"2022"},{"key":"ref14:C:BarMah09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-03356-8_22","article-title":"Merkle Puzzles Are Optimal - An $O(n^2)$-Query\n                   Attack on Any Key Exchange from a Random Oracle","volume-title":"CRYPTO\u00a02009","volume":"5677","author":"Boaz Barak","year":"2009"},{"key":"ref15:EC:ChuLinMah23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-031-30545-0_6","article-title":"Black-Box Separations for Non-interactive Classical\n                   Commitments in a Quantum World","volume-title":"EUROCRYPT\u00a02023, Part\u00a0I","volume":"14004","author":"Kai-Min Chung","year":"2023"},{"key":"ref16:nielsen2010quantum","article-title":"Quantum computation and quantum information","author":"Isaac L Nielsen Michael A and Chuang","year":"2010"},{"key":"ref17:C:Zhandry19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-030-26951-7_9","article-title":"How to Record Quantum Queries, and Applications to\n                   Quantum Indifferentiability","volume-title":"CRYPTO\u00a02019, Part\u00a0II","volume":"11693","author":"Mark Zhandry","year":"2019"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T16:25:35Z","timestamp":1733847935000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":17,"URL":"https:\/\/doi.org\/10.62056\/ahvr-11zn4","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2024-01-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-105"}}