Private search engines allow a user to retrieve documents from a public database that are similar to a text query. Our cryptographic protocol Mímir employs state-of-the-art homomorphic ciphertext switching techniques to realize the first stateless semantic private search engine for highly dynamic databases. The security of Mímir relies on (Ring) Learning with Errors. Mímir requires no offline communication, and it trades higher but highly parallelizable server computation for low per-query communication. When the database may change between queries, Mímir matches Tiptoe's search quality with 84$\times$ less per-query communication (0.24 MiB). At Tiptoe's per-query communication, it reaches 64$\%$ instead of 36$\%$ of non-private search quality and is 4.2$\times$ faster (0.87s on a single multithreaded machine). Against PACMANN, Mímir improves search quality from 76$\%$ to 81$\%$ of non-private with 72$\%$ of its per-query communication and a 9.54 MiB instead of 2.68 GiB one-time cost, but is 2.1$\times$ slower. Mímir can achieve 59$\%$ of the non-private search quality with 8.13 MiB of per-query communication and 0.77s of total latency. This matches PACMANN's latency at a 7.6$\times$ smaller per-query communication, and outperforms Tiptoe in all three metrics.

Universal thresholdizers offer one-round threshold signatures, but require evaluating an entire signer under fully homomorphic encryption (FHE). We present Balsamic, a complete homomorphic Unbalanced Oil and Vinegar (UOV) signer and its application to one-round threshold UOV signature. UOV's short salted target hash shifts the encrypted workload to finite-field linear solving, which we integrate with coin derivation and hashing in a packed discrete-CKKS circuit. Our paired-pivot solver selects both pivots before first-pivot normalization, then applies their coupled update with one inversion stage per pair and cubic field work. Pivot-success certificates enable encrypted retry selection without residual evaluation. In 2-out-of-3 semihonest threshold UOV signing, each partial signing (online) takes $10.7$ seconds on NVIDIA RTX 6000 Ada and $7.77$ seconds on NVIDIA GB300, with $5.25$ MB per response. These measurements demonstrate that complete homomorphic signing can provide the computational core of one-round threshold signatures without intermediate openings or per-signature interactive preprocessing.

Understanding the hardness of the complexity class PPAD is an important question in complexity theory given that it contains problems such as computing a Nash equilibrium. Evidence of hardness, however, has come primarily from cryptography, through a long line of work. Most recently, Chen, Freitag, Jin and Wichs (STOC 2025) based the hardness of PPAD on the polynomial hardness of the Learning with Errors (LWE) problem, together with a fine-grained average-case hardness assumption. In this work, we base the hardness of PPAD on a different lattice problem, the Short Integer Solution (SIS) problem, which, unlike the assumptions underlying prior work, is not known to imply public-key encryption. Specifically, we show that PPAD is hard on average assuming either: (i) polynomially hard SIS with a quasi-polynomial norm bound and a fine-grained average-case hardness assumption; or (ii) subexponentially hard SIS alone. Our main technical contribution is a succinct, incrementally updatable proof system for a class of exponentially large circuits with short descriptions. Building on the work of Wee (CRYPTO 2025) for succinct proof systems for circuits from SIS, we show how to make such proof systems satisfy these properties while preserving the unambiguity guarantee of the underlying scheme: it is hard to find two distinct accepted states for the same computation and time. Together, these are crucial for our PPAD hardness reductions.

Classical integral cryptanalysis relies on zero-sum properties that, for every key, hold with probability one. Existing arguments against such deterministic integrals, based on the division property and its algebraic variants, only exclude this extreme case: once the zero-sum probability falls below one, they say nothing about its actual value, nor about a probabilistic bias that could still be exploited. We develop a tool combining MILP-based trail search with a recursive evaluation of assignments to the constant inputs. It estimates the probability that no valid trail remains and uses an additional heuristic to predict the zero-sum probability. Applying this tool to PRESENT and GIFT, we obtain probabilistic integral distinguishers for 6 to 9 rounds, including 6- and 7-round PRESENT distinguishers using $2^4$ and $2^{12}$ plaintexts per structure, respectively. For the ASCON permutation, we obtain 4- and 5-round distinguishers using as few as $2$ and $2^{12}$ inputs per structure. We further explain algebraically the large bias of the 6-round PRESENT distinguisher, showing how the S-box and bit permutation restrict the way active variables combine. Finally, we show how these distinguishers can be used for key recovery, reducing both the data and time complexities compared to their deterministic variants for PRESENT and GIFT-64.

At CT-RSA 2026, Ng and Lau introduced $(t,n)$-integer coordinate families for threshold RSA signatures with $e=3$, and found some families by heuristic search for $2\le t \le n \le 9$. They asked whether such families always exist and, if so, can they be constructed efficiently. We answer both of these questions positively. We prove that a $(t,n)$-integer coordinate family is also a $(t+1,n)$-integer coordinate family. We construct such families for $t=2$, and $2\le n < 19$, using a polynomial time algorithm in $n$ and its output bit length. Answering another question raised in the Ng-Lau work, we prove super-polynomial lower bounds on coordinates of pairwise families. We also find the minimum families for $n \le 9$. Ng and Lau proposed a threshold signature scheme based on integer coordinate families. We show that the Ng-Lau scheme admits trivial forgeries, and has a flawed proof. We give a repaired scheme $\mathrm{PiIC}$ which does not suffer from these issues. Finally, we propose an integer secret-sharing scheme $\mathrm{PiZ}$ that works for every prime $e$ and every $(t,n)$, without relying on any special coordinate family. We prove that both the schemes $\mathrm{PiIC}$ and $\mathrm{PiZ}$ are TS-UF-CMA secure under the standard RSA assumption.

Generalized CKKS (GCKKS) trades slot count for reduced modulus consumption in high-precision approximate arithmetic. However, designing a GCKKS bootstrapping algorithm with reduced modulus consumption throughout its computation remains a challenging problem. We construct high-precision bootstrapping for GCKKS using low-precision overflow extraction followed by iterative precision enhancement. Our main ingredient is a ciphertext-conversion framework for changing the decryption factor and slot count without requiring the factors to be units. A slot-aware analysis bounds unused-slot magnitudes proportionally to the corresponding evaluations of the decryption factor, which is essential to ensure the unused-slot values remain well-bounded after conversion. We combine precision doubling with ciphertext splitting and develop a joint evaluation procedure that produces two error-cleaned outputs at the cost of only one evaluation of the cleaning polynomial. We also give a useful-slot-preserving conversion from CKKS to GCKKS that simultaneously resets unused slots through component-wise re-encoding. Underlying these constructions, we also improve the construction of the decryption factors by searching directly in the canonical embedding and obtain depth-free conjugation with non-unit factors. For target encoding precision $p$ and $2N/k$ useful slots in a ring of dimension $N$, the precision-dependent stages of the bootstrapping use $O(k)$ homomorphic operations and consume $O((p/k)\log k)$ modulus bits.

In the average key setting, a linear attack of Bak et al. on the TFHE-friendly stream cipher FRAST let wrong guesses pass, which they left as an open problem. The S-boxes of FRAST are public and random for every keystream block. For the mask on the least significant bit, we show that key differences fall into five indistinguishable classes per round. The filter of Bak et al. gives some wrong classes of the right parity a nonzero expected score. We compute the trail correlation exactly through the real cipher and bound the success of our statistic for every fixed master key. We bound its false alarms for a fixed master key with the last round kept and no filter, and for every attack against an ideal keystream. With known XOF inputs, our algorithm Contract recovered the classes of a branch pair of 15 rounds and the master key of ten rounds. A cost model gives class recovery for every sampled key at 26 rounds with known inputs and for a third at 38 rounds with chosen inputs. In the accounting of Bak et al., it reaches full FRAST on weak master keys of density $2^{-11.8}$ to $2^{-5.4}$ within the claimed security. A distinguisher of full FRAST has a proved advantage on these keys, and its time over the advantage stays below the claimed security as well. Independent branch S-boxes remove the cheap classes at a cost in TFHE.

Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data without decryption, providing strong privacy guarantees for secure cloud computing, encrypted analytics, and privacy-preserving machine learning. However, practical deployment of FHE remains limited by the high computational cost of polynomial arithmetic over large modular rings. In particular, Number Theoretic Transform (NTT)–based polynomial multiplication dominates the execution time of modern lattice-based FHE schemes. In this work, we present TP-NTT, a scalable, throughput-optimized NTT architecture supporting a wide range of ring dimensions used in FHE, from $2^{10}$ to $2^{16}$. Our design applies optimizations at multiple levels, from modular arithmetic to the NTT algorithm itself, including multi-dimensional decomposition without requiring additional multiplication blocks. The decomposition dimensionality is configurable at design time, supporting 2-D, 3-D, and 4-D decompositions, each advantageous in specific scenarios. Furthermore, TP-NTT provides design-time-configurable throughput. Combined with its scalable architecture, this enables significant advantages for batch NTT operations compared to other works in the literature. At $n=2^{16}$, it outperforms the best-performing prior design by $1.33\times$ in average latency while achieving $1.24\times$ better area–time-product (ATP). To demonstrate its efficiency, we present a case study on FHE relinearization, focusing on the BFV scheme. We propose a relinearization accelerator that leverages the fast batch NTT capability of TP-NTT, achieving $67.34\times$ speedup over state-of-the-art software implementations and highlighting TP-NTT’s effectiveness in real-world FHE applications.

In this paper, we present RISQrypt, the first unified architecture in the literature that implements ML-KEM (f.k.a. CRYSTALS-Kyber) and ML-DSA (f.k.a. CRYSTALS-Dilithium), two standardized lattice-based post-quantum cryptography (PQC) algorithms, with masking. RISQrypt is a hardware–software co-design framework that integrates dedicated cryptographic accelerators to speed up polynomial arithmetic, hashing, and mask-conversion operations, the latter being one of the primary bottlenecks in masked implementations of lattice-based PQC. Our design achieves low latency while providing both theoretical and practical side-channel security through formal proofs in the $t$-probing model and practical experiments. Specifically, the masked decapsulation of ML-KEM-768 requires $\mathbf{109K}$ clock cycles, while masked signing of ML-DSA-65 requires $\mathbf{1230K}$ clock cycles on average. These results demonstrate $\mathbf{11.3\times}$ time-performance improvement over existing masked implementations. Our time performance results for unprotected functions also outperform the existing work; achieving speed-ups of $\mathbf{10.64\times}$ and $\mathbf{8.94\times}$ for ML-KEM's encapsulation and decapsulation algorithms, respectively, and $\mathbf{1.14\times}$ and $\mathbf{2.23\times}$ for ML-DSA’s signature generation and verification algorithms, respectively, when compared to existing designs with similar resource usage. In addition, prior designs are more limited in scope, generally supporting only a single scheme and lacking either the side-channel protection or the unified, crypto-agile framework that enables support for both ML-KEM and ML-DSA as in our architecture. Leveraging the HW/SW co-design approach, the proposed architecture can be reprogrammed through firmware to support other (and future) PQC standards and algorithms sharing similar computational building blocks. As proof of concept, we demonstrate this capability by implementing FN-DSA (f.k.a. Falcon) and SLH-DSA (f.k.a. SPHINCS+).

Confidential sources are vital for investigative journalism and thus for holding those in power to account. However, sources often face great risks to their privacy and safety. SecureDrop is a system that enables sources to anonymously contact journalists, including at major news organisations around the world. Despite its widespread use, the current design requires physical servers hosted on premises. While cloud-based deployment would alleviate this burdensome requirement and improve SecureDrop's usability and accessibility, it would also introduce new threats to security that are not addressed by the current design. In particular, a lack of end-to-end encryption presents serious risks in the event that a cloud service provider is coerced into revealing information. In this work, we present and formally analyse a new protocol for SecureDrop which addresses the challenges of off-premises deployment. Our protocol composes an encryption scheme with hybrid post-quantum guarantees and an identity-hiding message-fetching mechanism to provide strong anonymity guarantees. In contrast to existing systems, we minimise incriminating evidence against whistleblowers by providing message-level deniability and by having sources remain stateless. Our formal security analysis combines the Tamarin prover for symbolic analysis and game-based proofs for computational analysis. Finally, our benchmarks demonstrate that the protocol achieves practical levels of performance in a browser context. The Freedom of the Press Foundation plans to deploy the new protocol, with integration efforts beginning in 2026.

Almost pairwise independence asks how closely a block cipher reproduces the joint output distribution of a random permutation on two distinct plaintexts. Existing analyses of AES with independent round keys combine bounds on the distribution after the first few rounds with contraction over later rounds. Diffusion makes local output differences dependent, and estimating local responses or successive transitions separately can lose useful information. We preserve these dependencies in two ways. First, Gram-moment estimates sum the squared overlaps between local responses whose inputs are linked by diffusion. Second, we estimate two consecutive transitions together. The compatible intermediate differences form affine fibers; summing over these fibers inside the composed operator retains the constraints shared by the two diffusion layers. We prove $\varepsilon_{8+2k}<2^{-92.19-41k}$ for every integer $k\ge0$, where $\varepsilon_r$ is the largest total variation distance, over distinct plaintext pairs, between the ciphertext-pair law and the corresponding random-permutation law. The round keys are independent and uniform, sampled once and reused across evaluations. Consequently, 10, 14, and 16 rounds suffice for statistical accuracy $2^{-128}$, $2^{-192}$, and $2^{-256}$. The same bound controls the complete view of an algorithm making at most two adaptive classical forward queries with an independent finite private seed. The resulting family gives 41 additional bits of pairwise accuracy for every two additional rounds, starting at eight rounds.

Building an Asynchronous Byzantine Fault Tolerant (BFT) protocol requires establishing payload availability with total order despite Byzantine faults and arbitrarily delayed messages. Although many BFT systems separate payload dissemination from agreement, they often couple their composition to protocol-specific selection or scheduling mechanisms. We present the Distributed Producer-Consumer Model (DPCM), an event-driven abstraction that separates payload-specific certified availability from payload-oblivious binary finalization. We prove that DPCM compiles any producer–consumer pair satisfying interfaces specified herein into an asynchronous BFT object log. DPCM batch-finalizes certified heights, deterministically refining failed batches until each height yields a normal or evidence-backed dummy entry. We instantiate DPCM as Octopus, which combines parallel consistent broadcast producers with batched asynchronous binary agreement (ABA). To achieve performance advantages, Octopus lets producers certify blocks without waiting for consumer decisions and keeps payload recovery off the agreement path. One ABA optimistically finalizes multiple consecutive producer columns, while failures trigger parallel row-wise refinement with logarithmic bisection depth. Across an eight-region WAN with $n\in\{8,16,32\}$ and 2200-transaction blocks, Octopus remains within 6.5% of Dumbo-NG's (ACM CCS'22) fault-free throughput. With the maximum tested number of silent faulty parties, it outperforms Dumbo-NG by 25.9% and 18.7% at $n=8$ and $n=16$, respectively, and remains within 1% at $n=32$. At $n=16$ and $n=32$, Dumbo-NG's latency is 1.9--2.5$\times$ that of Octopus. Across all evaluated settings, Octopus achieves 2.9--16.8$\times$ the throughput of Alea-BFT (USENIX NSDI'24), whose latency is 2.4--15.2$\times$ that of Octopus.

As AI increasingly automates cryptanalytic programming, transparent and reproducible frameworks are essential for making generated results human-verifiable. We present CLAASP-MP, a monomial-prediction tool integrated into CLAASP and based on the three-subset division property without unknown subset (3SDP-woU). CLAASP-MP generates a Mixed Integer Linear Programming (MILP) model directly from the CLAASP component graph, supporting S-boxes, linear layers, Boolean operations, modular addition and multiplication, and linear and nonlinear feedback shift registers. For selected output bits, CLAASP-MP computes the algebraic normal form (ANF) for small numbers of rounds, derives superpolies for a chosen cube, and bounds the algebraic degree with respect to plaintext, key, or IV variables. It detects absent monomials through vanishing ANF coefficients, zero superpolies, or degree bounds, thereby identifying balanced outputs and integral distinguishers. We evaluate CLAASP-MP on block ciphers, permutations, and stream-cipher update functions. For block ciphers, we reproduce known distinguishers, find new cubes, and report the first integral distinguishers for SAECHAM. For Splight, we reach rounds 10 and 11, despite a previous two-subset division-property search reporting no 10-round distinguisher. On MSX-128, a $96$-dimensional cube leaves $64$ of $128$ output bits balanced after 7 rounds. For permutations, we extend the best-known division-property distinguishers for ChaCha and Salsa from 6 and 5 rounds, respectively, to 6.75 rounds; give the first such distinguishers for Forr\'o; and reduce the data complexity for Chaskey-Pi from $2^{64}$ to $2^{23}$ at round 3 and from $2^{127}$ to $2^{122}$ at round 4. For stream ciphers, we find new 36-dimensional cubes for Bivium, extend the tight degree bounds for Trivium to later initialization clocks, and reproduce published superpolies. These results establish CLAASP-MP as a unified, practical, and human-verifiable framework for monomial prediction across symmetric primitives.

Hiding countermeasures, alongside masking, play an important role in modern hardware security for protecting against side-channel attacks. Additive noise generators are one such hiding countermeasure. They increase the noise, thereby lowering the signal-to-noise ratio and, simultaneously, amplifying the effectiveness of masking countermeasures. Among the different design options for additive noise generators, ring-oscillator-based designs feature regularly in scientific publications. These existing works not only differ in their designs, but also in their evaluation methods; therefore, they do not permit fair comparisons or enable systematic evaluations. Thus, it is currently not possible to design ring-oscillators for noise generation in an informed and tailored way. In this paper, we address this lack of systematic comparisons of existing designs, and discuss the possibility of filtering out the generated noise and further limitations of ring-oscillator-based noise generators. We find that many existing designs do not consider the need to amplify the output signal or the risk of filtering. As a consequence, the existing designs do not sufficiently lower the signal-to-noise ratio in our experiments. However, using these results, we provide a guideline for tailoring and configuring ring-oscillators so that they efficiently add noise in the desired frequency spectrum. This includes deciding on the inverter chain length, the amplification of the output, and the randomization of the output frequency. Finally, we apply this methodology to build a tailored ring-oscillator-based noise generator for an exemplary AES implementation and find that it significantly outperforms existing ring-oscillator-based designs.

ANNULAR is a shielded pool built on isogeny-based primitives. Notes are committed in a Merkle tree and spent by nullifier with hidden amounts, following the structure of Zcash's Sapling, but every primitive is post-quantum: spends are authorised by the prime-degree PRISM signature of Basso et al., note ciphertexts are keyed by the MIKE non-interactive key exchange, and each transaction carries a STARK proved natively over the isogeny field. The transaction proofs of a block are then folded into a single recursive proof. A ledger need record and verify only this one proof, 426 KB in 15 ms, whatever the batch holds, and check each transaction's two signatures alongside it. A transaction's body is the size of Sapling's at the same memo length (2,685 bytes against 2,756 with a 512-byte memo); its share of the batch proof adds under 500 bytes. A move to post-quantum primitives is generally expected to raise a pool's operating cost. We argue that the post-quantum change and the scaling change are complementary: with a STARK as the proof system, proofs fold, and with isogeny keys, the per-transaction data remains small. The cost moves to the sender, whose proof takes 1.4 s on sixteen cores, and to one aggregator per batch, which we measure: 1,248 transactions in 99 s on one GPU. Each proof in the tree carries 100 bits of round-by-round soundness and the batch about 90 under a union bound; under Fiat–Shamir that is the work an adversary needs. The constraints of the leaf circuit are proven in Lean 4 to encode the spend statement, while the soundness of the STARK itself rests on a paper argument. The scheme's claims rest on the signature's existential unforgeability; its strong unforgeability, argued by the construction's authors and not yet proved, is not relied on.

In this work, we look at collision-based attacks both for elliptic curve and isogeny problems. Our main focus is on attacks in the multi-user setting, i.e., where one tries to recover all secret keys of a large set of $L$ public keys simultaneously, in a faster way than the total time required to attack each key individually. We consider three different problems: (1) the discrete logarithm problem on elliptic curves, (2) the isogeny pathfinding problem on supersingular $\mathbb{F}_{p^2}$-curves, (3) the isogeny pathfinding problem on supersingular $\mathbb{F}_p$-curves. We first survey the existing van Oorschot and Wiener style attacks on these three problems. Then we propose versions of the pseudorandom walks that are better suited for isogeny pathfinding problems without additional restrictions. We then apply these new walks to the multi-user setting and analyse which properties we can achieve compared to the discrete logarithm case where we show that we can extract all $L$ public keys with $L$ useful collisions and without an infiltrator (a user for which we know the secret key). Specifically, for (2) we can extract $L$ public keys with approximately $L + \log(L)$ useful collisions and no infiltrator needed. Our analysis shows however that heuristic and infiltrator-aided strategies are more efficient while enjoying practically similar gains. For (3) we can extract approximately $0.75L$ public keys with $L$ useful collisions, but with an infiltrator.

Threshold cryptographic primitives have not been widely adopted in real-world distributed systems (i.e., beyond the closed committee model) presumably due to state-synchronization overhead and complex certification processes for the shareholders. These are both aspects of their overreliance on infrastructure, an assumption that is usually glossed over in their design. In this work, we propose OSST, a real-time threshold identification protocol that achieves non-interactivity and non-reliance on public shares by means of direct proof interpolation. Given a Shamir $(n, t)$-shared secret $x$, the proposed scheme allows any $t^* \ge t$ (but no less) shareholders to prove over designated communication channels that their key shares interpolate to $x$ without revealing any information beyond that. Provers do not engage in distributed computations, sending their packets to the verifier asynchronously; conversely, verifiers need only know the combined public key $y \equiv g ^ x$, without need to pre-validate and register the individual member identities. The protocol is intended for use in permissionless or unmanaged meshes that lack both overlay networks and trust infrastructure or governance, a use case space that has been tacitly neglected as ''niche'' by the current mainstream. No publicly verifiable setup is required beyond distributing $x$ according to Shamir's secret sharing (or equivalent distributed key generation scheme) and advertising its public counterpart; in particular, the protocol is intended to be secure against impersonation without relying on the auditability of any advertised public shares. We provide evidence that this has good chances to hold true by giving a reasonably restricted security proof in the random oracle model under the one-more discrete-logarithm (OMDL) hardness assumption.

Rotational-XOR (RX) cryptanalysis extends rotational cryptanalysis by combining rotational relations with XOR translations, enabling the analysis of symmetric-key primitives even in the presence of symmetry-breaking constants. Existing analyses of RX characteristics, however, typically rely on independence assumptions when estimating characteristic probabilities, which may lead to inaccurate probability evaluations and even incompatible characteristics. In this paper, we introduce the first application of the geometric approach to RX cryptanalysis. Inspired by the quasidifferential framework of Beyne and Rijmen, we define rotational-quasidifferential trails and derive exact expressions for fixed-key RX characteristic probabilities without relying on round-independence assumptions. We also derive explicit rotational-quasidifferential transition matrices for bitwise AND and modular addition. By incorporating the key schedule into the state space, we further obtain an exact expression for the Expected Rotational-XOR Probability (ERXP), the RX analogue of the Expected Differential Probability (EDP). We apply the framework to the ARX cipher SPECK, the ARX permutation Alzette, and the AND-RX ciphers SIMON and SIMECK. For SPECK, we repair an incompatible 12-round characteristic and show that the longest published RX characteristics for SPECK64/128, SPECK96/144, and SPECK128/256 are incompatible. For Alzette, we show that signed nonzero-mask contributions explain the discrepancy between independent-ADD estimates and experimentally observed full-data-path probabilities. For SIMECK, we experimentally verify a fixed-key probability distribution, explain incompatible characteristics, and correct the weak-key class estimates of rotational-XOR differential rectangle attacks. These results extend the geometric approach to both ARX and AND-RX designs and demonstrate its usefulness for exact characteristic-level analysis.

Blockchain-aided decentralized storage networks (DSNs) use public audits to verify outsourced storage and smart contracts to govern payments and collateral. Published audit evidence, however, remains available to servers and may let them reduce local storage while continuing to pass audits. Retrieval must also remain fair across adaptively selected sessions. We formalize DSN protocols across delegation, preservation, and retrieval, accounting for evolving server state and externally available proofs. To support adaptive replication soundness, we reformulate rational replication for proofs of replication (PoRep) as an extractor-based notion. We then give a generic construction combining PoRep, verifiable delay functions, and simulation-extractable zkSNARKs, with encrypted delivery and conditional authorization for retrieval. Our analysis identifies roles for succinctness and simulation-extractability beyond privacy and efficiency. Under the knowledge of strong compression assumption and the stated primitive and timing assumptions, we establish adaptive replication soundness subject to bounds on extraction resources and the cumulative public transcript. We also establish contract unforgeability and retrieval fairness. Controlled experiments illustrate storage offloading through public audit evidence, while a separate Merkle-PLONK prototype measures proving and verification costs through Cardano's Plutus interface.

Class group actions on supersingular elliptic curves over $\mathbb F_p$ as in CSIDH are typically evaluated as long chains of isogenies of small prime degree. Radical isogeny formulae compute such chains using a single $N$th root per step, without sampling torsion points. Compact formulae of linear size had been conjectured for all odd $N$. We prove a corrected version of these formulae for every $N\ge4$, odd and even, over every field of characteristic coprime to $2N$. In our formulation, every building block is a twisted sum of a discrete Kronecker function over $\mathbb Z/N\mathbb Z$, and the formulae follow from a distribution relation for the Kronecker theta function. For even $N$, the $N$th root is only determined up to sign over $\mathbb F_p$, and the sign decides whether the walk stays on the surface of the $2$-isogeny volcano. We show that the radical times a $2$-torsion coordinate of the next curve is a square, which yields the horizontal choice for all even $N$; previously this was only known for $N\le14$. Algorithmically, one radical step costs about $12.5N$ multiplications and one exponentiation, without inversions. For horizontal $2$-isogeny walks, radical $2^m$-isogenies with $m\in\{5,6,7\}$ are optimal for primes of $512$ to $4096$ bits. Finally, we show how to evaluate radical isogenies on points. As a consequence, a class group action can be computed from two given points, one on the curve and one on its quadratic twist, without ever sampling torsion points.

Registered Functional Encryption (Reg-FE) eliminates the key escrow issue in traditional functional encryption by allowing users to generate their own public/secret keys without the help of a central authority. The public key is then registered to the system along with a function, and all the registered public keys will be aggregated to a compact master public key by a transparent key curator. Messages are encrypted under the master public key, and users can learn functions of encrypted data from the ciphertext using their own secret keys. Prior constructions of Reg-FE either become insecure when more than one malicious users collude or require the heavy machinery of indistinguishability obfuscation. In this work, we construct the first collusion-resistant Reg-FE without obfuscations. The schemes are secure if the number of colluded users is bounded, and the collusion bound can be either a global parameter or specified by the encryption algorithm dynamically. In both settings, we provide generic constructions of Reg-FE from registered attribute-based encryption and instantiate them from either the standard $k$-Lin assumption or the succinct LWE assumption.

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.

The CKKS fully homomorphic encryption scheme enables efficient arithmetic over complex numbers, but each homomorphic multiplication consumes a large modulus to ensure enough precision, limiting both the circuit depth and precision supported by CKKS. This work addresses this problem by proposing Generalized CKKS (GCKKS), a CKKS analogue of the GBFV scheme (EUROCRYPT 2025) that trades the number of slots for reduced modulus consumption. Despite its high-level similarity to GBFV, GCKKS faces new challenges caused by the different encoding and encryption structures of CKKS. We address these challenges with novel techniques not present in GBFV. Our plaintext encoding starts with an improved and SIMD version of Costache, Smart, and Vivek's encoding in 2017. Namely, it rounds complex values to cyclotomic integers instead of Gaussian integers, and reduces the rounding problem to solving CVP instances. This encoding allows storing high-precision complex values in polynomials with small canonical norms. As an important observation, the encoding can be simplified to a sparse CKKS encoding followed by multiplication with a polynomial constructed from a short vector in the encoding lattice. We show that by integrating this encoding format into GCKKS decryption, most GCKKS homomorphic operations and the corresponding noise analyses reduce to their CKKS counterparts. This relieves GCKKS from any heavy computational or noise overhead. In experiments, GCKKS provides 7 levels with 1000-bit precision at ring dimension $2^{14}$, where each multiplication takes less than 30 ms. To our knowledge, this precision has never been achieved before. It can be used to preserve enough precision after noise flooding, a necessary ingredient for CKKS circuit privacy and a common approach to secure threshold CKKS and to provide IND-CPA$^\text{D}$ security.

This paper studies how local leakages characterize the global leakage in additive secret sharing over a finite abelian group, which is a special case of linear secret sharing and side-channel masking. Our main finding is structural: local-to-global leakage is governed by two disjoint components---the magnitude of local leakage and its spectral alignment across shares, while existing literature attempted to characterize the global leakage only by local mutual information (MI). We first give an exact decomposition of leakage in additive secret sharing. The decomposition reveals a structural parameter invisible to MI, while previous literature conjectured that the local MI alone suffices to characterize global leakage. We then show that this missing parameter is indispensable: two leakage channels with identical local MI can induce exponentially different global leakage. Our exact decomposition identifies the missing structural quantity and completely characterizes this phenomenon. We then show the separation theorem with its realizability---local MI, despite governing the classical leakage bounds, does not even determine the exponential rate at which leakage vanishes under homomorphic composition. More strongly, we establish a universal separation theorem: even when all permutation-invariant scalar measures of local leakage agree, the global leakage can exhibit exponentially different decay rates. We further provide the characterization of the spectral alignment factor and derive its lower bound through character-order multiplicity and Möbius inversion. We then extend the framework to automorphism-weighted sharing. We establish that automorphism-weighted sharing can achieve perfect leakage cancellation with finitely many shares, even for non-trivial full-support local leakage channels. In sharp contrast, such perfect cancellation is impossible for ordinary additive sharing with non-trivial i.i.d local leakage channels and finitely many shares. Consequently, local leakage magnitudes correctly measure the average amount of local leakage, but discard the compatibility structure needed for composition. Magnitude-only bounds must optimize over structural alignments that the actual leakage channel does not realize.

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.

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.

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.

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

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.

The CKKS scheme allows approximate arithmetic on encrypted data, and has found widespread use in privacy-preserving computation. A rigorous control of its homomorphic error is critical for both precision and security guarantees. In particular, in some settings such as IND-CPA^D or threshold settings, the latter computation error should be hidden at the time of decryption. This is achieved by noise flooding techniques, which require a precise upper bound on the computational error magnitude. When dealing with discrete data and a single decryptor, this is addressed by ensuring statistical correctness, which also requires a precise error management. Yet, current approaches to CKKS error analysis provide either rigorous worst-case bounds that are far off empirical measures, or average-case bounds that rely on various heuristics and do not provide strong enough guarantees for security. In this work, we develop a framework based on so-called randomization keys (RDKs), which are encryptions of zero injected at key-switching and rescaling steps to render the homomorphic error amenable to rigorous probabilistic analysis. Combined with tail bounds, this yields, to our knowledge, the first fully rigorous error analysis framework for CKKS computations. Our framework is modular: RDKs make the error of each elementary operation amenable to rigorous bounds, after which the error of a circuit follows by standard numerical error propagation. Our rigorous bounds are comparable to heuristic ones and closely match empirical measures, but cost additional evaluation material (RDKs) generated by the secret key holder. In the context of rigorous bootstrapping, this induces a communication overhead of 27% over the bootstrapping keys for a single evaluation, and of a further 8% for each additional evaluation. We show that, when a circuit is evaluated repeatedly, most of these keys can be reused across evaluations. As our main application, we derive a complete and rigorous analysis of binary CKKS bootstrapping, and a full, rigorous, parameter set for the bootstrap-and-clean technique. Compared to a standard Gaussian-type heuristic approach, our parameters only require a modulus increase for bootstrapping of $\approx 3\%$, while providing rigorous precision estimates.

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.

IND-CPA-D security is an extension of IND-CPA security introduced in the context of Fully Homomorphic Encryption (FHE). It captures the situation where the computation result is known to the adversary; it is in particular necessary for FHE with threshold decryption. This work presents three new attacks in this situation on the BFV and BGV FHE schemes, when their parameters are instantiated with heuristic assumptions commonly used to enable correctness. We first extend the \emph{bootstrapping failure attacks} from Cheon \emph{et al.} [CCS'24] on the DM/CGGI and CKKS schemes, to both BFV and BGV. We focus on BGV when instantiated with the so-called powerful-basis representation of ring elements. The second attack relies on \emph{skewing the ciphertext noise} in BFV, making it outpace the heuristic noise bounds for plaintext-ciphertext multiplications. This is achieved by crafting plaintexts, for which the noise bounds do not hold. The third and last attack focuses on outpacing the noise growth in BFV ciphertext-ciphertext multiplications. For this purpose, we \emph{skew the mask} part of the ciphertext by selecting a random encryption of zero, whose addition yields a ciphertext with a sufficiently large mask norm. While the first two attacks successfully recover the secret key, the last attack instead breaks the IND-CPA-D indistinguishability game. We report experiments on all these attacks, based on the HElib and OpenFHE libraries, respectively, for BGV and BFV. Notably, the second attack implemented in OpenFHE fully recovers the secret key in a few minutes to a few hours, depending on the parameters.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

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.

While quantum position verification aims to certify a prover's location using quantum information, existing security definitions only guarantee that part of the successful adversarial party is in the claimed location. This leaves open the possibility that a distributed team of adversaries can jointly simulate a prover in a way that defeats the intended meaning of ``being at a location'' in position-based cryptography. We introduce stronger notions of position verification that we call quantum localization, which requires that there is a specified, unclonable state at the verified spacetime point -- and that this state can be found nowhere else. We show that quantum localization leads naturally to a meaningful notion of trajectory verification, in which quantum information is verifiably tracked through space and time. We construct quantum localization and trajectory verification protocols using quantum anchor states, which generalize coset states from unclonable cryptography. The security of our schemes is proven in the classical oracle (i.e. ideal obfuscation) model, which can be heuristically instantiated in the plain model using post-quantum indistinguishability obfuscation. We also introduce and instantiate the concept of functionality localization, which guarantees that the adversary has the ability to compute a secret function at the verified spacetime point, and this function cannot be computed anywhere else. This raises the intriguing possibility of localizing computational capabilities in space and time. More broadly, we believe our notions of quantum localization and subsequent feasibility results provide stronger foundations for position-based cryptography. At a conceptual level, our results also explore the tight link between two fundamental notions in physics -- location and information -- thus serving as a natural foundation for cryptographic capabilities tied to physical spacetime.

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

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.

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.

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.

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.

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.

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.

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.

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.