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