⚛️ quantum physics

Instantiating Microcrypt: Obstacles and opportunities via tailored state certification

This paper refutes the conjecture that Hamiltonian phase state assumptions can exist without one-way functions by proving that these assumptions actually imply the existence of one-way functions, while simultaneously establishing a general framework for constructing efficiently verifiable one-way puzzles through tailored state certification protocols.

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

Published 2026-09-15

📖 6 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet, high-stakes world of cryptography, scientists have long relied on a single, unshakeable pillar: the one-way function. Imagine a lock that is incredibly easy to snap shut but impossible to pick without the key, no matter how much time or computing power you have. This concept underpins almost all modern digital security, from banking to private messaging. For decades, the assumption was that if these locks did not exist, the entire edifice of digital safety would crumble. However, the rise of quantum computing has forced researchers to ask a startling question: could there be a form of security that works even if those traditional locks are impossible to build? This hypothetical realm, where quantum mechanics provides the only defense, has been dubbed "Microcrypt." It is a world where the rules of classical security do not apply, and new, purely quantum tools might be the only things standing between order and chaos.

For a few years, a promising new candidate emerged to build this quantum-only world. It was based on something called Hamiltonian phase states, a specific type of quantum state that researchers believed could be created easily in a lab but would remain a mystery to anyone trying to copy or predict it. The hope was that these states could serve as the foundation for a new kind of cryptography that did not rely on the old, classical one-way functions. If true, this would have been a monumental discovery, proving that a secure digital future could exist even if the fundamental assumptions of classical math were proven false. It promised a genuine revolution, a way to build digital locks that were not just harder to pick, but fundamentally different in nature.

A team of researchers, however, has now carefully dismantled this specific hope. In a rigorous new study, they demonstrated that the very Hamiltonian phase states thought to be the key to this quantum-only world actually cannot exist without the traditional one-way functions they were meant to replace. The team did not merely suggest this; they proved it mathematically. They showed that if these quantum states are as secure as people hoped, then the old, classical one-way functions must also exist. In other words, the new quantum tool they wanted to use to build a house without a foundation actually requires that foundation to be there in the first place. This finding effectively closes the door on using these specific states to create the pure, independent form of quantum cryptography that scientists had been dreaming of.

The path to this conclusion was not a simple rejection but a deep dive into how these quantum states are verified. To use a quantum state as a cryptographic tool, one must be able to check if it is the correct state without destroying it. The researchers developed a new method for this checking process, which they call "measure first, ask later." Imagine taking a photograph of a delicate object before you know what you are looking for, and then using that photo to figure out what the object was. This method allows scientists to verify the identity of a quantum state using measurements that do not depend on knowing the state in advance. The team found that for Hamiltonian phase states, this verification process is so efficient that a classical computer could simulate the entire measurement process with high accuracy.

This ability to simulate the measurement is the critical turning point. In the world of cryptography, if a process can be simulated by a classical computer, it cannot be used to create a truly new, quantum-only security system. The researchers proved that because these states can be simulated, they inevitably lead back to the existence of the traditional one-way functions. It is a bit like finding that a new type of lock you designed actually requires a key that you already knew how to make; the new lock is not a breakthrough in independence, but rather a confirmation of the old system. The study explicitly rules out the possibility that these Hamiltonian phase states can instantiate a version of cryptography that exists independently of one-way functions.

Despite this setback for the specific goal of building a "Microcrypt" world, the research opens up a different, equally valuable avenue. The same mathematical tools used to disprove the independence of these states have revealed a powerful new way to construct one-way functions using inherently quantum assumptions. This means that while Hamiltonian phase states cannot build a world without classical locks, they can provide a novel, quantum-based foundation for building those locks in the first place. The researchers have shown that these states offer a fresh, quantum perspective on how to create the very security primitives that classical cryptography relies on. This shifts the narrative from a failed attempt at independence to a successful discovery of a new, quantum-powered method for strengthening the foundations of digital security.

The study also highlights a broader lesson for the field. The researchers identified a delicate balance required for any new quantum state to serve as a true Microcrypt primitive. It must be complex enough to be hard to learn or copy, yet structured enough to be efficiently verified by a computer. Crucially, the verification process itself must not be something a classical computer can easily mimic. The team found that Hamiltonian phase states, while structured enough to be verified, were too simple to prevent classical simulation. They also looked at other candidates, such as states made from random circuits or specific combinations of simpler quantum states, but found that most either lacked the necessary structure for verification or were too easy to simulate. This leaves the scientific community with a clear, challenging map of what is needed to find a true quantum-only security system, even if the first major candidate has been shown to be part of the old world after all.

Ultimately, this work is a testament to the rigor of theoretical science. It took a promising, exciting idea and subjected it to the most stringent tests possible. The result was not a failure of the idea's potential, but a clarification of its true nature. The researchers have shown that the path to a purely quantum cryptography is narrower and more difficult than previously thought, but they have also provided the tools and the understanding necessary to navigate it. By proving that these specific states imply the existence of classical one-way functions, they have not just closed a door; they have illuminated the landscape, showing exactly where the next breakthroughs must come from and what properties the next candidate must possess to succeed.

Technical Summary: Instantiating Microcrypt: Obstacles and opportunities via tailored state certification

Problem Statement

The paper addresses the fundamental question of whether "Microcrypt" – a cryptographic world where meaningful protocols exist even if one-way functions (OWFs) do not – can be concretely instantiated using Hamiltonian phase state (HPS) assumptions. Recent work [BHH+25] proposed that ensembles of Hamiltonian phase states could serve as pseudorandom state generators (PRSGs) and one-way state generators (OWSGs) under assumptions that might hold even if $P=NP$ (and thus OWFs do not exist). If true, this would provide a concrete foundation for the "Countcrypt" subworld of Microcrypt.

The central problem investigated is whether the HPS assumptions are truly independent of OWFs. Specifically, the authors ask: Can the Hamiltonian phase state assumptions be true if one-way functions do not exist?

Methodology

The authors develop a new theoretical framework connecting state certification protocols to the construction of cryptographic primitives. Their methodology proceeds in three main stages:

Generalization of OWP Construction: They generalize the existing construction of One-Way Puzzles (OWPs) from OWSGs (which previously relied on classical shadows) to any "measure first, ask later" state certification protocol. This protocol type involves performing target-independent measurements on copies of a state and then applying target-dependent classical post-processing to verify the state.
Analysis of Certification Properties: They define specific properties for these certification protocols:
- Copy Efficiency: Polynomial number of copies required.
- Computational Efficiency: Efficient classical post-processing.
- $\eta$ -Simulability: The existence of a classical algorithm that can simulate the measurement outcome distribution with negligible error ( $\eta$ ).
Implication Chains: They establish logical implications based on these properties:
- Certifiable OWSG $\to$ OWP: Any OWSG equipped with a copy-efficient certification protocol yields an OWP.
- Efficiently Certifiable OWSG $\to$ Efficiently Verifiable OWP (EV-OWP): If the post-processing is efficient, the resulting OWP is efficiently verifiable.
- Simulable Certifiable OWSG $\to$ OWF: If the certification protocol is classically simulable (specifically $1/3$ -simulable) and the key generation is classical, the resulting OWP implies the existence of OWFs.

Key Contributions

1. Obstacles: HPS Assumptions Imply One-Way Functions

The primary negative result of the paper is the falsification of the conjecture that HPS assumptions are independent of OWFs.

Theorem 1.2: If the Search HPS assumption is true, then a quantum-secure one-way function can be explicitly constructed.
Mechanism: The authors demonstrate that the state certification protocol for Hamiltonian phase states proposed in [HPS25] is not only computationally efficient but also $\eta$ -simulable with negligible error. Because the HPS-derived OWSG admits a simulable certification protocol, the resulting OWP can be classically simulated. By existing results (e.g., [KT25], [IL89]), the existence of a classically simulable OWP implies the existence of distributional OWFs, which in turn imply standard OWFs.
Consequence: The HPS assumptions cannot be used to instantiate genuine Microcrypt protocols (like Countcrypt) because their validity necessitates the existence of OWFs.

2. Opportunities: A Toolbox for Efficiently Verifiable OWPs

Despite the negative result for HPS, the paper provides a positive methodological contribution for constructing Efficiently Verifiable One-Way Puzzles (EV-OWPs), which are the minimal primitive for the "Quantumania" subworld.

Theorem 1.5 & Corollary 5.3: The authors show that any OWSG equipped with a computationally efficient "measure first, ask later" state certification protocol yields an EV-OWP.
Significance: This provides a new "toolbox" for identifying concrete candidates for EV-OWPs. Instead of relying solely on global Clifford shadows (which are not computationally efficient for arbitrary states), researchers can now look for tailored certification protocols that are computationally efficient but not classically simulable.

3. Direct Construction of OWFs from Simulable OWSGs

The paper refines the construction of OWFs from simulable OWSGs.

Theorem 1.7: They present a direct construction of a quantum-secure OWF from an $\eta$ -simulable, efficiently certifiable OWSG (where $\eta$ is negligible). This construction bypasses the intermediate steps of compiling a distributional OWF into a weak OWF and then into a standard OWF, offering a simpler and more direct proof path.

Results

Falsification of Microcrypt Instantiation via HPS: The paper proves that the Search HPS assumption implies the existence of OWFs. Consequently, cryptographic primitives built on HPS (such as the OWSG and PRSG proposed in [BHH+25]) belong to the world of "Minicrypt" (classical cryptography based on OWFs) rather than "Microcrypt."
Characterization of State Ensembles: The paper identifies a delicate balance required for a state ensemble to instantiate EV-OWPs genuinely in Microcrypt:
1. The states must be hard to learn (to form a PRSG/OWSG without OWFs).
2. The states must admit a computationally efficient "measure first, ask later" certification protocol.
3. The certification protocol must not be classically simulable.
Evaluation of Candidates: The authors evaluate several candidate state families (Table 1):
- OWF-based phase states: Fail condition 3 (require OWFs).
- Hamiltonian phase states: Fail condition 3 (admit simulable certification).
- Low stabilizer rank states: Fail condition 3 (structure allows classical simulation).
- Random brickwork circuits: Fail condition 2 (no known efficient certification protocol).
- Conclusion: No known family of states currently satisfies all three conditions simultaneously.

Significance and Claims

The paper claims to resolve the status of the HPS assumptions, demonstrating that they are not a route to "genuine" Microcrypt but rather a novel, inherently quantum assumption for constructing classical cryptography (Minicrypt).

The authors emphasize that their work shifts the focus from "Can we find a state that is hard to learn?" to "Can we find a state that is hard to learn, easy to certify, but whose certification is hard to simulate?" They argue that their framework provides the necessary criteria to evaluate future candidates for EV-OWPs.

The paper concludes modestly, noting that while they have ruled out HPS and low-rank stabilizer states as candidates for genuine Microcrypt, the search for a state ensemble satisfying the delicate balance of hardness, certifiability, and non-simulability remains an open and critical problem for the field. They explicitly state that their work does not provide a concrete instantiation of Quantumania but rather a rigorous set of conditions and a "toolbox" to guide future research toward such an instantiation.