On the Limits of Stretching Quantum Pseudorandomness

Andrea Coladangelo; Boyang Chen; Justin Tysdal; Nikos Skoumios; Yao-Ting Lin; Yiming Wang

arxiv: 2606.24736 · v1 · pith:ZBB657VE · submitted 2026-06-23 · quant-ph · cs.CR

On the Limits of Stretching Quantum Pseudorandomness

Boyang Chen , Andrea Coladangelo , Yao-Ting Lin , Nikos Skoumios , Justin Tysdal , Yiming Wang This is my paper

Reviewed by Pith2026-06-26 00:05 UTCgrok-4.3pith:ZBB657VE open to challenge →

classification quant-ph cs.CR

keywords pseudorandom statesblack-box separationCHRS modelquantum oraclesingle-copy securitystretchingquantum cryptography

0 comments

The pith

A quantum oracle shows single-copy pseudorandom states stretch linearly but not superquadratically.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves the first black-box separation between single-copy secure pseudorandom states with different output lengths. It constructs a quantum oracle relative to which states with output length 1.1n exist, but states with output length Omega(n to the 2 plus epsilon) do not, for any positive epsilon. The proof relies on the Common Haar Random State model together with a new bound on how many such resource states any generator can effectively use. This result indicates that quantum pseudorandom states lack the arbitrary polynomial stretching property of their classical counterparts. A reader cares because the separation delineates concrete resource limits on generating pseudorandom quantum states under black-box access.

Core claim

We prove the first black-box separation between single-copy secure pseudorandom states (1PRS) with different output lengths. Specifically, we construct a quantum oracle relative to which 1PRS with output length m(n)=1.1n exist, but 1PRS with output length m(n)=Ω(n^{2+ε}) do not, for any ε>0. Our proof leverages the Common Haar Random State (CHRS) model introduced by Chen, Coladangelo, and Sattath, and introduces a technique to bound the effective number of resource CHRS states utilized by any 1PRS generator in this model.

What carries the argument

The bounding technique on the effective number of Common Haar Random States (CHRS) utilized by any 1PRS generator in the CHRS model.

Load-bearing premise

The technique that bounds the effective number of resource CHRS states utilized by any 1PRS generator is valid and sufficient to rule out super-quadratic stretch while permitting linear stretch.

What would settle it

An explicit 1PRS generator with output length Omega(n^{2+ε}) that uses only a bounded number of CHRS states relative to the same oracle, or a counterexample showing the bounding technique fails to limit resource usage.

Figures

Figures reproduced from arXiv: 2606.24736 by Andrea Coladangelo, Boyang Chen, Justin Tysdal, Nikos Skoumios, Yao-Ting Lin, Yiming Wang.

read the original abstract

Pseudorandom states, introduced by Ji, Liu, and Song (CRYPTO '18), are quantum analogues of classical pseudorandom generators. A fundamental property of classical pseudorandom generators is that their output can be stretched to arbitrary polynomial length. Whether an analogous stretching property holds for quantum pseudorandom states remains unclear. In this work, we prove the first black-box separation between single-copy secure pseudorandom states ($\mathsf{1PRS}$) with different output lengths. Specifically, we construct a quantum oracle relative to which $\mathsf{1PRS}$ with output length $m(n)=1.1n$ exist, but $\mathsf{1PRS}$ with output length $m(n)=\Omega(n^{2+\epsilon})$ do not, for any $\epsilon>0$. Our proof leverages the Common Haar Random State (CHRS) model introduced by Chen, Coladangelo, and Sattath (EUROCRYPT '25), and introduces a technique to bound the effective number of resource CHRS states utilized by any $\mathsf{1PRS}$ generator in this model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Paper gives first black-box separation between linear and super-quadratic stretch for 1PRS in the CHRS model, but the new bounding technique on resource states is the part that needs verification.

read the letter

The core result is a quantum oracle in the CHRS model where 1PRS generators exist for output length 1.1n but not for Omega(n^{2+eps}). They achieve the separation by adding a counting argument that limits how many CHRS states any generator can effectively draw on under single-copy security.

This is new. Prior work on quantum pseudorandom states left the stretching question open, and no earlier paper gave an explicit black-box separation between different output lengths. The oracle construction itself looks explicit and the model is already in the literature.

The paper does a clean job stating the separation and the role of the new bound. If the counting step is solid, the result directly answers whether quantum PRS inherit arbitrary polynomial stretch from classical PRGs.

The soft spot is the bounding technique itself. The stress-test note is on point: the argument must come strictly from the single-copy definition and stay independent of output length. If the count ends up depending on the dimension of the output register or the number of measurement outcomes, the separation between linear and super-quadratic stretch would not hold. The abstract gives no error analysis or derivation, so the claim rests entirely on whether that step is rigorous.

This is for people working on quantum cryptography primitives and oracle separations. A reader who cares about security definitions for pseudorandom states will want to see the details. The paper deserves a serious referee to check the counting argument and the oracle construction in full.

Referee Report

1 major / 0 minor

Summary. The paper claims to prove the first black-box separation between single-copy secure pseudorandom states (1PRS) with different output lengths. It constructs a quantum oracle in the CHRS model relative to which 1PRS exist for output length m(n)=1.1n but do not exist for m(n)=Ω(n^{2+ε}) for any ε>0. The proof relies on a new technique that bounds the effective number of resource CHRS states utilized by any 1PRS generator.

Significance. If the central separation holds, the result is significant because it establishes concrete limits on stretching quantum pseudorandom states, in contrast to the arbitrary polynomial stretching possible for classical PRGs. The explicit oracle construction in the CHRS model and the introduction of a bounding technique for resource states are notable contributions to quantum cryptography.

major comments (1)

[Abstract (bounding technique)] The bounding technique for the effective number of resource CHRS states (described in the abstract) is load-bearing for the separation. It must be shown explicitly that this bound is derived solely from the single-copy security definition and is independent of output length m(n) (e.g., does not scale with the dimension of the output register or number of measurement outcomes); any such dependence would collapse the claimed separation between m(n)=1.1n and Ω(n^{2+ε}).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the importance of explicitly establishing the independence of the bounding technique. We address the comment below.

read point-by-point responses

Referee: [Abstract (bounding technique)] The bounding technique for the effective number of resource CHRS states (described in the abstract) is load-bearing for the separation. It must be shown explicitly that this bound is derived solely from the single-copy security definition and is independent of output length m(n) (e.g., does not scale with the dimension of the output register or number of measurement outcomes); any such dependence would collapse the claimed separation between m(n)=1.1n and Ω(n^{2+ε}).

Authors: We agree that an explicit derivation of independence is necessary for the separation to hold. The bound is obtained directly from the single-copy security definition: any 1PRS generator in the CHRS model can be shown to utilize only a bounded number of resource states because additional CHRS states would allow a single-copy distinguisher to detect statistical deviation from Haar randomness via a simple swap test or fidelity estimation on the single provided copy. This argument relies only on the fact that the distinguisher receives one copy and that the CHRS states are Haar-random; it makes no reference to the dimension of the output register or the number of possible measurement outcomes. Consequently the bound remains O(1) (or polylog in the security parameter) regardless of m(n). We will add a dedicated lemma and a short paragraph immediately after the definition of the bounding technique that isolates this independence argument and states explicitly that the proof nowhere invokes m(n). revision: yes

Circularity Check

0 steps flagged

Minor self-citation to CHRS model; central separation via explicit oracle construction and new bounding technique

full rationale

The paper constructs an explicit quantum oracle in the CHRS model (introduced in prior work by two overlapping authors) to separate 1PRS stretch lengths. The load-bearing step is the novel counting argument bounding effective CHRS states used by any 1PRS generator; this is presented as a new derivation from the single-copy security definition rather than a reduction to fitted inputs, self-definitions, or unverified self-citations. No equations or steps in the provided abstract reduce by construction to the target result. The self-citation is therefore minor and non-load-bearing for the separation claim itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the CHRS model (introduced in prior work) and standard properties of Haar-random states and oracle separations; no free parameters or invented entities are introduced.

axioms (1)

domain assumption Properties of the Common Haar Random State model and black-box oracle separations in quantum information
Invoked to define the oracle relative to which the separation holds.

pith-pipeline@v0.9.1-grok · 5734 in / 1166 out tokens · 16274 ms · 2026-06-26T00:05:13.373381+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 2 canonical work pages

[1]

Cryptography in the common haar state model: Feasibility results and separations

[AGL24] Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin. Cryptography in the common haar state model: Feasibility results and separations. In Elette Boyle and Mohammad Mahmoody, editors,Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part II, volume 15365 ofLecture Notes in Computer Scien...

2024
[2]

Pseudorandom(function- like) quantum state generators: New definitions and applications

4, 7, 8, 17 38 [AGQY22] PrabhanjanAnanth,AdityaGulati,LuowenQian,andHenryYuen. Pseudorandom(function- like) quantum state generators: New definitions and applications. In Eike Kiltz and Vinod Vaikuntanathan,editors,TheoryofCryptography-20thInternationalConference,TCC2022, Chicago,IL,USA,November7-10,2022,Proceedings,PartI,volume13747ofLectureNotes in Comp...

2022
[3]

3 [BBO+25] MohammedBarhoush,AmitBehera,LiorOzer,LouisSalvail,andOrSattath.Signaturesfrom pseudorandomstatesvia⊥-prfs. InGoichiroHanaokaandBo-YinYang,editors,Advancesin Cryptology-ASIACRYPT2025-31stInternationalConferenceontheTheoryandApplication of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings,PartVIII,vo...

2025
[4]

Oracle separation between quantum commitments and quantum one-wayness

3 [BCN25] John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings,...

2025
[5]

On the computational hardness needed for quantum cryptography

4 [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In Yael Tauman Kalai, editor,14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023, volume 251 ofLIPIcs, pages 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für I...

2023
[6]

On limits on theprovableconsequencesofquantumpseudorandomness.CryptologyePrintArchive,2025

3 [BHMV25] Samuel Bouaziz–Ermann, Minki Hhan, Garazi Muguruza, and Quoc-Huy Vu. On limits on theprovableconsequencesofquantumpseudorandomness.CryptologyePrintArchive,2025. 4 [BM24] Samuel Bouaziz–Ermann and Garazi Muguruza. Quantum pseudorandomness cannot be shrunk in a black-box way. Cryptology ePrint Archive, Paper 2024/291,

2025
[7]

A new world in the depths of microcrypt: Separating owsgs and quantum money from QEFID

3 [BMM+25] AmitBehera,GiulioMalavolta,TomoyukiMorimae,TamerMour,andTakashiYamakawa. A new world in the depths of microcrypt: Separating owsgs and quantum money from QEFID. InSergeFehrandPierre-AlainFouque,editors,AdvancesinCryptology-EUROCRYPT2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Sp...

2025
[8]

Universally composable security: A new paradigm for cryptographic protocols

45 [Can01] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14-17, 2001, pages 136–145. IEEE Computer Society,

2001
[9]

A meta-complexity characterization of minimal quantum cryptography

6 [CCC+25] Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li. A meta-complexity characterization of minimal quantum cryptography. arXiv preprint arXiv:2510.07859,

work page arXiv
[10]

Thepowerofasinglehaarrandomstate: Constructing and separating quantum pseudorandomness

3, 4, 6 [CCS25] BoyangChen,AndreaColadangelo,andOrSattath. Thepowerofasinglehaarrandomstate: Constructing and separating quantum pseudorandomness. In Serge Fehr and Pierre-Alain Fouque, editors,Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, ...

2025
[11]

Oncentralprimitivesforquantumcryptogra- phy with classical communication

1, 3, 4, 6, 7, 10, 17, 34, 35, 36, 37, 38 [CGG24] Kai-MinChung,EliGoldin,andMatthewGray. Oncentralprimitivesforquantumcryptogra- phy with classical communication. In Leonid Reyzin and Douglas Stebila, editors,Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Par...

2024
[12]

Cryp- tographic censorship.arXiv preprint arXiv:2402.03425,

14 [EFL+24] Netta Engelhardt, Åsmund Folkestad, Adam Levine, Evita Verheijden, and Lisa Yang. Cryp- tographic censorship.arXiv preprint arXiv:2402.03425,

work page arXiv
[13]

Commitments to quantum states

3 [GJMZ23] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. Commitments to quantum states. In BarnaSahaandRoccoA.Servedio,editors,Proceedingsofthe55thAnnualACMSymposium onTheoryofComputing,STOC2023,Orlando,FL,USA,June20-23,2023,pages1579–1588. ACM,

2023
[14]

4 [GZ25] EliGoldinandMarkZhandry. Translatingbetweenthecommonhaarrandomstatemodeland theunitarymodel.InYaelTaumanKalaiandSenyF.Kamara,editors,AdvancesinCryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II, volume 16001 ofLecture Notes in Computer Science, pages 269–300...

2025
[15]

Pseudorandomquantumstates

45 40 [JLS18] ZhengfengJi,Yi-KaiLiu,andFangSong. Pseudorandomquantumstates. InHovavShacham and Alexandra Boldyreva, editors,Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Pro- ceedings, Part III, volume 10993 ofLecture Notes in Computer Science, pages 126–152. Springer,

2018
[16]

Complementarityandtheunitarityoftheblackholes-matrix

8, 13, 16, 25, 45 [KP23] IsaacHKimandJohnPreskill. Complementarityandtheunitarityoftheblackholes-matrix. Journal of High Energy Physics, 2023(2):1–46,

2023
[17]

Quantum pseudorandomness and classical complexity

3 [Kre21] William Kretschmer. Quantum pseudorandomness and classical complexity. In Min-Hsiu Hsieh, editor,16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, Virtual Conference, July 5-8, 2021, volume 197 ofLIPIcs, pages 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2021
[18]

Commitments from quantum one-wayness

3, 15, 18 [KT24] Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 968–978. ACM,

2024
[19]

Quantum commitments and signatures without one-way functions

4 [MY22] Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors,Advances in Cryp- tology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, SantaBarbara, CA,USA,August15-18, 2022, Proceedings, PartI,volume13507ofLecture Notes in Compute...

2022
[20]

One-wayness in quantum cryptography

3, 13, 30, 32 [MY24] Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In Frédéric Magniez and Alex Bredariol Grilo, editors,19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, Okinawa, Japan, September 9-13, 2024, volume 310 ofLIPIcs, pages 4:1–4:21. Schloss Dagstuhl - Leibniz- Zentrum...

2024
[21]

Quantum event learning and gentle random measure- ments

4 41 [WB24] Adam Bene Watts and John Bostanci. Quantum event learning and gentle random measure- ments. In Venkatesan Guruswami, editor,15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024, volume 287 of LIPIcs, pages 97:1–97:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2024
[22]

General properties of quantum bit commitments (extended abstract)

16 [Yan22] Jun Yan. General properties of quantum bit commitments (extended abstract). In Shweta Agrawal and Dongdai Lin, editors,Advances in Cryptology - ASIACRYPT 2022 - 28th Inter- national Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV, volume 13794 ofLecture No...

2022
[23]

How to model unitary oracles

3 [Zha25] Mark Zhandry. How to model unitary oracles. In Yael Tauman Kalai and Seny F. Kamara, editors,Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II, volume 16001 ofLecture Notes in Computer Science, pages 237–268. Springer,

2025

[1] [1]

Cryptography in the common haar state model: Feasibility results and separations

[AGL24] Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin. Cryptography in the common haar state model: Feasibility results and separations. In Elette Boyle and Mohammad Mahmoody, editors,Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part II, volume 15365 ofLecture Notes in Computer Scien...

2024

[2] [2]

Pseudorandom(function- like) quantum state generators: New definitions and applications

4, 7, 8, 17 38 [AGQY22] PrabhanjanAnanth,AdityaGulati,LuowenQian,andHenryYuen. Pseudorandom(function- like) quantum state generators: New definitions and applications. In Eike Kiltz and Vinod Vaikuntanathan,editors,TheoryofCryptography-20thInternationalConference,TCC2022, Chicago,IL,USA,November7-10,2022,Proceedings,PartI,volume13747ofLectureNotes in Comp...

2022

[3] [3]

3 [BBO+25] MohammedBarhoush,AmitBehera,LiorOzer,LouisSalvail,andOrSattath.Signaturesfrom pseudorandomstatesvia⊥-prfs. InGoichiroHanaokaandBo-YinYang,editors,Advancesin Cryptology-ASIACRYPT2025-31stInternationalConferenceontheTheoryandApplication of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings,PartVIII,vo...

2025

[4] [4]

Oracle separation between quantum commitments and quantum one-wayness

3 [BCN25] John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings,...

2025

[5] [5]

On the computational hardness needed for quantum cryptography

4 [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In Yael Tauman Kalai, editor,14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023, volume 251 ofLIPIcs, pages 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für I...

2023

[6] [6]

On limits on theprovableconsequencesofquantumpseudorandomness.CryptologyePrintArchive,2025

3 [BHMV25] Samuel Bouaziz–Ermann, Minki Hhan, Garazi Muguruza, and Quoc-Huy Vu. On limits on theprovableconsequencesofquantumpseudorandomness.CryptologyePrintArchive,2025. 4 [BM24] Samuel Bouaziz–Ermann and Garazi Muguruza. Quantum pseudorandomness cannot be shrunk in a black-box way. Cryptology ePrint Archive, Paper 2024/291,

2025

[7] [7]

A new world in the depths of microcrypt: Separating owsgs and quantum money from QEFID

3 [BMM+25] AmitBehera,GiulioMalavolta,TomoyukiMorimae,TamerMour,andTakashiYamakawa. A new world in the depths of microcrypt: Separating owsgs and quantum money from QEFID. InSergeFehrandPierre-AlainFouque,editors,AdvancesinCryptology-EUROCRYPT2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Sp...

2025

[8] [8]

Universally composable security: A new paradigm for cryptographic protocols

45 [Can01] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14-17, 2001, pages 136–145. IEEE Computer Society,

2001

[9] [9]

A meta-complexity characterization of minimal quantum cryptography

6 [CCC+25] Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li. A meta-complexity characterization of minimal quantum cryptography. arXiv preprint arXiv:2510.07859,

work page arXiv

[10] [10]

Thepowerofasinglehaarrandomstate: Constructing and separating quantum pseudorandomness

3, 4, 6 [CCS25] BoyangChen,AndreaColadangelo,andOrSattath. Thepowerofasinglehaarrandomstate: Constructing and separating quantum pseudorandomness. In Serge Fehr and Pierre-Alain Fouque, editors,Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, ...

2025

[11] [11]

Oncentralprimitivesforquantumcryptogra- phy with classical communication

1, 3, 4, 6, 7, 10, 17, 34, 35, 36, 37, 38 [CGG24] Kai-MinChung,EliGoldin,andMatthewGray. Oncentralprimitivesforquantumcryptogra- phy with classical communication. In Leonid Reyzin and Douglas Stebila, editors,Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Par...

2024

[12] [12]

Cryp- tographic censorship.arXiv preprint arXiv:2402.03425,

14 [EFL+24] Netta Engelhardt, Åsmund Folkestad, Adam Levine, Evita Verheijden, and Lisa Yang. Cryp- tographic censorship.arXiv preprint arXiv:2402.03425,

work page arXiv

[13] [13]

Commitments to quantum states

3 [GJMZ23] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. Commitments to quantum states. In BarnaSahaandRoccoA.Servedio,editors,Proceedingsofthe55thAnnualACMSymposium onTheoryofComputing,STOC2023,Orlando,FL,USA,June20-23,2023,pages1579–1588. ACM,

2023

[14] [14]

4 [GZ25] EliGoldinandMarkZhandry. Translatingbetweenthecommonhaarrandomstatemodeland theunitarymodel.InYaelTaumanKalaiandSenyF.Kamara,editors,AdvancesinCryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II, volume 16001 ofLecture Notes in Computer Science, pages 269–300...

2025

[15] [15]

Pseudorandomquantumstates

45 40 [JLS18] ZhengfengJi,Yi-KaiLiu,andFangSong. Pseudorandomquantumstates. InHovavShacham and Alexandra Boldyreva, editors,Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Pro- ceedings, Part III, volume 10993 ofLecture Notes in Computer Science, pages 126–152. Springer,

2018

[16] [16]

Complementarityandtheunitarityoftheblackholes-matrix

8, 13, 16, 25, 45 [KP23] IsaacHKimandJohnPreskill. Complementarityandtheunitarityoftheblackholes-matrix. Journal of High Energy Physics, 2023(2):1–46,

2023

[17] [17]

Quantum pseudorandomness and classical complexity

3 [Kre21] William Kretschmer. Quantum pseudorandomness and classical complexity. In Min-Hsiu Hsieh, editor,16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, Virtual Conference, July 5-8, 2021, volume 197 ofLIPIcs, pages 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2021

[18] [18]

Commitments from quantum one-wayness

3, 15, 18 [KT24] Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 968–978. ACM,

2024

[19] [19]

Quantum commitments and signatures without one-way functions

4 [MY22] Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors,Advances in Cryp- tology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, SantaBarbara, CA,USA,August15-18, 2022, Proceedings, PartI,volume13507ofLecture Notes in Compute...

2022

[20] [20]

One-wayness in quantum cryptography

3, 13, 30, 32 [MY24] Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In Frédéric Magniez and Alex Bredariol Grilo, editors,19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, Okinawa, Japan, September 9-13, 2024, volume 310 ofLIPIcs, pages 4:1–4:21. Schloss Dagstuhl - Leibniz- Zentrum...

2024

[21] [21]

Quantum event learning and gentle random measure- ments

4 41 [WB24] Adam Bene Watts and John Bostanci. Quantum event learning and gentle random measure- ments. In Venkatesan Guruswami, editor,15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024, volume 287 of LIPIcs, pages 97:1–97:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2024

[22] [22]

General properties of quantum bit commitments (extended abstract)

16 [Yan22] Jun Yan. General properties of quantum bit commitments (extended abstract). In Shweta Agrawal and Dongdai Lin, editors,Advances in Cryptology - ASIACRYPT 2022 - 28th Inter- national Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV, volume 13794 ofLecture No...

2022

[23] [23]

How to model unitary oracles

3 [Zha25] Mark Zhandry. How to model unitary oracles. In Yael Tauman Kalai and Seny F. Kamara, editors,Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II, volume 16001 ofLecture Notes in Computer Science, pages 237–268. Springer,

2025