We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement. As an application, we establish the first PPAD hardness result based on the polynomial hardness of LWE combined with a widely believed complexity assumption. Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we give the first construction from the polynomial hardness of LWE. This notion may be of independent interest.

In this paper, we investigate the Extended Gabidulin (EG) codes and the Interleaved EG (IEG) codes, conduct more analysis on the Blockwise Rank Decoding (BRD) problem, and obtain efficient rank-based cryptosystems. First, we develop a general decoding algorithm for the (I)EG codes by solving the Linear Reconstruction (LR) problem. We find that the (I)EG codes can be probabilistically decoded by Welch-Berlekamp like algorithm, can achieve an arbitrarily small decoding failure rate, and can decode up to the rank Gilbert-Varshamov bound (even close to the minimal distance). Our conclusion intrinsically shows that it is not necessary to require that the generator be linearly independent as Gabidulin codes for designing decodable codes from $q$-polynomials. An interesting and important byproduct is that we demonstrate that decoding interleaved Gabidulin codes can be achieved deterministically by solving the LR problem. It has long been believed that there are only probabilistic decoding algorithms for interleaved Gabidulin codes (IEEE TIT 2011, DCC 2014, DCC 2024). Second, we propose the Blockwise Puncturing (BP) approach for solving the BRD problem (Asiacrypt 2023, IEEE TIT 2025). For this purpose, we derive a tight upper bound of independent equations in the MM modeling for general blocks, which further addresses an open question in (Asiacrypt 2023, IEEE TIT 2025, PQC 2024). We find that the BP approach can speed up the MM modeling. When the proposed approach is applied to the BRD problem used in existing rank-based cryptosystems, such as RQC and ROLLO (IEEE TIT 2025, PQC 2024), some parameters sets are lower than the practical security strength, and the security loss is up to 25 bits; nevertheless, the schemes still preserve the claimed security level. This work further supports the hardness of the BRD problem and enhances the security and performance of cryptosystems based on the BRD problem. Third, we apply the EG codes to the structured rank decoding encryption, namely RQC based on the BRD problem (Asiacrypt 2023, IEEE TIT 2025), and obtain the Bolckwise RQC with the EG codes (BRE). We find that the gain of using the EG codes in decoding capacity outweighs the complexity loss in solving the BRD problem with the BP approach, which still makes it possible to design more efficient schemes. As a result, BRE features a more attractive size with a bandwidth of about 1.6 KB for 128-bit security. Overall, BRE outperforms Hamming metric ones of NIST PQC Round 4 submissions, such as HQC, BIKE, and Classic McEliece, in terms of bandwidth, especially about 76% more compact than HQC selected by the NIST PQC. Fourth, we apply the EG codes to the unstructured rank decoding encryption, namely NH-Multi-UR-AG (IEEE TIT 2024), with the homogeneous errors, and obtain the Homogeneous Unstructured Rank decoding encryption with the EG codes (HURE). The bandwidth of HURE is about 6.7 KB for 128-bit security, which is slightly shorter than NH-Multi-UR-AG. This bandwidth also outperforms lattice-based unstructured PKEs, namely FrodoKEM and Scloud$^{+}$, respectively about 64% and 45% more compact. We intrinsically show that it is sufficient to construct an efficient unstructured PKE scheme by only homogeneous errors, without non-homogeneous errors. This application benefits from that we derive the concise DFR for the EG codes, which allows to choose flexible parameters.

Non-interactive zero-knowledge (NIZK) proofs tend to be randomized and there are many possible proofs for any fixed NP statement. Can we have NIZKs with only a single unique valid proof per statement? Such NIZKs are known under strong cryptographic assumptions (indistinguishability obfuscation), and are conversely known to require strong cryptographic assumptions (witness encryption). In this work, following Lepinski, Micali, and shelat (TCC '05), we consider the following relaxed notion of unique NIZKs (UNIZKs): - We only require (computationally) unique proofs for NP statements with a (computationally) unique witness; an adversary that can produce two distinct proofs must also know two distinct witnesses. - We consider NIZKs with prover setup, where a potentially malicious prover initially publishes a public key $\mathsf{pk}$ and keeps a corresponding secret key $\mathsf{sk}$, which it uses to produce arbitrarily many NIZK proofs $\pi$ in the future. While the public key $\mathsf{pk}$ is not required to be unique, once it is fixed, all the subsequent proofs $\pi$ that the prover can produce should be unique. We show that both of these relaxations are needed to avoid witness encryption. Prior work constructed such UNIZKs under the quadratic residuosity assumption, and it remained an open problem to do so under any other assumptions. Here, we give a new construction of UNIZKs under the learning with errors (LWE) assumption. We also identify and fix a subtle circularity issue in the prior work. UNIZKs are a non-interactive version of steganography-free zero-knowledge of Abdolmaleki et al. (TCC '22). As an application of UNIZKs, we get a general steganography detection mechanism that can passively monitor arbitrary functionalities to detect steganographic leakage.

We introduce Bounded-Equivocable PRFs, a new variant of pseudorandom functions. They combine standard pseudorandomness with a bounded form of programmability. In our model, an adversary may issue an arbitrary number of queries that remain indistinguishable from random. Bounded equivocability ensures that responses can be programmed consistently with a later-revealed key, up to a fixed bound q. This relaxation avoids known impossibility results, which preclude polynomial unbounded equivocability in the standard model, while preserving the programmability required for applications. We present standard-model constructions of bounded-equivocable PRFs under the DDH and LWE assumptions, and we show how to make these constructions verifiable. Prior SIM-AC style primitives could not achieve verifiability since their programmability relied on embedding the secret key into the random oracle. We demonstrate applications to (i) adaptively secure private-key encryption, (ii) two-round threshold Schnorr signatures secure against adaptive corruptions, and (iii) leader election in Proof of Stake blockchains. Together, these results establish bounded-equivocable PRFs as a practical primitive that achieves programmability with verifiability in the standard model, and enables applications previously out of reach.

Gluing theorem for random unitaries [Schuster, Haferkamp, Huang, QIP 2025] have found numerous applications, including designing low depth random unitaries [Schuster, Haferkamp, Huang, QIP 2025], random unitaries in $\mathsf{QAC0}$ [Foxman, Parham, Vasconcelos, Yuen'25] and generically shortening the key length of pseudorandom unitaries [Ananth, Bostanci, Gulati, Lin EUROCRYPT'25]. We present an alternate method of combining Haar random unitaries from the gluing lemma from [Schuster, Haferkamp, Huang, QIP 2025] that is secure against adversaries with inverse query access to the joined unitary. As a consequence, we show for the first time that strong pseudorandom unitaries can generically have their length extended, and can be constructed using only $O(n^{1/c})$ bits of randomness, for any constant $c$, if any family of strong pseudorandom unitaries exists.

We present a multi-prime multi-power generalization of RSA for arbitrary integer moduli $n>1$ and messages $m<n$ which are regular modulo $n$, meaning that they have a John-von-Neumann pseudoinverse modulo $n$. We prove that our RSA generalization is correct in the sense that it works for all regular messages modulo $n$, and complete in the sense that it works for no other message. Our correctness and completeness result, which implies the original RSA correctness theorem, is proved in a rigorous way based on a new sharpening of Charmichael's theorem established in this paper. As for CRT-RSA, decryption can be accelerated by Chinese remaindering, which results in a multi-prime multi-power generalization of CRT-RSA. We show that the restriction to regular messages modulo $n$ is negligible by proving that under reasonable assumptions almost all messages are regular modulo $n$. More precisely, we give a probabilistic argument that for $k$-bit primes $p_1,\dots,p_r$ the probability that a random message fails to be regular modulo $n=p_1^{e_1}\dots p_r^{e_r}$ is at most $r/{2^{k-1}}$, which quickly tends to $0$ as $k\rightarrow \infty$, and which shows that our general scheme can be used even with primes of moderate length.

Quantum copy-protection is a functionality-preserving compiler that transforms a classical program into an unclonable quantum program. This primitive has emerged as a foundational topic in quantum cryptography, with significant recent developments. However, characterizing the functionalities that can be copy-protected is still an active and ongoing research direction. Assuming the existence of indistinguishability obfuscation and learning with errors, we show the existence of copy-protection for a variety of classes of functionalities, including puncturable cryptographic functionalities and subclasses of evasive functionalities. This strictly improves upon prior works, which were either based on the existence of heuristic assumptions [Ananth and Behera CRYPTO'24] or were based on the classical oracle model [Coladangelo and Gunn STOC'24]. Moreover, our constructions satisfy a new and much stronger security definition compared to the ones studied in the prior works. To design copy-protection, we follow the blueprint of constructing copy-protection from unclonable puncturable obfuscation (UPO) [Ananth and Behera CRYPTO'24] and present a new construction of UPO by leveraging the recently introduced techniques from [Kitagawa and Yamakawa TCC'25].

We study error-detection and error-correction codes for computationally bounded adversarial channels. We consider seeded codes where the polynomial-time encoding and decoding procedures share a public random seed, but are otherwise deterministic. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct such errors with overwhelming probability, while achieving better trade-offs between rate and error tolerance than those possible for computationally unbounded channels. For large alphabets, prior work (ITCS '25) achieves essentially optimal parameters under minimal cryptographic assumptions. However, for the binary alphabet, prior works (TCC '20, EUROCRYPT '25) either only achieved a weaker notion of selective security under the learning with errors (LWE) assumption, or relied on non-standard cryptographic assumptions to get the full notion of adaptive security. In this work, we construct binary codes that achieve the full notion of adaptive security assuming trapdoor hashing, which can in turn be instantiated under a variety of standard cryptographic assumptions such as LWE, or Decisional Diffie-Hellman (DDH), or Quadratic Residuosity (QR), or Decisional Composite Residuosity (DCR). For error detection, our codes get essentially optimal rate $R \approx 1$ and relative error tolerance $p \approx \frac{1}{2}$. For error correction, they can uniquely correct $p < 1/4$ fraction of errors with a rate $R$ matching that of the best known list-decodable codes for this error tolerance. As a central technical tool of potentially independent interest, we construct multi-input correlation intractable hashing for ``shifted output relations'' under the standard cryptographic assumptions above.

Distributed Key Generation (DKG) protocols are fundamental components of threshold cryptography, enabling key generation in a trustless manner for a range of cryptographic operations such as threshold encryption and signing. Of particular widespread use are DKG protocols for discrete-logarithm based cryptosystems. In this Systematization of Knowledge (SoK), we present a comprehensive analysis of existing DKG protocols in the discrete-logarithm setting, with the goal of identifying cryptographic techniques and design principles that facilitate the development of secure and resilient protocols. To offer a structured overview of the literature, we adopt a modular approach and classify DKG protocols based on their underlying network assumption and cryptographic tools. These two factors determine how DKG protocols manage secret sharing and reach consensus as their essential building blocks. We also highlight various insights and suggest future research directions that could drive further advancements in this area.

We prove an extension of the lower bound due to Sch\"onhage on addition chains.

A reduction showing that the hardness of the discrete logarithm ($\mathsf{DL}$) assumption implies the hardness of the computational Diffie-Hellman ($\mathsf{CDH}$) assumption in groups of order $p$, where $p - 1$ is smooth, was first presented by den Boer [Crypto, 88].} We also consider groups of prime order $p$, where $p - 1$ is somewhat smooth (say, every prime $q$ that divides $p - 1$ is less than $2^{100}$). Several practically relevant groups satisfy this condition. 1. We present a concretely efficient version of the reduction for such groups. In particular, among practically relevant groups, we obtain the most efficient and tightest reduction in the literature for BLS12-381, showing that $\mathsf{DL}$ = $\mathsf{CDH}$. 2. By generalizing the reduction, we show that in these groups the $n$-Power $\mathsf{DL}$ ($n$-$\mathsf{PDL}$) assumption implies $n$-Diffie-Hellman Exponent ($n$-$\mathsf{DHE}$) assumption, where $n$ is polynomial in the security parameter. On the negative side, we show there is no generic reduction, which could demonstrate that $n$-$\mathsf{PDL}$ implies the $n$-Generalized Diffie-Hellman Exponent ($n$-$\mathsf{GDHE}$) assumption. This is in stark contrast with the algebraic group model, where this implication holds.

We construct a unitary oracle relative to which $\mathbf{BQP}=\mathbf{QCMA}$ but quantum-computation-classical-communication (QCCC) commitments and QCCC multiparty non-interactive key exchange exist. We also construct a unitary oracle relative to which $\mathbf{BQP}=\mathbf{QMA}$, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QMA}$ but pseudorandom unitaries exist. We also show that (poly-round) QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of ``quantum samplable'' one-wayness and are an intermediate primitive between pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if $\mathbf{BQP}=\mathbf{PP}$. Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if $\mathbf{BQP} = \mathbf{QCMA}$, but are broken if $\mathbf{BQP} = \mathbf{PP}$. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class "CountCrypt".

Pseudorandom functions (PRFs) are one of the most fundamental primitives in classical cryptography. On the other hand, in quantum cryptography, it is possible that PRFs do not exist but their quantum analogues could exist, and still enabling many applications including SKE, MACs, commitments, multiparty computations, and more. Pseudorandom unitaries (PRUs) [Ji, Liu, Song, Crypto 2018], pseudorandom isometries (PRIs) [Ananth, Gulati, Kaleoglu, Lin, Eurocrypt 2024], and pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, Yuen, Crypto 2022] are major quantum analogs of PRFs. PRUs imply PRIs, and PRIs imply PRFSGs, but the converse implications remain unknown. An important open question is whether these natural quantum analogues of PRFs are equivalent. In this paper, we partially resolve this question by ruling out black-box constructions of them: \begin{enumerate} \item There are no black-box constructions of $O(\log\lambda)$-ancilla PRUs from PRFSGs. \item There are no black-box constructions of $O(\log\lambda)$-ancilla PRIs with $O(\log\lambda)$ stretch from PRFSGs. \item There are no black-box constructions of $O(\log\lambda)$-ancilla PRIs with $O(\log\lambda)$ stretch from PRIs with $\Omega(\lambda)$ stretch. \end{enumerate} Here, $O(\log\lambda)$-ancilla means that the generation algorithm uses at most $O(\log\lambda)$ ancilla qubits. PRIs with $s(\lambda)$ stretch is PRIs mapping $\lambda$ qubits to $\lambda+s(\lambda)$ qubits. To rule out the above black-box constructions, we construct a unitary oracle that separates them. For the separations, we construct an adversary based on the quantum singular value transformation, which would be independent of interest and should be useful for other oracle separations in quantum cryptography.

One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in ''Microcrypt'' where OWFs do not exist but quantum cryptography is possible. OWPuzzs are implied by almost all quantum cryptographic primitives, and imply several important applications such as non-interactive commitments and multi-party computations. A significant goal in the field of quantum cryptography is to base OWPuzzs on plausible assumptions that will not imply OWFs. In this paper, we base OWPuzzs on hardness of non-collapsing measurements. To that end, we introduce a new complexity class, $\mathbf{SampPDQP}$, which is a sampling version of the decision class $\mathbf{PDQP}$ introduced in [Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]. We show that if $\mathbf{SampPDQP}$ is hard on average for quantum polynomial time, then OWPuzzs exist. We also show that if $\mathbf{SampPDQP}\not\subseteq\mathbf{SampBQP}$, then auxiliary-input OWPuzzs exist. $\mathbf{SampPDQP}$ is the class of sampling problems that can be solved by a classical polynomial-time deterministic algorithm that can make a single query to a non-collapsing measurement oracle, which is a ''magical'' oracle that can sample measurement results on quantum states without collapsing the states. Such non-collapsing measurements are highly unphysical operations that should be hard to realize in quantum polynomial-time, and therefore our assumptions on which OWPuzzs are based seem extremely plausible. Moreover, our assumptions do not seem to imply OWFs, because the possibility of inverting classical functions would not be helpful to realize quantum non-collapsing measurements. We also study upperbounds of the hardness of $\mathbf{SampPDQP}$. We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs), which are a natural quantum analogue of distributional collision-resistant hashing [Dubrov and Ishai, STOC 2006]. We show that dCRPuzzs imply average-case hardness of $\mathbf{SampPDQP}$ (and therefore OWPuzzs as well). We also show that two-message honest-statistically-hiding commitments with classical communication and one-shot message authentication codes (MACs), which are a privately-verifiable version of one-shot signatures [Amos, Georgiou, Kiayias, Zhandry, STOC 2020], imply dCRPuzzs.

With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote devices genuinely allocate the promised quantum memory with specified number of qubits and coherence time. In this paper, we introduce a new concept, proofs of quantum memory (PoQM). A PoQM is an interactive protocol between a classical probabilistic polynomial-time (PPT) verifier and a quantum polynomial-time (QPT) prover over a classical channel where the verifier can verify that the prover has possessed a quantum memory with a certain number of qubits during a specified period of time. PoQM generalize the notion of proofs of quantumness (PoQ) [Brakerski, Christiano, Mahadev, Vazirani, and Vidick, JACM 2021]. Our main contributions are a formal definition of PoQM and its constructions based on hardness of LWE. Specifically, we give two constructions of PoQM. The first is of a four-round and has negligible soundness error under subexponential-hardness of LWE. The second is of a polynomial-round and has inverse-polynomial soundness error under polynomial-hardness of LWE. As a lowerbound of PoQM, we also show that PoQM imply one-way puzzles. Moreover, a certain restricted version of PoQM implies quantum computation classical communication (QCCC) key exchange.

Is it possible to comprehensively destroy a piece of quantum information, so that nothing is left behind except the memory of that one had it at some point? For example, various works, most recently Morimae, Poremba, and Yamakawa (TQC '24), show how to construct a signature scheme with certified deletion where a user who deletes a signature on $m$ cannot later produce a signature for $m$. However, in all of the existing schemes, even after deletion the user is still able keep irrefutable evidence that $m$ was signed, and thus they do not fully capture the spirit of deletion. In this work, we initiate the study of certified deniability in order to obtain a more comprehensive notion of deletion. Certified deniability uses a simulation-based security definition, ensuring that any information the user has kept after deletion could have been learned without being given the deleteable object to begin with; meaning that deletion leaves no trace behind! We define and construct two non-interactive primitives that satisfy certified deniability in the quantum random oracle model: signatures and non-interactive zero-knowledge arguments (NIZKs). As a consequence, for example, it is not possible to delete a signature/NIZK and later provide convincing evidence that it used to exist. Notably, our results utilize uniquely quantum phenomena to bypass Pass's (CRYPTO '03) celebrated result showing that deniable NIZKs are impossible even in the random oracle model.

This paper presents a unified information-theoretic framework for steganography that simultaneously addresses reliability, statistical undetectability, computational security, and robustness over noisy channels. Unlike prior work that treated these aspects separately under idealized assumptions, the framework formalizes them within a single model, providing definitions, capacity bounds, and impossibility results based on statistical distances. It also considers computationally bounded adversaries and trade-offs between payload, detectability, and error, offering a rigorous foundation for designing secure, robust, and efficient steganographic systems.

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].

The quantum Haar random oracle model is an idealized model where every party has access to a single Haar random unitary and its inverse. We construct strong pseudorandom unitaries in the quantum Haar random oracle model. This strictly improves upon prior works who either only prove the existence of pseudorandom unitaries in the inverseless quantum Haar random oracle model [Ananth, Bostanci, Gulati, Lin, EUROCRYPT 2025] or prove the existence of a weaker notion (implied by strong pseudorandom unitaries) in the quantum Haar random oracle model [Hhan, Yamada, 2024]. Our results also present a viable approach for building quantum pseudorandomness from random quantum circuits and analyzing pseudorandom objects in nature.

A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reductions to almost any generic cryptographic primitive: for instance, anything that can be built from random oracles, generic multilinear groups, and virtual black-box obfuscation. Our result is optimal, as Ghentiyala and Guruswami (2024) observed that pseudorandom codes tolerating any sub-constant rate of random errors exist using a black-box reduction from one-way functions. The key technical ingredient in our proof is the hypercontractivity theorem for Boolean functions, which we use to prove our impossibility in the random oracle model. It turns out that this easily extends to an impossibility in the presence of "crypto oracles," a notion recently introduced---and shown to be capable of implementing all the primitives mentioned above---by Lin, Mook, and Wichs (EUROCRYPT 2025).

Is it possible to efficiently convert any arbitrary source with sufficiently high (min-)entropy into nearly uniformly random bits? Information-theoretically, this is achievable using seeded extractors, provided the source is independent of the seed. However, in the absence of any such independence guarantee, no solution is possible for general computationally unbounded sources. Even for efficiently samplable sources, we cannot extract randomness that is statistically close to uniform, but can at best condense the randomness into an output that is only missing logarithmically many bits of entropy compared to the uniform distribution. Dodis, Ristenpart and Vadhan (TCC '12) constructed such seeded condensers for efficiently samplable sources that can depend arbitrarily on the seed assuming near-optimal security of collision-resistant hash functions. In this work, we investigate whether such condensers can be made seedless. We present several new results: -- We construct seedless condensers for all efficiently samplable sources assuming near-optimal security of keyless multi-collision resistant hash functions. We justify this assumption by showing it holds in the auxiliary-input random oracle model. -- We show that such seedless condensers cannot be proven secure via a black-box reduction from any standard game-based assumption, even if we assume optimal exact security. In fact, we give a general black-box separation that applies to a broad class of seedless primitives, with seedless condensers as a special case. -- We consider the class of efficiently samplable distributed sources where two parties jointly sample randomness $x=(x_0,x_1)$, with one party honestly choosing $x_b$ uniformly at random while the other party adversarially chooses $x_{1-b}$ depending on $x_b$. We show how to construct seedless condensers for such sources assuming near-optimal security of game-based assumptions -- either: (1) adaptive one-way functions, or (2) a certain from of (single-input) correlation-intractable hash functions that can be instantiated from key-dependent-message (KDM) secure encryption.

A verifiable delay function (VDF) [Boneh et al., CRYPTO 2018] is a function $f$ that is slow-to-compute, but is quickly verifiable given a short proof. This is formalised using two security requirements: i) sequentiality, which requires that a parallel adversary is unable to compute $f$ faster; and ii) soundness, which requires that an adversary is unable to generate a proof that verifies wrong outputs. A time-lock puzzle (TLP), on the other hand, is a puzzle that can be quickly generated, but is slow-to-solve. The security requirement here is sequentiality, which requires that a parallel adversary is unable to solve puzzles faster. In this paper, we study the relationship between these two timed primitives. Our main result is a construction of ``one-time'' VDF from TLP using indistinguishability obfuscation (iO) and one-way functions (OWFs), where by ``one-time'' we mean that sequentiality of the VDF holds only against parallel adversaries that do not preprocess public parameters. Our VDF satisfies several desirable properties. For instance, we achieve perfectly sound and short proofs of $O(\lambda)$ bits, where $\lambda$ is the security parameter. Moreover, our construction is a trapdoor (one-time) VDF that can be easily extended to achieve interesting extra properties (defined in our paper) such as trapdoor-homomorphic and trapdoor-constrained evaluation. Finally, when combined with the results of Bitansky et al., [ITCS 2016], this yields one-time VDFs from any worst-case non-parallelizing language, iO and OWF. To the best of our knowledge, this is the first such construction that only relies on polynomial security.

We develop a toolbox for modular construction and analysis of succinct, non-interactive commitments and vector commitments in the random oracle model, while guaranteeing universally composable security. To demonstrate its power, we use the toolbox to construct and analyze a modular variant of the Kilian-Micali ZK-SNARK. Along the way we also propose a new UC formulation of a global random oracle, that avoids a weakness in existing formulations and also enables expressing more nuanced, session-specific abstractions. We hope that this toolbox will be useful for building secure applications in settings where both succinctness and non-interactivity are key.

Let $1$ be the all-one vector and $\odot$ denote the component-wise multiplication of two vectors in $\mathbb F_2^n$. We study the vector space $\Gamma_n$ over $\mathbb F_2$ generated by the functions $\gamma_{2k}:\mathbb F_2^n \to \mathbb F_2^n, k\geq 0$, where $$ \gamma_{2k} = S^{2k}\odot(1+S^{2k-1})\odot(1+S^{2k-3})\odot\ldots\odot(1+S) $$ and $S:\mathbb F_2^n\to\mathbb F_2^n$ is the cyclic left shift function. The functions in $\Gamma_n$ are shift-invariant and the well known $\chi$ function used in several cryptographic primitives is contained in $ \Gamma_n$. For even $n$, we show that the permutations from $\Gamma_n$ with respect to composition form an Abelian group, which is isomorphic to the unit group of the residue ring $\mathbb F_2[X]/(X^n+X^{n/2})$. This isomorphism yields an efficient theoretic and algorithmic method for constructing and studying a rich family of shift-invariant permutations on $\mathbb F_2^n$ which are natural generalizations of $\chi$. To demonstrate it, we apply the obtained results to investigate the function $\gamma_0 +\gamma_2+\gamma_4$ on $\mathbb F_2^n$.

We investigate the existence of non-interactive proof systems where the verifier runs in time sublinear in the input size. This seemingly paradoxical property has been shown possible in interactive settings for specific soundness notions, in particular proofs of proximity (Rothblum, Vadhan, and Wigderson, STOC 2013) and rational proofs (Azar and Micali, STOC 2012). We initiate the study of the Fiat-Shamir paradigm in the sublinear verification setting. We show Fiat-Shamir to generally fail in this context, and, importantly, we study how it fails. Our results include: - General impossibility results from properties of Boolean functions. We introduce an abstract framework that generically applies to the sublinear setting (regardless of the soundness notion). Our framework includes an appropriately adapted variant of Fiat-Shamir, as well as general sufficient conditions under which employing Fiat-Shamir yields insecure protocols. Motivated by their practical interest and simplicity, we then apply our framework to rational proofs. We develop attack strategies that leverage the sublinearity of the verifier and exploit complexity metrics of Boolean functions, revealing an intriguing connection. - Robustness and applicability of our attacks. We ask whether a strengthened variant of Fiat-Shamir—which includes even parts of the public inputs that the verifier has not queried—can yield secure protocols. We show negative results in this setting as well. In particular, we prove that representative protocols for broad and "easy" function classes—shallow Boolean circuits (Campanelli and Gennaro, 2015) and threshold circuits (Azar and Micali, 2013)—become insecure when compiled with either of our Fiat-Shamir transforms. Our general results provide further insights into non-interactive sublinear verification, complementing the concurrent work by Chen, Jin and Wichs (STOC 2025), which shows lower bounds for non-interactive proofs of proximity for a specific problem within P.

Cloud computing has matured into the default substrate for data processing, yet confidentiality demands of- ten force a hard trade-off between the utility of outsourced computation and the privacy of sensitive inputs. Homomorphic encryption (HE)[1] promises to dissolve that trade-off by enabling computation directly on ciphertexts, returning encrypted results that only the data owner can decrypt. Despite remarkable progress in fully homomorphic encryption (FHE) and leveled variants suitable for bounded-depth circuits, deploying HE at cloud scale remains challenging. The cost of ciphertext arithmetic is orders of magnitude higher than plaintext compute; noise growth and rescaling impose algorithmic discipline; vectorization and rotation keys complicate program layout; and the lack of verifiability in bare HE obliges trust in a correct-but-curious cloud[?]. This paper develops a system perspective on how to apply modern HE in cloud environments without reducing it to a boutique feature. We introduce a reference architecture that marries approximate-arithmetic HE for analytics with exact- arithmetic HE for integrity-critical operations, composes HE with succinct proofs for verifiability, and integrates a cost model into the scheduler so that elastically provisioned serverless workers can meet latency objectives under price constraints. The design begins with a compiler that lowers dataflow graphs to operator sequences parameterized by multiplicative depth L and rotation sets; it then chooses schemes and parameters—CKKS for floating-point style analytics and signal processing, BFV/BGV for integer operations and counters, TFHE-style bootstrapping for comparisons—that minimize the total time-to-result under explicit error and security budgets. A cryptographic key service supports threshold issuance and rotation-key escrow without learning plaintexts, while a storage layer packs columns into ciphertext SIMD lanes to amortize cost across tenants. For verifiability, we attach homomorphic message authentication tags to intermediate ciphertexts and wrap end-to-end executions in succinct non-interactive proofs specialized to the bilinear equations that certify correct key switching, rescaling, and boot- strapping. Analytically, we characterize latency by a linear model in the counts of core homomorphic primitives and show how to saturate GPUs or vector units with batched number-theoretic transforms to bend throughput toward practical regimes. Under realistic traces of analytic queries and encrypted inference, the architecture achieves sub-second P95 for circuits of depth six to eight with one or two bootstraps, while sustaining 128-bit security under RLWE. By treating HE not as an exotic afterthought but as a first-class cloud programming and scheduling primitive, the proposed approach demonstrates a path to confidential-by- default services in which the cloud never sees data in the clear yet remains efficient, elastic, and auditable.

Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate—the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography. More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. We also demonstrate several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding—all of which are classically identical—to have distinct or non-trivially equivalent complexity.

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: - A construction of collusion-resistant UTE from standard secret-key encryption (SKE). We additionally show that hyper-efficient shadow tomography (HEST) is impossible assuming collusion-resistant UTE exists. By considering a relaxation of collusion-resistant UTE, we are able to show the impossibility of HEST assuming only pseudorandom state generators (which may not imply one-way functions). This almost unconditionally answers an open inquiry of Aaronson (STOC 2018). - A construction of UTE from a quasi-polynomially secure one-shot message authentication code (OSMAC) in the classical oracle model, such that there is an explicit attack that breaks UE security for an unbounded polynomial number of decryptors. - A construction of everlasting secure collusion-resistant UTE, where the decryptor adversary can run in unbounded time, in the quantum random oracle model (QROM), and formal evidence that a construction in the plain model is a challenging task. We additionally show that HEST with unbounded post-processing time (which we call weakly-efficient shadow tomography) is impossible assuming everlasting secure collusion-resistant UTE exists. - A construction of secret sharing for all polynomial-size policies that is resilient to joint and unbounded classical leakage from collusion-resistant UTE and classical secret sharing for all policies. - A construction (and definition) of collusion-resistant untelegraphable secret-key functional encryption (UTSKFE) from single-decryptor functional encryption and plain secret-key functional encryption, and a construction of collusion-resistant untelegraphable public-key functional encryption from UTSKFE, plain SKE, and plain public-key functional encryption.

Recently, the concept of incompressible encryption has emerged as a powerful enhancement to key-leakage resilience. In an incompressible encryption scheme, an adversary who intercepts ciphertexts is forced to dedicate a significant amount of memory to store them in full if they wish to extract any information about the plaintext later when the secret key becomes available. Given two messages, the security game involves two adversaries: the first adversary receives an encryption of one of the messages and produces a compressed state. Then, the second adversary, given both the secret key and the compressed state, attempts to determine which message was encrypted. Several positive results exist in incompressible cryptography. On the one hand, there are constructions based on minimal assumptions but with a poor rate (i.e., rate tends to 0). On the other hand, there are rate-1 constructions that achieve optimal efficiency but rely on strong cryptographic assumptions, such as obfuscation. A stronger security notion, known as everlasting security, has been proposed for incompressible encryption. In this formulation, the second adversary, who receives the compressed state and the secret key, is allowed to be computationally unbounded. While this notion is conceptually appealing, no constructions of everlasting incompressible encryption are currently known, regardless of the underlying assumption or even in idealized models. In this work, we give the first construction of everlasting incompressible encryption. In fact, we show that everlasting incompressible encryption is inherent in any sufficiently secure public-key encryption scheme. Specifically, we prove that any public-key encryption scheme with subexponential security (when instantiated with an appropriate security parameter) already satisfies the definition of everlasting incompressible encryption with subexponential security. Furthermore, our scheme achieves rate-1, improving upon existing results even for the weaker notion of standard incompressible encryption. Our results raise concerns about whether the current definition of incompressible encryption adequately captures the expected efficiency properties of such schemes, indicating that refinements may be needed. As one concrete step in this direction, we propose a storage-rate definition for ciphertexts, and show how to construct schemes with constant storage-rate.

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.

The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption~(FHE), has relied on *cyclotomic* number fields and rings. This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on "packed" plaintexts, automorphisms, and ring-switching. However, selecting a suitable cyclotomic that has the desired number and type of plaintext "slots," while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency. This work provides a suite of tools for instantiating ring-based lattice cryptography to work over *subfields* of cyclotomics, which provide more flexibility and better-fitting parameters for applications. A particular focus is on realizing FHE with *optimal plaintext packing* and homomorphic SIMD parallelism for *any* plaintext characteristic, along with efficient *packed bootstrapping* that fully exploits this parallelism. Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory: -- For sampling and decoding errors in encryption and decryption (respectively), we construct geometrically short, structured bases for the number rings of arbitrary subfields of prime-power cyclotomics (and hence their composites as well). -- For fast ring arithmetic, we define and establish analogous structural properties for Chinese Remainder Theorem (CRT) bases in *abelian* number rings, and give specialized fast transforms that map between CRT bases and any similarly structured bases. -- For packed bootstrapping and homomorphic linear algebra, we give a general framework for *homomorphic evaluation of structured linear transforms* in abelian number rings, and show that CRT transforms can be evaluated using relatively few homomorphic operations.

We construct fully-homomorphic NIZKs from a broader range of cryptographic assumptions, including LWE, $O(1)$-LIN, and DDH (without circular security assumptions). Prior to this work, homomorphic NIZKs were only known based on pairing-based techniques. A key ingredient that we develop in this work is a new notion of a partially-hiding succinct delegation system, that we call encrypted RAM (eRAM) delegation. In addition to homomorphic NIZKs, we show that eRAM delegation is also useful for turning a semi-malicious multiparty computation (MPC) protocol into a full maliciously secure protocol in a communication-complexity-preserving manner (i.e., malicious and semi-malicious protocols have identical asymptotic communication complexity). Prior MPC compilers with similar efficiency required strong non-falsifiable assumptions. Furthermore, eRAM delegation also is useful for designing composable zero-knowledge batch arguments and multi-hop homomorphic signatures with strong-context-hiding.

When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity of finding a collision in a single-layer neural net, where a collision is defined as two distinct sets of weights that assign the same labels to all data. For binary perceptrons with oscillating activation functions, we establish the emergence of an overlap gap property in the space of collisions. This is a topological property believed to be a barrier to the performance of efficient algorithms. The hardness is supported by numerical experiments using approximate message passing algorithms, for which the algorithms stop working well below the value predicted by our analysis. Neural networks provide a new category of candidate collision resistant functions, which for some parameter setting depart from constructions based on lattices. Beyond relevance to cryptography, our work uncovers new forms of computational hardness emerging in large neural networks which may be of independent interest.

Directed Acyclic Graph (DAG)-based BFT consensus protocols often suffer from limited throughput and scalability due to bandwidth-intensive data replication to all participants. However, it is sufficient to replicate data to a smaller sub-committee of parties that holds an honest majority with high probability. In this work, we introduce tribe-assisted reliable broadcast, a novel primitive that ensures reliable broadcast (RBC) properties within a smaller honest-majority sub-committee—referred to as a clan—drawn from the entire network, called the tribe. Leveraging this primitive, we develop two efficient DAG-based BFT consensus protocols. First, we present a single-clan protocol, in which a single clan is elected from the tribe, and data is disseminated exclusively to this designated clan using tribe-assisted RBC. We then extend this design to a multi-clan setting, where multiple clans are elected and data is distributed within each respective clan via the same mechanism. Experimental results demonstrate that both protocols offer substantial improvements in throughput and latency over existing DAG-based BFT protocols, even at moderately large scales.

Pseudorandom codes (PRCs) are error-correcting codes with the distinguishing feature that their codewords are computationally indistinguishable from random strings. Introduced by Christ and Gunn (CRYPTO 2024), PRCs have found applications in areas such as AI watermarking, where both robustness and pseudorandomness are essential. All known constructions of PRCs rely on coding-theoretic hardness assumptions. In this work, we study how inherent the use of coding-theoretic hardness is in the construction of pseudorandom codes. We show that there is no black-box construction of PRCs with binary alphabets capable of decoding from a constant fraction of Bernoulli noise from a class of oracles we call local oracles. The class of local oracles includes random oracles and trapdoor permutation oracles, and can be interpreted as a meaningful notion of oracles that are not resilient against noise. Our separation result is cast in the Impagliazzo-Rudich framework and crucially relies on the Bonami-Beckner hypercontractivity theorem on the Boolean hypercube. As a complementary result, we show that PRCs with large alphabets that can tolerate high error rates can indeed be constructed in a black-box manner from one-way functions.

We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. 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.

We initiate the study of differentially private data-compression schemes motivated by the insecurity of the popular "Compress-Then-Encrypt" framework. Data compression is a useful tool which exploits redundancy in data to reduce storage/bandwidth when files are stored or transmitted. However, if the contents of a file are confidential then the length of a compressed file might leak confidential information about the content of the file itself. Encrypting a compressed file does not eliminate this leakage as data encryption schemes are only designed to hide the content of confidential message instead of the length of the message. In our proposed Differentially Private Compress-Then-Encrypt framework, we add a random positive amount of padding to the compressed file to ensure that any leakage satisfies the rigorous privacy guarantee of $(\epsilon,\delta)$-differential privacy. The amount of padding that needs to be added depends on the sensitivity of the compression scheme to small changes in the input, i.e., to what degree can changing a single character of the input message impact the length of the compressed file. While some popular compression schemes are highly sensitive to small changes in the input, we argue that effective data compression schemes do not necessarily have high sensitivity. Our primary technical contribution is analyzing the fine-grained sensitivity of the LZ77 compression scheme (IEEE Trans. Inf. Theory 1977) which is one of the most common compression schemes used in practice. We show that the global sensitivity of the LZ77 compression scheme has the upper bound $\mathcal{O}(W^{2/3}\log n)$ where $W\leq n$ denotes the size of the sliding window. When $W=n$, we show the lower bound $\Omega(n^{2/3}\log^{1/3}n)$ for the global sensitivity of the LZ77 compression scheme which is tight up to a sublogarithmic factor.

Non-interactive zero-knowledge proofs of knowledge (NIZKPoK) serve as a key building block in many important cryptographic protocols. In practice, NIZKPoK are often constructed from Sigma-protocols based on the discrete logarithm assumption, and proven secure in the random-oracle model (ROM). Recent work and standardization initiatives have highlighted the importance of concurrent security of NIZKPoK against adversaries who are capable of adaptive corruption. In this paper, we focus explicitly on Sigma-protocols from linear function families, which include those for proving discrete-logarithm based relations. We define a natural adaptivity property for this class of Sigma-protocols and show that, given any straight-line compiler which preserves the adaptivity property, it is possible to transform these protocols into adaptive, universally composable (UC) NIZKPoK in the global ROM. We then prove that the most efficient known construction of a straight-line compiler, Kondi and shelat's randomized version of Fischlin's transform, preserves the adaptivity property. Our construction avoids introducing any additional cryptographic primitives, and, following Kondi and shelat, requires only a polylogarithmic number of repetitions of the underlying Sigma-protocol.

Shannon’s 1949 theorem defines perfect secrecy as a condition where every possible message remains equally likely given any ciphertext, which requires a key at least as long as the message. This definition, while foundational, is binary and assumes uniform message priors—assumptions rarely met in real communication systems. It cannot express the fact that secrecy degrades gradually as key entropy decreases, and it does not account for semantic structure or contextual knowledge available to adversaries. This paper extends Shannon’s framework by introducing Operational Perfect Secrecy (OPS), which defines secrecy in terms of adversarial success probability rather than requiring complete message-space coverage. Within this framework we also define two new forms of information-theoretic security: Combinatorial ITS (C-ITS), which achieves OPS through combinatorial ambiguity of candidate decryptions, and Dimensional Ambiguity ITS (DA-ITS), which achieves OPS by concealing the dimensionality of the key space itself. We show that OPS converges to Shannon secrecy when the support size approaches the message space, while providing meaningful guarantees even with shorter keys. These results generalise the concept of perfect secrecy into a continuous, operational measure and establish a new theoretical foundation for scalable information-theoretic security.

The indifferentiability framework has become a standard methodology that enables us to study the security of cryptographic constructions in idealized models of computation. Unfortunately, while indifferentiability provides strong guarantees whenever the security of a construction is captured by a ``single-stage'' security game, it may generally provide no meaningful guarantees when the security is captured by a ``multi-stage'' one. In particular, the indifferentiability framework does not capture offline-online games, where the adversary can perform an extensive offline computation to later speed up the online phase. Such security games are extremely common, both in practice and in theory. Over the past decade, there has been numerous attempts to meaningfully extend the indifferentiability framework to offline-online games, however, they all ultimately met with little success. In this work, our contribution is threefold. First, we propose an extension of the classical indifferentiability framework, we refer to as *offline-online-indifferentiability*, that applies in the context of attackers with an expensive offline phase (á la Ghoshal and Tessaro, CRYPTO '23). Second, we show that our notion lends itself to a natural and meaningful composition theorem for offline-online security games. Lastly, as our main technical contribution, we analyze the offline-online-indifferentiability of two classical variants of the Merkle-Damg\aa rd hashing mechanism, one where the key is fed only to the first block in the chain and the other where the key is fed to each block in the chain. For both constructions, we prove a *tight* bound on their offline-online-indifferentiability (i.e., an upper bound and an attack that matches it). Notably, our bound for the second variant shows that the construction satisfies *optimal* offline-online-indifferentiability.

A relativized succinct argument in the random oracle model (ROM) is a succinct argument in the ROM that can prove/verify the correctness of computations that involve queries to the random oracle. We prove that relativized succinct arguments in the ROM do not exist. The impossibility holds even if the succinct argument is interactive, and even if soundness is computational (rather than statistical). This impossibility puts on a formal footing the commonly-held belief that succinct arguments require non-relativizing techniques. Moreover, our results stand in sharp contrast with other oracle models, for which a recent line of work has constructed relativized succinct non-interactive arguments (SNARGs). Indeed, relativized SNARGs are a powerful primitive that, e.g., can be used to obtain constructions of IVC (incrementally-verifiable computation) and PCD (proof-carrying data) based on falsifiable cryptographic assumptions. Our results rule out this approach for IVC and PCD in the ROM.

The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle. We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.

A weak pseudorandom function $F: \mathcal{K} \times \mathcal{X} \rightarrow \mathcal{Y}$ is said to be ring key-homomorphic if, given $F \left(k_{1}, x \right)$ and $F \left(k_{2}, x \right)$, there are efficient algorithms to compute $F \left(k_{1} \oplus k_{2}, x \right)$ and $F \left(k_{1} \otimes k_{2}, x \right)$ where $\oplus$ and $\otimes$ are the addition and multiplication operations in the ring $\mathcal{K}$, respectively. A recent work by Alamati et al. (CT-RSA' 23) initiated the study of ring key-homomorphic weak PRFs (RKHwPRFs) and showed that any RKHwPRF can be used to construct multiparty noninteractive key exchange (NIKE) for an arbitrary number of parties. In this work, we show that any RKHwPRF can, in fact, be used to construct indistinguishability obfuscation (iO) for all circuits in NC$^1$, which in turn can be bootstrapped to all polynomial-size circuits using standard techniques. The proof of security for our iO construction is in the standard model, and our assumptions (including weakenings of RKHwPRFs) are program-independent. We also consider restricted versions of RKHwPRFs that are structurally weaker than a classic RKHwPRF but suffice for all our constructions. We show how to instantiate these restricted RKHwPRFs from various multilinear maps and associated assumptions. Our framework gives several new results, notably the first iO scheme that relies on SXDH over the multilinear map presented by Ma and Zhandry (TCC' 18) (the authors only presented a NIKE protocol in their paper). To our knowledge, this candidate multilinear map has not been successfully cryptanalyzed, and the SXDH assumption plausibly holds over it. Our result in a sense completes the work initiated by Alamati et al. (Eurocrypt' 19, JoC '23) on building cryptosystems from generic Minicrypt primitives with structure. Given our construction of iO from RKHwPRFs, almost all of the major known cryptosystems can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space. Thus, a major contribution of this work is advancing the study of the relationship between structure and cryptography.

We resolve the Correlated Agreement (CA) problem for Reed-Solomon codes up to the information-theoretic capacity limit by introducing a fundamental change of basis: from the traditional evaluation domain to the syndrome space. Viewed through this “Syndrome-Space Lens,” the problem of proximity testing transforms into a transparent question of linear-algebraic geometry: a single affine line of syndromes traversing a family of low-dimensional subspaces. This new perspective makes a sharp phase transition at the capacity boundary visible, allowing for a complete characterization of the problem's behavior across all parameter regimes, yielding short, self-contained proofs. Classification. We establish a precise trichotomy organized by the rank margin $\Delta := t-d$. At the capacity boundary ($\Delta=0$), the CA premise is information-theoretically vacuous, and we prove that no rigidity can be concluded without imposing additional structure. One step beyond capacity ($\Delta=1$), the problem enters a “knife-edge” regime where unconditional rigidity does not hold; soundness is recovered either through a combinatorial witness (such as a repeated error support or a small union of supports) or by adding protocol-level structure (such as independent two-fold MCA checks, DEEP/STIR out-of-domain sampling, or a global error locator). For stricter gaps ($\Delta\ge 2$), unconditional rigidity holds under a simple algebraic condition ($(r{+}1)k<m{+}1$), with explicit quantitative bounds. MCA and Practical Implications. Below capacity ($\delta<1-\rho$), the strengthened mutual correlated agreement (MCA) problem reduces to ordinary correlated agreement. MCA holds under the same hypotheses as CA. When folds are generated with independent challenges (e.g., via domain-separated Fiat-Shamir), the per-round security margins add. The model-scoped soundness law is $\Pr[\mathrm{FA}] \le q^{-(\sum \Delta_i) s}$, providing a clear and complete rulebook for selecting safe and efficient parameters in FRI/STARK systems. This work bypasses the complex machinery of list-decoding algorithms entirely and resolves the long-standing open problem concerning the gap between the Johnson bound and capacity.

This manuscript introduces Semantic Holder (SH), the opposability primitive within the Chaotic Affine Secure Hash (CASH) toolkit, completing the framework’s implementation of the Q2CSI philosophy. SH enables legally opposable interpretations through algebraic extraction from polynomial iteration traces, working in concert with CEE (confidentiality) and AOW (reliability). Building upon the Affine Iterated Inversion Problem (AIIP) foundation, SH provides mathematically verifiable legal interpretations with guaranteed minimum opposability bounds. We establish that SH maintains an opposability score Ω ≥ 0.60 through rigorous entropy preservation, institutional explainability, and legal contestability guarantees. The primitive features efficient STARK-proof verifiable computation, cross-jurisdictional compatibility, and quantum resistance through its reduction to AIIP hardness. We demonstrate practical applications in legal smart contracts, regulatory compliance auditing, and digital evidence authentication, providing concrete parameter recommendations for standard security levels. SH represents a significant advancement in cryptographic systems that must operate within legal constraints, enabling transparent and verifiable legal opposability without compromising security or performance.

In 1997, Kani proved Kani's lemma, which asserts that a commutative diagram of four $g$‑dimensional abelian varieties induces an isogeny between product abelian varieties of dimension $2g$, in counting the number of genus-$2$ curves admitting two distinct elliptic subcovers. In these years, Kani’s lemma plays a fundamental role in isogeny-based cryptography: Kani’s lemma has found numerous cryptographic applications, including both cryptanalysis and protocol construction. However, direct investigation into the lemma itself remains scarce. In this work, we propose a generalization of Kani’s lemma. We present a novel formulation that, given a commutative diagram of $2^{n+1}$ abelian varieties of dimension $g$, yields an isogeny of dimension $2^{n}g$. We further establish a connection between this generalized lemma and the theory of Clifford algebras, using the latter as a foundational tool in our construction. To exemplify our framework, we explicitly construct the resulting $2^{n}g$‑dimensional isogenies for the cases $n=1,2,3$. The cases of $n=2,3$ provide nontrivial generalizations of the original Kani's lemma. This generalization is expected to have novel applications in the fields of both mathematics and cryptography.

We present a formally-verified (in Lean 4) framework for translating symbolic cryptographic proofs into the computationally-sound ones. Symbolic cryptography is a well-established field that allows reasoning about cryptographic protocols in an abstract way and is relatively easy to verify using proof assistants. Unfortunately,  it often lacks a connection to the computational aspects of real-world cryptography. Computationally-sound cryptography, on the other hand, captures this connection much better, but it is often more complex, less accessible, and much harder to verify formally. Several works in the past have provided a bridge between the two, but, to our knowledge, none of them have been implemented in a proof assistant. We close this gap by formalizing the translation from symbolic to computationally-sound cryptography in Lean 4. Our framework is based on the work of Micciancio (Eurocrypt, 2010) and Li and Micciancio (CSF, 2018), which builds on the idea of using co-induction (instead of induction) for reasoning about an adversary's knowledge in a symbolic setting. Our work encompasses (1) the formalization of the symbolic cryptography framework, (2) the formalization of the computationally sound cryptography framework, and (3) the formalization of the translation between the two. We also provide (4) an extended example of circuit garbling, which is a well-known cryptographic protocol frequently used in secure multi-party computation. We believe that our work will serve as a foundation for future research in the area of formal verification of cryptographic protocols, as it enables reasoning about cryptographic protocols more abstractly while still providing a formally verified connection to the computational aspects of real-world cryptography.

We introduce modular forms and Hecke operators to cryptography and propose the Hecke problem as a new foundation for post-quantum cryptography. Given two modular forms, the Hecke problem asks to recover the Hecke operator that maps one to the other. While there is a deep relation to isogeny problems through the modularity theorem, this problem is rooted in arithmetic geometry and differs fundamentally in structure and mechanism. We prove NP-hardness of this problem and use it to construct a non-interactive key exchange scheme that achieves higher efficiency than isogeny-based schemes and smaller key sizes than lattice-based and code-based schemes.

Users bid in a transaction fee mechanism (TFM) to get their transactions included and confirmed by a blockchain protocol. Roughgarden (EC'21) initiated the formal treatment of TFMs and proposed three requirements: user incentive compatibility (UIC), miner incentive compatibility (MIC), and a form of collusion-resilience called OCA-proofness. Ethereum's EIP-1559 mechanism satisfies all three properties simultaneously when there is no contention between transactions, but loses the UIC property when there are too many eligible transactions to fit in a single block. Chung and Shi (SODA'23) considered an alternative notion of collusion-resilience, called $c$-side-contract-proofness ($c$-SCP), and showed that, when there is contention between transactions, no TFM can satisfy UIC, MIC, and $c$-SCP for any $c\geq 1$. OCA-proofness asserts that the users and a miner should not be able to ``steal from the protocol.'' On the other hand, the $c$-SCP condition requires that a coalition of a miner and a subset of users should not be able to profit through strategic deviations (whether at the expense of the protocol or of the users outside the coalition). Our main result is the first proof that, when there is contention between transactions, no (possibly randomized) TFM in which users are expected to bid truthfully satisfies UIC, MIC, and OCA-proofness.This result resolves the main open question in Roughgarden (EC'21). We also suggest several relaxations of the basic model that allow our impossibility result to be circumvented.

In the $k$-Orthogonal Vectors ($k$-OV) problem we are given $k$ sets, each containing $n$ binary vectors of dimension $d=n^{o(1)}$, and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured to require $n^{k-o(1)}$ time in the worst case. We propose a way to plant a solution among vectors with i.i.d. $p$-biased entries, for appropriately chosen $p$, so that the planted solution is the unique one. Our conjecture is that the resulting $k$-OV instances still require time $n^{k-o(1)}$ to solve, on average. Our planted distribution has the property that any subset of strictly less than $k$ vectors has the same marginal distribution as in the model distribution, consisting of i.i.d. $p$-biased random vectors. We use this property to give average-case search-to-decision reductions for $k$-OV.

Distributed systems require robust, transparent mechanisms for verifiable temporal ordering to operate without trusted authorities or synchronized clocks. This paper introduces Affine One-Wayness (AOW), a new cryptographic primitive for post-quantum temporal verification based on iterative polynomial evaluation over finite fields. AOW provides strong temporal binding guarantees by reducing its security with a tight reduction to the hardness of the dis crete logarithm problem in high-genus hyperelliptic curves (HCDLP) and with a reduction to the Affine Iterated Inversion Problem (AIIP), which possesses dual foundations in multivariate quadratic algebra and the arithmetic of high-genus hyperelliptic curves. We present a con struction with transparent setup and prove formal security against both classical and quantum adversaries. Furthermore, we demonstrate efficient integration with STARK proof systems for zero-knowledge verification of sequential computation with logarithmic scaling. As the core reliability component of the Chaotic Affine Secure Hash (CASH) framework, AOW enables practical applications in Byzantine-resistant event ordering and distributed synchronization with provable security guarantees under standard cryptographic assumptions.

Public-coin protocols are cryptographic protocols in which all messages sent by a specific party (typically the receiver or verifier) consist solely of random bits. These protocols have been extensively studied $\textit{in the classical setting}$ due to their advantageous properties in several scenarios, such as the parallel repetition of interactive arguments, and the design of secure multi-party computation with low round complexity, among others. Curiously, $\textit{post-quantum}$ constructions of public-coin protocols remain limited, particularly when optimization is sought in additional factors like round complexity or hardness assumptions. We introduce the concept of $\textit{almost-total puzzles}$, a novel cryptographic primitive characterized by two key properties: (i) hardness against any efficient adversary, and (ii) an "almost-total" guarantee of the existence of solutions, even when the puzzle generator is malicious. We demonstrate that this primitive can be derived from one-way functions in public-coin, requiring only two rounds. By leveraging this primitive, we obtain a family of new $\textit{public-coin}$ results in both the classical and post-quantum settings, based on the $\textit{minimal assumption} $ of (post-quantum) one-way functions, including: - five-round post-quantum extractable commitments and witness-indistinguishable arguments of knowledge, where the (knowledge) extractors achieve the $\textit{coherently expected quantum-polynomial-time}$ ($\mathsf{EQPT}_c$) simulation proposed by Lombardi, Ma, and Spooner [FOCS'22]; - five-round classical extractable commitments that $\textit{do not suffer from over extraction}$; - five-round classical delayed-input strong witness-indistinguishable arguments of knowledge, and delayed-input witness-hiding arguments of knowledge; - the five-round post-quantum analogue of the last item, but with the difference that (1) the input can be delayed until the third round, and (2) post-quantum arguments of knowledge are again defined w.r.t. $\mathsf{EQPT}_c$-simulation; - $O(\log^* \lambda)$-round post-quantum non-malleable commitments.

We give a new approach for constructing statistical ZAP arguments (a two-message public-coin statistically witness indistinguishable argument) from quasi-polynomial hardness of the learning with errors (LWE) assumption with a polynomial modulus-to-noise ratio. Previously, all ZAP arguments from lattice-based assumptions relied on correlation-intractable hash functions. In this work, we present the first construction of a ZAP from LWE via the classic hidden-bits paradigm. Our construction matches previous lattice-based schemes by being public-coin and satisfying statistical witness indistinguishability.

Witness encryption allows one to encrypt a message to an $\mathsf{NP}$ relation $\mathcal{R}$ and a statement $x$. The corresponding decryption key is any valid $\mathsf{NP}$ witness $w$. In a succinct witness encryption scheme, we require that the size of the ciphertext be sublinear in the size of the $\mathsf{NP}$ relation. Currently, all realizations of succinct witness encryption for $\mathsf{NP}$ rely on strong assumptions such as pseudorandom obfuscation, extractable witness encryption, or differing-inputs obfuscation. Notably, none of these notions are known from standard assumptions. In this work, we consider a relaxation of succinct witness encryption for $\mathsf{NP}$ to the setting of batch $\mathsf{NP}$. In this setting, one encrypts to an $\mathsf{NP}$ relation $\mathcal{R}$ together with $K$ statements $x_1, \ldots, x_K$. In the basic version, one can decrypt if they have a witness $w_1, \ldots, w_K$ for all $K$ statements. The succinctness requirement is that the size of the ciphertext should be sublinear in the number of instances $K$, but is allowed to grow with the size of the $\mathsf{NP}$ relation (i.e., the size of a single instance). More generally, we can also impose a (monotone) policy $P \colon \{0,1\}^K \to \{0,1\}$ over the $K$ instances. In this case, decryption is possible only if there exists $w_1, \ldots, w_K$ such that $P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_K, w_K)) = 1$. In this work, we initiate a systematic study of succinct witness encryption for batch languages. We start with two simple constructions that support CNF and DNF policies based on plain witness encryption in conjunction with a somewhere statistically sound batch argument for $\mathsf{NP}$ or a function-binding hash function. Then, using indistinguishability obfuscation, we show how to support policies that can be computed by read-once bounded-space Turing machines. The latter construction is in fact a unique witness map for monotone-policy batch $\mathsf{NP}$, and as such, also gives a SNARG for monotone-policy batch $\mathsf{NP}$ where the size of the common reference string is sublinear in the number of instances. Finally, we demonstrate some immediate applications of succinct witness encryption for batch languages. We construct new succinct computational secret sharing schemes for CNFs, DNFs, and weighted threshold policies. We also show how to build distributed monotone-policy encryption, a notion that generalizes recent trustless primitives like distributed broadcast encryption and threshold encryption with silent setup.

The Legendre signature of an integer $x$ modulo a prime~$p$ with respect to offsets $\vec 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 $\vec 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.

In this paper, we present an improved framework for proving query bounds in the Quantum Random Oracle Model (QROM) for algorithms with both quantum and classical query interfaces, where the classical input is partially controlled by the adversary. By extending existing techniques, we develop a method to bound the progress an adversary can make with such partial-control classical queries. While this framework is applicable to different hash function properties, we decided to demonstrate the impact of the new techniques by giving an analysis of the multi-target extended target collision resistance property (m-eTCR). This new approach allows us to achieve an improved bound that significantly reduces the required function key size. Our proof is tight in terms of query complexity and has significant implications for cryptographic applications, especially for signature schemes in the hash & sign paradigm, enabling more efficient instantiations with reduced salt sizes and smaller signature lengths. For an example of multiple signatures aggregation, we achieve a signature size of 30 kB smaller.

The Hermite Normal Form (HNF) of a matrix is an analogue of the echolon form over the integers. A common obstacle in computing the HNF is the extensive blow up of intermediate values. We survey algorithms, deterministically computing the HNF. After presenting a naive algorithm, we discuss the MODULO DETERMINANT ALGORITHM from [DKT87]. It keeps the entries bounded by d, the determinant of the lattice, and has a time complexity of O(n^3 log2 d), where n is the dimension of the matrix. Although this algorithm is very useful if the determinant is small, in the general case the entries still become extremely large. Secondly, we survey the LINEAR SPACE ALGORITHM from [MW01]. It has a time complexity of O(n^5 polylog(M, n)), where M denotes the largest absolute value of the input matrix. This is as fast as the best previously known algorithms, but in contrast, it assures space complexity linear in the input size, i.e. O(n^2 log M). As last algorithm to compute the HNF we discuss the HEURISTIC ALGORITHM from [MW01], which is based on the first two algorithms. It achieves a much faster runtime in practice, yielding a heuristic runtime of O(n^4 polylog(M, n)), while keeping the linear space complexity.

Weintroduce the Chaotic Entropic Expansion (CEE), a new one-way function based on iterated polynomial maps over finite fields. For polynomials f in a carefully defined class Fd, we prove that N iterations preserve min-entropy of at least log2q − N log2d bits and achieve statistical distance ≤ (q − 1)(dN − 1)/(2√q) from uniform. We formalize security through the Affine Iterated Inversion Problem (AIIP) and provide reductions to the hardness of solving multivariate quadratic equations (MQ) and computing discrete logarithms (DLP). Against quantum adversaries, CEE achieves O(2λ/2) security for λ-bit classical security. We provide comprehensive cryptanalysis and parameter recommendations for practical deployment. While slower than AES, CEE’s algebraic structure enables unique applications in verifiable computation and post-quantum cryptography within the CASH framework.

When investigating the round-complexity of multi-party computation protocols (MPC) protocols, it is common to assume that in each round parties can communicate over broadcast channels. However, broadcast is an expensive resource, and as such its use should be minimized. For this reason, Cohen, Garay, and Zikas (Eurocrypt 2020) investigated the tradeoffs between the use of broadcast in two-round protocols assuming setup and the achievable security guarantees. Despite the prolific line of research that followed the results of Cohen, Garay, and Zikas, none of the existing results considered the problem of minimizing the use of broadcast while relying in a 𝑏𝑙𝑎𝑐𝑘-𝑏𝑜𝑥 way on the underlying cryptographic primitives. In this work, we fully characterize the necessary and sufficient requirements in terms of broadcast usage in the 𝑑𝑖𝑠ℎ𝑜𝑛𝑒𝑠𝑡 𝑚𝑎𝑗𝑜𝑟𝑖𝑡𝑦 setting for round-optimal MPC with black-box use of minimal cryptographic assumptions. Our main result shows that to securely realize any functionality with 𝑢𝑛𝑎𝑛𝑖𝑚𝑜𝑢𝑠 𝑎𝑏𝑜𝑟𝑡 in the common reference string model with black-box use of two-round oblivious transfer it is necessary and sufficient for the parties to adhere to the following pattern: in the first two rounds the parties exchange messages over peer-to-peer channels, and in the last round the messages are sent over a broadcast channel. We also extend our results to the correlated randomness setting where we prove that one round of peer-to-peer interaction and one round of broadcast is optimal to evaluate any functionality with unanimous abort.

Semantic communication systems focus on the transmission of meaning rather than the exact reconstruction of data, reshaping communication network design to achieve transformative efficiency in latency-sensitive and bandwidth-limited scenarios. Within this context, we investigate the rate-distortion-perception (RDP) problem for image compression, which plays a central role in producing perceptually realistic outputs under rate constraints. By employing the randomized distributed function computation (RDFC) framework, we derive an achievable non-asymptotic RDP region that captures the finite blocklength trade-offs among rate, distortion, and perceptual quality, aligning with the objectives of semantic communications. This region is further generalized to include either side information or a secrecy requirement, the latter ensuring strong secrecy against eavesdroppers through physical-layer security mechanisms and maintaining robustness in the presence of quantum-capable adversaries. The main contributions of this work are: (i) achievable bounds for non-asymptotic RDP regions subject to realism and distortion constraints; (ii) extensions to cases where side information is available at both the encoder and decoder; (iii) achievable, nonasymptotic RDP bounds with strong secrecy guarantees; (iv) characterization of the asymptotic secure RDP region under a perfect realism constraint; and (v) demonstrations of significant rate reductions and the effects of finite blocklengths, side information, and secrecy constraints. These findings offer concrete guidelines for the design of low-latency, secure, and high-fidelity image compression and generative modeling systems that generate realistic outputs, with relevance for, e.g., privacy-critical applications.

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness $−$ the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle (STOC 2013) give worst-case to average-case reductions from lattice problems to LWE, specifically from the approximate decision variant of the Shortest Vector Problem (GapSVP) and the Bounded Distance Decoding (BDD) problem. These reductions, however, are lossy in the sense that even the strongest assumption on the worst-case hardness of GapSVP or BDD implies only mild hardness of LWE. Our alternative perspective gives a much tighter reduction and strongly relates the hardness of LWE to that of BDD. In particular, we show that under a reasonable assumption about the success probability of solving BDD via a PPT algorithm, we obtain a nearly tight lower bound on the highest possible success probability for solving LWE via a PPT algorithm. Furthermore, we show a tight relationship between the best achievable success probability by any probabilistic polynomial-time algorithm for decision-LWE to that of search-LWE. Our results not only refine our understanding of the computational complexity of LWE, but also provide a useful framework for analyzing the practical security implications.

At Eurocrypt 2003, Szydlo presented a search to distinguish reduction for the Lattice Isomorphism Problem (LIP) on the integer lattice $\mathbb{Z}^n$. Here the search problem asks to find an isometry between $\mathbb{Z}^n$ and an isomorphic lattice, while the distinguish variant asks to distinguish between a list of auxiliary lattices related to $\mathbb{Z}^n$. In this work we generalize Szydlo's search to distinguish reduction in two ways. Firstly, we generalize the reduction to any lattice isomorphic to $\Gamma^n$, where $\Gamma$ is a fixed base lattice. Secondly, we allow $\Gamma$ to be a module lattice over any number field. Assuming the base lattice $\Gamma$ and the number field $K$ are fixed, our reduction is polynomial in $n$. As a special case we consider the module lattice $\mathcal{O}_K^2$ used in the module-LIP based signature scheme HAWK, and we show that one can solve the search problem, leading to a full key recovery, with less than $2d^2$ distinguishing calls on two lattices each, where $d$ is the degree of the power-of-two cyclotomic number field and $\mathcal{O}_K$ its ring of integers.

Accumulation schemes are powerful primitives that enable distributed and incremental verifiable computation with less overhead than recursive SNARKs. However, most existing schemes with constant-size accumulation verifiers suffer from linear-sized accumulators and deciders, leading to unsuitable linear-sized proofs in distributed settings such as accountable voting protocols. Our contributions are as follows: I) We introduce KZH, a novel multilinear polynomial commitment scheme (PCS) with sublinear opening and KZH-fold, a polynomial accumulation (PA) scheme where the verifier only does $3$ group scalar multiplications and $O(n^{1/2})$ accumulator size and decider time. Our scheme generalizes to achieve accumulator and decider complexity of $O(k \cdot n^{1/k})$ while a verifier complexity $O(k)$. 2) As an orthogonal contribution to KZH-fold, we build an IVC (PCD) scheme for R1CS via Spartan+PA, in which instantiated with KZH-fold, i.e. Spartan+KZH-fold results in a sublinear proof and decider. With the recipe of Spartan+PA, we build non-uniform IVC and non-uniform PCD. Our non-uniform PCD is the first approach in which the prover's computation and communication at each step and grow sublinearly with the combined circuit size of all instructions. This approach can be instantiated with any PA and doesn't depend on KZH-fold. 3) We demonstrate the power of Spartan+KZH-fold by implementing an accountable voting scheme using a novel signature aggregation protocol supporting millions of participants, significantly reducing communication overhead and verifier time compared to BLS-based aggregation. We implemented and benchmarked our protocols, Spartan+KZH-fold achieves a 2000x reduction in communication and a 50x improvement in decider time over Nova when proving 2000 Poseidon hashes, at the cost of 3x the prover time.

Maximum distance separable (MDS) matrices are the main building blocks that provide the maximum possible diffusion in several block ciphers and cryptographic hash functions. In addition to using MDS matrices directly, there are also some indirect but simple and efficient methods that provide the maximum possible diffusion property. In particular, the subfield construction introduced by Barreto et al. in [DCC 56 (2-3) 141-162 (2010)] and its generalization examined by Otal in [IJISS 11 (2) 1-11 (2022)] make use of MDS matrices over smaller finite fields to provide the maximum possible diffusion property over larger finite fields. ZK-friendly hash functions, in contrast to the classical cryptographic hash functions, use higher-dimensional MDS matrices over larger finite fields. In this paper, we examine the applicability of the generalized subfield construction and the possibility of improvements on ZK-friendly hash functions. As a case study, we focus on a recent ZK-friendly hash function Vision Mark-32 presented by Ashur et al. in [IACR Preprint 2024/633]. In particular, instead of using a $24\times 24$ MDS matrix over $\mathbb{F}_{2^{32}}$ for a $24\times 1$ column input over $\{0,1\}^{{32}}$, we suggest separating the $24\times 1$ column input over $\{0,1\}^{{32}}$ into four $24\times 1$ subcolumns over $\{0,1\}^{{8}}$ and then using a $24\times 24$ MDS matrix over $\mathbb{F}_{2^8}$ for each subcolumn. This method still keeps the maximum diffusion property without any compromise and provides simplicity and efficiency. For example, it is possible to significantly decrease the required LUT values to 265 from about 9200 and FF values to 102 from about 4600 for the hardware implementation. We also highlight that we do not need any additional tricks such as NTT for field multiplications. We also push the theoretical boundaries of the generalized subfield construction to see how much small finite fields we can use, examine the arithmetization complexity, and discuss its applicability to other ZK-friendly hash functions.

We introduce the Affine Iterated Inversion Problem (AIIP), a new candidate hard problem for post-quantum cryptography, based on inverting iterated polynomial maps over finite fields. Given a polynomial f ∈ Fq[x] of degree d ≥ 2, an iteration parameter n, and a target y ∈ Fq, AIIP requires finding an input x such that f(n)(x) = y, where f(n) denotes the n-fold composi tion of f. We establish the computational hardness of AIIP through two independent analytical frameworks: first, by establishing a formal connection to the Discrete Logarithm Problem in the Jacobian of hyperelliptic curves of exponentially large genus; second, via a polynomial time reduction to solving structured systems of multivariate quadratic (MQ) equations. The f irst construction provides number-theoretic evidence for hardness by embedding an AIIP in stance into the arithmetic of a high-genus curve, while the second reduction proves worst-case hardness relative to the NP-hard MQ problem. For the quadratic case f(x) = x2 + α, we show that the induced MQ system is heuristically indistinguishable from a random system, and we formalize a sufficient condition for its pseudorandomness under a standard cryptographic assumption. We provide a detailed security analysis against classical and quantum attacks, derive concrete parameters for standard security levels, and discuss the potential of AIIP as a foundation for digital signatures and public-key encryption. This dual hardness foundation, rooted in both algebraic geometry and multivariate algebra, positions AIIP as a versatile and promising primitive for post-quantum cryptography.

AES-GCM has seen great adoption for the last 20 years to protect data in various use-cases because of its optimal performance. It has also posed some challenges to modern applications due to its nonce, block size, and lack of key commitment. Nonce-derived schemes address these challenges by deriving a different key from random values and using GCM with the derived key. In this work, we explore efficient key commitment methods for nonce-derived schemes. For concreteness, we focus on expanding XAES-256-GCM, a derived key scheme originally introduced by Filippo Valsorda. We propose an efficient CMAC-based key commitment solution, and prove its security in the ideal-cipher model. This proposal yields a FIPS-compliant mode and offers much better data bounds than GCM. Finally, we benchmark the new mode's performance to demonstrate that the additional cost affects mostly small plaintexts.

This paper addresses the question of how many distinct Montgomery curves exist over a finite field $\mathbb{F}_p$ for a given order. We provide a complete answer by presenting precise counting formulas from two perspectives: (1) the number of $\mathbb{F}_p$-isomorphism classes, and (2) the number of coefficient pairs $(A,B)$. Additionally, we propose conjectural formulas that approximate the probability of a randomly chosen curve having an order with a specific, cryptographically relevant structure. As a byproduct of our methods, we also establish a novel identity for the Kronecker-Hurwitz class number.

We study the inherent limitations of additive accumulators and updatable vector commitments (VCs) with constant-size digest (i.e., independent of the number of committed elements). Specifically, we prove two lower bounds on the expected number of membership proofs that must be updated when a \emph{single} element is added (or updated) in such data structures. Our results imply that when the digest bit length approaches the concrete security level, then the expected number of proofs invalidated due to an append operation for a digest committing to $n$ elements is nearly maximal: $n-\mathsf{negl}(\lambda)$ in the case of exponential-size universes, and $n-o(n)$ for super-polynomial universes. Our results have significant implications for stateless blockchain designs relying on constant-size VCs, suggesting that the overhead of frequent proof updates may offset the benefits of reducing global state storage.

Collision resistance and collision finding are now extensively exploited in Cryptography, especially in the case of quantum computing. For any function $f:[M]\to[N]$ with $f(x)$ uniformly distributed over $[N]$, Zhandry has shown that the number $\Theta(N^{1/3})$ of queries is both necessary and sufficient for finding a collision in $f$ with constant probability. However, there is still a gap between the upper and the lower bounds of query complexity in general non-uniform distributions. In this paper, we investigate the quantum query complexity of collision-finding problem with respect to general non-uniform distributions. Inspired by previous work, we pose the concept of collision domain and a new parameter $\gamma$ that heavily depends on the underlying non-uniform distribution. We then present a quantum algorithm that uses $O(\gamma^{1/6})$ quantum queries to find a collision for any non-uniform random function. By making a transformation of a problem in non-uniform setting into a problem in uniform setting, we are also able to show that $\Omega(\gamma^{1/6}\log^{-1/2}\gamma)$ quantum queries are necessary in collision-finding in any non-uniform random function. The upper bound and the lower bound in this work indicates that the proposed algorithm is nearly optimal with query complexity in general non-uniform case.

One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security. In this work, we present new, meaningful, yet achievable definitions of one-time program security for *probabilistic* classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.

We study a secondary construction of Boolean functions, which generalizes the direct sum and the indirect sum. We detail how these two classic secondary constructions are particular cases of this more general one, as well as two known generalizations of the indirect sum. This unifies the known secondary constructions of Boolean functions. We study very precisely the Walsh transform of the constructed functions. This leads us to an interesting observation on the Walsh transforms $W_g,W_{g'},W_{g''}$, and $W_{g\oplus g'\oplus g''}$ when $g,g',g''$ are Boolean functions such that $(g\oplus g')(g\oplus g'')$ equals the zero function.

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, ${\rm K}^t$, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: * We show, perhaps surprisingly, that the $\rm KT$ complexity is bounded-error average-case hard if and only if there exist one-way functions in *constant parallel time* (i.e., ${\sf NC}^0$). This result crucially relies on the idea of *randomized encodings*. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that ${\sf NC}^0$-computable one-way functions exist if and only if logspace-computable one-way functions exist. * Inspired by the above result, we present randomized average-case reductions among the ${\sf NC}^1$-versions and logspace-versions of ${\rm K}^t$ complexity, and the $\rm KT$ complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the $\rm KT$ complexity and a variant of ${\rm K}^{\rm poly}$ complexity. * We prove tight connections between the hardness of ${\rm K}^t$ complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the *Perebor Hypotheses* for complexity measures such as ${\rm K}^t$ and $\rm KT$. We show that a Strong Perebor Hypothesis for ${\rm K}^t$ implies the existence of (weak) one-way functions of near-optimal hardness $2^{n-o(n)}$. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem. * We show that a Weak Perebor Hypothesis for ${\rm MCSP}$ implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of ${\rm MCSP}$ over a natural distribution. * Finally, we study the average-case hardness of ${\rm MKtP}$. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.

We strengthen Kaneko's bound to prove that, away from the $j$-invariant $0$, edges of multiplicity at least three can occur in the supersingular $\ell$-isogeny graph $\mathcal{G}_\ell(p)$ only if the base field's characteristic satisfies $p < 4\ell^3$. Further we prove a diameter bound for $\mathcal{G}_\ell(p)$, while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko's bound to deduce that the distance of $0$ and $1728$ in $\mathcal{G}_\ell(p)$ is at least one fourth of the graph's diameter if $p \equiv 11 \mathrel{\operatorname{mod}} 12$. We also study other phenomena in $\mathcal{G}_\ell(p)$ with Kaneko's bound and provide data to demonstrate that the resulting bounds are optimal; for one of these bounds we investigate the connection between loop multiplicities in isogeny graphs and the factorization of the `diagonal' classical modular polynomial $\Phi_\ell(X,X)$ in positive characteristic.

The hardness of Kolmogorov complexity is intricately connected to the existence of one-way functions and derandomization. An important and elegant notion is Levin's version of Kolmogorov complexity, \(\mathsf{Kt}\), and its decisional variant, \(\mathsf{MKtP}\). The question whether \(\mathsf{MKtP}\) can be computed in polynomial time is particularly interesting because it is not subject to known technical barriers such as algebrization or natural proofs that would explain the lack of a proof for \(\mathsf{MKtP} \not\in \mathsf{P}\). We take a major step towards proving \(\mathsf{MKtP} \not\in \mathsf{P}\) by developing a novel yet simple diagonalization technique to show unconditionally that \(\mathsf{MKtP} \not \in \mathsf{DTIME}[O(n)]\), i.e., no deterministic linear-time algorithm can solve \(\mathsf{MKtP}\) on every instance. This allows us to affirm a conjecture by Ren and Santhanam [STACS:RS22] about a non-halting variant of \(\mathsf{Kt}\) complexity. Additionally, we give conditional lower bounds for \(\mathsf{MKtP}\) that tolerate either more runtime or one-sided error. If the underlying computational model has a linear-time universal simulation, e.g.\ random-access machines, then we obtain a quadratic lower bound, i.e., \(\mathsf{MKtP} \not\in \mathsf{DTIME}[O(n^2)]\).

We show the key ideas of the above-referenced work for lattice Gaussian sampling are not new; the same ideas have been proposed by Ling et al. in 2014.

Asynchronous byzantine agreement extension studies the message complexity of $L$-bit multivalued asynchronous byzantine agreement given access to a binary asynchronous Byzantine agreement protocol. We prove that asynchronous byzantine agreement extension can be solved with perfect security and optimal resilience in $O(nL+n^2 \log n)$ total communication (in bits) in addition to a single call to a binary asynchronous Byzantine agreement protocol. For $L = O(n \log n)$, this gives an asymptotically optimal protocol, resolving a question that remained open for nearly two decades. List decoding is a fundamental concept in theoretical computer science and cryptography, enabling error correction beyond the unique decoding radius and playing a critical role in constructing robust codes, hardness amplification, and secure cryptographic protocols. A key novelty of our perfectly secure and optimally resilient asynchronous byzantine agreement extension protocol is that it uses list decoding - making a striking new connection between list decoding and asynchronous Byzantine agreement.

The $k$LIN problem concerns solving noisy systems of random sparse linear equations mod 2. It gives rise to natural candidate hard CSP distributions and is a cornerstone of local cryptography. Recently, it was used in advanced cryptographic constructions, under the name 'sparse LPN'. For constant sparsity $k$ and inverse polynomial noise rate, both search and decision versions of $k$LIN are statistically possible and conjectured to be computationally hard for $n\ll m\ll n^{k/2}$, where $m$ is the number of $k$-sparse linear equations, and $n$ is the number of variables. We show an algorithm that given access to a distinguisher for $(k-1)$LIN with $m$ samples, solves search $k$LIN with roughly $O(nm)$ samples. Previously, it was only known how to reduce from search $k$LIN with $O(m^3)$ samples, yielding meaningful guarantees for decision $k$LIN only when $m \ll n^{k/6}$. The reduction succeeds even if the distinguisher has sub-constant advantage at a small additive cost in sample complexity. Our technique applies with some restrictions to Goldreich's function and $k$LIN with random coefficients over other finite fields.

A common misconception is that the computational abilities of circuits composed of additions and multiplications are restricted to simple formulas only. Such arithmetic circuits over finite fields are actually capable of computing any function, including equality checks, comparisons, and other highly non-linear operations. While all those functions are computable, the challenge lies in computing them efficiently. We refer to this search problem as arithmetization. Arithmetization is a key problem in secure computation, as techniques like homomorphic encryption and secret sharing compute arithmetic circuits rather than the high-level programs that programmers are used to. The objective in arithmetization has typically been to minimize the number of multiplications (multiplicative size), as multiplications in most secure computation techniques are significantly more expensive to compute than additions. However, the multiplicative depth of a circuit arguably plays an even more important role in deciding the computational cost: For homomorphic encryption, it strongly affects the choice of cryptographic parameters and the number of bootstrapping operations required, which are orders of magnitude more expensive to compute than multiplications. In fact, if we can limit the multiplicative depth of a circuit such that we do not need to perform any bootstrapping, we can omit the large bootstrapping keys required to perform them all together. We argue that arithmetization should be treated as a multi-objective minimization problem, in which a trade-off can be made between a circuit's multiplicative size and depth. We present efficient depth-aware arithmetization methods for many primitive operations such as exponentiation, univariate functions, equality checks, comparisons, and ANDs and ORs, which take into account that squaring can be cheaper than arbitrary multiplications, and we study how to compose them.

An $(\epsilon_\mathsf{s},\epsilon_{\mathsf{zk}})$-weak non-interactive zero knowledge (NIZK) argument has soundness error at most $\epsilon_\mathsf{s}$ and zero-knowledge error at most $\epsilon_{\mathsf{zk}}$. We show that as long as $\mathsf{NP}$ is hard in the worst case, the existence of an $(\epsilon_\mathsf{s}, \epsilon_{\mathsf{zk}})$-weak NIZK proof or argument for $\mathsf{NP}$ with $\epsilon_{\mathsf{zk}} + \sqrt{\epsilon_\mathsf{s}} < 1$ implies the existence of one-way functions. To obtain this result, we introduce and analyze a strong version of universal approximation that may be of independent interest. As an application, we obtain NIZK amplification theorems based on very mild worst-case complexity assumptions. Specifically, [Bitansky-Geier, CRYPTO'24] showed that $(\epsilon_\mathsf{s}, \epsilon_{\mathsf{zk}})$-weak NIZK proofs (with $\epsilon_\mathsf{s}$ and $\epsilon_{\mathsf{zk}}$ constants such that $\epsilon_\mathsf{s} + \epsilon_{\mathsf{zk}} < 1$) can be amplified to make their errors negligible, but needed to assume the existence of one-way functions. Our results can be used to remove the additional one-way function assumption and obtain NIZK amplification theorems that are (almost) unconditional; only requiring the mild worst-case assumption that if $\mathsf{NP} \subseteq \mathsf{ioP/poly}$, then $\mathsf{NP} \subseteq \mathsf{BPP}$.

We give a sieving algorithm for finding pairs of primes with small multiplicative orders modulo each other. This problem is a necessary condition for obtaining constructions of $2$-cycles of pairing-friendly curves, which have found use in cryptographic applications. Our database of examples suggests that, with the exception of a well-known infinite family of such primes, instances become increasingly rare as the size of the primes increase. This leads to some interesting open questions for which we hope our database prompts further investigation.

We show that Brauer and a certain class of Hansen chains satisfy the requirements for an addition chain to be closed. This puts these types of addition chain as a subfamily of the so-called closed addition chains.

Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by generating nearly uniform randomness from two independent weak sources. Moreover, cryptographic systems must also be resilient to leakage and tampering attacks, necessitating the development of non-malleable two-source extractors. In this work, we construct a two-source non-malleable extractor in the Common Reference String (CRS) model, where a random low-degree polynomial is sampled once and made accessible to independent random sources, the distinguisher, and the tamperer. Our extractor requires only linear min-entropy in both sources and doesn't rely on strong computational assumptions, in contrast to prior constructions requiring computational assumptions such as sub-exponential hardness of the Decisional Diffie-Hellman (DDH) problem. Notably, our construction builds upon and relies on the recent breakthrough proof of the polynomial Freiman-Ruzsa conjecture. A connection of the Freiman-Ruzsa conjecture with two-source extractors was considered in prior work [ZBS11],[AGMR24], but their construction did not achieve non-malleability. Our results advance the state of non-malleable cryptographic primitives, with applications in secure storage, leakage-resilient cryptography, and privacy amplification. By eliminating the need for strong computational hardness assumptions, our techniques provide a more foundational and widely applicable method for randomness extraction. We also show, that the requirements on CRS for our application are so mild that the CRS can be sampled with $2$ party computation even when one of the parties is malicious (setting in which establishing unbiased coins is impossible).

A major challenge in cryptography is the construction of succinct garbling schemes that have asymptotically smaller size than Yao’s garbled circuit construction. We present a new framework for succinct garbling that replaces the heavy machinery of most previous constructions by lighter-weight homomorphic secret sharing techniques. Concretely, we achieve 1-bit-per-gate (amortized) garbling size for Boolean circuits under circular variants of standard assumptions in composite-order or prime-order groups, as well as a lattice-based instantiation. We further extend these ideas to layered circuits, improving the per-gate cost below 1 bit, and to arithmetic circuits, eliminating the typical Ω(λ)-factor overhead for garbling mod-p computations. Our constructions also feature “leveled” variants that remove circular-security requirements at the cost of adding a depth-dependent term to the garbling size. Our framework significantly extends a recent technique of Liu, Wang, Yang, and Yu (Eurocrypt 2025) for lattice-based succinct garbling, and opens new avenues toward practical succinct garbling. For moderately large circuits with a few million gates, our garbled circuits can be two orders of magnitude smaller than Yao-style garbling. While our garbling and evaluation algorithms are much slower, they are still practically feasible, unlike previous fully succinct garbling schemes that rely on expensive tools such as iO or a non-black-box combination of FHE and ABE. This trade-off can make our framework appealing when a garbled circuit is used as a functional ciphertext that is broadcast or stored in multiple locations (e.g., on a blockchain), in which case communication and storage may dominate computational cost.

The blocks in the Bitcoin blockchain record the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF). In this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks. We completely classify such functions in an idealized “continuous” model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the timed resources V and W, i.e., αΓ(S,V,W)=Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W)=W and the Chia rule Γ(S,V,W) = S · V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia). Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W_1 and a memory-hard PoW W_2. Previous work suggested to use W_1+W_2 as weight. Our results show that using e.g., √(W_1)·√(W_2) or min{W_1,W_2} are also secure, and we argue that in practice these are much better choices.

An important requirement in synchronous protocols is that, even when a party receives all its messages for a given round ahead of time, it must wait until the round officially concludes before sending its messages for the next round. In practice, however, implementations often overlook this waiting requirement. This leads to a mismatch between the security analysis and real-world deployments, giving adversaries a new, unaccounted-for capability: the ability to ``peek into the future.'' Specifically, an adversary can force certain honest parties to advance to round $r+1$, observe their round $r+1$ messages, and then use this information to determine its remaining round $r$ messages. We refer to adversaries with this capability as ``super-rushing" adversaries. We initiate a study of secure computation in the presence of super-rushing adversaries. We focus on understanding the conditions under which existing synchronous protocols remain secure in the presence of super-rushing adversaries. We show that not all protocols remain secure in this model, highlighting a critical gap between theoretical security guarantees and practical implementations. Even worse, we show that security against super-rushing adversaries is not necessarily maintained under sequential composition. Despite those limitations, we present a general positive result: secret-sharing based protocols in the perfect setting, such as BGW, or those that are based on multiplication triplets, remain secure against super-rushing adversaries. This general theorem effectively enhances the security of such protocols ``for free.'' It shows that these protocols do not require parties to wait for the end of a round, enabling potential optimizations and faster executions without compromising security. Moreover, it shows that there is no need to spend efforts to achieve perfect synchronization when establishing the communication networks for such protocols.

While many modern cryptographic primitives have stood the test of time, attackers started to expand beyond classic cryptanalysis by targeting implementations. Subversion attacks, where the attacker replaces the implementation of the cryptographic primitive to leak sensitive information about the user during a protocol execution, are among the most dangerous of such attacks. The revelations of Snowden have shown that these attacks are deployed by intelligence services. A very promising countermeasure uses cryptographic reverse firewalls that actively remove the covert channel leaking the secret. Chakraborty et al. (EUROCRYPT’22) presented the first model of such firewalls in the universal composability (UC) framework. However, using such a firewall also provides a possible new target for the attacker and in the case that an honest party uses a corrupted firewall, they were not able to prove any security guarantees. Furthermore, their model is quite complex and does not fit into the plain UC model as they restrict the environment. Hence, the authors needed to reprove fundamental theorems such as the composition theorem as well as the security of the underlying protocol. In this paper, we consider a slightly different model of subversion attacks that replace the used randomness, inspired by Dodis et al. (CRYPTO’16), that captures all known subversion attacks. Considering these realistic attacks allows us to use existing UC-secure protocols without the need to reprove their security. We also introduce additional notions of firewall properties, allowing us to reason about corrupted firewalls while maintaining strong security guarantees. To show the versatility of our model, we apply it to commitments and oblivious transfer. This demonstrates the usefulness of our plain UC model, as the only known previous subversion-resilient OT, recently provided by Chakraborty et al. (ASIACRYPT’24), is much more complicated and involved, and was also in the non-plain UC model.

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation. In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use *cryptographic constructions* in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows. $\bullet$ Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity ($\mathrm{K}^t(x \mid y)$) in the regime where $t \gg |y|$. Previously, the best hardness of approximation known was a $|x|^{1/ \mathrm{poly}(\log \log |x|)}$ factor and only in the sublinear regime ($t \ll |y|$). $\bullet$ Unconditionally, we show near-optimal NP-hardness of approximation for the Minimum Oracle Circuit Size Problem (MOCSP), where Yes instances have circuit complexity at most $2^{\varepsilon n}$, and No instances are essentially as hard as random truth tables. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC'13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity $s$ versus $10s\log N$. $\bullet$ Finally, we define a "multi-valued" version of $\mathrm{MCSP}$, called $\mathrm{mvMCSP}$, and show that w.p. $1$ over a random oracle $O$, $\mathrm{mvMCSP}^O$ is NP-hard to approximate under quasi-polynomial-time reductions with $O$ oracle access. Intriguingly, this result follows almost directly from the security of Micali's CS proofs (Micali, SICOMP'00). In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in proving NP-hardness of approximating meta-complexity.

The symmetric binary perceptron ($\mathrm{SBP}_{\kappa}$) problem with parameter $\kappa : \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq \kappa(m/n) \cdot \sqrt{m}~.$$ The number partitioning problem ($\mathrm{NPP}_{\kappa}$) corresponds to the special case of setting $n=1$. There is considerable evidence that both problems exhibit large computational-statistical gaps. In this work, we show (nearly) tight average-case hardness for these problems, assuming the worst-case hardness of standard approximate shortest vector problems on lattices. For $\mathrm{SBP}_\kappa$, statistically, solutions exist with $\kappa(x) = 2^{-\Theta(x)}$ (Aubin, Perkins and Zdeborova, Journal of Physics 2019). For large $n$, the best that efficient algorithms have been able to achieve is a far cry from the statistical bound, namely $\kappa(x) = \Theta(1/\sqrt{x})$ (Bansal and Spencer, Random Structures and Algorithms 2020). The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kizildag, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, $\kappa(x) = \widetilde{\Theta}(1/\sqrt{x})$ is the optimal value achieved by computationally efficient algorithms. We prove their conjecture assuming the worst-case hardness of approximating the shortest vector problem on lattices. For $\mathrm{NPP}_\kappa$, statistically, solutions exist with $\kappa(m) = \Theta(2^{-m})$ (Karmarkar, Karp, Lueker and Odlyzko, Journal of Applied Probability 1986). Karmarkar and Karp's classical differencing algorithm achieves $\kappa(m) = 2^{-O(\log^2 m)}~.$ We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve $\kappa(m) = 2^{-\Omega(\log^3 m)}$, once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor. Our hardness results are versatile, and hold with respect to different distributions of the matrix $\mathbf{A}$ (e.g., i.i.d. uniform entries from $[0,1]$) and weaker requirements on the solution vector $\mathbf{x}$.

A quantum copy-protection scheme (Aaronson, CCC’09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality. There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of Çakan and Goyal (IACR Eprint, 2025) showed how to copy-protect all cryptographically puncturable schemes with pseudorandom puncturing points. In this work, we show how to copy-protect even a larger class of schemes. We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is a flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not known how to copy-protect prior to our work. Going further, we show that our scheme is secure against arbitrary high min-entropy challenge distributions whereas previous work has only considered schemes that are punctured at pseudorandom points.

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography, and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity-theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove the following: (1) Any quantum state $2$-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0 \circ \mathsf{QNC}^0$ circuits with nearly linear ancillae. (2) Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes. (3) Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing. Our indistinguishability results for $2$-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLog) problems for abelian group actions. Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLog to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed how to convert an unreliable CDH oracle into one that is correct with overwhelming probability. However, while a theoretical breakthrough, their reduction is quite inefficient: if the CDH oracle is correct with probability $\epsilon$ then their algorithm to amplify the success requires on the order of $1/\epsilon^{21}$ calls to the CDH oracle. We revisit this line of work and give a much simpler and tighter algorithm. Our method only takes on the order of $1/\epsilon^{4}$ CDH oracle calls and is conceptually simpler than the Montgomery-Zhandry reduction. Our algorithm is also fully black-box, whereas the Montgomery-Zhandry algorithm is slightly non-black-box. Our main tool is a thresholding technique that replaces the comparison of distributions in Montgomery-Zhandry with testing equality of thresholded sets.

This work establishes the CRO Trilemma: no post-quantum proof system can simultaneously satisfy the following three properties beyond negligible failure probability: (i) Confidentiality, quantified by Priv > 1 - negl(lambda); (ii) Reliability, with Rel > 1 - negl(lambda); and (iii) Legal Opposability, measured by contextual entropy H_Opp ≈ log |V_J|, where V_J denotes the validation space of a polynomial-time institutional verifier J. The result formalizes the Invisible Authenticity Paradox through contextual entropy H(C) and quantum interpretability loss eta_q(C). Under standard quantum assumptions, we prove the following impossibility bound against QPT adversaries: H_Opp <= (Priv * Rel) / (epsilon_eff * 2^H(C)) + eta_q(C) + negl(lambda) A composable framework is introduced, including a composable model with verifier J (Algorithm 1), and an optimal entropy decomposition theorem (Theorem 2.3). Theoretical predictions are supported by empirical evidence indicating consistent violation of the bound (Gamma_CRO > 0.8) across NIST PQC finalists (e.g., Dilithium) and structured ZKPs (e.g., STARKs, Groth16).

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.

An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were proposed in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize the input transactions, a natural objective is to minimize the distance (in terms of number of transactions) between any pair of unfairly ordered transactions in the output ledger — a concept we call bounded unfairness. In state machine replication (SMR) parlance this asks for minimizing the number of unfair state updates occurring before the processing of any request. This unfairness minimization objective gives rise to a natural class of parametric order fairness definitions that has not been studied before. As we observe, previous realizable relaxations of order fairness do not yield good unfairness bounds. Achieving optimal order fairness in the sense of bounded unfairness turns out to be connected to the graph theoretic properties of the underlying transaction dependency graph and specifically the bandwidth metric of strongly connected components in this graph. This gives rise to a specific instance of the definition that we call “directed bandwidth order-fairness” which we show that it captures the best possible that any ledger protocol can achieve in terms of bounding unfairness. We prove ordering transactions in this fashion is NP-hard and non-approximable for any constant ratio. Towards realizing the property, we put forth a new distributed ledger protocol called Taxis that achieves directed bandwidth order-fairness. We present two variations, one that matches the property perfectly but (necessarily) lacks in performance and liveness, and another that achieves liveness and better complexity while offering a slightly relaxed version of the property. Finally, we comment on applications of our work to social choice, a direction which we believe to be of independent interest.

We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a generic template for constructing SSL-PRGs that combines the following two ingredients: (i) noisy‑$\mathsf{NC}^0$ PRGs, computable by constant‑depth circuits fed with sparse noise, with (ii) new local compression schemes for sparse vectors derived from combinatorial batch codes. Instantiating the template under the sparse Learning‑Parity‑with‑Noise (LPN) assumption yields the first SSL-PRGs with polynomial stretch and constant locality from a subquadratic‑sample search hardness assumption; a mild strengthening of sparse‑LPN gives strong SSL-PRGs of arbitrary polynomial stretch. We further show that for all standard noise distributions, noisy‑local PRGs cannot be emulated by ordinary local PRGs, thereby separating the two notions. Plugging SSL-PRGs into existing frameworks, we revisit the canonical applications of local PRGs and demonstrate that SSL-PRGs suffice for: (i) indistinguishability obfuscation, (ii) constant-overhead secure computation, (iii) compact homomorphic secret sharing, and (iv) deriving hardness results for PAC‑learning DNFs from sparse‑LPN. Our work thus broadens the landscape of low‑depth pseudorandomness and anchors several primitives to a common, well‑motivated assumption.

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. '94] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that **every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness.** This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is "game-based" instead of "simulation-based." Our construction builds on the work of Kuykendall and Zhandry [TCC '20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajícek and Pudlák's 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert's second problem (and, hence, also Gödel's incompleteness theorem). Our high-level idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.

Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing (including cryptography) communities. In particular there has been a major effort focused on improving the efficiency, and in particular depth, of generating the classical snapshot. Existing constructions rely on a distribution of unitaries as a central building block, and research is devoted to simplifying this family as much as possible. We diverge from this paradigm and show that suitable distributions over \emph{states} can be used as the building block instead. Concretely, we create the snapshot by entangling the unknown input state with an independently prepared auxiliary state, and measuring the resulting entangled state. This state-based approach allows us to consider a building block with arguably weaker properties that has not been studied so far in the context of classical shadows. Notably, our cryptographically-inspired analysis shows that for \emph{efficiently computable} observables, it suffices to use \emph{pseudorandom} families of states. To the best of our knowledge, \emph{computational} classical shadow tomography was not considered in the literature prior to our work. Finally, in terms of efficiency, the online part of our method (i.e.\ the part that depends on the input) is simply performing a measurement in the Bell basis, which can be done in constant depth using elementary gates.

Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. These are codes where a collection of polynomially many codewords is computationally indistinguishable from random for an adversary that does not have the secret key, but anyone with the secret key is able to efficiently decode corrupted codewords. In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist. 1. We show that if both the planted hyperloop assumption introduced in [BKR23] and security of a version of Goldreich's PRG hold, then there exist public-key PRCs for which no efficient adversary can distinguish a polynomial number of codewords from random with better than $o(1)$ advantage. 2. We revisit the construction of [CG24] and show that it can be based on a wider range of assumptions than presented in [CG24]. To do this, we introduce a weakened version of the planted XOR assumption which we call the weak planted XOR assumption and which may be of independent interest. 3. We initiate the study of PRCs which are secure against space-bounded adversaries. We show how to construct secret-key PRCs of length $O(n)$ which are $\textit{unconditionally}$ indistinguishable from random by $\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.

We present improved definitions and constructions for copy-protected digital signatures and pseudorandom functions (PRFs). Our new security definitions support challenge messages or inputs chosen from arbitrary high min-entropy distributions and allow signing or evaluation queries. This extends prior definitions, which assumed uniformly random challenges and did not consider oracle access. We construct schemes that satisfy these stronger definitions using only polynomially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), avoiding the subexponential assumptions and the Learning with Errors (LWE) assumption used in previous constructions, even in the uniform-challenge and query-free setting. Moreover, our constructions and security proofs are arguably simpler than existing ones. We also propose a new security notion for unclonable puncturable obfuscation (UPO), which primarily extends prior definitions to support challenge inputs drawn from arbitrary high min-entropy distributions, along with some additional refinements. We construct a UPO satisfying this notion from polynomially secure iO and the LWE assumption, thereby avoiding the subexponential assumptions and unproven conjectures required in previous constructions, even in the uniform-challenge setting. In fact, in the uniform-challenge case, we show that iO and OWFs alone suffice, further removing the need for LWE. Again, our constructions and security proofs are arguably simpler than existing ones. As applications, we show that a UPO satisfying this notion is sufficient to copy-protect a variety of puncturable functionalities beyond those studied in the prior work.

A length $n$ encryption cycle consists of a sequence of $n$ keys, each encrypting the next, forming a cycle, and an encryption scheme is $n$-circular secure if a length $n$ encryption cycle is computationally indistinguishable from encryptions of zeros. An interesting problem is whether CPA security implies circular security. This is shown to be not true. Using standard cryptographic assumptions and LWE, it was shown that within the class of CPA secure encryption schemes, for any $n$, there exists an $n$-circular insecure encryption scheme. Furthermore, there exists a particular encryption scheme that is $\ell$-circular insecure for all $\ell$. Following these results, it is natural to ask whether a circular insecurity of a particular length implies circular insecurity of different lengths and of multiple lengths. We answer this problem with an affirmative in this paper. We constructively prove that a CPA secure encryption scheme that is insecure in the presence of encryption cycles of length $(n+1)$ implies the existence of such a scheme for encryption cycles of any length less than $(n+1)$. The constructed $(\le n)$-circular insecure construction may have the same message space as the $(n+1)$-circular insecure encryption scheme, and our results apply to both public key and symmetric key settings.