International Association
for Cryptologic Research

The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data.

Our first contribution leverages LWE with a sparse small-norm secret, an assumption known to be equivalent to standard LWE and already widely used in FHE constructions. For an LWE secret of dimension $n$ and Hamming weight $h$, we obtain bootstrapping procedures whose arithmetic complexity decreases from $\tilde O(n^2)$ to $\tilde O(n h)$ $\mathbb{Z}_q$ multiplications while preserving the same asymptotic number of additions. Concretely, this yields a $4.5$--$7.5\times$ practical speedup for gate and functional bootstrapping over the state-of-the-art OpenFHE implementation.

Our second contribution introduces a new RLWE variant with structured secrets, called \emph{\mainrlwevarianttext}, and uses it to significantly reduce the circuit depth of FHEW/TFHE bootstrapping via a new relinearization-free BV multiplication technique. In concrete parameter settings, this reduces the number of sequential NTT/INTT layers required for bootstrapping to just 3, compared to more than 500 in standard FHEW/TFHE, while keeping the overall number of unit 32 or 64-bit word operations comparable to standard FHEW/TFHE bootstrapping. This substantial depth reduction suggests the potential for significantly lower bootstrapping latency on parallel, high-throughput architectures such as GPUs.

Finally, we analyze the security of the new RLWE assumption underlying our depth reduction, including worst-case-to-average-case and search-to-decision reductions, as well as evaluations against concrete attacks.

Zero-knowledge proofs are an operational infrastructure for rollups, private payments, verifiable execution, and zkVM applications. We treat them as succinct proofs of validity whose privacy properties depend on the system and the mode of use. Published benchmarks often compare different workloads, proof modes, and hardware paths, which makes their results hard to interpret. This work presents a unified host-agent framework for benchmarking heterogeneous proving systems under a common execution and reporting method. Each prover runs in an isolated containerized agent and is selected through a scheme-adapter layer. The agent reports canonical JSON artifacts linked to a hashed run manifest and workload-specific semantic contracts. The host checks the public semantic fields and the agent's verification flag to ensure backends are compared on the same declared public claim, even when their circuits, traces, or guest pipelines differ. We evaluate circuit-based, transparent, GPU-accelerated, folding, and zkVM systems: Groth16, ICICLE, Halo2, Plonky3, Winterfell, Nova, RISC Zero with CUDA and Groth16 wrapping, and SP1 with and without AVX. The suite uses six primary workloads with comparable semantics, together with secondary hash workloads that expose specialization. No prover family dominates all deployment criteria. At 8 CPU cores, Plonky3 and Winterfell have the smallest across-case proving-time and RAM figures. Groth16 and ICICLE produce sub-kilobyte proofs. Winterfell has the lowest host verification time. zkVM systems trade larger proofs and higher memory for programmability. On the Merkle-path micro-benchmark, pairing artifacts remain sub-kilobyte, whereas wrapping a zkVM receipt yields a Groth16-sized artifact at a high proving cost. GPU acceleration helps most after fixed setup costs are amortized. The main contribution is methodological: validate the statement being proved, disclose the security profile, and report resource limits in addition to proving time.

Decentralized lending protocols encode credit markets as smart contracts whose design choices affect gas cost, capital efficiency, liquidation behavior, and risk allocation. We compare Aave V3, SparkLend, Compound III, and Morpho Blue in matched Ethereum fork tests with wstETH collateral, USDC debt, and one fixed chain state. The tests measure call-path gas, annualized rates, thirty-day debt growth, maximum borrow capacity, and liquidation outcomes. It is important to note that the observed orderings for gas costs and rates are specific to this test artifact and could change under different collateral assets or utilization regimes. Within this setting, Morpho Blue has the lowest measured interaction call-path gas and highest borrow capacity, while shifting risk selection to isolated permissionless markets. Furthermore, Morpho Blue's evaluation uses a deployed market for rate measurements but a constructed market for liquidation testing. Aave V3 and SparkLend provide broader pooled-market abstractions with higher measured call-path gas. Compound III simplifies borrowing around one base asset per market; its low-gas absorb step is offset by a separate buy collateral liquidation path. We provide a Foundry-based Ethereum-fork test suite for reproducing these measurements and comparing lending-design trade-offs.

Decentralized Finance (DeFi) continues to experience rapid growth, yet a significant portion of capital remains inefficiently utilized in overprovisioned lending reserves or inactive liquidity positions. This paper presents two extension-based improvement proposals aimed at increasing capital efficiency in DeFi protocols. The first addresses idle capital in pool-based lending by adding an allocation layer that can deploy otherwise unused liquidity into external yield-generating strategies. The second targets inactive concentrated-liquidity positions through a position-management layer that automates range migration. Both proposals are examined in terms of motivation, mechanism design, expected effects, implementation approach, and practical limitations. Evaluation results are proposal-specific: the lending analysis indicates meaningful supplier-yield uplift under selected external-yield assumptions, while the range-migration analysis focuses on active-time sensitivity and execution cost. Prototype benchmarks suggest that both mechanisms can be implemented as modular extensions, but also expose additional gas overhead and proposal-specific risks, including external-strategy dependence, recall and loss-allocation concerns, and range-policy misconfiguration.

We remove the Boneh--Lipton conjecture from the proof of Corrigan-Gibbs and Wu (CRYPTO~2024) that Jacobi signatures modulo $N=p^2q$ are one-way. This relates the one-wayness of the pseudorandom generator proposed by Damg{\aa}rd in 1988 to a standard number-theoretic problem alone.

Several decentralized applications and blockchains, such as blockchain-based voting systems or Proof-of-Social-Capital, require a strict one-account-per-person policy, yet public identity records often expose sensitive attributes or enable offline attribution. This work presents a Proof-of-Uniqueness blockchain-based registry that composes an issuer-signed verifiable credential, two zero-knowledge proofs, a threshold verifiable oblivious pseudorandom function (vOPRF), and a smart contract. The first proof authorizes a blinded evaluation of an issuer's certified canonical identifier, and the second validates the OPRF transcript and binds the resulting global nullifier to a wallet. The design further binds issuer authorization, credential status, validity bounds, canonical encoding, and replay state. Its person-level guarantee is conditional on a stable injective identifier within a coordinated issuance namespace and a stable, valid OPRF key. Confidentiality holds against public observers and against fewer than the OPRF threshold of nodes, but not against an issuer that actively probes its own identifiers. Our prototype couples Noir and UltraPlonk circuits, three local threshold OPRF nodes, and a Solidity contract. For one fixed-schema credential input, it derives a single wallet-bound deterministic nullifier, verifies a real 2,144-byte proof on-chain, and rejects a repeated nullifier with $O(1)$ lookups. One real enrollment consumes 615k gas, and proof construction takes about 65 seconds on one desktop software thread.

Memory-Hard Functions (MHFs) are a cryptographic primitive designed to protect passwords and other low-entropy secrets against brute-force attacks. The strongest and most natural formalization of memory-hardness is sustained space complexity (SSC), which measures how long an attacker's memory remains above a given threshold. Ideally, one would like to ensure that any parallel attacker must sustain $\Theta(N)$ memory for $\Theta(N)$ steps, while the function can also be computed in sequential time $\Theta(N)$. Unfortunately, this goal is impossible to achieve. Thus, the appropriate objective is to establish strong tradeoffs between sustained space complexity and cumulative memory complexity (CMC), another strong notion of memory hardness. Blocki and Holman (CRYPTO 2022) achieved strong SSC/CMC tradeoffs in the dynamic pebbling model, but their construction relied on expensive combinatorial graphs, and the pebbling abstraction does not rule out more efficient attacks in the stronger Parallel Random Oracle Model (PROM).

We address both limitations. We construct a new data-dependent MHF (dMHF), DEGSample, and prove the first SSC/CMC tradeoff for dMHFs directly in the PROM. In the dynamic pebbling model, DEGSample achieves the same ideal tradeoff as prior work: any dynamic pebbling strategy either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a maximal CMC penalty $\Omega(N^{3-\epsilon})$. In the PROM, we prove that any attacker either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a steep CMC penalty of at least $\Omega(N^{2.5-\epsilon})$. To prove this, we introduce a new graph property called ancestral robustness and show that, together with another property called fractional depth-robustness, it suffices to obtain strong PROM tradeoffs via a natural dynamization procedure to turn the graph into a dMHF. The PROM lower bound combines a time-space trade-off argument with an extraction procedure that converts any PROM execution into a cost-equivalent pebbling of the realized graph.

While decentralized identity management systems strive for autonomy, most still rely on centralized mechanisms (e.g., phone numbers or government-issued IDs) to achieve Sybil resistance and prevent fake identity attacks. This article proposes an identity management architecture that ensures robust Sybil resistance and is fully decentralized, unlike the systems currently in widespread use. The proposed solution synergizes facial biometric verification with anti-Sybil social graph analysis. By leveraging blockchain technology, zero-knowledge proofs, and trusted execution environments, the system ensures the uniqueness, anonymity, and privacy of registered users without relying on centralized authorities. The operation of the proposed system was demonstrated through simulations of a network of 100 entities across three social graph models and through a proof-of-concept implementation that utilizes fast Plonky2 zero-knowledge proofs. To our knowledge, this is the first work that proposes a Sybil-resistant identity system without sacrificing decentralization and privacy, while not relying on any centralized credential issuers.

Zero-knowledge proofs based on VOLE have recently become a promising approach for designing post-quantum signature schemes. Such schemes are constructed by having a signer prove knowledge of a secret input for a prescribed one-way function. In this work, we optimize VOLE-based signature schemes from syndrome decoding (SD) and the permuted kernel problem (PKP). Despite relying on different one-way functions, these schemes share a common modeling method. Elementary vectors are compressed into shorter witnesses and then reconstructed through low-degree polynomials. We propose a unified framework for elementary-vector encoding and reconstruction. By choosing different parameters, this framework captures previous modeling approaches for SD and PKP as special cases. Based on this framework, we propose an optimized encoding and reconstruction approach that reduces the extended witness size and hence the final signature size. At NIST Level I security, our SD- and PKP-based schemes achieve “signature + public key” sizes of 3,496 and 3,341 bytes, respectively, improving over the corresponding 3,775 bytes of SDitH v2.0 and 3,577 bytes of PERK v2.2. Furthermore, we construct a 3,673-byte post-quantum ring signature for rings of 2^20 members, which is 27% and 70% smaller than those of Chiang et al. (CCS ’25) and BLOOM (ASIACRYPT ’22), respectively.

Private Set Union (PSU) allows two parties to compute the union of their private sets while revealing nothing beyond the union. Existing PSU protocols mainly follow two paradigms: reverse private membership test (RPMT) and invertible Bloom lookup table (IBLT). IBLT-based protocols achieve linear complexity using lightweight symmetric-key operations and offer excellent concrete efficiency. RPMT, on the other hand, provides a more general membership-testing functionality that can serve as a reusable building block for PSU and other private-set computations. However, existing RPMT-based protocols either rely on costly building blocks, such as public-key operations and generic secure two-party computation, or incur super-linear complexity. This raises a natural question: can the generality of the RPMT paradigm be retained while matching the asymptotic and concrete efficiency of IBLT-based PSU?

In this work, we answer this question affirmatively by introducing a lightweight mechanism for multi-query membership testing. Our mechanism yields a concretely efficient multi-query RPMT (mqRPMT) protocol that is useful beyond PSU and may be of independent interest. Building on this protocol, we construct a PSU protocol with linear computation and communication complexity. Our construction avoids expensive public-key operations and generic secure two-party computation, relying instead on efficient symmetric-key primitives.

We extensively evaluate our protocol against state-of-the-art PSU protocols from both the RPMT and IBLT paradigms. Compared with the leading RPMT-based PSU protocol from PKC 2024, our construction is $41.7\times$ $-$ $48.9\times$ faster in the LAN setting and up to $4.5\times$ faster in WAN settings. Compared with the leading IBLT-based PSU protocol from EUROCRYPT 2026, our protocol achieves competitive and, in several metrics, superior performance: it is $1.9\times$ $-$ $2.5\times$ faster in LAN settings and reduces communication by up to $1.4\times$. These results demonstrate that the broader applicability of the RPMT abstraction need not come at the cost of asymptotic or concrete efficiency.

The Learning With Errors (LWE) problem with small max-norm secrets and errors forms the foundation of several practical lattice-based cryptographic schemes, including NTRU-based constructions and the recently standardized CRYSTALS-Kyber and CRYSTALS-Dilithium. While recent combinatorial attacks have significantly improved the asymptotic complexity of solving small max-norm LWE, the fastest known methods require prohibitively large memory, often comparable to their runtime. To address this issue, Esser et al. (ASIACRYPT~2023) introduced the first substantially improved polynomial-memory algorithms for recovering small max-norm LWE secrets via nested collision search. In this work, we further improve the asymptotic complexity of polynomial-memory attacks on small max-norm LWE. We introduce a refined nested collision search framework together with new representation structures that increase the number of valid representations while preserving polynomial-memory complexity. This leads to improved asymptotic runtimes across the entire range of relative secret weights. For uniformly random ternary secrets of length $n$, our best algorithm reduces the polynomial-memory runtime from $2^{0.926n}$ to $2^{0.8595n}$, corresponding to an asymptotic speedup of approximately $2^{0.0665n}$. We further extend our framework to the secret distributions used in CRYSTALS-Kyber and CRYSTALS-Dilithium, obtaining improved complexity exponents. Additionally, we apply the proposed refinement to the polynomial-memory nested collision search framework of Esser and May~(EUROCRYPT~2020) for random subset-sum problem, reducing its asymptotic runtime from $2^{0.645n}$ to $2^{0.6432n}$. Although the latter improvement is modest, it provides an independent application of our framework and demonstrates its applicability beyond the LWE setting.

Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In this paper, we provide a positive answer to this question. Our Hoeffding exponent is sharp, as shown by a scalar obstruction. Our Chernoff and Bernstein constants improve upon those in [GLSS18] and Neeman, Shi, and Ward'24 [NSW24], respectively.

This paper studies the post-quantum multi-key security of Galois/Counter Mode (GCM) in the Quantum Ideal Cipher Model (QICM). GCM is one of the most widely deployed AEAD schemes. In practice, widely deployed cryptosystems are often instantiated under many independent keys, making the multi-key setting practically relevant. A trivial extension of a single-key security bound to the multi-key setting incurs a security loss proportional to the number of keys. In particular, in the post-quantum setting, the term corresponding to exhaustive key search becomes $up^2/2^k$, where $u$ is the number of keys and $k$ is the key length. Here, $u$ is the number of keys, $k$ is the key length, and $p$ is the number of quantum queries to the underlying block cipher $E$ and its inverse, which serves as a coarse measure of the amount of offline (quantum) computation performed by the adversary. For example, when $u=2^{32}$, the trivial bound does not guarantee security for $p \geq 2^{48}$ when $k=128$, and even for $k=192$, it ceases to guarantee security for $p \geq 2^{80}$.

We show that, at the cost of some additional loss terms, the term $up^2/2^k$ can be replaced by a term of order $\sqrt{dp^2/2^k}$, where $d$ denotes the maximum number of keys under which the same nonce appears in encryption queries. Thus, when $d$ is much smaller than $u$ (and the additional loss terms remain small), our bound improves upon the trivial multi-key bound. This can be viewed as a post-quantum counterpart of the classical result of Hoang et al. (CCS 2018). As in their work, we further show that, for randomized nonce-generation mechanisms that abstract patterns used in protocols such as TLS, the parameter $d$ remains small even when $u$ is large. Although our bounds are not tight and leave room for improvement, they yield a notable improvement over the trivial multi-key bound for several concrete parameter settings. To the best of our knowledge, this is the first non-trivial post-quantum multi-key security bound for an AEAD mode in the QICM. Our proof combines the reprogramming-and-resampling approach of Alagic et al. (EUROCRYPT 2022) with counting arguments used in the classical multi-user analysis of GCM by Hoang et al.

AI image generation has made image misinformation a serious concern. To address this issue, the Coalition for Content Provenance and Authenticity (C2PA) standard adopts digital signatures to attest that an image originates from an authorized source, such as an attested camera or authorized AI provider. In practice, however, raw images are rarely published directly: photos are typically compressed before publication, which invalidates any C2PA signature. Recent works have proposed the use of zero-knowledge proofs (zk-SNARKs) to prove that only allowed edits were applied to a C2PA-signed original image. Unfortunately, prior works only support simple edits (e.g. cropping, blurring, and resizing) and do not support lossy image compression like JPEG, which is ubiquitous. The purpose of compression is to save communication. Therefore, unlike other edits, it cannot be verified directly, requires small proof sizes, and is unsuitable to outsourcing. To address these limitations, we present SPEG, the first practical proof system that supports the full image-transmission pipeline on personal devices. We present two protocols that support JPEG compression, while proving validity of the C2PA signature on the original image. The two modes are incomparable: the first is compatible with an arbitrary hashing algorithm (we use Poseidon for efficiency), whereas the second is significantly faster but requires the C2PA to use a polynomial commitment (e.g., KZH) instead of a conventional hash. Our key optimizations are handling the non-algebraic JPEG Encoding outside the proving circuit, and avoiding range checks in our floating-point arithmetic. We can prove the JPEG compression of an FHD(1080p) image in 47s in the Poseidon mode and in 2s in the fast mode. The fastest prior work (VerITAS) which only handles simple resizing, requires 227s on the same consumer hardware. Additionally, we identify a security gap in VIMz (PETS 25) that enables forgery of proofs for unauthorized images and provide a fix. We also prove that we can securely use the popular powers-of-tau SRS with the polynomial commitment scheme KZH.

Silent threshold encryption is a generalization of threshold encryption where the public encryption key associated with a group of users is a deterministic function of their individual public keys. The main efficiency requirement is that the ciphertext size should be sublinear in (and ideally, independent of) the size of the decryption quorum $N$. Existing constructions of silent threshold encryption for arbitrary threshold policies have either relied on bilinear maps or on heavyweight tools such as witness encryption and indistinguishability obfuscation. Recently, several works have shown how to support constant thresholds from the decomposed learning with errors (LWE) problem.

In this work, we show how to construct a silent threshold encryption scheme from the decomposed LWE assumption where the ciphertext size for encrypting a single bit is $\tilde{O}(T) + \mathsf{poly}(\lambda, \log N)$. Here, $N$ is the total number of users, $T$ is the threshold, and $\lambda$ is the security parameter. Our scheme achieves non-trivial succinctness for all thresholds $T = N^\varepsilon$ for any constant $\varepsilon < 1$. More generally, our scheme extends beyond threshold policies to any monotone policy family that has a succinct (computational) secret sharing scheme; the ciphertext in this case scales with the maximum number of corrupted shares.

The core building block in our work is a new bounded-collusion registered functional encryption (FE) scheme with succinct ciphertexts. Specifically, for $N$ users and a collusion bound $Q$, we obtain a registered FE scheme that supports depth-$d$ Boolean circuits on $\ell$-bit inputs and single-bit output with ciphertext size $Q \cdot \tilde{O}(d) + \ell \cdot \mathsf{poly}(\lambda, d, \log N)$. Security relies on the decomposed LWE assumption in the random oracle model. Previously, bounded-collusion registered FE for general circuits was known only from bilinear maps, evasive LWE, or indistinguishability obfuscation.

NTRU is one of the longest-tested lattice-based public-key encryption families and is often viewed as a compact alternative to (R/M)-LWE. Yet, after three decades of research, its potential for compactness remains an open area for further exploration: recent designs such as NEV (Asiacrypt 2023) and DAWN (Asiacrypt 2025) suggest that there is still room for improvement. This raises a natural question: Has NTRU reached its compactness limit? If not, how compact can it be while still remaining secure and efficient?

Motivated by this question, we aim to formalize a unified relationship between compactness and efficiency under the required security level. We present a common two-stage view of NTRU decryption. In the first stage, the decoder constructs a small set of candidate wrap-around errors. In the second stage, it verifies these candidates using either algebraic redundancy or trapdoor-derived distributional information. We introduce Free Candidate Localization (FCL), a generic first-stage method that ranks coordinates by their proximity to the centered boundary. FCL could be used in most lattice-based encryptions; we instantiate it in ML-KEM to achieve a $10\%$ smaller ciphertext at the cost of a $5\%$ slower overall runtime in the reference C implementation under NIST-I.

We organize modern NTRU encryptions into two frameworks. NTRU with Encoding leverages algebraic structure via auxiliary quotient rings. NTRU with Trapdoor exploits geometric structure through the NTRU trapdoor, then verifies candidate corrections using distributional tests. These frameworks give a common language for existing NTRU designs and for the compactness searches in this paper. Within an explicit search model, we derive heuristic compactness frontiers for both frameworks. At NIST-I, the encoding frontier yields a total public-key plus ciphertext size of 812 bytes, and the trapdoor frontier yields a size of 754 bytes, $15\%$/$21\%$ smaller than the previous lowest size of 964 bytes in DAWN.

Furthermore, we propose END, an instantiation of NTRU with Trapdoor plus FCL. At NIST-I, \textsf{END} has a 384-byte ciphertext, which is exactly half the size of the 768-byte ciphertext of ML-KEM-512, and is $12-19\%$ smaller than the shortest prior NTRU-style ciphertexts in BAT (TCHES 2022) and DAWN. In our reference C implementation, the combined encapsulation and decapsulation cost of END-512 is about $3\%$ higher than that of ML-KEM-512.

In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.

Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic. Exploiting SIMD parallelism in these computations is nevertheless nontrivial: central routines such as Montgomery ladders contain loop-carried dependencies, while point, pairing, and theta-coordinate formulas expose only irregular fine-grained parallelism. We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of these higher-level primitives rather than vectorizing field multiplication in isolation.

We develop an end-to-end AVX-512IFMA implementation of SQIsign in which data remain in a radix-$2^{51}$ vector representation across most of the curve-side computation. Our redesign includes projective xDBLADD schedules for Montgomery ladders, batched point doubling in several coordinate systems, a vectorized biscalar ladder, fused cubical-arithmetic pairing steps, and batched one- and two-dimensional isogeny evaluation. Relative to the reference C implementation, our implementation achieves end-to-end speedups of $1.76\times$, $1.71\times$, and $3.18\times$ for key generation, signing, and verification, respectively, at NIST security level~I; combining the same implementation with Qlapoti increases the key-generation and signing speedups to $2.90\times$ and $2.69\times$.

To test whether these techniques are specific to SQIsign, we further apply the same AVX-512IFMA backend and higher-dimensional vectorization methodology to CORAL, a recent isogeny group action for post-quantum non-interactive key exchange based on two-dimensional $2$-isogenies. Across the five parameter sets in our experiments, this yields $1.28$--$1.40\times$ speedups for key generation and $1.92$--$2.46\times$ speedups for shared-key computation over the reference C implementation. These results provide cross-scheme evidence that algorithm-level SIMD scheduling is a reusable optimization dimension for higher-dimensional isogeny cryptography.

ML-DSA is a NIST post-quantum signature standard whose security argument rests on rejection sampling making released signatures independent of the secret key. Liu et al. and Damm et al. showed that a single leaked bit of the masking randomness per signature breaks this guarantee, making ML-DSA subkeys recoverable from a number of so-called informative relations, and the resulting attacks were sharpened by Schubert et al. and Bashiri et al.. All of them treat every leaked bit as equally trustworthy.

We show that they need not. After the $j$-independence transformation introduced by al., the values extracted from a clean and from a flipped bit are exact complements in absolute value, so the observable relation $|\tilde z|$ follows a two-component mixture whose components we determine in closed form for all leakage regimes. This yields, first, a method-of-moments estimator for the bit-error rate $p$ that requires only the informative relations an attack already collects and that, unlike the estimator of Schubert et al., also works in the low-leakage regime, down to leakage index $4$ for ML-DSA-44 and ML-DSA-87 and $5$ for ML-DSA-65, the same indices at which the attack itself remains feasible. However lower leakage indices come with a lower accuracy, at $25{,}000$ informative relations the mean absolute error for the lowest cases is about $0.022$ to $0.040$ compared to values below $0.002$ in the high-leakage regime. The noise estimator is also adjustable to estimate asymmetric noise rates. Second, it yields a posterior probability, for each individual relation, that its leaked bit is correct. Thresholding this posterior gives an $O(\alpha)$ preprocessing step that corrects relations classified as noisy and that any downstream attack can use unchanged, where $\alpha$ is the amount of informative relations.

Applied to the attack of Schubert et al., the preprocessing reduces the number of informative relations required for key recovery by about $20\%$ to $44\%$ across all three parameter sets, leakage indices $6$ to $9$, and error rates $20\%$ and $40\%$. Applied to the attack of Bashiri et al. for ML-DSA-44 at leakage index $8$, it improves key recovery across the noise range we tested: at $p = 0.45$ from $1{,}900{,}000$ informative relations, at $p = 0.40$ from $450{,}000$ informative relations, at $p = 0.20$ from $40{,}000$ informative relations, a single fixed threshold chosen in hindsight succeeds for $20$, $22$, and $23$ of $30$ seeds against $16$, $18$, and $19$ of $30$ without the preprocessing, and a parallel search over ten thresholds succeeds for $23$, $25$, and $29$ of $30$.

The Permutation Code Equivalence Problem (PEP) and Permuted Kernel Problem (PKP) are two notorious computational problems over linear codes used for building post-quantum digital signature schemes. Although traditionally analyzed over prime fields, recent proposals, such as the signature schemes PERK and SETH, have considered extension fields to improve efficiency and compactness. In this work, we analyze the hardness of solving PKP and PEP when instantiated over field extensions. %the latter between self-orthogonal codes. For binary field extensions, by exploiting a reduction to a structured variant of the Regular Syndrome Decoding Problem (RSD), we uncover new polynomial-time parameter regimes for both PKP and PEP, including families of self-orthogonal PEP instances and all self-dual instances over extensions of degree $\nu>4$. We also adapt the permutation-based Regular-ISD algorithm of Esser and Santini for RSD (CRYPTO '24) to PKP-derived instances, and uncover regimes of parameters for which it improves upon the state-of-the-art. Moreover, we present a reduction from a broad family of PEP instances over extension fields with odd characteristic to the Graph Isomorphism Problem, yielding a polynomial-time algorithm to solve those instances. Overall, our results invalidate the use of PEP over extension fields for most of the scenarios, and provide novel insights into the security of PKP over extension fields.