Laconic Oblivious Transfer (OT) enables a receiver to compress a large database into a short digest, allowing a sender to generate a succinct ciphertext that reveals only a single indexed message. While prior works achieve efficient constructions in the semi-honest model, known solutions for malicious security rely on inherently heavy non-black-box techniques, such as garbled circuits or succinct arguments, resulting in impractical schemes. In this work, we present the first construction of maliciously secure laconic OT that makes fully black-box use of its underlying primitives. Our construction is based on a simple and widely used paradigm combining vector commitments with witness encryption, previously known to yield efficient semi-honest protocols. We show that this approach can in fact achieve malicious security by introducing two minimal yet powerful enhancements: equivocal vector commitments and maliciously secure witness encryption. We prove that these properties suffice to obtain laconic OT with security against malicious senders in the universal composability model and against malicious receivers in the context model. We instantiate our framework from standard assumptions, including LWE and bilinear Diffie-Hellman variants, obtaining schemes in the standard model. Notably, our constructions avoid heavy non-black-box tools mentioned before, and therefore achieve efficiency comparable to the state-of-the-art black-box constructions with merely semi-honest security. In particular, in certain settings, we obtain malicious security at essentially no additional asymptotic cost. Our results resolve a central question on the feasibility of practical, maliciously secure laconic OT, and provide a unifying pathway for efficiently achieving malicious security in laconic cryptography.

In outsourcing computation to untrusted servers, one can cryptographically ensure privacy using Fully Homomorphic Encryption (FHE) or integrity using Verifiable Computation (VC) such as SNARK proofs. While each is practical for some applications in isolation, efficiently composing FHE and VC into Verifiable Computation over Encrypted Data (VCoED) with verification faster than local computation remains a challenge. We introduce $\mathsf{Laminate}$, a family of VCoED protocols for adding integrity to computations delegated using BGV/BFV-style FHE. Our approach combines the blind interactive proof framework with the GKR proof system, which avoids computing commitments to intermediate computation states under FHE. Our client-efficient variant employs novel transcript packing and folding techniques that reduce proof size to $O(\log^2 n + N)$ words (suppressing security parameters) for bounded-depth size-$n$ circuits, where $N$ is the BGV/BFV ring dimension. Unlike prior FHE-over-SNARK schemes, $\mathsf{Laminate}$ preserves the SIMD parallelism of FHE for both payload circuit evaluation and proof generation; eliminates the need for witness reductions; is field-agnostic; and adds only constant multiplicative depth on top of payload evaluation while performing $\widetilde{O}(n_{\mathsf{FHE}})$ FHE operations, where $n_{\mathsf{FHE}}$ is the number of payload FHE operations. We give an end-to-end concrete integrity analysis, implement the complete protocol, and provide a reproducible methodology for measuring server overhead and per-request client computation. We benchmark $\mathsf{Laminate}$ on payload circuits with $n=2^{34}$ scalar gates. One scheme variant has an overhead of $21$--$33\times$ compared to FHE evaluation without integrity, with proofs of $52$--$54\,\mathrm{MB}$. Another variant reduces overhead to $10$--$14\times$, with larger proofs. For both, per-request client computation is much faster than local evaluation, demonstrating concrete outsourced computation with privacy and integrity, a key distinction from prior VCoED work.

Vector Commitments (VCs) are a cryptographic primitive that allows users to commit to a tuple and later provide proofs about entries of the committed tuple. Literature on VCs provides many secure constructions with properties attractive for decentralized applications. These include fast commitment/proof update algorithms after a value in the committed vector changes, algorithms to aggregate position proofs, generating proofs for subvectors, commitment hiding, and many more. However, these works assume a static setting, where only vector values change and the length of the committed vector never changes. We initiate the study of designing VCs which support efficient updates to commitments and proofs after a change in vector length occurs (i.e. an insertion or a deletion of a vector value at an \textit{arbitrary} position). In order to construct such a primitive, we formalize a VC framework implicitly considered in VC based verifiable decentralized storage constructions. Parties control a subset of positions in the committed vector. A proof for an inserted vector value at a given position may only be generated via participation from enough honest parties. We call such primitives \textit{Multiparty Dynamic Vector Commitments}. Our work provides formal definitions for multiparty dynamic VC functionality and security. In particular, standard VC binding does not extend to our dynamic setting. This motivates us to define the \textit{dynamic multiparty binding} security notion. We also comment on how multiparty dynamic VCs can be applied to extend existing VC based instantiations of verifiable storage. Finally, we provide a vector commitment construction and show that it possesses multiparty dynamic binding under standard lattice assumptions.

Good-case latency, studied in early fast-consensus protocols (Martin and Alvisi, DSN 2005) and formalized by Abraham, Nayak, Ren, and Xiang (DISC 2020), captures a natural efficiency goal: when the sender is honest, agreement should be reached quickly for the honest parties. In the standard classical model, however, there exists a barrier for any $f\geq n/3$ corrupted parties. Specifically, synchronous broadcast requires good-case latency at least $\Delta+\delta$ for $f\geq n/3$, where $\delta$ is the actual, unknown message-delay bound and $\Delta \gg \delta$ is its known, conservative upper bound. Under partial synchrony, consistency and liveness cannot even both hold for $f \geq n/3$ (Dwork, Lynch, and Stockmeyer, JACM 1988). In this work we study the use of quantum information to get past these classical barriers, specifically using one-shot signatures (OSS) (Amos et al., STOC 2020, Shmueli and Zhandry, CRYPTO 2025). OSS prevents even a corrupt signer from issuing signatures on different messages under the same verification key, which provides cryptographic non-equivocation without trusted hardware assumptions. Assuming OSS and a public-key infrastructure, we obtain two main results against quantum polynomial-time static corruptions. First, under synchrony, we construct a state-machine replication (SMR) protocol without clients, with optimal $\delta$ good-case latency, tolerating any $f<n$ corruptions among $n$ parties. Second, under partial synchrony, we obtain SMR with $2\cdot \delta$ good-case latency which is consistent under any number of corruptions and live assuming $f<\frac{n}{2}$. Specifically, a corrupt majority may cause progress to stop, but cannot create conflicting histories. Such an always consistent protocol is impossible classically (without assumptions like trusted hardware) even if liveness is only required to hold against a single corrupt party. In both our SMR protocols, communication is entirely classical, with only local quantum computation.

Many recent constructions of probabilistic proofs achieve fast proving times but have high space complexity (much higher than that of the computation being proved). Empirically this arises due to the fact that error-correcting codes, a key ingredient of such constructions, suffer from limiting time-space tradeoffs. It remained open, however, whether such time-space tradeoffs exist for proofs themselves. We establish time-space tradeoffs for probabilistically checkable proofs (PCPs) as well as for their multi-round extension, interactive oracle proofs (IOPs), with straightline knowledge soundness. Our results hold for machine computations that have sequential input access, the same model for which similar tradeoffs hold for error-correcting codes. We complement this result by describing an IOP for R1CS that avoids the tradeoff but requires random access to the R1CS witness. Our techniques build on and extend results for codes of Cook and Moshkovitz (CCC~2024). A key difficulty that we encounter in establishing our tradeoff is that distance of the code plays a key role in prior results, while for probabilistic proofs there is no natural notion of distance. Nevertheless, we show that, assuming the existence of collision-resistant hash functions, we can establish time-space tradeoffs by carefully relating a small-space machine's information flow to the proof system's properties.

Sparse fixed-weight vector sampling is a highly critical primitive in several post-quantum cryptography schemes. It has also been the target of multiple side-channel attacks, demonstrating the need for robust implementations. While such implementations do exist, they are not necessarily practical in terms of runtime, and some have already been shown to be insecure. At CHES 2026, Filho et al. presented a runtime-optimized, but not side-channel protected, sparse fixed-weight vector sampling algorithm named Sota Voce. It consists of the Sota support sampler and MWSupport support-to-vector conversion, where the latter is planned to be included in the next HQC implementation. This work explores how both parts of Sota Voce can be transformed into a power side-channel protected implementation using masking gadgets for embedded devices. At the same time, we aim to preserve its competitive performance advantage over other masked implementations. By bitslicing core components of the algorithm, including sorting, merging, and compaction, we achieve high parallelism of the computation, improving the overall runtime. Moreover, we avoid slow masking conversions by masking exclusively in the Boolean domain. Thereby, our masked implementation is orders of magnitude faster than the state-of-the-art, while showing no power side-channel leakage in TVLA evaluations. For instance, for HQC, we achieve a speedup of up to 45x in comparison to previous work.

Privacy-free garbling schemes of Frederiksen et al. (Eurocrypt ’15) are designed to satisfy only the authenticity criterion of Bellare et al. (ACM CCS ’12) and to be more efficient than full-fledged garbling schemes. In this work, we improve the state-of-the-art privacy-free version of half-gates (HG) garbling of Zahur et al. (Crypto ’15) by allowing an AND gate to be garbled with zero ciphertexts whenever at least one of its input wires is freely settable by the garbler. Our full solution, AuthOr, then combines the ideas from the information-theoretic garbling of Kondi and Patra (Crypto ’17) with the improved HG-based scheme we obtain. AuthOr has a lower communication cost (i.e., garbled-circuit size) than HG garbling without any additional security assumptions. Theoretically, AuthOr’s garbled-circuit size reduction over HG garbling ranges from 0% to 100%, with the exact improvement depending on the circuit structure. We have implemented our scheme and evaluated it on various circuits constructed by independent researchers. Our experimental results show that, in practice, the garbled-circuit size reduction can reach roughly 98%.

Rerandomizable garbling is a powerful extension of Yao’s garbled circuits that allows a garbled circuit to be refreshed without changing its functionality, while preserving privacy as long as at least one rerandomization step is honest. Existing constructions, however, are limited to Boolean circuits and incur significant communication overhead. In this work, we initiate the study of rerandomizable garbling for arithmetic circuits. We present the first rerandomizable arithmetic garbling scheme, based on techniques inspired by recent advances in garbling from homomorphic secret sharing. Our construction departs fundamentally from previous approaches and achieves communication complexity $O(|\mathbf{C}|\log B)$ for circuits $\mathbf{C}$ with $B$-bounded computation. Concretely, our scheme requires 17 group elements per multiplication gate, while addition gates are free. Our scheme can be instantiated under standard subgroup-indistinguishability assumptions, including the Decisional Composite Residuosity (DCR) assumption and assumptions over class groups.

In a (non-interactive) multi-signature scheme, parties independently generate keys and produce signatures on a common message, which can be aggregated into a single signature verifiable with respect to the set of public keys. Existing multi-signature constructions, however, suffer from at least one of two limitations: either (1) aggregate signatures cannot be further aggregated, or (2) verification requires auxiliary information beyond the set of public keys, such as the aggregation topology. We argue that these limitations significantly restrict the applicability of multi-signatures in large-scale distributed systems, such as proof-of-stake blockchains. To address this gap, we initiate the formal study of hint-free multi-signatures, which support multi-hop aggregation while allowing verification using only the set of public keys. To the best of our knowledge, the only previously known (folklore) construction that is fully hint-free relies on recursive SNARKs, which introduces unclear heuristics for security (e.g., proving statements about random oracle relations) or inherently limits the depth of the aggregation topology. We show that hint-free multi-signatures can be realized without proof recursion, in the standard model. At a high level, we show how to publicly normalize BLS multi-signatures so that verification depends only on the set of public keys rather than a multi-set. While our scheme is not practical (it uses indistinguishability obfuscation), it establishes the feasibility of the primitive provides a foundation for future work on practical constructions.

Encrypted multi-maps (EMMs) allow a client to outsource a multi-map to an untrusted server and then later retrieve the values corresponding to a queried label. They are a core building block for various applications such as encrypted cloud storage and searchable encryption. One important metric of EMMs is memory-efficiency: most schemes incur many random memory accesses per search query, leading to larger overhead compared to plaintext queries. Memory-efficient EMMs reduce random accesses but, in most known solutions, this comes at the cost of higher query bandwidth. This work focuses on EMMs run on SSDs and we construct two page-efficient schemes, one static and one dynamic, both with optimal search bandwidth. Our static scheme achieves $\tilde{O}(\log N/p)$ page-efficiency and $O(1)$ client storage, where $N$ denotes the size of the EMM and $p$ the SSD's page size. Our dynamic scheme achieves forward and backward privacy with $\tilde{O}(\log N/p)$ page-efficiency and $O(M)$ client storage, where $M$ denotes the number of labels. Among schemes with optimal server storage, these are the first to combine optimal bandwidth with good page-efficiency, saving up to $O(p)$ and $\tilde{O}(p\log\log (N/p))$ bandwidth over the state-of-the-art static and dynamic schemes, respectively. Our implementation on real-world data shows strong practical performance.

Using the language of categories, we introduce a novel framework abstracting the key algorithmic features of the Deuring correspondence between supersingular elliptic curves and quaternion orders and of the post-quantum signature scheme SQIsign based on it. We then show how to construct an interactive identification scheme and digital signature within this framework, and also instantiate more advanced primitives, such as a chameleon hash function. We present two distinct instantiations of the framework based on isogenies of supersingular elliptic curves: the first recovers (one-dimensional) SQIsign, while the second leads to the recently published SQInstructor.

Isogeny-based cryptography implementations have to navigate a large space of options for representing elliptic curves and isogenies and for the corresponding arithmetic. This work collects, completes, and organizes the set of algebraic maps and relations available when working with genus-zero modular curves $X_0(N)$, which parametrize cyclic $N$-isogenies of elliptic curves and can be represented by a single field element. This abstract notion covers many single-parameter curve models, such as Montgomery, Edwards, Jacobi quartic, Hessian curve, Deuring normal form. Such single-parameter models for the same modular curve are related by degree-1 rational maps, which limits the remaining options for improving the expressions. This representation is universal in the sense that it can be obtained from any other algebraic parametrization of such isogenies, or simply from the $j$-invariants through which the isogeny passes, away from singularities. We propose a method to derive rational maps for computing such lifting from the $j$-line to $X_0(N)$. Our main technical contribution is the definition, analysis, and computation of non-backtracking modular polynomials over these curves obtained using an extended method of Elkies. In addition to characterizing cyclic extensions of isogenies, they have many other useful properties, such as having lower degree and being sparser than other typical modular polynomials, smoother walk models (being better at distinguishing different isogenies), carrying additional isogeny of different degree along the walk. We also propose radical representations of the same relation, which sheds new light on a few existing radical isogeny formulas. We illustrate the use of the framework by achieving more compact R1CS encodings for isogeny proofs of knowledge.

MPC with dynamic committees achieves scalability by having small committees execute each round of the computation, instead of involving all parties in the entire execution. However, achieving Guaranteed Output Delivery in efficient information theoretical protocols requires larger honest majority committees, limiting scalability. Moreover, using preprocessed correlated randomness to speed up the computation is prohibitively expensive due to the cost of transferring such randomness to parties that have not yet joined the execution. We propose Eras MPC, a model where small dishonest majority computation committees execute one or more rounds of the computation with the help of honest majority preprocessing and checkpointing committees. The computation is carried out in "Eras", which are sets of shorter epochs. In the beginning of each Era's first epoch, a preprocessing committee generates correlated randomness for the computation epochs to be executed by different computation committees. In the end of an Era, checkpoint committees verify the current state of the computation, save this state if it is valid and provide the latest valid state to the next Era. We show an Eras MPC protocol where the preprocessing is carried out using an honest majority MPC protocol to generate authenticated Beaver triples, requiring only enough rounds of interaction to perform two subsequent batches of multiplications. The computation is done via the SPDZ online phase executed in each epoch by a small dishonest majority committee. Finally, intermediate state is checkpointed by verifying the validity of wire shares and saving wire values in $4$ rounds, each executed by a different honest majority checkpoint committee.

The widespread adoption of shared last-level caches in modern multi-core processors improves memory efficiency but introduces timing channels between untrusted programs. In particular, Flush+Reload serves as a high-resolution cache side channel and a fundamental data leakage mechanism in transient-execution attacks. Existing detection approaches predominantly rely on aggregate hardware performance counters, which discard spatial context, fail to locate the malicious core, and often confuse stealthy attacks with benign cache-intensive workloads. This paper addresses these gaps by proposing RingTrace, a system-level monitoring framework that synergizes core-local and uncore telemetry. We capture and normalize per-core cache misses alongside distributed slice activity across uncore CBoxes. Through Joint Spatio-Temporal Attribution (JSTA), we formulate an interpretable joint-activity matrix that captures spatial concentration and co-activity without requiring model training. In the hierarchical response, the largest entry of this matrix serves as the initial screening score, while its row sums identify a candidate core. Our approach reliably identifies victim-independent flush activity prior to secret leakage, effectively suppresses false alarms under severe concurrent memory pressure, and achieves rapid process confirmation with negligible application runtime overhead on commodity processors. This work introduces an interpretable and tamper-resilient hardware-assisted defense model, bridging local CPU execution with physical uncore traffic to provide robust protection against cache side channels.

MSX is a recent family of lightweight block ciphers for microcontrollers, and its round function draws nonlinearity from modular addition and modular multiplication on $32$-bit words. The multiplication is the distinctive part of the design because it turns the round function into a strongly universal hash function, and from this, the designers prove ideal strong differential and linear properties. The same operation also kept MSX out of reach of automated cryptanalysis, since no exact bit-level model of a modular multiplication was available. We give two such models for $z=(x\cdot y)\bmod 2^n$. Both work at the bit level and, to the best of our knowledge, both are new. The first is for monomial prediction under the three-subset division property without an unknown subset (3SDP-woU), and it assigns an exact parity to every monomial without using a truth table. The second is a deterministic truncated model for impossible differential search, and we prove that it is not merely sound but exact for two independent operands, so every incompatibility a miss-in-the-middle search reports through a multiplication is genuine. Both properties are deterministic, so our results are exact, whereas the designers' own analysis provides bounds and estimates, with no explicit trail. Using the two models, we analyze MSX. As far as we know, this is its first independent cryptanalysis. For MSX-128 we obtain a $7$-round deterministic integral distinguisher of data complexity $2^{96}$, where a $96$-bit cube leaves $64$ of the $128$ output bits balanced, and we extend it to key recoveries on $8$ and $9$ of the $18$ rounds that recover the $256$-bit master key in about $2^{228}$ operations, improving over the MSX designers' generic yoyo key recovery attack on seven rounds. Searching all $16,384$ single-bit pairs at each round count, we also find $1,984$ impossible differentials at seven rounds and none at eight. Both models are implemented in the CLAASP library, so they can be used on any included primitive that uses modular multiplication.

The migration to post-quantum cryptography is becoming unavoidable for security protocols. Yet as the historical "goto fail" incident illustrates, deploying new primitives is not sufficient: subtle implementation bugs, especially in verification logic, can yield systems that remain fully interoperable while compromising security silently. Existing confirmation code techniques make certain errors observable, but they do not cover post-quantum signatures and provide limited protection in multi-stage handshakes. Therefore, we present a migration-oriented solution that spans both the algorithm and protocol layers. At the algorithm layer, we develop two generic confirmation-code construction frameworks for Fiat–Shamir signatures and GPV-style Hash-and-Sign signatures, instantiated with ML-DSA and Falcon. For KEMs, we further propose a protocol-friendly, KEM-level confirmation-code method, instantiated with ML-KEM, HQC, and DAWN (NTRU-based KEM). We then prove confirmation-code unpredictability for each instantiation. At the protocol layer, we design PQCD-TLS, a post-quantum TLS handshake that binds confirmation codes into chained key derivation, ensuring that any verification fault induces key mismatch and causes handshake failure. We then extend a multi-stage authenticated key-exchange model with error-injection capabilities to formalize matching correctness with implementation errors, and prove that PQCD-TLS exposes such internal errors without compromising protocol security. Our implementation evaluates 48 configurations combining confirmation code-enhanced PQC algorithms and authentication modes. Results show that handshake latency overhead remains below 1% across all tests, while turning silent verification bugs into observable handshake failures.

SLH-DSA is a hash-based digital signature algorithm, standardised by NIST as a post-quantum signature scheme. While prior work has analysed the vulnerability of its pseudorandom function (PRF) to differential side-channel analysis (SCA), no prior work has thoroughly examined this vulnerability under SHAKE as the PRF, nor recovered a full secret seed in practice. In this work, we address this gap by first analysing the differential SCA vulnerability of SLH-DSA-SHAKE, examining the inputs to the PRF and the possible selection functions for an attack. Then, based on this analysis, we propose a methodology to efficiently apply correlation power analysis (CPA) on every parameter set of SLH-DSA-SHAKE with three main steps: a strategy of averaging subtraces of the same signature to increase the signal-to-noise ratio; a partial-then-total CPA approach to reduce the complexity; and an efficient algorithm for the remaining exhaustive search to recover a full secret seed, which enables universal forgery. We then provide experimental results in simulation and on a 32-bit microcontroller. Our attack requires on average from $280$ to $559$ signatures, and in our experiments the exhaustive search completes within $45$ minutes on $72$ cores.

Many lattice-based cryptographic schemes still require sampling integers following a Gaussian-like distribution. Depending on the application, this sampling should be generic to tackle variable (and possibly large) standard deviations and centers, with a low memory footprint, easily implementable in constant-time, and with the highest throughput. Combining all these features is very challenging, as shown by the numerous works on optimizing discrete Gaussian samplers. In contrast, the rounded Gaussian (and associated samplers), formalized by Hülsing, Lange and Smeets (PKC'18), seems to satisfy these criteria, but its formal definition makes security analyses of the schemes using it more complex, thus explaining why they are rarely used in practice. In this paper, we show that a small correction on the parameter $\sigma$ of the rounded Gaussian yields a distribution that is close to a discrete Gaussian of parameter $s$. More formally, defining $\sigma = s - 1/(24s)$ yields a Rényi divergence between the two distributions evolving as $1 + O(1/s^8)$. As a result, for mild to large parameters $s$, one can use the corrected rounded Gaussian sampler, while still analyzing security with an ideal discrete Gaussian at a very mild loss. It then readily gives a discrete Gaussian sampler that benefits from all the features of rounded Gaussian samplers.

A block cipher is trusted once it resists every published attack and its S-boxes pass the standard tests. A design-level backdoor turns this trust against its users. Its designer hides a structure that only they can exploit, and that the usual tests miss. Four such backdoors have been published, by Rijmen and Preneel, Paterson, Bannier and Filiol, and Peyrin and Wang. Each paper shows what the hidden structure gives its designer. Everyone else needs answers to two other questions. Does the structure also weaken the cipher against ordinary cryptanalysis? Can an evaluator who holds only the specification find it? Neither has been answered for all four designs, so an S-box that passes the usual tests is trusted by default. In this paper we answer both questions. We place the four designs in one taxonomy and in Beyne's correlation-matrix framework. We give an algorithm that recovers a partition trapdoor from the S-box tables, and prove that it never reports a false one and, below an explicit cap, never misses one. We show that inversion and affine equivalence preserve a trapdoor, while extended affine and CCZ equivalence can erase it. We then attack KG-DES (Paterson's S-boxes in DES), BEA-1 and LowMC-M. The answer to the first question depends on the rest of the cipher. In KG-DES the trapdoor makes ordinary attacks far stronger. The best $16$-round differential characteristic has probability $2^{-21.23}$, against $2^{-61.97}$ for DES, and a two-stage attack recovers the $56$-bit key in minutes. In BEA-1 the trapdoor opens no useful trail. However, for every key both ciphers act as an exact smaller cipher on the cosets, and fall to known-plaintext distinguishers from about $2^{16.5}$ and $2^{20.5}$ texts. An independent MILP model confirms every optimum it can prove, and shows that single characteristics put the KG-DES boomerang at $2^{-36.79}$ when it returns with probability $1$. The answer to the second question depends on where the backdoor sits. Our algorithm finds Paterson's trapdoor and BEA-1's four in the S-boxes that carry them. Rijmen and Preneel's trapdoor needs unbalanced S-boxes, which linear algebra exposes. LowMC-M's MALICIOUS backdoor sits in the linear layers instead. With an ideal XOF a backdoored instance is distributed as an honest one, so no test of the primitive finds it. Its holder recovered the key from $35$ to $409$ queries in seven full-size measurements. A deterministic trapdoor in the S-boxes therefore leaves a trace that a sound algorithm finds. A trapdoor in unexplained linear layers leaves none, and only constants derived verifiably from a public seed rule it out. We recommend both as routine checks. Probabilistic trapdoors and trapdoors in only some S-boxes remain open.

We propose a new approximate homomorphic encryption scheme to process small batches of complex numbers. Leveled operations are based on a new shaped rounding, whose error is a multiple of a fixed public ring element $g$, small on the data slots and larger on the others. The unused slots form a guard band that is computed on but never decoded, and the polynomial scaling factor $g^{-1}\Delta$ generalizes the CKKS scaling factor, with $g=1$ recovering CKKS. Guard-domain bounds determine the scaling factor needed for stability, while a norm bound limits the precision gain for a given guard amplification. A replicated layout uses a unit from a small cyclotomic subring to preserve shaping under admissible rotations and traces. We give a native bootstrapping algorithm whose forward transform reads only data slots, and conversions to and from CKKS with shared keys. Security reduces to Ring-LWE with the same parameters as CKKS. In poulpy, at ring degree $2^{15}$ and parameters targeting 128-bit security, bootstrapping a ciphertext holding 16 or 64 values restores 21 levels and retains at least 22.6 bits of minimum precision after 21 sequential products by fresh operands, while sparse CKKS supports only four levels at that degree and comparable precision. For these batch sizes, bootstrapping to restore 16 levels is about 5 times faster on one thread than sparse CKKS, which requires ring degree $2^{16}$.

Lookup arguments with sublinear prover time typically rely on bilinear pairings. The only exception is the recent work of Campanelli, Carrillo, Cascudo, Fiore, Francati, and Gennaro (ePrint 2025/238); however, they rely on general-purpose SNARKs to certify expensive preprocessing, which requires non-black-box usage of cryptographic primitives. Thus practical realizations of sublinear lookups with post-quantum security remain challenging. We develop the first plausibly post-quantum sublinear lookup arguments that avoid general-purpose SNARKs via polynomial preprocessing and a novel adaptation of proximity testing for Reed-Muller codes into the Interactive Oracle Proof (IOP) framework. Our starting point is a knowledge-sound polynomial commitment scheme (PCS) with prover-side preprocessing based on the Kedlaya-Umans framework. Rather than proving the expensive preprocessing computation inside a general-purpose SNARK, we directly certify its output using Reed-Muller proximity testing and an associated evaluation protocol. For polynomials of size $N$, our approach yields multivariate and univariate PCS with $N^{1+\epsilon}\mathsf{polylog}(N)$ preprocessing and only $\mathsf{polylog}(N)$ online prover time, while retaining $\mathsf{polylog}(N)$ proof size and verification. We leverage this PCS to obtain a lookup argument for \textit{static} tables of size $N$ and $k\ll N$ lookups with $k\cdot\mathsf{polylog}(N)$ online prover time and $\mathsf{polylog}(N)$ verification and proof size. We further extend the approach to \textit{updatable} tables, obtaining $O(k(N^\epsilon+\mathsf{polylog}(N)))$ amortized prover time for a $k$-sized batch of reads and writes, where $\epsilon \in (0,1)$. We retain $\mathsf{polylog}(N)$ proof size and verification. The IOPs underlying our lookup arguments satisfy round-by-round (knowledge) soundness, which can be compiled into plausibly post-quantum arguments in the (quantum) random oracle model with transparent setup.

Algebraic error-correcting codes such as BCH let lattice-based key encapsulation mechanisms (KEMs) reduce bandwidth and the decryption-failure rate. The decoder’s input is determined jointly by the long-term secret and a ciphertext that an adversary may choose. Variable work or table accesses that reveal error positions can enable key recovery even when the KEM uses implicit rejection. Walters and Sinha Roy (WSR) gave a constant-work BCH decoder whose fixed-address realization scans the entire field per protected lookup. We introduce algebraic index elimination, a table-free realization of WSR’s paired Berlekamp–Massey schedule in which received-word-dependent selections become fixed circuits over public addresses. We prove bounded-distance correctness through radius t and source-level trace regularity for the parameterized decoder. We instantiate the construction with length-511 subcodes of dimension k , using ( k,t ) = (384 , 14) and (320 , 22). Their implementations eliminate, respectively, 5.2 and 7.2 KiB of received-word-selected field and encoder tables required by matched fixed-address WSR baselines. On WSR’s published parameter sets, an Intel i7-13700 runs the deterministic cores 35.7–82.4 × faster than the fixed-address WSR baselines. In the identity-based lattice KEMs ANSA-IBKEM1 and ANSA-IBKEM2, decapsulation is 25.5 × and 10.9 × faster than with fixed-address WSR baselines for the same 384-dimensional subcode. Index elimination does not equalize operands. Ordinary C masks compiled to received-word-dependent branches under Apple Clang 21; a compiler-opaque primitive prevented this transformation in the audited builds. At the measured radii, scalar binaries of both codes pass the x86-64, Cortex-A76 and Cortex-M4 mean-timing screens, and the Apple M5 screens with Data Independent Timing (DIT) enabled.

Trusted Platform Module (TPM) 2.0-based full-disk encryption (FDE) has gained renewed importance with the rise of bring-your-own-device environments. Aside from Windows Bitlocker, which uses the TPM since the days of Windows Vista, FDE has also been recently adopted by several Linux distributions. We revisit tamper attacks against TPM 2.0-based FDE systems and analyze the security of current Windows and Linux implementations. We examine TPM 2.0 sealing mechanisms and demonstrate passive and active attacks against systems using discrete TPMs (dTPMs) connected via SPI, using a mini PC and a notebook platform as case studies. While dTPMs are highly tamper-resistant, they remain vulnerable to attacks on the communication bus. We further show that active attacks are not limited to dTPM bus interception but can also affect firmware TPMs (fTPMs). Specifically, we present a prototype attack in a virtualized QEMU environment targeting UEFI firmware rather than bus communication, impacting both Windows and modern Linux systems. These attacks enable us to break not only BitLocker-based full-disk encryption on Windows, but also all current Linux implementations, including those that utilize parameter encryption to secure the bus communication. Our findings expose weaknesses in current TPM 2.0 FDE implementations and motivate stronger specification-level protections.

MAYO, a multivariate quadratic signature scheme with small public keys and signatures, is a third-round candidate in the additional signature standardization process of the National Institute of Standards and Technology. Cloud and application servers receiving many independent signing requests need to batch them on Graphics Processing Units (GPUs). MAYO's nibble-sliced representation suits CPU shuffle instructions or multiplication tables, but on GPUs it costs a memory access or several instructions per $\mathbb{F}_{16}$ multiplication. The existing GPU implementation cuMAYO (CHES 2026) uses the second-round nibble-sliced representation and looks up a shared-memory table per $\mathbb{F}_{16}$ multiplication. Our GPU implementation keeps all keys and intermediate values in the bitsliced representation yet matches the official Known Answer Test vectors. Its bitsliced multiply-accumulate circuit computes matrix products $32$ coefficients at a time with only word-wide AND and XOR. One thread block handles one instance; KeyGen, Sign, and Verify each run as a single kernel from the expansion of the compact key to the output; and representation conversion is confined to reading and writing specification-defined byte strings. For same-key batches, an additional tensor path decomposes $\mathbb{F}_{16}$ matrix products into binary ones and computes the large Sign and Verify matrix products on Tensor Cores. To our knowledge, the tensor path is the first use of Tensor Cores for MAYO, and ours is the first GPU implementation of the third-round specification. On an RTX 4090, the bitsliced implementation achieves $2.75\times$ to $6.73\times$ higher throughput and $6.99\times$ to $34.35\times$ lower single-shot latency than cuMAYO for all three operations of the four parameter sets. In same-key batches, the tensor path, including key preparation, reaches $13.75\times$ to $30.62\times$ the throughput of cuMAYO on distinct-key batches.

Estonia’s IVXV system is one of the world’s longest-running and largest-scale deployments of internet voting, yet it lacks a precise public specification of the protocol as implemented or security claims, which has left it difficult to audit independently. We address this as follows: First, we reverse engineer a detailed specification of IVXV as implemented—covering the setup, voting, tallying, and audit phases—comprising protocol-flow diagrams, pseudocode algorithms, and the core data structures, reconstructed from the public source code, official documentation, and configuration examples. Second, we complement the specification with an executable TLA+ model of the setup, voting, and tally phases, which we check with TLC for basic executability and correctness and which serves as an extensible basis for modelling concrete attack scenarios. Third, using the reconstructed specification, we carry out a systematic security analysis under a broad range of threat models spanning individual verifiability, universal verifiability, privacy, coercion resistance, and eligibility verifiability, and we reassess previously known attacks against the current protocol. Fourth, we compare IVXV against two of the most extensively studied deployed systems, Belenios and Swiss Post, across these properties in order to situate its guarantees. Fifth, we discover numerous previously unknown, vulnerabilities—spanning ballot privacy, individual verifiability, and universal verifiability, many of them arising from inconsistent validation logic across components, encoding discrepancies, and unchecked cryptographic parameters—and validate selected findings with proof-of-concept tests that exercise the real implementation. Finally, we propose concrete mitigations for the attacks we identify.

A broadcast and trace scheme combines broadcast encryption with accountability. Specifically, broadcast encryption is augmented with an algorithm for tracing traitors within a specified set, even if the given pirate decoder is created by an arbitrary collusion of users. As in broadcast encryption, the size of the ciphertext should be sublinear in the total number of users $N$. In this work, we generically construct collusion-resistant broadcast and trace that supports public tracing from attribute-based encryption with succinct ciphertexts and lockable obfuscation, both of which are known from the decomposed LWE assumption. Our scheme has ciphertext size $\sqrt{N}\cdot\mathsf{poly}(\lambda, \log N)$, while the master public key and secret keys have size $\mathsf{poly}(\lambda, \log N)$. Previously, collusion-resistant broadcast and trace with public tracing required pairing-based assumptions, positional witness encryption, or indistinguishability obfuscation. In particular, we provide the first construction that relies on a simple and instance-independent lattice assumption. At the heart of our construction is a novel way to use nested lockable obfuscations, taking inspiration from the recent work of Nassar, Waters, and Wu that constructs positional witness encryption from indistinguishability obfuscation for null programs.

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.

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.

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

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

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.

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.

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.

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.

Predicate encryption (PE) encrypts a message under an attribute that the ciphertext hides, allowing a secret key for a predicate to recover the message only when the attribute satisfies the predicate. Existing public-key implementations support useful specialized predicates, but enforcing heterogeneous conditions with one key requires an attribute representation fixed before encryption, which grows with the supported types of conditions and cannot express types it does not anticipate, such as regular expressions. Lattice-based PE for general circuits is far more expressive, but existing constructions rely on fully homomorphic encryption (FHE), typically evaluated as a Boolean circuit over key-homomorphic encodings, which expands the computation and amplifies noise growth and leads to impractically large parameters. Existing PE thus offers either practicality for restricted predicates or expressiveness at an impractical cost. We present a lattice-based PE scheme for branching programs that avoids FHE entirely and combines heterogeneous conditions in a single predicate over a common attribute representation. It rests on two techniques: asymmetric multiplication, which multiplies a hidden program state by an encrypted attribute symbol through decryption inside an encoding, and lookup tables over exponents, which evaluate arbitrary state transitions on a single encoding by ring automorphisms. Under circular Ring-LWE, the scheme is selectively weakly attribute-hiding against polynomially many colluding unauthorized keys. We give, to our knowledge, the first implementation of PE for a predicate class as expressive as branching programs. On a single NVIDIA A100 GPU, for a predicate that combines a range check and a regular-expression check on a $10$-bit attribute, with parameters targeting $128$-bit security against known Ring-LWE attacks, encryption takes $4.06$ hours, key generation $4.70$ hours, and decryption $4.23$ hours, with $342.25$ GB ciphertexts. These costs remain large, but compared with a single FHE multiplication evaluated as a Boolean circuit over encodings, the basic step of PE that evaluates FHE over encodings, whose ciphertexts alone occupy tens of exabytes per attribute bit, our ciphertexts are at least $2\times10^9$ times smaller per attribute bit, and our decryption needs at least $2\times10^{16}$ times fewer $64$-bit integer multiplications.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.