Papers updated in last 183 days (Page 6 of 2708 results)
Efficient and Compact High-order Masking Raccoon on Memory Constrained Devices
Raccoon, presented at CRYPTO 2024, is a provably secure lattice-based signature scheme featuring an $O(d \log{d})$ masking overhead. Although it did not advance beyond the first-round of NIST's additional call for post-quantum digital signatures, Raccoon remains a promising candidate due to its low masking overhead and strong provable side-channel resistance.
This paper proposes the first efficient and compact implementation of high-order Raccoon on the ARM Cortex-M4, with a focus on optimizing its polynomial multiplication, sampling, and memory consumption.
1) For polynomial multiplication, we present a consecutive 32-bit NTT/INTT implementation for the two moduli in Raccoon, enabling optimal 3+3+3 layer merging to reduce memory-access overhead, together with extensive lazy reduction to minimize modular reductions. As a side contribution, we propose a novel negative double Montgomery reduction technique to accelerate double modular reductions in multi-moduli NTT.
2) For polynomial sampling, we identify and resolve a previously overlooked performance bottleneck caused by frequent incremental SHAKE256 invocations for small data chunks on ARM Cortex-M4. By transitioning to the one-shot approach, we achieve speedups of at least $1.80\times$ across all sampling routines in Raccoon.
3) Finally, we explore memory-saving techniques to enable the practical deployment of high-order masked Raccoon (up to 32 orders) on resource-constrained IoT devices.
The proposed implementations outperform the Raccoon reference implementation by $1.85\times$-$2.25\times$. Notably, high-order masked Raccoon-192 outperforms masked Dilithium3 by $3.12\times, 8.07\times$, and $2.71\times$ at masking orders $d=2$, $4$, and $8$, respectively. Finally, the leakage evaluations confirm that the second-order Raccoon implementation provides strong resistance to differential power analysis (DPA) once micro-architectural transitional leakages are mitigated.
On the Common Bias of Majorities: Poly-Time Attacks on THR-XOR PRGs
Pseudorandom Generators (PRGs) based on Threshold-XOR predicates with large locality and high stretches have recently gained traction, since they lend themselves as shallow weak Pseudorandom Functions (PRFs) to fast multiparty computation protocols. In this work, we present novel fast attacks on such PRGs that achieve substantial advantages. Concretely, we break the security levels of most parameters collected by Boura, Couteau, Perrin and Rotella (ToSC'25), as well as those proposed by Fu, Li, Lyu and Liu (EC'26). On the asymptotic side, we prove that our attacks achieve an advantage of $n^{-n/a}$ where $n$ denotes the seed length and $a$ the locality of threshold predicates. As a consequence, when $a \in \Theta(n)$, we get poly-time attacks with noticeable advantage. These results close current gaps on the theoretical study of THR-XOR based Goldreich PRGs.
Additionally, we demonstrate how the attack advantage can be amplified for PRGs with large output lengths (which are common in the context of weak PRFs). Finally, we discuss alternative predicates for Goldreich PRGs that resist all currently known attacks.
Hidden parabolic subgroups of $\mathrm{GL}_n$ over finite chain rings
We give a bounded-error quantum polynomial-time algorithm for finding hidden parabolic subgroups of $\mathrm{GL}_n(R)$ over any effectively presented finite chain ring $R$. We call auxiliary group elements or subgroups used to extract information through oracle queries \emph{probes}. For chain length at least two, elementary abelian socle probes first recover the complete flag modulo the maximal ideal. When the residue field has size $q\ge3$, we reconstruct the flag recursively, lifting rank-one terminal members one digit at a time. The intermediate digits reduce to abelian hidden subgroup problems, while the final digit is a finite-field multiple-shift problem solved using learning from subset and Fourier sampling. For $q=2$, where distinct flags can have the same stabilizer, we instead lift the conjugate parabolic subgroup through the congruence filtration. A final linear system determines it modulo normalizer directions. The algorithm outputs generators with probability at least $1-\epsilon$ in time $\mathrm{poly}(n,\log|R|,\log(1/\epsilon))$. Consequences include $\mathrm{GL}_n(\mathbb{Z}/N\mathbb{Z})$ for every $N\ge2$ and, with an explicit maximal-order presentation, $\mathrm{GL}_n(\mathcal{O}_K/N\mathcal{O}_K)$ for number fields $K$.
Faster Logical Operations from Discrete CKKS
We study non-arithmetic operations for BFV with arbitrary plaintext moduli and for large-modulus GBFV. Existing approaches either rely on interpolation over large plaintext spaces or use digit representations that are efficient for logic but poorly matched to native arithmetic. We build conversions between BFV/GBFV and Discrete CKKS, so that radix-based integer computation in Discrete CKKS can be used as a reusable backend. For fixed radix base, comparison uses $O(\log p \log\log p)$ bootstrappings for BFV with plaintext modulus $p$ and $O(\log\log p)$ bootstrappings for GBFV with associated modulus $p=b^\ell+1$.
Stronger Security for Blind Signatures with Attributes
Single-use anonymous credentials are issued once and allow users to unlinkably authenticate exactly once. Recent anonymous-token and age-verification systems increasingly rely on such credentials to minimize credential reuse and simplify revocation. These systems are typically instantiated from blind signatures, yielding lightweight credentials whose presentation reduces essentially to signature verification. Many deployments additionally require embedded attributes and selective attribute disclosure. While this functionality can be achieved through Blind Signatures with Attributes (BSAs), only a handful of blind-signature constructions support attributes, and the security guarantees of selective disclosure are not yet fully understood or properly formalized.
We close this gap by first revisiting the security definitions for BSAs and introducing stronger notions capturing secure showing under partial attribute reveal. We then present a generic transformation that lifts a broad class of two- and three-move blind signatures into BSAs supporting embedded attributes and selective disclosure. Our construction uses Merkle commitments and cut-and-choose techniques to enforce attribute consistency and achieves concurrent one-more unforgeability, upgraded blindness, and the stronger secure-showing notion. Finally, we prove that the well-known Anonymous Credentials Light (ACL) construction satisfies these stronger notions without modification in the ROM+AGM.
Efficient Private Set Intersection and Searchable Encryption using Homomorphic Bloom Filters
Existing encrypted search and private set intersection (PSI) protocols struggle to reconcile post-quantum security with practical efficiency, often leaking search and access patterns or requiring prohibitively deep fully homomorphic encryption (FHE) circuits. We address these limitations by introducing a new Homomorphic Bloom Filters (HBF) framework, a quantum-resilient framework that embeds length-$m$ Bloom filters directly into the plaintext space of an RLWE-based FHE scheme, enabling shallow homomorphic evaluation and matching without structural leakage.
Building on HBF, we construct a searchable encryption (SE) scheme and a private set intersection (PSI) protocol, both based on a depth-1 homomorphic missing-bit circuit. The SE scheme requires no rotations or bootstrapping at server side and incurs no additional computational cost as the number of query keywords increases.
The PSI protocol reduces each packed Bloom-filter comparison to a single ciphertext--plaintext multiplication, with cost depending on the Bloom-filter length rather than direct element-wise comparisons with the responder's set.
This framework confines leakage to benign dataset dimensions, tunable false-positive rates, and other public metadata, thereby eliminating explicit pattern leakage.
DASTE: Decentralized Ad-Hoc Access-Structured Threshold Encryption with Dynamic Policy Evolution
We introduce DASTE, a decentralized encryption primitive for auditable access control in settings where users independently generate public keys, register them on an immutable ledger, and decrypt only through collaboration.
In DASTE, a sender encrypts under an access structure (e.g., an access tree / LSSS) whose leaves are concrete registered public keys selected at encryption time.
A ciphertext can therefore be opened only by a qualifying coalition of registered key holders that jointly reconstructs the masking secret.
DASTE is designed for dynamic policy-governed environments in which access conditions may need to change after encryption.
To support this, we provide ciphertext-only policy evolution operations, including semantically neutral insertion, threshold escalation, subtree revocation, and ciphertext rerandomization, that update ciphertexts without reissuing user secret keys and without requiring plaintext access.
We give two instantiations: a classical discrete-log-based construction, included as a conceptual baseline, and a post-quantum construction based on decisional Ring-LWE. For the RLWE construction, we prove coalition-bounded IND-CPA security via a standard hybrid argument.
Together, these results yield a ledger-anchored, access-structured, post-quantum threshold encryption framework suitable for decentralized key management and governance-oriented decryption workflows.
DISCO*: DIstributed and SCalable Oblivious Joins and Oblivious Primitives
Trusted Execution Environments (TEEs) let clients outsource computation to untrusted clouds, but they remain vulnerable to side-channel and leakage-abuse attacks. Recent work closes this gap by combining hardware enclaves with oblivious computation, which offers strong security guarantees yet struggles to meet the performance and scalability demands of real-world deployments. In this work, we present DISCO, the first scalable, distributed, and fully oblivious database system that seamlessly combines hardware enclaves with cutting-edge oblivious primitives and novel optimizations that significantly reduce inter-server communication overheads. What distinguishes DISCO from prior work is a suite of distributed frameworks that unlock parallel computation and fundamentally shift the design paradigm of distributed oblivious systems, enabling practical deployment at scales that were unattainable with previous solutions. We provide a thorough evaluation of the performance of our system on both synthetic and real-world datasets. Our evaluation demonstrates that our design significantly reduces the gap between theory and practice, achieving 88× speedup over Jodes and 180× over SODA on non-foreign key joins with N = 2²⁵ elements. Most importantly, we report, for the first time, results for computations at the terabyte scale.
Membership Inference in Privacy-Preserving Vector Search
Vector retrieval increasingly runs over sensitive embedding databases. Backend-compatible protections are desirable in such settings in that they transform the plaintext vectors while leaving the search algorithm itself unchanged. However, the protected database then leaks some geometry, that is, information about the distances between the stored vectors. We study membership-inference attacks on such leakage given a single database snapshot and known plaintexts. Our central finding is that membership privacy depends on how much geometry is revealed and on whether known plaintexts can be linked to positions in the snapshot, and that the effect of each of these depends on the other.
We first break the prior Scale-and-Perturb (SAP) scheme of Fuchsbauer et al. (FGHO, SCN 2022) with no known plaintexts. Empirically, our attack achieves advantage 0.997 on MS-MARCO. We then introduce Rotate-and-Perturb (RAP), a special case of a scheme FGHO call SAP-I and leave unanalyzed. For uniform data on the sphere, we prove perfect membership privacy with no known plaintexts. For fixed noise parameter β ∈ (0, 2], achieving constant advantage requires a number of known plaintext-ciphertext pairs at least logarithmic in the database size, provided that number is below the embedding dimension. Empirically, our attack reaches advantage 0.5 with 3 such pairs at database size 100 and 7 at 100,000 on text embeddings.
We also study two more approaches, namely ideal distance-comparison-revealing encryption (DCRE) and an encrypted HNSW index using function-hiding inner-product functional encryption. Ideal DCRE remains vulnerable to known plaintext-ciphertext pairs. On the tested MS-MARCO databases, our attack on the encrypted HNSW index requires knowing 19–32% of the database and their corresponding index vertices to reach advantage 0.5.
Finally, we study augmentations to these schemes to mitigate our attacks, shuffling and secret projection. Together, they substantially increase the number of known plaintexts needed by our tested attacks on RAP and comparison-only leakage.
High-Precision CKKS with Focal Units
In CKKS, higher precision requires a larger scaling factor, increasing modulus consumption during homomorphic arithmetic and leaving less modulus available after bootstrapping under the same modulus budget. We introduce Focused CKKS, which trades unused SIMD slots for precision through focused rescaling and key-switching based on cyclotomic units. These units reduce error in selected focus slots while allowing larger error in the background slots. Using only a $1/k$ fraction of the slots provides approximately $k$ times as many bits of precision at the same scaling factor and CKKS parameter setting. Such a high-precision multiplication costs the same as an ordinary CKKS multiplication, with each focus slot supported by $(k-1)$ background slots. More generally, the construction supports different precision requirements across slots.
We also construct a bootstrapping procedure tailored to Focused CKKS. Only the base modulus at the bottom level needs to grow with the target precision; the remaining bootstrapping computation maintains approximately the same modulus consumption by using fewer slots. By adapting the high-precision bootstrapping based on discrete CKKS and performing its error-cleaning step in Focused CKKS, we further reduce this base modulus by approximately the same factor $k$.
Optimal Proofs of Sequential Work
In a proof of sequential work (PoSW), introduced by Mahmoody, Moran and Vadhan [MMV'13], a verifier can be convinced that a prover performed a computation of $T$ sequential steps. Such a proof is $(\delta, \lambda)$-sound if a malicious prover making at most $(1-\delta)T$ sequential steps can produce a valid proof only with probability $2^{-\lambda}$, even when using massive parallelism.
Besides time-lock puzzles (TLPs) and verifiable delay functions (VDFs), PoSW are one of the central primitives in timed cryptography. Unlike TLPs or VDFs, PoSW can be constructed just from hash functions, with a security proof in the random oracle model. Existing PoSW are based on graph labeling: the prover must sequentially compute a labeling of a graph of $T$ nodes, where each node's label is the hash of its parents' labels.
The [MMV'13] construction uses node-depth-robust graphs. A simple and much more efficient construction was later given by Cohen and Pietrzak [CP'18]. In the [CP'18] PoSW, getting $(\delta, \lambda)$ soundness requires transmitting $\Omega((\lambda\log T)/\delta)$ hash outputs. The underlying graph has average in-degree $\Theta(\log T)$, so labeling takes $\Theta(T\log T)$ total hash inputs.
Our first result is a lower bound: any efficient graph-labeling-based PoSW that is $(\delta, \lambda)$-sound requires the prover to send $\Omega((\lambda\log T)/\delta)$ labels. To prove this result, we relate PoSW soundness to a cut-depth game and bound this game using a refinement of Valiant's depth-reduction argument. This shows that [CP'18] achieves asymptotically optimal communication and verifier hash-input complexity, while leaving open whether its $\Theta(\log T)$ average indegree (and thus $\Theta(T\log T)$ prover hash-input complexity) is necessary.
Our second result is a new PoSW that matches these lower bounds up to constant factors and has maximum indegree two. In particular, it reduces the honest prover's total hash-input complexity from $\Theta(T\log T)$ to $\Theta(T)$ while retaining $O((\lambda\log T)/\delta)$ communication and verifier hash-input complexity.
Efficient NTRU+ Implementations on Cortex-M
Post-quantum cryptography on embedded devices requires implementations that perform cryptographic operations efficiently within limited computation and memory. Most lattice-based KEMs use 2-way NTTs over power-of-two cyclotomic rings, and their embedded implementations have been studied extensively. In contrast, implementations of schemes based on 3-way NTTs, which combine radix-3 and radix-2 layers, remain scarce. This work therefore presents efficient implementations of NTRU+, a KEM built on 3-way NTTs, on Arm Cortex-M0+, M3, M4, and M7. We configure the layer fusion, modular arithmetic, and instruction scheduling of the 3-way NTT for each parameter set and core. We also introduce ω-folded front layers, which compute the first two layers of the forward NTT on ternary inputs without modular reduction. Based on these techniques, we present two implementations. The speed-optimized implementation keeps operands as full polynomial arrays to prioritize execution time. The memory-optimized implementation reuses a single polynomial workspace and regenerates the required operands in pieces aligned with radix-3 blocks. On physical boards, the speed-optimized implementation reduces execution time by up to 52.43% compared with the official optimized C implementation. The memory-optimized implementation reduces peak stack usage by up to 82.60% while running faster than the official optimized C implementation in every KEM operation. A controlled NTT-replacement experiment and per-technique comparisons show that the same technique can have different effects depending on the instruction set and pipeline of each core.
A Systematic Evaluation of Fault Attacks and Countermeasures on ML-DSA Rejection Sampling
This paper presents a systematic evaluation of fault attacks on the rejection sampling of ML-DSA (FIPS 204) and of the countermeasures proposed against them. Using the identity \(\mathbf{Az} - ct = \mathbf{Ay} - c\cdot\mathbf{s}_2 = \mathbf{r}\), we prove that the quantity compared by the "third rejection test" of patent WO2025261784A1 is exactly \(\mathbf{r}_1\), which is already produced during signing, while check 2 passing is what implies \(\mathbf{r}_1 = \mathbf{w}_1\). The third check therefore re-verifies a condition that check 2 guarantees, rather than being an independent test. We further show that the six embodiments claimed by the patent reduce to only two independent conditions, both covering only skips of the second check. An experiment with 30,000 fault injections confirms that all six embodiments detect the skip of the \(\mathbf{z}\)-norm check — the route that directly recovers the signing key \(\mathbf{s}_1\) — at a rate of zero. Building on this blind spot, we fully recover \(\mathbf{s}_1\) against a third-check-protected implementation (all 1024 coefficients of the four polynomials) under randomized signing, the default form in FIPS 204. We then report a complete evaluation matrix over three fault models and two implementation variants, and show that the third check and sign-then-verify are complementary with neither being sufficient on its own: the latter fails entirely against the second-check skip on the reference implementation (all faulty signatures pass verification), while the cheapest embodiment of the former detects every exploitable signature, whereas against the \(\mathbf{z}\)-check skip only sign-then-verify is effective. Their union covers every attack path we evaluate, and deploying either one alone leaves a complete attack path open. Overhead measurements show that this embodiment costs 0.04–0.05% of a signing on x86-64 and 0.83% on Cortex-M4, about 460–590 and 48 times less than sign-then-verify on the same platforms (22–24% and 40.0%, respectively). We therefore recommend deploying both, at a combined cost that is almost entirely sign-then-verify's.
Fault-Induced Nonce Repetition in Threshold Lattice Signatures: A Reveal-Structure Criterion, Cross-Scheme Analysis, and Detection Boundaries
Threshold ML-DSA is regarded as a deployment model that eliminates single-point key risk, and the NIST threshold call (IR 8214C) has likewise attracted many proposals. Existing security analyses, however, generally assume malicious or compromised protocol participants. For the threat of "physical faults in the devices of honest participants," single-party lattice signatures have been studied systematically for over a decade, whereas threshold schemes, to our knowledge, have not yet been systematically evaluated. We show that fault-induced cross-session sample replay by one party leaks that party's share, and that mechanisms such as RNG state rollback can trigger it. In a t-of-n deployment, the attacker need only fault t devices to recover the complete signing secret, while every signature is fully valid when examined individually; the hedged nonce, commitment/session binding, and fail-closed final verification all remain untriggered. We verify the attack end to end on Mithril (ePrint 2026/013, USENIX Security 2026): two implementation versions, six (t,n) configurations, and 96/96 statistical scan groups all achieve exact recovery, with residual error identically 0 and no lattice reduction. The secret recovered solely from the coordinator-visible transcript can be used to forge a signature on the spot that passes the implementation's FIPS 204 verifier. We further elevate the attack to a class-level criterion. The attack surface is determined by the reveal structure, that is, by whether the scheme reveals per-party responses to a party visible to the attacker, rather than by the distributional properties of the nonce. Quorus's structural immunity thus comes from non-reveal and is unrelated to uniformity. TALUS can be broken via a double-spend path in which "one-time consumption of preprocessing is skipped". Trilithium's signing algorithm hands the Server's response share to the Client in plaintext, and [TALUS] classifies it as internally uniform (\(I = 0\)), making it an instance of the "statistically immune and fault-fragile" quadrant; the attack requires only 1 device fault. The simulator message "(ss, sid, [z']_S)" in the original proof, together with [Jarv26]'s verbatim copy of this algorithm, is the evidence for this determination; see Appendix D for the evidence tier. This yields two independent evaluation dimensions: the statistical axis \(I\) and the reproducibility axis (reveal structure). Different design levers allow the two axes to take values independently. All three quadrants already have instances: (reveal, \(I > 0\)), (non-reveal, \(I = 0\)), and (reveal, \(I = 0\)). Two cases lie on the anti-diagonal, [Trilithium] and [Kao26]. We design detection as two layers of transcript-level checks. The early-warning surface alarms on reveal-hash liveness and achieves 305/305 exact hits over the full corpus with zero false positives. The full-coverage surface runs the identification computation shared with the attack; within the feasible range of identification, there is no window in which the attack is usable but undetectable. §6.1 explains the difference in alarm timing. For imperfect faults, we prove the threshold law for full-key recovery \(m^* = (\ell-1)N+\lceil N/K \rceil\) and verify it coordinate by coordinate; for ML-DSA-44 the law gives \(768+\lceil 256/K \rceil\), namely 896 at K=2 and 787 at K=14. This reveals the trade-off nature of K. All claims have undergone a tool-assisted verification workflow with three analysis paths that are independent of one another. The authors direct the workflow; §8.2 describes its execution mode and artifact disclosure.
Fully Anonymous Perfect Threshold Secret Sharing: Explicit One-Bit Construction and Rate Amplification
Secret sharing distributes a secret among participants so that only sufficiently large groups can recover it. Fully anonymous secret sharing also allows recovery from share values alone, without participant identities. Below the reconstruction threshold, the shares must look exactly like independent uniform random values, revealing neither the secret nor their holders' identities. Con, Li, and Mazor established that such schemes with error-free recovery exist for every threshold, leaving an efficient general construction open.
We give efficient constructions for every threshold 2 ≤ t ≤ n among n participants. For an L-bit secret, each share has L + O(t² log² n) bits. Sharing runs in expected polynomial time, and reconstruction runs in deterministic polynomial time. Our approach combines an efficient one-bit construction with a general transformation that uses it to protect a short message needed for anonymous reconstruction of a long secret. The additional share length has an upper bound depending only on the number of participants and the threshold. For a fixed participant count and threshold, the rate approaches one as secrets grow longer, while anonymity remains exact and recovery never errs.
Stay in Your Lane: Scalable Large-Integer Arithmetic in CKKS
Recent work has shown that the approximate homomorphic encryption scheme CKKS can perform exact modular arithmetic with large moduli. This enables high-precision integer computation: given bounds on the outputs of an arithmetic circuit, we can recover the exact integer results from the modular outputs using any sufficiently large modulus. The particular choice of modulus does not affect correctness. Long computations require periodic bootstrapping, which refreshes ciphertexts so that further operations remain possible. However, in Gao and Zheng's construction (Crypto '26) and its extensions by Wei et al. and Liu et al. (both ePrint '26), converting between the representations used for arithmetic and bootstrapping, which is required at every refresh, becomes increasingly expensive as the integers grow.
We reduce this overhead by choosing message spaces that fit the representations already used inside standard CKKS bootstrapping. Building on GBFV (Geelen and Vercauteren; Eurocrypt '25) and its interpretation within CKKS (Kim; Asiacrypt '26), we organize encrypted data into independent polynomial “lanes” (namely, the factors of $(\mathbb{R}[X]/(X^n+1))^{N/n}$) that already appear as intermediate representations during bootstrapping (as intermediate stages of CoeffToSlot and SlotToCoeff). This avoids additional conversions specific to the message encoding. Supported message spaces include integers modulo $\beta^n+1$, where $n$ is a power of two and $\beta\geq2$ is a small integer, selected prime fields of up to $1\,024$ bits, and extension fields. For integer messages, we also give conversions in both directions between an arithmetic representation (for operations on whole integers) and a digit representation (for operations on their encrypted base-$\beta$ digits).
We evaluate our construction and our port of Gao and Zheng in Lattigo on the same AWS Graviton5 hardware, using one thread at $N=2^{16}$ and targeting $128$-bit security. Our bootstrapping latency remains nearly constant for $8\leq n\leq2^{14}$ and stays below $8$ seconds across all tested message spaces, including $24\,577$-bit moduli ($n=4\,096$, $\beta=64$). For $8\leq n\leq1\,024$, this gives a speedup of $2.1\times$ to $6.8\times$ over the port, comparing arithmetic modulo $2^n+1$ with their arithmetic modulo $2^n$. These gains carry over to sustained computation: including bootstrapping to support arbitrary evaluation depth, we estimate amortized multiplication speedups of $3.2\times$ to $12.8\times$ over the port for $8\leq n\leq512$. As one concrete example, arithmetic bootstrapping takes $6.44$ seconds per ciphertext packing $16$ integers modulo $2^{4\,096}+1$. In sustained computation, the amortized cost is $0.22$ seconds per integer multiplication at over $4\,000$ bits of precision, including refreshing. Our arithmetic-to-digit conversion has per-call timings comparable to our implementation of Wei et al.'s conversion for $64\leq n\leq1\,024$ and $\beta=2$, and our analysis indicates better scaling for larger integers.
The Structure of Witness-Update Tradeoffs in Additive Positive Accumulators
An additive positive accumulator maintains a short public digest of a growing set while each accumulated element carries a membership witness. As new elements are inserted, old witnesses may need to be refreshed, creating a tradeoff between succinct public state and witness-maintenance cost. Previous lower bounds capture this tradeoff through particular scalar measures, such as the maximum lifetime update frequency [Qi, IACR Communications in Cryptology 2026] or the total number of witness updates [Bonneau--Chen--Christ--Karantaidou, CRYPTO 2025]. We instead characterize the structure of the entire labeled witness-update pattern.
Our main result reduces witness-update tradeoffs to optimization over bounded-right-depth ordered binary trees. Except with negligible probability, every execution of a sound, NeedUpd-complete accumulator admits such a tree whose prescribed updates can be matched injectively to genuine updates of the same witnesses occurring no earlier. Conversely, every feasible tree profile is realized exactly by a bounded-width online merger [Mahmoody--Qi, ITC 2023], and efficiently generated merger schedules admit Merkle-forest implementations. Thus the same family of trees governs both the security lower bound and the constructive side of the tradeoff.
Because the tree certificate is independent of the maintenance objective, the same structural event simultaneously controls every nonnegative coordinatewise nondecreasing function of the lifetime update vector. This recovers the known maximum- and total-update bounds as special cases and yields heterogeneous weighted, cohort, threshold, top-$k$, and nonlinear bounds from the same theorem. Heterogeneous costs model settings in which different witness holders face different computational, communication, availability, or delegated-maintenance costs. For efficiently specified weights, an optimal tree can be computed in polynomial time and realized by the corresponding merger schedule.
The framework also extends beyond lifetime update counts. For per-witness update prices that are nondecreasing in time, the same tree optimization remains exact and yields matching lower bounds and merger realizations, together with an efficient dynamic program. More generally, arbitrary nonnegative time-dependent prices admit structural lower bounds. Our results therefore give a structure-first framework in which cryptographic security first forces a common combinatorial constraint on the update process, and different maintenance objectives are optimized only afterwards.
Vespa: Efficient Secure Aggregation with Integrity Defense under Server Privacy
Secure aggregation with input validation enables a server to securely compute the summation of private data from multiple clients while verifying that the inputs satisfy specific constraints. However, the practical deployment of this paradigm at scale is hindered by two primary limitations. First, existing schemes suffer from severe efficiency bottlenecks due to their reliance on generic, computationally expensive zero-knowledge proofs (ZKPs). Second, the scope of input validation is currently restricted to norm checks (e.g., $L_2$ and $L_\infty$) against public bounds.
This paper presents \textsf{Vespa}, a single-server secure aggregation scheme that simultaneously achieves practical efficiency and expands validation capabilities to support both \textit{norm checks against public bounds} and \textit{similarity checks against private server inputs}. Specifically, we design a novel validity-weighted secure aggregation protocol over committed inputs, built upon highly efficient vector oblivious linear evaluation (VOLE). To efficiently realize input validation, we introduce customized $L_2$ and $L_\infty$ norm checks based on VOLE-based ZKPs, centered around optimized range proofs with reduced range sizes. Furthermore, we extend our framework to support advanced similarity-based checks against private server inputs, instantiated with widely used Euclidean and cosine similarities. This allows \textsf{Vespa} to first filter out invalid inputs using norm checks, followed by performing fine-grained validation via similarity metrics.
We compare our scheme with the state-of-the-art secure aggregation works, including RoFL (S\&P 2023), ACORN (USENIX Security 2023), and Armadillo (CCS 2025), and extensive evaluation shows that our $L_2$ and $L_\infty$ norm checks achieve runtime improvements of up to $2\sim 3$ and $1\sim 3$ orders of magnitude, respectively.
Our similarity checks also achieve practical performance, consuming only around $94$ seconds for an $818$k-entry vector.
Further Elaborations on the Provable Dual Attack
The dual attack is one of the main strategies for attacking the learning-with-errors (LWE) problem. A recent line of work aims at provable analyses of dual attacks that rely on as few heuristic assumptions as possible.
We present a provable dual attack that recovers a subvector $\boldsymbol{s}_{\mathrm{guess}}$ of the LWE secret, and we derive an explicit lower bound on its success probability without any heuristic assumption. Our analysis unifies the provable approaches of Pouly and Shen (EUROCRYPT 2024) and Bashiri and Wiemers (J. Math. Cryptol. 2025), and removes the very few informal assumptions left in the previous works. Inspired by Qu, Tian, Wang, and Xu (ePrint 2026/2117), the dual vectors are sampled from the sublattice spanned by the first vectors of a reduced basis. Our key ingredient is a first-moment estimate for the wrong candidates, which is based on the exact uniform distribution of some appearing cosets. This leads us to discard certain typical assumptions on shortest vectors from previous works.
We apply our results to ML-KEM, under one heuristic on its structured matrix, and improve on the first provable dual attack by $22$ to $52$ bits without any assumption on the rank of the sublattice, and by $47$ to $100$ bits ($21$ to $56$ bits compared with Qu, Tian, Wang, and Xu (ePrint 2026/2117)) if this rank is bounded as in Qu, Tian, Wang, and Xu (ePrint 2026/2117). We also apply our results to ML-DSA, and demonstrate the attack experimentally on small instances.
Our results do not threaten the security of ML-KEM or ML-DSA.
Last updated: 2026-10-20
Regular Syndrome Decoding Is Easier Than Previously Estimated
The Regular Syndrome Decoding (RSD) problem is a structured variant of classical Syndrome Decoding and underlies a growing number of efficient cryptographic constructions, including zero-knowledge protocols, pseudorandom correlation generators, and MPC-in-the-Head signatures. Although RSD is generally believed to be computationally hard, recent works have shown that algebraic attacks can outperform information-set decoding on important RSD parameter regimes.
Building on this line of work, we revisit the concrete hardness of RSD and show that many widely used parameter sets are substantially easier to solve than previously estimated.
This improvement stems from a refined hybrid-algebraic attack that exposes and removes
a previously overlooked source of concrete complexity: the joint blockwise placement of zero-coordinate guesses and syndrome-based variable
eliminations. Rather than treating the two guessing stages and linear
elimination as largely separate choices, our method coordinates them
across all regular blocks so that the guessing penalty is balanced while
sufficient equations are retained for linearization. This gives a systematic
block-balancing principle for the entire guess–reduce–solve pipeline.
We reassess several RSD-based applications, including Ferret (CCS~2020), Wolverine (IEEE S\&P~2021), and committed VOLE (CCS~2025). Our estimates place at least one parameter set per application below its 128-bit target, with losses approaching 67~bits. On PCG benchmarks, we improve previous best attack costs by up to 29.77 and 25.91~bits over non-binary and binary fields, respectively. Moreover, for the revised 128-bit PCG parameter sets of Liu et al. (EUROCRYPT~2024) evaluated here, estimated attack costs are all below $2^{111}$ field operations.
These results substantially revise the concrete-security landscape of RSD and indicate that several existing parameter choices overestimate the hardness of their underlying RSD instances.
ARION: Attention-Optimized Transformer Inference on Encrypted Data
Privacy-preserving Transformer inference (PPTI) is essential for deploying large language models (LLMs) such as BERT and LLaMA in sensitive domains. In these models, the attention mechanism is both the main source of expressiveness and the dominant performance bottleneck under fully homomorphic encryption (FHE), due to large ciphertext matrix multiplications and the softmax nonlinearity. This paper presents Arion, a non-interactive FHE-based PPTI protocol that specifically optimizes the computation of encrypted attention. First, for the three consecutive ciphertext matrix multiplications in multi-head attention, we introduce the double Baby-Step Giant-Step algorithm, which significantly reduces the number of ciphertext rotations. On BERT-Base, Arion achieves an 82.5% reduction in rotations over the state-of-the-art PPTI protocol MOAI (2025), corresponding to a 5.7x reduction in rotation cost. Second, we propose a linear–nonlinear fusion technique tailored to the softmax evaluation in attention. By decomposing softmax into shift-by-maximum, exponentiation, and reciprocal sub-steps and fusing them with the surrounding encrypted matrix operations, Arion enables efficient attention evaluation while remaining compatible with diverse ciphertext packing formats. We implement Arion using Lattigo and first evaluate attention kernels on popular LLMs including BERT-Tiny, BERT-Base, and LLaMA, confirming the practicality and scalability of the proposed optimizations for encrypted attention computation. For end-to-end applications, on classification tasks for several benchmark datasets, Arion attains accuracy comparable to plaintext inference and yields up to 2.5x end-to-end speedups over MOAI for BERT-Base.
Regular Syndrome Decoding Is Easier Than Previously Estimated
The Regular Syndrome Decoding (RSD) problem is a structured variant of classical Syndrome Decoding and underlies a growing number of efficient cryptographic constructions, including zero-knowledge protocols, pseudorandom correlation generators, and MPC-in-the-Head signatures. Although RSD is generally believed to be computationally hard, recent works have shown that algebraic attacks can outperform information-set decoding on important RSD parameter regimes.
Building on this line of work, we revisit the concrete hardness of RSD and show that many widely used parameter sets are substantially easier to solve than previously estimated.
This improvement stems from a refined hybrid-algebraic attack that exposes and removes
a previously overlooked source of concrete complexity: the joint blockwise placement of zero-coordinate guesses and syndrome-based variable
eliminations. Rather than treating the two guessing stages and linear
elimination as largely separate choices, our method coordinates them
across all regular blocks so that the guessing penalty is balanced while
sufficient equations are retained for linearization. This gives a systematic
block-balancing principle for the entire guess–reduce–solve pipeline.
We reassess several RSD-based applications, including Ferret (CCS~2020), Wolverine (IEEE S\&P~2021), and committed VOLE (CCS~2025). Our estimates place at least one parameter set per application below its 128-bit target, with losses approaching 67~bits. On PCG benchmarks, we improve previous best attack costs by up to 29.77 and 25.91~bits over non-binary and binary fields, respectively. Moreover, for the revised 128-bit PCG parameter sets of Liu et al. (EUROCRYPT~2024) evaluated here, estimated attack costs are all below $2^{111}$ field operations.
These results substantially revise the concrete-security landscape of RSD and indicate that several existing parameter choices overestimate the hardness of their underlying RSD instances.
SAT and Neural Network Filters for Misinjections in Fault Attacks
A misinjection, an injection that misses the fault form an attack assumes, can make an elimination fault attack discard the correct key. They occur when the attacker has not determined the timing of the device, and a random-delay countermeasure wider than the S-box layer can force them even on one who has. This paper presents a SAT filter that removes misinjections without the secret key, one injection at a time. It models the differential propagation from the injected round to the end of the cipher in SAT and rejects an injection when the model has no solution for the assumed fault and the observed ciphertext difference. The paper also presents a neural network filter, which passes an injection when the score of a network trained for the same decision is at least 0.5, and a combined filter, which passes it only when the SAT model of the injection also has a solution. We measure the filters on faults injected by clock glitching into GIFT-64, GIFT-128 and BAKSHEESH on a microcontroller, in three settings, a non-profiling attacker without and with a random-delay countermeasure and a profiling attacker with it. The SAT filter rejected none of the 14669 intended faults and, for the non-profiling attacker without the random-delay countermeasure, at least 0.940 of the misinjections at the full-diffusion round, over at least 385 each. For the same attacker it raises the success probability of ToFA on BAKSHEESH, which recovers the master key, from 5.2% to 61.2%, and the combined filter raises it to 96.2%, each over 2000 trials.
IISFA: Ineffective Instruction-Skip Fault Attacks on Bitslice Implementations
Redundancy countermeasures prevent differential fault analysis by withholding faulty ciphertexts. Ineffective fault analysis and statistical ineffective fault attacks exploit executions in which an injected fault leaves the result unchanged, using constraints on intermediate values or statistical bias to recover keys. In this paper, we present an Ineffective Instruction-Skip Fault Attack (IISFA) on bitsliced implementations protected by redundancy. A bitsliced instruction processes $m$ S-boxes simultaneously. Skipping it leaves the group unchanged exactly when all $m$ S-box inputs belong to its ineffective set, which we compute from the implementation. Each ciphertext output by the device therefore restricts all $m$ $n$-bit subkeys to candidates whose S-box inputs belong to that set. The ineffective probability specifies how often a uniformly random S-box input makes the skip ineffective, and its $m$-th power gives the ciphertext output probability for independent inputs. We determine which key candidates remain indistinguishable under a single target instruction. We give key-recovery procedures for both known and chosen plaintexts and combine different target instructions across queries, with one instruction skipped per execution. We calculate expected injection counts or enclosing intervals for the known- and chosen-plaintext procedures from the ineffective sets and use them to reduce the search for efficient target sequences. We evaluate five bitsliced implementations of GIFT, SKINNY and PIPO on an 8-bit AVR microcontroller under a redundancy countermeasure using clock glitches. All measured key-recovery campaigns succeed in every trial.
SALUS: Large-Scale Homomorphic Circuit Synthesis via Logic-Aware LUT Optimization
Recently, growing interests are developed in optimizing fully homomorphic encryption (FHE) circuits to enable Boolean function evaluations over ciphertexts. While existing works utilize functional bootstrapping (FBS) to efficiently evaluate logic gates, the evaluation efficiency for large-scale circuits remains limited. Recent advances introduce a fast ciphertext conversion method, making it feasible to evaluate look-up tables (LUTs) over homomorphic multiplexer operation. In this work, we propose a new circuit synthesis framework, SALUS, which automatically generates and evaluates gate-level graphs over homomorphic LUTs given an input Boolean circuit. We apply the binary decision diagram (BDD) reordering method and multi-value refresh techniques to efficiently evaluate complex LUTs. Additionally, we propose a heuristic algorithm to merge LUTs in a given circuit into multi-output LUTs. In the experiments, we examine the efficiency of SALUS using a wide range of benchmark suites, including the EPFL and ISCAS benchmark circuits. We show that SALUS achieves a maximum reduction of up to 26× in computational latency compared to state-of-the-art homomorphic circuit synthesis method. Furthermore, we evaluate real-world applications, e.g., image filtering and matrix multiplication, and achieve an average speedup of 8.6× (with a maximum speedup of 24×) compared to the FBS-based method.
Binding Security of Combined KEMs: An Analysis of Real-World KEM Combiners
In this work we analyze the various binding properties of combiners for KEMs. We show that several binding properties follow easily for the most general combiner—assuming a collision-resistant hash function—while more performance-oriented combiners require the respective property from one or both of the underlying KEMs. Other binding properties are not obtained as directly and require either more properties of one underlying KEM or the respective property from both KEMs. Additionally, we provide an overview of the binding properties for several combinations of real-world KEMs.
Balancing Exploration and Exploitation: Discriminative-Model-based Fault Injection Parameter Search
Fault Injection (FI) attacks are physical attacks that deliberately induce malfunctions in a target device. Inducing the intended fault requires precise tuning of the FI parameters, for which automated search strategies have been proposed. Most favor either exploration or exploitation: the former covers a broad region of the parameter space, while the latter discovers many successful parameters. An effective search, however, should find parameters that are both numerous and broadly spread. We propose a search framework that achieves this with two complementary discriminative models: an exploration model that learns the boundary where faults are likely, and an exploitation model that concentrates on the neighborhoods of discovered faults. We further introduce the Refinement-Oriented Successive Halving Algorithm (RSHA), which selects a highly reliable parameter from the discovered ones, using an evaluation budget derived from a target estimation precision. Across four scenarios---voltage glitching and electromagnetic fault injection on two off-the-shelf microcontrollers, the 8-bit ATXmega and the 32-bit SAM4S---our method finds up to 26.7x as many distinct successful parameters as state-of-the-art methods and attains up to 5.8x their parameter space coverage. At the full budget of 100,000 injections, the parameter that RSHA selects from our discovered set achieves a success rate up to 7.6 percentage points higher than the one it selects from the best baseline's set.
FN-DSA on Arm Cortex-M55: Revisiting a Floating-Point Lattice Signature with Native FP64 and Helium
FN-DSA has the shortest signatures among NIST's post-quantum signature standards, but on microcontrollers its signing is slow because the binary64 arithmetic it specifies is emulated with integer instructions.
Previous speedups either change the arithmetic or the order of random sampling, so their signatures no longer match the known-answer tests (KATs) of the reference implementation, or rely on double-precision SIMD
instructions that microcontrollers lack.
The Arm Cortex-M55 has both a double-precision FPU and the M-Profile Vector Extension (MVE).
On this core, we present the first FN-DSA implementation that, unlike these approaches, reproduces the KATs of the reference and runs in constant time, yet is faster than the reference.
On MVE, we vectorize the NTTs with layer merging and the fixed-point FFT of
key generation with split-word Q32 arithmetic on 32-bit lanes.
On the FPU, bit-exact FP64 computes the FFT, LDL decomposition, split, merge and sampler of signing without changing any result, and exponent-normalized division turns the bit-by-bit divisions of key generation into a single VDIV.F64 with operand-independent latency.
For Keccak, vectorized bit interleaving speeds up every permutation, and request-level batching processes four independent verification requests at once; SLOTHY then reschedules our MVE and Keccak assembly.
Key generation, signing and verification become up to 1.23x, 1.93x and 1.30x faster than the reference on the same core, and batch verification of four signatures up to 1.75x faster.
Overall, the FPU pays off where the reference emulates an operation with many integer instructions, and MVE where it already computes with integers or fixed point.
Faster Bootstrapping for Fully Homomorphic Encryption over Mixed-Radix Cyclotomic Ring
Homomorphic matrix arithmetic is central to many data-intensive fully homomorphic encryption (FHE) applications, including privacy-preserving machine learning. Standard CKKS over power-of-two cyclotomic rings provides only a one-dimensional slot structure, forcing encrypted matrix operations to rely heavily on cyclic slot rotations and the associated key-switching overhead. Although the multivariate cyclotomic ring introduced by Jang et al. (AsiaCCS 2022) and later leveraged by Gentry--Lee (Crypto 2026) naturally supports matrix-structured computations, existing implementations still rely on Number-Theoretic Transforms (NTTs) based on Rader's algorithm for the non-power-of-two dimensions, making homomorphic arithmetic inefficient. Moreover, they lack an efficient bootstrapping algorithm.
We instantiate CKKS over a mixed-radix cyclotomic ring whose order has \(2\) and \(3\) as prime factors, yielding a bivariate slot structure with independent row and column rotations. By realizing efficient NTT-based polynomial arithmetic over this ring and developing homomorphic radix-\(3\) FFT algorithms for the slot-to-coefficient (StC) and coefficient-to-slot (CtS) transformations in bootstrapping, we obtain the first practical end-to-end implementation of CKKS over this mixed-radix ring, thereby broadening the parameter space of CKKS beyond conventional power-of-two ring degrees.
Based on this foundation, we further present an efficient bootstrapping algorithm for Gentry--Lee. Our mixed-radix decomposition factors the Discrete Fourier Transform and its inverse underlying StC and CtS into their radix-\(2\) and radix-\(3\) local counterparts. Exploiting the inherent batch structure of Gentry--Lee, we evaluate these components as batch plaintext--ciphertext matrix multiplications. This formulation replaces rotation-heavy linear transformations with matrix multiplications over cleartexts that can be accelerated by high-performance libraries such as BLAS and FLINT.
Our proof-of-concept implementation achieves up to $5.31\times$ and $2.96\times$ speedups in amortized runtime for CtS and for full bootstrapping, respectively, over our optimized single bootstrapping, and is up to $1.87\times$ and $1.39\times$ faster than the construction of Crockett et al. (Crypto 2026).
Comments on "Server-Aided Public Key Authenticated Searchable Encryption With Constant Ciphertext and Constant Trapdoor"
Cheng and Meng (IEEE Transactions on Information Forensics and Security 2024) introduced server-aided public key authenticated encryption with keyword search (SA-PAEKS). In this short note, without a public-key infrastructure, we show that a cloud server (tester) can obtain keyword information from both a ciphertext and a trapdoor.
Limber: Low Overhead SNARKs for Integers from Any PCS
In real-world applications of SNARKs, non-native arithmetic, the emulation of computation outside of the specified SNARK field, is a key bottleneck. It introduces large overheads, and proof system designers often resort to non-standard SNARK-friendly hash-functions or other means like elliptic curve cycles to mitigate its costs. Besides performance concerns, non-native circuit arithmetization is also a major cause of implementation errors. In a collection of 27 critical bugs in real world ZK systems (0xPARC/zkbugtracker), 9 were related to non-native arithmetization.
We tackle these challenges by constructing a minimal overhead SNARK for integer computation that generically handles non-native arithmetic. We follow the recipe of Zaratan (PKC 26), which proves an integer relation such as $a\cdot b = c + u\cdot m$ by fingerprinting---reducing it to the same relation but over a randomly sampled prime field. Realizing this recipe requires an integer mod-PCS that commits to integer polynomials and opens their evaluations modulo a random prime, which is crucially chosen after the underlying PCS's setup and commitment phases.
Our central contribution is Limber, the first practical integer mod-PCS construction that asymptotically has $o(1)$ multiplicative commitment overhead and can be instantiated with any standard field polynomial commitment scheme, including ones over small fields. Combining Limber with a PIOP for integer R1CS over the random prime yields our SNARK. We demonstrate its practicality by implementing our scheme and showing that we can prove an RSA accumulator benchmark $15$-$30\times$ faster than circuit-based approaches, and non-native Poseidon2 hashing $24\times$ faster.
Argo: Leaking a Secret from an Invalid Groth16 Proof
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.
Catching Many Traitors in Threshold Traitor Tracing: Lower Bounds and Constructions
A $t$-out-of-$n$ threshold decryption scheme distributes decryption key shares among $n$ parties so that any $t$ of them can jointly decrypt a ciphertext, while fewer than $t$ learn nothing about the plaintext. Traditional threshold schemes provide no accountability: a coalition of $t$ or more parties can combine their key shares and construct a pirate decoder that decrypts arbitrary well-formed ciphertexts, without any risk of being traced. To address this, Boneh, Partap, and Rotem [CRYPTO '24] introduced the notion of threshold traitor tracing (TTT), where a tracing algorithm that is given black-box access to the pirate decoder can identify at least one of the colluding parties. Many subsequent threshold traitor tracing schemes similarly find only a single traitor, even though the decoder must have been constructed using at least $t$ keys. While some constructions can find multiple traitors, they do so at the cost of large ciphertexts or only achieving a weak form of correctness.
In this work, we make the following contributions:
- Lower bounds: We show that for all existing traitor tracing techniques, the ciphertext must be large to allow tracing close to $t$ traitors. In particular, to trace $t-O(1)$ traitors, the ciphertext size must be at least $\Omega(t)$. To trace $a \leq t- \omega(1)$ traitors, the ciphertext size must scale with $\Omega(\frac{a-1}{t-a+1})$. For schemes that rely on fingerprinting codes, we show an even stronger lower bound.
- Upper bounds: We present two generic compilers that construct traitor tracing for general access structures (beyond threshold) from two building blocks: attribute based encryption for general access structures and sufficiently-expressive policies and mixed functional-encryption. We also present two concrete instantiations. Under exponential security assumptions, we construct a pairings-based threshold traitor tracing scheme that can trace $t$ traitors with ciphertext size $O(t^2)$. We also construct an LWE-based traitor tracing scheme for a DNF access structure, that can trace an authorized subset of traitors with ciphertext size $O(\hat{t}^2)$, where $\hat{t}$ denotes the size of the largest unauthorized subset in the access structure.
- A Candidate Theoretical Instantiation: We present a new tracing mechanism that can trace $t(1-1/\lambda^c)$ traitors with $\mathsf{poly}(\lambda)$ size ciphertext, public key, and secret keys. We prove security assuming ideal (black box) obfuscation.
Our work raises several open questions in the context of tracing multiple parties in a threshold traitor tracing scheme.
Registered ABE via Predicate Encodings, Revisited
Predicate encodings, proposed by Wee (TCC'14), are a simple framework that abstracts a variety of attribute-based encryption (ABE) schemes.
Zhu et al. showed how to apply predicate encodings to registered ABE (Reg-ABE) using the same definition as in vanilla ABE (Asiacrypt'23).
We provide a new definition of predicate encodings that is more suitable for registered ABE and allows us to obtain more efficient Reg-ABE schemes than those by Zhu et al. for predicates captured by predicate encodings.
Notably, we obtain
\begin{itemize}
\item the first Reg-ABE scheme for (non-)zero inner product with $ O(\log L) $-size ciphertexts,
\item the first Reg-ABE scheme for conjunctions/disjunctions with $ O(\log L) $-size ciphertexts,
\item the first registered broadcast encryption scheme with $ O(\log L) $-size ciphertexts,
\end{itemize}
under the standard $ k $-Lin assumption, where $ L $ denotes the maximum number of users.
Prior to our work, Reg-ABE schemes for (non-)zero inner product, conjunctions, and disjunctions require $ O(\ell\log L) $-size ciphertexts where $ \ell $ is the vector length or the policy size, and registered broadcast encryption schemes rely on the generic group model.
Analysis of an AI based code distinguisher
Recently, DeepDistinguisher demonstrated the capability of transformer-like architectures to accurately distinguish Goppa codes from linear codes randomly generated, outperforming traditional distinguishers in certain settings. The purpose of our research is to examine the working mechanism of the mentioned machine learning algorithm. In particular, we explore the performance of the distinguisher using saliency maps and attention visualization techniques. We first identify a low-weight-row artifact present in the random instances used during training and show that the model partially relies on this feature.
After removing this artifact, the distinguisher still achieves significant accuracy, suggesting the use of more structural properties. Inspired by the constraints induced by the minimum distance of Goppa codes, we proposed a rule based on pairwise XOR operation between the rows of the generator matrix. Our experiments have shown that the predictions made by DeepDistinguisher and XOR-based rule are highly correlated especially for high-rate codes. Furthermore, when evaluated on random matrices satisfying both the minimum distance and XOR constraints, the neural distinguisher loses most of its predictive power. This suggests that transformer-based architectures exploit general combinatorial properties of a code rather than some hidden underlying algebraic structure.
Post-quantum commutative group actions from oriented superspecial abelian varieties
We study the cryptographic use of Shimura class group actions on superspecial principally polarized abelian varieties equipped with a CM orientation, within the context of post-quantum cryptography. Besides giving an accessible introduction to the topic, illustrated with many examples, we provide tools for representing CM orientations through higher-dimensional isogenies and for computing the Shimura class group action in the restricted effective group action model. Here, key auxiliary results are a version of Kani's lemma "with CM" and a trick that often allows to halve the ambient dimension. We also give a method for finding superspecial principally polarized abelian surfaces that are oriented by a given CM order, which is extracted from an algebraic framework for studying CM orientations using the Ibukiyama-Katsura-Oort correspondence. We also analyze obstructions to transitivity of the Shimura class group action, related to the characteristic-zero notion of CM type.
The Covering Radius of $\text{RM}(1,9)$ is Precisely $242$
Let $\text{RM}(r,n)$ be the $r$th order Reed-Muller code of length $2^n$, and let $\rho(r,n)$ denote its covering radius, so that $\rho(1,n)$ is the largest possible nonlinearity of a Boolean function in $n$ variables. For odd $n$, the value of $\rho(1,n)$ was previously known only for $n\le 7$. It is known that $242\le\rho(1,9)\le 244$, but the exact determination of $\rho(1,9)$ has been a long-standing open question. We give a computer-assisted proof that $\rho(1,9)=242$. We first show that a function of nonlinearity $243$ would yield one of nonlinearity $244$, so it suffices to exclude $244$. Divisibility properties of the Walsh spectrum then attach to any function of nonlinearity $244$ a cubic $p$ whose spectrum attains the sharp bound $\sum\limits_a|W_p(a)|\le 10240$, and the cases of equality take one of two forms. One form is eliminated directly. The other is eliminated by an exhaustive computation that leverages the classification of the $349$ orbits in $\text{RM}(3,9)/\text{RM}(2,9)$ under $\text{GL}(9,2)$, using Langevin's catalog of representatives together with an audit of its completeness, and the enumeration is carried out twice with independent implementations. The notebook to verify the computer search portion, $\texttt{Verify_RM(1,9).ipynb}$, contains all data and recomputes each check, and may be found in the repository $\texttt{https://github.com/FreemanSlaughter/Covering-Radius}$.
Concrete LDVR Attacks with Fewer Signers
We improve the concrete parameters of the attacks on the low-dimensional vector representation (LDVR) problem by Rodríguez García and Tessaro (ePrint 2026/2126), whose attack on canonical evaluation points uses $5{,}020$ signers. By combining their Chinese remainder theorem construction with a generalized birthday search over many challenges, we obtain a concrete attack with $488$ signers and $173$ corruptions over the Curve25519 scalar field. In $64$ batches of $2^{25}$ challenges, the search finds solutions for six distinct challenges. We compare the counts measured at each stage of the search with predictions from an explicit heuristic model. For adversarially chosen evaluation points, we build on the binary attacks of Rodríguez García and Tessaro and give a construction that attains the optimal LDVR success probability for every oracle query budget when $2\le n\le253$ and $t_c=t$ in the uniform oracle model. At $228$ signers and $114$ corruptions, our implementation finds a successful subset using SHA-512 challenges after a cumulative total of $360.13$ million queries across two runs, taking $168.60$ seconds in total. We also give an explicit set of $256$ evaluation points for which an efficient subset search attack using $128$ corruptions succeeds with probability at least $51.92\%$ per uniform challenge. For both canonical and adversarially chosen evaluation points, we analyze the query complexity and report measured and estimated running times.
Near-Optimal Early Stopping with Optimal Communication
Minimizing both the round and communication complexity of Byzantine agreement (BA) is a longstanding problem.
In the synchronous setting, early stopping protocols aim to terminate in number of rounds that is proportional to the actual number $f\leq t$ of corruptions in an execution, rather than on the worst case threshold $t$.
The lower bound on the round complexity for such protocols is known to be $\min\{f+2, t+1\}$ rounds.
Existing protocols, however, achieve either round complexity close to the optimal bound or low communication complexity, but not both simultaneously.
Elsheimy, Loss, and Papamanthou (ASIACRYPT 2024) obtain $(1+\epsilon)f+O(1)$ rounds for any $1> \epsilon>0$, with $O(n^4f \kappa)$ communication. In contrast, Lenzen and Sheikholeslami (PODC 2022) achieve asymptotically optimal $O(n \cdot t)$ communication for $t<n/3$, but with a $25f+13$ number of rounds.
In this work, we present deterministic synchronous Byzantine agreement protocols that achieve new tradeoffs between early stopping round complexity and communication. For $t<n/3$, without cryptographic setup, we obtain $f+O(\sqrt{f\log f})$ termination rounds with optimal $O(n\cdot t)$ communication (here and throughout, $\sqrt{f}$ denotes $\sqrt{f+1}$ and $\log f$ denotes $\log(f+2)$, so that the bounds are well defined when $f=0$). Thus, our round complexity has the optimal leading coefficient of one, with a sublinear additive overhead. By allowing slightly higher communication, we reduce this overhead to $O(\sqrt f)$, obtaining $f+O(\sqrt f)$ rounds with $O(n\cdot t+f^2\log f)$ communication. Finally, for $t<n/2$, assuming a public key infrastructure and threshold signatures, we obtain $f+O(\sqrt f)$ rounds with $O(n\cdot t\cdot\kappa)$ bits of communication, where $\kappa$ is the signature length.
$\mathsf{Veloz}$: Efficient and Flexible Distribution Framework for Interleaved-Code-Based Polynomial Commitment Scheme
Polynomial commitment schemes (PCSs) are a fundamental cryptographic primitive that allows a prover to reveal evaluations for a committed polynomial. Motivated by the inefficiency of proof generation for large-scale computations as well as the concerns regarding third-party reliance and quantum threats, a line of recent works has focused on distributing code-based PCS, where the proving workload is distributed among multiple sub-provers to accelerate proof generation, while preserving transparent setup and plausible quantum resilience. However, for $M$ sub-provers generating an evaluation proof for a polynomial of size $N$, existing solutions either require $O(N)$ total communication among sub-provers, or incur an $O(M)$ overhead in proof size.
In this paper, we introduce $\mathsf{Veloz}$, a novel distribution framework for interleaved-code-based multilinear PCS, which for the first time achieves communication cost sublinear in $N$, and eliminates the dependence of proof size on the number of sub-provers, without compromising proving speed or security. At its core is a customized proof aggregation method from interleaved code that efficiently combines sub-proofs via minimum communication. We further present two instantiations of $\mathsf{Veloz}$: one based on Reed-Solomon code, $\mathsf{Veloz}_{\text{RS}}$, achieves $O(\frac{N}{M}\log{\frac{N}{\log{N}}})$ proving time, $O(\lambda \cdot \frac{\log^{2}{N}}{\log\log{N}} + M\cdot\frac{N}{\log{N}})$ communication, and $O(\lambda \cdot \frac{\log^{2}{N}}{\log\log{N}})$ proof size; the other based on the fast linear code from Brakedown (Golovnev et al., CRYPTO 2023), $\mathsf{Veloz}_{\text{Lin}}$, features $O(\frac{N}{M})$ proving time, $O(\lambda \cdot K + M\cdot\frac{N}{K})$ communication, and $O(\lambda \cdot K)$ proof size for $K \in [\sqrt[3]{N}, \sqrt{N}]$, while enjoying field agnosticism.
We also implement both schemes in Rust and conduct a comprehensive performance evaluation. The experimental results demonstrate their efficient scalability with increasing $M$. More specifically, for $N = 2^{30}$ and $M = 8$, $\mathsf{Veloz}_{\text{RS}}$ takes 61.8s for proof generation, achieving a 6.46$\times$ speedup compared to running a single prover, while $\mathsf{Veloz}_{\text{Lin}}$ generates a proof in 26.9s and achieves a 7.03$\times$ speedup.
CHARRM - Characterizing Hardware Leakage in the Robust Random Probing Model
Masking is a prevalent countermeasure against passive physical implementation attacks such as Side-Channel Analysis (SCA). Despite its theoretical soundness, the practical application of masking is often fraught with complexity and prone to errors, underscoring the necessity for automated security verification. This paper presents a comprehensive methodology for efficient security verification in the $(g, t, c)$-robust $(p, \epsilon)$-random probing model. In particular, we advance the state-of-the-art concept of leakage characteristics to account for robust probe extension schemes across arbitrary circuit structures, enabling efficient leakage probability bound computation for glitch-extended and transition-extended robust probing scenarios. By further linking the leakage characteristic to the Set of Input Shares (SIS) function, we extend our verification methodology to established composability notions. Our automated reasoning framework demonstrates practicality and superior performance and accuracy for larger circuits in comparative evaluations with \ironmask as state-of-the-art competitor. For the first time, our method allows for the exact verification of larger, composed circuit structures, validated by corresponding case studies. Consequently, this work advances the state-of-the-art in automated hardware security verification, providing a versatile tool for evaluating the security of masked cryptographic implementations against SCA in the presence of transient physical effects.
Privacy with Leakage from Falsifiable Assumptions
An inherent challenge in cryptography is finding realistic
and meaningful models and assumptions. Such assumptions must be fal-
sifiable. For symmetric-key cryptography in the standard model (i.e.,
black-box without leakage), it is conjectured that we have identified
the right assumptions: pseudorandom functions and permutations (PRFs
and PRPs). However, when considering side-channel attacks (SCAs) that
exploit physical side-channel leakage, the answer is less clear. Moreover,
the requirements for integrity and privacy may differ in the leakage-aware
SCA setting. For integrity: due to advances in the so-called unbounded
leakage model, it is sufficient to claim integrity based only on black-box
properties by instantiating a single strongly unpredictable-with-leakage
(tweakable) block cipher. For privacy: one approach relied on simulatabil-
ity, proposed by Yu and Standaert at CRYPTO 2013. That is, it should
be possible to simulate leakage traces without access to the underlying
secret key. Unfortunately, simulating the leakage behavior of a complex
electronic system and arguing that distinguishing simulation from reality
is hard has proved highly challenging (e.g., Galea et al., ASIACRYPT
2014, and Deperz et al., Cascade 2026).
In this paper, we propose a new model and assumption. We isolate a key
component, namely the key-refreshing process, and provide a security
definition for it that is both falsifiable in practice and usable in security
proofs: secure refreshing. Like simulatability, this assumption is designed
to capture the security of the key-refreshing process. Rather than re-
lying on a simulator, however, we formalize security through a direct
refreshing experiment that can be practically falsified by evaluation lab-
oratories. Therefore, our approach avoids many of the concrete problems
and challenges associated with previous models. Furthermore, inspired
by this new assumption (and its accompanying model), and to provide
an additional security assumption for the strongly SCA-protected leak-
free component, we introduce strongly protected secure refreshing. As one
concrete example, using these assumptions, we prove the privacy of the
well-known PSV encryption scheme. We provide the first privacy proof
based only on falsifiable assumptions and, importantly, without assuming
that the strongly protected component is leak-free which can effectively
translate to significant computational cost reduction.
PPGA: A Framework for Privacy-Preserving Graph Algorithms using the Prepare/Propagate/Gather/Apply Paradigm
Privacy-preserving graph computation enables the secure analysis of graphs modeling social interactions and networks, financial transactions, etc., while keeping the graph private. One approach is to use secure multiparty computation (MPC), allowing different clients to contribute parts of a graph without need of disclosure, and multiple MPC protocols have been proposed for running message-passing-based graph analysis. Yet, existing public implementations are prototypes for fixed analysis functions that require substantial MPC expertise to modify and extend. We present PPGA, a practical framework based on the MultiCent protocol (PETS'25). PPGA lets users define their custom message-passing graph algorithms with a high-level interface, clients input parts of the graph, and then runs the algorithm in MPC. It significantly improves performance compared to MultiCent's implementation, running BFS on a graph of size |V|+|E|=30 million in 23 minutes without leaking the graph topology.
Firebolt: Fast, Lightweight, Malicious Non-Interactive Vector-OLE
We introduce a new maliciously-secure vector oblivious linear evaluation (VOLE), building upon a recent construction of (semi-honest) Paillier-based non-interactive VOLE. Our protocol is non-interactive (the sender can adaptively reveal entries of the VOLE using a single message to the receiver) and enjoys low communication (535 bytes for each VOLE entry) and low computation (around 5ms per party, single-threaded). Our protocol can be used as a drop-in replacement for less efficient VOLEs used in a variety of threshold schemes. We exemplify it by devising a new concurrently-secure two-round two-party ECDSA protocol that significantly improves over the state of the art. Along the way, we introduce several new strategies for proving shortness of plaintexts in Paillier ciphertexts or integer commitments, and we devise a modular framework for building threshold-ECDSA in a VOLE-hybrid model with concurrent security without requiring the use of (typically less efficient) UC-secure VOLE. All of these contributions are of independent interest.
Evasive Inner Product Functional Encryption Is Broken Too
We show that the Evasive Inner Product Functional Encryption assumption introduced by Hsieh, Lin and Luo (Eurocrypt 2024) is false in its full generality. Our counterexample adds to a long sequence of works that have attacked different variants of Evasive LWE, taking down another instance that has been considered ``public coin'' (and hence safe) in the literature.
Our attack extends the counterexample against pseudorandom functional encryption ($\mathsf{PRFE}$), developed by Agrawal, Modi, Yadav and Yamada (TCC 2025) to encompass the notion of Evasive Inner Product Functional Encryption ($\mathsf{evIPFE}$) proposed by Hsieh, Lin and Luo (Eurocrypt 2024). The original attack relied crucially on the underlying functional encryption scheme being powerful enough to compute pseudorandom functions; our attack shows, perhaps surprisingly, that the much weaker ``evasive'' inner product functionality suffices to mount the attack.
We interpret our attack as showing that even the slightest power given to the adversary in choosing unrestricted private coins in the evasive LWE family of assumptions, renders it insecure.
$\mathcal{iO}$ from LWE with Structured Preimage
Constructing $\mathcal{iO}$ from simple, safe assumptions in the post-quantum regime is an important problem with wide-ranging applications. In this work, we make progress towards this goal. We formulate a new, arguably simple assumption called LWE with Structured Preimage that suffices to build $\mathcal{iO}$. Our assumption is instance-independent, falsifiable and non-interactive. Our assumption posits that a set of LWE (Learning With Errors) samples is indistinguishable from random given a short Gaussian matrix which is carefully chosen to satisfy the required functionality while avoiding problematic leakage.
We provide a thorough cryptanalysis of our assumption, using the extensive cryptanalytic effort against the related evasive LWE assumption (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) to gain confidence. We emphasize that our assumption is superficially similar but fundamentally different from evasive LWE. Thus, we obtain $\mathcal{iO}$ from a simple lattice assumption whose hardness is somewhat better understood as compared to brand new assumptions.
A Note on the Security of ECDSA with Presignatures or Biased Nonces
Over the years, several ECDSA security experiments have been proposed to enable faster distributed ECDSA signing. These experiments are not known to reduce to the standard ECDSA game, and recent work (Groth and Shoup, Eurocrypt 2022) shows that some are vulnerable, especially when combined with raw signing (signing hash digests directly, rather than pre-hashed messages) and additive key derivation. Furthermore, several of these variants are implemented in public libraries and used by companies, sometimes in commercially deployed products, yet lack sound security foundations.
In this note, we revisit the security landscape of these alternative modes of operation for ECDSA. As our main result, we show that the security of some of these variants, which are used in the wild, is equivalent in the generic group and random oracle model to a standard conjecture from fine-grained complexity on the average-case hardness of the $k$-SUM problem. We complement our study by proving lower bounds, conditioned on fine-grained complexity conjectures, on the running time of generic group model attacks against other standard modes of operation analyzed in (Groth and Shoup, Eurocrypt 2022). Overall, our results provide a complete picture of the security landscape of ECDSA variants, and reveal an elegant connection with (old and new) conjectures from the field of fine-grained complexity.
Cirrus: Performant and Accountable Distributed SNARK
Succinct Non-interactive Arguments of Knowledge (SNARKs) can enable efficient verification of computation in many applications. However, generating SNARK proofs for large-scale tasks, such as verifiable machine learning or virtual machines, remains computationally expensive. A promising approach is to distribute the proof generation workload across multiple workers. A practical distributed SNARK protocol should have three properties: horizontal scalability with low overhead (linear computation and logarithmic communication per worker), accountability (efficient detection of malicious workers), and a universal trusted setup independent of circuits and the number of workers. Existing protocols fail to achieve all these properties.
In this paper, we present Cirrus, the first distributed SNARK generation protocol achieving all three desirable properties at once. Our protocol builds on HyperPlonk (EUROCRYPT'23), inheriting its universal trusted setup. It achieves linear computation complexity for both workers and the coordinator, along with low communication overhead. To achieve accountability, we introduce a highly efficient accountability protocol to localize malicious workers. Additionally, we propose a hierarchical aggregation technique to further reduce the coordinator’s workload.
We implemented and evaluated Cirrus on machines with modest hardware. Our experiments show that Cirrus is highly scalable: it generates proofs for circuits with 33 million gates in under 40 seconds using 32 machines with 8 cores each. Compared to the state-of-the-art accountable protocol Hekaton (CCS'24), Cirrus achieves over 7$\times$ faster proof generation for PLONK-friendly circuits such as the Pedersen hash. Our accountability protocol also efficiently identifies faulty workers within just 4 seconds, making Cirrus particularly suitable for decentralized and outsourced computation scenarios.
WISCH: Efficient data signing via correlated signatures
We present WISCH, a commit-reveal protocol that combines compact aggregate signatures with hash-based commitments to enable selective disclosure of correlated data in multiparty computation. The protocol separates an on-chain verification core from off chain preparation, so that verification cost depends only on the number of openings, not on the size of the underlying message space. This yields asymptotic efficiency: on-chain cost grows linearly in the number of revealed items and is independent of the ambient domain, while the per-byte overhead decreases with the message granularity. Security is established via a simulation-based proof in a UC framework with an ideal ledger functionality, in the algebraic group and global random-oracle models, under standard assumptions for discrete-log-based signatures and hash-based commitments. Thus WISCH provides selectively verifiable revelation with succinct on-chain checks and provable security guarantees.
Blind-DLPA: An End-to-End Framework for Profiled Blind Side-Channel Analysis
Conventional profiled side-channel analysis generally assumes that the plaintexts or ciphertexts associated with target traces are available during key recovery. We consider a profiled blind setting in which the attacker can obtain labeled traces from a profiling device using known inputs and keys, but observes only leakage traces from the target device. Under this setting, we propose Blind-DLPA, an end-to-end multi-task framework for {profiled blind side-channel analysis (profiled BSCA) that processes complete preprocessed trace windows} and jointly estimates the soft Hamming-weight posteriors of an input variable and a key-dependent intermediate variable. These posteriors are combined with pre-computed theoretical joint distributions to rank the key hypotheses, avoiding both manual {point of interest} (PoI) selection and a parameter-sensitive Gaussian label-error model. Evaluations on unprotected AES and Kyber demonstrate successful key recovery, while experiments on protected AES implementations show robustness to desynchronization and Boolean masking. To the best of our knowledge, Blind-DLPA provides the first reported profiled blind key recovery on the ASCAD dataset, reaching a guessing entropy of zero with 39 attack traces. Complementing these results, we revisit the Ascon Hamming-weight joint-distribution model adopted in prior work and identify previously overlooked collisions between key-dependent theoretical distributions that prevent unique key recovery under this model.
A Key-Recovery Attack on the GTLN Knapsack Cryptosystem via Continued Fractions
We present a continued-fraction key-recovery attack on the knapsack-based public-key cryptosystem proposed by Gómez-Torrecillas, Lobillo, and Navarro (GTLN). The key observation is that ratios of public-key differences closely approximate rational numbers with small denominators, enabling their exact recovery by continued fractions. Divisibility relations in the recovered fractions yield multiples of two private-key integers through greatest common divisor computations. Once these two integers are identified by a bounded cofactor search, all remaining private-key integers except the modulus and the shift are uniquely determined. Further greatest common divisor computations, cofactor enumeration, and modular inversion then recover the secret modulus and shift. The above process of key recovery uses only public keys. For fixed cofactor bounds, the algorithm runs in polynomial time in the public-key bit length, while a heuristic analysis predicts a high probability of recovering the original key. In experiments with prime-based key generation, our Python implementation recovered the complete private key in all 2,400 trials across the 24 recommended parameter sets, with each attack taking less than 0.05 seconds.
From if to Oops: Turning a conditional into a key-recovery oracle
Deterministic variants of CSIDH remove randomness from the group action, either through implementation techniques or, as in Houben's deterministic CSIDH and OSIDH-LD, by design. Since earlier fault attacks on CSIDH mostly target random point sampling, determinism seems to close that avenue. We show that it opens another: every secret-dependent step occurs at a fixed, public point of every execution, so an attacker can fault the same step repeatedly. Our attack forces the mask that selects which of two lanes computes the next isogeny to zero, for example by skipping one instruction. Whether the output changes reveals whether a secret exponent reaches a chosen threshold, and a binary search over these thresholds recovers the full key with one fault per execution: at most 297 oracle queries for OSIDH-LD and 222 for deterministic CSIDH with CSIDH-512-sized keys. We recover full OSIDH-LD keys in a software fault simulation of the reference implementation, and show on a ChipWhisperer-Lite that the targeted instruction is skipped with probability at least $0.94$ at an isolated fault position. Finally, we argue that fault resistance requires giving up determinism, and propose countermeasures relying on randomization.
Provable Lattice Reduction in Nearly the Time of QR Factorization
We propose a deterministic lattice-reduction algorithm with bit complexity matching QR factorization up to logarithmic factors, and an implementation that uses fewer instructions than \texttt{flatter} (CRYPTO 2023) in our benchmarks. The key technical innovations are iterative precision management, a finer-grained potential analysis, and a new representation for bases and transformations, all integrated into a recursive framework.
We analyze the asymptotic behavior of our algorithm, and show
that, for fixed reduction and output accuracy,
the running time is $\widetilde O\!\left(
n^\omega\bigl(1+\log\kappa_{\rm col}(\mathbf B)\bigr)\right)$,
where $\mathbf B\in\mathbb Z^{n\times n}$ is a nonsingular lattice basis and
$\kappa_{\rm col}$ is the optimally column-scaled spectral condition number.
This gives a finer complexity than prior art, by allowing a tighter condition number $\kappa_{\rm col}$. Besides, through a new observation on the recursive structure, we demonstrate that the algorithm is free from heuristic assumptions. We compare our implementation with \texttt{flatter} on q-ary, NTRU-like, scaled q-ary, and Coppersmith inputs. Our implementation uses fewer instructions in all 153 executions. The median ratios of \texttt{flatter}'s instruction count to ours are 1.55 for ordinary q-ary inputs and 1.86 for NTRU-like inputs.
SCMAC and LOL2.0: An AEAD Design Framework and A New Version of LOL Stream Cipher Design Framework
In this paper, we introduce SCMAC, a general framework that transforms large-memory stream ciphers into AEAD schemes. It represents an intermediate design paradigm between Encrypt-then-MAC and dedicated single-pass AEAD, partially integrating encryption and authentication mechanisms while mitigating the risk of state leakage associated with immediate absorption and squeezing. Consequently, this approach harmonizes high performance with enhanced security. Additionally, we propose LOL2.0, an enhanced version of the blockwise stream cipher design framework LOL. This new framework improves security through modifications to the FSM update and output functions, and increases flexibility in constructing LFSR components. Based on SCMAC}$ and LOL2.0, we present two AEAD ciphers, LOL2.0-Mini and LOL2.0-Double, which support both stream cipher and AEAD modes. These ciphers are tailored to Beyond 5G/6G environments, offering 256-bit key length and resistance to known cryptanalysis methods, including differential, linear, and integral attacks. They also provide 128-bit security against forgery attacks in the nonce-respecting setting. Due to their compatibility with AES-NI and SIMD instructions, LOL2.0-Mini and LOL2.0-Double achieve software performance of 90 Gbps and 144 Gbps in stream cipher mode, respectively. In AEAD mode, they perform at 59 Gbps and 110 Gbps, significantly faster than their predecessor's Encrypt-then-MAC versions.
SoK: Pseudorandom Generation for Masked Cryptographic Implementation
This paper investigates pseudorandom generation in the context of masked cryptographic implementation. Although masking and pseudorandom generators (PRGs) have been distinctly studied for a long time, there has been little study on how randomness should be generated in masked implementation. The lack of analysis on mask-bits generators obscures the practical security of masked cryptographic implementation, potentially confusing practitioners (e.g., designer, implementer, and evaluator) about how to realize them securely. This paper provides a novel viewpoint and comprehensive analyses by developing three new models, each of which corresponds to a practical scenario: leakage assessment, experimental evaluation of attack success rate or key lifetime, and deployment. We reveal what PRG properties are required. In particular, we support a long-held belief/folklore through proof and experiment: for the output of PRG for masking, cryptographic security (i.e., unpredictability) is not necessary. In addition, we thoroughly investigate the practical security of PRGs within the masking context. We conclude this paper with some recommendations for practitioners and a proposal of leakage-resilient method offering comparative performance.
Optimizing HQC with Enhanced Parallel Binary Polynomial Multiplication on GPUs
Graphics processing units (GPUs) are widely employed as accelerators in modern servers to handle key-establishment requests in bulk. Such deployments require the GPU implementation to sustain high throughput while keeping each request within its latency bound. In this work, we present a high-performance, end-to-end GPU implementation of Hamming Quasi-Cyclic (HQC), a code-based key encapsulation mechanism (KEM). We propose two novel techniques to accelerate the dominant cost of HQC, which is binary polynomial multiplication over Galois Field GF(2). The first is a parallelization of the Frobenius additive fast Fourier transform (FAFFT), and the second is a mapping of the cyclic product, viewed as a Toeplitz matrix–vector product, onto one-bit integer (INT1) tensor cores. We further explore the design space of these multipliers, measuring them directly on the GPU to derive the best combination for the architecture. We further propose a GPU-resident computation strategy that keeps the entire KEM on the GPU, thereby reducing costly memory traffic. Beyond multiplication, we introduce warp-level parallelization strategies to accelerate the remaining stages, hashing, Reed–Muller/Reed–Solomon (RM/RS) coding, and fixed-weight sampling, which become the performance bottleneck once multiplication is optimized. By varying the mapping of KEM instances to GPU threads, we derive five variants spanning the trade-off between throughput and latency and organize them into a thread-to-KEM mapping taxonomy. On an RTX 4090, the Coarse-Grained (CG) variant maximizes batch throughput. Our multiplier reaches 3,828k polymul/s for standalone multiplication, about 2.9× the latest GPU HQC implementation HIGH, and for the full KEM the CG variant achieves 1.56×, 1.55×, and 2.03× higher end-to-end throughput than HIGH for keygen, encaps, and decaps. For single-shot latency the tensor-core-based BMMAw variant achieves a latency as low as 254 µs. The proposed warp-parallel FGmw variant still attains a latency of 354 µs, demonstrating that our approach remains effective on GPU architectures lacking INT1 tensor-core support. All five variants are further evaluated on an RTX 3090 and an embedded Jetson AGX Orin to confirm cross-platform portability.
Circular Dragon: $\widetilde{{O}}$ptimal Adaptively Secure Distributed Randomness/Key Generation and Parallel Broadcast
We present the first strongly adaptive common coin protocol, under the PKI setup (in the random oracle model and the algebraic group model, yet with no trusted dealer), that (i) achieves the optimal resilience $t< n/2$ in synchronous networks, and (ii) attains near-optimal asymptotics: near-quadratic communication $O(\kappa \lambda n^2\log n)$ and logarithmic rounds $O(\kappa\log n)$, with failure probability $\textsf{negl}(\lambda)+2^{-\kappa}$, where $\lambda$ (resp. $\kappa$) is the computational (resp. statistical) security parameter. Furthermore, the coin protocol assumes no memory erasure. At its core is a ``special-purpose'' distributed key generation (DKG) protocol that produces a secret in an elliptic-curve group.
Our common coin immediately implies the first strongly adaptive and optimally resilient Byzantine Agreement with subcubic communication and sublinear rounds in the absence of a trusted dealer. Furthermore, we give two non-trivial applications of independent interest: (i) a strongly adaptive Parallel Broadcast (PBC) under standard PKI with near-quadratic communication and logarithmic rounds, whereas all existing subcubic solutions (Gelles et al. CRYPTO'25, Civit et al. PODC'24) require at least linear rounds; (ii) a strongly adaptive ``general-purpose'' DKG for field-element secrets with $O(\lambda\kappa n^2\log n)$ communication and $O(\kappa\log n)$ rounds (assuming memory erasures), fully compatible with legacy threshold schemes (BLS, Schnorr, ElGamal), improving upon (Feng et al. PODC'24), which requires $O(\lambda\kappa n^{2.5} \log n)$ communication and $O(n)$ rounds.
Our core is a new design methodology, which we call \emph{Circular Dragon}. This extends the Dragon method (PODC'24) that was originally developed for sub-cubic communication DKG protocols but with linear rounds, by further reducing the round complexity.
Off-Key: Inconsistent MAC Keys Compromise Privacy in SPDZ-Family MPC
SPDZ-family protocols for maliciously secure multi-party computation protect secret-shared values with message authentication codes (MACs) under a secret-shared global key. Their security requires that all values and preprocessing used together be authenticated under the same key. We present Off-Key, a privacy attack that exploits violations of this requirement. Depending on which specific MAC check protocol is used, a corrupted party can either recover the value of a shared secret from a single authentication check or test a guess through selective failure by modifying a MAC share and observing whether a masked check succeeds. While this attack does not compromise the theoretical security guarantees of the protocols, we demonstrate this key-consistency vulnerability in evaluated versions of MP-SPDZ, SCALE-MAMBA, and FANNG-MPC, which allow a corrupted party to use different keys across batches, threads, or process runs. To help implementations avoid this class of attacks, we identify the state that enforces key consistency in representative preprocessing protocols and show how preserving and reusing it prevents the attack.
HERMES: High-Performance Private Decoding for Large Language Models
Privacy-preserving inference (PI) enables users to query large language models (LLMs) without revealing their prompts, but incurs substantial computation and communication overhead. Prior PI systems primarily optimize prefill and time to first token (TTFT). This suits applications that need only a single output token, yet most real-world use cases require multi-token responses. Such autoregressive workloads are dominated by time per output token (TPOT) instead.
For the first time, we investigate generating full multi-token answers for real prompts under PI. We show that PI decode is hindered by two bottlenecks: (i) nonlinear kernels that require many interactive communication rounds, and (ii) attention protocols that underutilize ciphertext capacity and repeatedly re-encrypt or transmit the growing key and value (KV) cache.
We present HERMES, a PI system optimized for LLM decoding. HERMES replaces high-round nonlinear protocols with compute- and bandwidth-intensive alternatives that require fewer communication rounds. It also introduces a novel matrix-multiplication protocol based on homomorphic encryption that keeps the KV cache encrypted on the server and uses grouped-query attention (GQA) to improve ciphertext utilization. On Llama 3.1 8B Instruct, across the network conditions and prompts used in our evaluation, HERMES lowers TPOT by up to 2.7× and total PI latency by up to 2.1×.
Computing endomorphisms of superspecial principally polarized abelian surfaces in time and memory \(p^{4/5+o(1)}\)
We present an algorithm for computing endomorphisms of superspecial principally polarized abelian surfaces over finite fields. Under a standard heuristic, we obtain a non-scalar polarized endomorphism in expected time and memory $p^{4/5 + o(1)}$.
Revisiting the Security of VDOO
VDOO is a multivariate signature scheme submitted to the Next-generation Commercial Cryptographic Algorithms Program (NGCC). We study the security of its submitted parameter sets. In this paper, VDOO is described as a multilayer Rainbow construction. By retaining only its last oil space, we obtain a generalized UOV instance and apply existing wedge attacks.
For the parameter set targeting 512-bit security, we estimate costs of $2^{432}$ and $2^{379}$ gates for the reconciliation and intersection variants, respectively. These estimates rely on the assumptions of the attack model and are below both the claimed security level and the attack costs reported in the specification.
Our analysis uses only the generalized UOV structure. The additional information in the multilayer structure may allow further improvements. Our results also motivate further study of parameter choices that balance resistance to known attacks with signing efficiency.
How Secure are NTRU+ Keys? Analysing the Best Module Attacks
A recent analysis of module-BKZ [Ducas–Engleberts–Perthuis, Asiacrypt'25] predicts subexponential speedups for lattice reduction on module lattices over cyclotomic fields whose conductor has small odd prime factors. This threatens NTRU+, the South Korean standard for key encapsulation, and related schemes; however, the short vectors one seeks to find are short in the coefficient geometry, whereas module-BKZ operates in the canonical geometry.
We introduce relative canonical and relative coefficient embeddings, realising a module over a cyclotomic field $K$ as a module over any subfield $L$, and characterise when the two agree up to scaling: exactly when the radicals of their respective conductors $c$ and $\ell$ satisfy $\mathrm{rad}(c)/\mathrm{rad}(\ell) \in \{1,2\}$. Furthermore we quantify the distortion incurred in general when passing between embeddings, and hence identify the optimal subfield for module-BKZ and BKZ to use.
Estimating the cost of the best attack with simulation-based models [Perthuis–Trenkić, PQCrypto'26], we find that the best module attack saves only 4–10 blocksizes, costing NTRU+ keys at most three bits of security in the Core-SVP model.
We further extend the analysis of overstretched NTRU regimes [Ducas–Woerden, Asiacrypt'19] to the module setting, and find the fatigue point is reached sooner than with unstructured counterparts, though NTRU+ parameterisations remain safe.
Optimal Threshold Implementations of all bijective 4-bit S-boxes and new Infinite Families
Threshold implementations (TIs) are now an established class of side-channel countermeasures. Their underlying idea is simple and compelling: under mild, practical assumptions, they provide protection against glitches and allow composability. Yet our understanding of one-stage TIs with a minimal number of shares remains limited, both for cryptographically relevant families—particularly power functions—and for concrete small functions. In particular, until now, except for Feistel-constructions, no optimal TI had been found for families of mathematically well-structured and cryptographically non-trivial functions, especially power functions. In small dimensions, many functions - particularly cryptographically interesting ones — were not known to admit an optimal TI. This was especially true for the 4-bit S-boxes frequently used in practical lightweight ciphers. Optimal refers to share-optimal, direct one-stage, uniform, first-order TI. Here, we introduce new families of TIs, including the first infinite families of cryptographically nontrivial power permutations. Moreover, every four-bit permutation of algebraic degree t admits a direct, uniform TI with t+1 shares and no fresh randomness. Those results prove several previous conjectures and claims wrong. Since such permutations are widely used in symmetric ciphers, our constructions offer new implementation options.
$\textbf{Note:}$ The threshold implementations presented in this paper are available at: https://github.com/enripicc/Optimal-Threshold-Implementations-for-3-4-and-5-bits-permutations
Zero-knowledge and Quantum CSS Codes Are Equivalent
Zero-knowledge codes, introduced by Decatur, Goldreich, and Ron (ePrint 1997), are error-correcting codes in which few codeword symbols reveal no information about the encoded message, and have been extensively used in cryptographic constructions. Quantum CSS codes, introduced by Calderbank and Shor (Phys. Rev. A 1996) and Steane (Royal Society A 1996), are error-correcting codes that allow for quantum error correction, and are also useful for applications in quantum complexity theory.
In this short note, we show that (linear, perfect) zero-knowledge codes and quantum CSS codes are equivalent. We demonstrate the potential of this equivalence by using it to obtain explicit asymptotically-good zero-knowledge locally-testable codes.
Faster ABE for Turing Machines from Circular Evasive LWE
We present a new ABE for Turing machines, where
- encryption runs in time $O(T)$ and produces a ciphertext of size $O(T)$ for time $T$ computation;
- key generation produces a key of size $O(1)$;
- security relies on the (public-coin) circular evasive LWE assumption.
In fact, we obtain an ABE for a simple and more general model of computation which we refer to as iterated (local) computation.
We improve on the recent construction of Agrawal, Kumari, and Yamada (CRYPTO 24) in three ways: (i) faster encryption and smaller ciphertext size; (ii) smaller key size, and (iii) weaker assumptions, eliminating the need for circular tensor LWE.
DPA-style Attacks on VOLE-in-the-Head Signature Schemes
VOLE-in-the-Head (VOLEitH) has emerged as a promising paradigm for the design of post-quantum signatures, as it enables efficient signing and verification while also achieving small signature sizes. In the ongoing NIST PQC standardization process for additional digital signatures, two VOLEitH signature schemes, namely FAEST and SDitH, have advanced to the third round. Regarding their practical security, especially resistance to power side-channel attacks, existing studies have focused on only a few specific operations, and thus a comprehensive analysis remains lacking. To address this gap, we present, to the best of our knowledge, the first DPA-style attack framework against VOLEitH signatures. Our framework targets the secret witness, whose recovery permits the generation of valid signatures for arbitrary messages. Based on this framework, we systematically analyze the leakage stemming from the computation of sensitive intermediate values involved in VOLE correlations, and characterize how such leakage can be linked to secret witness hypotheses for mounting DPA-style attacks. As a consequence, we propose six classes of DPA-style attacks on FAEST and SDitH, including two vertical and four horizontal attacks. Finally, the proposed attacks are validated using both simulated leakage under varying noise conditions and practical measurements on three ARM Cortex-M4 devices, demonstrating their effectiveness in both settings.
Attacking CRT-RSA with Small Exponents via Unravelled Linearization
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.
Enjoy FAEST on Hardware: Efficient and Novel Hardware Acceleration of Emerging Post-Quantum Digital Signature Scheme FAEST
Uncategorized
Uncategorized
The National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process has drawn significant attention from the research community recently, especially regarding these PQC schemes' hardware acceleration. Nevertheless, related research on the emerging schemes, e.g., those currently under consideration by the NIST additional digital signature scheme standardization, still needs further exploration. With this background, this paper presents an efficient and novel hardware acceleration for FAEST, one of the promising signatures in the NIST Round 3 additional scheme competition. Overall, we have presented several layers of innovative efforts to obtain the proposed acceleration. First of all, we have conducted detailed algorithmic analysis on the major computationally intensive operations within FAEST and proposed novel design strategies and algorithms for their efficient hardware implementation. Next, we have proposed novel design efforts to construct these major operations into efficient building blocks to finalize the overall accelerator, along with the help of optimized operational phase workflow. The dedicated extension to build the L1-EM-fast accelerator is also given. Finally, we have provided a detailed and thorough evaluation process to showcase the superior performance of the proposed design over the existing complete, Sign part, and single security level MPC-in-the-head signature acceleration works. For instance, at the same security level, the proposed fast variant has at least 98\% less equivalent Area-Delay Product (eADP) than the recent complete SDitH design. To the authors' best knowledge, this is the first hardware acceleration work for FAEST, and we hope the outcome of this research will facilitate the ongoing PQC standardization process.
LogVOLE: Succinct and Efficient Chosen-Input VOLE for ZK and Beyond
Random Vector Oblivious Linear Evaluation (VOLE) correlations can be generated efficiently for zero-knowledge proofs and secure computation. Applications that need correlations on the receiver’s actual input typically derandomize random VOLE by sending a linear-size vector, a main communication bottleneck.
We study chosen-input VOLE (CI-VOLE), where the receiver privately chooses a large vector \(\mathbf{x}\), the sender fixes \(\Delta\), and the parties obtain shares of \(\mathbf{x}\cdot\Delta\) without communicating a linear-size object. This work presents LogVOLE, a concretely efficient CI-VOLE protocol with polylogarithmic end-to-end communication under Ring-LWE. The construction uses a recursive shrink/expand design: it authenticates short digests of the chosen input and then uses a succinct telescope to expand those relations back to the full vector. The protocol has \(O(\lambda\log^2(|\mathbf{x}|+m_{\mathsf{msg}}))\) one-time setup and query communication and \(O(|\mathbf{x}|/n)\) ring operations. Here, \(n\) is the underlying ring degree, \(\lambda\) is the computational security parameter, and \(m_{\mathsf{msg}}\) is the size of the shares.
LogVOLE also supports a public-key non-interactive mode: for a fixed \(\Delta\), the sender publishes reusable parameters, and a receiver sends one compact \(\mathbf{x}\)-dependent message to obtain the matching VOLE shares. This gives a route to non-interactive VOLE-based ZK with polylogarithmic communication for arbitrary circuits. We also give a malicious-security extension in the random oracle model.
Using LogVOLE, we construct the first concretely efficient VOLE-based designated-verifier ZK protocol for arbitrary circuits with polylogarithmic communication. At 128-bit computational and 40-bit statistical security, our implementation achieves online throughput of 13.9 million \(\mathbb{Z}_p\) correlations/s and 12.9 million ZK multiplication gates/s using 16 CPU cores per party. With golden-seed optimization and reusable setup, our GPU implementation processes 532.3 million \(\mathbb{Z}_p\) correlations/s and 451.7 million ZK multiplication gates/s online on an H200 GPU. With one CPU thread per party, our implementation proves \(1024\times1024\) matrix multiplication in about 4 seconds online, with 226 kB of online communication.
SwiftAuth: Conditional Privacy-Preserving UAV Authentication with Multi-Source Credential Aggregation and Non-Interactive Authorization
To address the challenges of interactive credential issuance and conditional privacy-preserving authentication for dynamic terminals accessing multiple third-party services, we propose an traceable and aggregatable tagged witness signature (TA-TWS). Building upon this scheme, we design an efficient and privacy-preserving anonymous authentication framework, termed SwiftAuth.
SwiftAuth decouples the issuer’s authorization phase from the user’s credential acquisition process in traditional anonymous authentication systems by introducing an asynchronous credential distribution mechanism. This allows issuers to generate authorization components even when users are offline, while ensuring that only the designated user can derive the complete access credential.
Furthermore, during the authentication phase, SwiftAuth reduces communication and verification overhead in concurrent multi-service access by compressing multiple credentials into a constant-size representation, and supports verifier-side batch verification across users. In addition, it provides conditional privacy by integrating a regulatory trapdoor, ensuring default anonymity for legitimate users while enabling authorities to trace malicious actors upon protocol violations.
Finally, we formally prove that the proposed TA-TWS achieves unforgeability and witness hiding. Extensive experiments were conducted on multiple resource-constrained devices, and Aliyun servers, using the MIRACL Core cryptographic library, demonstrate the practicality and efficiency of our approach.
CRISP: Channel-Randomised Single-Image Steganography with Permutations
We introduce CRISP (\underline{C}hannel-\underline{R}andomised Single-\underline{I}mage\\ \underline{S}teganography with \underline{P}ermutations), a homomorphic steganography scheme for outsourced computation. In the setting we consider, a client (Alice) hides Boolean inputs in the least-significant bits of cover images and asks an honest-but-curious cloud (Carol) to evaluate a logic circuit, gate by gate, directly on those images so that a receiver (Bob) can later extract the result. The setting is natural for outsourcing but non-standard for steganography: Carol knows that steganographic embedding is used, knows the scheme, and knows the public channel-assignment permutations; the only secret is the per-execution pixel position $(\mathit{row}, \mathit{col})$ in the image at which the bits live. The security goal is therefore positional hiding under known presence, not Cachin-style undetectability.
CRISP embeds all three inputs of a Fredkin gate (a universal reversible three-bit logic gate) into the three RGB channels of a single cover image at a secret pixel position, and writes all three outputs into a single output cover at the same position. Two independently sampled permutations $(\pi_{\mathrm{in}}, \pi_{\mathrm{out}}) \in S_3 \times S_3$ assign channels to logical roles at the input and output of each gate, and both travel with the public circuit specification.
Two results about the limits of this design follow, and we regard them as the more useful contribution. First, per-gate resampling of $\pi_{\mathrm{out}}$ does not give circuit privacy. We prove that a server holding the circuit specification reads the channel-to-role map at every gate directly, and that a weaker adversary holding only the images recovers the same map and the wiring graph with nine channel-pair comparisons per gate. Second, a $1/(h{\times}w)$ positional bound proved on a single image does not survive a full multi-image transcript when ancillary wires carry publicly known constants. We restate the security game over the whole transcript and prove a bound $2^{\lambda}/(2^{\lambda}+n-1)$ with $n = h{\times}w$ and $\lambda$ the gap between the number of secret input bits and the collision entropy of the server's prior on them. Constants embedded only at the secret pixel push $\lambda$ up by one bit each, and enough of them pin the pixel down exactly. Two cheap repairs drive $\lambda$ back to zero and restore the exact $1/(h{\times}w)$ bound. The decay is polynomial, not super-polynomial, so the bound is statistically small but not cryptographically negligible in the standard sense.
Superspecial points on Humbert surfaces and the probability of (N,N)-splitting
Let $p\equiv3\pmod4$ be a prime and let $N\geq2$ be an integer. We determine, to first order in $1/p$ and with an explicit error bound, the proportion of superspecial principally polarized abelian surfaces over $\overline{\mathbb{F}}_p$ that are optimally $(N,N)$-split. The surfaces are weighted by the reciprocals of their automorphism orders, which is the stationary measure of the Richelot random walk. The main theorem states that for $p\nmid N$ the expected number of optimal $(N,N)$-splittings of a surface is exactly $5NJ_2(N)(p-1)/(p^2+1)$, where $J_2$ is Jordan's totient; that for $p>2N^2$ the second factorial moment is $c_N/(p^2+1)$ with $c_N$ independent of $p$; and consequently that, for fixed $N$, the proportion of split surfaces is $5NJ_2(N)/p+O_N(p^{-2})$. The constants $c_N$ are determined explicitly for $2\leq N\leq7$. This proportion is the stationary target density of the splitting-detection attack on the superspecial isogeny problem in dimension two. It was previously known only from experiments or from a one-sided bound. The method is to show that the superspecial surfaces sample the genus of their refined Humbert invariants with Siegel's weights, which makes Siegel's theorem on genus averages available. The same method gives the first moment of primitive representations of every discriminant prime to $p$, mixed moments for several levels, an exact probability at level $2$, and a proof that the geometric upper bound of earlier work has the correct leading term. All results are proved; the enumerations enter only through the values of $c_N$, and every formula was additionally confirmed by exact computation at twelve primes.
Efficient Fixed-Point Implementation of Mitaka
The Mitaka signature scheme is a variant of Falcon (FN-DSA). It has a considerably simpler signing procedure that can be parallelized while retaining Falcon's efficiency advantage. Mitaka offers two different signing approaches: a default one relying on floating-point arithmetic and an alternative, called MitakaZ, avoiding floating-point arithmetic at the cost of more Gaussian samples. Despite its better portability, MitakaZ has not previously been implemented in practice.
This work presents an efficient fixed-point implementation of the Mitaka signing algorithm. We optimize the MitakaZ Gaussian sampler to make it suited to fixed-point arithmetic while achieving higher efficiency. Specifically, we replace the wide integral Gram root decomposition used in MitakaZ with a fixed-point square Cholesky decomposition, which substantially reduces the cost of integer Gaussian sampling. We prove bounds on intermediate values and representation errors without empirical assumptions on their magnitudes. The distributional analysis models each integer Gaussian call as exact at its represented inputs. We provide a fixed-point implementation of the new Mitaka signing algorithm in C. On an Intel Core~i7-1360P, our native AVX2 implementation generates signatures in an average of 361 kcycles for Mitaka-512 and 707 kcycles for Mitaka-1024, measured with Linux hardware performance events. On an ARM Cortex-M4F STM32F411, the corresponding measured costs are 4.0 and 7.8 Mcycles.
Unpredictability from Parity: Understanding Linear Correctors for Markovian Sources
Linear correctors reduce the bias of random bits via parity (XOR), but their guarantees are known mostly for independent bits, an assumption violated by many physical entropy sources.
We give a general, exact formula for the parity bias of dependent bits from a (hidden, possibly non-homogeneous) Markov chain, as a product of twisted transfer kernels.
Under next-bit unpredictability, i.e. conditional bias at most $\beta$, the decay is governed by $\beta$ itself: sharp for a one-bit context, $|\mathrm{bias}|\le\beta^{\lceil n/2\rceil}$, and \emph{near-optimal} for an $m$-bit context, within a factor $3^{1/3}\approx1.44$ of the best possible per-bit rate, which is at least $\beta^{1/(m+1)}$ (attained by a noisy LFSR) and asymptotically equal to it as $\beta\to0$.
Against the best previous bound (Zhou and Bruck, ISIT 2011) we \emph{correct the exponent} and \emph{tighten the bound on $n$ bits by a factor of about $2^{\lfloor(n-1)/2\rfloor}/\beta$}, with a matching construction. The decay is non-monotone, so a corrector should be certified at every operating length, or via the envelope $\beta^{\lceil n/2\rceil}$.
Finally, bounded memory is necessary: if unpredictability is imposed on the full history, XOR-ing does not reduce the bias at all.
Heterogeneous CPU–NPU Implementation of the AIMer Post-Quantum Signature for Low Latency on a Mobile SoC
Signatures in the MPC-in-the-head paradigm rest only on a symmetric primitive, but their signing is slow, because it computes hash functions and a linear map for every simulated party of every repetition. We show that the Hexagon NPU of Snapdragon SoCs shortens one complete signing operation of AIMer, the MPC-in- the-head signature that the Korean post-quantum cryptography competition selected. Prior work speeds up such signatures on one CPU core, accelerates post-quantum arithmetic on GPUs for batches of operations, and reports only single post-quantum functions for mobile NPUs. Our implementation divides each signing operation along its dependency graph. The NPU computes the hashing and the per-party linear map of the last repetitions, which need no secret key, and the CPU keeps the secret key and the two hashes that absorb the repetitions in index order. A fast AArch64 implementation serves both as the CPU part and as the baseline, and it signs 4.5 to 6.1 times faster than the reference implementation on one core. On a Snapdragon 8 Gen 3 tablet, one core with the NPU signs 1.30 to 1.42 times faster than two cores and 1.74 to 1.97 times faster than one core for the three short-signature parameter sets. The same configuration uses 13 to 27 % less energy per signing operation than two cores. On Snapdragon 8 Elite and 8 Gen 2 phones, one core with the NPU signs 1.28 to 1.35 and 1.74 to 1.82 times faster than two cores.
GPU Acceleration for Boyar-Peralta Algorithm in High Dimensional Linear Layers
The design of lightweight cryptographic schemes necessitates efficient circuit implementations of linear layers. A commonly used metric for evaluating circuit efficiency is the number of XOR gates required. For a given linear transformation over $\mathbb F_2$, finding its circuit implementation with the minimum number of XOR gates is referred to as the Shortest Linear Program (SLP) problem. As a prominent heuristic, the Boyar-Peralta (BP) algorithm provides competitive results, and numerous subsequent studies have introduced further optimizations. However, the inefficient implementations of the BP-like algorithms significantly limit their applicability to high-dimensional and dense matrices, and effective solutions to these performance bottlenecks remain scarce.
In this paper, we address the performance bottlenecks of the BP algorithm and its variants (e.g., A1, A2 and BP-LSL) both theoretically and practically. We introduce the meet-in-the-middle (MITM) approach to reduce their theoretical time complexity. Practically, we re-design the implementation framework of these algorithms to fully leverage GPU parallelism, which significantly reduces the time spent on computing multiple XOR sums of bases, performing binary search, and updating distances. Meanwhile, we also propose a candidate pruning mechanism to reduce the computational burden on the GPU side and further improve the overall efficiency. Compared with the original implementations, we significantly accelerate the solving process for both normal and depth-constrained scenarios while maintaining the same solution quality.
Our experimental results demonstrate that, for a 26-dimensional matrix with density 0.5, our implementation requires only 9.44 seconds on an entry-level GTX 1650 GPU, achieving a speedup of over $6{,}200\times$ compared with the current recursive, exhaustive, and one-threaded implementation.
Using a high-performance RTX 4090 GPU, we extend the solvable boundary to 64-dimensional sparse matrices and 42-dimensional matrices with density 0.381. For 32-dimensional dense matrices, our accelerated A1 algorithm successfully establishes some new g-XOR records, including a 172-step g-XOR implementation for Whirlwind M0 and a 170-step implementation for Whirlwind M1. Besides, we also provide a 157-step g-XOR sequence for AES-InvMixColumn matrix with depth 5 through our BP-LSL implementation. Based on our accelerated BP implementation, we construct some MDS matrices with dimension 40 or more. For $4\times 4$ blockwise circulant matrices of dimensions 40, 48, and 64, the minimum g-XOR sequence lengths we found are 110, 132, and 184.
Associated-Data Correlations in Eevee: Deterministic Forgeries against Nonce-Misuse Security
Eevee's Umbreon and Espeon modes claim online authenticated-encryption security under nonce reuse. We give an independent analysis of associated-data correlations that yield probability-one non-empty-message forgeries with three encryption queries and one verification query. Two AD-only tags reveal a mask difference that translates a ciphertext to another AD value. The basic attacks and their proof diagnosis overlap with independent and concurrent work by Mao et al. Our complementary contribution is a systematic affine treatment of partial final message blocks. For any admissible fixed final-fragment length r, n-r+3 encryption queries suffice; allowing the forged length to be r or r-h for a chosen 1 <= h < r < n, while choosing the source plaintext adaptively, reduces this to n-r+2. Both constructions satisfy the padding check and succeed with probability one. They apply to general message lengths, with at least one preceding complete block for Espeon. We also analyze the published short-message Espeon AD omission, validate the published complete-block Umbreon attack using the official ForkSkinny primitive in a specification adapter, and report a separate two-query attack accepted by the unmodified public C modes. Finalization is discussed only as an unproved countermeasure direction.
SnarkMux: Streaming SNARK Aggregation with Constant Online Verification
SNARKs let a verifier check an expensive computation via a succinct proof, without re-executing the computation. However, many applications still verify proofs individually, creating verifier load and high fees in replicated or constrained-verifier settings. Existing proof aggregation schemes largely follow the generalized inner product argument (GIPA) line, achieving $O(\log n)$ proof size and verifier work for aggregating $n$ proofs, but remaining costly in practice and operating in batch mode. Rather than batching until a full window is available, we present SNARKMux, a streaming SNARK aggregation scheme that maintains a constant-size aggregate and requires $O(1)$ online verifier work per window of size $n$. Motivated by incremental verifiability, SNARKMux directly folds the Groth16 and Plonk verification relations and composes these proof-system-specific folds with Nova's circuit-layer fold; this defers expensive target-verifier logic (e.g., pairings) to the final check while keeping constant aggregator state. As part of public-input aggregation, we propose a generic instance-delegation technique: the prover aggregates instances, and the verifier performs a simple binding preprocessing costing only $O(n)$ hashes per window, after which online verification is constant-cost. Notably, our Groth16 and Plonk instantiations cover both circuit-specific and universal-setup SNARKs, with preprocessing that makes Plonk challenges folding-compatible, leading to a 0.7 KB Groth16 aggregate with 18 ms verification and a 0.5 KB Plonk one with 2 ms verification for 256 proofs.
Twist and Shout: Faster memory checking arguments via one-hot addressing and increments
Memory checking arguments enable an untrusted prover to prove that it is correctly processing reads and writes to memory. They are used widely in modern SNARKs, especially in zkVMs, where the prover proves the correct execution of a CPU including the correctness of memory operations.
We describe a new approach for memory checking, called the method of one-hot addressing and increments. We instantiate this method via two families of protocols, called Twist and Shout. Twist supports read/write memories, while Shout targets read-only memories (also known as lookup arguments). Both have logarithmic verifier costs. Unlike prior works, these protocols do not invoke "grand product" or "grand sum" arguments.
Twist and Shout reduce commitment costs in two Jolt settings: 32 RISC-V registers and structured lookup tables of size $2^64$. With curve-based commitments, Twist at $d=1$ has about 3.7x fewer nonzero committed values and 1.7x fewer field multiplications than Spice for 32 registers; Shout at $d=2$ has at least 8x fewer nonzero committed values and 3.4x fewer field multiplications than Lasso for structured tables.
We integrate Twist and Shout into the Jolt zkVM. They speed up the Jolt prover 3x while reducing proof size by about 5x.
Lattice Bingo: Asynchrony and One-Shot Adaptivity in Verifiable Secret Sharing via Erasure Code Commitments
Asynchronous verifiable secret sharing (AVSS) allows a dealer to distribute a secret among parties while preserving privacy and consistent reconstruction, despite Byzantine faults and arbitrary message delays. It is a fundamental building block for Byzantine agreement, distributed key generation, and secure multiparty computation. Packed AVSS protocols share many secrets together to reduce communication per secret. The best known AVSS protocols achieve quadratic communication while sharing linearly many secrets. In particular, Bingo (Abraham et al., CRYPTO 2023) shares a batch of $\Theta(k)$ secrets among $k$ parties using $O(\lambda k^2)$ words of communication, while also achieving adaptive security, but relies on assumptions that are not post-quantum secure. Known post-quantum alternatives have higher worst-case communication for comparable batch sizes or require substantially larger batches to achieve linear amortized communication.
We present Lattice Bingo, a lattice-based packed AVSS protocol with quadratic communication and linear packing. For every constant $\epsilon>0$, it shares $\Theta(k)$ secrets among $k\geq(3+\epsilon)f$ parties, tolerates $f$ Byzantine parties, and uses $O(k^2\operatorname{poly}(\lambda))$ words of communication. It additionally achieves one-shot adaptive secrecy: the adversary may adaptively choose its corruption and reconstruction requests based on the public transcript observed so far, but must submit these requests together in a single batch.
Our main technical contribution is a commitment scheme for two-dimensional linear codes based on the PowerBASIS assumption. We combine PowerBASIS commitments with the linear code based secret sharing of Applebaum, Nir, and Pinkas, replacing the Reed–Solomon encoding and KZG commitments used in Bingo. Our commitment supports proof interpolation, enabling parties to recover missing shares and their opening proofs. It additionally achieves a notion that we call one-shot simulation hiding. Together, these properties allow us to adapt Bingo’s framework to obtain Lattice Bingo with the same efficiency and one-shot adaptive security.
Zippel: A Language, Compiler, Runtime, and Analyzer for ZK Proof Systems
This paper introduces Zippel, a language, compiler, runtime, and analyzer for cryptographic proof systems. Zippel lets developers write proof systems with ease using syntax that mimics pseudocode in cryptography papers. It also eliminates entire classes of vulnerabilities by construction owing to its type system and runtime. For example, Zippel automatically synchronizes protocol transcripts and correctly applies the Fiat--Shamir transform. Zippel also has fully automated static analyses that confirm whether a protocol is complete and sound given only the protocol's description. We have implemented 35 proof systems in Zippel including Sumcheck, Schnorr, KZG, Groth16, Bulletproofs, Hyrax, Spartan, Dory, HyperPlonk, DeKART, and Pari. Our evaluation shows that Zippel programs are competitive with hand-written implementations on multi-core hardware, so Zippel's security and implementation benefits do not come at high cost.
Watermarking Proofs with Provenance-Binding ZK-SNARKs
The emerging ecosystem of outsourced proving services, decentralized prover networks, and prover marketplaces raises a new requirement for ZK-SNARKs: the need to watermark proofs with provenance information, such as the prover identity and a fresh request-time nonce. The prover identity records who should receive credit for the proof, while the nonce binds the proof to a particular request and is intended to prevent the prover from reusing work performed before that request was created. The key security requirement is that a prover must perform fresh work—comparable to computing the proof from scratch—when generating a proof for a fresh provenance, even if the attacker may have generated the same proofs before or performed precomputation.
Prior attempts, such as Succinct Network, proposed embedding provenance information in the Fiat-Shamir challenges, though without a rigorous security definition or analysis. We show that this approach is not secure and is vulnerable to preprocessing attacks, in which an adversary can precompute provenance-independent information that can later be used to reduce the effort required to generate proofs for a fresh provenance. We instantiate these attacks against KZG-PLONK.
To arrive at a secure construction, we propose the first formal definition for provenance-binding ZK-SNARKs to capture the above desired property. We present a generic construction that augments code-based polynomial commitments, such as BaseFold and FRI, with provenance binding. Compiling them with Poly-IOPs yields provenance-binding ZK-SNARKs. Our construction incurs minimal overhead.
CHAMP: Cayley HAshing with Matrix Products
Cayley hash functions hash binary strings by representing the bits of the message as elements of a semigroup and multiplying the corresponding elements. This gives Cayley hash functions useful homomorphic properties. Here, we propose CHAMP, a Cayley hash function based on products of $2\times 2$ matrices over a finite field, and discuss its security, implementation, and performance.
Analysis of the Multi-Key Optimization for SPECK
SPECK has recently been introduced as a code-based digital signature scheme exploiting the similarities between the Permuted Kernel Problem (PKP) and the Permutation Code Equivalence Problem (PEP). By utilizing PEP as a trapdoor for PKP, SPECK achieves a significant speedup compared to LESS, replacing expensive Gaussian elimination with vector-matrix multiplications.
This comes at the cost of larger signatures, since each round of the Zero Knowledge (ZK) protocol used in SPECK has soundness error $1/2$.
A well known technique to reduce the soundness errors (and thus the number of parallel repetitions and, ultimately, the signature size) in ZK proofs based on group actions consists in giving multiple elements in the public keys.
Despite being constructed around an instance of PEP, which admits a natural description as a code-based group action, the protocol employed in SPECK deviates from the traditional proof of knowledge used for group actions.
As shown by the authors of SPECK, a naive use of the multi-key optimization may lead to concrete security concerns.
Therefore, the question on whether such a technique can be applied successfully to SPECK remains open.
In this paper, we give a positive answer to such a question.
We revisit the multi-key optimization for SPECK and investigate the underlying security concerns in detail, identifying conditions and parameter constraints under which multiple keys can be securely integrated into the protocol.
Even though, when instantiated with conservative parameters, the multi-key optimization leads to unappealing performance, we show there is wide room for improvements.
Furthermore, we design a ring signature scheme based on the same underlying construction.
Enforcing Winner-Only Disclosure: Verifiable Tally Hiding for Weighted DAO Governance
Token-weighted governance can fingerprint individual voters: when weights are unequal and externally known, the exact weighted tally may reveal who voted which way. Publishing only the winning outcome hides the tally from the public, but a system that reconstructs the tally in order to decide still hands it to whoever runs the computation. Publishing only the winner is not the same as computing only the winner. We present a verifiable protocol for weighted DAO votes in which no protocol role ever receives the weighted tally in plaintext. Each ballot proves in zero knowledge that its encrypted contribution is exactly zero or the voter’s registered weight. Trustees add accepted contributions and compare the sum with a threshold entirely under encryption using the Cortier–Gaudry–Yang (CGY) conditional-gate toolbox, and decrypt only the final decision. A public verifier checks that the computation consumed exactly the ciphertexts accepted by the governance contract. We prove accepted-result correctness even when all trustees are malicious; restricted-I/O SUC security of the tally against static active corruption of any sub-threshold trustee coalition, which is any four of five in our reference instance; and winner-only disclosure relative to the real sealed board. With 1,024 voters, the encrypted tally takes 157 s and independent replay 115 s, while ballot proving dominates the 28.5-minute end-to-end pipeline. A fresh Arbitrum Sepolia execution exercises the complete public-chain path.
SLEEK: Sparse Quasi-Cyclic Codes with Closed-Form DFR Key Encapsulation
Performance in terms of bandwidth and execution time, as well as decoding failures remain important challenges for code-based KEMs. This paper introduces SLEEK: Sparse quasi-cycLic codEs with closEd-form DFR Key encapsulation, a Key Encapsulation Mechanism (KEM) based on Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes. The scheme employs a parallel bit-flipping decoder with three iterations and a closed-form estimate of the decoding-failure rate (DFR). The latter allows parameter selection with analytically bounded failure probability and supports the use of standard IND-CCA transformations.
We designed two variants of SLEEK. The first, SLEEK-LT, targets IND-CCA security for long-term keys, and supports QC-MDPC codes with different rates, allowing a tradeoff between public-key and ciphertext size. The second, SLEEK-E, targets IND-CPA security for ephemeral keys in settings requiring forward secrecy. While SLEEK-LT makes conservative choices and aims at security against active attackers, SLEEK-E relies on a novel QC key structure, for which we establish security equivalent to that of the original QC-MDPC construction under the same assumptions, while reducing key-generation cost. We explore a broad design space and provide parameter sets targeting $128$-, $192$-, and $256$-bit security, together with an $80$-bit configuration for constrained embedded platforms. We also optimize polynomial inversion and parallel bit-flipping decoding, the two dominant components of the implementation. We provide quantitative benchmarks of our optimized AVX2 implementation of SLEEK. For SLEEK-LT, ciphertexts are $4.9\times$ smaller than those of the NIST standard choice, HQC, at the cost of a $47$% increase in the runtime, and is $1.3\times$ to $2.7\times$ faster than BIKE. For SLEEK-E, execution time improves by $1.6\times$ over HQC with a bandwidth usage reduced by $2.1\times$. Compared with Lean-BIKE, SLEEK-E is $5.3\times$ faster and substantially reduces the impact of decoding failures on system reliability.
I Want to Ride My BIKE: Customizing Bit-Flipping Decoders for Ephemeral Key KEMs
Large public keys and ciphertexts remain a major obstacle to the deployment of post-quantum cryptosystems in applications currently relying on compact classical schemes. In code-based post-quantum key encapsulation mechanisms, reducing the Decoding Failure Rate (DFR) generally requires larger parameters, further increasing communication and storage overheads. Ephemeral key-pair scenarios allow a different trade-off: ideally, each secret key is used for a single decapsulation, limiting the opportunities to observe and exploit decryption failures. We investigate how this setting can be used to reduce the public-key and ciphertext sizes of code-based key encapsulation mechanisms such as BIKE.
We present the first optimized implementation of the $\textsf{BF-max}$ decoder:
compared with conventional parallel bit-flipping decoders currently used by BIKE, $\textsf{BF-max}$ provides better error-correction capability, but its computational structure makes an efficient implementation less straightforward.
Combining $\textsf{BF-max}$ with other decoders from the literature, we introduce decoding strategies that offer different trade-offs among DFR, execution time, public-key size, and ciphertext size.
Experimental results show that the proposed design reduces both public-key and ciphertext sizes by 7.8\% compared with LeanBIKE, a BIKE variant specifically designed for ephemeral-key use, while retaining similar execution time and DFR.
For additional context, the selected parameter set yields a combined public-key and ciphertext size that is 22\% smaller than that of BIKE and smaller by a factor of 2.79 than that of HQC. Note that BIKE and HQC, unlike LeanBIKE and our design, target the long-term-key setting. As a concrete application, we show that the solutions we propose make it possible to incorporate BIKE into constrained protocols, such as Internet Key Exchange version 2 (IKEv2), in which no code-based KEM would otherwise fit.
New Constructions of Quadratic and Cubic Permutations Admitting Optimal Threshold Implementations
Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. Threshold implementation (TI), introduced by Nikova et al. in 2006, was proposed to resist differential power analysis side-channel attack on hardware implementations of block ciphers and eliminate information leakage due to glitches. For a function of algebraic degree $t\ge 2$, a TI requires at least $t+1$ shares. However, achieving this bound without fresh randomness is challenging, and we refer to such TIs as optimal. While a universal construction using $t+2$ shares is available, attaining the $t+1$ lower bound depends on the target permutation.
In this paper, we present four constructions for optimal TIs of bijective S-boxes. We first demonstrate how adjoining identity coordinate functions enables optimal TIs, and then prove that $\mathcal{Q}_{30}^5$ admits optimal TIs. Second, we derive a matrix criterion for a class of quadratic permutations with optimal TIs, which covers all known examples, and can yield new $6$-bit quadratic classes with optimal TIs. Third, we introduce a weighted interpolation construction, which yields an infinite family of power permutations admitting optimal TIs, thereby providing counterexamples to the conjecture by Piccione et al. in 2023 that nonlinear power permutations cannot meet the $t+1$ lower bound. Notably, this family includes Bracken-Leander functions. To the best of our knowledge, this represents the first time optimal TIs have been constructed for permutations achieving differentially 4-uniform. Finally, we present a derivative-uniform framework. Although this construction is not algebraic-degree-preserving for TIs and comes at a high cost of implementation, it is of significant theoretical interest and enables us to prove that every $4$-bit cubic permutation admits optimal TIs.
Secure Compilation of Probabilistic Side-Channel Countermeasures
Probabilistic countermeasures are a common means of protecting programs against side-channels. These countermeasures are hard to implement and are routinely broken by compilers. Proving that a compiler preserves probabilistic side-channel security directly would require reasoning about perfect simulatability of distributions, a challenging technique normally reserved for high-assurance cryptography in frameworks like EasyCrypt and out of scope for compiler correctness.
In this paper, we present a language- and leakage-model-agnostic framework for provably secure compilation of probabilistic side-channel security notions. Our main contribution is formalizing a deterministic leakage-preservation relation that implies preservation of probabilistic security notions, including d-NI and d-SNI for masking and cryptographic constant-time. Our framework establishes the same guarantees without probabilistic proof obligations, reducing preservation to a per-pass simulation argument on deterministic traces.
We use the Rocq proof assistant to prove that a model of the core pipeline and several optimizing passes of the Jasmin compiler preserve security in the value-probing model with glitches. We also show how to harden against transition leakage with lightweight annotations at the source level. On top of this, we build libmasking, an open-source library of arbitrary-order masked gadgets in Jasmin that securely compiles to ARM and RISC-V assembly, provides C language bindings, and is benchmarked on real hardware. Together, these contributions are a step towards programming environments in which masked code is written or generated, verified at the source level, optimized, and compiled without breaking security.
LazyArc: Dynamic Out-of-Order Engine for High-Throughput FHE
Fully Homomorphic Encryption (FHE) is a modern cryptographic technique that allows performing computations directly on encrypted data. This makes FHE an indispensable method for privacy-preserving applications, where users' data are encrypted and processed by a potentially untrusted third party. Nevertheless, FHE operations are computationally expensive, often rendering them impractical for realistic scenarios. Notably, a major performance bottleneck for FHE is an operation called bootstrapping that allows refreshing the inherent noise of FHE data to support more computations. In this work, we introduce LazyArc, a versatile lightweight dynamic Out-of-Order (OoO) software engine that enables higher-throughput FHE computations. Our proposed OoO paradigm improves the performance by masking the latency of bootstrapping via a bespoke instruction-bootstrapping scheduling paradigm. Also, we introduce a novel tool, dubbed RegisterMap Tool, to statically analyze FHE arithmetic circuits and track the noise of each ciphertext to allow proactive bootstrapping scheduling. Our approach is evaluated using linear algebra benchmarks and achieves more than 2x speedup compared to in-order baselines, and more than 5x speedup compared to the FHEBooster scheduler.
Low-Depth Bootstrapping for Matrix-Native FHE
Fully homomorphic encryption (FHE) enables computation directly on encrypted data and is increasingly researched for privacy-preserving machine-learning inference. Such workloads are dominated by matrix multiplication, which is not represented natively by conventional vector-oriented FHE schemes. CKKS is widely used for approximate encrypted inference because it supports packed real and complex arithmetic; however, matrix multiplication generally requires specific packing formats that are tailored to certain models, and involves many expensive ciphertext rotations. Depending on the matrix dimensions and packing strategy, these techniques can introduce substantial latency and memory overhead. The recently proposed Gentry-Lee (GL) scheme instead provides native slot-encoded matrix arithmetic through a multivariate ring construction while retaining approximate packed computation. Although promising, the prime-p GL instances considered here require prime-length NTTs and a three-dimensional DFT message encoding, whose efficient implementation has received limited study. Moreover, the original scheme does not specify a concrete bootstrapping procedure, which is required to support the deep computations used by large neural-network models.
In this work, we present a low-depth complex bootstrapping framework tailored to the GL scheme. Our construction combines a two-stage GL StC, in which the X-axis inversion uses native plaintext-ciphertext matrix multiplication and the W-axis inversion uses a diagonal BSGS transform, with a slice-wise adaptation of SHIP to the Gaussian (X, W) algebra. The public masked-column candidates evaluate the complete W-axis monomial action and the fine X-axis residue, leaving only the coarse X-axis displacement for hidden HMux selection and eliminating encrypted W-axis selection. We further algebraically reduce the online plaintext-encoding requirement of the masked-column interface from the fully expanded candidate-family upper bound of 8θφ(p) + 2 to 2φ(p) + 2 plaintexts per Y-slice and optimize the Rader NTT through fused kernels and other arithmetic optimizations.
Across the evaluated configurations, the faster GL axis order gives amortized per-slice StC speedups of 3.44x-4.10x at one thread and 7.75x-9.04x at 32 threads over the matched CKKS baselines. For full complex bootstrapping, the CKKS-to-GL per-slice latency ratios are 0.78-1.21 at one thread and 1.05-1.95 at 32 threads.
Chimera: A Hybrid GPU Backend for Sumcheck Acceleration in Zero-Knowledge Provers
Sumcheck is increasingly used in proof systems based on multilinear polynomials, but its execution structure differs from that of conventional GPU targets such as MSM and NTT. Each round contains substantial data-parallel polynomial computation, but consecutive rounds depend on challenges derived from previous rounds and interact with the surrounding prover's proof-generation operations. Efficient acceleration therefore depends not only on GPU arithmetic throughput, but also on where polynomial data resides, what crosses the CPU-GPU boundary, and when execution should return to the CPU.
We present Chimera, a hybrid CPU-GPU backend for Sumcheck computations in the Spartan R1CS prover. Chimera keeps large polynomial data on the GPU across profitable rounds, returns only the compact polynomial values needed by Spartan's transcript, and sends the resulting challenge back to the GPU for folding. It switches sufficiently small late rounds to Spartan's native CPU implementation. When polynomial data exceeds GPU memory, Chimera processes it in smaller portions and transitions to resident GPU execution once the remaining data fits. Chimera preserves Spartan's proof format and verifier behavior while also reducing CPU-side overhead directly surrounding the accelerated Sumcheck computations.
On BN254 Spartan R1CS instances, Chimera reduces the measured
Sumcheck-related region from \(672.785\) ms to \(84.245\) ms at
\(N=2^{17}\), a \(7.99\times\) speedup. Complete proving time improves at every measured size, reaching \(1.27\times\)-\(1.64\times\) speedup for \(N=2^{24}\)-\(2^{27}\). Separately, our standalone quadratic GPU Sumcheck executes in \(28.7\) ms at \(N=2^{22}\), compared with \(84.2\) ms for ICICLE's CUDA Sumcheck implementation, a \(2.94\times\) GPU-to-GPU improvement. These results show that effective Sumcheck acceleration depends on both efficient GPU execution and careful integration with the surrounding proof system.
Refined Approx-SVP Rank Reduction Conditions and Adaptive Lattice Reduction for MSIS Security Estimation
The security of lattice-based cryptography relies critically on the concrete hardness of the approximate shortest vector problem (Approx-SVP). For cryptographic-sized instances, existing Approx-SVP rank reduction conditions may be overly aggressive, as they implicitly assume access to a large number of extremely short lattice vectors. In this work, we systematize and refine Approx-SVP rank reduction conditions from a feasibility perspective. We identify that, in the context of the dimension-for-free (D4f) technique, the existence of a single sufficiently short vector is the essential requirement, and we derive two refined and compact rank reduction conditions accordingly. The first condition is based on geometric properties of lattice sieving, while the second incorporates a basis-quality-dependent probabilistic bound. These results are validated through extensive experiments on high-dimensional lattices, where the compact condition outperforms prior methods by up to a factor of $60$ in dimensions $850$ and $925$. To reliably realize these conditions in high dimensions, we present APBKZ, an adaptive Pump-based lattice reduction strategy that dynamically selects the blocksize and D4f parameters according to the evolving Gram-Schmidt profile. We further introduce HeadAPBKZ, a head-focused execution mode that restricts reduction to a critical prefix once the rank reduction condition is satisfied. Combining these advances, we develop an improved concrete security estimation framework for the MSIS problem. Applied to Dilithium, our analysis indicates that, when compact rank reduction behavior is integrated with the D4f technique, the estimated concrete security of Dilithium is reduced by 3.65-6.09 bits relative to the conservative Core-SVP baseline, providing a more realistic concrete assessment. We also derive an analytic approximation whose closed-form estimates remain close to the numerical estimation, with discrepancies of only about 1.1 bits.
Janus-FHE: Reducing Microarchitectural Leakage in GPU-Based Homomorphic Encryption
Homomorphic Encryption (HE) enables secure cloud computing through computations on encrypted data, but the physical execution of HE workloads on shared GPUs can still expose relevant metadata through microarchitectural behavior. We present a case study of BFV relinearization in HEonGPU, a state-of-the-art GPU HE library, and show that repeated executions exhibit structured, reproducible variation in shared-L2 activity across relinearization-key contexts. Our analysis further shows that the regular control-flow structure observed in the optimized HEonGPU binary is compiler-dependent rather than enforced by the source implementation. Together, these observations motivate an HE design in which execution regularity is established explicitly rather than obtained as a consequence of compilation.
We present JANUS-FHE, a GPU framework for BFV multiplication and relinearization that restructures the computation around fixed-width large-integer arithmetic. JANUS reconstructs ciphertext coefficients from the RNS representation, uses Kronecker substitution to express polynomial multiplication as large-integer multiplication, and evaluates the resulting convolution through a Stockham-organized Discrete Galois Transform (DGT). JANUS carries this fixed execution structure through product recovery, BFV scale-and-round, and method-I relinearization, using fixed-width computation and branchless masked arithmetic throughout. This formulation makes the control flow, memory-access schedule, and execution geometry depend on public parameters rather than the ciphertext or evaluation-key values. Under the same shared-L2 methodology used for HEonGPU, JANUS exhibits fewer recurring key-conditioned differences, while SASS-level analysis confirms that its intended regular execution structure is preserved after compilation. At \(N=8192\), JANUS completes the full multiplication-and-relinearization path in \(0.350\) ms, compared with \(0.153\) ms for HEonGPU, representing a \(2.29\times\) latency overhead for JANUS's parameter-determined execution structure.
Sparse Secrets, Dense Problems: Efficiently Masking HQC in Hardware
HQC has recently been selected by NIST as a code-based alternative to ML-KEM and is currently undergoing standardization. While multiple timing and power side-channel attacks against HQC have been presented, application of masking has so far only been studied for software implementations.
As part of this work, we close this gap by first proposing a novel masking technique for the sparse-dense vector multiplication, one of the core components in all HQC operations. We manage to securely exploit the sparsity of the secret operand using a mixed Boolean and arithmetic masking technique and prove its first-order security in the transition- and glitch-robust probing model as well as its PINI-composability. With the same memory width, our configurable and highly parallelizable masked design takes only 3% more clock cycles than a previous unprotected HQC multiplier. Furthermore, our technique requires only 81 bits of randomness per cycle, irrespective of its parallelism. However, like previous Rotate-and-Add constructions, it is vulnerable to profiled horizontal side-channel attacks, which recover all support indices within ±8 positions from 200 traces of our FPGA implementation despite TVLA showing no signs of leakage after 10 million traces. To prevent such attacks, we integrate efficient hiding countermeasures natively into the architecture of the multiplier, resulting in only 1.7% additional latency and moderate area overhead.
Together with efficiently masked fixed-weight samplers and a masked decoder, we present the, to our knowledge, first fully masked hardware implementation of HQC, supporting first-order masked key generation, encapsulation, and decapsulation. Notably, our masked key generation is faster than a previous unprotected design from literature on an Artix-7 FPGA. Lastly, all modules of our complete designs show no signs of first-order leakage after 1 million traces.
A Billion Hard CRYSTALS: Automated Design Space Exploration of Mixed-Domain Masking for PQC in Hardware
Lattice-based post-quantum cryptographic schemes such as ML-KEM or ML-DSA combine bitwise operations, which are most efficiently masked using Boolean secret sharing, with arithmetic operations modulo q, which are cheaper to mask using an additive sharing in the respective field or ring. Previous work has automated the generation of Boolean-masked hardware circuits as well as the design space exploration process, but to the best of our knowledge, no similar generic framework exists for hardware designs requiring mixed masking domains.
Such designs pose three additional challenges. First, share-wise arithmetic requires no registers to be secure, leading to long critical paths without deliberate pipelining. Second, the conversions required at domain boundaries increase both complexity and susceptibility to human error. Finally, generation of masking randomness from a traditional PRNG requires post-processing, e.g., via rejection sampling, to achieve uniformity modulo q, which results in a variable output rate.
We solve these issues and integrate our scheme-agnostic solutions into the masking and design space exploration framework HADES. An efficient pre-synthesis critical path estimation, which is around 60 times faster than synthesis with traditional timing analysis, enables effective exploration of mixed-domain masked circuits without compromising the maximum clock frequency. Our adapted gadget-based masking procedure tracks masking domains and inserts pipelined conversions at domain boundaries automatically, or lets the template developer place resource-shared conversions manually. Lastly, a Markov-chain model of probabilistic masking randomness generation and buffering yields cost-minimal design configurations that guarantee stall-free masked operation except for a user-defined failure probability.
We evaluate our methodology for multiple relevant moduli and implement an arbitrary-order masked ML-KEM decapsulation core as a case study for our open-source framework. Its area-optimized configurations represent, to the best of our knowledge, the most compact reported ML-KEM designs, with 54.1 kGE unmasked and 125.4 kGE at first order using the NanGate45 library. Jointly optimizing for area and critical path yields competitive clock frequencies of 325–429 MHz for at most 31% more area, which is still smaller than all previous designs. Practical side-channel security at both first and second masking order is validated through FPGA-based TVLA measurements of the full decapsulation routine using 10 million traces each.
$\textsf{Sluice}$: Prove-Phase Bounded-Memory Groth16 via Read-Write Streaming
We present $\textsf{Sluice}$, a read-write streaming Groth16 prover that reduces $\textit{prove-phase}$ random-access working memory from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$ once the CRS, QAP, and witness are materialized as private streams. It preserves the standard Groth16 interface: a proof of 3 group elements, 3-pairing verification, and unchanged verifier contracts.
Our key technical contribution is $\textit{Split-Butterfly-Merge}$
($\mathsf{SBM}$), an NTT algorithm in the read-write streaming model with $\mathcal{O}(\log N)$ memory, $\mathcal{O}(N \log N)$ total I/O, and $\mathcal{O}(\log N)$ sequential passes over external storage.
Combining SBM with streaming sparse R1CS evaluation and chunked
Pippenger MSM yields a verifier-compatible Groth16 proving path that
exchanges RAM for sequential storage I/O and wall-clock time. Our
prototype uses a fixed-window MSM engineering point; the measurements validate memory reduction and proof compatibility, while the theorem states the asymptotically tuned MSM schedule.
We implement $\textsf{Sluice}$ over BN-254. Direct prove-only runs produce valid 128-byte proofs through $N=2^{25}$. The same-size bounded-memory comparison is at $N=2^{23}$: $\textsf{Sluice}$ succeeds under an 8GB Linux cgroup cap, whereas the standard prover is killed under 8GB and 12GB caps and succeeds only at 16GB. These results position $\textsf{Sluice}$ as a storage-rich, RAM-limited proving option rather than a replacement for optimized in-memory provers.
Power Analysis on SQIsign via Ideal Reconstruction from Quaternion Leakages
SQIsign is an isogeny-based signature scheme, which is one of the Round-3 candidates for NIST's additional post-quantum digital signature standardization.
NIST considers resistance to side-channel attacks as one important factor in evaluating digital signature schemes.
However, side-channel analysis of SQIsign remains very limited.
To the best of our knowledge, all existing studies target the Round-1 version, so their applicability to the substantially revised Round-3 SQIsign has not been established.
Moreover, existing studies either provide experimental validation only for toy parameters or assume exploitable leakage without demonstrating its extraction in practice, leaving their applicability to realistic implementations unclear.
In this work, we identify five side-channel vulnerabilities in the signing procedure of Round-3 SQIsign and provide polynomial-time algebraic algorithms that recover the secret key from the corresponding leaked intermediate values.
Additionally, we further provide algorithms that enable the reconstruction of the complete secret key even when the side-channel leakage reveals only partial bits of an algebraic value, for each vulnerability.
Finally, we further perform power analysis attack on the SQIsign source code, extracting the necessary leakage or its partial information for each vulnerability.
Yoshan: Algebraic-Circuit Co-Synthesis and Search Methodology of Hardware-Efficient S-Boxes
Choosing a hardware S-box means balancing cryptanalytic strength (differential uniformity δ, linearity L, and algebraic degree) against circuit cost (AND count and AND depth D). Under masking, non-linear gates dominate silicon area, registers, and fresh randomness, while D sets pipeline latency. As a result, automated searches have largely retreated to quadratic permutations (D = 1), whose slow degree growth forces high cipher round counts. We present Yoshan, a co-synthesis engine that optimizes an S-box permutation and its gate-level circuit together across n ∈ {5,6,7,8}. Inside a quality-diversity archive, Yoshan seeds search with subfield towers, Feistel/Misty/MM networks, affine wrappers, CCZ graph automorphisms, and bilinear or shear constructions. It then evolves circuits via cryptographically guided DAG rewrites and exploratory differentiable Piling-Up seeding and crossover with Hungarian LSAP projection, before compressing them with SMT sub-DAG shaving, stage-preserving CSE, exact depth-1 SAT, and four-tier inverse compilation. Every archived circuit is exported gate for gate to SystemVerilog and certified by exhaustive simulation and a Z3 miter. Across 31,337 certified netlists (30,986 distinct permutations) in 56 (n,δ,L,deg) profiles, EA invariants and an exact affine-equivalence solver against a 712-entry catalogue (power maps, 5- and 6-bit quadratic/quartic classifications, Feistel/MISTY/Bridge structures, two-point-swapped power maps, and cipher S-boxes) partition the archive into known catalogue classes (Category A, 2,681 permutations) and permutations certified EAseparated from it (Category B, 28,305 permutations; 12 benchmark classes YSHn,i). All 30 benchmark S-boxes and their explicit inverses are synthesized gate-exactly in 45nm CMOS (unmasked and pipelined d = 2 DOM) and traced from seed to final netlist. For known classes, we obtain a gate-exact depth-3 AES-class pair (42 AND, 101 XOR; inverse 42 AND, 106 XOR at D = 3) and a provably AND-optimal 5-AND, D =1 circuit for the 5-bit Q71 class (δ = 4,L = 16). When the lookup table can vary, we find a 12-AND 6-bit degree-5 S-box YSH6,5 (δ = 6,L = 24,β = 14), a 5-AND, D =2 5-bit quartic S-box YSH5,2 in both directions, and 28- and 18-AND 8-bit degree-7 S-boxes, all compared against the best published circuits.
safeRNSgcd: Accelerating Falcon key generation with RNS in SafeGCD
The deepest level of Falcon's NTRU solver needs only one Bézout
coefficient from two large integer resultants already represented in a
residue number system (RNS). We give $\mathtt{safeRNSgcd}$, which computes
this coefficient while keeping the large states in RNS. Its central
insight is that centered explicit CRT can recover the exact low bits
needed by SafeGCD batches using single-word fixed-point arithmetic.
Integrated into $\mathtt{ntrugen}$, our
C implementation reduces inversion and private-key basis-generation
costs on a Raspberry Pi 5 and two x86-64 processors, compared with
original $\mathtt{ntrugen}$ and a variant omitting the unused coefficient.