PaperlayerView exact revision on arXiv

Source-linked AI summary

Instantiating Microcrypt: Obstacles and opportunities via tailored state certification

Jose Carrasco, Jens Eisert, Soumik Ghosh, Dominik Hangleiter, Nicky Kai Hong Li, Ryan Sweke

arXiv:2609.15842v1quant-phcs.CR

TL;DR

The paper asks whether Hamiltonian phase state assumptions can instantiate Microcrypt even if one-way functions do not exist, a possibility motivated by quantum cryptography under P = NP. It constructs one-way puzzles using tailored state-certification protocols and proves that true HPS assumptions imply one-way functions.

  • Problem

    The central question is whether HPS assumptions can instantiate Microcrypt even if one-way functions do not exist, a possibility motivated by quantum cryptography under P = NP.

    Source: §1 · pp. 3–4

  • Method

    The paper constructs one-way puzzle variants from one-way state generators using tailored measure-first, ask-later state-certification protocols, relating puzzle properties to protocol properties.

    Source: §1 · p. 4

  • Results

    If the HPS assumptions are true, then one-way functions exist, obstructing genuine Microcrypt instantiation.

    Source: §1 · p. 4

  • Takeaways & Limitations

    State-certification protocols with efficient classical post-processing yield efficiently verifiable one-way puzzles, offering a toolbox for their construction.

    Source: §1 · p. 4

    Identifying explicit state ensembles that are plausibly pseudorandom and admit efficient, nonsimulable measure-first, ask-later certification remains open.

    Source: §1.3 · p. 11

Abstract

from arXiv · show

Recent work has introduced the Hamiltonian phase state (HPS) assumptions, which postulate that Hamiltonian phase states can be used to instantiate pseudorandom and one-way state generators. Additionally, it has been conjectured that these assumptions can be true, even if one-way functions do not exist. This is exciting, because if true, then the HPS assumptions provide a route to the instantiation of Microcrypt. In this work we falsify this conjecture, by proving that if the HPS assumptions are true, then one-way functions exist. While this removes the possibility of instantiating genuine Microcrypt cryptography with Hamiltonian phase states, it shows that the HPS assumptions provide novel inherently quantum assumptions for the construction of classical cryptography. Technically we achieve this via a method for the construction of one-way puzzles from one-way state generators and tailored "measure first, ask later" state certification protocols. This generalizes prior constructions of one-way puzzles from one-way state generators via classical shadows and allows us to relate properties of the one-way puzzle to properties of the state certification protocol used in the construction. Specifically, if the state certification protocol admits efficient classical post-processing then one obtains an efficiently verifiable one-way puzzle, and if the state certification protocol can be efficiently classically simulated in a certain sense, then one obtains a classical one-way puzzle, which implies one-way functions. The latter observation allows us to prove that the HPS assumptions imply one-way functions, by exploiting properties of state certification protocols for phase states. The former observation provides a new toolbox for the construction of efficiently verifiable one-way puzzles by exploiting tailored state certification protocols for pseudorandom and one-way state generators.

1 Introduction · 1.1 Our contributions

Search HPS implies an explicit quantum-secure one-way function, ruling out genuine Microcrypt instantiation from HPS. Tailored state certification protocols also offer routes to efficiently verifiable puzzles and simpler one-way functions.

1 Introduction

  • The HPS assumptions [BHH+25] posit Hamiltonian phase-state ensembles for PRSGs and OWSGs, and were proposed as candidates for instantiating Microcrypt without OWFs.The paper asks whether these assumptions can hold in the absence of OWFs and answers no.Source: §1 · p. 4

1.1 Our contributions

  • The contributions are organized around obstacles and opportunities for concrete Microcrypt instantiations.The obstacle is that HPS implies OWFs; the opportunity is to use tailored state certification protocols to construct efficiently verifiable one-way puzzles.Source: §1.1 · p. 4

1.1.1 Obstacles: Hamiltonian phase state assumptions imply one-way functions

  • Search HPS yields an explicit quantum-secure OWF, and Decision HPS does too because it implies Search HPS, blocking genuine Microcrypt instantiation while supplying a quantum assumption for classical cryptography.The result provides an obstacle to instantiating Microcrypt and an opportunity for classical cryptography from inherently quantum assumptions.Source: §1 · p. 4, §1.1.1 · p. 5
  • The construction generalizes the classical-shadow OWP method [KT24]: copy-efficient “measure first, ask later” certification yields OWPs, while classical simulability can yield classical OWPs and hence OWFs [KT24].The authors use existing certification protocols for phase states [HPS25] to establish the efficiency and simulability conditions needed for the Search HPS result.Source: §1 · p. 4, §1.1.1 · pp. 5–6

1.1.2 Opportunities: Efficiently verifiable one-way puzzles via tailored state certification protocols

  • A certifiable OWSG yields an OWP, while an efficiently certifiable OWSG yields an efficiently verifiable OWP; with classical key generation, 1/3-simulability also yields a quantum-secure OWF.Thus, simulability can make the resulting puzzle unsuitable for genuine Microcrypt, even as it enables a classical OWF.Source: §1.1.2 · p. 7
  • A computationally efficient “measure first, ask later” certification protocol with efficient classical post-processing makes the resulting OWP efficiently verifiable.This generalizes the classical-shadow construction to tailored protocols for the OWSG’s output states, offering a potential route to Quantumania candidates.Source: §1 · p. 4, §1.1.2 · p. 7
  • A genuine Microcrypt EV-OWP route requires an OWSG not built from OWFs and an efficient certification protocol that is not 1/3-simulable.The framework therefore offers a potential route to Quantumania only when both conditions hold.Source: §1.1.2 · p. 7

1.1.3 Towards simpler one-way functions from the Search HPS assumption

  • An η-simulable, efficiently certifiable OWSG with classical key generation yields a direct quantum-secure OWF when η is negligible for polynomially bounded key length and copy count.This construction avoids the intermediate distributional-OWF and weak-OWF steps; the existing phase-state protocol [HPS25] meets the stronger conditions used for Search HPS.Source: §1.1.3 · p. 8

1.2 Related work

The related work situates this paper’s new route from tailored state certification to one-way puzzles among Microcrypt constructions, quantum learning assumptions, and recent state-certification protocols. It highlights that HPS assumptions imply one-way functions and identifies certification requirements and protocols relevant to the paper’s constructions.

Microcrypt

  • The work introduces certifiable and efficiently certifiable OWSGs and uses tailored state certification to construct OWP variants, adding a route to efficiently verifiable OWPs [GMM+25].Previous EV-OWP constructions use quantum pseudorandom generators or non-interactive QCCC primitives [CGG24]; this work adds another method to that toolbox.Source: §1.2 · p. 8

Cryptography from (quantum) hardness of learning

  • HPS assumptions [BHH+25], previously considered potentially independent of OWFs, cannot instantiate genuine Microcrypt but do imply OWFs, providing a route to Minicrypt [BHH+25].The paper places HPS alongside learning stabilizers with noise assumptions, which have been used to instantiate Cryptomania [PQS25] [LPQ+26] [KLP+25].Source: §1.2 · p. 9
  • Other quantum learning assumptions support cryptographic constructions: computational no-learning and no-cloning assumptions yield OWSGs, commitments, and signatures [FGS+25], while quantum advantage assumptions yield OWPs.These assumptions differ from HPS in the circuit families and learning tasks considered [FGS+25] [HE23].Source: §1.2 · p. 9

State certification

  • For the paper’s applications, certification must cover candidate OWSG outputs and use “measure first, ask later” protocols with polynomial copy complexity and efficient measurements.Efficiently certifiable OWSGs additionally require computational efficiency, including efficient classical simulation of the oracle model; robustness is unnecessary.Source: §1.2 · pp. 9–10
  • Global Clifford shadows certify all target states with polynomially many efficient measurements and support OWP construction from any OWSG [HKP20] [KT24], but are not computationally efficient for arbitrary states.Efficient shadow variants exist for structured states, including stabilizer and Gaussian states, but their suitability for OWSG construction is unclear [HKP20] [ZRM21] [WHL+23].Source: §1.2 · p. 10
  • For Hamiltonian phase states, the HPS25 protocol is the only discussed protocol that is both “measure first, ask later” and computationally efficient with post-processing; PCK+26 also implicitly gives a protocol meeting the desired criteria.Its measurement and copy complexity and robustness are weaker than newer protocols, but polynomial complexity suffices and robustness is not required.Source: §1.2 · p. 10

1.3 Discussion and open questions

The discussion identifies open questions about finding useful efficiently certifiable state ensembles, relating and refining Quantumania primitives, and assessing what HPS assumptions can support. It also asks whether efficiently certifiable OWSGs can exist without OWFs and how state certification with quantum post-processing changes the constructions available.

Concrete instantiations of efficiently certifiable OWSGs

  • Which explicit state ensembles are plausibly pseudorandom and admit efficient, non-simulable measure-first certification, enabling efficiently verifiable OWPs?The authors especially seek ensembles whose pseudorandomness does not rely on or imply OWFs; Hamiltonian phase states were a prior candidate, and their requirements analysis may help identify others.Source: §1.3 · p. 11

QCCC cryptography via efficiently certifiable OWSGs

  • Can efficiently certifiable OWSGs directly construct QCCC protocols or primitives, including interactive bit commitments [ALY23] and public-key encryption?The discussion asks whether the primitives introduced in the work are useful for QCCC cryptography [CGG24] [KQT25].Source: §1.3 · p. 11

Separations and implications between Quantumania primitives

  • Can efficiently certifiable OWSGs and efficiently verifiable OWPs be separated, and how do certifiable OWSGs relate to other Quantumania primitives?Prior oracle separations show OWPs can exist without OWSGs [BMM+25] [BCN24]; the open questions include relations to quantum-computable OWFs [KQT25], logarithmic-depth output PRSGs, and quantum pseudorandom generators [ALY23].Source: §1.3 · p. 11

Refinements of certifiable primitives

  • Do single-copy or non-adaptive certifiable primitives enable cryptographic protocols unavailable from multi-copy or adaptive versions?The definitions can be constrained in these ways, and such protocols may be harder to construct; learning and testing already exhibit measurement-related separations.Source: §1.3 · p. 11

Evidence for efficiently-certifiable OWSGs without OWFs

  • Can efficiently certifiable OWSGs exist without OWFs, as evidence for Microcrypt primitives suggests they may?An oracle world with P = NP but quantum-computable OWFs, logarithmic-output PRSGs, quantum pseudorandom generators, and EV-OWPs is known [KQT25].Source: §1.3 · p. 11

Classical cryptography from quantum assumptions

  • Can the HPS assumptions support Cryptomania primitives, such as trapdoor OWFs, or other OWSGs whose simulable efficient certification yields OWFs?The paper notes that HPS assumptions imply an explicit OWF and therefore instantiate Minicrypt cryptography.Source: §1.3 · pp. 11–12

Independence and relation of HPS assumptions from classical assumptions

  • How plausible are the HPS assumptions, and how are they related to established classical assumptions such as Learning with Errors?The authors say the assumptions have not been tested and their relation to existing assumptions is largely unclear.Source: §1.3 · p. 12

Quantumania via state certification protocols with quantum post-processing

  • What power do measure-first certification protocols with efficient quantum post-processing provide for quantum-verifiable OWPs and QCCC cryptography?Allowing efficient deterministic quantum verification would make copy-efficient certification protocols with efficient quantum post-processing sufficient; the discussion names one-time digital signatures and interactive quantum bit commitments as examples.Source: §1.3 · p. 12

1.4 A short story on the highs and lows of developing this work · 1.5 Structure of this work · AI Disclosure

The authors describe how a search for tailored phase-state certification led from a proposed HPS-based, efficiently verifiable one-way puzzle to the realization that HPS assumptions imply one-way functions. The paper then outlines its technical structure and discloses how generative AI assisted with review of the proofs.

1.4 A short story on the highs and lows of developing this work

  • The project began with the idea that tailored “measure first, ask later” certification could yield efficiently verifiable one-way puzzles from one-way state generators and address an open question about QCCC signatures [FGS+25].An experimental signature [NLO+26] lacked efficient verifiability because it used standard classical shadows.Source: §1.4 · p. 12
  • Using the phase-state certification protocol from [PCK+26], the authors drafted an HPS-based candidate for an efficiently verifiable one-way puzzle and an experimentally feasible QCCC one-time signature.They initially considered the candidate plausibly independent of one-way functions, describing it as an explicit instantiation of Quantumania.Source: §1.4 · p. 12
  • After learning of the protocol in [HPS25], the authors found that its resulting puzzle sampling algorithm is classically simulable and implies one-way functions, so HPS assumptions imply one-way functions.They withdrew the manuscript before its arXiv announcement; they state that the original construction was not wrong, but its foundational assumption was.Source: §1.4 · p. 12

1.5 Structure of this work

  • Sections 2–4 introduce notation and definitions, formalize state certification protocols, and define certifiable Microcrypt primitives.Section 2 covers notation, existing definitions, and assumptions; Sections 3 and 4 build on these foundations.Source: §1.5 · p. 13
  • Sections 5–8 construct certifiable one-way puzzles and, for simulable certifiable generators, one-way functions; prove Theorem 1.2; and discuss candidate state ensembles.The proof of Theorem 1.2 is in Section 7, following the one-way-function constructions in Section 6.Source: §1.5 · p. 13

AI Disclosure

  • Generative AI was used to produce critical referee reports that identified mathematical issues, and the authors verified the correctness and originality of all content and references.The reports informed proof details in Corollary 2.8, Theorems 5.1, 6.1, and 6.4, and Lemma 7.6.Source: AI Disclosure · p. 13

2 Preliminaries

The preliminaries define the classical and quantum cryptographic primitives, Microcrypt puzzles and state generators, and Hamiltonian phase states used in the paper, and introduce the Search HPS assumption and its associated one-way state generator. They also state that Decision HPS implies Search HPS, so showing that Search HPS implies one-way functions suffices for both assumptions.

2.1 Classical cryptographic primitives

  • OWFs require negligible inversion success, while weak OWFs allow inverse-polynomial failure; weak OWFs imply OWFs, including in the quantum-secure setting [KK07] [RS19].The adversary must return a preimage of the function output.Source: §2.1 · pp. 13–14
  • A classical D-OWF makes sampling a uniform preimage harder than finding one, and D-OWFs imply OWFs.The definition lower-bounds by an inverse polynomial the total-variation distance between the true input-output distribution and an adversary's sampled preimage paired with the output.Source: §2.1 · pp. 14–15
  • Quantum-secure D-OWFs require QPT adversaries to fail at preparing uniform superpositions over preimages and imply quantum-secure OWFs [KK07] [RS19].The definition permits mixed quantum outputs and strengthens the earlier definition in [KK07].Source: §2.1 · pp. 14–15

2.2 Microcrypt primitives

  • For a one-way puzzle with an efficient deterministic classical sampling algorithm, classical sampling implies a quantum-secure distributional one-way function, and such puzzles yield quantum-secure one-way functions.Source: §2.2 · pp. 15–16
  • Pure OWSGs use keyed quantum-state generation and projective verification; prior work constructs puzzles from them via classical shadows, which this work generalizes to tailored state-certification protocols [MY22; KT24].The generalization allows arbitrary “measure first, ask later” protocols in place of classical shadows.Source: §2.2 · pp. 16–17
  • Standard PRSGs have stretch n(λ) = ω(log λ), yield OWSGs and puzzles, and are the regime this work targets for efficiently verifiable puzzles.PRSG security here is multi-copy; the preliminaries distinguish standard, logarithmic-length, and sublogarithmic stretch regimes.Source: §2.2 · pp. 17–18

2.3 Hamiltonian phase states and Microcrypt

  • Hamiltonian phase states are diagonal-unitary phase states; the Decision HPS assumption postulates hardness against QPT tests on polynomially many copies and directly yields a PRSG construction [BHH+25].The stated parameter regime takes m(n) polynomial and q(n) = 2^O(poly(n)).Source: §2.3 · pp. 18–19
  • The Search HPS assumption immediately yields an OWSG that samples a key from the specified distribution and generates its corresponding Hamiltonian phase state.The assumption uses parameter functions q(n) and m(n) and a classically efficiently sampleable key distribution.Source: §2.3 · pp. 19–20
  • Decision HPS implies Search HPS, which is the weaker assumption and the focus for proving that HPS assumptions imply one-way functions.The passage says this implication immediately extends the conclusion to Decision HPS.Source: §2.3 · p. 20

3 State certification

The section defines “measure first, ask later” state certification: measurements are independent of the target state, while classical post-processing may depend on it. It extends the definition from one target to a finite set and distinguishes copy efficiency, computational efficiency, and simulability.

State certification

  • A target-independent measurement followed by target-dependent classical post-processing accepts the exact target and rejects states below the fidelity threshold, each with error at most δ.The rejection condition is |⟨ψ|φ⟩|² < 1 − ε.Source: §3 · p. 21
  • For a finite target set, one measurement outcome can support certification of each keyed state, while the verifier rejects keys outside the set.Copy efficiency requires t = poly(n, ε⁻¹, log δ⁻¹, log |K|).Source: §3 · pp. 21–22

Efficiency notions

  • Copy efficiency plus efficient verification defines computational efficiency; verification may alternatively be efficient given classical oracle access to the target state.For a set of states, the oracle is queried on a key and an input to the corresponding state oracle.Source: §3 · p. 22
  • η-simulability requires a classical PPT sampler to approximate measurement-outcome distributions, a property used to obtain one-way functions from constructed one-way puzzles.The set-valued sampler takes the key, n, and t as inputs.Source: §3 · p. 22

Remarks

  • Global Clifford shadows give copy-efficient certification for any state set, but may lack meaningful efficiency or simulability; single-qubit non-adaptive certification of almost all states is known with an amplitude oracle [HPS25].The framework can also be refined by restricting the measurement algorithm to be single-copy or non-adaptive.Source: §3 · p. 22

Relevant parameter ranges

  • With ε = 1/8, δ = 2⁻ⁿ, and |K| = 2^O(poly(n)), copy efficiency yields polynomially many copies and efficient verification runs in polynomial time.These parameter ranges are used in the cryptographic setting described in the section.Source: §3 · p. 22

4 Certifiable Microcrypt primitives

Section 4 defines certifiable OWSG and PRSG variants by pairing generators with “measure first, ask later” state certification protocols. The protocol’s efficiency and simulability determine which cryptographic primitives these variants can construct.

4 Certifiable Microcrypt primitives

  • A C-OWSG or C-PRSG pairs a generator with a “measure first, ask later” protocol; copy efficiency defines certifiability, while efficiency and η-simulability define stronger variants.η-simulable variants require copy efficiency and η-simulability; efficiently certifiable variants require a computationally efficient protocol.Source: §4 · pp. 22–23
  • The same OWSG can yield different cryptographic primitives depending on the properties of its certification protocol, so the certifiable variants are distinct primitives.The variants’ uses include OWPs, EV-OWPs, and OWFs.Source: §4 · p. 23
  • Certifiable OWSGs yield OWPs, efficiently certifiable OWSGs yield EV-OWPs, 1/3-simulable certifiable OWSGs yield OWFs via distributional OWFs, and η-simulable efficient ones yield OWFs directly.For direct OWF construction, η(|k|, n, t) must be negligible in λ when |k|, n, and t are all O(poly(λ)).Source: §4 · p. 23
  • Global Clifford shadows provide copy-efficient certification for any state set, making any OWSG certifiable and enabling an OWP construction [KT24].The paper identifies this as the method used by Khurana and Tomer [KT24].Source: §4 · p. 23
  • Restricted certification protocols can define single-copy or non-adaptive certifiable variants, which may enable more powerful cryptographic protocols, though this is conjectured.The text observes that imposing more restrictions on certification protocols makes the primitives harder to construct.Source: §4 · p. 23
  • A standard PRSG with stretch ω(log λ) transfers certifiability, efficient certifiability, and η-simulability to an OWSG using the standard verification algorithm [CGG+25].The transfer also holds for η-simulable efficiently certifiable PRSGs.Source: §4 · pp. 23–24

5 One-way puzzles from certifiable one-way state generators

The section constructs one-way puzzles (OWPs) from certifiable one-way state generators (OWSGs) using tailored state-certification protocols. The resulting puzzle can inherit properties of the protocol, including efficient verifiability when the protocol is efficiently certifiable.

5 One-way puzzles from certifiable one-way state generators

  • Any copy-efficient “measure first, ask later” certification protocol for a certifiable OWSG’s output states yields an OWP, generalizing Khurana and Tomer’s global-Clifford-shadow construction [KT24].The OWP can inherit protocol properties such as computational efficiency or η-simulability, enabling tailored variants beyond those obtained using global Clifford shadows.Source: §5 · p. 24
  • The certification test accepts |ψ⟩ when it equals |ϕ_k⟩ and rejects it when squared overlap is below 7/8, with probability greater than 1 − 2^-λ.Source: §5 · p. 25
  • An efficiently certifiable OWSG yields an efficiently verifiable OWP.The construction samples copies of the OWSG output state and uses the certification protocol’s verifier to check the puzzle solution.Source: §5 · pp. 24, 26

6 One-way functions from simulable certifiable one-way state generators

The section derives quantum-secure one-way functions from simulable certifiable one-way state generators, first through a distributional one-way function and then through a direct construction under stronger simulability. It also shows how efficient verifiability enables the direct construction from a suitably accurate classical puzzle sampler.

6.1 OWFs from simulable certifiable OWSGs via distributional OWFs

  • A 1/3-simulable certifiable OWSG with classical PPT KeyGen yields a quantum-secure OWF by classically sampling its OWP and compiling the resulting distributional OWF.The construction uses the sampled puzzle to obtain a quantum-secure distributional OWF, then applies a further construction to obtain an OWF.Source: §6.1 · p. 27

6.2 Direct OWF construction via efficient verifiability

  • A direct reduction can fail because an inverter may return a bad preimage even when it inverts the puzzle string, so the modified function forces good preimages.The construction’s efficiency depends on the underlying OWP being efficiently verifiable.Source: §6.2 · pp. 29–30
  • An efficiently verifiable OWP with an efficient deterministic sampler negligibly close to its puzzle distribution yields a quantum-secure OWF.The theorem’s construction modifies the function so a successful inverter on good inputs must return a good preimage; efficient verification makes the function efficiently computable.Source: §6.2 · p. 30
  • When η(|k|, n(λ), t(...)) is negligible, an η-simulable efficiently certifiable OWSG with classical PPT KeyGen yields a quantum-secure OWF directly from its EV-OWP.The construction obtains a deterministic classical sampler negligibly close in total variation distance to the puzzle sampler, avoiding the intermediate distributional-OWF compilations.Source: §6.2 · p. 32

7 Hamiltonian phase state assumptions imply one-way functions

This section shows that Search HPS implies quantum-secure one-way functions, with Decision HPS also implying them through its constructive implication of Search HPS. The proof uses an efficiently computable, classically simulable phase-state certification protocol, whose analysis also yields a polynomial-time classical sampler for its outcomes.

7 Hamiltonian phase state assumptions imply one-way functions

  • Search HPS implies a quantum-secure one-way function, and Decision HPS implies one as a corollary.The Decision HPS assumption constructively implies Search HPS.Source: §7 · p. 32
  • A classical-key OWSG from Search HPS, combined with a 1/3-simulable copy-efficient certification protocol, suffices for a quantum-secure OWF.The section instead proves a stronger negligible-simulability and computational-efficiency condition, enabling a direct OWF construction rather than one compiled from a distributional OWF.Source: §7 · pp. 32–33

7.1 Computationally efficient certification of phase states

  • Ref. [HPS25]'s “measure first, ask later” protocol is computationally efficient for phase-state sets with efficiently computable phase functions and efficiently decidable membership.The measurement is target-independent; it measures all but one qubit in the Z basis, then measures the remaining qubit in a randomly chosen X, Y, or Z basis.Source: §7.1 · pp. 33, 35

7.2 Classical simulability of phase state certification

  • For phase states with efficiently computable phase functions, Ref. [HPS25]'s certification protocol is η-simulable with negligible η(n) whenever t is polynomial in n.A classical PPT simulator replaces the protocol's measurements; its sampling uses approximate Bernoulli draws because exact sampling is not polynomial-time, with negligible approximation error.Source: §7.2 · pp. 35–37
  • The certification protocol’s negligible-approximate sampler runs in time polynomial in n, |k|, and t.It calls the sampler for one block t times, with block parameter l = n.Source: §7.2 · pp. 38–39

7.3 Proof of Theorem 7.1

  • The Search HPS assumption yields a quantum-secure one-way function through an efficiently certifiable, η-simulable one-way state generator.The proof establishes the required efficiency and negligible simulability error for the phase-state certification protocol, then applies Theorem 6.4.Source: §7.3 · p. 39
  • The alternative state-certification method from [PCK+26] achieves constant copy complexity in n, improving on Theorem 7.3’s O(n²/ε²) scaling, but requires more elaborate target-independent measurements than single-qubit measurements.The all-state single-qubit measurement protocols from [GHO25] are inapplicable here because they require target-state-dependent adaptive measurements.Source: §7.3 · p. 39
  • The proven one-way function is specified explicitly in Appendix E, and its domain depends on the certification protocol’s copy complexity t.This dependence motivates considering alternative certification protocols with constant copy complexity.Source: §7.3 · p. 40

8 Towards concrete instantiations of efficiently verifiable one-way puzzles

The section identifies three conditions for state families to yield genuinely Microcrypt-efficiently verifiable one-way puzzles: PRSG/OWSG generation under an assumption independent of one-way functions, efficient state certification, and a certification protocol that is not efficiently classically simulable. It surveys candidate families against these conditions and reports that no known family satisfies all three.

Conditions for concrete instantiations

  • A state family can yield a genuine Quantumania EV-OWP if it supports PRSG/OWSG generation under an OWF-independent assumption and admits efficient measure-first certification that is not 1/3-simulable.If the protocol is 1/3-simulable, the resulting EV-OWP implies a one-way function.Source: §8 · p. 40
  • Properties 1 and 2 suffice for an EV-OWP, but genuine Microcrypt additionally requires Property 3; whether any state family meets all three remains open.The desired family must be hard enough to learn, structured enough to certify, yet not so structured that its certification protocol is classically simulable.Source: §8 · p. 40

Candidate state families

  • No known candidate family satisfies all three properties; Hamiltonian phase states meet Properties 1 and 2 but fail Property 3, while OWF-based phase states fail OWF-independence.Table 1 summarizes the candidate landscape.Source: §8 · p. 40, Table 1 · p. 41
  • Low-stabilizer-rank states may meet Property 1, admit efficient certification via classical shadows, but their structure enables classical simulation and thus fails Property 3.Whether these states can be efficiently learned from copies remains open (Question 2 in Ref. [AA23]).Source: §8 · p. 41
  • Log-depth random brickwork outputs may meet Property 1 [FGS+25], but no efficient measure-first certification protocol is known, so Property 2 is unmet and Property 3 cannot be assessed.This certification gap is why proposed QCCC digital-signature schemes based on these states lack efficient classical certification [NLO+26].Source: §8 · p. 41
  • Forrelation states yield a single-copy PRSG without implying OWFs relative to an oracle [KQS+23], but single-copy PRSGs are too weak for OWPs; multi-copy PRSGs and certifiability remain a possible route.The multi-copy route assumes a strong conjecture on t-Forrelation states [KQS+23].Source: §8 · p. 41
  • One-dimensional tensor-network states with polynomial bond dimension are efficiently learnable, whereas states on arbitrary graphs may retain enough complexity for PRSG/OWSGs and structure for efficient certification.Source: §8 · p. 41
  • For ordinary OWPs and Countcrypt, copy-efficient certification suffices, but because global Clifford shadows certify every ensemble, tailored protocols add no insight into candidate suitability.Source: §8 · p. 41

A Proof of Corollary 2.8

The proof shows that a successful quantum adversary against a distributional OWF can be used to contradict the security of the OWP built from it, following the strategy of Claim D.1 in.

A Proof of Corollary 2.8

  • The proof first converts a successful quantum adversary for a distributional OWF into the guarantee of a successful classical adversary.It defines a QPT algorithm that applies the adversary to the computational-basis state |y⟩⟨y| and outputs its result.Source: A Proof of Corollary 2.8 · p. 42
  • Using that converted adversary and the deterministic classical sampler SampC, the proof constructs a QPT adversary for the OWP, as in Claim D.1 in.The proof reproduces the earlier construction for convenience.Source: A Proof of Corollary 2.8 · p. 42
  • Correctness of the OWP makes the constructed QPT puzzle adversary succeed for infinitely many λ, contradicting the OWP’s assumed security.The adversary is constructed using the classical sampler SampC and the converted adversary for the distributional OWF.Source: A Proof of Corollary 2.8 · pp. 42–43

B Physical implementation of Hamiltonian phase states

Hamiltonian phase states are physically accessible through simple commuting IQP circuits, making the paper’s obstruction relevant to an experimentally motivated family of states. Their required operations can be implemented across several quantum architectures, while classical simulability of their certification measurements underlies the implication to one-way functions.

Physical implementation

  • Hamiltonian phase states can be prepared with simple commuting IQP circuits, making the obstruction apply to a concrete, experimentally motivated family of quantum states.The appendix discusses how the preparation operations can be realized in common experimental architectures.Source: B Physical implementation of… · p. 43
  • A weight-w Ising phase rotation can be implemented without auxiliary systems using 2(w−1) CNOT gates and one single-qubit Z rotation.A parity-accumulation ladder computes the participating qubits’ parity, applies the Z rotation, then reverses the ladder; connectivity can permit parallelization to reduce depth.Source: B Physical implementation of… · p. 43
  • Rydberg-atom platforms support two-qubit ZZ rotations and, with suitable pulse sequences, three-qubit controlled-phase gates; interaction range and connectivity depend on geometry, blockade radius, and control protocol [SWM10] [JP22].Rydberg-ion systems may facilitate multi-qubit phase operations with short pulse sequences [MLL+08], while superconducting devices compile higher-weight or non-local rotations into native gates with connectivity-dependent overhead [KSB+20].Source: B Physical implementation of… · p. 43
  • The certification protocol uses single-qubit Pauli measurements after computational-basis measurements of the remaining qubits, and its statistics on Hamiltonian phase states are efficiently classically simulable, implying one-way functions.These measurements and single-qubit readout are standard capabilities of the discussed architectures; the protocol’s role in the work is primarily conceptual.Source: B Physical implementation of… · p. 43

C Proof of Theorem 7.3

The proof extends state certification to a family of phase states by combining concentration bounds with a union bound; phase states have relaxation time τ = n.

C Proof of Theorem 7.3

  • Theorem C.1, restating Theorem 6 from [HPS25], says the certification algorithm rejects with probability at least 1 − δ when |⟨ψ|ϕ⟩|² < 1 − ε.The theorem is stated for a target state with relaxation time τ, error ε, and failure probability δ.Source: C Proof of Theorem 7.3 · p. 44
  • The proof tests a gap in state overlap through expected shadow overlap, then bounds the sample complexity needed to concentrate its estimator around that expectation.The overlap cases are |⟨ψ|ϕ⟩|² > 1 − ε/(2τ) and |⟨ψ|ϕ⟩|² < 1 − ε; the estimator threshold is 1 − 3ε/(4τ).Source: C Proof of Theorem 7.3 · pp. 44–45
  • A union bound yields simultaneous certification across all |ϕ_k⟩, with the overlap-dependent test conditions holding with probability at least 1 − δ; for phase states, τ = n.The proof applies the single-state concentration bound to every member of the family.Source: C Proof of Theorem 7.3 · p. 45

D Proof of Lemma 6.3

The proof establishes correctness and security of (Samp′, Ver), using an expectation identity for verification and analyzing QPT adversaries in the security argument.

D Proof of Lemma 6.3

  • The proof addresses both correctness and security of (Samp′, Ver).For security, it considers a QPT adversary that maps s to a candidate k′.Source: D Proof of Lemma 6.3 · p. 46
  • For any function h taking values in [0, 1], the probability that Ver(k, s) = 1 equals the expected value of Ver(k, s) over (k, s) sampled by Samp′(1^λ).The proof uses this identity for both correctness and security.Source: D Proof of Lemma 6.3 · p. 46

E The one-way function obtained from Search HPS

The appendix makes explicit the one-way function implied by Theorem 7.1 under Search HPS, using Theorem 6.2 and an efficiently verifiable one-way puzzle built from an implied OWSG and a state-certification protocol.

E The one-way function obtained from Search HPS

  • The construction combines the Search HPS assumption, its implied OWSG, and an η-simulable efficient state-certification protocol to build an EV-OWP.The protocol certifies the phase states from t copies, and the EV-OWP is constructed using Construction 5.2.Source: E The one-way function obtained from… · p. 46
  • To define the OWF, the construction pulls randomness from the approximate sampler into efficiently computable deterministic functions for the key and certification data.The key function uses a deterministic sampler for χ_q,m,λ, while the certification-data function pulls randomness from the iterative sampler.Source: E The one-way function obtained from… · p. 47
  • Under Search HPS, the OWF implied by Theorem 7.1 is made explicit as Fλ using Theorem 6.2.The construction applies Theorem 6.2 to an efficiently verifiable one-way puzzle.Source: E The one-way function obtained from… · pp. 46, 48
  • The OWF’s domain depends on the certification protocol’s copy complexity, and improved copy complexity can reduce the output-string length.The post-processing function of the state-certification protocol is efficiently computable.Source: E The one-way function obtained from… · p. 48

Related papers

Loading 2609.15842v1…