Theory of Cryptography

We initiate the study of untelegraphable encryption (UTE), founded on the no-telegraphing principle, which allows an encryptor to encrypt a message such that a binary string representation of the ciphertext cannot be decrypted by a user with the secret key, a task that is classically impossible. This is a natural relaxation of unclonable encryption (UE), inspired by the recent work of Nehoran and Zhandry (ITCS 2024), who showed a computational separation between the no-cloning and no-telegraphing principles.

In this work, we define and construct UTE information-theoretically in the plain model. Building off this, we give several applications of UTE and study the interplay of UTE with UE and well-studied tasks in quantum state learning, yielding the following contributions:

In this work, we make progress on this problem. Our main technical contribution is a computational variant of the celebrated monogamy of entanglement game, where the secret is only computationally hidden from the players, rather than information-theoretically. In these settings, we prove a negligible bound on the maximal winning probability over all strategies. As a direct application, we obtain a non-interactive (simultaneous message) QKD protocol from any post-quantum classical non-interactive key exchange, which satisfies everlastingly secure assuming Alice and Bob agree on the same key. The protocol only uses EPR pairs and standard and Hadamard basis measurements, making it suitable for near-term quantum hardware. We also propose how to convert this protocol into a two-round protocol that satisfies the standard notion of everlasting security.

Pseudorandom unitaries (PRUs), one of the key quantum pseudorandom notions, are efficiently computable unitaries that are computationally indistinguishable from Haar random unitaries. While there is evidence to believe that PRUs are weaker than one-way functions, so far its relationship with other quantum cryptographic primitives (that are plausibly weaker than one-way functions) has not been fully established.

In this work, we focus on quantum cryptographic primitives with classical communication, referred to as QCCC primitives. Our main result shows that QCCC bit commitments and QCCC key agreement, cannot be constructed from pseudorandom unitaries in a black-box manner.

Our core technical contribution is to show (in a variety of settings) the difficulty of distinguishing identical versus independent Haar unitaries by separable channels. Our result strictly improves upon prior works which studied similar problems in the context of learning theory [Anshu, Landau, Liu, STOC 2022] and cryptography [Ananth, Gulati, Lin, TCC 2024].

\(\textsf{MIP}^*\) is the class of languages decidable by an efficient classical verifier interacting with multiple quantum provers that share entangled qubits but cannot communicate. Notably, \(\textsf{MIP}^*\) was proved to equal RE, the class of all recursively enumerable languages.

We introduce the complexity class \(\textsf{Clifford}\)–\(\textsf{MIP}^*\), which restricts quantum provers to Clifford operations and classical post-processing of measurement results, while still allowing shared entangled qubits in any quantum state. We show that any strategy in this model can be simulated by classical provers with shared random bits, and therefore admits a local hidden-variable description. Consequently, \(\textsf{Clifford}\)–\(\textsf{MIP}^*\) = \(\textsf{MIP}\), a vastly smaller complexity class compared to \(\textsf{RE}\).

Moreover, we resolve an open question posed by Kalai et al. (STOC 2023), by showing that quantum advantage in any single-round non-local game requires at least two provers operating outside the \(\textsf{Clifford}\)–\(\textsf{MIP}^*\) computational model. This rules out a proposed approach for significantly improving the efficiency of quantum advantage tests that are based on compiling non-local games into single-prover interactive protocols.

Recent active studies have demonstrated that cryptography without one-way functions (OWFs) could be possible in the quantum world. Many fundamental primitives that are natural quantum analogs of OWFs or pseudorandom generators (PRGs) have been introduced, and their mutual relations and applications have been studied. Among them, pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, and Yuen, Crypto 2022] are one of the most important primitives. PRFSGs are a natural quantum analogue of pseudorandom functions (PRFs), and imply many applications such as IND-CPA secret-key encryption (SKE) and EUF-CMA message authentication code (MAC). However, only known constructions of (many-query-secure) PRFSGs are ones from OWFs or pseudorandom unitaries (PRUs).

In this paper, we construct classically-accessible adaptive secure PRFSGs in the invertible quantum Haar random oracle (QHRO) model which is introduced in [Chen and Movassagh, Quantum]. The invertible QHRO model is an idealized model where any party can access a public single Haar random unitary and its inverse, which can be considered as a quantum analog of the random oracle model. Our PRFSG constructions resemble the classical Even-Mansour encryption based on a single permutation, and are secure against any unbounded polynomial number of queries to the oracle and construction. To our knowledge, this is the first application in the invertible QHRO model without any assumption or conjecture. The previous best constructions in the idealized model are PRFSGs secure up to \(o(\lambda /\log \lambda )\) queries in the common Haar state model [Ananth, Gulati, and Lin, TCC 2024] and (inverseless) PRUs in a relaxed QRHO model without inverse access [Ananth, Bostanci, Gulati, and Lin, Eurocrypt 2025].

We develop new techniques on Haar random unitaries to prove the selective and adaptive security of our PRFSGs. For selective security, we introduce a new formula, which we call the Haar twirl approximation formula. For adaptive security, we show the unitary reprogramming lemma and the unitary resampling lemma along with the several technical tools for unitary oracle security proof with pure state queries. These have their own interest, and may have many further applications. In particular, by using the approximation formula, we give an alternative proof of the non-adaptive security of the PFC ensemble [Metger, Poremba, Sinha, and Yuen, FOCS 2024] as an additional result.

Finally, we prove that our construction is not PRUs or quantum-accessible non-adaptive PRFSGs by presenting quantum polynomial time attacks. Our attack is based on generalizing the hidden subgroup problem where the relevant function outputs quantum states.

Single decryptor encryption (SDE) is public key encryption (PKE) where the decryption key is an unclonable quantum state. Coladangelo, Liu, Liu, and Zhandry (CRYPTO 2021) realized the first SDE assuming subexponentially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), along with the polynomial hardness of the learning with errors (LWE) assumption. Since then, SDE has played a pivotal role in recent advances in quantum cryptography. However, despite its central importance in unclonable cryptography, many fundamental questions about SDE remain unanswered. For example, a line of works has proposed various security notions for SDE, but their relationships have hardly been discussed. Moreover, while many subsequent works have adopted the construction methodology of Coladangelo et al., none have explored its improvement, leaving the possibility of a more efficient approach to SDE.

In this work, we address these fundamental questions concerning SDE. Our contributions are threefold.

In this paper we bridge this gap, by showing a generic construction lifting any unforgeable threshold signature scheme to strong unforgeability. The building blocks of our construction can be instantiated in the standard model under standard assumptions. The achieved notion of strong unforgeability extends the definition of Navot and Tessaro to achieve the strongest level of security according to the hierarchy of Bellare et al. (following a recent classification of security notions for (blind) threshold signatures by Lehmann, Nazarian, and Özbay [Eurocrypt’25]).

The starting point for our transformation is an existing construction for single-user signatures from chameleon hash functions by Steinfeld, Pieprzyk and Wang [RSA’07]. We first simplify their construction by relying on a stronger security notion for chameleon hash functions. The bulk of our technical contribution is then to translate this framework into the threshold setting. Towards this goal, we introduce a game-based definition for threshold chameleon hash functions (TCHF) and provide a construction of TCHF that is secure under DDH in the standard model. We believe that our new notion of TCHF might also be of independent interest.

First, contrary to what one might expect, we show that there is a simple attack on the non-resignability property sNR of the BUFF-transform when instantiated with an iterative hash function. The attack relies on leaking an intermediate result of the hash computation to the adversary who is challenged to “resign” the message. This negative result once more shows the subtlety in the non-resignability property.

Second, on the positive side, we propose a small modification to the original BUFF transform, which we call Sandwich BUFF (for reasons to become clear), and prove the non-resignability property sNR of Sandwich BUFF both for Merkle-Damgård-based hash functions in the random oracle model, and for Sponge-based hash functions in the random permutation model.

In this paper, we prove that the supersingular isogeny problem (\({{ \textsc {Isogeny}}}\)), endomorphism ring problem (\({{ \textsc {EndRing}}}\)) and maximal order problem (\({{ \textsc {MaxOrder}}}\)) are equivalent under probabilistic polynomial time reductions, unconditionally.

Isogeny-based cryptography is founded on the presumed hardness of these problems, and their interconnection is at the heart of the design and analysis of cryptosystems like the SQIsign digital signature scheme. Previously known reductions relied on unproven assumptions such as the generalized Riemann hypothesis. In this work, we present unconditional reductions, and extend this network of equivalences to the problem of computing the lattice of all isogenies between two supersingular elliptic curves (\({{ \textsc {HomModule}}}\)).

For cryptographic applications, one requires computational problems to be hard on average for random instances. It is well-known that if \({{ \textsc {Isogeny}}}\) is hard (in the worst case), then it is hard for random instances. We extend this result by proving that if any of the above-mentioned classical problems is hard in the worst case, then all of them are hard on average. In particular, if there exist hard instances of \({{ \textsc {Isogeny}}}\), then all of \({{ \textsc {Isogeny}}}\), \({{ \textsc {EndRing}}}\), \({{ \textsc {MaxOrder}}}\) and \({{ \textsc {HomModule}}}\) are hard on average.

The Legendre signature of an integer x modulo a prime p with respect to offsets \(\textbf{a} = (a_1, \dots , a_\ell )\) is the string of Legendre symbols \((\frac{x+a_1}{p}), \dots , (\frac{x+a_\ell }{p})\). Under the quadratic-residuosity assumption, we show that the function that maps the pair (x, p) to the Legendre signature of x modulo p, with respect to public random offsets \(\textbf{a}\), is a pseudorandom generator. Our result applies to cryptographic settings in which the prime modulus p is secret; the result does not extend to the case—common in applications—in which the modulus p is public. At the same time, this paper is the first to relate the pseudorandomness of Legendre symbols to any pre-existing cryptographic assumption.

We revisit the polynomial attack to the \(\textsf{ROS}\) problem modulo p from [6]. Our new algorithm achieves a polynomial time solution in dimension \(\ell \gtrsim 0.726 \cdot \log _2 p\), extending the range of dimensions for which a polynomial attack is known beyond the previous bound of \(\ell > \log _2p\).

We also combine our new algorithm with Wagner’s attack to improve the general \(\textsf{ROS}\) attack complexity for a range of dimensions where a polynomial solution is still not known.

We implement our polynomial attack and break the one-more unforgeability of blind Schnorr signatures over 256-bit elliptic curves in a few seconds with 192 concurrent sessions.

A threshold signature allows one to delegate its signing rights to n parties, such that any subset of size t can sign a message on their behalf. In this work, we show how to construct threshold signatures for any t and n from one way functions, thus establishing the latter as a necessary and sufficient computational assumption. Our protocol makes non-black box use of one-way functions, and can be generalized to other access structures, such as monotone policies.

A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine. In this work, we propose a new approach for constructing PoQ protocols where soundness holds unconditionally assuming a bound on the memory of the prover, but otherwise no restrictions on its runtime. In this model, we propose two protocols:

We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs.

In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover’s messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture.

We show the following two main constructions of qIOPs, both of which are unconditional:

As a key component of our construction, we introduce a novel single prover many-qubits tests, which may be of independent interest.

At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. As applications, we derive the first direct product theorems in the average case, in the hybrid setting—i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.