Hardness of Quantum Distribution Learning and Quantum Cryptography
Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae · 2025
Read Hardness of Quantum Distribution Learning and Quantum Cryptography by Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01292.txt.
Introduction
Taiga Hiroka and co-authors wrote a 2025 paper that ties quantum cryptography to the hardness of learning distributions. In classic crypto, one-way functions are the base assumption. Quantum crypto has a weaker cousin, called one-way puzzles, whose place was less clear.
The authors prove the first full match for those puzzles: they exist if and only if one strict form of quantum distribution learning is hard on average. They then ask if plain hardness of a hard class could yield the puzzles on its own. That path, they show, would force a split between quantum and classic sampling classes. A looser learning form gives a clean two way match with that class split. Side results link learning hardness to sampling gaps.
Catalog record
| CREATOR | Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01292
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hardness of Quantum Distribution Learning and Quantum Cryptography Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae Abstract The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. One-way puzzles (OWPuzzs) introduced by [Khurana and Tomer 2024] provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies 𝐏𝐏 ≠ 𝐁𝐐𝐏 \mathbf{PP}\neq\mathbf{BQP} [Cavalar, Goldin, Gray, Hall, Liu, and Pelecanos 2025], while the converse remains an open question. In classical cryptography, the analogous problem – whether OWFs can be constructed from 𝐏 ≠ 𝐍𝐏 \mathbf{P}\neq\mathbf{NP} – is one of the most central open problems, and has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to the existence of OWFs or to 𝐏 ≠ 𝐍𝐏 \mathbf{P}\neq\mathbf{NP} . In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows from our result is whether the worst-case hardness of proper quantum distribution learning can be derived from 𝐏𝐏 ≠ 𝐁𝐐𝐏 \mathbf{PP}\neq\mathbf{BQP} , because if this is the case and the worst-case to average-case hardness reduction within proper quantum distribution learning is achieved, it would imply OWPuzzs solely from 𝐏𝐏 ≠ 𝐁𝐐𝐏 \mathbf{PP}\neq\mathbf{BQP} ! However, we show that answering the question positively would be extremely difficult: if worst-case hardness of proper quantum distribution learning is 𝐏𝐏 \mathbf{PP} -hard (in a black-box reduction), then 𝐒𝐚𝐦𝐩𝐁𝐐𝐏 ≠ 𝐒𝐚𝐦𝐩𝐁𝐏𝐏 \mathbf{SampBQP}\neq\mathbf{SampBPP} is derived solely from the infiniteness of the polynomial-time hierarchy, which solves a long-standing open problem in the field of quantum advantage. Despite that, we show that 𝐏𝐏 ≠ 𝐁𝐐𝐏 \mathbf{PP}\neq\mathbf{BQP} is equivalent to another standard and well-studied notion of hardness of learning, namely agnostic. We show that 𝐏𝐏 ≠ 𝐁𝐐𝐏 \mathbf{PP}\neq\mathbf{BQP} if and only if agnostic quantum distribution learning with respect to the KL divergence is hard. Finally, as a byproduct, we also obtain an interesting implication for quantum advantage: we show that hardness of agnostic quantum distribution learning with respect to the statistical distance against PPT Σ 3 𝐏 {\rm PPT}^{\Sigma_{3}^{\mathbf{P}}} learner implies 𝐒𝐚𝐦𝐩𝐁𝐐𝐏 ≠ 𝐒𝐚𝐦𝐩𝐁𝐏𝐏 \mathbf{SampBQP}\neq\mathbf{SampBPP} . This provides the first construction of sampling-based quantum advantage from a hardness assumption on a standard and natural framework in learning theory. Moreover, hardness of agnostic learning is of the worst-case type, and therefore this result is the first construction of sampling-based quantum advantage solely from a worst-case hardness assumption. 1 Introduction In classical cryptography, the existence of one-way functions (OWFs) is the minimal assumption [ FOCS:ImpLub89 ] : OWFs are known to be existentially equivalent to a wide range of cryptographic primitives, including pseudorandom generators (PRGs) [ Hill99 ] , pseudorandom functions (PRFs) [ JACM:GolGolMic86 ] , secret-key encryption (SKE) [ GM84 ] , message authentication codes (MACs) [ C:GolGolMic84 ] , digital signatures [ STOC:Rompel90 ] , and commitment schemes [ C:Naor89 ] . Moreover, nearly all cryptographic primitives (including public-key encryption (PKE) and multiparty computation) imply OWFs. In contrast, in quantum cryptography, OWFs would not necessarily be the minimal assumption [ TQC:Kre21 , C:MorYam22 , C:AnaQiaYue22 ] . Several quantum analogues of OWFs, PRGs, and PRFs have been introduced, such as pseudorandom unitaries (PRUs) [ C:JiLiuSon18 ] , pseudorandom state generators (PRSGs) [ C:JiLiuSon18 ] , one-way state generators (OWSGs) [ C:MorYam22 ] , one-way puzzles (OWPuzzs) [ STOC:KhuTom24 ] , and EFI pairs [ ITCS:BCQ23 ] . They could be weaker than OWFs [ TQC:Kre21 , STOC:KQST23 , STOC:LomMaWri24 , myKreQiaTal24 ] , yet they support a variety of important applications including private-key quantum money [ C:JiLiuSon18 ] , SKE [ C:AnaQiaYue22 ] , MACs [ C:AnaQiaYue22 ] , digital signatures [ C:MorYam22 ] , commitments [ C:MorYam22 , C:AnaQiaYue22 , AC:Yan22 ] , and multiparty computation [ C:MorYam22 , C:AnaQiaYue22 , C:BCKM21b , EC:GLSV21 ] . In particular, one-way puzzles (OWPuzzs) introduced by Khurana and Tomer [ STOC:KhuTom24 ] are a natural quantum analogue of OWFs, and one of the most fundamental quantum cryptographic primitives. A OWPuzz is a pair (\mathsf{Samp},\mathsf{Vrfy}) of two algorithms. \mathsf{Samp} is a quantum polynomial-time (QPT) algorithm that, on input the security parameter 1^{n} , outputs two classical bit strings, \mathsf{ans} and \mathsf{puzz} . \mathsf{Vrfy} is an unbounded algorithm that, on input (\mathsf{puzz},\mathsf{ans}^{\prime}) , outputs \top/\bot . Correctness requires that \mathsf{Vrfy} accepts (\mathsf{puzz},\mathsf{ans})\leftarrow\mathsf{Samp}(1^{n}) with high probability. Security requires that no QPT adversary that receives \mathsf{puzz} can output \mathsf{ans}^{\prime} such that (\mathsf{puzz},\mathsf{ans}^{\prime}) is accepted by \mathsf{Vrfy} with high probability. The existence of OWPuzzs implies \mathbf{PP}\neq\mathbf{BQP} [ arXiv:CGGHLP23 ] . On the other hand, in a recent breakthrough paper by Khurana and Tomer [ STOC:KT25 ] , OWPuzzs were constructed from \mathbf{PP}\neq\mathbf{BQP} in conjunction with an additional standard assumption in the field of quantum advantage [ STOC:AarArk11 , BreMonShe16 ] , which we refer to as the ‘‘quantum advantage assumption’’ for simplicity 1 1 1 This is so-called “anti-concentration” and “average-case \mathbf{\#P} -hardness”. For the definition, see 2.10 . . Although the quantum advantage assumption has been intensively investigated for over a decade, and some partial progress has been made [ NatPhys:BFNV19 , Ramis ] , it remains unproven. Moreover, the assumption was a newly introduced one, devised specifically for this purpose, and has not been explored in other areas. As a result, the following question posed by [ STOC:KT25 ] remains one of the most important open problems in quantum cryptography. Can OWPuzzs be constructed solely from \mathbf{PP}\neq\mathbf{BQP} ? This question serves as a quantum analogue of the long-standing open problem in classical cryptography [ DifHel76 ] : Can OWFs be constructed from \mathbf{P}\neq\mathbf{NP} (or \mathbf{NP}\not\subseteq\mathbf{BPP} )? In the classical setting, OWFs and \mathbf{P}\neq\mathbf{NP} (or \mathbf{NP}\not\subseteq\mathbf{BPP} ) have been extensively studied through the lens of learning hardness [ STOC:Valiant84 , ACM:PV88 , FOCS:ImpLev90 , C:BFKL93 , STOC:Regev05 , C:NaoYog15 , FOCS:HirNan23 ] . Impagliazzo and Levin [ FOCS:ImpLev90 ] first constructed OWFs based on a specific type of learning hardness, and subsequent works [ C:BFKL93 , ACM:NR06 , C:NaoYog15 , FOCS:HirNan23 ] extended this approach to more standard and general learning models. In particular, OWFs can be constructed from the average-case hardness of proper PAC learning [ STOC:Valiant84 , C:BFKL93 ] , while \mathbf{NP}\nsubseteq\mathbf{BPP} implies the worst-case hardness of proper PAC learning [ ACM:PV88 ] . These characterizations suggest a promising pathway toward resolving the open problem of constructing OWFs from \mathbf{NP}\not\subseteq\mathbf{BPP} , namely, establishing the worst-case to average-case hardness reduction within proper PAC learning! Learning theory is closely connected to meta-complexity [ Ko91 , FOCS:HirNan21 , CCC:GKLO22 , CCC:GolKab23 ] , which is another compelling direction for addressing the open problem [ FOCS:Hirahara18 , FOCS:LiuPas20 , C:LiuPas21 , IRS21 , C:LiuPas23 , STOC:HILNO23 , STOC:Hirahara23 ] . Therefore, characterizing OWFs with hardness of learning also deepens our understanding of OWFs in terms of meta-complexity. Characterizing cryptographic primitives with hardness of learning has another important implication: it can offer valuable insights into identifying concrete hardness assumptions on which cryptographic primitives can