Upgrading cryptocurrencies to post-quantum security is inherently difficult, because their on-chain state associates users' holdings with public keys: users who fail to transfer their funds to (yet to be added) post-quantum signature schemes remain exposed to theft. In networks with Confidential Transactions (CT) such as Liquid, Monero, and Grin, which hide monetary amounts inside homomorphic Pedersen commitments, the situation is worse still: an adversary who computes a single discrete logarithm can inflate the currency as a whole, rather than merely steal individual funds. The contentious remedy is to expire all funds not transferred by a deadline, destroying the funds of everyone who fails to act. Switch commitments (Ruffing and Malavolta 2017) were proposed to avoid exactly this expiration, but only Grin has deployed them deliberately—and the security theorem later stated for its scheme does not hold, as we show. In this paper, we show that Liquid and Monero already deploy a switch commitment scheme by coincidence: the ciphertext a sender stores on-chain to convey the hidden amount to the recipient can be re-interpreted, together with the Pedersen commitment, as a switch commitment. We conceptualize this construction as coincidental switch commitments and prove it secure in the quantum random oracle model. Additionally, we save the construction that Grin deploys: it is computationally switch binding, with practical bounds in the algebraic group model. The real-world implication of our results is that these networks can be upgraded to post-quantum CT schemes without expiring any user funds.

SQIsign samples a random ideal of odd prime norm at every key generation and every signature through $\mathbf{PrimeNormIdealInertSampling}$. We revisit this step from a new perspective: the inert ideals of a given norm form a circle modulo the norm, and drawing lines through a fixed point of this circle turns a single random parameter into an ideal, hitting each ideal exactly once. Compared with the reference implementation, the new algorithm requires one modular inversion and a handful of additions and multiplications. It achieves $13.76\times$ speed-up at NIST security level I in SQIsign while producing an uniform output.

Quantum linear key-recovery attacks using QFT-based correlation state preparation can achieve superquadratic speedups, but their complexity grows rapidly with the active subkey dimension, potentially erasing the advantage over Grover's search. WSP (EUROCRYPT 2024) provides a natural mechanism for alleviating this bottleneck by replacing the key-recovery map with a spectrally punctured approximation of smaller active dimension. In this work, we establish a puncture-aware framework for QFT-based quantum key recovery, extending quantum linear cryptanalysis to key-recovery problems whose active-subkey dimension can be reduced through spectral puncturing. We further propose Q-Puncture, an automated optimization method tailored to quantum key-recovery complexity. Applied to Serpent, RECTANGLE-128, and PIPO-128, Q-Puncture yields a new family of punctured quantum linear key-recovery attacks whose modeled quantum complexities improve upon generic Grover search. The resulting attacks improve upon comparable QFT-based results, extend them to new settings, and provide further examples in which structured quantum cryptanalysis surpasses the generic quadratic speedup of Grover's search.

Falcon is one of the three post-quantum signature schemes selected by NIST for standardization so far. It is efficient and has particularly short signatures, but has the drawback of being difficult to implement correctly and securely, owing to its use of floating point arithmetic and secret-dependent lattice Gaussian sampling. In particular, obtaining implementations of Falcon that are protected against side-channel attacks seems to be a tremendous challenge that has no satisfactory solution so far. While it is theoretically possible to rely on generic countermeasures like masking, they are likely so costly as to be effectively inapplicable. And yet, side-channels are an actual threat to Falcon: a number of them have been demonstrated against various parts of the signing algorithm, including floating point operations and Gaussian sampling. Multiple power analysis attacks in fact achieve full key recovery from very realistic numbers of traces. This is especially the case for a series of side-channel attacks that can be broadly categorized as based on “sign leakage” within a specific part of the one-dimensional Gaussian sampler. In this paper, we take a closer look at this class of side-channel attacks, and obtain yet another one of a somewhat different flavor: while it also targets the sign of a variable in the one-dimensional Gaussian sampler, that variable is the input center, and in particular does not depend on the sampling randomness, making previously proposed mitigations modifying the base sampler ineffective. Furthermore, we propose, analyze and experimentally validate a novel, inexpensive countermeasure to protect Falcon against this class of side channel attacks. The idea, taking inspiration from shuffling, is to twist the target vector by random roots of unity in every recursive call of the fast Fourier sampling algorithm: this averages away the sign leakage efficiently. While this mitigation technique is heuristic and does not offer the provable guarantees of masking, it significantly enhances the physical security of Falcon fairly cheaply. In particular, it provides a more robust and more widely applicable protection than the countermeasure of Lin et al. (PKC 2025) at a much lower cost (incurring a 1.4-fold overhead in signing in dynamic mode and 2-fold in tree mode, compared to 3.5-fold and 6.8-fold for Lin et al. respectively). To the best of our knowledge, this is the first shuffling countermeasure proposed for Falcon.

AIMer v3 replaces AIM2 with AIM3. We test whether SIMD methods developed for AIM2 can accelerate AIM3 while preserving its results. We port the field-arithmetic, affine, party-parallel, and SHAKE methods of the earlier AVX-512 implementation to AIMer v3 and implement the same operations for AVX2. For Cortex-M55 MVE, we use 16-bit polynomial partial products for field multiplication, group corresponding 32-bit words from four parties, and vectorize both affine layers, including the input layer introduced in AIM3. The implementations preserve AIMer v3’s mathematical structure and proof procedures. For all six parameter sets, their outputs match the official known-answer tests and the reference results in differential tests. Relative to the reference on each platform, AVX2 and AVX-512 accelerate signing and verification by 3.14–4.41× and 4.59–6.55×, respectively. Cortex-M55 MVE accelerates the same operations by 1.28–1.91×.

Efficient execution of Post-Quantum Cryptography (PQC) in resource-constrained embedded environments requires the joint optimization of not only algorithm vectorization but also dataflow and instruction execution order. This paper implements the HAETAE-2/3/5 and SMAUG-T1/3/5 parameter sets of two Korean Post-Quantum Cryptography Competition (KpqC) winners using the M-profile Vector Extension (MVE) of the Arm Cortex-M55 and analyzes the contribution of each optimization stage to performance improvement. We first establish an MVE-intrinsic implementation as the baseline and then present Manually Optimized MVE Assembly that redesigns the data layout, register reuse, and memory access patterns of the principal kernels. Slothy is subsequently applied to this assembly to optimize instruction order and register allocation for the Cortex-M55 pipeline. This process is applied to the Keccak/SHAKE operations shared by the two schemes; the Number-Theoretic Transform (NTT), fixed-point Fast Fourier Transform (FFT), and Gaussian sampling of HAETAE; and the Toom-Cook/Karatsuba polynomial multiplication of SMAUG-T. Measurements on the STM32N657 show that the implementation with Slothy achieves speedups of 2.349–2.424× for the HAETAE forward NTT, 1.701–1.732× for the FFT including squared-value accumulation, and 1.322–1.350× for the SMAUG-T matrix–vector multiplication over the intrinsic implementation. At the complete-scheme level, HAETAE and SMAUG-T achieve speedups of 1.050–1.212× and 1.108–1.212×, respectively. These results demonstrate that direct dataflow redesign and automated instruction scheduling eliminate different bottlenecks and that combining the two stages can effectively improve the performance of Cortex-M55-based PQC implementations.

We present new constructions of the following primitives featuring succinct communication: - Batch threshold encryption: Assuming RSA and DCR, we construct a threshold encryption scheme in which a batch of ciphertexts can be decrypted via short hints from a quorum of decryptors. Previously, this was known only from bilinear maps. - Aggregate signatures: Assuming RSA, we construct a signature scheme where signatures on different messages from an arbitrary number of signers can be aggregated into one signature. Our construction achieves bounded-query security. In contrast to prior (fully secure) schemes in the standard model, ours makes black-box use of cryptography. - Broadcast encryption: Assuming RSA, we construct a secret-key encryption scheme where a sender can encrypt a message to multiple recipients via a short ciphertext. Our construction achieves bounded-query security. Previously, (fully secure) broadcast encryption was known from bilinear maps or obfustopia or nonstandard lattice assumptions. Our constructions are simple and achieve optimal succinctness in the key parameter (decryption batch size or number of signers or recipient set size). In this metric, they outperform or match known constructions. Our results are obtained by applying the lens of projective pseudorandom generators (PPRGs) to these problems. Towards this, we identify new enhanced properties for PPRGs and instantiate them from the RSA assumption.

The dual attack is a central tool for evaluating the concrete security of the Learning with Errors (LWE) problem, which underlies lattice-based cryptosystems such as ML-KEM. The MATZOV-style FFT dual attack combines dual distinguishing with an FFT-accelerated guessing phase and provides one of the main frameworks for concrete attack estimates against ML-KEM. However, its correctness analysis has traditionally relied on heuristic independence assumptions, leaving a gap between practical attack estimates and provable guarantees. In this work, we give a rigorous correctness analysis of a MATZOV-style FFT-based dual attack for the ML-KEM parameter sets. The analysis treats the correct and incorrect candidates separately and applies different conditioning arguments on the two sides, because the former requires a provable lower bound on the score of the true candidate, while the latter requires a uniform upper bound for all wrong recovered guesses. Combining these two parts, we obtain an explicit success criterion and a provable threshold separation for the FFT score. For concrete cost estimation, we follow the same cost-estimation convention as previous provable dual-attack analyses whenever the same subroutine is involved, using Pouly and Shen's estimates (EUROCRYPT 2024) as our main baseline. We obtain attack costs of 210, 300, and 410 bits for ML-KEM-512, ML-KEM-768, and ML-KEM-1024, respectively. Relative to this baseline, our estimates reduce the attack costs by 28, 47, and 68 bits for ML-KEM-512, ML-KEM-768, and ML-KEM-1024, respectively.

We present Argo, a randomized encoding scheme for the invalidity of pairing-based SNARKs like Groth16. Argo allows an encoder to encode a proof such that a decoder can derive a secret if the proof is invalid. We prove the selective security of invalidity Argo, as well as the adaptive security of validity Argo, under DDH in one source group of a bilinear pairing in the standard model, a standard assumption that holds in the generic group model used to analyze Groth16. We show how to couple invalidity Argo with a projective garbling scheme like Argo MAC or Duty-Free Bits to construct a garbled circuit for Groth16 invalidity as a function of the proof bits, and how to use it with BitVM to construct a permissionless, optimistic Groth16 verifier for Bitcoin: a decoder proves a proof invalid by publishing a secret, and the decoder can be anyone, not necessarily known in advance. When instantiated with BN254, Argo has an offline encoding size of about 21 kB, a thousand times smaller than the projective garbling scheme, and an end-to-end protocol size more than three orders of magnitude smaller than existing Yao-based approaches. Generating an Argo + Argo MAC garbled circuit takes tens of milliseconds on a laptop, compared to minutes for a Yao GC. Argo is the first protocol that makes permissionless, optimistic SNARK verification on Bitcoin practical.

Updatable Public-Key Encryption (UPKE) enables forward secrecy in asynchronous settings like secure group messaging. At EC'25, Albrecht, Benčina and Lai proposed the first plausibly post-quantum UPKE scheme supporting unlimited updates, based on permutation code equivalence (PCE) over finite fields and hollow lattice problems. However, it has impractically large public keys (4.8MiB) and ciphertexts (1.5MiB). In this work, we first replace the information-theoretic Hollow LHL with a computational assumption secure under binary-secret binary-error LWE, reducing key sizes by an order of magnitude. Second, we show that generalising to Module-LWE is not beneficial: PCE instances over $\mathbb{F}_{q^d}$ admit a linearisation attack via the $q$-Frobenius structure, enabling recovery of secret isometries unless code rates are inflated by $d$, negating any size benefit from module lattices. Third, we establish IND-CCA security in the model of Alwen, Fuchsbauer and Mularczyk (EC'24), but do not achieve `joiner security' like other post-quantum candidates. Finally, we introduce a heuristic multi-key variant using matrix-valued secret keys, enabling efficient encryption of $\ell$ bits per ciphertext. We define the Hinted SPCE assumption to capture the main cryptanalytic challenge and show that the performance gain is likely too small to justify adoption, unless the new assumption can be avoided. Overall, our `unlimited' scheme has update sizes 3.5 to 10 times larger than lattice-based schemes limited to $2^{20}$ updates, depending on the aggressiveness of parameter choices.

Oblivious RAM (ORAM) protocols enable a resource-constrained client to outsource data to an untrusted server, and access this data without revealing what is being accessed. While ORAM protocols are almost optimal, concretely efficient ORAM protocols incur sub-optimal bandwidth overhead and require multiple roundtrips of communication between the client and the server. In this work, we introduce write-public ORAM: a relaxed variant of ORAM that hides what data is being read, but not what data is being updated on the server. We present wpORAM, a write-public ORAM that modifies Path ORAM to achieve a log N-factor improvement in bandwidth and roundtrips over Path ORAM during writes. The asymptotic cost of reads in wpORAM remains the same as Path ORAM, with a slight slowdown in practice. wpORAM, when used with a Trusted Execution Environment (TEE), can implement a dynamic Private Information Retrieval scheme that efficiently updates data stored in a public database. We use wpORAM to implement a private blockchain RPC server that enables blockchain clients to query RPC nodes without revealing their queries to the server operator. Our evaluation shows that, while syncing with the latest blockchain state, our RPC node achieves a 3-4x speedup over Path ORAM. Our RPC node can serve reads with a slowdown of approximately 23% compared to Path ORAM.

A pseudorandom code (PRC) is a cryptographic primitive combining pseudorandom encryption and error-correcting codes (Christ and Gunn, CRYPTO 2024). That is, any polynomial number of codewords are pseudorandom, and decryption tolerates a constant rate of bit-flips. Although this might seem like a natural combination of standard properties, it is a fundamentally new object: PRCs are black-box separated from many primitives, including one-way functions, public-key encryption, and even virtual black-box obfuscation (Döttling et al., Garg et al., TCC 2025). Pseudorandom codes were introduced to build watermarks for AI-generated content. In particular, they imply watermarks that preserve the model's quality in a strong sense and withstand modification of the content. This relationship makes pseudorandom codes an inviting area for researchers: improvements to this simple theoretical object yield better watermarks. Beyond watermarks, PRCs have been used to construct error-correcting codes against computationally bounded channels (Lu et al., CRYPTO 2026), and techniques underlying them have led to new public-key encryption schemes (Döttling et al., CRYPTO 2026, Dyseryn et al. ASIACRYPT 2026). This survey aims to equip the interested researcher with tools to make progress in the area. We detail the current landscape of definitions, techniques, and applications. A main contribution is introducing new tricks and assembling existing tricks to generically strengthen PRCs (e.g., from substitution-robustness to random-deletion-robustness). We also show natural weakenings of PRCs that can be constructed from OWFs or even unconditionally. We conclude with a number of concrete open questions.

This paper studies the cryptanalytic extraction of convolutional neural networks (CNNs). Existing cryptanalytic extraction attacks on CNNs assume that the network architecture is known, and try to recover model parameters. In this paper, we prove for the first time that the architecture assumption can be removed for CNNs with both max and average pooling. Our core finding is that the spatial geometry of the weight vectors recovered by existing parameter-recovery attacks naturally leaks the architecture. We formalize this geometry and establish its correspondence with the architectural knowledge of a convolutional layer: (1) The sparsity consistency with the convolution receptive field reveals the layer type, the kernel size, and the stride; (2) The numerical consistency with the kernel parameters reveals the padding mode and the output-channel number; (3) The structural consistency with the pooling operation reveals the pooling type, the window size, and the stride. Although the recovered vectors are obtained using different methods in the raw-output and hard-label settings, their spatial geometry remains the same. Therefore, our architecture recovery is feedback-agnostic: combined with a parameter-recovery attack, it yields a complete cryptanalytic extraction framework that recovers both the architecture and the parameters in the black-box setting. Extensive experiments, including both layer-wise and end-to-end ones, on a wide range of CNNs demonstrate that simultaneously recovering the network architecture and the model parameters is practical.

We present $\mathsf{Accordion}$, a new proof system that works in two steps: - $\textit{Accumulate}$: The first building block is a multi-folding scheme that efficiently accumulates $k$ different instances of a degree-$d$ polynomial relation into a single accumulated instance, without using recursion. Our scheme builds on the Protostar [Bünz & Chen, ASIACRYPT '23] and Protogalaxy [Eagen & Gabizon, ePrint 2023/1106] line of work, improving further the verifier efficiency. It supports the same expressive class of relations, arbitrary-degree polynomial constraints, enabling efficient folding for CCS, Plonkish constraints, and even custom gates. - $\textit{Decide}$: The second block is a SNARK decider for the folding scheme, which efficiently proves the validity of the resulting accumulated instance using off-the-shelf optimized building blocks. We give a concrete instantiation consisting of a Plonk-based proof plus an additional KZG polynomial commitment opening. This design is especially attractive in batch-aggregation settings where a prover collects many independent witnesses, folds them into a single accumulator, and then runs one succinct decider to certify the entire batch. Our scheme avoids costly recursion overheads. We implement $\mathsf{Accordion}$ and evaluate it against a highly optimized Plonk proving pipeline ($\texttt{midnight-zk}$). For $k=64$ instances, $\mathsf{Accordion}$ is up to $2.5\times$ faster than computing $k$ Plonk proofs for SHA-256 preimages, with a $3\times$ faster verifier and $4\times$ smaller proofs. Its prover is also an order of magnitude faster than using IVC to aggregate the $k$ proofs.

Many cryptographic protocols rely on affine message authentication tags of the form \({\boldsymbol\sigma}=\Delta{\boldsymbol x}+{\boldsymbol k}\), the batch version of information-theoretic MAC. Generating the tags for a long message vector typically requires communication linear in its length. Recent chosen-input VOLE protocols achieve succinct communication, but do not allow the authenticator’s key $k$ to be fixed in advance. We introduce $\mathit{batch\text{-}MAC}$, a primitive that authenticates a chosen message vector in two messages while allowing the authenticator’s key vector to be generated beforehand from a short seed. For a vector of length \(m\), we construct batch-MACs with \(O(m^{2/3}\lambda)\) communication under the decisional composite residuosity (DCR) assumption and \(\operatorname{poly}(\log m,\lambda)\) communication under the learning with errors assumption. Both constructions require a common reference string (CRS). We find applications in constrained pseudorandom functions, 2-message 2PC, and succinct zero-knowledge arguments.

The Terrapin attack against SSH channel integrity (USENIX Security 2024) used a novel attack vector: attacks on the channel state. Surprisingly, not all AEAD modes of SSH were equally affected by this attack, and it remained an open question if "unaffected" meant "secure". Existing formal models for secure channels are based on stateful encryption. However, these models do not define what the channel state is and how it is used as input to the different AEAD modes. In this paper, we propose a formal model for channel integrity under partially chosen state. Applied to the Terrapin attack, the chosen state is the SSH sequence number. It uses an abstract stateful encryption interface, for which we provide pseudocode descriptions for the eight most prominent AEAD modes used in SSH. By varying the SND oracle, we can model ciphertext-only (CO; the Terrapin attack), known-plaintext (KPA), and chosen-plaintext (CPA) attacks. This allows us to establish concrete bounds on the security of the AEAD modes. We find that all three Encrypt-then-MAC (EtM) modes and ChaCha20-Poly1305 in SSH are insecure in the CO model. AES-GCM is the only cipher secure in all three model variants. Going beyond Terrapin, we show that Encrypt-and-MAC (EaM) with a CBC cipher is secure, even in the KPA model. In particular, we describe a novel BEAST-like chosen-plaintext attack on the channel integrity of EaM-CBC, which separates the KPA and CPA models for this scheme.

In this work, we verify, using the Lean 4 proof assistant, that the Jolt zk-VM's expanded programs faithfully emulate a RISC-V CPU. Prior work translated the official Sail specification of RISC-V into Lean. We extend this model to define the Jolt ISA in Lean. We build a generator that runs Jolt's Rust bytecode expander and renders its output as Lean programs. Finally, for 51 out of 58 such programs, we prove these expansions are equivalent to their corresponding RISC-V instructions. This lays the groundwork for proving completeness and soundness of further stages of Jolt's proving pipeline.

Goldreich's pseudorandom generators (PRGs) expand a secret seed by evaluating a fixed low-locality predicate on random subsets of its bits. We study the concrete and asymptotic security of constructions whose local predicate combines majority with XOR. We introduce Deterministic Pooled Recovery (DPR), which guesses a set of seed positions and pools the outputs whose majority inputs are forced by the guess. The selected outputs yield noiseless sparse linear equations. For the proposed \(\operatorname{MAJ}_7\oplus\operatorname{XOR}_4\) challenge published in ToSC 2025, with seed length \(n=1024\) and output length \(m=n^2\), DPR has an estimated recovery cost of \(2^{109.71}\) operations using \(\omega=2.38\) for the linear-algebra exponent. This is below the claimed 128-bit security level. We also refine the common-bias analysis by evaluating its advantage at each fixed seed weight. This viewpoint motivates Bias-Amplified Pooled Recovery (BAPR), which uses partial majority bias to construct pooled noisy linear systems. For \(m=n^s\) with fixed \(s>1\), odd majority locality \(a\in\omega(1)\cap O(\log n)\), and fixed XOR locality \(b\ge3\), we prove that BAPR admits a worst-case \(2^{o(n)}\)-time implementation that recovers any fixed seed with high probability. This rules out exponential security in this intermediate-locality regime. In addition, we identify exploitable affine structure and residue constraints in proposed alternative predicates.

Adaptor signatures enable conditional payments on blockchain networks: a pre-signature is bound to a public instance $Y$ and can be completed into a valid signature by any party knowing a witness $y$ with $\mathcal{R}(Y,y)=1$, while the pre-signature and full signature together allow the signer to extract $y$. Existing constructions only support specific algebraically-structured relations, lose witness privacy, or have significant overhead both in signature size and computation. We present a practical adaptor signature framework for arbitrary NP relations, built from a new primitive we call Online/Offline NIZK whose proof is separated into online and offline parts. The key property is that the witness can be extracted from the online part knowing the randomness used in the offline part. We give two generic constructions: a basic scheme achieving witness hiding, and an instance-hiding scheme achieving a new, stronger forward-secure privacy notion we introduce. We instantiate our framework for the AES-128 relation using the VOLE-in-the-Head paradigm and the FAEST post-quantum signature scheme. The resulting complete signature is $11.6$ kB, roughly $60\%$ smaller than the state-of-the-art adaptor signature for NP (Ciampi et al., CT-RSA '25), and our implementation is an order of magnitude faster in overall signature generation, verification, and extraction.

The Round-3 SNOVA signer samples vinegar variables, which are elements of $\mathbb{F}_q$, by reducing uniform byte strings modulo a power of $q$. We show that the resulting bias leaks secret-key information for the six odd-characteristic alternative parameter sets. Even though the leakage is small (the most leaky variables leak at most $0.086$ bits of information), this still leads to efficient key-recovery attacks which we demonstrate in practice. Key recovery becomes a $q$-ary LPN problem of dimension $o\ell$ with a known, full-support error distribution. A naive algorithm needs some ten thousand signatures and $2^{90}$ to $2^{130}$ operations, which is already far below the $170$ to $331$ bits claimed for the six affected sets. Using more signatures makes the attack practical: using standard LPN machinery - BKW reduction with Fourier hypothesis testing - we recover the secret key for four parameter sets in practice using between $9$ and $180$ million signatures, and at most 16 minutes of wall clock time. Fixing SNOVA to sample the vinegar variables uniformly would prevent the attack completely.

Many isogeny-based schemes rely on the Deuring correspondance and thus require computations with quaternion ideals. In this paper, we generalize the recent results of Leroux on the inert representation of quaternion ideals, yielding a normalized representation together with a set of simple and efficient algorithms for quaternion ideals in the context of the Deuring correspondence when the prime characteristic $p$ is equal to $3 \bmod 4$. One of the main benefit of our new algorithms is that the size of the integers involved in the computations is both easy to bound, and smaller than previous work. In particular, when applied to the latest version of SQIsign, our algorithms yield a concrete integer bound of $O(p^4)$ in the worst case, proven under an experimentally verified assumption on the size of the integers required to perform the lattice reduction part of the response sampling. This bound improves upon all known previous bound by a factor at least $O(p^2)$. Our new algorithms are used in the latest update of SQIsign's implementation submitted to the third round of the NIST call for additional post-quantum signatures. In particular, their low integer bounds facilitated the removal of a dependency on the GMP library in favor of a custom library of fixed-size integers without performance overhead. We stress that our algorithms are not limited to SQIsign, but apply to any isogeny-based cryptographic protocol that relies on the Deuring correspondence such as the PRISM signature scheme for instance.

The Institute of Commercial Cryptography Standards (ICCS) launched the Next-generation Commercial Cryptographic Algorithms Program (NGCC) and invited worldwide comments on draft submission requirements and evaluation criteria for cryptographic hash algorithms. Our analysis of seven submitted hash functions gives the following results: - Message differences that cancel in every key injection give explicit collisions for all four fixed-output variants of \textbf{MoFang} and both XOF variants at every finite output length. - Two distinct states of \textbf{Neulaser} become equal after one update, giving collisions for all three variants with the initialization used by the v2 reference and optimized implementations. - An invariant subspace of \textbf{CHIME-512} permits collision search using at most \(2^{64}\) hash evaluations when shifts act separately on 64-bit words, as in both submitted implementations. - \textbf{CHAMP}'s determinant constraint gives collision searches using at most \(2^{192}\) and \(2^{384}\) hash evaluations for its 512- and 1024-bit variants, respectively. - We exhibit explicit free-start collisions for all three \textbf{QSH} variants. In the semi-free-start setting, both messages and every tree node share one chosen complete reset. We prove upper bounds of \(2^{64},2^{128},2^{128}\) compression evaluations for finding collisions with 512-, 768-, and 1024-bit digests, respectively, plus constant preparation and finalization costs. - In both versions of \textbf{WChain}, the message expansion preserves invariant sets and admits sequences of expanded blocks with periods one, three, and six over all prescribed steps. - On a set of 256 message blocks, \textbf{Cuishen}'s message expansion acts as a cyclic shift of eight binary coordinates throughout all 64 rounds. With the same initial chaining register and counter, these blocks give XOR differences between round keys with periods dividing eight. The stated evaluation budgets for \textbf{CHIME-512} and \textbf{CHAMP} give success probabilities greater than \(0.39\).

Middle-Product LWE (MP-LWE) can inherit hardness from Ring-LWE over many number fields. Peikert and Pepin developed a direct reduction using field traces. Njah Nchiwo and Pellet-Mary (NP26) proved polynomial loss for the route through Polynomial-LWE under an additional condition on the defining polynomial. Recently, Pellet-Mary and Xia (PX26) unified both routes and proved polynomial loss for defining polynomials with polynomially bounded coefficients under suitable modulus conditions. We analyze Peikert and Pepin's trace reduction for monic irreducible integer polynomials $f$ of degree $n\ge2$ with coefficients of absolute value at most a fixed $B\ge1$. First, when the prime modulus satisfies $q\nmid[\mathcal O_{\mathbb{Q}(\theta)}:\mathbb{Z}[\theta]]$, where $\theta$ is a root of $f$, we prove the existence of multipliers with primal loss $O_B(n\sqrt{\log n/\log\log n})$ and dual loss $O_B(n^2)$. The multipliers have polynomial-size descriptions and serve as advice. Second, whenever the polynomial class is nonempty, every $Q\ge21$ admits a prime $q\in[Q,2Q]$ for which the index condition holds for at least a $1-O_B(n\log n/Q)$ fraction of the polynomials. At the same prime, we prove the same lower bound when counting the distinct number fields defined by these polynomials. Both coverage bounds tend to one as $n\to\infty$ if $Q/(n\log n)\to\infty$. Third, we prove that the trace reduction can match the linear noise bounds achieved by NP26's reduction through Polynomial-LWE. For the same defining polynomial, Ring-LWE variant, and MP-LWE parameters, a suitable trace multiplier exists whose linear noise amplification is no larger than that achieved by NP26's multipliers.

Recent works have studied Byzantine agreement (BA) in the mixed-fault model with resilience threshold $n>2t+r+s$, where $n$ is the number of parties, $t$ is the number of Byzantine parties, $r$ is the number of receive-faulty parties, and $s$ is the number of send-faulty parties. In particular, Feng et al.~(ASIACRYPT~2025) proposed a BA protocol with optimal resilience, expected asymptotically quadratic communication complexity, and expected constant round complexity. However, existing BA protocols guarantee a meaningful output $v$ only when all parties hold the same input $v$. Such a guarantee is insufficient for efficient construction of atomic broadcast protocols, leaving efficient atomic broadcast in the mixed-fault setting as an open problem. In this paper, we present the first atomic broadcast protocol (UABC) with optimal resilience in the mixed-fault model. In addition, our protocol achieves communication complexity $\mathcal{O}(n\ell+n^2\lambda^2)$ when $t=\Theta(n)$, where $\ell$ is the input size and $\lambda$ is the security parameter. This complexity is asymptotically optimal for moderately large $\ell$, namely when $\ell\ge n\lambda^2$. At the core of our design is an undead verifiable information dispersal (UVID) protocol, which allows an input to be efficiently dispersed and later reconstructed in the mixed-fault setting. Leveraging UVID together with the undead multi-valued consensus (ASIACRYPT~2025), we further construct a new primitive called weak undead multi-valued validated Byzantine agreement (wUMVBA) and its optimized variant (Opt-wUMVBA). Unlike standard multi-valued validated Byzantine agreement, wUMVBA and Opt-wUMVBA guarantee that the output is either a meaningful value satisfying the validity predicate or $\bot$. Moreover, the probability of outputting $\bot$ is at most $(t+s)/n$. Finally, by leveraging Opt-wUMVBA, we obtain our optimal atomic broadcast protocol for the mixed-fault setting.

The rapid expansion of quantum computing threatens the security foundations of classical public-key cryptography, including RSA and ECC, both vulnerable to Shor's algorithm. For the automotive industry, where secure communication underpins critical functions such as over-the-air (OTA) updates, secure boot, firmware signing, PKI validation, and vehicle-to-everything (V2X) connectivity, this threat demands early and informed migration planning. This paper presents a cross-platform performance evaluation of NIST-selected and candidate Post-Quantum Cryptography (PQC) algorithms integrated into the Transport Layer Security (TLS) protocol, in both standalone and hybrid (classical + PQC) configurations. Signature schemes CROSS, MAYO, SPHINCS+ (SHA and SHAKE variants), ML-DSA, and FALCON are evaluated alongside key encapsulation mechanisms including FrodoKEM, BIKE, and ML-KEM. Testing spans two representative platforms: a resource-constrained Raspberry Pi 4B (Broadcom BCM2711, 4GB RAM) representing embedded automotive ECUs, and an Ubuntu-based Intel Core i5 system representing backend or gateway infrastructure. Execution time, memory consumption, and CPU core utilization are measured across algorithm-KEM combinations to characterize real-world feasibility. Results indicate lattice-based schemes offer a strong balance of performance, interoperability, and long-term assurance suited to V2X and PKI-heavy communication, while compact signature schemes such as MAYO and FALCON better serve resource-constrained operations like secure boot and firmware signing, where verification speed and low memory footprint are prioritized over frequent key exchange. The study further identifies a critical dependency of PQC feasibility on 64-bit architecture, highlighting the limitations of legacy 32-bit automotive chipsets that lack dedicated cryptographic accelerators. These findings offer practical, use-case-specific guidance for automotive OEMs and suppliers navigating the transition from classical to quantum-resistant cryptography, supporting risk-informed decisions across onboard and offboard vehicle communication architectures.

We construct the first non-trivial weighted threshold encryption scheme with silent setup. The CRS and each public key consists of O(W) group elements, where W is the maximum committee weight. Both the weight assignments and the threshold for decryption can be dynamically chosen at encryption time. Each partial decryption is a single G1 element computed non-interactively with one scalar multiplication, independent of the party's weight. The CPA ciphertext is two G_1 elements, improving upon the shortest known unweighted scheme, and CCA security costs two additional field elements. We prove security in the generic bilinear group model.

Polynomial commitment schemes (PCSs) allow a prover to commit to a polynomial and later prove its evaluations succinctly. Among hash-based constructions, FRI (Ben-Sasson et al., ICALP 2018) and its follow-up works achieve polylogarithmic proofs by recursively ``folding'' Reed-Solomon (RS) codes. However, their concrete evaluation costs remain relatively high, as the first few folding rounds operate on the largest codewords and dominate the prover work. We present \emph{ReedWeave}, a Reed-Solomon PCS that successfully incorporates interleaving with folding, achieving the best of the two worlds. ReedWeave decomposes a degree-$d$ polynomial into $m$ smaller components and commits to their RS encodings over a common domain. Under our novel decomposition, a random linear combination of these codewords is exactly an $m$-ary folding. At a high level, ReedWeave starts with an $m$-ary folding, followed by standard binary folding as in FRI. The prover costs are substantially reduced in the sense that at the very beginning it suffices to do interleaved-RS encoding rather than standard RS encoding. That is, we reduce prover costs from $\mathcal{O}(d \log d)$ to $\mathcal{O}(d\log(d/m))$ for constant code rate while maintaining efficient polylogarithmic verification. Moreover, our approach essentially works for arbitrary $m$, relaxing the smoothness requirements of the underlying fields by a multiplicative factor of $m$. We benchmark our Rust implementation over Goldilocks using 32 threads and targeting 100-bit security. At $d=2^{24}$, $\rho=1/4$, and $m=64$, the DEEP variant commits in $475.0$ ms, opens in $111.6$ ms, verifies in $2.07$ ms, and produces a $594.7$ KiB proof. Compared with FRI (ICALP 2018), commitment, opening, and verification are $6.9\times$, $51.5\times$, and $4.2\times$ faster, respectively. Against STIR (CRYPTO 2024), the corresponding speedups are $2.9\times$, $68.5\times$, and $2.1\times$. Its proof is only $0.69\times$ the size of FRI's and $2.31\times$ that of STIR's.

Range proofs are a fundamental building block of lattice-based proof systems. Existing approaches relying on standard Johnson-Lindenstrauss (JL) struggle to provide succinctness: unstructured JL incurs linear verifier complexity, while structured JL introduced in RoK and Roll [ASIACRYPT'25] produce large projection vectors that need to be sent in costly committed form. For a witness of dimension $m$ and a security parameter $\lambda$, the JL projection vector is $O(\lambda),$ but the projection matrix is $O(\lambda m)$. Structured JL can be represented in $\widetilde O(\rho \lambda^2)$, but the resulting projection length grows to $\widetilde O(m / \rho)$ for any trade-off parameter $\rho > 1$. \hspace{5mm} In this paper, we introduce Tensor Train Random Projection (TTRP) to lattice-based cryptography, offering a ``best of both world" structured JL variant. The Tensor Train (TT) matrix representation drops to $\widetilde O(\lambda)$, while maintaining the projection vector at $O(\lambda)$. \hspace{5mm} We show that TTRP can be seamlessly integrated into proof systems by linearizing the well-formedness of the projection with the sum-check protocol. Concretely, using TTRP + sum-check as a drop-in replacement for existing range proof techniques yields an approximate shortness check with $O(\lambda \log m (\log\log m)^2)$ verifier complexity and proof size around $4$ KB for relevant parameter settings.

Fully anonymous secret-sharing schemes ensure two properties at once: for any fixed secret, the combined shares of every unauthorized set of participants are uniformly random, and every authorized set can reconstruct the secret exactly using only the share values, without needing to know which participant holds which share or in what order the shares appear. It was previously open whether such schemes exist for nontrivial exact-threshold parameters 2 < t < n. For the smallest previously open threshold, t= 3, we give, for every n≥4, an explicit fully anonymous scheme for one-bit secrets, with 2⌈log n⌉-bit shares and a perfect reconstruction algorithm running in poly(log n) time. The next result, found by ChatGPT, shows that for every 1 ≤t ≤n there exists a fully anonymous perfect (t,n) threshold secret-sharing scheme for one-bit secrets, in which each share has length O(tlog n) bits. The proof is purely existential and does not provide an efficient construction. Moreover, ChatGPT identified a simple construction of a fully anonymous perfect scheme for every access structure A; if A contains ℓ authorized sets, then each share consists of ℓ2 bits. The authors subsequently verified and streamlined the proofs on their own and take full responsibility for their correctness.

We study affine and linear equivalence of functions $F,G:\mathbb{F}_q^n\to\mathbb{F}_q^m$. We present practical equivalence algorithms that handle arbitrary functions (any algebraic degree, permutations and non-permutations) and are particularly effective on structured instances with nontrivial self-equivalences, covering most cryptographically relevant cases. We also give a dedicated algorithm for computing generators for the group of self-equivalences $(A_1,A_2)$ satisfying $A_2\circ F = F\circ A_1$, for which no comparably efficient general method was previously available.

We formalize and construct $sparse$ arguments of knowledge, where given a length $N$ witness that contains $n$ non-zero values the prover time is $O(n) \circ o(N)$. In particular, we achieve a sparse argument of knowledge for the customizable constraint system relation, which generalizes circuit-satisfiability. We achieve this by first utilizing $sublinear$ lookup arguments to provably select only the subset of the constraint system that touches the non-zero entries of the variable assignment, and then running a standard argument of knowledge with mild qualifications. Our resulting sparse argument of knowledge is publicly verifiable and supports a universal and updatable setup. It features an $O(N \log N)$ preprocessing phase, an $O(n \log n)$ prover time, and an $O(1)$ verifier time, improving on the prior $O(n \log^2 n)$ and $O(n \log N)$ prover time.

We propose an efficient threshold mechanism that is well suited for certain hash-based signatures. Our proposal has a number of compelling features: • The final signature assembled from a quorum of signature shares has the same format as a non-threshold hash-based signature. In particular, the verifier is unaware that the signer is thresholdized. Moreover, we can add and remove parties and change the threshold without changing the public key. • Our framework can be used to thresholdize one-time signature schemes, such as Winternitz, and a few-time schemes, such as XMSS, HORS, FORS, and PORS+FP. • The public key and the signatures reveal nothing about the number of parties $n$ or the threshold $t$. • An instantiation of our framework scales well to a large number of parties $n$ and a large threshold $t$. One limitation of the framework is that it does not support an efficient distributed key generation protocol (DKG). Another limitation is that the framework does not directly apply to SLH-DSA. It is primarily designed for the Winternitz, XMSS, and FORS schemes.

We introduce BitZ, a hash-based Polynomial Commitment Scheme (PCS) for committing to multilinear polynomials $\mathbf{f}$ with coefficients in an arbitrary finitely generated ring $S$, e.g.\ a finite field $\mathbb{F}$, the integers $\mathbb{Z}$, a cyclotomic ring, etc. Moreover, given another arbitrary ring $R$ and a ring homomorphism $\psi:S\to R$, BitZ then proves evaluation claims over $R$ for the polynomial $\psi(\mathbf{f})$. BitZ's costs depend almost exclusively on the number of bits in the coefficients of $\mathbf{f}$, and not on $S$, $R$ or $\psi$. Moreover, BitZ provides range checks (or more generally, bit-size checks) essentially for free. BitZ can thus be used as a PCS in essentially any proof system. We do so to build a SNARK, called BitZ-SNARK, for integer polynomial constraints, following the fingerprinting technique of Campanelli and Hall-Andersen, where one commits over $\mathbb{Z}$ and proves the constraints over a random prime field $\mathbb{F}_q$, i.e. BitZ is deployed with $S=\mathbb{Z}$, $R=\mathbb{F}_q$, and $\psi$ reduction modulo $q$. BitZ applies equally to other ring-based proof systems, or field-based ones. To commit to $\mathbf{f}$, BitZ first decomposes $\mathbf{f}$ into a string of bits, and then commits to it over a binary field $\mathbb{F}_{2^{\nu}}$, in packed form. The scheme then proves the linear claim on $\psi(\mathbf{f})$ over the arbitrary ring $R$, even though it committed to the bits forming $\mathbf{f}$ over a binary field. We implement BitZ-SNARK and use it to prove, among others, SHA-256 hashing followed by ECDSA signature verification; RSA modular exponentiation and Poseidon hashing; integer multiplication; and SHA-256 hashing followed by multiplication modulo $2^{32}$, consistently obtaining better performance than prior approaches on most tasks. As an example, we achieve a throughput of $9$ million proved 32-bit integer multiplications per second on a MacBook Air M5 24 GB (10 threads, CPU-only) with proof sizes under $200$ kB. We prove a SHA-256 hash of a $2$ kB ($2^5$ compressions) message followed by a P-256 ECDSA signature verification with $32$ ms and $3.1$ ms prover and verifier time, respectively, and with a proof of $65$ kB, single-threaded. With $10$ threads the times are $17$ ms and $3.7$ ms.

Adaptive reprogramming is a central tool for proving security in the quantum random oracle model (QROM). Recently, it has been extended to the setting when an oracle-dependent advice is in presence. However, the existing result is restricted to classical advice, and addresses only a single reprogramming. Extending it to n reprogrammings through naive hybridization yields a loss that is linear in the number of reprogrammings. In this paper, we establish an adaptive reprogramming theorem that accommodates quantum advice, and has a tighter overall security loss that only scales in the cubic-root of n, with an attack that matches the number of queries required in order to reach constant advantage. Using our reprogramming theorem, we provide improved time-space tradeoff bounds for PRG security of random oracles, and an IND-CPA security proof of salted pseudo one-time pad, in the quantum advice setting. Along the way, we also identify and prove a folklore lemma about indistinguishability of two oracles, which may be of independent interest. As another application, we provide a generic security analysis of Fiat-Shamir and hash-and-sign signature schemes, in QROM with quantum advice. We do so via a two-step modular analysis, where in the first step we perform a generic UF-CMA to UF-NMA reduction using our reprogramming theorem, and in the second step we provide a characterization of when such a scheme satisfies UF-NMA security, which we then use to discuss security of several signature schemes in this model.

The NIST SP 800-208 eXtended Merkle Signature Scheme (XMSS) profile XMSS-SHAKE256_10_256 repeatedly invokes SHAKE256 primitives, making field-programmable gate array (FPGA) accelerator latency sensitive to Keccak permutation time and absorb/finalization-control overhead. Established round unrolling reduces permutation-side latency but leaves residual controller work. We propose SAFE Final-Block Construction (SAFE FBC), combining guarded SHAKE256-rate-aware eligibility, direct eligible final-block construction, and sequential-finalization bypass without modifying Keccak. A controlled 12-configuration study crosses four controller/finalization organizations with one-, two-, and three-round-per-cycle datapaths over nine XMSS-oriented cases: 96-byte F and pseudorandom-function (PRF) inputs, 128-byte H and PRFkeygen inputs, and selected message-hash cases around the SHAKE256 rate boundary. At every fixed depth, SAFE FBC reduces aggregate L2-final latency by 13 cycles versus the Structural Controller Decoupling (SCD) baseline; L2-final spans the first accepted AXI input beat to the final accepted AXI output beat. At three rounds per cycle, aggregate latency falls from 305 to 292 cycles, with no case regressing. F and ordinary PRF show the largest per-call gain, from 30 to 25 cycles (16.67%). Component measurements localize the saving to absorb/finalization control; Keccak permutation latency, squeeze latency, and input-transfer span remain unchanged. SAFE FBC complements unrolling, trading latency for substantial lookup-table/slice growth with very small flip-flop overhead.

Robust asynchronous threshold Schnorr signatures enable honest parties to complete signing despite malicious behavior and network delays. To reduce online latency, these schemes typically follow an offline–online paradigm. The parties prepare batches of shared nonces in the offline phase and consume them to generate signatures online. In high-throughput constructions such as SPRINT (Benhamouda et al.~Eurocrypt 2024), super-invertible matrices are used to extract multiple nonces and their corresponding commitments from a single execution of the nonce-generation protocol. However, the associated group operations incur substantial computational overhead. We identify several computational bottlenecks in SPRINT and present $\mathsf{DASH}$, a suite of robust asynchronous threshold Schnorr signature protocols that substantially improve computational efficiency while retaining SPRINT’s amortized linear communication cost. Our contributions are threefold. First, we propose distributing the group computations involved in nonce extraction among the parties. This reduces the amortized computational cost from $\mathcal{O}(\log n)$ to $\mathcal{O}(1)$ group operations per signature per party. To enable this distributed computation, we employ a batching technique that allows each dealer to distribute $L$ nonce polynomials simultaneously. Second, we introduce an efficient batched share-verification procedure that jointly checks shares of all $L$ polynomials. For concrete parameters, this can accelerate share verification by a factor of $40-60$. We also introduce a simple agreement protocol via player elimination, which could be of independent interest. Finally, under a stronger honest-majority assumption, we develop a packed two-stage online reconstruction protocol that enables parties to reconstruct signatures through error correction. This eliminates the need for signature-share verification, and consequently, avoids the expensive group operations performed by the aggregator in SPRINT. Surprisingly, even in the worst case, our $\mathsf{DASH}$ protocols preserve the same asymptotic amortized computation and communication costs, provided that $L \gg n\log n$. %We prove the security of all $\mathsf{DASH}$ variants in the random oracle model under the standard discrete logarithm assumption.

Key generation in ML-KEM (CRYSTALS-Kyber) samples a short secret from a centered binomial distribution (CBD) and immediately transforms it with the number-theoretic transform (NTT). Each execution draws fresh randomness, so an attacker obtains a single trace and cannot average. We show that one power trace of the optimized pqm4 implementation on an Arm Cortex-M4 suffices, and that the two operations leak complementary information. The CBD sampler stores each coefficient as a signed $16$-bit two's-complement word, which reveals its sign almost without error but too little about its magnitude to yield long error-free hint sets. The missing magnitude leaks in the subsequent NTT, where coefficients are multiplied by public twiddle factors. Used as hints in a primal lattice attack, the combined leakage reduces the estimated BKZ block size for ML-KEM-768 from $624$ to $129$, corresponding to $2^{182.2}$ and $2^{37.7}$ in the core-SVP model. A control experiment shows that the same NTT code leaks the Hamming weight of a near-uniform operand as strongly as that of the secret, yet reveals almost nothing about its value. What makes a coefficient vulnerable is how few values it can take, not how small it is. That points to a countermeasure inside the CBD sampler. Each sample $v$ is stored as a random representative $\widetilde v = v + rq$ of its residue class, with $r$ nonzero, so the NTT and all later code run unchanged. This $q$-randomization drives the sign leakage to the noise floor, reduces the NTT magnitude leakage by $4.5\times$, and raises the block size from $129$ back to $611$, about four bits of estimated security lost instead of more than $140$. The sampler grows by $937$ bytes of firmware.

The Learning With Errors (LWE) problem provides a conservative and well-established security foundation for lattice-based cryptography, while Learning With Rounding (LWR) improves bandwidth efficiency through deterministic rounding. However, the rounding noise in LWR is inherently correlated with the hidden linear term, preventing tight and sample-preserving reductions to standard LWE for polynomial moduli. Prior work on the Learning With Quantization (LWQ) problem established a tight security reduction from LWE, where standard additive noise is intrinsically replaced by quantization error. We specialize this framework by explicitly instantiating the quantization lattice as a scaled integer lattice. Under this geometric choice, specifically utilizing aligned power-of-two moduli, we derive the exact finite-support error distribution and construct an explicit bijection between transmitted split samples and normal-form LWE samples. These ingredients yield \(\mathsf{MAMBA\text{-}Frost}\), a plain LWQ-based key encapsulation mechanism that seamlessly pairs unstructured LWE security with quantization-based compression. Because its effective error stems entirely from public dithered quantization, \(\mathsf{MAMBA\text{-}Frost}\) operates strictly with hardware-friendly power-of-two arithmetic. Furthermore, the construction employs an \(E_8\)-coded message embedding to optimize the correctness margin without altering the underlying LWQ hardness argument. We instantiate \(\mathsf{Frost}\) at NIST security levels 1, 3, and 5 and provide a complete software implementation. Its power-of-two design realizes the core arithmetic with shifts and masks, keeping the implementation simple and amenable to constant-time engineering. At level 1, \(\mathsf{Frost\text{-}128}\) reduces the combined public-key and ciphertext size by about \(40\%\) compared with \(\mathsf{FrodoKEM\text{-}640}\) and by about \(8\%\) compared with \(\mathsf{SCloud}^{+}\text{-}128\). On an AVX2 platform, \(\mathsf{Frost\text{-}128}\) achieves speedups of \(2.3\times\), \(1.8\times\), and \(1.5\times\) for key generation, encapsulation, and decapsulation over \(\mathsf{FrodoKEM\text{-}640}\), and \(2.1\times\), \(1.5\times\), and \(1.3\times\) over \(\mathsf{SCloud}^{+}\text{-}128\).

We give a sharper bound on the error introduced by replacing a random permutation oracle with Carolan’s compressed permutation oracle. Building on Rosmanis’s representation-theoretic approach, we represent exact permutation states in the compressed oracle’s database space, allowing a direct comparison of the two query operations. For a uniform permutation on N points, this comparison bounds the soundness error by 4q/√N after q ≤ N/4 queries. As the main application, we obtain tight query complexity for constant success probability in sponge preimage and collision search by substituting this bound into Carolan’s search reductions. The same analysis improves bounds for the one-more problem and cycle finding, and gives tight query complexity for constant success probability in keyless Davies–Meyer collision search

We give a lattice identity-based signature scheme from annular NTRU trapdoors and Fiat--Shamir with aborts (FSwA). Countered hashing maps each identity to its first invertible DLP/NTRU syndrome $a$. Extraction returns a short witness to $s_0+s_1h=a\bmod q$, and signing normalizes this relation to a fixed-target two-response equation with public commitment recovery. Gärtner's iterative rejection method fits naturally into this signing layer: processing the challenge monomials separately reduces the Gaussian mask width and expected signing attempts, yielding shorter signatures. We report three parameter sets whose signing layer is calibrated against NIST security categories 2, 3, and 5, with fixed signature sizes of $8486$, $11309$, and $12727$ bytes, respectively.

Folding is a core technique in building efficient code-based polynomial commitment schemes with polylogarithmic proof size and verification. To date, there are two families of linear error-correcting codes that have been known to allow folding, i.e., Reed-Solomon (RS) codes and foldable codes. However, neither admits optimal proximity gaps, which constitutes a fundamental bottleneck in the resulting proof sizes. In this work, we give the first folding scheme that enjoys optimal proximity gaps. Specifically, we construct IOPPs (interactive oracle proofs of proximity) for both folded RS (FRS) codes and univariate multiplicity (UM) codes, which achieve optimal proximity gaps $1-R-\varepsilon$ as shown in a recent work of Goyal and Guruswami (STOC 2026), where $R$ is the code rate and $0<\varepsilon<1-R$. Our key observation is that the typical even/odd folding commutes with polynomial reduction for suitably paired moduli, enabling consistency checks via the Chinese remainder theorem. This implies a new generic folding framework that recovers the FRI folding for RS codes and enables efficient folding for FRS and UM codes. We further refine the optimal proximity gap analysis for FRS and UM codes, yielding tighter concrete soundness bounds. Our IOPPs have $O(N)$ prover time and oracle proof size, together with $O(\lambda\log{N})$ query complexity and verification time, where $N$ is the block length and $\lambda$ is the security parameter. These bounds match the asymptotic complexity of FRI while attaining optimal proximity gaps and allowing smaller underlying fields at the same security level. E.g., a $128$-bit field suffices for $100$-bit security.

Multiparty Private Set Union (MPSU) allows multiple parties to compute the union of their private sets while revealing no additional information beyond the prescribed output. Existing practical MPSU protocols typically manipulate individual elements and rely on a distributed shuffle to hide element ownership, introducing an $O(n)$ round-complexity bottleneck. We present United, a shuffle-free MPSU framework based on a new data-structure abstraction, Oblivious Insert-Only Invertible Sketches (OIIS). Rather than anonymizing an element-wise intermediate representation, the parties directly construct a protected symmetric sketch of the union. Conditional oblivious insertion ensures that each distinct union element is inserted exactly once while hiding the insertion condition and modified locations. We provide two realizations of OIIS. Our HE-based construction instantiates OIIS with a standard Invertible Bloom Lookup Table protected by multi-key partially homomorphic encryption, while our MPC-based construction uses additive secret sharing and introduces a new row-local power-sum OIIS technique for efficient conditional insertion. We implement and evaluate both constructions. Across the evaluated configurations, our MPC-based construction achieves up to $3.10\times$ lower runtime in LAN settings, while our HE-based construction achieves up to $2.73\times$ lower runtime in WAN settings compared with prior MPSU protocols.

The security of RSA is generally understood to be based on the complexity of factoring, and key size parameters are extrapolated from the general number field sieve (GNFS). However, this may not accurately represent RSA security in practical scenarios. An under-appreciated 2007 algorithm of Joux, Naccache, and Thomé allows an attacker to forge RSA signatures after temporary access to a raw RSA signing/decryption oracle in time close to the *special* number field sieve (SNFS) without factoring the key. We implement and run this algorithm for 1024-bit RSA. In total, the attack took 1380 CPU core-years over five calendar months, and made $2^{32}$ oracle queries. Most of this time is precomputation; after the precomputation the attacker can forge any signature of choice, offline, in 180 core-years. We carried out our attack using a hardware security module (HSM) as the signing oracle, thus demonstrating the ability to impersonate the HSM through black-box API interactions, without exfiltrating the key. Blind RSA schemes also provide such a signing oracle. Extrapolating our empirical running times to larger key sizes, we conclude that the concrete security of RSA with a signing oracle should be 15 to 30 bits lower than the factoring-based security estimates for the 1024-bit to 4096-bit RSA parameters that are common in practice. Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model. This highlights a gap in current RSA-type security assumptions, and gives classical cryptanalytic evidence in favor of moving away from RSA entirely during the current post-quantum transition.

Covert communication can be achieved without anamorphic encryption.

We analyze a recently published construction of redactable blockchains based on multivariate polynomial equations. We show that its public integrity conditions reveal sufficient algebraic structure to recover the relevant private evaluation points efficiently. As a consequence, the blockchain unauthorized redaction problem reduces to univariate root finding over a finite field followed by solving a linear system. We also discuss an alternative attack based on linearization.

Modern cryptocurrency wallets use Schnorr signatures together with public, deterministic key derivation: by repeatedly rerandomizing a single master public key, an unlimited number of public keys for incoming payments can be derived without access to secret data. Moreover, some wallets support multi-signature schemes such as MuSig2 for optionally aggregating derived public keys from $n$ distinct parties into "$n$-of-$n$" public keys, so that funds received on such aggregated keys can be spent only when authorized by all $n$ parties. However, these advanced key-management techniques stretch the underlying cryptographic schemes beyond the guarantees provided by existing security proofs. Although deterministic Schnorr wallets and MuSig2 have each been proven secure in isolation, the provable security of their composition---despite its deployment in wallets---has not been established thus far. The goal of this work is to narrow this gap between theory and practice. We provide the first formal security analysis of the joint use of single-signer Schnorr signatures and MuSig2, both under rerandomization and in deterministic wallets. First, we introduce the notion of a (rerandomizable) joint-signature scheme, in which an honest signer uses the same secret key for single-signer signatures and multi-signatures. Within this model, we prove tight security of Schnorr signatures plus MuSig2 under the algebraic one-more discrete logarithm (AOMDL) assumption in the combination of the algebraic group model (AGM) and the random oracle model (ROM). Finally, we provide a formal model of deterministic wallets with joint-signature schemes and show that Schnorr plus MuSig2 remains secure under public, deterministic key derivation.

Deep Neural Networks (DNNs) have emerged as a cornerstone of modern AI systems, rendering their internal parameters highly valuable intellectual property. Consequently, the security of DNNs against model extraction attacks has garnered significant research attention. Recent cryptanalytic extraction methods have demonstrated that recovering DNN parameters is feasible in polynomial time, both when attackers have exact logit access and in the more restrictive hard-label setting. However, a critical limitation of these state-of-the-art frameworks is the assumption that the attacker possesses a complete architecture knowledge of the target network, including the exact depth and width of the hidden layers. To date, the efficacy of parameter extraction algorithms under limited architecture knowledge remains unexplored. This paper demonstrates that in the limited architecture knowledge scenario, existing cryptanalytic attacks suffer from neuron omission, which causes subsequent parameter recovery to fail entirely. To address this, we propose a general adaptive extraction workflow integrated with a novel error detection algorithm capable of identifying missing neuron anomalies and successfully recovering the correct parameters. Through experiment, we achieve the first successful extraction of a four-hidden-layer ReLU network (comprising over 1.1 million parameters) trained on CIFAR-10 under the limited architecture knowledge setting, while maintaining a 100% error detection recall.

We present the first polynomial-time attacks against certain parameter choices of the low-dimensional vector representation (LDVR) problem, introduced by Crites, Katz, Komlo, Tessaro, and Zhu (CRYPTO '25) to prove the adaptive security of FROST in the Algebraic Group Model. Building on work by Crites and Stewart (CRYPTO '25), they also show that every attack against LDVR directly yields an adaptive attack—i.e., one leveraging adaptive corruptions—against any threshold Schnorr signature that exposes to the attacker the values $g^{\mathrm{sk}_i}$ for the secret-key shares $\mathrm{sk}_i$ held by the signers, where $g$ is a generator of the underlying group. This class of protocols includes FROST (Komlo and Goldberg, SAC '20), Sparkle (Crites, Komlo, and Maller, CRYPTO '23), Lindell's three-round protocol (CiC '24), along with other masking-free protocols. Consequently, our results give the first polynomial-time adaptive attacks against a class of practical threshold signatures. Our attacks require a large, but still polynomial, number of signers: asymptotically, we require $n = \Theta(\log^2 p)$ signers and corrupt $t_c = \Theta(\log p)$ of them. For the prime-order subgroup of Curve25519, concrete and optimized instantiations of our attack require $n=5020$ signers and corrupt $204$ of them. This exceeds the signer counts commonly encountered in practice, but falls within the scenarios considered by NIST's call for threshold signatures. At the theoretical level, our results also yield a non-artificial separation between static and adaptive security based on a real-world multi-party protocol. Our results arise from a new reduction from LDVR to structured subset-sum problems determined by the evaluation points of the polynomial used to secret-share the signing key. We further show that allowing these evaluation points to be chosen adversarially can lead to substantially more efficient attacks.

Over the last fifteen years, side-channel analysis (SCA) against implementations of both classical and post quantum cryptography has undergone a quiet but fundamental change of paradigm: from treating leakage as evidence to be combined with an algorithm’s structure into a system of exact equations to be solved, to treating it as evidence to be combined into a joint probability distribution to be queried. This survey gives a systematic account of that evolution through four paradigms: Algebraic SCA (ASCA), which encodes leakage as hard Boolean or algebraic constraints and solves the resulting system with SAT or Gröbner-basis solvers; Tolerant/weighted Algebraic SCA (TASCA), which relaxes hard constraints into pseudo-Boolean costs and recovers a maximum-a-posteriori key via combinatorial optimization; Soft Analytical SCA (SASCA), which retains leakage as full likelihood functions attached to a factor graph and approximates the posterior with loopy belief propagation; and Exact SASCA (ExSASCA), which replaces the uncertified approximation of loopy belief propagation with exact inference on a knowledge-compiled tractable probabilistic circuit. Our central contribution is a single Bayesian factor-graph formulation under which all four paradigms are shown to be different representations of the same leakage-augmented joint distribution combined with different inference queries and solvers: we prove, in a precise but lightweight sense, that ASCA is the zero-temperature limit of TASCA, that TASCA is a maximum-a-posteriori restriction of SASCA’s model, and that ExSASCA is SASCA with its approximate solver replaced by an exact one on the identical graphical model. Building on this formulation, we develop a taxonomy that organizes the literature along a representation axis (hard, weighted, probabilistic) and a solver axis (satisfiability, combinatorial optimization, approximate message passing, exact tractable inference), survey the concrete attack literature in each paradigm on both AES and NTT-based post-quantum schemes (Kyber, Dilithium, Falcon/FN-DSA), and analyze the computational and security trade-offs of each approach, including its implications for what a security evaluator may soundly conclude from a failed attack. We close with open problems at the current frontier of tractable probabilistic inference for cryptographic implementation security.

Falcon offers compact signatures and well-studied mathematical security, but its side-channel security remains a critical challenge. In particular, its floating-point Gaussian sampler constitutes a major source of side-channel leakage, while protecting it efficiently is difficult because of its reliance on floating-point arithmetic. However, existing attacks targeting the sampler under realistic noisy-leakage conditions typically require thousands of traces and are evaluated on unoptimized implementations. In this paper, we present a new attack on Falcon's sampler, which reduces the number of required traces by more than two orders of magnitude compared with prior attacks under realistic noisy-leakage conditions and works on both unoptimized (\texttt{-O0}) and highly optimized (\texttt{-O3}) builds. Our attack targets the floating-point Gaussian centers $\mu$ used by the sampler at the recursion leaves of the \texttt{ffSampling} procedure. Specifically, it exploits signed-exponent leakage arising when $\lfloor\mu\rfloor$ is converted from an integer back to floating-point representation, as well as the weaker sign-only leakage. Signed-exponent leakage places the integer part $\lfloor\mu\rfloor$ of each center in one of $17$ signed power-of-two intervals, whereas sign-only leakage divides it into two intervals according to its sign. We propose CB-MLE, which uses gradient descent to obtain an estimate $f^\star$ whose computed Gaussian-center classifications are consistent with the observed classifications under the profiled confusion matrix. An ISD-style search tests subsets of the more reliable coefficients in $f^\star$ with LLL/BKZ on the corresponding reduced NTRU lattices to recover the full key. We collect power traces from the Falcon implementation in the PQClean library running on an ARM Cortex-M4 microprocessor. Our Gaussian-center classifier achieves single-trace classification accuracies of $0.9997$ and $0.884$ at the \texttt{-O0} and \texttt{-O3} optimization levels, respectively, confirming exploitable signed-exponent leakage from the Gaussian centers. Using these classification results, the full attack recovers Falcon-$512$ keys with success rates of $100\%$ from $20$ signatures at \texttt{-O0} and $100\%$ from $56$ signatures at \texttt{-O3}. For Falcon-$1024$, it reaches $100\%$ from $21$ signatures at \texttt{-O0} and $100\%$ from $100$ signatures at \texttt{-O3}.

Let $C_0$ be the least constant such that, for every finite family of vectors $u_1,\ldots,u_n\in\mathbb C^d$ and independent finitely supported real random variables $\xi_i$, there are values $\varepsilon_i\in\operatorname{supp}(\xi_i)$ satisfying $\|\sum_{i=1}^n(\varepsilon_i-\mathbb{E}[\xi_i])u_i u_i^*\| \leq C_0\|\sum_{i=1}^n\mathrm{Var}[\xi_i](u_i u_i^*)^2\|^{1/2},$ where $\|\cdot\|$ denotes the operator norm. This rank-one matrix discrepancy formulation generalizes the signing formulation of the Kadison--Singer problem [KS59], resolved by Marcus, Spielman, and Srivastava [MSS15b]. Let $C_1$ be the least constant such that, for every $\epsilon>0$ and every finite family in $\mathbb C^d$, in every dimension $d$, satisfying $\sum_{i=1}^n u_i u_i^*=I$ and $\max_{i\in[n]}\|u_i\|^2\leq\epsilon$, there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i u_i u_i^*\|\leq C_1\sqrt\epsilon.$ Taking the $\xi_i$ to be independent symmetric signs gives $C_1\leq C_0$, since $\|\sum_{i=1}^n(u_i u_i^*)^2\|\leq\epsilon$ under these hypotheses. The general formulation allows arbitrary finite real supports and does not require $\sum_{i=1}^n u_i u_i^*=I$. Kyng, Luh, and Song [KLS20] proved $C_0\leq4$. We prove $2\leq C_1\leq C_0\leq2.176$. This improves the bounds $\sqrt2\leq C_0\leq3$ of Xie, Xu, and Zhu [XXZ21]. We conjecture that the optimal constant is $C_0=2$.

Traditional secure multiparty computation (MPC) protocols assume a fixed set of participants throughout the computation. Dynamic MPC (DMPC) relaxes this assumption by permitting parties to join or leave during the process. However, practical deployment of DMPC in Internet settings favors tolerating asynchrony and achieving guaranteed output delivery (GOD). Recently, AD-MPC [CCS 2025] introduced an asynchronous DMPC (ADMPC) achieving this goal, but its reliance on per-epoch preprocessing and masking randomness incurs substantial concrete overhead. In this paper, we present Continuum, a concretely efficient ADMPC protocol with GOD. We introduce an aggregated hand-off protocol that ensures transfer consistency across epochs while eliminating per-epoch masking randomness, and a batch multiplication protocol based on the BGW paradigm that defers degree reduction to the hand-off phase and aggregates verification for all multiplications into succinct proofs. Together, these protocols enable a non-interactive computation phase with interaction concentrated in an efficient hand-off phase, overcoming the primary concrete inefficiencies of prior ADMPC designs. We implement Continuum and evaluate its performance on up to 128 geographically distributed servers. In experiments on 22 servers with circuits of depth 6 and width 100, Continuum reduces linear-gate transfer latency from 76.60s to 15.13s (80% reduction) and multiplication-gate evaluation time from 476.62s to 35.67s (93% reduction), compared with AD-MPC, while preserving strong security guarantees.

Aggregate signatures play an important role in proof-of-stake systems, where many validators sign a block. There is a strong desire to aggregate all these signatures into one short signature that is fast to verify. Since all validators know the block number they are signing, this setting is well suited for synchronous (a.k.a stateful) signatures. Boneh and Kim (2019) showed that lattice-based one-time signatures (OTS) can be aggregated very efficiently. The Chipmunk and Lemur signature schemes extend this to an $\ell$-time synchronous scheme using a (homomorphic) Merkle tree of $\ell$ one-time public keys. Each leaf of the tree is used to sign one message, and these one-time signatures can be aggregated across many signers. Due to the Merkle tree, every aggregate signature includes a Merkle authentication path of length $O_\lambda(\log \ell)$. We present a different lattice-based approach to constructing a synchronous aggregate signature scheme. The length of an aggregate signature in our scheme is independent of $\ell$. The resulting signatures are asymptotically shorter than existing schemes, and concretely shorter for some parameter choices. The resulting signature verification algorithm is algebraic, which makes it amendable to efficient threshold signing. Moreover, we are able to prove security in an adaptive corruption model. We thus obtain an efficient lattice-based synchronous threshold signature scheme, where signatures from many signers can be aggregated into a single short signature. The scheme relies on a one time trusted setup to generate the public parameters.

Multi-Key Fully Homomorphic Encryption (MKFHE) is a variant of fully homomorphic encryption (FHE) that allows computations over data encrypted under different keys. Its support for non-interactive, dynamic participation and on-the-fly computation makes it an attractive primitive for multi-party applications. However, MKFHE has been largely overlooked in practice as its performance scales poorly, since the ciphertext size grows linearly with the number of participants in all existing constructions. Resolving this issue was a major open problem for almost a decade. In this work, we close this gap by providing the first construction of an MKFHE scheme with compact ciphertexts: the size of ciphertexts remains constant throughout the entire homomorphic evaluation, even when the number of participating parties changes during computation. As a result, our construction retains all the advantages of MKFHE while simultaneously offering fast evaluation performance similar to that of a single-key scheme. Our methodology is generic and applies to a broad class of RLWE-based FHE schemes. Concretely, we construct efficient multi-key variants of RGSW and FV-like schemes, and further develop a compiler that transforms a wide range of RLWE-based FHE schemes into their multi-key counterparts. We implement our multi-key FV scheme in Go. Empirical results show that our scheme achieves $30.6 \times$ faster multiplication and $60.6 \times$ faster automorphism for 16 parties compared to the state-of-the art construction by Kwak et al. (CCS '23), demonstrating the concrete efficiency of our construction.

Bootstrapping enables deep homomorphic computation in CKKS by replenishing multiplicative levels. It remains one of the scheme's most expensive operations. HEAAN reports a bootstrapping latency of 6.97ms, substantially faster than other publicly documented alternatives. However, the algorithmic and implementation techniques underlying this result have not been disclosed, leaving it unclear how such performance is achieved. In this work, we present a fully specified CKKS bootstrapping construction that achieves performance comparable to that reported by HEAAN. Building on SHIP (presented in Eurocrypt 2025), we introduce several algorithmic innovations that reduce communication and computational overhead while enabling efficient parallel execution. Our implementation bootstraps a single complex-valued ciphertext in 8.2ms and achieves an amortized latency of 4.6ms per ciphertext for a batch of 64. These results demonstrate practical sub-10ms CKKS bootstrapping.

Secure multiparty computation (MPC) enables mutually distrustful parties to compute on private digital inputs. We initiate the study of $\mathbf{spatiotemporal}$ $\mathbf{MPC}$, extending this paradigm to functionalities whose inputs additionally depend on physical facts such as the parties' locations, times, or trajectories. Such protocols must simultaneously hide spatiotemporal information and ensure its physical consistency: a malicious party should not be able to make the functionality operate on a spatiotemporal input inconsistent with its actual physical state. The main conceptual challenge is to formulate extraction of spatiotemporal information within the simulation-based security framework. We introduce $\mathbf{arguments}$ $\mathbf{of}$ $\mathbf{spatiotemporal}$ $\mathbf{knowledge}$, following the principle "I prove, therefore I am:" rather than defining physical presence directly through a mathematical relation, we define it operationally through the ability to complete a sound spatiotemporal verification protocol. Accordingly, an extractor recovers a spatiotemporal point from a successful prover and certifies its physical validity by using the extracted prover to succeed in an auxiliary spatiotemporal verification protocol. Building on this notion, we define universally composable (UC) security for spatiotemporal MPC, capturing privacy, physical consistency, and composability. We provide constructions achieving this new MPC notion. We first construct UC-secure commit-and-prove protocols for spatiotemporal knowledge: in the CRS model under LWE against quantum provers without pre-shared entanglement, and in the QROM against quantum provers with unbounded pre-shared entanglement. Using these protocols, we obtain general-purpose UC-secure spatiotemporal MPC from semi-honest post-quantum MPC. We also extend our framework to UC-secure spatiotemporal multiparty quantum computation over private quantum inputs and classical spatiotemporal information.

The Learning with Errors (LWE) problem is a cornerstone of post-quantum cryptography, and the dual attack is a central tool for evaluating its concrete hardness. In provable dual attacks, a major bottleneck is the large number of discrete Gaussian samples required over the dual lattice. While recent works have focused on accelerating the guessing step via modulus switching, the sampling bottleneck has remained largely unoptimized. In this paper, we address this issue from a new perspective. First, we observe that Banaszczyk's inequality can be significantly improved when the first minimum of the lattice is suitably large. This yields a refined distinguishing inequality, which provides sharper conditions for attack success. Second, we propose a new provable dual attack framework based on lattice projection. Instead of sampling over the entire dual lattice, we sample over a carefully chosen sublattice, whose dual is the projection of the primal lattice onto a lower-dimensional subspace. This reduces the lattice dimension and thus substantially accelerates discrete Gaussian sampling. We rigorously analyze the parameter conditions for the success of our framework, and by enumerating all feasible parameters we achieve an improvement of $26.1$--$43.7$ bits over the original provable dual attack framework.

In this note we find large primes $p$ such that $\Phi_k(p)$ is $B$-smooth for the cyclotomic polynomials $\Phi_k$, with $k = 3,4$ and $6$, and a sufficiently small smoothness bound $B$. These primes hence provide the first instantiation of integer factoring challenges that, a priori would be difficult to factor but, are actually easy to factor with traditional algorithms not typically used in practice.

Optimizing quantum circuits is critical: circuits must fit within the resource limits of a quantum computer, and every unnecessary operation increases their cost and probability of failure.We present a simple optimization algorithm for quantum circuits that (1) is very fast, (2) scales to millions of operations, and (3) matches or outperforms the optimization quality of the best existing optimizers and superoptimizers. Our key insight is that we can compactly represent circuit equivalence classes as a map which associates a projective unitary with a smallest representative circuit implementing it. We give a sound algorithm for synthesizing such maps, which we call minimal unitary representative maps (MURMs). Armed with a MURM, our optimizer inspects every bounded subcircuit in a linear pass and replaces it with a minimal variant. Incremental computation and symbolic arithmetic make every replacement fast and sound. Our evaluation shows that our approach achieves significantly greater circuit reductions than leading optimizers, runs orders of magnitude faster, and scales to circuits with millions of operations.

We propose a new variant of the Fiat–Shamir transformation where the Fiat-Shamir hash is instantiated by an external verifiable random function (VRF) service. We prove that soundness holds as long as the VRF secret key remains hidden from the prover, i.e., assuming no collusion between the prover and the VRF evaluator. Crucially, due to the public verifiability of VRF outputs, the VRF computation itself need not be trusted beyond the key-generation phase. This yields the first NIZK compiler in a non-idealized model that is both practical and provably sound. Our transformation can be instantiated using extensively deployed blockchain-based VRF services. Moreover, it naturally supports distributed VRF services, allowing the no-collusion assumption to be relaxed: soundness holds even if the prover colludes with up to a threshold number of evaluators. In this setting, distributed key generation for the VRF further eliminates trust in the setup. A distinctive feature of our approach is that the verification step is local and does not require accessing the VRF. This is particularly advantageous for recursive proof systems such as incrementally verifiable computation, where the verification circuit must be embedded within the circuit for which a proof needs to be generated. This enables construction of the first provable and practical recursive proof -- bypassing well-known impossibilities in the random oracle model. We demonstrate the real-world utility of our framework with an implementation for the GKR protocol.

Noisy linear algebraic assumptions (NLAs), such as $\mathsf{LWE}$ and Alekhnovich’s $\mathsf{LPN}$, have long served as the most reliable sources of post-quantum hardness. However, a series of recent classical attacks on assumptions once believed to be quantum-secure, coupled with the rapid progress in quantum technology, underscores the urgent need for assumptions that are plausibly hard even if both $\mathsf{LWE}$ and $\mathsf{LPN}$ turn out to be broken. A fascinating recent work of Ghosal et al. (Eurocrypt 2025) takes an important first step in this direction, constructing a PKE scheme by combining two NLAs that remain plausibly secure even if $\mathsf{LWE}$ and Alekhnovich’s parameter regime for $\mathsf{LPN}$ were to be polynomially broken. A critical weakness of their work, however, is that it is still $\mathsf{LPN}$-broken: namely, an oracle that breaks $\mathsf{LPN}$ with $n^{-\delta}$ noise rate can break their NLA, for some $\delta>0$. We ask: can this barrier be overcome? We answer this question positively, by introducing an NLA that is plausibly hard given an oracle that breaks even constant noise rate $\mathsf{LPN}$, while still being plausibly hard given an oracle that breaks $\mathsf{LWE}$. Along the way, we improve upon the work of Ghosal et al. significantly in several dimensions. Specifically, we introduce a single new natural NLA and provide constructions of (i) public-key encryption and (ii) two-round maliciously secure oblivious transfer protocol from this single assumption. We also construct a one-time circular-secure secret-key encryption from a binary variant of this assumption. Our assumption takes the form $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e})$, where $\mathbf{A}$ is a random unstructured square matrix, the secret $\mathbf{s}$ has short and sparse entries, and the error $\mathbf{e}$ is a mixture of two components: a small-but-dense error combined with a large-but-sparse error. We provide a comprehensive initial cryptanalysis, ruling out (1) efficient combinatorial attacks that exploit sparsity such as information set decoding, (2) dimension reduction attacks, and (3) dual lattice attacks. We also prove, via a reduction, that our assumption, and its binary variant, is at-least as hard as $\mathsf{LWE}$. Additionally, we show that for a broad range of parameters including those used by our constructions, our assumption does not appear to fall within the class of “lattice” assumptions, that is, there seems to be no reduction to approximate shortest vector problem solvers, and, crucially, it is plausibly hard even given an oracle that breaks $\mathsf{LPN}$ for any noise density parameter.

We construct the first polynomial commitment in groups of unknown order that simultaneously requires no trusted setup, has quasilinear prover time, and has constant-size opening proofs. Our main technical contribution is a transparent class group realization of the subset-product accumulator relation introduced by Morphic accumulators (CRYPTO ’26). It supports accumulating a fixed family of class group elements and proving prescribed algebraic relations among the accumulated elements, yielding constant-size range arguments with quasilinear prover time. Combining these range proofs with the DewTwo framework (CRYPTO ’25) gives the first transparent polynomial commitment with quasilinear prover time and constant-size openings. Concretely, our construction also gives the shortest known opening proofs (1.3 KB) among transparent polynomial commitments. We prove security under falsifiable class group assumptions and also develop new extraction techniques over dyadic rationals, which may be of independent interest.

Binomial coefficients modulo an integer, $\binom{N}{R} \pmod m$, are a primitive of combinatorial counting, yet the two textbook methods collapse at scale: the Pascal recurrence costs $\Theta(NR)$ time, and the factorial-table method costs $\Theta(N)$ memory, requires a prime modulus, and requires $N < m$. Composite moduli are harder still, because factorials are not invertible modulo prime powers and the exact power of $p$ dividing the coefficient must be tracked. We present a complete, provably correct engine for arbitrary $m < 2^{62}$ and $N < 2^{64}$. Methodology. The modulus is factored as $m = \prod p_i^{k_i}$ by trial division, deterministic Miller-Rabin, and Pollard-Brent rho. For each prime power we prove and implement the decomposition $\binom{N}{R} \equiv p^e F_p(N) F_p(R)^{-1} F_p(N-R)^{-1} \pmod{p^k}$, where $F_p$ is the $p$-free part of the factorial and $e$ is Kummer's carry count; the same count yields an $O(\log_p N)$ short-circuit that decides $p^k \mid \binom{N}{R}$ before any multiplication. A periodicity lemma derived from Gauss's generalization of Wilson's theorem compresses the state of Pascal's triangle modulo $p^k$ to $p^k$ prefix products, giving two regimes with proven bounds: a table regime answering queries in $O(\log_p N)$ multiplications after $O(\min(p^k, N_{\max}))$ preprocessing, and a direct regime costing $O(R + \log_p N)$ multiplications for $R < p^k$ with $O(1)$ memory. Residues are recombined by the Chinese Remainder Theorem. The hot loops are division-free: Montgomery arithmetic exploits an incremental-form identity so that every unit costs one multiply and one add, and moduli $2^k$ reduce by a bit-mask. Four modular-inverse strategies are compared, including Fermat-Hensel lifting and an inverse-prefix table built with a single inversion. Validation. 3,139,684 oracle checks against Pascal's triangle, Lucas' theorem, Gauss's theorem, and literature constants, plus 3,004 exact big-integer comparisons, passed with zero failures; all 101 benchmark checksums are bit-identical across a Windows GCC 16 12th-gen Intel laptop and a Linux GCC 11 Xeon server. Results. At $N \approx 10^{18}$ a query costs 1.4 to 6.9 microseconds for composite moduli and scales linearly in $\log N$ at 15 to 36 ns per base-$p$ digit. For prime moduli the table regime answers queries in 0.09 to 0.27 microseconds independently of $p$, and building the table costs 0.36 to 0.85 of a single worst-case direct query, so it pays for itself immediately. Montgomery arithmetic is 2.0 to 3.1 times faster than 128-bit modulo and bit-masking up to 6.7 times; Fermat-Hensel inversion is 16 to 20 times faster than the extended Euclidean algorithm at $2^{40}$ and 1.4 to 2.0 times faster for large odd prime powers. Against the Pascal recurrence the engine is already 7,100 to 12,800 times faster at $N = 4 \times 10^4$; at $N = 10^9$ the recurrence would need 4.6 to 5.8 CPU-years and a 4 GB row, whereas the engine answers in about 2 microseconds from a 244-byte table. With uniformly random $R$, the Kummer short-circuit resolves 95% to 99.998% of prime-power solves in $O(\log N)$ time, a rate predicted exactly by Fine's theorem. We also report the honest wall: for a prime $p \approx 10^9$ with $R \approx N/2$ no table fits in memory and a query costs 3.4 to 4.5 seconds—the intrinsic $\Theta(p^k)$ bound that only sub-linear factorial algorithms could remove.

Context-committing security binds an authenticated encryption (AE) ciphertext uniquely to its encryption context. Many conventional AE schemes lack this guarantee, while most generic committing transforms rely on idealized primitives. We develop committing AE from explicit forkcipher collision-resistance properties: $\mathsf{fCR}$ and zero-message collision resistance ($\mathsf{zmCR}$). For an $n$-to-$2n$-bit forkcipher, we establish matching query complexities of order $2^{n/2}$ and $2^n$, respectively. MILP- and SAT-based differential and reduced-round collision analyses of $\textsf{ForkSkinny-128-384}$ support the corresponding generic security levels for the full-round primitive. We also analyze collisions in ButterKnife and ZIP-AES. We lift $\mathsf{fCR}$ and $\mathsf{zmCR}$ through FCPRF and FixM to fixed-length collision-resistant PRFs. We introduce nonce-based PRF security to capture the nonce-respecting pseudorandomness needed by our constructions, and construct FHashN, proving its variable-input-length collision resistance, pseudorandomness, and nonce-based pseudorandomness. We present AEaH-2K, a two-key variant of AEaH combining secure AE with a variable-input-length collision-resistant PRF. Including the AE key in the commitment input gives confidentiality, authenticity, and CMT-4 security in the standard model. We also construct $\textsf{FCTR-CMT}$, an AEAD mode using a single forkcipher, and prove nonce-respecting privacy, authenticity, and CMT-4 security. With FHashN based on FCPRF, $\textsf{FCTR-CMT}$ achieves $n$-bit confidentiality and $n/2$-bit authenticity and CMT-4 security; with FixM, all 3 reach $n$ bits. All construction proofs reduce to explicit pseudorandomness and collision-resistance assumptions.

We develop a new Coppersmith lattice attack on balanced CRT-RSA with small CRT exponents $d_p, d_q$ using unravelled linearization. The new attack matches the practical effectiveness of the Takayasu–Lu–Peng attack (JoC 2019) while using lattices of roughly half the dimension. In contrast to their attack, for which there is a noticeable gap between the theoretical predictions and experimental results, our theoretical estimates closely match the experimental results for all tested parameter sets. Our analysis further shows that the asymptotic bound remains $d_p,d_q<N^{0.122}$, so the new attack does not achieve the asymptotic improvement anticipated by Takayasu, Lu, and Peng. Nevertheless, performing LLL reduction on lower-dimensional lattices substantially reduces the running time, allowing us to attack much larger $d_p,d_q$ in practice. Furthermore, through elegant variable substitutions, we extend our attack to two most significant bit (MSB) leakage models, obtaining the first attack exploiting MSB leakage of $p+q$ and an improved attack exploiting MSB leakage of $d_p,d_q$. In both models, the asymptotic bounds improve as the amount of leakage increases and recover the Takayasu–Lu–Peng bound in the absence of leakage.

Computing smooth-degree isogenies between supersingular elliptic curves with known endomorphism rings is a fundamental task in isogeny-based cryptography. Via the Deuring correspondence, this task is equivalent to finding a connecting ideal of smooth norm between the corresponding quaternion maximal orders. KLPT-type algorithms address this problem by transforming a known connecting ideal into an equivalent ideal of smooth norm. Although connecting ideals of norm approximately $p$ are expected to exist, the best known such algorithms for general input only achieve norm $\widetilde{O}(p^{4.5})$. In this paper, we propose $\Delta$-KLPT$^+$, a new KLPT-type algorithm that lowers this bound to $\widetilde{O}(p^4)$. Our construction builds on $\Delta$-KLPT, which attains a smaller norm bound but requires two input ideals of the same prime norm. To extend $\Delta$-KLPT to arbitrary inputs, we introduce a new subroutine IdealNormReduce, which reduces the common norm of an ideal pair. By iterating IdealNormReduce, we obtain two ideals with a common norm below $p$. Then we apply $\Delta$-KLPT to the resulting ideal pair to obtain a desired connecting ideal of smooth norm. As an application, we construct Delfar, a fully anonymous isogeny-based ring signature scheme. Compared to Erebor-full, Delfar achieves shorter signatures and lower signing and verification costs for large rings.

The Keccak hash function, designed by Bertoni et al., was selected as the new generation of Secure Hash Algorithm (SHA-3) in 2012. For NIST-standardized SHA-3 instances (SHA3-224/256/384/512, SHAKE128, SHAKE256), practical collision attacks have reached five rounds; six-round SHAKE128 was known only as a theoretical attack with cost $2^{123.5}$ six-round evaluations~\cite{tuyi2022sha3}. In this paper, we present the first classical practical collision attack on six-round SHAKE128 with $d{=}160$ and total complexity about $2^{47.82}$. Building on the Dinur-framework Dinur et al.~\cite{dinur2012new} and the SAT tooling of Guo et al.~\cite{tuyi2022sha3}, we introduce a parameterized colliding-trail SAT model--- collision length in digest and weight bounds are chosen at setup together with leaner differential encodings. Specifically, we introduce an enhanced heuristic strategy to identify suitable differential trails and employ multiple techniques to optimize the connectors: for the connector phase, we minimize weighted propagation cost of second round and third round, and penalize costly $\mathrm{DDT}{=}2$ transitions; candidate $\chi$-compatible equations are chosen by a bit-granular greedy routine that maximizes connector degrees of freedom. In addition to SHAKE128, we report six-round \textbf{near}-collisions on SHA3-224 and SHA3-256 (four and six differing digest bits, respectively), and practical collisions on four- and five-round SHAKE256 with the full $512$-bit digest.

We present Couplet, a new pairing-based multivariate polynomial commitment scheme (PCS). Couplet is the first multivariate PCS whose opening proofs are solely two group elements. In addition, for the case of multilinear polynomials, Couplet is the first constant-proof PCS with a prover that requires only a sublinear number of group operations. We achieve those properties simultaneously at the expense of a quasilinear, polynomial-specific, one-time preprocessing phase, whose cost can be amortized over multiple subsequent openings. On BN254, our implementation opens multilinear polynomials with $20$ variables about $20\times$ faster than Mercury after preprocessing, breaking even in total prover time after roughly 100 openings. Our approach generalizes to batched evaluation proofs, yielding a constant-size proof for multiple evaluation points without using random oracles. Applications include verifying repeated inferences of a committed model as well as more efficient auditable authenticated dictionaries. Our main technique involves compressing Papamanthou--Shi--Tamassia (PST) evaluation proofs, giving a single commitment which encodes all $\log n$ quotient polynomials which are normally given out separately in a PST proof. In doing this, we reduce the verification to a univariate sumcheck problem, which we solve with techniques from Groth16 using a single additional group element. We prove extractability in the algebraic group model under a parameterized discrete-logarithm assumption. We give hiding variants and prove perfect zero-knowledge of the opening protocols. All opening protocols are noninteractive and require no random oracle.

MPC-based privacy-preserving machine learning (PPML) typically operates over finite rings rather than floating-point arithmetic, making arithmetic overflow an inherent risk. Existing overflow-detection techniques generally require the evaluation of nonlinear functions, resulting in substantial computation and communication overhead. We propose Soft Boundary Detection, which reduces boundary verification to probabilistic functions over partitioned intervals, with a cost comparable to that of linear computation. Building on this abstraction, we develop an efficient mechanism for detecting arithmetic overflow in PPML workloads. Moreover, we show that Soft Boundary Detection naturally extends to the malicious-adversary setting. In ring-based computation, it further avoids the need to choose a ring space substantially larger than the actual data range to ensure soundness against malicious behavior. Our framework provides two key benefits: (1) highly efficient arithmetic overflow detection, and (2) active security without requiring ring extension or enlarging the underlying ring space. Experimental results demonstrate that our approach substantially strengthens security while retaining high efficiency, providing a practical solution for robust and actively secure PPML.

Multiplicative zero-knowledge ($\mathsf{MZK}$) replaces the negligible statistical distance required by statistical zero-knowledge ($\mathsf{SZK}$) with symmetric $(\varepsilon,\delta)$ approximate max-divergence between real and simulated verifier views. Prior work established efficiency gains from this relaxation; we study its computational power. With negligible completeness, soundness, and additive simulation errors, \[ \mathsf{HVMZK}[\varepsilon]=\mathsf{MZK}[\varepsilon]=\mathsf{SZK} \qquad\text{for }\varepsilon(n)=O(\log n), \] where $n$ is the input length. Taking the union over polynomial leakage bounds gives \[ \mathsf{MZK}[\mathrm{poly}]=\mathsf{HVMZK}[\mathrm{poly}]=\mathsf{PSPACE}, \] even with zero additive simulation error. For every fixed $c>0$, a polynomially padded $\operatorname{TQBF}$ language remains $\mathsf{PSPACE}$-complete and belongs to $\mathsf{MZK}[O(n^c)]$. A linear-leakage protocol for $\operatorname{SAT}$ separates $\mathsf{MZK}$ from $\mathsf{SZK}$ unless the polynomial hierarchy collapses to its second level. Padding yields $\mathsf{NP}$-complete separators at every fixed positive polynomial exponent. Under a subexponential weakening of the nonuniform nondeterministic Strong Exponential Time Hypothesis, every polylogarithmic level $\mathsf{MZK}[O((\log n)^j)]$ with fixed $j\geq2$ strictly contains $\mathsf{SZK}$. The logarithmic threshold is tight relative to oracles: every polynomial-time computable, polynomially bounded superlogarithmic leakage budget admits an oracle separating classical $\mathsf{MZK}$ from quantum statistical zero-knowledge. Finally, fraction statistical knowledge complexity exactly characterizes one-sided real-to-simulator multiplicative simulation, with the sharp knowledge parameter and negligible statistical error.

Lattice-based proof systems are one of the leading routes to quantum-safe succinct proofs. Existing lattice-based schemes come with inherent limitations arising from the coupling between the commitment and constraint domains. First, commitment efficiency is restricted by the need for invertible challenge differences, which precludes the use of fully splitting moduli that enable the fastest lattice arithmetic. Second, the characteristic of the constraint field must equal the commitment modulus. This limits the efficiency of proving binary computations, including standard hash function evaluations. We present $\mathsf{LaBinius}$, a lattice-based polynomial commitment scheme, in which the evaluation arithmetic is separated from that of the commitment. The commitment runs over a composite modulus, and all of its prime factors are NTT-friendly. The evaluation claim lives in a binary extension field, without bitness checks or overhead over a binary arithmetisation. We implement the scheme with AVX-512 kernels and connect it to the $\mathsf{Binius}$ and $\mathsf{Flock}$ front ends in an almost black-box way, which lets us use their arithmetisations tailored to binary fields. As a result, we obtain a SNARK for standard hashes. Proving $\mathsf{Keccak}$-$\mathsf{256}$, $\mathsf{SHA}$-$\mathsf{256}$ and $\mathsf{BLAKE3}$ on one core, our prover takes at most $1.2$ times as long as the hash-based prover supplied with each system, and we obtain a single-core throughput of over $67{,}000$ $\mathsf{BLAKE3}$ compressions per second with verification in under $40$ milliseconds. With $\mathsf{LaBRADOR}$ as a recursive compressor, the prover takes less than twice as long as the hash-based provers at the largest sizes we consider, while the proof size is below $100$ KiB. This is about five times smaller than the proofs of $\mathsf{Binius}$ and $\mathsf{Flock}$ at those sizes and constitutes the smallest quantum-safe proof of a standard hash evaluation to date.

Decryption in EC-ElGamal and Twisted ElGamal based Additively Homomorphic Encryption (AHE) requires solving a small exponential Elliptic Curve Discrete Logarithm Problem (ECDLP) that recovers a bounded plaintext scalar $m$ from $m \cdot G$. This recovery step is the performance-critical path in various applications, such as electronic voting systems (e-Voting), private federated learning, and privacy-preserving blockchain confidential payment systems including Zether (EC-ElGamal), Solana Token-2022 Confidential Transfers (Twisted ElGamal), and the forthcoming XRPL XLS-96 standard (EC-ElGamal). The state-of-the-art FastECDLP (Tang et al., 2023) employs the baby-step giant-step algorithm (BSGS) to solve ECDLP in $\ell$-bit range by utilizing a baby-step table $T_1'$ of $2^{\ell_1 - 1}$ affine points and achieves fast decryption by precomputing a giant-step table $T_2'$ of all $2^{\ell_2 - 1}$ affine points where $\ell_1 + \ell_2 = \ell$. Even with the signed-range halving of Tang et al., the giant-step table for secp256k1 requires 5.91 GB for a 58-bit search space and exponentially increases to 378 GB for a 64-bit search space. Thus, as noted by Tang et al., a 64-bit range remains impractical on a typical workstation due to the memory requirements. We present three algorithmic contributions that together eliminate $T_2'$ and enable practical 64-bit decryption. (i) A Jacobian coordinate loop advances the giant-step point iteratively in Jacobian coordinates, removing the need to precompute the giant steps in affine coordinates. (ii) Windowed batch inversion batch-inverts a window of a small $W$ accumulated $Z$-coordinates at once, reducing the per-thread working memory required for the giant-step computation from $O(2^{\ell_2})$ (the size of $T_2'$ in FastECDLP) to $O(W)$ regardless of bit size. (iii) Co-Z arithmetic computes two giant steps simultaneously by maintaining a shared $Z$-coordinate, reducing the field multiplication cost per step. We validate our solver on two machines, a laptop-class Apple M1 Pro and a desktop-class Intel Core Ultra 9 285K, with consistent results across both. On the Intel machine, our complete solver outperforms a faithful re-implementation of FastECDLP at 54-bit and 58-bit ($\ell_1 = 31$, up to $2.3\times$ faster) without storing the giant-step table $T_2'$. At 63-bit and 64-bit, Tang et al.'s giant-step table $T_2'$ requires 189 GB and 378 GB respectively, making their approach infeasible on typical desktop or laptop computers. So far, our solver is the only feasible approach, completing full 63-bit and 64-bit decryption in 53 sec and 105 sec, directly overcoming the memory limitation identified by Tang et al. We also discuss two additional arithmetic optimizations, an inversion-chaining scheme and a co-Z Jacobian addition, that reduce the per-step arithmetic cost.

Private information retrieval (PIR) inherently requires public-key cryptography. A recent line of work suggests that this barrier can be avoided in secret-key PIR, where the client first preprocesses an N-bit database and retains only a short secret key. This line of work has yielded communication O(N^\epsilon) for any constant \epsilon under the Learning Parity with Noise (LPN) assumption in a high-noise regime not known to imply public-key cryptography, and communication O(N^{1/2}) under one-way functions. Whether compression beyond N^{1/2} can be achieved without relying on structured assumptions such as LPN has remained open. We show that interaction enables polylogarithmic communication in the random oracle model. We construct a secret-key PIR protocol with O(log N ) rounds and polylogarithmic total communication. Alternatively, for any constant \epsilon, we obtain a constant-round protocol with communication O(N^\epsilon). We also obtain protocols with similar communication in the plain model under the weakest version of LPN, with maximal noise rate 1/2 − o(1). Our main idea, inspired by the free-XOR technique for circuit garbling, is to make secret-key preprocessing homomorphic under XOR, while relying on security against related-key attacks.

The Groth16 verification equation has a compact algebraic description, yet garbling its Boolean implementation can require tens of gigabytes. We show how to garble this computation using native elliptic-curve group operations. Motivated by proof verification in trust-minimized Bitcoin bridges, we construct a projective partial garbling scheme for conditional disclosure on invalid Groth16 proofs. For a fixed verification key and public statement, evaluation reveals a garbler-held secret when the supplied proof is invalid and hides the secret when it is valid. The proof itself remains public. The main technical challenge is handling a pairing whose two arguments are supplied by the evaluator. We introduce a rekeying gadget that resolves this using a single private scalar multiplication. Building on Argo MAC (Eagen and Lai, 2026), BABE (Garg et al., 2026), and Duty-Free Bits (Khambhati et al., 2026), we prove a composition theorem for partial garbling across input representations and apply it to transform group encodings into bitwise projective encodings. This requires extending the projectivization technique of Duty-Free Bits to quadratic extension fields. The resulting garbled program has size $O(\lambda^2)$ bits, where $\lambda$ is the computational security parameter. We prove privacy under the decisional Diffie-Hellman assumption, in the random oracle model. Our BN254 implementation produces a 2.4 MiB garbled program, including projectivization, compared with the 48 GB reported for Boolean garbling of Groth16. Thus, we improve over prior state of the art in Groth16 garbling by over four orders of magnitude.

Succinct arguments are a fundamental cryptographic primitive for verifying computational claims with small communication. In the classical setting, succinct arguments for NP can be constructed from unstructured hardness alone (e.g., hash functions) by compiling probabilistically checkable proofs (PCPs) or interactive oracle proofs (IOPs) for NP via the commit-and-open paradigm. In contrast, known succinct arguments for QMA rely on ``structured'' cryptographic primitives, or on the quantum PCP conjecture. We construct the first succinct argument for QMA in the quantum random oracle model (QROM) without relying on additional cryptographic assumptions or unproven conjectures. This yields succinct arguments for QMA from unstructured hardness alone, showing that ideal hash functions not only suffice for succinct arguments for NP but also for QMA. Underlying our result is an efficiency-preserving transformation that compiles quantum interactive oracle proofs (QIOPs), a recently introduced interactive generalization of quantum PCPs, into quantum arguments for the same language, via a natural quantum commit-and-open paradigm. Our transformation applies to every QIOP with public-query soundness, a notion that we formalize to capture a natural requirement of the commit-and-open paradigm and is satisfied by a known QIOP for QMA. As a key ingredient in our transformation, we formalize and construct extractable vector commitments for quantum states with local openings in the QROM, which may be of independent interest.

Known lower bounds prohibit the construction of very-efficient authenticated dictionaries that support both insertions and deletions. It remains an open question, however, whether it may be possible to construct very efficient authenticated dictionaries that are \emph{insertion-only}. The current paper answers this question in the affirmative, providing the constructions that strictly dominate the classic Merkle tree in the incremental setting. Our first result is an authenticated incremental dictionary, called the exponential Verkle forest, that supports retrieval queries with time and proof size $O(\log \log n)$ and that supports insertions with time and proof size $O(\log \log \log n)$. The data structure also offers an \emph{amortized} bound of $O(1)$ for insertions. Building on this, we also present a full-query version of the dictionary, supporting both retrieval and exclusion queries. This data structure continues to support retrieval queries in time and proof size $O(\log \log n)$, while supporting all other operations in time and proof size $O(\log n)$. Our results take a purely data-structural perspective on authenticated data structures, seeking to achieve the best bounds possible with the cryptographic primitives (collision-resistant hashing and position-binding vector commitments) that already exist. We also give partial evidence, in the form of a lower bound that applies to a natural class of data structures, that our $O(\log \log n)$ query bound is optimal for any solution with linear construction time.

The importance of deep neural networks (DNNs) is widely recognized, and the parameters obtained through training are regarded as valuable assets. Recently, attacks that extract these parameters using only oracle queries to a DNN have been actively studied at IACR conferences. The hard-label setting is the most challenging setting for model extraction, where an adversary can observe only the final output label, such as “dog” or “cat.” At Eurocrypt 2025, Carlini et al. proposed polynomial-time hard-label extraction of ReLU-based MLPs. However, one step of this attack process, i.e., sign recovery, requires a large number of queries and substantial computation. Implementing this step in a black-box setting remains difficult. Consequently, a fully black-box end-to-end demonstration on trained deep ReLU MLPs has remained a challenge. In this paper, we propose a new sign-recovery algorithm based on a completely different principle from the existing method. Our method requires no dedicated queries for sign recovery. In our experiments, it achieves higher sign-recovery accuracy than the existing method. Consequently, it enables efficient sign recovery even for trained models. With our sign-recovery algorithm, all steps of hard-label model extraction can be implemented in a black-box setting. By combining these implementations, we demonstrate end-to-end model extraction from models trained on MNIST and Fashion-MNIST, with width 16 and 4 or 6 hidden layers, achieving over 98% label agreement.

Traditional public-key encryption (PKE) schemes have a static secret key. This means that the secret key owner can decrypt any old ciphertext in perpetuity. Schemes with changing secret keys, supporting so-called epochs, have been considered for a variety of reasons, such as post-compromise security or more simply supporting communication among a dynamically changing group. This complicates perpetuity, especially in settings where the epoch number itself is supposed to be confidential. We address this concern by introducing perpetual encryption (PE). The scheme leverages a trusted group manager to distribute states for each epoch such that: (1) without such a secret state, ciphertexts look pseudorandom and, hence, hide the epoch number; and (2) parties in a later epoch can still decrypt encryptions for old epochs in sublinear time (in the number of epochs). More stringently, we require that whenever a party in an earlier epoch decrypts to a message m then any party in a later epoch must arrive at the same message, even for adversarially crafted ciphertexts. We build an efficient, unbounded-epoch PE scheme based on anonymous PKE, hashing, and other standard symmetric primitives. We also extend our scheme to protect against malicious group managers, at the expense of limiting the maximum number of epochs. All our schemes have fixed-sized states and decryption times, independent of the number of epochs.

Cryptanalytic model extraction aims to reconstruct a functionally equivalent model through black-box interactions with the victim model. Under the fundamental assumption that the network architecture is completely known, existing attacks achieve the goal by recovering the model parameters. In this paper, we explore whether this assumption can be removed practically. Focusing on ReLU fully connected networks, which are widely studied in this field, we propose a guess-and-determine framework that jointly recovers the network architecture (including network depth and hidden-layer dimensions) and the model parameters. This framework is based on a simple yet effective high-level idea: after designing a parameter recovery attack under the known-architecture assumption, we can analyze the architecture-sensitive traces observed during parameter recovery to recover the network architecture. We identify two such traces in differential extraction attacks: (i) a zero suffix in the merged weight vectors produced by signature recovery, whose length reveals the hidden layer dimension; and (ii) an equality pattern in the preimage-based sign recovery, which occurs only under the true hidden layer dimension. These two signals give rise to two routes for network architecture recovery. For the second-to-last layer, we further propose two methods, one for identifying it, and one for recovering its dimension. Practical end-to-end attacks are implemented on a wide range of ReLU neural networks, including both expansive and non-expansive networks. To the best of our knowledge, this is the first time the feasibility of achieving functionally equivalent extraction on deep neural networks, after removing the known-architecture assumption, has been demonstrated in practice.

Assuming the polynomial-time hardness of Decomposed LWE, a variant of the learning with errors (LWE) problem, we construct ciphertext-policy attribute-based encryption for depth-unbounded (but bounded-space) predicates. Previously, attribute-based encryption for depth-unbounded predicates was only known from an insecure version of evasive LWE, or by additionally assuming the cryptographic hardness of discrete logarithms, which makes such schemes quantum-insecure. Adapting these techniques, we also obtain the first construction of lattice-based delay encryption [Burdges and De Feo, EUROCRYPT'21], additionally assuming the existence of any space-bounded sequential function. Finally, as a contribution of independent interest, we show how to instantiate the latter from a circular variant of decomposed LWE. This also gives the first delay encryption that does not require explicit sequentiality assumptions.

Assuming the polynomial-time hardness of a variant of the short integer solution (SIS) problem, we show the existence of sequential and memory-hard functions. Such an assumption postulates the hardness of a problem against polynomial-time algorithms, regardless of their memory and depth. Yet, we show that this assumption implies that $\mathsf{P} \neq \mathsf{NC}$, that $\mathsf{P} \neq \mathsf{L}$, and that the $\mathsf{NC}$ hierarchy is proper, i.e., that $\mathsf{NC}^1 \subsetneq \mathsf{NC}^2\subsetneq \mathsf{NC}^3 \dots$ Our main technical tool is a new variant of homomorphic computation over lattice encodings, which does not impose a bound on the circuit depth and is not based on bootstrapping.

We study the regular indifferentiability of the sum of two n-bit permutations. Previous work proved 2n/3-bit security and gave a 5n/6-bit attack against the uniform simulator. We prove 3n/4-bit se curity for the simulator and give a matching attack. Our proof bounds the KL divergence between response distributions by tracking the bias in unrevealed construction values through their conditional distribution, which was not analysed in detail in previous work. To exceed this thresh old, we introduce the Gyroscope simulator, which adjusts inverse-query acceptance probabilities to compensate for the bias left by earlier re sponses. The Gyroscope simulator achieves 4n/5-bit security.

With the widespread adoption of NIST's new signature standard ML-DSA imminent, understanding its vulnerability to side-channel attacks is increasingly important. Current approaches that are based on deriving (Concealed) Integer Learning with Errors (ILWE) samples from side information require hundreds of thousands of signatures even in noise-free conditions, limiting their practicality. In this work, we show that the number of signatures required in these attacks has been drastically overestimated. Keeping track of the error probability distribution when deriving ILWE samples allows for a soft-analytic approach to solving ILWE. Concretely, we show that distribution hints (Eurocrypt 2025) may be derived from ILWE samples and the corresponding belief propagation-based solver can recover the secret key efficiently. We then conceptually compare previous solvers to our soft-analytic approach. Furthermore, we provide an information-theoretic analysis and answer an open question---on how to filter out relations---posed in a different line of attacks against ML-DSA (Crypto 2025); thereby, we can propose improvements in the application of these solvers. We evaluate our approach across various ILWE and Concealed ILWE parameter sets. In addition, we analyze a recently discovered timing leakage in ML-DSA and show how to solve for the secret key with far fewer signatures. In a noise-free attack setting, our approach reduces the average number of signatures required by a factor of 62---from 139 million to 2.25 million---compared with linear regression, as originally proposed, with larger improvements under noise. Thus, we show that attacks that derive ILWE and Concealed ILWE instances require far fewer signatures than previously believed, and their impact has been underestimated.

Since the SHA-3 family was standardized by NIST in 2015, its collision resistance has been extensively studied. The previous best-known collision attack on 5-round SHA3-384 is based on internal differentials and the probabilistic-linearization variant of two-block Target Internal Differential Algorithm (TIDA). Its connector replaces deterministic affine restrictions that guarantee S-box differential validity by higher-dimensional affine relaxations, reducing the number of linear constraints and preserving more degrees of freedom. The price is that solutions of the linearized system are only probabilistically valid. In particular, once the first message block fixes the inner part variables, the remaining affine solution space cannot be treated as a set of independent trials; only part of its freedom effectively contributes to the connector probability. This paper refines the probabilistic-linearization framework in two ways. We first propose SA-PIDS, a simulated-annealing-based search for affine-subspace assignments, improving the trade-off among capacity constraints, the product-density estimate, and the remaining solution-space dimension. We then give a structural evaluation of the actual connector probability, explaining how the effective remaining freedom in the solution space after fixing the first block could be used and counted. Using the same target internal differential characteristic as the previous 5-round SHA3-384 attack, our refinements reduce the theoretical complexity from $2^{170.73}$ to $2^{164.11}$.

In a multi-party protocol, incoercibility aims to protect protocol participants by allowing them to use their honest inputs even in the presence of a coercer. A coercer is an adversary who pressures protocol parties into deviating from the protocol. One goal of an incoercible protocol is that the coercer cannot distinguish if the coerced party obeys their command or is deceiving: The coerced party should be able to plausibly deny their deception to ensure their safety. In the past, several attempts at modeling incoercibility in the Universal Composability framework have been made. In Alwen, Ostrovsky, Zhou, and Zikas’ model (CRYPTO 2015), the deception is modeled as a mapping of protocol messages that are sent and received by the coerced party beyond the reach of the coercer. Similar to proofs in plain UC, in order to prove the incoercibility of a protocol, one shows the indistinguishability of ideal and real worlds. Alwen et al.’s incoercibility definition makes use of four worlds: In both the ideal and the real worlds either coercion or deception takes place. If the environment can neither distinguish between the two coercion worlds nor between the two deception worlds for all ideal deception strategies, the protocol incoercibly UC-realizes the ideal functionality. While this shows that it is always possible for a coerced party to deviate from the coercer’s instructions and deceive them, it does not cover if this deception can be detected by the coercer. In this paper, we tackle the question how the perceived difference between deception and coercion can be modeled in UC. In particular, we make the following contributions. First, we refine the incoercibility notion by Alwen et al. by limiting the deception strategies to ones that allow the coerced party to plausibly deny the deception. We propose a multi-party computation protocol, derived from the one presented by Alwen et al., that fulfills this notion. The protocol uses hardware tokens to make UC-protocols, now including reactive functionalities, incoercible, where coerced parties can deceive the coercer about inputs as well as outputs. Secondly, we define a notion for plausible deniability, which we call Γ-deniability, and show that when the evaluated function is a differentially private mechanism, the deceiving party can plausibly deny their actions.

We study the detectability of split surfaces in isogeny graphs of principally polarized superspecial abelian surfaces, a question relevant to the security analysis of dimension-$2$ isogeny-based cryptography. Our approach uses refined Humbert invariants to replace explicit isogeny computations with primitive representation problems for positive definite quadratic forms in five variables. We develop algorithms to detect $(N,N)$-splittings and to compute the minimum $(N,N)$-splitting level of a superspecial Jacobian without constructing the corresponding isogeny path. The same framework detects embeddings of real multiplication (RM) orders through primitive representations of discriminants of real quadratic orders. For RM, we use exhaustive small-prime data together with $100{,}000$ random polarizations per prime for $227\leq p\leq1619$, testing primitive representations of square-free discriminants $D\leq100$; the first nontrivial primitively represented discriminant is typically small. We apply these methods experimentally in two regimes. For $11\leq p\leq251$, where the irreducible principal polarizations are known exhaustively, the automorphism data recovered from the refined Humbert invariant reproduces the counts of Ibukiyama--Katsura--Oort for the irreducible polarizations. For large parameters, we reach primes of $1000$ bits, where the splitting degrees produced satisfy $\log_2N\approx\log_2p$ with a distribution whose shape is stable across the whole range, so the detected $(N,N)$-isogeny has degree about $p^{2}$; the smallest observed largest prime-power divisor of $N$ remains small up to $250$ bits and increases sharply from $300$ bits onward.

Batched Threshold Encryption (BTE) enables a committee of parties to jointly decrypt any subset of ciphertexts from a large set, while all other ciphertexts remain private. BTE has applications in blockchains, particularly in designing encrypted mempools, where transactions are encrypted until included into a block to prevent maximal extractable value (MEV) attacks. Existing BTE constructions, however, encounter one of the following usability downsides: (a) reliance on expensive distributed key generation (DKG) protocols, (b) dependency on a batch label during ciphertext generation, (c) ciphertexts that are only decryptable if they are encoded with respect to a non-conflicting index in the batch, or (d) no support for weighted threshold policies. In this work, we present a BTE scheme that simultaneously addresses all of the above issues. It has a silent setup (key generation does not require interaction between parties), is batch and index independent, and supports weighted threshold policies. Our construction is based on prime-order groups with bilinear pairings with security proof in the Generic Group Model. Our ciphertext size is also the shortest among existing silent batched threshold encryption schemes with only $2$ group elements in addition to the message length.

The paper investigates secret sharing schemes based on linear codes, focusing primarily on the access structures and adversary structures arising from dynamic participant updates, as well as on whether such access structures can be realized by ideal linear secret sharing schemes. First, we characterize the maximal adversary structure corresponding to the access structure obtained by adding new participants to every authorized subsets of a given access structure.Second, we prove that the original access structure can be realized by a linear code $C(n+1)[n+1,k;q]$ if and only if the access structure obtained after adding $\ell$ new participants can be realized by a linear code $C(n+\ell+1)[n+\ell+1,k+\ell;q]$. In addition, we establish the correspondence between the codewords of these two linear codes. Furthermore, We prove that the original access structure can be realized by an ideal secret sharing scheme if and only if the expanded access structure can be realized by one as well. Finally, we demonstrate that every linear secret sharing scheme realizing a disjoint access structure is ideal. We also prove that access structures whose any two minimal authorized subsets share all but one participant can be realized by an ideal linear secret sharing scheme. In addition, we determine the adversary structure corresponding to this class of access structures. More generally, we obtain the maximal adversary structure when new participants are added to merely part of the minimal authorized subsets.

In this work, we present a quantum implementation of Keccak-$f(25)$, a toy version of SHA-3 introduced in the specification of Keccak, with the objective of using as few qubits as possible so that the resulting implementation can be run both on quantum emulators and on quantum hardware. The code, written in Qiskit, uses $25$ qubits representing the internal state. All computations are performed in-place, meaning that no ancillary qubit is required. We use this implementation to compare the number of logical and instruction-set-architecture quantum gates required to run Keccak-$f(25)$, both on emulators and on quantum hardware, as well as for Grover's algorithm on the hash function. Finally, we use our implementation to highlight the specificity of quantum password cracking using Grover's algorithm with Keccak-$f(25)$.

Kannan's algorithm, as analyzed by Hanrot and Stehl\'e in 2007, solves the exact Euclidean shortest vector problem in polynomial space and \(n^{\frac{n}{2e}+o(n)}\) time. In the classical setting with polynomial space, we obtain the first improvement on this bound via a randomized algorithm that runs in \(n^{\frac{n}{4e}+o(n)}\) time. The main idea is to represent a fixed shortest vector in many ways as a difference of samples, thereby enabling the low-space collision search of Lyu and Zhu (SODA 2023) to replace exhaustive enumeration in the original analysis.

LtHash is a lattice-based incremental hash function introduced by Bellare and Micciancio at EUROCRYPT 1997. It can be used in distributed systems to efficiently maintain digests of changing data. Its set-collision resistance rests on the average-case hardness of the ternary short integer solution (SIS) problem in the random oracle model. LtHash implementations typically use power-of-two groups $(\mathbb{Z}/2^d\mathbb{Z})^N$ for efficient machine-word arithmetic and SIMD parallelism. Previous security estimates were based on Wagner-type generalized birthday attacks with sub-exponential running time. Chen, Liu, and Zhandry (CLZ, EUROCRYPT'22) describe a folklore algorithm attributed to Regev that solves ternary SIS modulo $2^d$. Applying this algorithm to LtHash yields polynomial-time collision attacks requiring $O(N^d)$ hash queries, a result that has not been previously documented. We improve the Regev--CLZ algorithm by canceling two modulus bits per layer instead of one, while preserving ternary coefficients. This reduces the number of input columns---and hence the number of LtHash queries---from $O(N^d)$ to $O(N^{\lceil d/2\rceil})$. This refutes the uniform average-case formulation of Liyan Chen et al.'s conjecture (ITC'26) that the Regev--CLZ bound is optimal. Our technique also extends to inhomogeneous SIS with the same bound. For LtHash16 with $(N,d)=(1024,16)$, used at Facebook and in Solana, our attack requires approximately $2^{81}$ hash queries. Its expected computational cost is at most $2^{101}$ scalar operations over $\mathbb{F}_2$, compared with our estimates of approximately $2^{180}$ operations for the Regev--CLZ algorithm and $2^{188}$ for the state-of-the-art generalized birthday attack of Tang et al. (CRYPTO'26), under their respective operation models. Our query and scalar-operation costs are both far below the level suggested by the original claim of at least 200-bit security.

We introduce RisePIR, the first preprocessing keyword private information retrieval (PIR) scheme that absorbs insert, update, and delete on its key-value store at a cost proportional to the number of mutations alone. Where the static state-of-the-art schemes ChalametPIR and $\mathsf{KPIR}^{\mathsf{index}}$ re-run their preprocessing from scratch on every change, RisePIR patches its preprocessing in place and stays as practical as both in the online phase. We give a generic construction of incremental preprocessing keyword PIR from any updatable preprocessing index PIR, an index PIR that efficiently supports in-place update. The construction rests on our $d$-ary Segmented Cuckoo Filter, a cuckoo filter that confines the $j$-th candidate bucket of every key to the $j$-th of $d$ segments and stays dynamic under partial-key cuckoo hashing. Instantiating the construction over FrodoPIR and SimplePIR, each equipped with the entry-level hint patch of iSimplePIR, gives RisePIR-F and RisePIR-S, both secure under decisional LWE. On a store of about one million keys, both variants patch their hint in place in 0.06–4.7 ms per mutation, five to six orders of magnitude faster than the 56–686 s full re-run of the preprocessing phase. Their online phase stays competitive with ChalametPIR and $\mathsf{KPIR}^{\mathsf{index}}$ in both asymptotic and concrete cost. We deploy RisePIR-S as a privacy-preserving eth_getBalance service over the $2.05 \times 10^{8}$ accounts of Ethereum mainnet, so that a wallet reads a balance without revealing to its RPC provider which account it holds. The running service answers a private query in 0.69 s and absorbs each block's changes in 5.6 ms, well inside the 12 s block interval. The filter and RisePIR ship as an open-source Rust implementation, together with the benchmark harness behind every number in this paper.

Polynomial commitment schemes (PCSs) are fundamental cryptographic primitives, with applications to SNARKs, data availability, and privacy preserving protocols. Many efficient transparent PCSs are built from interactive oracle proofs of proximity (IOPPs) for codes in the Hamming metric. In constructions based on the fast Reed-Solomon IOPP (FRI), low degree polynomials are encoded as Reed-Solomon (RS) codewords over suitable evaluation domains, and FRI is used to test proximity to the RS code. The efficiency of this approach relies on fast Fourier transform (FFT) based encoding and recursive proximity testing through folding operations. Motivated by applications of rank metric codes in post quantum cryptography, random linear network coding, and distributed storage, we develop an analogous framework based on Gabidulin codes, the rank metric counterparts of RS codes. These codes encode $q$-linearized polynomials of bounded $q$-degree over $\mathbb F_{q^m}$ by evaluating them at $\mathbb F_q$-linearly independent points in this field. We construct a recursive FFT for these polynomials and show that its algebraic structure supports both proximity testing for Gabidulin codes and succinct verification of polynomial evaluations, yielding a FRI-style PCS for $q$-linearized polynomials. Our contributions are as follows. \begin{enumerate} \item[(1)] \textbf{FFT algorithms for $q$-linearized polynomials.} For every $O(1)$-smooth positive integer $n\mid m$, we construct an $\mathbb F_q$-linearly independent evaluation set $\mathcal A\subseteq\mathbb F_{q^m}$ of size $n$. On this set, we present FFT and inverse FFT algorithms for evaluating and interpolating $q$-linearized polynomials of $q$-degree less than $n$ over $\mathbb F_{q^m}$. Both algorithms require $O(n\log n)$ operations in $\mathbb F_{q^m}$. Consequently, Gabidulin codes defined over $\mathcal A$ admit encoding with the same complexity. \item[(2)] \textbf{A FRI-style IOPP for Gabidulin codes.} The recursive structure of our FFT induces a folding operation that reduces a Gabidulin code instance of length $n$ to one of length $n/2$. Combining this operation with recent proximity gap results for Gabidulin codes, we construct a FRI-style IOPP, which we call the Fast Gabidulin IOPP (FGI). The soundness analysis accounts for the Frobenius twists introduced by folding and their effect on rank metric proximity. \item[(3)] \textbf{A FGI based PCS for $q$-linearized polynomials.} The usual quotient based opening reduction in PCSs for ordinary polynomials does not directly preserve for $q$-linearized polynomials. We instead use the FGI folding structure to recursively reduce the proximity claim and the evaluation claim together. Combined with Merkle tree commitments, this yields a transparent PCS for $q$-linearized polynomials with polylogarithmic proof size and verification time. \end{enumerate}

The increasing deployment of unmanned aerial vehicles (UAVs) in communication, surveillance, and other mission-critical applications has created a growing requirement for efficient mechanisms to preserve the integrity of exchanged data. UAV platforms may operate under computational, memory, energy, and communication constraints, making lightweight cryptographic techniques an important consideration for secure data processing. This paper investigates the applicability of lightweight cryptography for UAV data integrity using two extendable-output functions (XOFs), Ascon-XOF128 and SHAKE128. A mathematical framework is developed to represent UAV messages, cryptographic processing, integrity verification, and relevant security and performance metrics. The two XOF constructions are analyzed with respect to their internal structures, sponge-based processing, security properties, computational characteristics, and suitability for resource-constrained UAV communication. A comparative evaluation framework is established using message-size and output-length variations, with performance and integrity-related measures including execution time, throughput, computational cost, memory usage, communication overhead, and Hamming-distance-based analysis. The study aims to provide an evidence-based comparison of Ascon-XOF128 and SHAKE128 for UAV data-integrity workloads and to identify the practical trade-offs between lightweight resource requirements and cryptographic integrity performance.

The cosine function is widely used in machine-learning applications, but evaluating it on secret-shared data is difficult. Conventional approaches use polynomial approximations or lookup tables, whose costs grow substantially over large input domains. More recent protocols first reduce the private input modulo the cosine period, but securely performing this modular reduction also incurs significant cost. We present a period-aligned two-party cosine protocol. Based on the cosine addition rule, it rescales each share so that a wrap of the input modulus corresponds to a full $2\pi$ period and therefore does not change the recombined cosine. Each party evaluates sine and cosine locally on its share, while the secure computation uses only two cross-party products and one fixed-point output conversion. We evaluate the protocol directly on synthetic inputs and within private RFF-based RBF-SVM prediction. Comparisons with the protocol of Xing et al. (NDSS 2025) and Guo et al. (USENIX Security 2026) demonstrate better efficiency of our proposed protocol.

State-of-the-art lattice-based cryptography requires a power-of-two cyclotomic field that limits the attainable security levels, or a module structure for which the cost grows quadratically in the module rank. Radical rings were recently proposed as a solution in the context of Learning With Errors (LWE) based Key Encapsulation Mechanisms (KEMs) with heuristic hardness arguments for the Ring-LWE security and failure probability. We develop the Learning With Rounding counterpart, Radical Ring-LWR (RR-LWR). We give a proved closed-form bound on the distortion incurred from the error sampling independent of the radical ring parameters: this places RR-LWR inside the regime identified by Peikert as safe for instantiating Ring-LWE/LWR. We instantiate two schemes: Mithril, an IND-CCA KEM, and Octarine, an EF-CMA signature scheme. They are built on a single radical-ring arithmetic foundation based on powers of two (favorable for sampling, rounding and masking) and we provide security reductions in the QROM to RR-LWR and SelfTarget-RR-SIS, a radical-ring variant of SIS. We show that the KEM failure probability estimators used for power-of-two cyclotomics are insufficient and provide an exact solution tailored to the RR-LWR setting. Finally, we instantiate Mithril and Octarine with concrete parameters and benchmark optimized AVX2 and Arm Cortex-M4 implementations, showing that both are competitive with (and in some cases significantly faster than) the MLKEM and MLDSA standards.

The post-quantum migration for key agreements and signatures being well underway, the focus naturally shifts to other properties and primitives that still lack efficient solutions. One such area is that of privacy-enhanced primitives, with a growing number of post-quantum constructions. Among the most fundamental are group signatures, which represent an important milestone of anonymity and accountability towards more involved designs. However, despite recent progress, most compact lattice constructions are either computationally intensive or suffer large key materials, or both. In this paper, we introduce a new lattice group signature scheme that reaches compact signatures and keys, while being runtime-efficient in all its procedures. Our key element is a new tag-based gadget sampler that properly interfaces with NTRU, then benefiting from the desirable properties of such trapdoor frameworks for advanced constructions while leveraging the compactness of NTRU. Although applied to group signatures, our sampler may be of independent interest and used for more expressive privacy-driven primitives like anonymous credentials. We also introduce two assumptions, which can be seen as hybrid versions of NTRU and ISIS, that independently underly the security of our group signature. Despite their similarities with the recently introduced NTRU-ISIS$_f$ assumption, they appear strictly harder and even admit reductions from R-ISIS in some parameter settings.

Bootstrapping is the bottleneck of BGV/BFV homomorphic encryption, and for large plaintext primes $p$ its cost is dominated by digit extraction. Recently, this stage has been accelerated along two separate routes. The first lowers the degree of the digit-extraction polynomial: the bounded-support construction of Ma et al. (Eurocrypt'24) confines its support, and the order-four filter of Xiong et al. (to appear in Asiacrypt'26) removes three quarters of its monomials. The second lowers the depth of its evaluation: the Galois norm map of Okada et al. (Asiacrypt'23) and Zhao et al. (Crypto'26) evaluates a degree-$d$ factor in logarithmic depth. However, how the two routes relate and whether they compose has remained open. We propose a symmetry-graded framework that views the two evaluation routes as commuting group actions on the digit-extraction polynomial. Under this unified perspective, the existing evaluators correspond to different specializations of $\mathrm{cost}(D;r,d)$. For lower degree, we identify a novel rank-two lattice structure underlying digit extraction. The crystallographic restriction limits the filter order to $r\in\{1,2,3,4,6\}$. In particular, the methods of Ma et al. and Xiong et al. correspond to $r=2$ and $r=4$, respectively. Moreover, our framework derives a sparser order-six digit-extraction polynomial, enabling order-six symmetry for Mersenne primes. For lower evaluation cost, we construct a composed evaluator that first folds $P_A$ using the scalar filter and then evaluates the folded polynomial via the slot ring's Galois norm map. Since the rotation and Frobenius actions commute, the two optimizations can be combined within the same framework. Consequently, for any $(p,m)$ we select the optimal $(r,d)$ and evaluate digit extraction in $2\sqrt{D/(rd)}+O(\log D)$ non-scalar multiplications. On 13 general cyclotomic rings at $\geq 80$-bit verified security, our single-threaded HElib implementation improves upon the state-of-the-art evaluator of Ma et al., accelerating digit extraction by $2.4$–$4.9\times$ and thin bootstrapping by $1.3$–$2.8\times$, while modifying only the digit-extraction stage. In particular, on Ma et al.'s set IV with the Mersenne prime $p=8191$ and set V with $p=65537$, digit extraction is accelerated by $3.6\times$ and $3.8\times$, respectively, reducing the total bootstrapping time from 180.4 s to 85.5 s and from 217.6 s to 103.1 s. The implementation is publicly available, and the core analysis is machine-checked in Lean 4.

The growing use of machine learning (ML) has raised concerns that an ML model may reveal private information about an individual who has contributed to the training dataset. To prevent leakage of sensitive data, we consider using differentially-private (DP), synthetic training data instead of real training data to train an ML model. A key desirable property of synthetic data is its ability to preserve the low-order marginals of the original distribution. Our main contribution comprises novel upper and lower bounds on the excess empirical risk of linear models trained on such synthetic data, for continuous and Lipschitz loss functions. We perform extensive experimentation alongside our theoretical results

Private aggregation schemes enable aggregation of sensitive data across clients without leaking any individual client's input. Their applications include privacy-preserving federated learning, private heavy hitters, and anonymous systems. Many private aggregation schemes assume two non-colluding servers and aim to guarantee privacy even when one server is malicious, i.e., the malicious server learns an aggregation result that includes all honest client inputs. However, many private aggregation schemes in the literature fail to achieve privacy, which we believe is in large part due to a lack of formalism for the nuanced variations of privacy guarantees. In this work, we present ideal functionalities for several variants of private aggregation. We also formalize a common paradigm underlying most prior private aggregation schemes. The formal treatment helps us identify security flaws or underspecifications in existing private aggregation schemes. We then present modular modifications or fill in critical details to help prior schemes in the share-aggregate paradigm securely realize the private aggregation functionalities we formally define, including in settings where clients may have unreliable networks.