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 remain true without one-way functions and answers negatively. It develops state-certification-based constructions for one-way puzzles, showing that HPS assumptions imply quantum-secure one-way functions while tailored certification can support efficiently verifiable puzzles.

  • Problem

    It was unknown whether Hamiltonian phase state assumptions could hold when one-way functions do not exist, a condition required for genuine Microcrypt instantiation.

  • Method

    The paper constructs one-way puzzle variants from one-way state generators using tailored “measure first, ask later” state-certification protocols.

  • Results

    If the Search HPS assumption holds, one can explicitly construct a quantum-secure one-way function; efficient classical post-processing also yields efficiently verifiable one-way puzzles.

  • Takeaways & Limitations

    HPS assumptions obstruct genuine Microcrypt cryptography but provide inherently quantum assumptions for classical cryptography, while tailored certification offers a route to Quantumania.

  • Takeaways & Limitations

    The paper leaves open whether explicit pseudorandom state ensembles can admit efficient, non-simulable “measure first, ask later” certification protocols.

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

The paper falsifies the conjecture that Hamiltonian phase state assumptions can hold without one-way functions, while developing state-certification tools for one-way puzzles and efficiently verifiable variants.

  • 1 Introduction: The paper constructs one-way puzzle variants from one-way state generators and copy-efficient “measure first, ask later” state-certification protocols, generalizing classical-shadow constructions.The protocol measures copies first and later uses classical post-processing to decide whether a state matches a target state.
  • Opportunities: Efficiently verifiable one-way puzzles via tailored state certification protocols: Efficient classical post-processing of the certification protocol yields an efficiently verifiable one-way puzzle, providing a potential route toward Quantumania instantiations.The approach permits certification protocols tailored to the state ensemble defining the one-way state generator.
  • 1 Introduction: The work frames its contributions as both an obstacle to concrete Microcrypt instantiation and an opportunity for classical cryptography under inherently quantum assumptions.It also identifies tailored state certification as a toolbox for finding explicit efficiently verifiable one-way puzzles.
  • Obstacles: Hamiltonian phase state assumptions imply one-way functions: If the Search HPS assumption holds, one can explicitly construct a quantum-secure one-way function, so HPS assumptions cannot instantiate genuine Microcrypt cryptography.Because Decision HPS implies Search HPS, the same conclusion applies to Decision HPS; these assumptions instead support classical cryptography.
  • 1 Introduction: Certifiable one-way state generators yield one-way puzzles, while efficiently certifiable generators yield efficiently verifiable puzzles and simulable certifiable generators yield one-way functions.The latter route proceeds through distributional and weak one-way functions unless the stronger direct conditions of Theorem 1.7 apply.
  • Towards simpler one-way functions from the Search HPS assumption: A sufficiently simulable, efficiently certifiable one-way state generator with classical key generation directly yields a quantum-secure one-way function without passing through a distributional one-way function.The direct construction applies when η(|k|, n, t) is negligible for polynomially bounded |k| and t.

1.2 Related work

This section situates the work within Microcrypt, quantum learning assumptions, and state certification, emphasizing tailored certification as a route to cryptographic constructions.

  • The work introduces certifiable and efficiently certifiable OWSGs and uses tailored state certification protocols to construct OWP variants.
  • The HPS assumptions are framed as quantum hardness-of-learning assumptions, but this work shows they cannot instantiate genuine Microcrypt primitives and instead suffice for OWFs.
  • State certification protocols are central because they can translate progress in quantum state certification into candidate Microcrypt primitives.
  • “Measure first, ask later” protocols use target-independent measurements followed by target-dependent classical post-processing, with polynomial copy and efficient measurement complexity required here.
  • Classical shadows provide the paradigmatic construction, but their computational efficiency is unclear for state ensembles suitable for OWSGs.
  • For Hamiltonian phase states, the HPS25 protocol is the only identified protocol combining “measure first, ask later” structure with computationally efficient post-processing.

1.3 Discussion and open questions

The discussion identifies open problems around efficient certification, QCCC cryptography, primitive separations, restricted certification models, and evidence for Microcrypt without OWFs.

  • Concrete instantiations of efficiently certifiable OWSGs: A central open question is whether explicit state ensembles can be pseudorandom and efficiently certifiable without their certification also being classically simulable.
  • QCCC cryptography via efficiently certifiable OWSGs: Future work asks whether efficiently certifiable OWSGs directly yield QCCC bit commitments, public-key encryption, or other QCCC protocols.
  • Separations and implications between Quantumania primitives: It remains open whether Quantumania contains subworlds and whether efficiently certifiable OWSGs separate black-box from efficiently verifiable OWPs.
  • Refinements of certifiable primitives: Single-copy and non-adaptive certification variants may be more powerful than unconstrained multi-copy and adaptive versions, motivating cryptographic separation questions.
  • Evidence for efficiently-certifiable OWSGs without OWFs: The paper asks whether efficiently certifiable OWSGs can exist when P = NP and OWFs do not exist, paralleling evidence for other Microcrypt primitives.
  • Independence and relation of HPS assumptions from classical assumptions: Although HPS assumptions provide a novel quantum assumption for classical cryptography, their plausibility and relation to established assumptions remain largely untested.

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

The paper began as a proposed HPS-based efficiently verifiable OWP, but a different certification protocol revealed that the construction implies OWFs and invalidated its Microcrypt premise.

  • The authors initially sought an efficient certification protocol for Hamiltonian phase states to instantiate an efficiently verifiable OWP plausibly independent of OWFs.
  • An early draft claimed an explicit HPS-based EV-OWP and experimentally feasible QCCC signature, presenting it as a Quantumania instantiation.
  • Using the HPS25 certification protocol made the OWP sampler classically simulable, enabling construction of an OWF and disproving the intended foundational assumption.
  • The manuscript was withdrawn before announcement after this issue was identified, and the corrected result became the present work.

2 Preliminaries

The preliminaries define classical and quantum-secure one-way notions, one-way puzzles, and HPS assumptions, then state the implication from weaker primitives to stronger cryptographic objects.

  • OWFs require every efficient adversary’s inversion success to be negligible, while weak OWFs require only an inverse-polynomial failure probability.
  • Distributional OWFs make the harder task of sampling uniformly from function preimages computationally difficult, and they imply OWFs through standard transformations.
  • Quantum-secure distributional OWFs similarly imply quantum-secure OWFs, including through quantum-secure weak OWFs.
  • A one-way puzzle consists of a sampler producing a key and puzzle plus a verifier, with correctness and computational key-recovery security.
  • Classical sampling for a one-way puzzle yields a quantum-secure distributional OWF, and therefore an OWF.
  • The paper generalizes the classical-shadow construction of OWPs from OWSGs to arbitrary “measure first, ask later” certification protocols, focusing on the weaker Search HPS assumption.

3 State certification

The paper introduces “measure first, ask later” certification, where quantum measurements occur before a target state is specified and classical post-processing later decides acceptance. For state sets, the protocol’s efficiency and simulability properties determine how it can support cryptographic constructions.

  • Single-state certification: “Measure first, ask later” certification measures copies without depending on the target state, then uses target-dependent classical post-processing to accept or reject.For a single state, acceptance is required for the exact target and rejection for states with squared overlap below 1 − 𝜖, each with failure probability at most 𝛿.
  • Certification for state sets: For a state set, one measurement outcome string can later be checked against any keyed target state in the set.The verifier rejects keys outside the allowed key set and applies the same acceptance and rejection guarantees to every target state.
  • Efficiency properties: Copy efficiency requires t = poly(n, 𝜖^-1, log 𝛿^-1, log |𝕂|), while computational efficiency requires efficient classical post-processing.In the cryptographic parameter range 𝜖 = 1/8, 𝛿 = 2^-n, and |𝕂| = 2^O(poly(n)), the required copy count is polynomial.
  • Simulability: η-simulability means a classical PPT algorithm can sample measurement outcomes close to those produced by measuring the target state copies.The paper later uses this property to obtain a one-way function from the one-way puzzle constructed through certification.
  • Relation to classical shadows: Global Clifford shadows provide a copy-efficient protocol for arbitrary state sets, but need not be computationally efficient or η-simulable for meaningfully small η.For a fixed known target state, target-dependent projective measurements instead give a trivial constant-copy certification protocol.

4 Certifiable Microcrypt primitives

The paper equips one-way and pseudorandom state generators with state-certification protocols and distinguishes variants by the protocol properties they satisfy. These variants yield different one-way puzzle and one-way function consequences.

  • Cryptographic consequences: Certifiable OWSGs yield OWPs, while efficiently certifiable OWSGs yield efficiently verifiable OWPs.The distinction depends on whether the associated “measure first, ask later” protocol is copy efficient or computationally efficient.
  • Simulable variants: A 1/3-simulable certifiable OWSG with classical key generation yields a quantum-secure OWF through a distributional OWF.The construction first obtains a suitably accurate classical sampler for the associated puzzle, then applies the distributional-OWF compilation.
  • Simulable variants: An η-simulable efficiently certifiable OWSG directly yields an OWF when η is negligible for polynomially bounded key, state, and copy parameters.This direct route avoids the intermediate distributional-OWF construction.
  • Primitive taxonomy: The same OWSG can support different cryptographic primitives depending on the properties of its associated certification protocol.The paper therefore treats the certifiable OWSG variants as distinct primitives rather than merely notational refinements.
  • PRSG-to-OWSG transfer: A standard PRSG with super-logarithmic stretch becomes a certifiable OWSG when equipped with its standard verification algorithm.This implication preserves both certifiability and η-simulability properties of the certification protocol.

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

The paper generalizes the construction of one-way puzzles from one-way state generators by replacing classical shadows with arbitrary copy-efficient “measure first, ask later” certification protocols. Properties of the protocol transfer to the resulting puzzle.

  • Construction: Replacing global Clifford shadows with tailored certification protocols lets the resulting puzzle inherit additional properties of the chosen protocol.This generalizes the earlier shadow-based construction and enables variants unavailable from a fixed universal protocol.
  • Construction: Any certifiable OWSG yields a one-way puzzle through a construction based on certification of its output states.The construction samples a key, generates multiple copies of the corresponding state, measures them, and uses the resulting string with the key for verification.
  • Correctness and efficiency: The construction uses fixed certification parameters 𝜖 = 1/8 and 𝛿 = 2^-𝜆, giving the guarantee that valid target states are accepted with probability exceeding 1 − 2^-𝜆.Polynomial key-space size, state size, and copy complexity ensure that the sampler remains quantum polynomial time.
  • Correctness and security: Puzzle security follows from one-wayness of the underlying state generator together with the certification guarantee and a union-bound argument.An adversary that produces an accepted puzzle under a sufficiently different key would contradict the state-generator security or certification soundness.
  • Efficient verifiability: Efficiently certifiable OWSGs yield efficiently verifiable OWPs.The verifier evaluates the certification post-processing efficiently using the puzzle key and measurement string.

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

The paper converts simulable, certifiable one-way state generators into quantum-secure one-way functions. It first uses approximate classical sampling through distributional one-way functions, then gives a direct route under negligible simulation error and explains the obstacle that motivates the stronger construction.

  • 6.1 OWFs via distributional OWFs: A 1/3-simulable certifiable OWSG with classical PPT key generation yields a quantum-secure OWF via a distributional OWF.The proof replaces quantum measurement with a classical sampler whose output distribution is sufficiently accurate, then applies standard distributional-OWF and OWF transformations.
  • 6.1 OWFs via distributional OWFs: The classical sampler simulates the certification measurement on the generated key and outputs the key together with the simulated measurement string.Copy efficiency and polynomial key, state, and simulator runtimes make this sampler PPT.
  • 6.2 Direct OWF construction: The naive function f_𝜆(r) = s_𝜆(r) need not be a standard OWF because an inverter may output a preimage in the bad set while still satisfying the function-inversion condition.The paper illustrates this problematic adversary and uses efficient verifiability to enforce the needed connection between inversion and puzzle acceptance.
  • 6.2 Direct OWF construction: A classical efficiently verifiable OWP with negligibly inaccurate classical sampling directly yields a quantum-secure OWF.The construction relies on the sampler’s negligible total-variation distance from the original puzzle distribution.
  • 6.2 Direct OWF construction: An η-simulable efficiently certifiable OWSG therefore yields a direct quantum-secure OWF when η is negligible for polynomially bounded parameters.This route avoids first constructing a distributional OWF and then compiling it through a weak OWF.

7 Hamiltonian phase state assumptions imply one-way functions

The section proves that Search and Decision HPS assumptions imply quantum-secure one-way functions. The proof builds one-way puzzles from one-way state generators using efficiently certifiable and classically simulable phase-state protocols.

  • Search HPS implies a quantum-secure one-way function, and Decision HPS implies Search HPS constructively, yielding the same consequence for Decision HPS.
  • The proof starts from an HPS-derived one-way state generator with classical key generation and applies the construction from Theorem 6.1.
  • The required certification protocol measures each copy independently, recording computational-basis outcomes on all but one qubit and a random Pauli measurement on the remaining qubit.
  • Classical post-processing compares a classical-shadow estimate with a target-state single-qubit reconstruction and accepts when their averaged overlap exceeds the tolerance threshold.
  • For efficiently computable phase functions, the protocol is computationally efficient and η-simulable with negligible η when the copy count is polynomial in n.
  • The simulated protocol cannot be sampled exactly in polynomial time because it requires Bernoulli sampling, but efficient approximation is negligibly close and suffices to construct the quantum-secure one-way function directly.

8 Towards concrete instantiations of efficiently verifiable one-way puzzles

The section identifies three requirements for genuine Microcrypt instantiations via efficiently verifiable one-way puzzles and surveys candidate state families. No known family currently satisfies all three requirements.

  • An EV-OWP is genuinely in Microcrypt only when its state family supports PRSG or OWSG construction, efficient certification, and independence from one-way functions.
  • The certification protocol must not be 1/3-simulable, because such simulability makes the resulting EV-OWP imply a one-way function.
  • No known candidate family satisfies all desired properties simultaneously, leaving the existence of such a family as an open question.
  • Hamiltonian phase states satisfy the PRSG or OWSG and efficient-certification properties but fail the independence-from-OWF property.
  • Low stabilizer-rank states plausibly satisfy the first two properties, whereas random-circuit states lack a known computationally efficient measure-first certification protocol.
  • Tensor-network states on arbitrary graphs may combine cryptographic complexity with enough structure for efficient certification, while copy-efficient certification alone adds no discrimination among ensembles.

A Proof of Corollary 2.8

The appendix proves the corollary by converting a quantum adversary against a distributional one-way function into an adversary against the originating one-way puzzle. Correctness then contradicts puzzle security.

  • The proof assumes the candidate function is not a quantum-secure distributional one-way function and uses the resulting quantum algorithm to build a puzzle adversary.
  • The constructed adversary runs the quantum algorithm on a computational-basis encoding of the puzzle input and measures its output to obtain a classical preimage candidate.
  • The induced classical sampling procedure supplies the key and state needed to define the puzzle adversary on its input.
  • Puzzle correctness makes the adversary succeed for infinitely many security parameters, contradicting the assumed one-way-puzzle security.

B Physical implementation of Hamiltonian phase states

Hamiltonian phase states can be prepared with commuting quantum circuits and implemented across several experimental architectures. Their certification protocol uses standard single-qubit Pauli measurements, although its role here is primarily conceptual.

  • Hamiltonian phase states are experimentally accessible because they can be prepared using simple commuting circuits, making the paper’s obstruction relevant to concrete implementations.
  • The states can be generated with IQP circuits whose Ising terms are specified by a binary matrix and implemented as multi-qubit phase rotations.
  • Two-qubit phase rotations fit naturally on Rydberg-atom platforms, while higher-weight rotations can be synthesized from CNOT gates and a single-qubit Z rotation.
  • Rydberg-ion and superconducting-qubit architectures provide alternative routes using dipolar interactions, local entangling gates, and single-qubit rotations, with connectivity constraints requiring compilation.
  • Certification requires computational-basis measurements followed by single-qubit Pauli measurements, but the protocol’s measurement statistics on Hamiltonian phase states are efficiently classically simulable.

C Proof of Theorem 7.3

The proof establishes state-certification correctness by separating overlap discrimination from concentration of the empirical shadow overlap, then applying a simultaneous union bound for phase states.

  • Theorem C.1: Theorem C.1 guarantees rejection when |⟨𝜓|𝜙⟩|2 < 1 −𝜖, with failure probability at most 𝛿.The protocol's output is determined by whether the estimated shadow overlap crosses 1 −(3𝜖/(4𝜏).
  • Proof strategy: The proof compares the expected shadow overlap against thresholds to distinguish high overlap, |⟨𝜓|𝜙⟩|2 > 1 −𝜖/(2𝜏), from low overlap, |⟨𝜓|𝜙⟩|2 < 1 −𝜖.It suffices to test whether 𝔼[𝜔] is below 1 −𝜖/𝜏 or at least 1 −𝜖/(2𝜏).
  • Proof strategy: Concentration bounds ensure the empirical estimate ̂𝜔𝑡 is sufficiently close to 𝔼[𝜔] using a sample-complexity argument.The proof separately bounds concentration and uses the resulting threshold guarantees for the protocol output.
  • Phase states: For phase states, the relaxation time is 𝜏 = 𝑛.This substitution yields the phase-state parameter setting used in the theorem.
  • Simultaneous certification: To certify all target states simultaneously, the proof applies a union bound over |𝕂| states to the concentration inequality.The resulting failure probability is controlled by the bound in Eq. (C.7), after setting ̃𝜖 = 𝜖/(4𝜏).

D Proof of Lemma 6.3

The proof of Lemma 6.3 establishes correctness and security of the sampling-and-verification construction by expressing verifier success as an expectation and analyzing arbitrary QPT adversaries.

  • Proof strategy: Correctness and security are both proved using the identity that verifier acceptance probability equals the corresponding expectation for any function valued in [0,1].This identity is stated as Eq. (D.2).
  • Security: Security is analyzed against any QPT adversary producing a candidate key from the sampled instance.The proof defines a function for the adversary's behavior before deriving the security bound.

E The one-way function obtained from Search HPS

The appendix makes explicit the one-way function implied by Search HPS by derandomizing the sampling procedures and applying the state-certification construction.

  • Construction: The appendix explicitly constructs the OWF that Theorem 7.1 implies under the Search HPS assumption.The construction begins from the Search HPS distribution and the associated one-way state generator.
  • Construction pipeline: The construction instantiates the OWSG, a computationally efficient state-certification protocol, and the resulting efficiently verifiable one-way puzzle.The sampled state-certification transcript consists of t(𝜆) records containing indices, strings, Pauli measurements, and bits.
  • Derandomized sampling: The key-generation randomness is pulled out of Samp_C using an efficiently computable deterministic function k_𝜆.Efficient samplability of χ_{q,m,𝜆} provides the deterministic map from random bits to keys.
  • Derandomized sampling: The sample randomness is similarly extracted from the iterative procedure ̂𝑀_C, producing the deterministic function s_𝜆.For measurement choices Z, X, and Y, s_𝜆 uses the corresponding deterministic functions and the first random bit when M = Z.
  • Final OWF: The resulting OWF is defined over the randomized input domain R(𝜆), with output determined by verification and the post-processing function 𝓕.The domain depends on copy complexity t(𝜆), while improved copy complexity could reduce the output-string length.
Loading 2609.15842v1…