Translating Between the Common Haar Random State Model and the Unitary Model
Eli Goldin, Mark Zhandry · 2025
Read Translating Between the Common Haar Random State Model and the Unitary Model by Eli Goldin, Mark Zhandry (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11634.txt.
Introduction
Eli Goldin and Mark Zhandry wrote this cryptography paper in 2025. Black-box separations show that some crypto goals cannot be reached from others by plain means. For quantum goals, many separations are known in a shared random-state model, but that model counts only as a start. A full proof needs a unitary model, and some past tries to lift results across were flawed.
The pair give broad terms under which the lift works cleanly. Their methods yield tidy proofs for known separations and fresh ones that were held only in the weaker model. The work is modular, so later teams can reuse the steps. The authors frame it as a fix and a toolkit: sound lifts, with the bugs of past attempts named and avoided.
Catalog record
| CREATOR | Eli Goldin, Mark Zhandry |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11634
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Translating Between the Common Haar Random State Model and the Unitary Model Eli Goldin, Mark Zhandry Abstract Black-box separations are a cornerstone of cryptography, indicating barriers to various goals. A recent line of work has explored black-box separations for quantum cryptographic primitives. Namely, a number of separations are known in the Common Haar Random State (CHRS) model, though this model is not considered a complete separation, but rather a starting point. A few very recent works have attempted to lift these separations to a unitary separation, which are considered complete separations. Unfortunately, we find significant errors in some of these lifting results. We prove general conditions under which CHRS separations can be generically lifted, thereby giving simple, modular, and bug-free proofs of complete unitary separations between various quantum primitives. Our techniques allow for simpler proofs of existing separations as well as new separations that were previously only known in the CHRS model. 1 Introduction As cryptography transitions into a quantum world, it is important to understand the relationship between various quantum cryptographic concepts. In particular, while one-way functions are widely considered to be the most basic classical object, it has recently become apparent that there is a vast world of primitives that live even below one-way functions. To help understand this new world (often dubbed “MicroCrypt”), there has recently been much work on showing black-box separations between various tasks. In this work, we will focus on a recently popular approach, which is the common Haar-random state (CHRS) model [ CCS25 , AGL24a ] . This model gives all users – protocols and adversaries alike – many copies of a single Haar-random quantum state. Some primitives such as quantum commitments, one-way state puzzles, and 1-copy pseudorandom states (1-PRS) exist in this model, but several recent works [ CCS25 , AGL24a , AGL24b ] have shown that a number of other primitives do not exist, such as many-time PRSs, one-way state generators, and commitments and key agreement with classical communication. Thus, these primitives are all separated from quantum commitments/one-way puzzles/1-PRSs in this model. The power of the CHRS model comes from its simplicity, as it is essentially the most basic idealized model one can imagine. However, the CHRS model is an isometry mapping a small input state (in this case, the empty state) into a larger output state. Importantly, the isometry is irreversible , and there is no way to coherently eliminate a copy of the state. Such an oracle does not adequately reflect “real-world” techniques that are available, as quantum (unitary) circuits are reversible. For this reason, a separation in the CHRS model is not considered a full separation, though it is still useful as a starting point. Instead, it is preferable to use a unitary (reversible) oracle. Remark 1.1 . One may ask if it is even better to use a classical oracle for separations. Such a classical oracle separation would capture systems based off of classical functions, and would indeed be relevant for separating primitives that live “above” one-way functions. However, for the inherently quantum MicroCrypt primitives we focus on here, the primitives in general cannot be represented using classical functions, but instead will be represented using unitary operations. Therefore, a unitary separation seems essentially as good as a classical one. Unfortunately, unitary oracles are much harder to work with, as now one has to reason about query complexity and deal with issues like reversing computation or adaptivity. Very recently, several works have started to “lift” the CHRS model separations into a unitary separation [ CCS25 , BCN25 , BMM+25 ] 1 1 1 The first version of [ CCS25 ] only included the CHRS model, but was more recently updated to include extensions to the unitary model. to give a unitary black-box separation. The main result common to these works is to show that quantum commitments do not imply many-time PRSs, though the different works have different variants of this statement. These works all employ somewhat similar ideas, but differ significantly on the underlying details. Our Work. Our main result, which is inspired by the particular techniques of [ BMM+25 ] , is the following: Theorem 1.2 (informal) . For any ‘‘typical’’ 2 2 2 Here, a “typical” primitive is one whose security experiment only queries the underlying primitive a bounded polynomial number of times. We note that certain primitives such as quantum one-wayness or many-time PRSs technically allow an arbitrarily polynomial number of queries, but we can also consider bounded-query versions which are “typical” by this definition, and will be sufficient for our purposes. primitive A , A exists in a slightly modified CHRS model if and only if it exists in a unitary oracle model. In particular, separations that exist in the modified CHRS model also hold in a unitary oracle model. Here, the CHRS variant provides all parties copies of the state \ket{\psi-}:=\ket{\psi}-\ket{0} for a Haar-random \ket{\psi} , rather than \ket{\psi} itself. It may seem that \ket{\psi} and \ket{\psi-} should have roughly the same power, and in one direction we show that this is true: Theorem 1.3 (informal) . For any primitive A whose security is described by a ‘‘single-stage game’’, 3 3 3 A single-stage game is a potentially interactive game between a single adversary and challenger, as opposed to “multi-stage” games which have multiple isolated adversaries. if A exists in the plain CHRS model, it also exists in a \ket{\psi-} model and hence in a unitary model. On the other hand, we show that a generic solution to the converse is actually false, in the sense that there is no way to generically construct \ket{\psi-} from even many copies of \ket{\psi} . However, the models are close enough that we expect typical separations in the plain CHRS model to also hold in the modified CHRS model. In fact, we show that the separation between commitments and many-time PRSs (or even quantum one-wayness) holds in the \ket{\psi-} model. This reduces to showing that many-time PRSs and quantum one-wayness do not exist in the \ket{\psi-} model, which we show through a very similar proof structure to the \ket{\psi} case analyzed in [ CCS25 , BCN25 ] . Combined with Theorem 1.2 this gives an alternative proof of some of the main results of [ CCS25 , BCN25 , BMM+25 ] that is more modular and arguably conceptually simpler. Along the way, we identify significant conceptual errors in both [ CCS25 ] and [ BCN25 ] , rendering their unitary oracle separations incorrect. In particular, these bugs left separating commitments and one-wayness open relative to a unitary oracle, which we resolve. 4 4 4 Separating commitments and PRSs also appeared in [ BMM+25 ] , but there is no bug in their proof. We therefore argue that future work in this space should focus on proving separations in the \ket{\psi-} model, which still has much of the simplicity of the plain CHRS model, but which is equivalent to a unitary separation through our Theorem 1.2 . We also give conditions under which a converse of Theorem 1.3 holds, meaning that separation in the \ket{\psi} model implies an separation in the \ket{\psi-} model and hence unitary model. In particular, we show the following: Theorem 1.4 (informal) .