Pith. sign in

REVIEW 1 cited by

MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Quantum input sampling turns several MicroCrypt primitives into equivalent weak forms, and black-box separations show these forms are strictly weaker than uniform-sampling primitives.

arxiv 2505.14461 v1 pith:Q4C6OSKN submitted 2025-05-20 quant-ph cs.CR

Mohammed Barhoush , Ryo Nishimaki , Takashi Yamakawa This is my paper · ORCID
classification quant-phcs.CR
keywords textsfquantumprimitivessamplinginputlogarithmic-sizeinputsmicrocrypt
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Most cryptographic building blocks, like pseudorandom generators, take a random string as input. This paper asks what happens if that input is chosen by a quantum computer instead of by a coin flip. The authors call the resulting objects pseudorandom generators and pseudorandom states with quantum input sampling. They show that in this relaxed world, several primitives that were thought to be different collapse into one another: a pseudorandom state of logarithmic size, even one that only allows a limited number of copies, can be converted into a pseudorandom generator, and vice versa.

The paper also proves that some of these relaxed primitives are genuinely weaker than their traditional versions. Using oracle constructions, it shows that no 'black-box' method can convert a pseudorandom function whose key is sampled quantumly into an ordinary pseudorandom generator. Similar separations hold for other primitives, including one-way state generators and certain puzzles. These results confirm that the hierarchy inside MicroCrypt, the collection of assumptions weaker than one-way functions, is richer than previously known.

The proofs are reductions: they show how any attack on one primitive would translate into an attack on another, and they build oracle worlds where one primitive exists but the other cannot. No code or experiments are involved; this is a mathematical paper.

Extended reading notes

Core claim

Theorem 9: There does not exist a fully black-box construction of a PRG from a (quantum-query-secure) PRF^qs with inverse access. In addition, the paper claims an equivalence: PRG^qs, bounded-copy SPRS^qs, and SPRS^qs are all equivalent under a certain parameter regime (Constructions 3 and 4, Theorems 7 and 8).

Load-bearing premise

The hybrid proofs in the separations rely on the almost-determinism of PRGs and OWSGs to prevent inverse-polynomial errors from accumulating over exponentially many oracle perturbations (Remark 1 and the analogous step in Claim 12). If almost-determinism were weakened or the errors added instead of being absorbed by the modal output, the invariance Lemmas 10 and Claim 12 would fail. This premise is structurally distinct from the claimed separations: it is about the stability of deterministic outputs under oracle changes, not about the existence of the primitives.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The paper defines new primitives (PRG^qs, PRS^qs, PRF^qs, PRP^qs, PRU^qs, BQ-PRU^qs) but these are formal cryptographic definitions with explicit syntax and security games, not unexplained entities invoked to force a result. No independent evidence is required beyond the security definitions themselves.

free parameters (4)
  • PRS^qs state-size constant c = c > 24 (constructions), c > 36 (corollaries)
    The constructions require a sufficiently large constant c to make tomography errors negligible. It is chosen by hand, not fitted to data.
  • bounded-copy parameter q = 500λd^8 = q = 500λd^8 where d = λ^c
    The construction of PRG^qs from BC-SPRS^qs requires this many copies; it sets the required bounded-copy parameter. Introduced ad hoc to make the proof work.
  • expansion factor m > λ^{2c+1} = m > λ^{2c+1}
    Construction of SPRS^qs from PRG^qs needs this expansion to interpret the PRG output as a function on a domain of size λ^c.
  • m in separation proofs = m = 10(rλ/µ)^4 + λ (Theorem 14), m = 10(rλ)^4 + λ (Theorem 11)
    Choice of m makes the birthday-bound collision probabilities and the encoding length 16m^3 work. Chosen by hand.
assumptions (6)
  • standard math BQP ⊆ PSPACE
    Used to break any PRG or OWSG with a PSPACE oracle (Lemma 1 from [13] and final attacks in Theorems 11, 13, 15).
  • standard math Random oracle acts as a quantum-query-secure PRF
    Lemma 2.2 from [33], used in Lemmas 9 and 14 and Claim 10 to show the oracle constructions are secure PRF^qs/⊥-PRGs.
  • standard math Lower bound for unstructured search (Grover optimality)
    Used in Claims 7 and 16 to bound the ability of G to find a distinguishing input among random oracle values.
  • domain assumption Flip-oracle simulation theorem (Theorem 10 from [14])
    Used in Claims 6 and 8 to replace a swap oracle with copies of the state; the simulation error and copy count drive the hybrid argument.
  • domain assumption Tomography guarantees (Lemma 2 from [1], Lemmas 3-4 from [2])
    Used in Construction 3 and Lemma 7 to extract classical strings from pseudorandom states and to define the good set G_λ.
  • domain assumption Domain extension for PRFs (Lemma 14 from [18])
    Used in Appendix A to build bounded-query PRF^qs and then BQ-PRU^qs from polynomial-domain PRF^qs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations." pith.science (2026). https://pith.science/paper/Q4C6OSKN

@misc{pith2026250514461,
  author       = {Pith},
  title        = {Pith review of: MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q4C6OSKN}},
  note         = {Machine review of arXiv:2505.14461}
}
abstract

We investigate two natural relaxations of quantum cryptographic primitives. The first involves quantum input sampling, where inputs are generated by a quantum algorithm rather than sampled uniformly at random. Applying this to pseudorandom generators ($\textsf{PRG}$s) and pseudorandom states ($\textsf{PRS}$s), leads to the notions denoted as $\textsf{PRG}^{qs}$ and $\textsf{PRS}^{qs}$, respectively. The second relaxation, $\bot$-pseudodeterminism, relaxes the determinism requirement by allowing the output to be a special symbol $\bot$ on an inverse-polynomial fraction of inputs. We demonstrate an equivalence between bounded-query logarithmic-size $\textsf{PRS}^{qs}$, logarithmic-size $\textsf{PRS}^{qs}$, and $\textsf{PRG}^{qs}$. Moreover, we establish that $\textsf{PRG}^{qs}$ can be constructed from $\bot$-$\textsf{PRG}$s, which in turn were built from logarithmic-size $\textsf{PRS}$. Interestingly, these relations remain unknown in the uniform key setting. To further justify these relaxed models, we present black-box separations. Our results suggest that $\bot$-pseudodeterministic primitives may be weaker than their deterministic counterparts, and that primitives based on quantum input sampling may be inherently weaker than those using uniform sampling. Together, these results provide numerous new insights into the structure and hierarchy of primitives within MicroCrypt.

Figures

Figures reproduced from arXiv: 2505.14461 by the authors.

Figure 1
Figure 1. The black straight arrows indicate implications that are trivial or from previous works [31, 2, 4]. The black dotted arrow indicates a separation from previous work [25]. The blue straight arrows are implications from this work. The red dotted arrow is a separation under inverse access from this work. The orange dotted arrows are separations under CPTP access from this work. 8 [PITH_FULL_IMAGE:figures/full_fig_p008… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Provable learning separation for predicting time-evolution of quantum many-body systems

    quant-ph 2026-07 accept novelty 6.0 of 10

    A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.

Reference graph

Works this paper leans on

47 extracted references · 41 canonical work pages · cited by 1 Pith paper

  1. [1]

    Pseu- dorandom (Function-Like) Quantum State Generators: New Definitions and Applications

    Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. “Pseu- dorandom (Function-Like) Quantum State Generators: New Definitions and Applications”. In: Theory of Cryptography: 20th International Con- ference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I . Springer. 2022, pp. 237–265

    work page 2022

  2. [2]

    Pseudorandom Strings from Pseudorandom Quantum States

    Prabhanjan Ananth, Yao-Ting Lin, and Henry Yuen. “Pseudorandom Strings from Pseudorandom Quantum States”. In:arXiv preprint arXiv:2306.05613 (2023)

    work page Pith review arXiv 2023

  3. [3]

    Cryptography from pseudorandom quantum states

    Prabhanjan Ananth, Luowen Qian, and Henry Yuen. “Cryptography from pseudorandom quantum states”. In: Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I. Springer. 2022, pp. 208–236

    work page 2022

  4. [4]

    Signatures From Pseudorandom States via $\bot$-PRFs

    Mohammed Barhoush, Amit Behera, Lior Ozer, Louis Salvail, and Or Sat- tath. Signatures From Pseudorandom States via ⊥-PRFs. 2024. arXiv: 2311.00847 [cs.CR]. url: https://arxiv.org/abs/2311.00847

    work page Pith review arXiv 2024

  5. [5]

    Secure Quantum Computation with Classical Communi- cation

    James Bartusek. Secure Quantum Computation with Classical Communi- cation. Cryptology ePrint Archive, Paper 2021/964. 2021. url: https : //eprint.iacr.org/2021/964

    work page 2021

  6. [6]

    Quantum state obfuscation from classical oracles

    James Bartusek, Zvika Brakerski, and Vinod Vaikuntanathan. “Quantum state obfuscation from classical oracles”. In:Proceedings of the 56th Annual ACM Symposium on Theory of Computing . 2024, pp. 1009–1017. 54

    work page 2024

  7. [7]

    Obfuscation of pseudo-deterministic quantum circuits

    James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. “Obfuscation of pseudo-deterministic quantum circuits”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 1567– 1578

    work page 2023

  8. [8]

    Pseudo- randomness with proof of destruction and applications

    Amit Behera, Zvika Brakerski, Or Sattath, and Omri Shmueli. “Pseudo- randomness with proof of destruction and applications”. In: Cryptology ePrint Archive (2023)

    work page 2023

Show all 47 references
  1. [9]

    A new world in the depths of microcrypt: Separat- ing OWSGs and quantum money from QEFID

    Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. “A new world in the depths of microcrypt: Separat- ing OWSGs and quantum money from QEFID”. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques . Sprin...

    2025

  2. [10]

    Strengths and weaknesses of quantum computing

    Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. “Strengths and weaknesses of quantum computing”. In: SIAM journal on Computing 26.5 (1997), pp. 1510–1523

    1997

  3. [11]

    Oracle separation be- tween quantum commitments and quantum one-wayness

    John Bostanci, Boyang Chen, and Barak Nehoran. “Oracle separation be- tween quantum commitments and quantum one-wayness”. In: Annual In- ternational Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2025, pp. 3–22

    2025

  4. [12]

    Scalable pseudorandom quantum states

    Zvika Brakerski and Omri Shmueli. “Scalable pseudorandom quantum states”. In: Annual International Cryptology Conference . Springer. 2020, pp. 417–440

    2020

  5. [13]

    On the computational hardness of quantum one-wayness

    Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, and An- gelos Pelecanos. “On the computational hardness of quantum one-wayness”. In: arXiv preprint arXiv:2312.08363 (2023)

    2023 arXiv

  6. [14]

    The power of a single Haar random state: constructing and separating quantum pseudorandom- ness

    Boyang Chen, Andrea Coladangelo, and Or Sattath. “The power of a single Haar random state: constructing and separating quantum pseudorandom- ness”. In: arXiv preprint arXiv:2404.03295 (2024)

    2024 arXiv

  7. [15]

    On central primitives for quantum cryptography with classical communication

    Kai-Min Chung, Eli Goldin, and Matthew Gray. “On central primitives for quantum cryptography with classical communication”. In: Annual In- ternational Cryptology Conference. Springer. 2024, pp. 215–248

    2024

  8. [16]

    On black-box separations of quantum digital signatures from pseudorandom states

    Andrea Coladangelo and Saachi Mutreja. “On black-box separations of quantum digital signatures from pseudorandom states”. In: arXiv preprint arXiv:2402.08194 (2024)

    2024 arXiv

  9. [17]

    Security amplification for interactive cryptographic primitives

    Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Ka- banets. “Security amplification for interactive cryptographic primitives”. In: Theory of Cryptography: 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings...

    2009

  10. [18]

    A combinatorial ap- proach to quantum random functions

    Nico D¨ ottling, Giulio Malavolta, and Sihang Pu. “A combinatorial ap- proach to quantum random functions”. In:Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, Decem...

    2020

  11. [19]

    Quantum vs classical proofs and sub- set verification

    Bill Fefferman and Shelby Kimmel. “Quantum vs classical proofs and sub- set verification”. In: arXiv preprint arXiv:1510.06750 (2015)

    2015 arXiv

  12. [20]

    CountCrypt: Quantum Cryptography between QCMA and PP

    Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. “CountCrypt: Quantum Cryptography between QCMA and PP”. In:arXiv preprint arXiv:2410.14792 (2024)

    2024

  13. [21]

    How to construct random functions

    Oded Goldreich, Shafi Goldwasser, and Silvio Micali. “How to construct random functions”. In: J. ACM 33.4 (1986), pp. 792–807. doi: 10.1145/ 6490.6503. url: https://doi.org/10.1145/6490.6503

    1986

  14. [22]

    Limits on the provable conse- quences of one-way permutations

    Russell Impagliazzo and Steven Rudich. “Limits on the provable conse- quences of one-way permutations”. In: Proceedings of the twenty-first an- nual ACM symposium on Theory of computing . 1989, pp. 44–61

    1989

  15. [23]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. “Pseudorandom quantum states”. In: Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III 38. Springer. 2018, pp. 126–152

    2018

  16. [24]

    Commitments from quantum one- wayness

    Dakshita Khurana and Kabir Tomer. “Commitments from quantum one- wayness”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing . 2024, pp. 968–978

    2024

  17. [25]

    Quantum Pseudorandomness and Classical Com- plexity

    William Kretschmer. “Quantum Pseudorandomness and Classical Com- plexity”. In: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography. 2021

    2021

  18. [26]

    Quantum-Computable One-Way Functions without One-Way Functions

    William Kretschmer, Luowen Qian, and Avishay Tal. “Quantum-Computable One-Way Functions without One-Way Functions”. In:arXiv preprint arXiv:2411.02554 (2024)

    2024

  19. [27]

    How to construct random unitaries

    Fermi Ma and Hsin-Yuan Huang. “How to construct random unitaries”. In: arXiv preprint arXiv:2410.10116 (2024)

    2024 arXiv

  20. [28]

    A note on black-box separations for indistinguishability ob- fuscation

    Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji, Rafael Pass, et al. “A note on black-box separations for indistinguishability ob- fuscation”. In: Cryptology ePrint Archive (2016)

    2016

  21. [29]

    Quantum Unpredictability

    Tomoyuki Morimae, Shogo Yamada, and Takashi Yamakawa. Quantum Unpredictability. Cryptology ePrint Archive, Paper 2024/701. 2024. url: https://eprint.iacr.org/2024/701

    2024

  22. [30]

    One-wayness in quantum cryptography

    Tomoyuki Morimae and Takashi Yamakawa. “One-wayness in quantum cryptography”. In: arXiv preprint arXiv:2210.03394 (2022)

    2022 arXiv

  23. [31]

    Quantum commitments and signatures without one-way functions

    Tomoyuki Morimae and Takashi Yamakawa. “Quantum commitments and signatures without one-way functions”. In:Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I. Springer...

    2022

  24. [32]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quan- tum information. New York, NY, USA: Cambridge University Press, 2000. isbn: 0-521-63503-9. doi: 10.1017/CBO9780511976667

    doi

  25. [33]

    Tightly-secure key-encapsulation mechanism in the quantum random oracle model

    Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. “Tightly-secure key-encapsulation mechanism in the quantum random oracle model”. In: Advances in Cryptology–EUROCRYPT 2018: 37th Annual International 56 Conference on the Theory and Applications of Cryptographic Techniques, ...

    2018

  26. [34]

    Computationally binding quantum commitments

    Dominique Unruh. “Computationally binding quantum commitments”. In: Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35 . Springer. 2016...

    2016

  27. [35]

    Quantum proofs of knowledge

    Dominique Unruh. “Quantum proofs of knowledge”. In: Annual interna- tional conference on the theory and applications of cryptographic tech- niques. Springer. 2012, pp. 135–152

    2012

  28. [36]

    Grover’s quantum searching algorithm is optimal

    Christof Zalka. “Grover’s quantum searching algorithm is optimal”. In: Physical Review A 60.4 (1999), p. 2746

    1999

  29. [37]

    A note on quantum-secure PRPs

    Mark Zhandry. “A note on quantum-secure PRPs”. In: arXiv preprint arXiv:1611.05564 (2016)

    2016 arXiv

  30. [38]

    How to construct quantum random functions

    Mark Zhandry. “How to construct quantum random functions”. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE. 2012, pp. 679–687

    2012

  31. [39]

    Schr¨ odinger’s pirate: How to trace a quantum decoder

    Mark Zhandry. “Schr¨ odinger’s pirate: How to trace a quantum decoder”. In: Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part III 18. Springer. 2020, pp. 61–91. A BQ-PRUqs from PRGqs In this section, we sh...

    2020

  32. [40]

    QSamp(1λ) : Outputs a string k ∈ {0, 1}m

  33. [41]

    Fk(x): Takes a key k ∈ {0, 1}m and an input x ∈ {0, 1}n and outputs a string y ∈ {0, 1}n

  34. [42]

    F −1 k (y): Takes a key k ∈ {0, 1}m and an input y ∈ {0, 1}n and outputs a string x ∈ {0, 1}n

  35. [43]

    57 and Pr k←QSamp(1λ) F −1 k (y) = π−1 k (y) ≥ 1 − negl(λ)

    ( Inverse Relation) For every k ∈ {0, 1}m, there exists a permutation πk over {0, 1}n such that for all x, y∈ {0, 1}n, the following conditions are satisfied: Pr k←QSamp(1λ) [Fk(x) = πk(x)] ≥ 1 − negl(λ). 57 and Pr k←QSamp(1λ) F −1 k (y) = π−1 k (y) ≥ 1 − negl(λ)

  36. [44]

    where Πn is the set of permutations on {0, 1}n

    ( Security) For any QPT distinguisher A: Pr k←QSamp(1λ) h AFk,F −1 k (1λ) = 1 i − Pr O←Πn h AO,O−1 (1λ) = 1 i ≤ negl(λ). where Πn is the set of permutations on {0, 1}n. We say a PRPqs is quantum- query-secure if the above holds even if A is given quantum-query-access. Furtherm...

  37. [45]

    QSamp(1λ): Outputs a m-bit key k

  38. [46]

    Uk: Quantum channel that takes an m-bit key k and acts on n-qubit states

  39. [47]

    where µ denotes the Haar measure on the unitary group U (Cn)

    For any QPT adversary A, Pr k←QSamp(1λ) AUk (1λ) = 1 − Pr U ←µ AU (1λ) = 1 ≤ negl(λ). where µ denotes the Haar measure on the unitary group U (Cn). If A is restricted to only q = q(λ) queries to the unitary, then this is denoted as (q, m, n)-BQ-PRUqs. Note that our definition ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.