A robust combiner for a cryptographic primitive $P$ takes multiple candidate constructions of $P$ and produces a secure construction of $P$ provided that sufficiently many of the candidates are secure. A closely related notion is that of a security amplifier, where given a weakly secure construction of $P$, we aim to obtain a (strongly) secure one. Intuitively, one may expect that any robust combiner should act as an amplifier by thinking of "good randomness" as inducing secure instances, and of "bad randomness" as inducing insecure instances. Formalizing this intuition, however, has turned out to be challenging. Despite significant progress, general results remain limited and confined either to specific primitives or only to the statistical setting. We establish a new framework of robust indistinguishability combiners, which greatly extends the class of combiners covered by prior work, and prove that they inherently act as security amplifiers. Our results extend to the computational setting, provided that the combiner makes a single query to each candidate. The new framework allows us to rederive previously known amplification results in a simplified manner, as well as prove new amplification results that have so far been out of reach. As our main application, we present the first security amplifier for functional encryption, resolving an open question that first arose in constructions of indistinguishability obfuscation, and for which a gap was discovered in previous proofs. Our amplifier transforms a weak scheme with any constant indistinguishability error into one with full negligible security.

At EUROCRYPT 2025, Carlini {\em et al.} proposed a breakthrough in the cryptanalytic extraction on hard‑label (S1) deep neural networks (DNNs), demonstrating polynomial-time signature and sign recovery. However, Carlini {\em et al.}'s sign‑recovery method ({which we call \em Future Toggle}) suffers only a marginal advantage over random guessing, producing high‑confidence wrong sign predictions in deeper layers. Such errors trigger expensive exponential‑time enumeration. This work presents {\em Normal Alignment}, a novel statistical sign‑recovery approach for S1 DNNs. Drawing on the expected length difference between projected normals of adjacent decision facets at dual points, our method infers neuron signs via normal‑signature alignment. It delivers higher voting accuracy and pushes erroneous predictions to low‑confidence ranks, which further enables a more efficient combined method, {\em eSOE + Alignment}, by combining {\em Normal Alignment} with the hard‑label {SOE} extension. This combined strategy removes heavy enumeration overhead and realizes exact polynomial‑time full sign recovery. Experiments demonstrate the effectiveness of our method, especially for deep layers. For example, with our method, the signs for CIFAR-10 (architecture 192-64$\times$8-10) and MNIST (architecture 64-96$\times$3-32-10) models can be fully recovered in polynomial time; in contrast, Carlini {\em et al.}'s sign‑recovery method would require exponential‑time enumerations involving $2^{52}$ or $2^{82}$ guesses of the signs, respectively.

EIP-7702, live on Ethereum since the Pectra upgrade, lets externally owned accounts delegate their execution to arbitrary contract code with a single signature. The consequences are measurable: 63% of observed delegations point to malicious contracts, with $2.36M in confirmed losses, and ecosystem guidance already warns about cross-chain replay and front-run initialization. What is missing is a formal account of the problem: the 7702 delegation lifecycle has no formal treatment, and none of the recommended mitigations has been machine-verified. We present DelegProof, to our knowledge the first symbolic formal analysis of EIP-7702 authorization semantics composed with the ERC-4337 EntryPoint pipeline. Our Tamarin models are calibrated by reproducing four documented attack classes, and yield ten machine-checked attack patterns—among them the silent failure of the advertised temporary-delegation bundle, storage confusion across re-delegation, and an ERC-1271 substitution attack that reaches into the signature checks of relying contracts—together with the security invariants that do hold. Formalizing the recommended mitigations shows that banning chainId-0 authorizations eliminates cross-chain replay, that an account-bound initialization gate restores init authorization while an unbound gate is provably still bypassable, and that namespaced storage slots make the storage-confusion class structurally inexpressible. All models and proofs are available at https://anonymous.4open.science/r/delegproof-artifact-F7FE/.

We present four quantum-safe schemes: the Kyber (ML-KEM) and FrodoKEM key encapsulation mechanisms, and the Dilithium (ML-DSA) and Falcon (FN-DSA) signature schemes. We also develop the mathematical background on lattices needed to understand why Kyber, FrodoKEM, Dilithium and Falcon are regarded as lattice-based cryptosystems, and we provide insight into the computational hardness of the underlying lattice problems. The exposition is intended to be accessible to senior undergraduate students and beginning graduate students.

Verifiable election systems allow voters to verify that their secret ballots were accurately recorded and counted, while enabling anyone to verify the announced tallies. However, two practical obstacles stand between this guarantee and actual verification. First, public election records can be prohibitively large: for an election with one million ballots, deployed systems may publish more than 100GB of cryp- tographic data. Second, most existing systems protect ballot privacy through encryption, introducing key management—usually one of the most cumbersome and error-prone components of election administration. We present Haechi, a keyless verifiable election scheme for in-person voting, based on cryptographic vector commitments rather than encryption. At the core of Haechi is a new zero-knowledge proof of ballot well-formedness based on Compressed Σ-protocol theory. Our proof scheme proves the validity of an entire ballot using only a logarithmic number of group elements in the number of the ballot options. This allows all of a voter’s selections to be encoded into a single vector commitment. With this approach, Haechi reduces the data required for public verification by more than an order of magnitude compared to prior in-person verifiable election systems. Haechi thereby makes verifications for large-scale election considerably more practical. We also give a post-quantum instantiation of Haechi based on lattice commitments, which preserves the same keyless workflow at the cost of larger election records.

There is a growing literature on differential privacy (DP) in multiparty protocols, enabling use in distributed settings and reduced trust assumptions. A largely overlooked aspect of such protocols is the extent to which an adversary can undermine the DP guarantees by making the protocol abort. Another is the DP properties of the honest parties' outputs. We initiate the study of both these issues. First, we propose an idealized model of aborts, where an aborter is leaked some information about a DP mechanism execution and then chooses whether or not to let an independent malicious analyst learn the mechanism output. We bound the effects of aborts according to what information (the database, randomness, output, or any combination of these) is leaked. These bounds are not only applicable to multiparty DP via general-purpose multiparty computation (MPC) but may also be used in the analysis of other methods to certify DP properties of a protocol. Second, we apply these bounds to analyze ideal protocol executions in MPC. We show, for the first time, that the ideal execution with fairness gives strictly stronger DP guarantees than that for security-with-abort, for the outputs to the honest parties. Further, solitary-output functionalities satisfy guarantees similar to those of the execution with fairness. Finally, we analyze multiparty protocols with respect to the way in which they realize the respective ideal functionalities. We show that partially fair and fully fair protocols have very similar DP guarantees. Since partial fairness, as opposed to full fairness, can be achieved in dishonest-majority settings, and in particular the two-party setting, this opens up for enhanced DP guarantees in two-party computation.

As digital identity frameworks (DIFs) gain traction around the world, many see privacy-enhancing technologies (PETs) as the key to prevent their potential negative societal impacts such as discrimination or surveillance. We critically examine whether PETs can achieve this goal using the European Digital Identity Framework (EUDIF) as an example. We develop a harm analysis methodology based on harm trees that illustrates how information leakage, certain design decisions, or a DIF's deployment context lead to harms. We leverage techniques from cryptographic modeling to formally capture the leakage of the core functionality of the EUDIF and its proposed applications. Our harm modeling elucidates which pathways to harm are inherent to the EUDIF's core functionality, and which pathways can be mitigated through PETs. Our analysis shows that, while PETs can reduce information flows, they fall short in actually mitigating the harms that deploying digital identity can bring to individuals and society.

We propose a new polynomial evaluation algorithm to evaluate a degree-$d$ Boolean polynomial $f(x_n,\ldots,x_1)$ on all elements in some structured sets $S\subseteq \mathbb F_2^n$. This problem has been well-studied for $S=\mathbb F_2^n$ and there are efficient polynomial evaluation algorithms like standard Mobius transform, memory-efficient Mobius transform (EUROCRYPT 2021, TOMS 2024) and fast exhaustive search (CHES 2010, PQCrypt 2023) for the case $S=\mathbb F_2^n$. In addition, the standard Mobius transform can also be used to evaluate a polynomial over the set $S=P_{n}^w$ of all $(x_n,\ldots,x_1)\in\mathbb F_2^n$ whose Hamming weight is upper bounded by $w$, and its memory complexity is the same as the size of $S$. In Dinur's algorithm for polynomial method proposed at EUROCRYPT 2021, there is a critical step to efficiently evaluate $f$ over a more general input set $P_{n-n_1}^{w}\times P_{n_1}^{n_1}\subseteq \mathbb F_2^n$. To our knowledge, in the literature, no memory-efficient polynomial evaluation algorithms are designed for such a special input set. Dinur proposed a tweaked fast exhaustive search algorithm for this problem, but it has not been proved nor implemented. This leaves us with a natural question: can we design an efficient polynomial evaluation algorithm tailored for a more general input set $P_{n_s,\ldots,n_1}^{w_s,\ldots,w_1}=P_{n_s}^{w_s}\times \cdots \times P_{n_1}^{w_1}\subseteq \mathbb F_2^n$ where $\sum_{i=1}^{s}n_i=n$ and $w_i\leq n_i$? We answer this question by proposing a new polynomial evaluation algorithm named \textbf{FESG}, i.e., \textbf{F}ast \textbf{E}xhaustive \textbf{S}earch over a more \textbf{G}eneral input set, to handle the input set $P_{n_s,\ldots,n_1}^{w_s,\ldots,w_1}$. This algorithm is based on the derivative-based polynomial evaluation framework proposed at CHES 2010. In addition to extending the application of derivative-based framework to a more general input set, we also successfully address a major issue in existing derivative-based algorithms over $\mathbb F_2$ proposed at CHES 2010 and PQCrypt 2023, reducing the time complexity of the initialization phase from $\mathcal O\big(\binom{n}{\leq d}^2\big)$ to $\mathcal O\big(\binom{n}{\leq d}\big)$. As a result, FESG is also efficient for large $d$. Our algorithm is almost optimal, whose theoretic time and memory complexity are $\binom{n}{\leq d}+d\cdot |P_{n_s,\ldots,w_1}^{w_s,\ldots,w_1}|$ bit operations and $2\cdot \binom{n}{\leq d}$ bits, respectively. Here, $|P_{n_s,\ldots,w_1}^{w_s,\ldots,w_1}|$ is the size of the set $P_{n_s,\ldots,w_1}^{w_s,\ldots,w_1}$. An efficient implementation of the FESG algorithm for any $(d,n_s,\ldots,n_1,w_s,\ldots,w_1)$ is also given in this work. In particular, the FESG algorithm also provides a proven method for a critical step in Dinur's algorithm for polynomial method without affecting its overall complexity.

The meet-in-the-middle (MITM) attack framework is one of the most powerful cryptanalytic techniques with broad influence to preimage, key recovery, and collision attacks. In this paper, we present two generic techniques. First, we observe that the constant space in MITM attacks is an exploitable source of degrees of freedom: its value-independence enables MITM-style partition and acceleration of attack subprocesses. With this intuition in mind, we revisit the single-color initial structure technique by Chen et al. at Asiacrypt 2025, and find an improved algorithm that relaxes the canonical optimization objective in automatic search for MITM attacks. Second, we extend the partial-target-preimage-to-collision conversion by Li, Isobe, and Shibutani at FSE 2012 used in MITM-based collision attacks to the settings of chosen-prefix collision and diamond structure construction. We demonstrate the practical relevance of our techniques by presenting a number of improved results in (pseudo-)preimage, (chosen-prefix) collision, and herding attacks on AES-like constructions over the state-of-the-art.

We put forward a generalization of attribute-based signcryption, called anonymous attribute-based signcryption (A$^2$BSC). Beyond message confidentiality and ciphertext unforgeability, A$^2$BSC further requires \textit{ciphertext anonymity}: no information about the signcryptor's attributes or ciphertext-related attributes/policies is leaked, regardless of the decryption outcome. Specifically, we begin by establishing the syntax and security notions for A$^2$BSC within a \textit{unified} framework, which encompasses various variants (key-policy, ciphertext-policy, dual-policy, and a hierarchical dual-policy variant called Special A$^2$BSC). Then, we construct a Special A$^2$BSC scheme for \textit{general policies} (modeled as bounded-depth Boolean circuits) from the succinct learning with errors and the basis-augmented short integer solution assumptions in the standard model, hence achieving post-quantum security. This naturally yields lattice-based instantiations of both ciphertext-policy and dual-policy A$^2$BSC. Beyond its independent interest, we also show the expressiveness and generality of our A$^2$BSC by exploring its application to matchmaking encryption (ME) and arranged matchmaking encryption (AME) proposed by Ateniese et al. (Crypto '19). As a byproduct, we give generic constructions of both ME and AME for \textit{arbitrary policies} against unbounded collusions, and strengthen the CPA-privacy of (A)ME to achieve CCA security. The latter is achieved for free in our construction, as A$^2$BSC natively provides CCA security. Overall, our new solution enhances the diversity of approaches for building the advanced primitive (A)ME.

We revisit the problem of mitigating information leakage in the widely used but insecure compress-then-encrypt paradigm. While encryption hides message contents, the ciphertext length is directly related to the length of the compressed message, which may, in turn, leak information about the {\em content} of the message itself. Recent work of Blocki et al. (TCC~2025) proposed an $(\varepsilon,\delta)$-differentially private approach that adds randomized padding calibrated to the global sensitivity of the compression algorithm, and showed that LZ77 has global sensitivity $O(W^{2/3}\log n)$ for input length $n$ and sliding window size $W$. However, prior analysis focused only on sensitivity with respect to single-character edits, which leads to limited privacy guarantees when protecting longer substrings such as passwords, passphrases, cookies, or confidential user records. A natural attempt to handle longer secrets is to appeal to group privacy, but for approximate differential privacy, this leads to very poor parameter degradation: in particular, the effective value of $\delta$ can grow exponentially with the group size $g$. In this work, we introduce and study the sensitivity of compression schemes under block edits. Specifically, we define two strings to be $g$-neighbors if they differ only within a contiguous interval of length $g$. Our main technical contribution is a nearly tight characterization of the $g$-consecutive sensitivity of LZ77. We show that the $g$-consecutive sensitivity of LZ77, both with and without self-referencing, is at most $O\!\left((W^{2/3}+g+\sqrt{Wg})\log n\right)$. In particular, when $g \leq W^{1/3}$, the bound simplifies to $O(W^{2/3}\log n)$, matching the known bound for single-character edits. Combined with the framework of Blocki et al., our bound yields $(\varepsilon,\delta)$-differential privacy for $g$-neighbors with the same asymptotic padding scale as for single-character edits. We provide matching lower bounds to demonstrate that our upper bound is tight, e.g., when $n=W=\Theta(g^2)$, the $g$-consecutive sensitivity of LZ77 is at least $\tilde{\Omega}(g^{3/2})$, matching the $\sqrt{Wg}=\Theta(g^{3/2})$ term from our upper bound up to a logarithmic factor.

Bootstrapping is the key technique that turns leveled homomorphic encryptionc into fully homomorphic encryption, but it remains a major efficiency bottleneck. Recent work by Z. Liu and Y. Wang (ASIACRYPT 2023) showed how to bootstrap \(N\) LWE ciphertexts with total cost of \(\widetilde{O}(N)\) polynomial multiplications based on the BFV scheme. However, their results achieve \(\widetilde{O}(1)\) complexity only through amortization over large batches, and do not give a genuine non-amortized \(\widetilde{O}(1)\) bound for a single ciphertext. In this paper, we present a BFV-based functional bootstrapping algorithm for arbitrary functions over large plaintext spaces with total cost of \(\widetilde{O}(1)\) polynomial multiplications for one LWE ciphertext. The same construction also supports small and moderate batches, and processes a batch of \(m\) ciphertexts with total cost \(\widetilde{O}(m)\) in the supported parameter range. The main technical ingredient is a sparse-packing polynomial-evaluation method for BFV ciphertexts, which exploits the duplicated-slot structure to evaluate an arbitrary polynomial on \(m\) encrypted inputs with total cost of \(\widetilde{O}(m)\). We implement the scheme in Lattigo using the BFV scheme. At 128 bit security and on a single thread, bootstrapping an arbitrary function takes 3.15 seconds for one ciphertext encrypting a 9-bit plaintext and 3.77 seconds for 128 such ciphertexts in one batched invocation. For 16-bit plaintexts, it takes 10.63 seconds for one ciphertext and 18.07 seconds for 16 ciphertexts. These results show that non-amortized single-ciphertext functional bootstrapping, as well as small and moderate batch bootstrapping, can be practical for arbitrary functions over relatively large plaintext spaces.

Understanding the minimal computational power needed to realize a pseudorandom function (PRF) is a long-standing question in cryptography. By the Razborov–Smolensky polynomial approximation method, it is known that $AC^0[2]$ cannot support strong pseudorandom functions with subexponential security, since any such function can be distinguished from random with quasipolynomially many samples. In this work, we initiate the study of low-complexity strong PRFs under a refined framework that separates adversary query complexity from running time and distinguishing advantage, and observe that distinguishing algorithms for $AC^0[2]$ do not apply if the number of queries is below the threshold implied by the Razborov–Smolensky approximation bound. In this setting, we prove that strong PRFs cannot exist in the smaller class $MOD_2 \circ AC^0$, showing that every such function family can be efficiently distinguished from random using polynomially many queries. Together with the fact that functions in $AC^0 \circ MOD_2$ are conjectured to have heavy Fourier coefficients (ITCS 2014), this identifies $AC^0[2]$ as the minimal candidate class for realizing strong PRFs in the bounded-query setting. We propose the first candidate strong PRF in $AC^0[2]$, which we conjecture to offer subexponential security against adversaries limited to a fixed quasipolynomial number of queries. Furthermore, our candidate is in the class $MOD_2 \circ AC^0\circ MOD_2$, arguably the minimal class given the above barriers. We show that our candidate lacks heavy Fourier coefficients, resists many settings of linear attacks, is non-sparse over $\mathbb{F}_2$ with high probability, has high rational degree, is inapproximable by low-degree polynomials over $\mathbb{F}_2$, and has low correlation with fixed function families. As a final contribution, we show that if any strong PRF exists in $AC^0[2]$ (or a superclass), then we can construct a universal PRF, i.e., a single, fixed function which is guaranteed to be a strong PRF in the same class.

List decoding Reed–Solomon codes is a central problem in coding theory and, together with mutual correlated agreement (MCA), underpins the soundness of many succinct cryptographic proofs. In this work, we give precise quantitative bounds on Reed–Solomon list decoding and MCA up to capacity, provide deterministic decoding algorithms that remain efficient over cryptographically large fields, and specialize our bounds to reduce proof sizes in implemented proof systems. Our bounds apply to arbitrary prescribed evaluation domains; beyond Johnson, they require sufficiently large field characteristic. Refining the hidden-derivative method of Brakensiek, Chen, Putterman, Zhang, and Zheng, we obtain an explicit agreement threshold $a_1(\rho)$ strictly below the Johnson bound $\sqrt{\rho}$, using only the first derivative, without requiring its evaluations in the received word. At agreement $a_1(\rho)+\eta_1$, where $\eta_1>0$, our sharper interpolation and candidate counts give list size $O_\rho(n/\eta_1^2)$ and MCA error $O_\rho(n^2/(q\eta_1^4))$ for codes of length $n$ over $\mathbb{F}_q$. Higher derivatives give explicit quantitative bounds up to capacity, uniformly over all rates, sharpening prior MCA results in Zheng's unpublished manuscript and Jeronimo's work, concurrent with ours. At fixed rate, for agreement gap $\eta_0>0$ above Johnson, we improve the MCA error bound of Ben-Sasson et al. (BCHKS) from $O_\rho(n/(q\eta_0^5))$ to $O_\rho(n/(q\eta_0^3))$, in every characteristic. Our decoders use agreement constraints to recover close messages without enumerating initial field values. With fast explicit field arithmetic, at fixed rate and a fixed positive agreement margin above the respective threshold, deterministic decoding takes $\widetilde O(n\log q)$ bit operations above Johnson in every characteristic and $\widetilde O(n^2\log q)$ above our first-order curve in sufficiently large characteristic. Decoding remains polynomial in $n$ and $\log q$ at every fixed positive gap from capacity, under the same requirement of sufficiently large characteristic. Our first-derivative bounds give the first proof-size reductions in existing proof-system implementations from provable Reed–Solomon proximity-gap bounds beyond the Johnson radius. At unchanged security targets, we save 79.4 KB (11.1%) for ProveKit passport proofs, 13.2 KB (4.63%) for ZisK compressed final proofs, and 59.8 KB (4.85%) for LambdaVM CPU subproofs. We have formally verified the list-decoding and MCA bounds and concrete parameter certificates in ArkLib, a Lean library for verified cryptographic proofs, and proved correctness of a simplified version of our list-decoder.

Bounded Distance Decoding (BDD) is a fundamental primitive in both code- and lattice-based post-quantum cryptography. Prior work of Regev (FOCS~2002) and Brakerski, Kirshanova, Stehl\'e and Wen (PKC~2018) connected lattice BDD and Learning With Errors (LWE) to the Extrapolated Dihedral Coset Problem (EDCP), but these reductions rely heavily on geometric structure and do not naturally extend to coding-theoretic metrics. We present a general quantum reduction from BDD over finite Abelian groups equipped with translation-invariant metrics to EDCP, requiring only the existence of an appropriate locality-sensitive hash family. Instantiating this framework yields new reductions for decoding in the Hamming metric, rank metric, and the $p$-Lee metric (which coincides with the standard Lee metric when $p = 1$). For the Hamming and rank metrics, our reductions only yield a non-negligible number of EDCP states in parameter regimes where known decoding algorithms are already efficient. However, we recover the LWE-to-EDCP reduction within our framework by combining known equivalences between lattice CVP/BDD in the $\ell_p$ norm and $p$-Lee metric decoding.

Rounding error plays a key role in approximate homomorphic encryption (HE), as it determines the noise level and affects the achievable precision. While rounding is typically performed coordinate-wise in the coefficient basis, an alternative is to perform lattice-based rounding in the canonical embedding. These two approaches coincide for power-of-two (PoT) cyclotomics, but can differ for non-PoT cyclotomics. This difference opens the possibility of new parameter tradeoffs for approximate HE over general cyclotomic rings. Motivated by this distinction, we study rounding error in the Closest-Vector Problem (CVP) over cyclotomic lattices of arbitrary order. We derive new worst- and average-case bounds, showing improved rounding for non-PoT cyclotomics over their PoT counterparts. To enable efficient rounding, we analyze Babai’s nearest-plane algorithm as an approximation to exact nearest-point rounding, while retaining efficient ring arithmetic for broad families of cyclotomic orders. These improved bounds, together with the additional flexibility afforded by moving beyond the sparse PoT orders, inform the choice of encryption parameters for approximate HE. Our concrete evaluation yields parameters with simultaneously smaller lattice dimension and ciphertext modulus than the corresponding PoT choices at fixed output precision and target security level. Our results highlight the potential benefits of non-PoT cyclotomics for approximate HE.

In this work, we introduce Lemur+, a compact post-quantum synchronized multi-signature scheme based on standard lattice assumptions (namely, Module LWE and Module SIS). Lemur+ builds on Lemur (CCS 2026) and targets large-scale, long-term distributed applications such as blockchain consensus while supporting non-interactive aggregation. Lemur+ maintains an almost constant signature size of about 56 KB even for one million signers and a 42-year key lifetime, compared to 491 KB in Lemur, yielding about $8.8\times$ reduction in communication/storage. Our end-to-end implementation demonstrates practical runtime performance: 7.75 s for signature aggregation and 0.29 s for verification with $2^{13}$ signers. These are roughly within $2\times$ of the corresponding Lemur runtimes. The key to Lemur+ is our proposed Homomorphic Vector Commitment with Succinct Opening Proof (HVC-SOP), a new primitive that augments standard HVC with succinct opening proofs. We show that HVC-SOP can be generically combined with key-homomorphic one-time signatures (KOTS) to construct non-interactive synchronized multi-signatures, and prove the security of the resulting construction against rogue-key attacks. We then instantiate HVC-SOP using the lattice-based LaBRADOR proof system (CRYPTO 2023), yielding Lemur+. Finally, we extend Lemur+ to support multi-hop aggregation, allowing signatures to be recursively aggregated across distributed network trees. Beyond Lemur+, our HVC-SOP may be broadly applicable and of independent interest.

Xue, Lu, and Au design a logarithmic-size verifiable shuffle for rerandomized ElGamal ciphertexts by combining a KZG permutation argument with a tagged inner-product argument, with cost $(2\log N+11) \mathbb{G}_1 + 8 \mathbb{F}$. We reduce the communication and computation of their construction by observing that the rerandomization vector $\boldsymbol{\rho} \in \mathbb{F}^N$, despite being utilized as a full witness vector, only enters the consistency equations through the scalar $\rho^* =\langle\boldsymbol{a}, \boldsymbol{\rho} \rangle$. We bind this scalar into an existing KZG commitment and replace XLA's two-vector consistency argument with a one-sided folding proof, while preserving the original relation, polynomial degrees, and powers-of-$\tau$ setup. We show that the the naive scalarization is unsound. Applied correctly, the committed scalar indeed permits extraction of the full rerandomization vector. We present two variants: Variant A has proof size $(2\log_2 N+8) \mathbb{G}_1 + 5 \mathbb{F}$, while Variant B adds one group element but removes one interactive round. Under XLA's grouped base-scalar-pair accounting, the prover's exponentiation count decreases from approximately $18N$ to $13N$ (or $14N$, for Variant B), and the verifier's drops from approximately $7N$ to $6N$. Each proof is a constant $240$ B smaller than XLA's; in a $4$-server mix-net election protocol with $N = 2^{10}$ ballots, our Variant A mixing proof costs $5.88$ KiB in total, about $14\%$ smaller than XLA.

Linkable ring signatures (LRS) let a member sign on behalf of a group anonymously while ensuring that any two signatures by the same signer are publicly linkable, a major component in e-voting and cryptocurrencies. Random systems of multivariate quadratic (MQ) equations are one of the most conservative post-quantum assumptions, yet there are only two MQ-based LRS's in the literature: the first is due to Omar, Padhye, and Dey, and the second by Namdeo, Mishra, and Srivastava. Both of these schemes are built from Sakumoto-style identification protocols whose soundness for signatures is well-established, but in the ring setting was never re-examined. We present a sumset attack that lets a signer with no knowledge of an MQ solution universally forge accepting signatures in both protocols. In the same vein, we show that the four-challenge MQ protocol of Monteiro, Goya, and Terada (as transcribed in Namdeo, Mishra, and Srivastava) has soundness error $3/4$ instead of the claimed $1/2$, and this bound is tight. Its natural repair does achieve $1/2$, but is only $3$-special sound, so the two-transcript extraction argument upon which their LRS relies upon does not hold regardless. We then build PyuQuMuQu, a plausibly post-quantum MQ-based LRS from a $5$-pass proof with a $d$-dimensional vector first challenge and an additively split second challenge, whose soundness error is $\frac{1}{2} + \frac{N}{2(q^d-1)}$ for a ring with $N \leq q^d-1$ members. We demonstrate anonymity, linkability, and non-slanderability in the random-oracle model under explicitly stated assumptions involving random MQ maps. PyuQuMuQu attains $355$ kB signature sizes for a ring with $4$ members $128$ bits of security.

The McEliece cryptosystem based on algebraic geometry codes has been proposed as a way to reduce the key size of code-based cryptography, but several structural attacks have demonstrated the vulnerability of particular families of algebraic geometry codes. Despite this, until recently, there remained schemes and parameter sets that were not vulnerable to any known attack. We propose a new structural attack with ``hints'' that applies to elliptic codes with arbitrary effective divisors. In particular, we prove that, given the elliptic curve, the public generator matrix, and three points from the evaluation divisor, the entire divisor can be recovered in polynomial time, independently of the number of errors used in the cryptosystem. The attack requires $\mathcal{O}(k^2n^2+|\mathcal{E}(\mathbb{F}_q)|+n)$ operations in $\mathbb{F}_q$ and succeeds with overwhelming probability, after which the second divisor is recovered in $\mathcal{O}\!\left(k^2n^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations. We further propose an optimized version of the attack that requires no additional information at all. Exploiting the action of the automorphisms of the curve, the three known points are replaced by the enumeration of a single pair of field elements, which yields an equivalent key on the given public curve in $\mathcal{O}\!\left(k^2n^2 + q^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations on average.

We give an itemized conditional arithmetic estimate for ``Holdout'' key recovery on each Classic McEliece parameter set. This attack uses polynomial relations to recover locators, the hidden field values specifying the code. Shortening restricts codewords to zero on selected positions and then deletes those positions. Assuming the public tests uniquely recover enough compatible locator values, one shortened coordinate set suffices for each parameter set, instead of the four or five in the analysis of Ghoshal, Ishai, Jain, and Sun. We make the linear solves reliable using Eberly's random scaling of rows and columns and scalar Lanczos, an iterative solver over a larger field. Returned solutions are mapped back and checked in the original equations. Charging operations with binary coefficients separately from general field arithmetic gives conditional arithmetic estimates of $2^{126.77}$ bit operations for mceliece348864, $2^{145.22}$ for mceliece460896, $2^{137.48}$ for mceliece6688128, $2^{136.65}$ for mceliece6960119, and $2^{137.48}$ for mceliece8192128}. The corresponding working-memory estimates are $2^{51.33}$, $2^{59.10}$, $2^{55.18}$, $2^{54.86}$, and $2^{55.18}$ bits. All five arithmetic estimates lie below the NIST classical-gate reference level for their claimed category; the model excludes address generation and memory traffic and uses budget estimates for some stages.

Threshold traitor tracing [Boneh et al., Crypto’24] enhances threshold decryption with anti-collusion guarantees via a tracing mechanism. In this model, a set of colluders constructs a decryption box, called a decoder, and sells it to an external buyer. Collusion-resilience is guaranteed by a tracing algorithm that, given only black-box access to the decoder, can identify at least one of the colluders. Since its introduction, threshold traitor tracing has attracted significant attention, leading to a number of new constructions that have been proven secure within this model [Asiacrypt'25, CiC'25, CCS’25, Eurocrypt’26], focusing on optimizing parameter sizes and removing trusted authority. However, in this paper, we argue that the state-of-the-art definition and constructions are not resilient against natural attacks where the decoder is sold to an insider, i.e., a member of the decryption committee. Motivated by this gap, we introduce new definitions to model decoder boxes that are sold to insiders. We show that existing threshold traitor tracing techniques are inherently vulnerable to insider attacks. Then, we introduce a novel approach to achieve insider resilience through \emph{multi-traitor tracing}, i.e., identifying multiple traitors. We present compilers that amplify the number of traitors that can be found, thereby achieving insider-resilience with efficient parameters, in particular, sublinear ciphertext size. These compilers may also be of independent interest.

The digital signature scheme SQIsign, currently under consideration in NIST's call for additional post-quantum signatures, offers the smallest key and signature sizes among all candidates. Its signing procedure, however, relies on an involved arithmetic layer over quaternions, in which the objects are represented by small-dimensional integer lattices. In this layer, the intermediate integers can grow significantly larger than the final outputs. Controlling this growth is essential for fixed-precision and, ultimately, constant-time implementations. In this work, we revisit the integer-size analysis of this arithmetic layer. We first observe that all lattices arising in SQIsign satisfy a structural containment property that allows their canonical form to be computed with a modulus of half the bit length used in previous analyses. Exploiting the same property, we give a matrix inversion algorithm using only exact divisions whose intermediate integers remain bounded by twice the modulus. This algorithm avoids the cubic blow-up of standard inversion methods. We show that the triangular-form convention used in the SQIsign implementation reduces the size of intermediate values by a factor of $O(p)$. Second, we show that these lattices can be represented in dimension two over the Gaussian integers instead of dimension four over the integers. This allows us to replace the LLL algorithm by the simpler Lagrange reduction that has the number of iterations bounded by a multiple of the bit-size of the longest input vector. Furthermore, this reduction provably outputs the shortest basis without requiring floating-point arithmetic. Combining these results, we derive integer-size bounds for SQIsign key generation and signing, improving on previous bounds for key generation and for all signing subroutines outside of the response quaternion sampling. We provide an implementation of our algorithms in the GMP-based C reference implementation of SQIsign.

An oblivious pseudorandom function (OPRF) is a two-party protocol that enables a client to obtain $F_k(x)$ on an input $x$ without learning the server-held key $k$, while the server learns nothing about $x$. OPRF is a fundamental building block in a wide range of privacy-preserving applications, including password-authenticated key exchange (PAKE), private set intersection (PSI), and distributed function secret sharing. In this work, we present the first concrete, high-throughput, post-quantum secure, verifiable distributed OPRF (dOPRF) tolerating $t < n/2$ malicious servers and a malicious client over replicated secret sharing, extending the recently introduced Gold OPRF of Yang et al. (IEEE S&P 2025) to a threshold setting. We adopt an offline-online paradigm and introduce new protocol designs for both phases. (i) In the offline phase, we develop efficient protocols for batched generation of replicated secret sharing of $\alpha^e$ whose cost is independent of $e$. We present two complementary approaches, each designed for different parameter regimes: the first leverages a degenerate additive encoding under which exponentiation commutes with secret sharing; the second employs $t+1$ designated dealers that prove dual-share consistency via non-interactive zero-knowledge proofs, instantiated using both VOLE-in-the-Head and Ligero, yielding post-quantum security based solely on collision-resistant hashing. (ii) In the online phase, we propose a constant-round protocol that tightly integrates secure multiplication-and-opening with distributed zero-knowledge proof (DZKP) verification, reducing communication in every setting we evaluate and computation in all but the largest batched setting, compared to naively using the standard DZKP framework. (iii) We give a verifiable input protocol that enforces a possibly-malicious client providing well-formed inputs; its well-formedness check is absorbed into a hash exchange the online protocol already performs, and it lowers the client's upload from a full replicated share to one field element per server per input. Our end-to-end benchmarks show that the construction substantially outperforms the state-of-the-art Legendre-PRF dOPRF of Kaluđerović et al. (ESORICS 2025) in terms of communication across all evaluated settings, and remains practical up to $(n,t)=(9,4)$, a regime where prior approaches become bandwidth- or memory-prohibitive.

Generative large language models (LLMs) have achieved state-of-the-art performance on many real-world tasks such as code generation and question answering. These models predominantly rely on an autoregressive decoding strategy that generates output tokens sequentially. However, their pervasive deployment raises serious privacy concerns, motivating private inference frameworks based on fully homomorphic encryption (FHE). A major limitation of existing FHE frameworks is their inefficiency in evaluating nonlinear operations, which incur substantial overhead and dominate the decode stage. In this paper, we propose ROSETTA, a hybrid CKKS/TFHE framework that overcomes this limitation. We first observe that nonlinear operations in the decode stage exhibit heterogeneous workload patterns, which can be handled effectively via a hybrid approach. We then realize this with two key contributions: 1) an adaptive segmented lookup-table protocol based on TFHE that enables efficient and accurate evaluation of nonlinear operations; and 2) a scheme-aware operator-selection framework that automatically assigns each nonlinear operator to CKKS or TFHE to minimize end-to-end decoding latency. We demonstrate that ROSETTA achieves up to 4.8x Softmax speedup and 1.5--2.1x end-to-end speedup over the SOTA framework CacheMir.

The alternative mod-$2$/mod-$3$ function is one of the most widely used weak PRF constructions in modern cryptographic protocols. Despite its practical importance, its security has received relatively limited attention, with the main cryptanalytic results consisting of two distinguishing attacks due respectively to Cheon et al. and Johansson et al. In this work, we revisit the cryptanalysis of this primitive by analyzing the output distribution of the weak PRF under fixed Hamming weights for both the secret key and the inputs. This refined analysis allows us to isolate and amplify statistical biases that were averaged out in previous works. Using this approach, we derive a new distinguishing attack with asymptotic data and time complexity $\mathcal O(2^{0.099n})$. We implemented the attack for the original parameter set $n=384$, thereby obtaining the first practical attack against this instance of the construction. We then introduce a generic technique, called the splitting strategy, which consists in partially fixing or guessing part of the secret key in order to amplify the biases while introducing an additional computational cost that can be efficiently handled using Fast Fourier Transform-like techniques. This leads to the currently best known attack against the construction, with asymptotic data, time, and memory complexities $\widetilde{\mathcal O}(2^{0.09n})$. This last technique also provides a useful time-memory trade-off for estimating the security of real-world constructions when the available data is bounded: we show that the weak PRF offers less than $128$-bit security for $n = 510$ when the data is limited to $2^{45}$. Finally, we revisit the attack of Johansson et al. and provide a corrected and refined analysis of the underlying bias, showing that the statistical behavior of the attack differs significantly once the Hamming weight of the secret key is taken into account. This new analysis explains phenomena previously observed experimentally but left unexplained. Thanks to this approach we are able to identify a large class of keys for which the attack performs much better asymptotically than anticipated by Johansson et al.

Falcon is one of the 3 post-quantum signature schemes already selected by NIST for standardization (as FN-DSA). It is very compact and efficient, but also infamously difficult to implement correctly and securely. This is due in particular to its reliance of various floating point operations, the most complex and costly of which are square root computations. In this paper, we first point out that those square root computations are in fact wholly unnecessary: the algorithm can be rewritten without them, resulting in a somewhat simpler implementation that is equally fast or even slightly faster. We then observe that they also present security risks, in particular as a singularly sensitive target for physical attacks. We demonstrate this with a fault attack, supported by concrete experiments against an ARM Cortex-M4 microcontroller target. We show that injecting a single glitch in one square root computation, and then generating around a million signatures with the unperturbed signing algorithm, leads to full key recovery with 100% success rate and, moreover, faulty signatures are not easy to distinguish from validly generated ones. This makes this fault attack the most devastating against Falcon to date, in contrast with earlier attacks requiring hundreds of millions of signature samples, many injected faults, or resulting in signatures that are straightforward to distinguish from regular ones. In addition, we mention potential risks of the square root computations from the standpoint of dependency management and supply chain security.

In the NIST post-quantum standardization process, Fujisaki-Okamoto-like (FO-like) transformation has become the de facto paradigm for constructing IND-CCA secure key encapsulation mechanisms (KEMs) from public-key encryption (PKE). However, most post-quantum PKE schemes exhibit decryption error, which poses significant challenges for the security proofs of FO-like PKE-to-KEM transformations, particularly in the quantum-accessible random oracle model (QROM). Hofheinz, Hövelmanns, and Kiltz (TCC 2017) gave the first QROM security proofs for PKE-to-KEM transformations under \textit{worst-case} decryption error. To relax this to the more designer-friendly one of \textit{average-case} decryption error, Duman et al. (PKC 2023) presented two transformations, $\mathsf{FOAC}_0$ and $\mathsf{FOAC}$, which are under average-case decryption error but introduce substantial loss in QROM reduction tightness ($\mathcal{O}(q^8)$ for $\mathsf{FOAC}_0$ and $\mathcal{O}(q^6)$ for $\mathsf{FOAC}$) and the need for the $\gamma$-spread assumption on the underlying PKEs. Very recently, Ge et al. (ePrint 2025) removed the $\gamma$-spread assumption for $\mathsf{FOAC}_0$ and improved the QROM reduction tightness to $\mathcal{O}(q^4)$ for both $\mathsf{FOAC}_0$ and $\mathsf{FOAC}$. In this work, we make further advances by introducing two refined variants: $\mathsf{FOAC}'_0$ and $\mathsf{FOAC'}$. We provide new security analyses in both the ROM and the QROM, and present the following key contributions: (1) Compared with previous transformations under average-case decryption error, $\mathsf{FOAC}'_0$ and $\mathsf{FOAC'}$ exhibit tighter security proofs with QROM reduction loss of only $\mathcal{O}(q^2)$ for $\mathsf{FOAC}'_0$ and $\mathcal{O}(q^3)$ for $\mathsf{FOAC'}$ when the underlying PKE is OW‑CPA secure, and just $\mathcal{O}(q)$ when it is deterministic or IND‑CPA security; (2) Both $\mathsf{FOAC}'_0$ and $\mathsf{FOAC'}$ eliminate the $\gamma$-spread assumption entirely, further relaxing the requirements on the underlying PKE. To support our QROM proofs, we provide three new QROM proof techniques that build on Zhandry's compressed oracle technique (CRYPTO 2019). These techniques may be of independent interest and could have broader applicability in post-quantum cryptography.

We present a practical component-wise fault injection attack against randomized MAYO implementations. The attack targets the final addition of oil and vinegar components during signing. Depending on compiler optimization, a fault may expose either oil coefficients directly or vinegar coefficients that can be used to recover the oil coefficient via the public verification algorithm. By accumulating partial coefficient-wise information across multiple faulty signatures and exploiting the linear structure of the oil space, we recover the full secret oil space. Unlike prior attacks, our method does not rely on deterministic signing, memory reuse, or faulting a hash function. We validate the attack on ARM Cortex-M4 platforms using clock glitching and electromagnetic fault injection, and recover the MAYO-1 secret oil space for both the -O3 and -Os compiler optimization settings. Additionally, we analyze several countermeasures against our attack, showing that some are ineffective or increase the attack cost, while others provide effective protection at additional implementation cost.

Secure multi-party computation (MPC) traditionally assumes that parties execute protocols on trustworthy machines. This assumption fails under machine subversion, where compromised devices may leak sensitive information through manipulated protocol transcripts. Reverse Firewalls (RFs), introduced by Mironov and Stephens-Davidowitz, counter this threat by externally sanitizing messages in a functionality-preserving manner, without trusting the internal execution environment. Prior RF constructions are limited to Boolean-circuit-based MPC using oblivious transfer (OT) and garbled circuits (GC). In contrast, many high-performance MPC protocols are predominantly arithmetic, relying on Oblivious Linear Evaluation (OLE) as a core primitive. Achieving subversion resilience in this setting requires sanitizing OLE, a problem that has remained open. We initiate a systematic study of subversion-resilient arithmetic MPC in the universally composable (UC) framework against semi-honest adversaries. We formalize a sanitizable OLE functionality \FsOLE, prove a two-round impossibility for a natural class of additive homomorphic encryption (AHE)-based protocols, and present a UC-secure three-round construction from key-malleable AHE. To recover the full expressiveness of plain OLE, we further introduce wrapped sanitizing OLE under a covert adversary model, yielding an efficient UC-secure two-round protocol. Both constructions are instantiated using a key-malleable AHE scheme from class groups that we construct. Using OLE as a black box, we obtain the first subversion-resilient UC-secure protocols for Oblivious Polynomial Evaluation (OPE), Oblivious Polynomial Addition (OPA), and Private Set Intersection (PSI), achieving optimal communication for PSI. A full end-to-end implementation demonstrates that RF protection incurs only a 1.5--3X overhead, showing that practical subversion-resilient MPC is attainable.

Anonymous communication is one of the fundamental tools to achieve privacy for communication over the internet. Almost all existing design strategies (e.g., onion routing/Tor, mixnets) for anonymous communication rely on the existence of some honest server/router in the network infrastructure to provide anonymity. A seminal work by Shi and Wu (Eurocrypt 2021) proposes the first cryptographic design for a non-interactive anonymous router (NIAR) that can use a single untrusted server or router to permute a set of messages without revealing the permutation to the untrusted router. This work is a really important step towards showing the possibility of designing such protocol from standard cryptographic assumptions. However, the existing constructions are only of theoretical nature and still leaves many open questions towards realizing such systems in practice: (1) the cryptographic building blocks used in those designs are really difficult to implement in practice. (2) Their setup phase takes the permutation as an input to generate the encryption/decryption keys; which means that the messages from the same sender in different rounds will be at the same position in the output vector, unless the setup phase is run before every round with a new permutation. (3) It is not known how to realize such a setup procedure, that initializes a random permutation obliviously, without any trusted entities in the system. In this paper, we propose the first (somewhat) practical design, which we call sPAR, that solves the above problems. Our design also relies on a one-time setup phase, however the setup phase does not take any specific permutation as input. Instead, our design can reuse the same setup for many rounds and generates a fresh permutation for every round based on the random values locally generated by the clients. Our design is implementable and deployable in practice; and this presents a new direction for designing anonymous communication systems. Unlike some existing systems like Tor, sPAR does not scale to millions of users, however, we demonstrate with a proof-of-concept implementation that sPAR supports around one hundred users, and show that an optimized variant of our algorithm reduces the latency to a few seconds per message.

What is the round complexity of $n$-party secure multiparty computation (MPC) over point-to-point networks in the dishonest-majority setting with unanimous or identifiable abort? Despite decades of research, this foundational question remains open. While two-round MPC is achievable given a broadcast channel, and broadcast protocols with expected-constant rounds exist tolerating any constant fraction of corruptions, a naive combination of the two yields MPC with expected $O(\log n)$ rounds. The core obstacle lies in maintaining round efficiency under parallel composition without an honest majority. Moreover, existing lower bounds for standard broadcast do not apply to broadcast with abort, leaving the exact round complexity of this setting unknown. In this work, we systematically investigate the round complexity of MPC over point-to-point networks, providing positive and negative results: - We show that any broadcast protocol (and thus generic MPC) with unanimous abort tolerating super-constant corruptions requires super-constant rounds, ruling out strict-constant-round protocols. - We construct a round-preserving, black-box parallel composition compiler for broadcast with unanimous abort. This yields our main result: Expected-constant-round MPC with unanimous abort in the PKI model against any constant fraction of corruptions, assuming oblivious transfer (OT) and verifiable random functions (VRFs). - Finally, we prove that expected-constant round broadcast (and MPC) with identifiable abort is impossible against $n - o(n)$ corruptions.

We revisit the security bounds of Sparkle+, the threshold Schnorr signature scheme which first appeared in 2023. This scheme has been updated and corrected in several versions and papers (also of other authors). However, no version or paper has checked in detail the final bounds of Theorem 1 and 2 of the June 2025 version, which have therefore, to the best of our knowledge, been taken for granted in the related literature. There, the derivation of the final bounds of its Theorems 1 and 2, on full static security under DL and on adaptive security up to $t/2$ corruptions under AOMDL, from the intermediate inequalities established by their proofs is left to the reader. Carrying it out, we obtain bounds that differ from the stated ones in three distinct algebraic respects: the terms produced by the two game hops precede the rewinding and therefore appear outside the square root rather than inside it; the whole game-hop aggregate, and not only its collision part, re-enters through the extraction inequality with coefficient $2q$ rather than $1$; and the exact inversion of the general forking lemma contributes $q/2p$ outside the root together with $q^2/4p^2$ inside it, with $q$ the number of queries and $p$ the group order, its standard relaxation combining the two into an additive $q/p$, and the statements carry none of this. We prove the bounds that do follow, for both theorems, and determine exactly when each of ours and the original is the tighter. Conditional on the correctness of the game transitions from which those inequalities come, the asymptotic security conclusions are unaffected.

Blind signatures and OPRFs are widely used to build anonymous tokens and privacy-preserving protocols. This paper shows that several prior claims of blindness and request-privacy for such primitives are false under the standard security definitions. In particular, we give explicit malicious-signer/evaluator adversaries showing that the theorems claimed for several existing constructions, including the blind ECDSA scheme of Qin et al. and the verifiable Dark Matter OPRF, do not hold. The attacks exploit a simple but previously overlooked channel: a malicious signer can craft its response so that the honest user's final verification aborts if and only if the user's hidden message satisfies a chosen predicate. The abort/no-abort outcome, therefore, becomes a one-bit testing oracle on the hidden message. Importantly, this is not a failure of the standard blindness definition: our attacks win the standard blindness/request-privacy games. Rather, the flaw is that prior proofs implicitly used encryption hiding or commitment hiding in settings where the adversary also learns an input-dependent abort event. Our main attack applies to a general pattern of homomorphic-encryption-based blind signatures and OPRFs, in which the user encrypts its input, then decrypts and verifies the signer's homomorphic response. We also present two additional case studies, based on derandomization and selective use of signer components, which illustrate the same proof pitfall in other constructions. We identify a positive design criterion: schemes with publicly checkable signature derivation, in the sense of Fischlin-Schröder, do not leak extra information through such selective aborts. Finally, we discuss mitigations. Generic protection requires publicly verifiable honest evaluation, e.g., via zero-knowledge proofs. For random-token use cases of some HE-based blind signatures, we give a partial mitigation based on random unknown-message blindness RUMBL and a random-oracle transformation to standard blindness.

Ideal lattices over number fields play a central role in post-quantum cryptography, as evidenced by the NIST-standardized schemes Kyber and Dilithium. Understanding the hardness of ideal-lattice problems such as the Unique Shortest Vector Problem (Id-uSVP) and Bounded Distance Decoding (Id-BDD) is therefore essential. Recent works have shown that certain algebraic symmetries can significantly reduce the dimension of the Ideal-SVP problem. In particular, subfield attacks exploit the decomposition group to solve SVP in a smaller subfield. However, existing reductions are limited to SVP and rely on multiplicatively closed substructures. In this work, we introduce a representation-theoretic framework for solving Id-uSVP and Id-BDD. Let $K/\mathbb{Q}$ be an abelian extension whose Galois group $G$ is known, and let $I$ be an integral ideal of $K$ stabilized by a nontrivial subgroup $H\subseteq G$. We use the irreducible rational representations of $H$ to construct scaled projection operators $q_i$ that decompose $K$ into a direct sum of linear subspaces $V_i$. Applying these operators to $I$ yields low-dimensional lattices $I_i = q_i(I)$. We show that an Id-BDD instance $(t,I)$ can be solved by solving independent BDD instances on the $I_i$'s and recombining the solutions, provided the target is within a distance bounded by $\lambda_1(I)/(2|H|^2)$. For Id-uSVP, we prove that under mild uniqueness conditions a shortest vector of $I$ lies in at least one of the nonzero $I_i$. In cyclotomic fields, the rotation property gives two stronger results: (i) every nonzero $I_i$ contains a shortest vector of $I$, so solving SVP on the lowest-rank nonzero $I_i$ suffices; and (ii) BDD is further accelerated by reducing a single instance to $n$ low-rank instances on the same lowest-rank nonzero $I_i$. To the best of our knowledge, our approach is the first to employ group representation theory directly in lattice cryptanalysis. It addresses the limitation of previous subfield methods that they cannot solve BDD, removes the need for multiplicative closedness, and remains at least as efficient as prior SVP reductions. These results refine the understanding of the hardness of structured lattice problems and have implications for the security analysis of cryptosystems with additional algebraic structure.

Folding is a powerful technique for constructing efficient succinct proof systems, especially for computations that are expressed in a streaming fashion. We present PikkuFold, a new lattice-based folding protocol that improves upon state-of-the-art folding schemes such as SALSAA (ePrint 2025/2124) and Cyclo (EUROCRYPT 2026). One folding step communicates $5.7$ KB beyond the commitments to its fresh inputs, against $\geq 30$ KB for Cyclo and $\geq 60$ KB for SALSAA on similar instances, with a prover more than an order of magnitude faster and the verifier in the millisecond range. At the heart of our construction are layered random projections, whose algebraic structure makes them fast to verify and whose final image is short enough to send to the verifier directly, cutting out the cost of auxiliary commitments. We use those techniques to replace the extensive and restrictive range proofs of Cyclo, while still achieving only a small additive increase in the accumulator norm across multiple folds. PikkuFold is the first lattice-based construction that does not require any in-protocol commitments beyond those of the fresh inputs. Such commitments are the heavy part of a folding transcript: every prior lattice-based scheme commits to a decomposed or otherwise transformed witness during the fold, immediately increasing the communication by dozens of kilobytes. On top of that, we provide two contributions of independent interest, applicable beyond the context of folding schemes: (i) a Johnson-Lindenstrauss theorem for biased ternary matrices modulo $q$ with certified concrete constants, which replaces the heuristic parametrisation of prior works, and (ii) a thorough analysis of the short-challenge sampler with fixed Hamming weight and operator-norm rejection, offering a wide range of parameter sets. Using this sampler as a drop-in replacement would lead to immediate improvements in a wide family of lattice-based protocols.

Plaintext-checking oracle (PCO) attacks are among the most prominent types of attacks against NIST's recently standardized ML-KEM. Previous works have drastically reduced the number of queries needed to recover the secret key. Although this number is now close to the information-theoretic bound, current attacks have not yet been adapted to settings with increased noise and highly imperfect oracles. In attacks targeting real-world protected implementations, noisy leakage may lead to oracles that only provide a small advantage over guessing. This work shows how to efficiently exploit imperfect oracles arising from highly noisy side channels. We present several soft-analytic techniques that enable highly noise-tolerant parallel PCO attacks. These techniques allow for successful attacks in relatively few traces from information that gives just a slight advantage over guessing. Additionally, we extend the generic framework for side-channel information from Eurocrypt 2025 and thereby relate our techniques to previous work. We then discuss several oracle instantiations that are based on the noisy Hamming weight model. These oracles rely on widely accepted assumptions, are easy to simulate, and allow for fair comparisons between different attacks. Furthermore, they allow taking countermeasures into account, and we evaluate the impact of masking. Our evaluations in these and previous models show that PCO attacks are noise-tolerant on an entirely different scale compared to previous work. These improvements are of an algorithmic nature and orthogonal to the fact that the Fujisaki-Okamoto transform in ML-KEM offers a large attack surface. Finally, we discuss the implications of our findings for protected ML-KEM implementations.

Side-channel analysis (SCA) has historically developed along two parallel research avenues: key recovery attacks (e.g., CPA, MIA, Templates) and leakage assessment methodologies (e.g., TVLA, $t$-tests, $F$-tests, Kolmogorov-Smirnov tests). While both paradigms fundamentally process trace distributions partitioned by intermediate values or key hypotheses, they are typically viewed as disparate techniques with distinct mathematical formulations. In this paper, we propose a unifying statistical framework that decomposes side-channel distinguishers into orthogonal building blocks: (i) a subkey-induced leakage partition, (ii) a distribution comparison statistic (categorized into binary (two-distribution) or multi-class (multi-distribution) comparison operators), (iii) an aggregation operator over pairwise distribution comparisons, and (iv) a global decision rule. This formalization proves that classical key distinguishers and leakage tests are instances of a single generic model. Furthermore, our framework transforms statistical leakage tests into fully functional key recovery attacks, naturally introducing novel distinguishers based on non-parametric statistics (Kolmogorov-Smirnov, Anderson-Darling, MMD, Energy Distance) paired with suitable aggregation operators. We evaluate 18 statistical metrics across experimental configurations combining 8-bit AVR XMEGA and 32-bit ARM Cortex-M4 targets, unmasked and masked AES, under both targeted and automated POI scenarios. Our results demonstrate that the vast majority of these newly introduced attacks successfully achieve complete key recovery. Crucially, no single metric consistently dominates across all targets and leakage conditions, highlighting the complementary nature of statistical distinguishers and paving the way for metric combination and ensemble strategies.

The VOLE-in-the-Head (VOLEitH) paradigm compiles VOLE-based zero-knowledge proofs into publicly verifiable post-quantum signature schemes. A central component of VOLEitH is a GGM-style tree used to realize a vector commitment, whose size dominates the signature. In this work, we adapt vector semi-commitment (VSC)---previously developed for MPC-in-the-Head (MPCitH) by Kim et al. (\emph{Eurocrypt 2025})---to the VOLEitH paradigm and prove its security. While prior MPCitH analyses relied on assumption-specific, fragmented security proofs, we give a \emph{unified} treatment that characterizes which abstract property the underlying tree must satisfy, and instantiate it under the random oracle, Davies--Meyer, counter (CTR), and pseudorandom generator (PRG) models. Building on this, we construct reduced VOLE-in-the-Head (rVOLEitH) and apply it to FAEST, one of the NIST additional post-quantum signature candidates, obtaining signature sizes comparable to those of FAEST v2.0, ranging from 94.9\% to 102.8\% of the corresponding FAEST v2.0 sizes, while attaining 27.7--124.2\% faster signing and 28.3--115.3\% faster verification for 128-bit parameters. Finally, we describe a forgery attack on a recently proposed VOLEitH variant of the subfield bilinear collision (SBC) signature scheme by Huth and Joux (\emph{Asiacrypt 2025}) which replaces leaf commitments with a single global commitment, demonstrating the necessity of the commitment structure retained by VSC.

We present a machine-checked security proof for the NTOR key exchange protocol, which is used to establish connections in the Tor onion routing system. It was previously studied by Goldberg et al. (DCC 2013) and the protocol ladder project, however there is no full proof including forward secrecy in the computational model. Our proof is formalized in EasyCrypt, adding to the still small set of cryptographic protocols verified using EasyCrypt. A key contribution is a systematic treatment of halting reductions involving failure events expressed as global properties of the execution. In the course of this work, we also contributed improvements to the EasyCrypt framework itself. We prove NTOR secure in a model for unilaterally authenticated key exchange (UAKE) similar to the maximum exposure model by Fiedler et al. (Crypto 2025). It captures forward secrecy concretely, and is intentionally close to established bilaterally authenticated key exchange models (such as eCK) while being simple to formalize. By examining more carefully how identities and public keys are used in key exchange protocols, we obtain simpler formal arguments and introduce several variants of the UAKE security model, connected by general reductions that, in the case of NTOR, are also verified in EasyCrypt. This allows us to carry out the main proof in a simpler setting and then derive the desired security guarantee for NTOR via these reductions.

We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct claw-state generation protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.

Tools for generating deep fake photographs are proliferating with greater ease of use and prominence in pop culture. Image authentication tools can defeat these deceitful developments by verifying that a digital image was actually produced by a physical camera. The challenge is that these tools must be robust to desirable image transformations. Camera attestation uses digital signatures to prove an image's provenance from a camera. Lossy compression makes minute changes in order to reduce an image's size, and blurring or redacting regions of an image can protect its subjects. These changes invalidate an image's signature. Prior works use zero-knowledge (ZK) to prove a published image's edit history, but they do not survive lossy encoding such as the JPEG format. We present \zkjpeg, a cryptographic tool for JPEG compression that proves an image was correctly compressed from a secret, committed input. In addition, our tool can verify a large family of image transformations by integrating them into JPEG compression with minimal cost. Our system is fast, flexible, and can be instantiated from off-the-shelf ZK tools. We use PicoZK to convert Python image editing code into a ZK circuit for the line-point zero knowledge (LPZK) proof system.

Lightning's BOLT 12 (offers, onion messages, blinded paths) is the largest addition to the Lightning protocol suite, and it is rolling out now. The specification changed three times in 2026, the community is actively debating its privacy posture, and its newest mechanism, Payer Proofs, landed in July 2026 without any analysis. We give the offer family its first formal treatment, covering the full lifecycle from request to receipt, pinned to specification commits e20a924/1528972 and machine-checked in twenty-two ProVerif models that each converge within seconds. The results read as a map rather than a checklist: the family's privacy and integrity rest on seven bindings, removable assumptions whose removal consequences we check row by row. Receiver anonymity and payer-payee unlinkability hold under unbounded sessions and corrupted path nodes, and every protocol-level attack we exhibit lands on an assumption the specification already leans on out-of-band. The map's structure is itself the finding. The blinding key chain, designed for unlinkability, authenticates recipient-side transit for free, while the payer side's delivery binding rests on implementation discipline alone. The newest part of the specification, its payment receipts, turns out to hide a precise disclosure boundary. We close with six testable recommendations for the BOLTs repository.

Silent payments (BIP-352) let Bitcoin users publish one static address and receive at fresh, unlinkable outputs. The protocol already ships in major wallets, yet its own specification concedes it has no formal security proof—and 2026 brought a worst-case scanning attack, a funds-locking hardware-wallet disclosure, and an omitted-payment bug. We supply the missing analysis. Receiver and co-transactor unlinkability are proved under DDH, with the label system as a corollary that includes an executable linking attack and its fix. We then quantify what scanning costs and what an attacker can buy with it. The community's K_max cap turns quadratic attack amplification into linear; every compliant scanner needs Ω(N+KM) work; our set-probing scanner meets this bound and runs 39× faster in our measurements; and a year of fee data prices a full-block attack as low as 0.0015 BTC. For collaborative transactions we show what the specification's warning was about (the transaction assembler can always identify the recipient's output, and malformed partial secrets burn payer funds, the failure class disclosed in August 2026), and we construct the variant the warning called for: blind collaborative payments with information-theoretic payer privacy. Delegation, finally, offers no safe default: scanning servers either learn too much or can hide payments. A twelve-experiment benchmark suite accompanies the paper.

In this work, we construct highly efficient pseudorandom correlation generators (PCGs) over binary extension fields. PCGs allow for the distribution of a great amount of correlated randomness by having each party locally expand a short seed, enabling efficient multi-party computation (MPC) protocols with silent and sublinear preprocessing. Our PCGs achieve nearly linear time, both asymptotically and concretely, where expanding $N$ VOLEs (vector oblivious linear evaluations) over $\mathbb{F}_{2^k}$ consists of $O(N)$ PRG calls, $O(N)$ multiplications in $\mathbb{F}_{2^k}$ and $O(kN\log{N})$ binary XORs. In fact, the $O(kN\log{N})$ XORs are insignificant in practical parameter regimes where $N\approx 2^{20}$. Concretely, we achieve a throughput of $\approx 5,000,000$ VOLEs per second over $\mathbb{F}_{2^{128}}$, which is at least $4.7$x, $1.9$x and $1.6$x faster than the state-of-the-art PCGs of Expand-Accumulate (EA), Block-Accumulate (BA) and Expand-Convolute (EC) codes, respectively. For oblivious linear evaluations (OLEs), expanding $N$ instances requires $O(\lambda N)$ PRG calls, $O(N)$ multiplications in $\mathbb{F}_{2^k}$ and $O(kN\log{N})$ binary XORs, where $\lambda$ is the security parameter. Based on the $\mathsf{libOTe}$ library, we also give the first full implementation of PCGs for OLEs over extension fields, which shows a throughput of $\approx 42,000$ OLEs per second over $\mathbb{F}_{2^{128}}$. At the heart of our technical contribution is an efficient multivariate FFT algorithm. It evaluates any $n$-variate polynomial $f(x_1,\ldots,x_n)$ over $\mathbb{F}_{2^k}$ of individual degree$\le2$ using exactly $\frac{5}{6}kN\log_3{N}$ additions and $\frac{1}{6}kN\log_3{N}$ multiplications in $\mathbb{F}_4$, where $N=3^n$ and $k$ is an arbitrary even integer. Note that this is considerably faster than normal FFT algorithms that require $O(N\log{N})$ multiplications in the underlying field $\mathbb{F}_{2^k}$. Along the way, we generalize our approach to work over a degree-$k$ Galois extension of $\mathbb{Z}_{2^{\ell}}$, denoted by $\mathbb{GR}(2^{\ell},k)$. Similarly, our algorithm takes only $\frac{7}{6}kN\log_3{N}$ additions and $\frac{1}{6}kN\log_3{N}$ multiplications in $\mathbb{GR}(2^{\ell},2)$ to evaluate $f(x_1,\ldots,x_n)\in\mathbb{GR}(2^{\ell},k)[x_1,\ldots,x_n]_{\leq 2}$. This implies practically efficient PCGs for (V)OLE over Galois rings. As a side contribution of independent interest, we derive fast encoding algorithms for a family of Quasi-Abelian codes, which are even concretely $1.66$x faster than Repeat-Accumulate-Accumulate (RAA) codes over $\mathbb{F}_{2^{128}}$, whose encoding only involves a linear number of additions and two random permutations. As Quasi-Abelian codes have been proven to attain concretely large minimum distance in a recent work of Li et al. (CRYPTO 2026), this opens a door to building more efficient succinct arguments over extension fields.

Safety and liveness are the two classical pillars of payment channel security. Both price attacks that merely occupy channel resources, such as jamming, at zero. We propose a third pillar, deterrence: harm carries a provable price. We give its theory for occupied shared-state resources. Within a holding-cost framework, we characterize occupation pricing for lock-resolve channels. Time-dependence in the occupier's liability is necessary for any deterrence: today's time-independent pricing admits unbounded griefing, with damage-to-cost ratios above 10^7. Linear time-proportional liability achieves the tight rate. Its two faces, deadline-proportional upfront fees and hold-proportional penalty bonds, differ exactly in what they charge honest traffic. Our main theorem maps the landscape of four desiderata: deterrence against colluding sinks, penalty-only honesty, zero intermediary lockup, and path privacy. Three of them are jointly unachievable, and every remaining combination is achieved by a matching construction; onion-message fee-swallowing gives a second enforcement instance. Single-channel enforcement is characterized exactly: penalty-only pricing is unilaterally enforceable if and only if scripts expose time. The proof is a three-case exhaustion, and it explains why pre-BIP65 Bitcoin could not support trustless occupation pricing. Our flagship fused-bond construction runs on Bitcoin today, with no covenants, oracles, or miner assumptions; it improves slot-jamming deterrence by eight orders of magnitude at zero net cost to punctual honest payments. For multi-hop payments we prove the forwarding trilemma, settling a 2020 conjecture of the Lightning engineering community, and we quantify the price of privacy, including a new O(1/n) extreme-value side channel on the sender's path length.

The 5G-Advanced air interface is acquiring its first AI-native functions (AI/ML-based CSI feedback compression and beam management, studied by 3GPP since Release 18) and their models increasingly arrive through third-party supply chains. We present the first cross-use-case backdoor study of this interface. Poisoning as little as 0.5% of the training data implants an arbitrary trigger-to-target association into CRNet (and, at 5% poisoning, into CsiNet): attack success is 100% with no measurable clean cost, with physical triggers so weak that a 2-bit RIS suffices to launch them. The same trigger and pipeline hijack a second standardized function, beam prediction, with 99.5% success. Hijacked feedback steers gNB beamforming toward a phantom channel: a victim's rate falls by 98%, and the diverted beam concentrates 88% of the array-gain ceiling onto the attacker, raising interception probability to 100%. An adaptive attack that matches codeword statistics drives both statistical detectors from ≈1.0 to 0.53 AUC with attack strength unchanged, yet behavioral consistency still detects it: codewords can be disguised, behavior cannot.

Private Set Intersection (PSI) enables two parties to compute the intersection of their private sets without revealing any additional information. For plain PSI, there exist extremely efficient solutions based on symmetric-key techniques for both the semi-honest and malicious settings. However, for more enriched set operations such as PSI-Cardinality, PSI-Sum, Circuit-PSI, and Private Set Union, the efficiency gap between the semi-honest and malicious settings is significant, often spanning orders of magnitude. A key bottleneck underlying these protocols is the need for a shuffled distributed oblivious pseudorandom function (SH-DOPRF) with malicious security. Existing constructions for this primitive are asympotically suboptimal and/or concretely inefficient. In this work, we present a new protocol for SH-DOPRF with malicious security that achieves linear computation and communication complexity. We present two instantiations: a DDH-based construction using the Dodis-Yampolskiy PRF (PKC 2005), and a plausibly post-quantum secure construction based on a variant of the Dark-Matter PRF (Aranha et al., S&P 2026). Our approach is almost entirely based on symmetric-key techniques, with public-key operations used only for evaluating PRF outputs. This primitive yields maliciously secure protocols for multi-query reverse private membership test (Zhang et al., USENIX Security 2023), which in turn can be used to realize the aforementioned private set operations. These protocols provide two-sided outputs while only additionally leaking the cardinality of the intersection. We implement and evaluate our construction to demonstrate concrete efficiency. Our DDH-based maliciously-secure SH-DOPRF achieves a 2--3 orders of magnitude improvement in total running time compared to the state-of-the-art (Miao et al., CRYPTO 2020 & Yang et al., PoPETs 2025), leading to a similar improvement for PSI-Cardinality. The resulting protocols for various other private set operations also achieve significant improvements over prior work; for example, our PSI-Sum and Circuit-PSI protocols are 1--2 orders of magnitude more efficient.

Zero-knowledge proofs (ZKPs) based on vector oblivious linear evaluation (VOLE) excel in prover efficiency but typically require linear communication and verification. Antman (Weng et al., CCS '22) introduced information-theoretic polynomial authentication codes (IT-PACs) to achieve sublinear communication: $O(B + C)$ for SIMD (single-instruction-multiple-data) circuits and $O(B^3 + C)$ for general circuits, where $N=B \cdot C$ is the total circuit size and $B,C$ are batch size and subcircuit size, respectively. Antman++ (Bui et al., J. Cryptol. '25) further reduced the general-case communication to $O(B + C)$. However, these protocols remain interactive and cannot be made non-interactive via traditional techniques like Fiat-Shamir, due to limited functionalities of IT-PACs; also, the verifier of Antman++ is not succinct for processing $N\times N$ public matrices. In this work, we present a succinct non-interactive ZKP system $\mathsf{Wasp}$. Specifically, (1) we enhance the IT-PAC primitive to a fully functional polynomial commitment scheme (PCS) with the support of generic evaluation openings. With this PCS, we construct $\mathsf{Wasp^S}$, a non-interactive ZKP for SIMD circuits based on Antman; also, we build $\mathsf{Wasp^G}$, a general zkSNARK with constant verifier time and proof size based on the Plonkish constraint system. (2) We optimize the SIMD-to-general compiler from Antman++ by exploiting sparse representation of matrices and extending preprocessing techniques to the SIMD setting, and achieve a sublinear verifier. All our protocols achieve non-interactivity in the VOLE-hybrid model (i.e., given preprocessed VOLE correlations). Experiments show the non-interactive verifier of our SIMD zkSNARK $\mathsf{Wasp^S}$ is $1\sim 2$ orders of magnitude faster than the interactive one of Antman; when compiled with our compiler, the general-case verifier is $2\sim 3$ orders of magnitude faster than the one in Antman++. Our general zkSNARK $\mathsf{Wasp^G}$ has a $1\sim 2$ orders of magnitude faster prover than pairing-based, coding-based and lattice-based zkSNARKs, with less than 1 ms verifier time and 122 KB proof size; compared to the non-succinct VOLE-based ZKP, $\mathsf{Wasp^G}$ is $3\sim22\times$ slower in proving but can be 4 orders of magnitude faster in verification with $3$ orders of magnitude smaller proof size.

A Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size $n$. Lin, Mook, and Wichs (STOC 2023) presented the first DEPIR, from RLWE, and Lee (Crypto 2026) gave a barely doubly-efficient scheme from LWE in the CRS model, answering each query in $o(n/\log n)$ time. These are essentially the only constructions known, and both rest on lattices. Whether DEPIR could be realized from non-lattice-based foundations, particularly from number-theoretic assumptions, remained in doubt. In this work, we construct a DEPIR scheme from quadratic residuosity in the CRS model, answering each query in $o(n/\log n)$ time. As in Lee's LWE-based construction, our scheme leverages Williams's matrix-vector multiplication preprocessing (SODA 2007). Privacy follows from the pseudorandomness of Legendre symbols under quadratic residuosity, proved by Corrigan-Gibbs and Wu (TCC 2025). To cope with a new modulus at every query, we additionally develop a data structure that reduces a preprocessed integer modulo any modulus in sublinear time.

The growing deployment of large language models (LLMs) in privacy-sensitive settings demands inference mechanisms that preserve data confidentiality. Homomorphic encryption (HE) offers a principled solution by enabling computation directly on encrypted data; however, existing solutions struggle to scale to full LLMs. We present Tricycle, a system for efficient private transformer inference. At its core, Tricycle introduces tricyclic encodings, a novel packing scheme that enables batch matrix multiplications with optimal multiplicative depth while naturally supporting multi-head attention. We demonstrate that Tricycle's matrix multiplications are particularly amenable for integration with other optimizations including Baby-Step Giant-Step optimizations, optimized block matrix multiplications, lazy relinearization, and complexification, which significantly improve performance. We further introduce statistical max estimation, a lightweight method for stabilizing softmax under HE. We implement Tricycle end-to-end on a GPU-accelerated CKKS pipeline and evaluate it on BERT models. For BERT-Base with 128 tokens, Tricycle achieves 100.5 seconds latency on a single GPU, yielding $6\times$ and $3.4\times$ speedups over prior state-of-the-art systems, Thor and Powerformer, respectively. These results demonstrate that careful design of packing, algorithms, and optimizations can significantly reduce the cost of private LLM inference, bringing practical deployment closer to reality.

We study the optimal dimension-free constant $C_*(a)$ in Talagrand's Boolean convolution inequality $\Pr_\mu[T_af\ge u]\le C_*(a)/(u\sqrt{\log u})$, where $T_a$ is the noise operator, $\mu$ is the uniform measure on the Boolean cube, $f\ge0$ satisfies $\mathbb{E}_\mu[f]=1$, and $u>1$. We establish explicit upper bounds for every $0<a<1$ and prove $\limsup_{a\uparrow1}C_*(a)/\sqrt{\kappa_a}<0.3577$, where $\kappa_a:=(1+a)/(1-a)$. We establish the lower bound $\liminf_{a\uparrow1}C_*(a)/\sqrt{\kappa_a}\ge0.3570$.

Doubly-efficient private information retrieval (DEPIR) enables sublinear per-query work (in the database size $N$) for both client and server, while requiring no client state. Despite its theoretical promise, single-server DEPIR exhibits a prohibitive concrete efficiency gap: for $N=2^{23}$, the state-of-the-art construction (Eurocrypt '25) requires a 733TB server state and over $2^{37}$ online RAM/Disk reads, rending it infeasible to execute. This paper advances single-server DEPIR towards practicality through a series of algorithmic innovations. Compared with the state-of-the-art, we achieve a 4 orders of magnitude reduction in server state and a 6 orders of magnitude reduction in query time. In particular, for the same level database ($N=2^{23}$), querying $5461$ elements in a single batch requires only 171GB of server state and $2^{24}$ online RAM/disk reads, yielding a 112s total query time and a 21ms amortized query time.

Pseudorandom correlation functions (PCFs) allow two parties to expand short correlated keys into an unbounded, locally evaluatable source of correlated randomness. In this paper, we give the first constructions of PCFs for correlated oblivious transfer (COT) and vector oblivious linear evaluation (VOLE) correlations over $\mathbb{Z}_M$ for an arbitrary modulus $M$, with reasonable concrete efficiency. Our construction comes with a lightweight, two-round distributed setup protocol, and relies solely on the decisional composite residuosity (DCR) assumption. As part of our security analysis, we introduce a new family of extended power DDH problems over subgroup indistinguishability groups, and give a novel master theorem showing that this is implied by standard DCR. This suffices to prove security of our PCF based on DCR, and also implies that prior constructions relying on related power-DDH style assumptions in composite groups can be based on DCR alone. We further extend our construction to obtain a PCF for oblivious linear evaluation (OLE) and general degree-two correlations over $\mathbb{F}_2$. As an application of our PCF for VOLE, we derive a designated-verifier exponent-verifiable random function (eVRF), where the publicly verifiable output is the VRF output in the exponent. As an independent contribution, we additionally give a publicly verifiable eVRF from an offline/online variant of homomorphic secret sharing. Both of these constructions have much shorter proof sizes than prior work.

Secure key leasing (SKL) is a quantum cryptographic primitive that enables the leasing of decryption keys to delegated users with the guarantee that, once revoked, the lessees irreversibly lose decryption capability. A key feature that makes SKL practically relevant is classical revocation: the ability to revoke keys at any time and from anywhere, without relying on a quantum channel. In this work, we revisit SKL schemes for public-key encryption (PKE) and identity-based encryption (IBE), and present a new approach for concrete efficiency under the standard Learning With Errors (LWE) assumption. First, we refine the security analysis of the Dual-Regev SKL-PKE scheme with classical revocation from [Ananth, Poremba, and Vaikuntanathan, TCC 2023; Ananth, Hu, and Huang, TCC 2024], establishing security under the polynomial hardness of LWE with polynomial modulus. Together with the resource efficiency of the Dual-Regev-based construction, our analysis shows that this approach yields the most quantum-efficient known SKL-PKE scheme. Second, we present a simple and efficient construction of selectively secure SKL-IBE with classical revocation from standard LWE. Our approach directly extends the Dual-Regev SKL-PKE within the IBE framework of [Agrawal, Boneh, and Boyen, Eurocrypt 2010], avoiding garbled circuits and obfuscation-based assumptions and achieving improved concrete efficiency over prior generic approaches.

Theta series are fundamental functions that record lattice-vector lengths and connect lattice geometry with Gaussian quantities such as Gaussian mass and the smoothing parameter. For ideal lattices under the canonical embedding, arithmetic coordinates are generally coupled, making fixed-coset theta-series evaluation and related Gaussian computations difficult in high dimensions. We show that an explicit, verifiable relative-basis condition yields an exact factorization of each fixed-coset theta series into lower-dimensional factors. For each fixed coset, when n = ℓ n₀, its n-dimensional theta-series computation is replaced by ℓ independent computations in dimension n₀. Equivalently, the canonical Gram matrix is block diagonal in the relative coordinates, and the factorization holds for every Gaussian parameter without approximation or a smoothing assumption. We verify the condition for several cyclotomic and non-cyclotomic extensions and derive explicit formulas for representative cyclotomic families. The same factorization gives lower-dimensional identities for Gaussian masses, independent Gaussian sampling within a fixed coset, and smoothing-parameter equations. It reduces the dimension of each coset calculation, while the outer sum over the residue classes in I_q remains unchanged. Our implementation achieves speedups of up to 335×, 215.45×, and 7.9× for fixed-coset theta-series evaluation, numerical smoothing-parameter evaluation, and sequential Gaussian sampling, respectively.

Private Information Retrieval (PIR) permits clients to query data entries from a public database hosted on untrusted servers while preserving client privacy. Traditional PIR models suffer from high computation and/or bandwidth overhead due to linear database processing for privacy. Recently, Online-Offline PIR (OO-PIR) has been proposed to improve PIR practicality by precomputing query-independent materials to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&P’24, CRYPTO’23) successfully reduce online processing cost to sublinear levels, they still impose substantial bandwidth and storage burdens on the client, especially when operating on large databases. In this paper, we propose Pirex, a new two-server OO-PIR with semi-honest security that offers minimal client inbound bandwidth and storage cost while retaining the sublinear processing efficiency. The Pirex design is simple with most operations are naturally low-cost and streamlined (e.g., XOR, PRF, modular arithmetic). We have fully implemented Pirex and evaluated its real-world performance using commodity hardware. Our results showed that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. With a 1 TB database, Pirex takes 55ms to retrieve a 4 KB entry, compared with 9-30s by state-of-the-art. For practical databases with billions of 4 KB entries, Pirex only takes 16 KB of inbound bandwidth, which is up to three orders of magnitude more efficient.

Standard hash-to-curve constructions first hash the message to a field element through a cryptographic hash-to-field step, then map this field element to an elliptic-curve point. Inside constraint systems, this inner cryptographic hash is often the dominant cost. Groth, Malvai, Miller and Zhang (Asiacrypt 2025) introduced \emph{constraint-friendly map-to-elliptic-curve-group relations} that bypass this step, achieving substantial reductions in circuit size. Their security proof works in the Elliptic Curve Generic Group Model (EC-GGM). We identify three gaps. First, the security bound in terms of the message space size $M$ and tweak bound $T$ is not explicitly analyzed, and the bounds stated for the concrete instantiations are loose. Second, the EC-GGM does not capture the algebraic structure of most deployed curves; we exhibit a concrete signature forgery using the parameters claimed secure. Third, the construction requires a congruence condition on the field that is not satisfied by all deployed curves; we extend it to any field, although witness generation remains practical only for fields of low 2-adicity. As a countermeasure we propose a $y$-increment variant that, on the $j=0$ curves used in practice, neutralizes the algebraic attack, removes the field restriction in practice, and preserves a comparable constraint count. We implement and benchmark both constructions in the open-source gnark (Go) library; the attack is additionally demonstrated via a self-contained SageMath simulation and confirmed at the circuit level against the authors' own Noir (Rust) implementation.

Computing cube roots in quadratic extensions of finite fields is a subroutine that arises in elliptic-curve point decompression, hash-to-curve and isogeny-based protocols. While the factorization $p^2-1=(p-1)(p+1)$ suggests a known subgroup decomposition, computing a cube root via separate operations in the two subgroups does not beat a direct $\mathbb{F}_{p^2}$ exponentiation in practice. We propose a carefully engineered algorithm that reduces the $\mathbb{F}_{p^2}$ cube root to a single $\mathbb{F}_p$ addition chain and a single Lucas sequence in the algebraic torus $\mathbb{T}_2(\mathbb{F}_p)$. The concrete formulas apply to primes $p \equiv 1 \pmod 3$ with $v_3(p-1) \leq 2$, which includes all six primes considered here. We prove correctness in all residuosity cases and implement the algorithm in Go. Benchmarks on six primes spanning pairing-based and isogeny-based cryptography show $1.6–2.3 \times$ speed-ups over direct (addition chain) exponentiations in $\mathbb{F}_{p^2}$.

Updatable Private Set Intersection (UPSI) extends conventional PSI protocols to dynamic scenarios, where input sets evolve over time. A straightforward approach is to rerun the entire PSI protocol after each update, incurring redundant computational and communication overhead. Although several UPSI schemes have been proposed to enable updates without full protocol re-execution, existing constructions remain impractical. Building on the high efficiency of unbalanced PSI designs, this work introduces Leopard---a general framework that leverages unbalanced PSI to realize UPSI without complete re-execution, while handling both insertions and deletions. Leopard is compatible with any unbalanced PSI protocol and achieves further performance gains by reusing internal data structures across updates. Specifically, we observe that certain data structures in unbalanced PSI can be incrementally updated instead of fully rebuilt. We provide an FHE-based instantiation of Leopard that demonstrates substantial performance improvements through such data structure reuse. Through comprehensive experiments, we evaluate Leopard's performance. Compared to Badrinarayanan et al. (ASIACRYPT 2024) and Alborch et al. (ACNS 2026), our instantiations reduce computational cost by up to 111.28× and at least 1.48×, and communication cost by up to 118.97× and up to 522.01×, respectively.

The Middle-Product Learning With Errors (MP-LWE) problem, introduced by Roşca, Sakzad, Steinfeld, and Stehlé (Crypto 2017), is a structured variant of LWE defined independently of any specific number field $K$. Its hardness has been based on the hardness of Ring-LWE (RLWE) over families of number fields. Two main reductions exist, one from Roşca, Sakzad, Steinfeld, and Stehlé (Crypto’17) and Njah Nchiwo and Pellet-Mary (PKC’26), and another one due to Peikert and Pepin (Journal of Cryptology’24). Both reductions cover different families of number fields, and none of the two supersedes the other. In this work, we propose a unified reduction from RLWE to MP-LWE parameterized by a pair of field elements $(y_a,y_s) \in K^2$, which recovers both prior reductions as concrete instantiations. Optimizing the choice of $(y_a,y_s)$, we obtain the first reduction from RLWE to MP-LWE that holds for all number fields $K = \mathbb{Q}[X]/f(X)$ where $f$ is a monic irreducible polynomial of a given degree and with polynomially bounded coefficients (and whose discriminant is coprime to the modulus $q$ of the RLWE and MP-LWE problems, a constraint that also appeared in previous works). This new reduction supersedes the two previously known reductions.

Anti-money laundering and counter-terrorist financing (AML/CFT) rules require payment service providers to assess incoming funds' provenance: for a target account, which earlier transfers contributed to it, how closely, and through which intermediaries? On transparent ledgers such as Bitcoin or Ethereum, this reduces to a graph traversal over the public transaction history. In private payment systems such as Zerocash or Tornado Cash Nova coins are burnt and created at each payment, while the sender, receiver, and amount are hidden. Provenance analysis is then impossible: the cryptography protects ordinary and illicit users alike. This creates an apparent deadlock, not merely a trade-off. We avoid this deadlock by giving a regulator a specific and bounded investigative capability rather than full visibility or none. Our construction extends Zerocash but applies naturally to most private systems with the same spend-and-create coin model (Tornado Cash, Railgun, Lelantus, etc.) The capability is backward provenance within a bounded neighbourhood of a transfer, together with the power to freeze funds derived from a designated illicit source, and to reconstruct a full clear-text provenance graph when a holder chooses to disclose. Everything outside that capability remains hidden from the supervisor and from every other party: receivers, amounts, the link from an output to its later spend, and the provenance of any coin that has not been disclosed.

Beam search bounds differential-trail exploration, but may still expand many intermediate differences. We test whether a learned short-horizon tail-cost residual can reduce this work while leaving classical selection in control. A regressor estimates a residual adjustment to an active-nibble heuristic. With four or two rounds remaining, the post-selection policy protects the best $25\%$ of the classical frontier, removes at most $30\%$ of accepted states, and abstains when fewer than five states can be pruned. It cannot restore candidates already rejected by classical selection. We develop the method on a state-grouped GIFT-64 corpus and evaluate it on $D=8$ and $D=12$ holdouts and a $D=16$ stress test. Target recovery and the best classical cost are preserved on all $48$ holdout cases and all $18$ stress cases. Aggregate node reductions are $6.832\%$, $0.099\%$, and $0.040\%$ at $D=8$, $D=12$, and $D=16$. An equal-budget ablation fixes the frontier, protected core, and pruning quota while changing only the removed-state ranking. Learned and classical ranking preserve all $48$ holdout cases, with aggregate reductions of $2.359\%$ and $2.411\%$. Their removal sets differ on $57$ of $85$ active frontiers, but the learned score does not establish a measurable advantage over the classical control. Random ranking produces larger raw reductions but loses quality. All comparisons use a bounded classical baseline; no globally optimal trails are claimed.

Cryptographic combiners take $n$ candidate schemes for some primitive $P$, and realize it securely provided that at least $k$ candidates are secure. Intuitively, we expect that if we plug $n$ independent instances of a $\delta$-weak candidate for $P$ into the combiner, assuming $\delta \ll (n-k)/n$, security should be amplified and the resulting candidate should exhibit a significantly smaller weakness. This intuition relies on the implicit “all-or-nothing” assumption that each candidate fails with probability $\delta$ and is otherwise perfectly secure, allowing us to bound the failure probability of the combiner using a simple binomial tail bound. However, this intuition often fails for standard security notions where, for example, a weak candidate may consistently leak partial information rather than exhibit a clean all-or-nothing failure. Recently, Applebaum, Bitansky and Geier (CRYPTO 2026) showed that indistinguishability combiners inherently act as security amplifiers. However, this general result incurs a multiplicative loss of roughly $2^{n-k}$ in the error parameter relative to the natural all-or-nothing bound. Moreover, the combiner-is-amplifier approach is fundamentally restricted to the regime $\delta < 0.5$. Consequently, both the resulting error rate and the amplification threshold $\delta_0$ are suboptimal. In this work, we overcome these limitations by establishing a new specialized framework of bias-resilient indistinguishability combiners. This formulation allows us to achieve the optimal all-or-nothing bound without the exponential penalty. We observe that bias-resilience provides a unifying abstraction for security amplification across different primitives, neatly capturing prior ad hoc results such as those for weak PRGs and weak NIZK. As our main application, we use this framework to establish a generalized XOR lemma over prime fields $\mathbb{F}_p$, showing that the sum modulo $p$ of independent weakly pseudorandom elements becomes computationally indistinguishable from uniform. This improves upon a recent work by Shimizu and Yasunaga (STOC 2026) by achieving a sample complexity that is independent of the field size. Finally, we explore the idealized notion of an all-or-nothing amplifier. We establish a tight characterization of the multiplicative penalty incurred when applying such an amplifier to candidate schemes that only guarantee standard weak indistinguishability error.

The latency of sleepy consensus protocols has been improved significantly, with recent designs achieving constant-round confirmation. However, existing protocols either rely on unrealistic additional assumptions about access to historical messages, where messages sent in round $t$ may depend on messages received in rounds $[t-k,t-1]$ for some $k>1$, or do not consider optimizing performance under optimistic conditions. In this work, we study history-independent sleepy atomic broadcast protocols while simultaneously considering optimistic conditions, where messages sent in round $t$ depend only on messages received in round $t-1$. We first design a sleepy atomic broadcast protocol that achieves a confirmation latency of $2\Delta$ ($\Delta$ is the upper bound on network delay) and an optimal latency of $\Delta$ under up to $1/5$ corruption. Second, we present a super-optimistic atomic broadcast protocol, achieving a best-case latency of $2\Delta$ under fault-free executions. Building on this insight, we propose an optimistic sleepy atomic broadcast protocol that relaxes the super-optimistic condition to tolerate sub-optimal faults. As a building block, we introduce an optimistic graded agreement protocol, $OptimisticGA$, which enables a dynamic optimistic quorum with four decision grades. Built on $OptimisticGA$, our optimistic atomic broadcast protocol achieves a good-case latency of $2\Delta$ when the leader is honest, while tolerating up to $1/6$ corruptions rather than requiring a fault-free setting. When corruption is more than $1/6$, it seamlessly adapts to $1/3$ resilience with a good-case latency of $3\Delta$. All protocols require no historical messages and tolerate an adversary that grows proportionally with honest nodes, with a minimal delay of $\Delta$.

Post-quantum cryptography has become pivotal for ensuring communication security in the quantum era. NTRU-based signature schemes have gained attention due to their computational efficiency and compact public keys and signatures, which reduce communication overheads. However, the algebraic structure of NTRU lattices introduces vulnerabilities in physical attack scenarios, where partial secret key leakage can severely undermine system security. In this paper, we propose the Dimension-and-Sample Reduced NTRU Attack (DSRNA). The core principle of DSRNA is to apply a dimension-reduction strategy that transforms the NTRU instance into a lower-dimensional NTRU instance with fewer samples, which is efficiently solvable via lattice basis reduction. Furthermore, we design a unified hint-embedding technique that jointly exploits side information from both secret keys $f$ and $g$, thereby improving both attack efficiency and success rates. We evaluate the residual security of Falcon and its variants Mitaka and Hawk, under perfect, modular and approximate leakage models. Experimental results demonstrate security degradation. Compared to the method of May et al. at Asiacrypt 2023, DSRNA achieves speedups of $5.8\times$ for Falcon-512 with 400 leaked coefficients and over $29.4\times$ for Falcon-1024 with 905 coefficients. This study reveals the potential vulnerability of NTRU-based signature schemes to partial secret key leakage.

Enhanced Gabidulin Matrix Codes (EGMC), introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asiacrypt 2024, were designed to hide the algebraic structure of Gabidulin matrix codes while enabling very compact McEliece- and Niederreiter-type encryption schemes, with ciphertexts as small as 65 bytes at the claimed 128-bit security level. Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code. We show that this enhanced construction leaves enough structure for an equivalent code of the secret key to be recovered. Unlike previous cryptanalysis, our attack combines combinatorial and algebraic techniques to recover a Gabidulin-equivalent compressed code. This code can then be extended to a full-length equivalent secret key in polynomial time. As a result, the attack provides both a distinguisher and a key-recovery attack against the EGMC encryption schemes. The attack breaks all 16 proposed EGMC parameter sets by large margins. For example, for the claimed 128-bit parameter set (2,17,37,4,0), it reduces the security level from 186 bits to 35 bits and in our implementation, the equivalent secret key of this parameter set is recovered in less than 10 minutes.

While an abundance of SCA methodologies have arisen over the years with impressive theoretical backgrounds, they fail to take into account some important real-world aspects in the analysis. Most of them fail on three key points. First, most assume IID or normally distributed data points in their framework without verifying that the experimental setup indeed meets that requirement. Second, most methods rely on visual aspects or failed statistical tests to define the success or failure of the tests without quantifying the precision of their measurement with formal boundaries. Third, in most cases, the test harness is not completely oblivious to the secret data, remaining completely free of data-dependent branching, conditional formatting, or conditional triggering, which can leak environmental noise and contaminate the data points. We are proposing a new SCA methodology, which we named BLAQ, to bridge this gap between the theoretical mathematical models and the real-world imperfect testing environment.

In 2022, the National Institute of Standards and Technology (NIST) initiated a second call for post-quantum digital signature proposals to broaden algorithmic diversity beyond the already standardized schemes based on structured lattices and hashes. While five out of the 14 second-round entries were built on the MPC-in-the-Head paradigm, only two advanced into the recently announced third round. Despite their theoretical appeal, available results on their implementation costs imply a reduced applicability to resource-constrained embedded devices. In this work we analyze one of the remaining candidates, the revised second version of the Syndrome Decoding in the Head (SDitH) signature scheme based on the VOLE-in-the-Head framework, and showcase that these issues are not inherent to the family of algorithms. We propose an area-efficient hardware design including highly optimized variants of both Batch Line Commitment (BLC) and Polynomial Interactive Oracle Proof (PIOP) routines. As a result, we reduce memory requirements by a factor of 22 to 52 compared to the approach of the reference implementation and by a factor of 40 to 88 compared to the previous hardware implementation of SDitH-v1, while still achieving competitive runtimes. To the best of our knowledge, this yields the most compact hardware implementation of any MPCitH or code-based signature primitive, with our algorithmic improvements directly transferable to software designs. During our analysis, we additionally determined nine significant discrepancies between specification and reference implementation of SDitH-v2, with a subset breaking test vector compatibility. Beyond addressing these issues, we suggest specification changes to further reduce resource usage on embedded targets without compromising security assumptions.

Let $\mathrm{MQ}_0(n)$ and $\mathrm{MQ}_1(n)$ be the sets of square systems of $n$ quadratic equations in $n$ variables over $\mathbb{F}_2$ having, respectively, no solution and exactly one solution, and write $\alpha_0=|\mathrm{MQ}_0(n)|$, $\alpha_1=|\mathrm{MQ}_1(n)|$. It is known that $\alpha_0<\alpha_1$, so injections $\mathrm{MQ}_0(n)\hookrightarrow\mathrm{MQ}_1(n)$ exist; the proof is a counting argument and produces no map. We exhibit a partial injection $\tau$, in the following sense. The map $\tau$ adds to a system a single correction supported on an affine flat of codimension two through a point read off by a three-point decoder; it is computable in $\Theta(n^3)$ bit operations from the dense coefficient representation, with no precomputation and no advice. We prove that there is a subset $\mathcal{D}\subseteq\mathrm{MQ}_0(n)$ with $|\mathcal{D}|/|\mathrm{MQ}_0(n)|>0.745$, uniformly in $n\ge3$, on which $\tau$ is injective into $\mathrm{MQ}_1(n)$. We then show that inverting $\tau$ is \emph{equivalent} to locating a zero of the image system --- the solvable case of the multivariate quadratic problem, and its one-solution case on the uniquely solvable part of the image --- and that $\tau$ is randomly self-reducible on each orbit of its symmetry group. Under the standard assumption that solvable $\mathrm{MQ}$ is hard on average --- the planted-$\mathrm{MQ}$ assumption of $\mathrm{MQ}$-based identification and signature schemes --- $\tau$ is therefore a one-way function, injective on $\mathcal{D}$, explicit and randomly self-reducible on each orbit, between two sets which are, as languages, complexity-theoretically far apart. We also show that the associated flat-collision problem is NP-complete.

We present FaFROST+, the first two-round Schnorr threshold signature scheme achieving full adaptive security under the Algebraic One-More Discrete Logarithm (AOMDL) assumption with identifiable aborts. Building on the FROST framework, FaFROST+ preserves its communication efficiency while dispensing with the LDVR assumption introduced at CRYPTO'25. Our result demonstrates that round-optimal adaptive security, practical efficiency, and identifiable aborts are simultaneously achievable under the well-studied AOMDL assumption.

Fresh payloads need not hide persistent watermark geometry. For a Gaussian latent model with refreshed fair angular bits and isotropic covariance, we derive the exact fourth-order signature, the boundary of distributional hiding, and an attainable obstruction imposed by a uniform decoding margin. A fixed-probe learner has sufficient observation count O(p3 log p/c2) at fixed rank, accuracy and confidence, where c is the angular signal strength. Our central statistical result is a sharp, dimension-independent centered fourth-tensor covariance bound. It yields public finite-sample lower bounds on a frozen candidate’s carrier overlap, using independent validation directions, a carrier-dimension bound and scale information, without the secret key or payload. Exact partial-index spectra expose the tradeoff between geometric compression and validation variance. On eight fixed candidates, known- and unknown-scale lower bounds average 0.173 and 0.057, while oracle overlap averages 0.600. Population identities characterize feedback signal; a paired, budgeted MIPP comparison evaluates empirical training with independent Gaussian threshold calibration and a shared public spectral initialization control. All rank failures, zero-threshold sensitivities and negative results are reported. The guarantees concern latent subspaces under the stated iid model and exact arithmetic. They do not establish convergence of same-data adaptive training, ordered bit recovery or a neural watermark attack.

The server-aided Secure Multi-Party Computation (MPC) model with dynamic participation, where servers may join or leave during the computation is particularly well-suited for practical, long-running applications. Unfortunately, existing protocols supporting dynamic participation either incur communication costs that scale linearly with the circuit size or rely on the heavy hammer of Fully Homomorphic Encryption (FHE). This contrasts with “classic” MPC protocols, where sublinear communication can be achieved without FHE. Focusing on the Layered MPC framework (introduced by David, Ishai, Konring, Kushilevitz, and Narayanan, CRYPTO 2023), we show that this overhead is not inherent. We construct sublinear-communication Layered MPC protocols while maintaining a minimal number of online servers — only two or three per layer. Our constructions rely on a layered-friendly adaptation of Homomorphic Secret Sharing (HSS), which we formalize as HSS with Layered Resharing.

Distributed randomness beacons enable mutually distrustful parties to jointly generate public randomness. Several existing beacons built from secret sharing use costly pairings or group operations to verify shares. Their underlying discrete-logarithm assumptions are also vulnerable to quantum attacks. Moreover, running a separate Byzantine fault-tolerant (BFT) consensus instance for each output incurs repeated computation and communication costs, even when secrets are shared in batches. We present Silk, a computation-efficient, post-quantum-friendly and deterministic randomness beacon under partial synchrony. Silk's sharing protocol, Mulberry, realizes batched asynchronous verifiable secret sharing with partial output (bAVSS-PO), using hash-based share verification to reduce computation cost. Silk further amortizes BFT consensus across a batch of outputs, requiring only one BFT instance per batch. We establish Mulberry's bAVSS-PO properties and Silk's beacon properties under static corruption and the stated security assumptions. We implement Silk and Mulberry in Rust and evaluate their computation and communication costs. In WAN experiments with 121 replicas across eight AWS regions, Silk achieves a throughput of 5.414 outputs/s, 1.53× that of Rondo [NDSS'25] and 4.18× that of Spurt [IEEE S&P'22].

We study the local leakage resilience of $t$-out-of-$n$ threshold secret sharing schemes. We present a remarkably simple, perfectly correct attack that fully breaks any scheme with linear reconstruction over a finite field using $\lg t + \mathcal{O}(1)$ bits of leakage per share. In particular, this yields concretely efficient attacks on additive secret sharing and on Shamir’s scheme for arbitrarily large thresholds over arbitrarily large finite fields. Our key technical idea is an approximately linear scale-and-round function that maps shares from an arbitrarily large field into a much smaller ring, while preserving the distance of well-separated secrets. Our results provides two surprising insights: Bigger finite fields do not necessarily improve leakage resilience and increasing the reconstruction threshold in Shamir’s scheme does not help too much either.

Cryptanalytic model extraction treats the parameters of a neural network as hidden secrets and attempts to recover them from black-box oracle access. Existing attacks have shown that such recovery is possible for several neural-network architectures, but practical evaluations typically assume high-precision target-model evaluation, often in float64. This assumption creates a mismatch with deployed machine-learning systems, where models are commonly evaluated in float32 or lower-precision formats. We study cryptanalytic signature recovery under finite-precision target-model evaluation. We decompose the recovery pipeline into numerical subproblems, including critical-point localization, finite-difference estimation and perturbed linear-system solving, and analyze how errors are introduced, propagated, and amplified across these stages. We further relate the resulting perturbation amplification to intrinsic properties of the target network, including the geometry of local linear regions and local parameter-to-gradient sensitivity. In particular, we derive approximate instability boundaries for key precision-sensitive stages of the recovery pipeline. When the target model is evaluated in float32, oracle-induced perturbations cannot be removed by higher-precision downstream computation, leading to a substantially higher local error floor than in the float64 setting. Experimental results suggest that recovery becomes less stable as the network size increases. We also discuss how the finite-precision perspective extends to hard-label recovery and piecewise-affine network components, while smooth non-piecewise-linear activations require additional curvature-aware error modeling.

Private inference can protect user queries and model weights without trusted hardware or statistical privacy relaxations, but transformers combine large secret matrix multiplications, costly nonlinearities, and sequential autoregressive execution. Prior surveys organize the literature mainly by cryptographic backend, deployment setting, or supported operation, obscuring when techniques remain applicable or composable across execution phases, model adaptations, or security boundaries. We systematize 58 cryptographic private transformer frameworks (2022--2026) across three interacting levels: systems (execution and optimization), models (cryptography--machine learning co-design and adaptation), and cryptography (secure realization of transformer operations). This analysis reveals two recurring cross-backend applicability constraints: optimizations do not transfer unchanged across execution phases when they require values not yet available, while data-dependent pruning, cache management, routing, and sparsity require private execution structure to be hidden, constrained, predicted, or disclosed. Against an output-only reference baseline, we identify four classes of security concerns affecting 5 frameworks and synthesize composition boundaries in maliciously secure designs. We find that 16 frameworks rely on empirically calibrated or distribution-specific mechanisms and 21 require additional training, limiting generalization and cross-framework comparability. We distill these findings into 12 open problems and 16 outlooks spanning protocol efficiency, cross-level co-design, dynamic execution, security, evaluation, and scalability.

In this paper, we systematically study the (im)possibilities of proactive secret sharing (PSS) in fully asynchronous authenticated networks. To reflect the subtleties arising from the absence of a global clock, we first formalize a hierarchy of natural mobile adversary models for asynchronous PSS (APSS), capturing different adversarial capabilities over corrupted parties and distinct ways of accounting for mobile corruption in asynchrony. Under these models, we then (i) establish new impossibility results by exhibiting generic attacks on APSS, thereby deriving the corresponding resilience upper bounds, and (ii) demonstrate the tightness of these bounds via explicit APSS protocols achieving optimal resilience in each model.

Adaptor signatures enable scriptless protocols on blockchains such as Bitcoin by allowing a buyer to lock a coin based on an NP statement and release payment to any party that reveals the corresponding witness. They underlie a broad class of layer-2 protocols, including payment channels, cross-chain swaps, and coin-mixing services, which today secure billions of dollars in locked value. Fairness for existing adaptor-signature constructions, however, is inherently two-party, so does not apply to deployments in which the buyer or witness holder is operated by a committee. In this work, we formalize and solve the fair exchange problem in that setting. We consider a buyer group holding shares of a signing key controlling a coin, and a seller group holding shares of a secret witness. The goal is to guarantee fairness both between groups (ensuring that each group obtains its asset if and only if the other does), as well as within groups (ensuring that all honest buyers learn the witness and all honest sellers receive payment), even in the presence of malicious insiders and/or partial information leakage. We present efficient protocols achieving these guarantees under standard cryptographic assumptions on scriptless blockchains with timelocks. Our construction introduces two new primitives of independent interest, threshold adaptor signatures and certified witness encryption, which we define, analyze, and instantiate efficiently.

Masking is a widely used countermeasure against side-channel attacks, where sensitive variables are split into randomized shares in order to prevent information leakage from intermediate computations. Its security is commonly analyzed in the random probing model, in which each internal variable leaks independently with some probability $p$. Constructing large masked circuits that achieve random probing security (RPS) is challenging, and a common approach is to rely on composability frameworks ensuring that suitable local gadget-level properties imply circuit-level guarantees. Recent works have introduced compositional frameworks based on leakage diagrams to derive security guarantees in the random probing model. While elegant and scalable, these approaches rely on conservative analyses and security proofs tailored to specific gadget constructions. In this work, we revisit and refine a leakage-diagram approach published in TCHES 2023. We formalize and generalize the proof to show that the probability of an orbit in the leakage diagram upper bounds the adversary's RPS advantage. Our analysis identifies the local gadget-level conditions needed for this composition result, refines the analysis of edge inclusion probabilities in leakage diagrams for the underlying multiplication gadgets, leading to tighter final security bounds, and improves the combinatorial analysis of orbits through a detailed study of small cases and new structural properties for larger ones. We evaluate the resulting constructions on AES. Our results significantly improve the concrete security guarantees compared to previous leakage diagram analyses, while also improving the randomness complexity compared to existing composable approaches.

We give a quantum algorithm for the elliptic curve discrete logarithm problem over an \(n\)-bit prime field using \(\frac{5}{2}n+o(n)\) logical qubits and \(\widetilde O(n^2)\) Toffoli gates. Luo et al.'s exact space-efficient affine construction uses \(3n+O(\log n)\) qubits with \(O(n^3/\log n)\) Toffoli gates; ours lowers the leading qubit term from \(3n\) to \(\frac{5}{2}n\) and the Toffoli count to near-quadratic. We construct an exact in-place modular inverter with \(\frac{3}{2}n+o(n)\) logical qubits and \(\widetilde O(n)\) Toffoli gates. For consecutive Euclidean remainders \(R>r\) and coefficient magnitudes \(0\le T<t\), the invariant \(Rt+rT=p\) allows us to store only three of \(R,r,T,t\) in the persistent Euclidean state and reconstruct the fourth on demand. Temporary Euclidean data are recovered from the updated state and erased after each update. The arithmetic queries used in these steps are implemented in sublinear workspace using measurement-based uncomputation. We then use Hua's identity to reduce the variable-square multiplications needed for affine point addition to inversions, yielding exact controlled point addition within \(\frac{5}{2}n+o(n)\) logical qubits and \(\widetilde O(n)\) Toffoli gates.

Standard differential-linear (SDL) cryptanalysis has matured rapidly, now backed by the SDL connectivity table (SDLCT) framework, multi-round middle-part extensions, and automated CP-based search models. The rotational differential-linear (RDL) variant lacks even an SDLCT counterpart, and the analogous combination of internal differentials with linear approximations, which we call internal differential-linear (IDL) cryptanalysis, has never been formulated. We unify SDL, RDL, and IDL in a single Walsh-transform framework on the difference transition function (DTF). Existing SDL machinery, including recent multi-round middle-part search models, transfers to RDL and IDL, yielding efficient correlation computation and distinguisher search. For ARX primitives, we derive a $2\times 2$ matrix-product formula for the SDL and RDL correlations of a single modular addition. The formula exposes a rank-$1$ structure on the input-difference matrix that decouples the running product into independent factors, making a CP approximation with only linear inequalities and table lookups practical. This partially resolves the open problem of Niu et al. (CRYPTO 2022). We apply the framework to \xoodoo-$p$, \ascon-$p$, \alzette, \siphash, and \specksixtyfour. For \xoodoo-$p$, we obtain a 6-round RDL distinguisher and the first IDL distinguisher in the literature (both at 6 rounds). For \ascon-$p$, the first RDL distinguisher (6 rounds). For \alzette, an 8-round RDL distinguisher, doubling the previous 4-round best. For \siphash, the longest known distinguisher (5 rounds). For \specksixtyfour, the longest known SDL distinguisher (14 rounds).

Lattice extraction often produces openings normalized by challenge differences, whereas an inconsistency must ultimately yield a short integral SIS relation. Clearing each extracted branch before comparison removes every denominator obstruction carried by that branch, including factors irrelevant to the mismatch that is eventually tested. We formalize direct integral comparison for generic polynomial block systems. If block \(a\) has width \(r_a\) and the two extraction centers differ on \(J\), the minimum worst-case coefficient degree is \(\max\{\max_a r_a,\sum_{a\in J} r_a\}\). Within a branch-separated polynomial integralize-then-compare architecture, it is \(2\sum_a r_a\). The coordinate case gives \(\max\{1,h\}\) and \(2L\), where \(h=|J|\). Exact conditional resampling obtains the required partially synchronized successful executions without a reciprocal-success loss. The coordinate schedule uses at most \(2L+1\) additional retry invocations in unconditional expectation. Two cases illustrate the bounds. For Cyclo-style coordinate folding, one unsynchronized coordinate has the same certified radius as same-root synchronization. For two independently extracted Esgin-style Vandermonde stars, direct comparison has degree \(\binom{k+1}{2}\) in the anchor-universal polynomial-linear model. The degree is \(k^2\) within the stated branch-separated integralize-then-compare architecture.

Sumcheck-based transparent SNARKs over small prime fields encounter a basic soundness bottleneck. When instantiated over $\mathbb{F}_p$, the round-by-round soundness error is $O(d/p)$, where $d$ is the degree parameter in the sumcheck instance. This is non-negligible for small $p$. A common remedy is to work over an extension field, which departs from native $\mathbb{F}_p$ arithmetic and requires implementing general $\mathbb{F}_{p^k}$ arithmetic, in particular multiplication. A natural alternative is to amplify soundness by parallel repetition. However, naive $k$-parallel repetition does not achieve a proportional $k$-fold increase in round-by-round soundness for multi-round sumcheck. In this work, we propose the \emph{packed sumcheck protocol}, which amplifies round-by-round soundness over $\mathbb{F}_p$ by combining repetition with folding, while avoiding extension field multiplication. The core idea is to couple $k$ independent instances within each round using random matrix challenges from the matrix ring $\mathbb{F}_p^{k \times k}$, so that every folding step mixes all $k$ coordinates. For degree-$d$ claims, we obtain round-by-round soundness error $\bigl(((2k-1)d)/p\bigr)^k$. The prover uses $O((kd^2+k^2d)N)$ base field multiplications and the verifier uses $O(k^2 d\mu)$ base field operations, with communication $O(k d\mu)$ base field elements, where $N=2^\mu$ is the size of the $\mu$-dimensional Boolean hypercube. To compile the packed sumcheck protocol into SNARKs, we introduce \emph{matrix-weighted multilinear extension (MW-MLE) commitments}, capturing the matrix-weighted linear forms induced by packed sumcheck, and instantiate them by adapting Brakedown (CRYPTO~2023) and Basefold (CRYPTO~2024). The resulting components are integrated into the HyperPlonk (EUROCRYPT~2023) framework by replacing its sumcheck and polynomial commitment modules with packed variants, obtaining transparent SNARK instantiations without extension field multiplication in the Random Oracle Model. We further apply our packed techniques to construct a TFHE-friendly SNARK; we evaluate its prover performance for a single bootstrapping, obtaining a prover time of 2.2 seconds.

A multi-party distributed point function (DPF) compresses a point function instance $f_{\alpha,\beta}$, i.e., $f$ evaluates to $\beta$ at $\alpha$ and to $0$ otherwise, into short keys that are distributed to $N$ parties. Each key allows a party to locally derive an additive share of the point function evaluation. DPFs have become a widespread building block for cryptographic protocols and sometimes rely on a distributed setup. In this work, we present an $N$-party, full-threshold DPF for full-domain evaluation making black-box use of oblivious tensor evaluation. Let $L$ denote the domain size of the point function and $\lambda$ the security parameter. Instantiated with the non-interactive oblivious tensor evaluation primitive (NIOTE) by Abram et al. (STOC '25) based on learning with errors (LWE), we obtain $N$-party DPFs with (i) key-size $\mathcal{O}(N \cdot \mathsf{poly}(\lambda) \cdot \log^2 L)$ with a $\log L$-round distributed setup protocol, or (ii) similar key-size with almost $(\log \log L)$-rounds (asymptotically $\Theta(\log L)$ but for relevant values of $L$ in practice equal to $\log \log L$), or (iii) key-size $\mathcal{O}(N \cdot \mathsf{poly}(\lambda) \cdot \log L \cdot \sqrt{L})$ with $(\log \log L)$-round distributed setup (also asymptotically). Our construction improves over most of the state of the art either in terms of key-size or in the setup round complexity.

Pseudorandom generators (PRGs) are a foundational primitive in classical cryptography, underpinning a wide range of constructions. In the quantum setting, pseudorandom quantum states (PRSs) were proposed as a potentially weaker assumption that might serve as a substitute for PRGs in cryptographic applications. Two primary size regimes of PRSs have been studied: logarithmic-size and linear-size. Interestingly, logarithmic PRSs have led to powerful cryptographic applications, such as digital signatures and quantum public-key encryption with tamper-resilient keys, that have not been realized from their linear counterparts. However, PRGs have only been black-box separated from linear PRSs, leaving open the fundamental question of whether PRGs are also separated from logarithmic PRSs. In this work, we resolve this open problem. We establish a quantum black-box separation between (quantum-evaluable) PRGs and PRSs of either size regime. Specifically, we construct a unitary quantum oracle with inverse access relative to which no black-box construction of PRG from (logarithmic or linear) PRS exists. This does not directly separate PRG from some of the applications of SPRS since these applications involve, as a first step, a non-black-box construction of a notion termed bot-PRGs. To address this, we present another unitary separation showing that PRG are also separated from bot-PRGs. Thus, we obtain separation from digital signatures and quantum public-key encryption.

Verifiable oblivious pseudorandom functions (VOPRFs) enable a client to evaluate a pseudorandom function on a private input under a server-held key while verifying that the server evaluated the function honestly using its committed key. Existing practical VOPRFs rely mainly on assumptions that are vulnerable to quantum attacks. Prior lattice-based constructions achieving both round optimality and malicious security have remained theoretical proposals without concrete implementations, largely because proving the correct evaluation of the underlying lattice-based PRF in zero-knowledge is prohibitively expensive. We present Beasley, the first concrete prototype implementation of a round-optimal, maliciously secure, lattice-based VOPRF from standard lattice assumptions. Beasley builds upon the framework of Albrecht et al. (PKC 2021) and LeOPaRd (CRYPTO 2026), introducing two core optimizations: First, we generalize the Boneh-Lewi-Montgomery-Raghunathan (BLMR13) pseudorandom function where each step processes w input bits simultaneously; instantiated with w=4 in our implementation, this reduces evaluation depth and running time by a factor of 4 without impact on security; Second, we replace LaBRADOR-style proofs with a ring-switching sumcheck protocol and develop an efficient arithmetization of the OPRF computation. This design allows us to use a relatively large ring dimension of 512, simultaneously delivering fast ring arithmetic and compact keys with efficient exact range proofs without security-degrading slack. Benchmarked on a commodity consumer laptop using a single core with AVX2, Beasley generates the full client request and NIZK proof in 520 ms, with a server verification time of 15.3 ms, a peak RAM footprint of 113.7 MB, and a client communication size of 109 KB. The NIZK proof itself is 75.4 KB. Our results demonstrate that maliciously secure, lattice-based VOPRFs can achieve practical performance for real-world applications.

There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs) and quantum-computable PRGs. Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relations among quantum pseudorandomness have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel differential geometric \emph{barrier theorem} for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible ``gap'' between two large trace-separated sets. Our separation is based on an oracle that outputs Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states. Variations of this oracle can be used to study other relationships between quantum cryptographic primitives, and we use it to achieve partial separations, that highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting. More precisely, we obtain separations showing limitations of: (i) deriving ancilla-free pseudorandom unitaries (PRUs) from PRFSGs, and (ii) a natural way of constructing super-log-length output PRSGs from log-length output PRFSGs. The latter partly complements the known hardness of shrinking the PRSG output lengths.

A central line of inquiry in the study of indistinguishability obfuscation (IO) is to minimize the size of the obfuscation. Today we know how to obfuscate programs represented as Turing machines, where the size of the obfuscation grows only with the input size and not with the machine's running time. Jain and Jin [FOCS 2022] showed how to remove the dependency on the input size for functionally equivalent programs where equivalence can be proven in Cook's theory PV. In this work we investigate the limits of the pursuit of succinct obfuscation. We consider the task of obfuscating a program with a large description, most of which can be made public while some portion of the description is secret. We put forth a new notion of fully succinct IO where the size of the obfuscated program only grows with the size of the program's secret part and not with the public part or with the input size. Starting with input-succinct IO for PV-equivalent machines, which is known from super-polynomially hard IO for circuits and LWE, we construct fully succinct IO for the same class of programs. We refer to such an obfuscation as fully succinct pv-IO. Next, we show how to bootstrap our fully succinct pv-IO to achieve full IO security. Our bootstrapping theorems are based on succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs. We also require that the correctness of these primitives can be proven in theory PV. We show that these assumptions are sufficient and necessary. We demonstrate several applications of fully succinct IO and pv-IO: (i) We give the first IO construction where the size of the obfuscated program is less than twice the size of the original program for a large class of useful programs. (ii) We show how to avoid padding the program before obfuscating it—a step often necessitated by security analysis—by replacing the padding with a public random string. (iii) We give the first construction of succinct computational secret sharing for access structures represented by polynomial-size monotone circuits where the share size does not grow with the size of the access structure.

We present new constructions of (n - t + 1)-out-of-n threshold and slice secret sharing schemes for short secrets with imperfect secrecy for constant t and growing n. Our main results are 1. an ε-differentially secret, (n - t + 1)-out-of-n bit secret sharing scheme with share alphabet size Õ_t(1/ε^2). In contrast, perfect secrecy requires share alphabet size n - t + 1 (Bogdanov, Guo, and Komargodski, ToC 2020). For t > 3, the security of our scheme relies on a conjecture about factorizations of univariate polynomials in finite fields. 2. an ε-statistically secret bit secret sharing scheme for every (n-2)-out-of-n slice with share size O(log n log 1/ε). Previous constructions with comparable parameters achieved only computational security (Beimel, Farràs, Lasri, and Nir, TCC 2024). Variants of our first construction produce plain and anonymous (n-1)-out-of-n weak bit secret sharing schemes with optimal share size. We discuss the relevance of these schemes to secret sharing duality.

Fast randomized linear codes used in pseudorandom correlation generators and code-based proof systems require quantitative guarantees on the probability of sampling a code with insufficient distance. For chosen-block Block--Accumulate--Accumulate (BAA) codes, prior work provides finite-length upper bounds, sparse failure mechanisms, and permutation obstructions that persist under every nonzero coordinate scaling. We determine the global minimum-distance lower tail across field sizes. For a fixed-length constituent of minimum distance $d\ge2$, sufficiently small fixed $\delta>0$, and $Q=q-1$, we prove, uniformly over finite fields and constituent coefficients, \[ \PP[d_{\min}\le\floor{\delta N}] =\Theta\!\left(N^{1-d} +N^{1-\ceil{d/2}}Q^{-\floor{d/2}}\right). \] A support-dependent weighted-gap estimate controls every active-block count and every cancellation layer. It identifies linear field growth as the exact order needed for the $N^{1-d}$ law. Certified extensions reach distance $0.30$ for $[16,8,9]_q$ MDS blocks and $0.60$ for $[16,4,13]_q$ MDS blocks over all $q\ge2^{20}$; binary instances reach their stated useful thresholds. For the two MDS families, when $Q/N\to\infty$, we further prove that the known marked one-block coefficient is the leading constant of the actual failure probability. Grouping full-block gap events and bounding their dependence gives near-exact two-sided finite certificates at the published large-field benchmarks. These show that the existing numerical guarantees are essentially optimal for the unchanged ensemble. \keywords{Random linear codes \and BAA codes \and Minimum distance \and Pseudorandom correlation generators \and Sampling failure}

Password-Authenticated Key Exchange (PAKE) allows two parties to establish a common high-entropy secret from a possibly low-entropy pre-shared secret such as a password. In this paper, we revisit the question of constructing PAKE protocols with subversion resilience in the framework of universal composability (UC), where the latter roughly means that UC security still holds even if one of the two parties is malicious and the honest party's code has been subverted (in an undetectable manner). The latter goal was recently achieved by Chakraborty, Magliocco, Magri and Venturi (ASIACRYPT 2024), based on sanitation of oblivious transfer protocols and dual-mode cryptosystems via cryptographic reverse firewalls (Mironov and Stephens-Davidowitz, EUROCRYPT 2015). Our contributions are as follows: - We introduce so-called malleable trapdoor smooth projective hash functions (M-TSPHF), as an enhancement of trapdoor smooth projective hash functions (Benhamouda et al., CRYPTO 2013). Our extension incorporates new properties including key malleability and element rerandomizability. - We give a generic construction of subversion-resilient UC PAKE based on M-TSPHF and other standard cryptographic primitives. As we demonstrate, our PAKE protocol can be instantiated efficiently yielding an improved round and communication complexity with respect to the previous protocol of Chakraborty et al. In particular, our PAKE protocol achieves round optimality, as it concludes in a single round.

Bitcoin Improvement Proposal 327 specifies a variant of the MuSig2 multi-signature protocol that is becoming widely adopted in Bitcoin applications. This protocol enables multiple participants to collaboratively compute (BIP 340) Schnorr signatures for a single aggregate public key efficiently, while preventing external parties from distinguishing whether multiple signers were involved. It has been widely proposed that it should be secure to allow MuSig2 participant keys to themselves be "nested" MuSig2-aggregated keys. No security argument has previously been presented for this practice, though various applications have been proposed that assume the security of such an operation. In this work, we propose NestedMuSig2, a recursive variant of MuSig2 that enables a tree of nested cosigners to privately generate aggregate Schnorr signatures while maintaining all of the efficiency and security benefits of MuSig2, including non-interactive public key aggregation. Nested signers in this scheme cannot distinguish between cosigners that are using further nesting and those that are not. In particular, this means that NestedMuSig2 is compatible with all existing protocols that use MuSig2. We reduce the security of NestedMuSig2 to the AOMDL assumption in the random oracle model. Similarly, we reduce the security of a more efficient and compact variant to the AOMDL assumption in the random oracle model used in conjunction with the algebraic group model.

We construct homomorphic secret sharing (HSS) and pseudorandom correlation functions (PCFs) in a general group-theoretic framework, with security based on the subgroup indistinguishability (SgI) assumption introduced by Brakerski and Goldwasser (Crypto 2010). Under certain instantiations of this framework, SgI corresponds to decisional composite residuosity (DCR), but other instantiations are possible as well. Hence, our work expands the set of assumptions that imply HSS and PCFs. Our constructions crucially rely on the existence of an efficient distributed discrete logarithm (DDLog) algorithm for the utilized group. We construct a new DDLog algorithm that works in general groups as long as the order $t$ of the base is smooth. In particular, our DDLog supports the prime-power case, which was previously an open problem. Moreover, we apply a divide-and-conquer optimization that significantly improves the performance from $\mathcal O(\log^2 t / \log \log t)$ group operations (Abram et al., Crypto 2022) to $\mathcal O(\log t \log \log t)$. Toward constructing PCFs, we introduce a new notion of public-coin subgroup indistinguishability (PC-SgI). We show that, in certain instantiations, SgI implies PC-SgI, so no new assumption is required. We then obtain PCFs for VOLE, OT, OLE, and degree-two correlations, all generically under PC-SgI. Our PCFs for OLE and degree-two correlations additionally rely on the sparse LPN assumption. Along the way, we discover and patch two security issues in prior work: first, an attack on decisional Diffie–Hellman (DDH) in the Joye–Libert instantiation by Abram et al. (Crypto 2022), and second, a flaw in the security proofs of optimized variants of the IKNP OT extension protocol and of many silent OT extension protocols.

We characterize the arithmetic complexity of reproducing a prescribed error-compensated pruning procedure: select weights for removal, set them to zero, and propagate each removal error to later columns. With its interaction factor supplied, an $m\times d$ layer with $m=\Theta(d^\alpha)$ admits a recursive execution in $O_\varepsilon(d^{\omega(\alpha,1,1)+\varepsilon}+C)$ operations, where $C$ is the decision cost. The execution preserves every corrected group snapshot and every subsequent decision, including unequal groups and stateful column policies. For every fixed row-wise $r$-of-$q$ rule, the exponent is exactly $\omega(\alpha,1,1)$; one row already has quadratic complexity. In square dimensions, matching lower bounds also hold for per-column half selection, whole-group half selection under every contiguous partition, and the reference implementation's inclusive threshold rule with its actual removal count. Under the inverse-Cholesky kernel, all these square lower bounds survive raw calibration and every prescribed nonnegative damping. The square reductions encode an arbitrary product with quadratic overhead, weights bounded by four, covariance condition number below two, and separated score cuts. Their mechanism is a source-to-target factor cancellation, with separate snapshot bounds and isolated guards enforcing the different selectors. A local coefficient-extraction argument validates the exponent comparison in the presence of comparisons and square roots. The results concern exact numerical execution in a nonuniform scalar model; raw rectangular preprocessing and the direct inverse-matrix kernel are treated separately.

Compressing primitives such as accumulators and vector commitments, allow to rep- resent large data sets with some compact, ideally constant-size value. Moreover, they support operations like proving membership or non-membership with minimal, ideally also constant- size, storage and communication overhead. In recent years, these primitives have found numer- ous practical applications, with many constructions based on various hardness assumptions. So far, however, it has been elusive to construct these primitives in a strictly structure-preserving setting, i.e., in a bilinear group in a way that messages, commitments and openings are all ele- ments of the two source groups. Interestingly, backed by existing impossibility results, not even conventional commitments with such constraints are known in this setting. However, in many practical applications it would be convenient or even required to be structure-preserving, e.g., to commit or accumulate group elements. In this paper we investigate whether strictly structure-preserving compressing primitives can be realized. We close this gap by presenting the first strictly structure-preserving commitment that is shrinking (and in particular constant-size). We circumvent existing impossibility results by em- ploying a more structured message space, i.e., a variant of the Diffie-Hellman message space. Our main results are constructions of structure-preserving vector commitments as well as structure- preserving accumulators. We first discuss generic constructions and then present concrete con- structions under the Diffie-Hellman Exponent assumption. To demonstrate the usefulness of our constructions, we discuss various applications. Most notable, we present the first entirely prac- tical constant-size ring signature scheme in bilinear groups (i.e., the discrete logarithm setting). Concretely, using the popular BLS12-381 pairing-friendly curve, our ring signatures achieve a size of roughly 3 Kbits.

We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.

Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries. Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.

Sleepy consensus allows parties to join and leave execution arbitrarily, which is a fundamental requirement for large-scale distributed systems. Classic longest-chain protocols, such as Bitcoin and its variants, achieve consensus under this model but suffer from inherent long latency. In contrast, recent protocols that build upon the classic view-based BFT paradigm can achieve constant expected latency and short best-case latency under optimal resilience, but they often incur high communication cost. We observe that the high communication overhead stems from the time-shifted quorums, a technique that makes quorum certificates transferable under dynamic participation. The technique relies on extensive message forwarding to reconcile parties' inconsistent local views, and thus incurs a cubic communication cost unavoidably. In this work, we tackle the problem by proposing a novel way to transfer certificates. Building on this, we construct a Byzantine Agreement (BA) protocol secure against the state-of-the-art growing adversary model. Our BA protocol achieves optimal resilience, constant expected round complexity, and an expected communication complexity of $O(nNL+nN\kappa+nN\log N)$, where $n$ is the maximum number of awake parties throughout the execution, $N$ is the total number of eligible parties, $L$ is the input length, and $\kappa$ is the security parameter. We also present an efficient recovery mechanism for our BA, incurring only $O(N\kappa+nL)$ bits per recovering party. Then we extend our BA to an Atomic Broadcast (ABC) protocol that achieves optimal resilience, constant expected latency, and an expected amortized communication complexity of $O(nNL+nN\kappa+nN\log N)$ per input value. The recovery mechanism for our ABC incurs $O(N\kappa+n\ell L+n\ell \kappa)$ bits per recovering party, where $\ell$ is the number of views that the party has slept for. Last but not least, we establish communication lower bounds of $\Omega(N^2L)$ for sleepy BA and ABC. The result shows that our BA and ABC are communication-optimal when $L$ is sufficiently large (i.e., when $L=\Omega(\kappa+\log N)$), and highlights a fundamental limitation of communication efficiency in the sleepy model.

We describe THED, a threshold version of the Dilithium signature scheme (ML-DSA), whose issued signatures are valid for the genuine Dilithium verification algorithm. The signing protocol has two rounds of communication, one of which that lends itself to preprocessing. The scheme supports arbitrary number of users and threshold parameter. The construction consists in running Dilithium's signing algorithm under Threshold Fully Homomorphic Encryption (ThFHE), except for the computation of the signing challenge that happens in clear. For signing-mask generation, SHAKE is replaced by a ring variant of the Darkmatter PRF under an additional pseudorandomness assumption. Due to the type of operations performed, we rely on the CKKS scheme for homomorphic computations. However, a number of challenges remain, for which we develop new tools. In particular, we describe a CKKS-BFV continuum that helps for modular operations in the context of other non-arithmetic operations, a hybrid-format homomorphic comparison when the input is the sum of a bit-decomposed integer and a small integer, and a modulus-thrifty homomorphic comparison of larger non-bit-decomposed integers. Furthermore, to ensure the protocol is communication efficient, we developed a new threshold decryption method for CKKS providing more compact decryption shares. Our proof-of-concept implementation of the FHE components of the signing protocol runs in under 1.3s on an RTX-5090 GPU, with 23.6KB of communication per party for the NIST level-2 Dilithium variant. In the randomized signing mode, most of the computation can be run in an offline phase without the message to be signed; the online cost then shrinks to under 0.25s. Apart from the two decryption steps, this computation is entirely public and can be delegated to a server with more powerful hardware.