Fault injection attacks have been extensively studied in the context of post-quantum cryptography, yet existing analyses on code-based KEMs largely focus on faults targeting the Fujisaki-Okamoto transform. This work presents new fault injection attacks against BIKE and HQC that operate beyond this commonly protected component and target less obvious instructions within the decapsulation process. The proposed attacks achieve full key recovery using only valid ciphertexts under NIST Level 1 parameters, requiring 17392 and approximately 3 million decapsulation queries for HQC and BIKE, respectively. In addition, we introduce a general approach to identify effective fault locations by analyzing decoder behavior under perturbed conditions. The attacks are experimentally validated on an STM32H7 microcontroller using laser fault injection, demonstrating high repeatability. These results reveal a broader attack surface and provide a foundation for more efficient fault attack analyses in future work.

Shift-invariant permutations of \(\mathbb F_2^n\) are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of \(\mathbb F_2^n\) constructed from a recursively defined sequence of mappings \(\{\gamma_j\}_{j\ge 0}\) associated with landscapes. First, we prove that, under an explicit dimension condition relating \(n\) to the support of the landscape, the sequence \(\{\gamma_j\}_{j\ge 0}\) has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on \(\mathbb F_2^n\) with a nonzero special index. Then, we determine the eventual zero or periodic behavior of \(\{\gamma_j\}_{j\ge0}\), including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring \(\mathbb F_2[z]/\langle p(z)\rangle\), where \(p(z)\) is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

We study a protocol-level reaction leakage in CKKS deployments where public coefficient-to-slot (C2S) evaluation keys are combined with a client's 1-bit validity response. Under this deployment surface, a malicious evaluator can recover a ternary secret key using asymptotically optimal $O(\mathcal{H})$ reaction queries, where $\mathcal{H}$ is the entropy of the secret key. The attack does not break RLWE or CKKS IND-CPA security. Instead, it exploits the interaction between client-side validity reactions and public homomorphic linear transformations. A shift of a public encryption key yields a ciphertext whose plaintext is a function of the secret key; the public ${\sf C2S}$ layer then repacks this information to construct a ciphertext whose validity depends strictly on whether a targeted secret coefficient matches a guessed value. Furthermore, each submitted query is independently randomized with a fresh encryption of zero, so that each resulting malicious ciphertext appears entirely distinct, thereby allowing the attack to simply evade trivial detection mechanisms on the client side. We implemented the full end-to-end attack in Lattigo v6.2.0 and recovered the full secret key across four parameter sets drawn from standard CKKS presets. For uniform ternary secrets, the attack uses $O(N)$ queries and is within a factor $2/\log_2 3 < 2$ of the oracle-only entropy lower bound. For sparse ternary secrets, a tailored variant further reduces the number of queries in practice. Our results show that observable validity reactions form a practical key-recovery channel in CKKS deployments exposing this surface, even when the underlying cryptographic assumptions remain intact.

FAEST is a post-quantum signature scheme that combines VOLE-in-the-Head with QuickSilver to prove knowledge of a secret key. It relies on well-established symmetric primitives and offers small public keys, but signing and verification are computationally expensive. We present an NVIDIA GPU implementation of the key-generation core and the QuickSilver procedures OWFProve and OWFVerify for the standard and EM constructions in both s and f variants. Profiling shows that once AES is accelerated by hardware, field multiplication in QuickSilver becomes the largest cost throughout this parameter grid. In FAEST-128f, field multiplication takes about 82% of signing time. To address this bottleneck in our GPU implementation of FAEST, we use PTX clmad for native carry-less arithmetic and Karatsuba to reduce the number of limb products. The clmad build improves throughput across all twelve OWFProve and OWFVerify paths, and its advantage grows with the field width. On an RTX A5000, PTX clmad raises standard OWFProve throughput to 1.99x, 2.45x, and 2.82x that of the software-multiplication build at 128, 192, and 256 bits, respectively. Together, PTX clmad and Karatsuba deliver 26.6x the throughput of the software-multiplication build in the field-multiplication-heavy kernel of standard 256-bit OWFProve. When all OWFProve stages are included, the combined build reaches 2.9x and 3.1x the software throughput for standard and EM at 256 bits, respectively. These results establish native carry-less arithmetic as a key design choice for GPU implementations of FAEST, with Karatsuba providing an additional improvement for 256-bit proving.

Choosing an S-box for a hardware-oriented cipher means balancing cryptanalytic quality (differential uniformity $\delta$, linearity $L$, algebraic degree), circuit complexity (the number of AND gates and the AND depth $D$), and implementation cost (silicon area and, in masked designs, registers and fresh randomness). Under Boolean masking the non-linear gates dominate this cost and $D$ sets the latency, so automated S-box searches have concentrated on quadratic permutations, which admit depth-1 circuits but make the algebraic degree of a cipher grow slowly. We present YOSHAN, a co-synthesis system that optimizes an S-box and its gate-level circuit together instead of fixing the lookup table first. It combines structural algebraic seeding (subfield towers, Feistel, Misty, and product-round Feistel constructions, affine wrappers, CCZ graph automorphisms, bilinear and shear seeds), cryptographically guided evolution of the circuit DAG by algebraic rewrites, a differentiable Piling-Up relaxation with Hungarian LSAP projection, and multi-level circuit optimization (SMT sub-DAG shaving, stage-preserving common-subexpression elimination, exact depth-1 SAT synthesis, and algebraic-structural inverse compilation) inside a quality-diversity archive across $n \in \{5,6,7,8\}$. Every archived circuit is exported gate for gate to SystemVerilog and certified by exhaustive simulation and a Z3 miter. The archive holds 31,129 certified netlists covering 56 $(n,\delta,L,\deg)$ profiles; three extended-affine invariants and an exact affine-equivalence solver split them into members of known classes (Category A) and permutations provably not extended-affine equivalent to any power map or to the cipher S-boxes we compare against (Category B, 15 benchmark classes $\mathsf{YSH}_{n,i}$, 13 with stratified subspace-filtration degree spectra). All 30 reported S-boxes and their explicit inverses are synthesized gate-exactly in 45 nm CMOS, unmasked and as pipelined first-order DOM modules, and every benchmark circuit is traced to its seed and the search stage that shaped it. Results include a gate-exact AES-equivalent circuit at the optimal AND depth $3$ ($42$ AND, $101$ XOR) with an explicit depth-3 inverse ($42$ AND, $106$ XOR), a 6-bit degree-5 permutation $\mathsf{YSH}_{6,5}$ ($\delta=6$, $L=24$, boomerang uniformity $\beta=14$) with $12$ AND gates, a 5-bit quartic permutation $\mathsf{YSH}_{5,4}$ with $5$ AND gates at depth $2$ in both directions, and 8-bit degree-7 permutations with $28$ and $18$ AND gates. All forward and inverse circuits are compared with the best published implementations.

Profiled side-channel attacks combine noisy leakage predictions with the mathematical relations imposed by the target algorithm to recover secrets from a small number of observations. Two established approaches are algebraic side-channel analysis (ASCA), which encodes leakage predictions and algorithmic relations as a Boolean satisfiability (SAT) problem, and soft-analytical side-channel analysis (SASCA), which performs probabilistic inference over a factor graph using belief propagation (BP). We evaluate both on the AES-based MILENAGE authentication algorithm deployed on USIM cards, targeting the first AES-128 invocation on $\mathit{RAND}\oplus\mathit{OPc}$ under the subscriber key $K$, where $\mathit{OPc}$ is an operator-specific secret unknown to the attacker. Neural networks predict posterior probability distributions over the AES S-box output byte values across multiple rounds and these predictions are supplied to ASCA and SASCA to recover $K$ and $\mathit{OPc}$ from a single trace. SASCA recovers both secrets in 87.7% of attacks, but converges to an incorrect $\mathit{OPc}$ in 6.1% of cases despite recovering $K$ correctly. ASCA enforces global consistency and resolves this ambiguity, but it succeeds in only 34% of attacks under a 1-hour timeout and our constraint-selection strategy. Motivated by these complementary failure modes, we combine the two into a hybrid attack in which BP refines the neural network predictions before they are supplied to the SAT solver. The hybrid approach recovers both secrets in 93.8% of single-trace attacks, resolving all cases where SASCA recovers $K$ correctly but $\mathit{OPc}$ incorrectly. It has a higher success rate and a lower average runtime than either method alone, despite performing more work per attack. Finally, we suggest a countermeasure, based on masking each AES round key with an independent, per-device secret, that reduces an attacker's advantage over guessing $K$ and $\mathit{OPc}$ to zero bits, and confirm empirically that it defeats the hybrid attack in all evaluated cases.

Signatures in the MPC-in-the-head paradigm rest only on a symmetric primitive, but their signing is slow, because it computes hash functions and a linear map for every simulated party of every repetition. We show that the Hexagon NPU of Snapdragon SoCs shortens one complete signing operation of AIMer, the MPC-in- the-head signature that the Korean post-quantum cryptography competition selected. Prior work speeds up such signatures on one CPU core, accelerates post-quantum arithmetic on GPUs for batches of operations, and reports only single post-quantum functions for mobile NPUs. Our implementation divides each signing operation along its dependency graph. The NPU computes the hashing and the per-party linear map of the last repetitions, which need no secret key, and the CPU keeps the secret key and the two hashes that absorb the repetitions in index order. A fast AArch64 implementation serves both as the CPU part and as the baseline, and it signs 4.5 to 6.1 times faster than the reference implementation on one core. On a Snapdragon 8 Gen 3 tablet, one core with the NPU signs 1.30 to 1.42 times faster than two cores and 1.74 to 1.97 times faster than one core for the three short-signature parameter sets. The same configuration uses 13 to 27 % less energy per signing operation than two cores. On Snapdragon 8 Elite and 8 Gen 2 phones, one core with the NPU signs 1.28 to 1.35 and 1.74 to 1.82 times faster than two cores.

Fully homomorphic encryption (FHE) allows arbitrary computation over encrypted data, but its secret key presents a single point of failure which limits its applications. Threshold FHE patches this gap by distributing the secret key to $K$ parties, requiring a threshold $t \leq K$ of them to cooperate for decryption. We focus on the asynchronous setting where a ciphertext can be decrypted by collecting decryption shares from any $t$ parties who do not need to coordinate or even be online simultaneously. Asynchronous schemes are sought in applications such as privacy-preserving Ethereum Virtual Machines (EVM), processing of long-lived private data with quorum-based decryption and the thresholdisation of any cryptographic primitive in general. We present Tulva, a practical threshold FHE scheme which equips a base FHE scheme with an asynchronous threshold decryption mechanism in a modular way. Our scheme simultaneously (1) is compatible with virtually any base FHE scheme and leaves its ciphertexts unchanged apart from an appended random tag, (2) supports a wide range of threshold profiles $(t,K)$ and ring degrees $\geq 256$ with 6--25 bits partial decryption per plaintext bit, and (3) achieves security in the presence of partial decryption queries on challenge ciphertexts based on the standard LWE assumption. We provide an open-source implementation, benchmark its threshold decryption performance and evaluate the end-to-end costs for typical privacy-preserving EVM use cases. For 16-out-of-512 threshold and a publicly preprocessed ciphertext, computing secret-dependent partial decryption and public share combination requires only 3.7ms and 0.5ms, respectively, on commodity hardware. Compared with the state-of-the-art synchronous scheme [Zyskind et al., CCS'25], we replace their ciphertext-independent yet interactive preparation of secret-correlated randomness with a public, ciphertext-dependent 0.5s preprocessing step, eliminate interaction in the online phase while maintaining similar decryption time on the same machine, and support 32$\times$ more total users.

Unbiased and publicly verifiable randomness is a fundamen- tal component of Web3 security, and output-private distributed verifiable random functions (DVRFs) extend this guarantee by keeping the gener- ated randomness hidden from chain observers until the requester chooses to reveal it. Two constructions currently realize output privacy under dif- ferent algebraic regimes: FlexiRand, whose on-chain verification rests on bilinear pairings, and IcyVeil, a pairing-free design whose verification re- duces to a constant number of group operations. While it is folklore that pairing-free verification should be cheaper on the Ethereum Virtual Ma- chine (EVM), the actual on-chain cost of output-private randomness has never been measured for either scheme. In this paper, we present the first EVM implementations of both constructions. Both verifiers are served by a single coordinator contract realizing the common blind–evaluate–pre- verify lifecycle, so that every measured difference is attributable solely to the verification arithmetic. The isolated verification is 57% cheaper in execution gas for the pairing-free scheme (51,561 against 118,541 gas); over the full request lifecycle, whose remaining stages are shared, the ad- vantage is about 11%. This on-chain saving comes with a cost off chain: the pairing-free scheme’s distributed evaluation requires roughly 2.5 to 8.2 times more aggregate committee compute across committee configu- rations (n, t), a gap absorbed comfortably by Ethereum’s block time and one that narrows further once the committee executes concurrently. We report both axes, separating one-time distributed key generation (DKG) cost from IcyVeil’s consumable preprocessing, and reconcile the on-chain and off-chain ratios, which point in opposite directions. All contracts, harnesses, and raw measurements are publicly available.

Mitigating Side‑Channel Analysis (SCA) of cryptographic implementations relies heavily on masking schemes; however, achieving efficient and straightforward hardware realizations remains challenging. While Threshold Implementation (TI) provides provable security against glitches in hardware, it incurs significant area overhead due to the large number of shares required to protect non‑linear functions. Successor schemes achieve the same security order with a minimal number of shares, but often rely on a high amount of per‑cycle randomness, especially at higher orders. Recent optimizations such as NullFresh and MultiStage attain minimal share counts without additional randomness; however, they lack a generalized methodology for higher‑order security. In particular, although MultiStage enables automated generation of low‑randomness masked designs, it is currently limited to first‑order protection. In this work, we bridge this gap by introducing an automated masking technique for arbitrary functions that guarantees second‑order security in the glitch‑extended probing model. Building upon the MultiStage approach, our method preserves the efficiency of NullFresh by minimizing requirements for fresh masks, while overcoming structural limitations of previous schemes. We demonstrate the feasibility of the approach on the lightweight block ciphers PRINCE, Midori, and SKINNY. The resulting designs are formally verified using SILVER and PROLEAD, and experimentally evaluated on FPGA using TVLA.

The work of (Escudero et al., CRYPTO 2020) introduces the so-called edabits, which are defined as a secret sharing of an integer over an arithmetic domain, together with its bit decomposition secret shared over a binary domain. In the same work, it is shown how edabits can be used to securely evaluate advanced primitives such as comparison, bit decomposition, and truncation, which are essential building blocks in more complex applications such as privacy-preserving machine learning and beyond. Edabits are general and can be defined over any secret-sharing scheme or corruption model. Such flexibility, coupled with their wide range of applications, makes edabits a powerful target correlation. Escudero et al.~introduced a protocol to generate edabits that works in the arithmetic black-box (ABB) model, that is, it is agnostic to the concrete secret-sharing scheme and even works both for fields $\mathbb{F}_p$ and rings $\mathbb{Z}_{2^\ell}$, as well as both for honest majority $t<n/2$ and dishonest majority $t<n$. Unfortunately, the communication complexity of their approach grows as $\Omega(n^2\ell)$ bits with $\ell$ being the bit-length of an element in the arithmetic domain. This becomes a bottleneck in larger protocols since most MPC primitives such as multiplications or openings can be done with linear communication of $O(n\ell)$ bits. In this work we present a novel approach for generating edabits in the ABB model that achieves \emph{quasi-linear} communication complexity of $O(n\ell\log n)$ bits, for the setting where $t<n(1-\epsilon)$ for a constant $\epsilon>0$. This includes the honest majority case $t<n/2$, but also dishonest majority with an (arbitrarily small) constant fraction of honest parties. Our result is achieved via novel applications of randomness extraction methods, as well as better edabit aggregation for the binary components. Along the way and of independent interest, we improve the communication complexity of dabit generation (dabits are bits shared in both binary and arithmetic domains) from $\Omega(n^2\ell)$ bits achieved in (Rotaru and Wood, INDOCRYPT 2019), to linear $O(n\ell)$ bits.

We present a new proximity test for Reed--Solomon codes that admits a higher-agreement regime with soundness approaching the field's bit length. All prior work in this area [AHIV2017,BCIKS2020,BCHKS2025] uses the idea of *scalar* batching in which the verifier provides a scalar challenge for each codeword, and the prover must supply a codeword equivalent to the combination, and the verifier tests it at randomly opened columns. Our main insight is to instead use a low-degree polynomial challenge for each codeword. We prove that the low-dimensional spaces generated by polynomial challenges become maximum distance separable (MDS) after deleting a few coordinates, and this phenomenon leads to a new kind of proximity gap that we can exploit. This insight enables a simpler, in fact elementary counting proof for soundness of the proximity tests. We do not need the Polishchuk--Spielman lemma or Guruswami--Sudan decoding. The same technique proves soundness of Polygero, a Ligero-inspired IOP~[AHIV17], beyond the unique-decoding regime. Through recursion, Polygero produces proofs with a number of field elements logarithmic in the witness size, independently of the number of linear constraints. It does not require roots of unity in the finite field or out-of-domain sampling. The soundness analysis, including the extractor and the recursive composition, and every reported parameter schedule are machine-checked in Lean.

We present an architecture that provides WireGuard’s resistance against future quantum adversaries. By preserving the core protocol, our approach minimizes deployment effort and adds certificate-based identities to WireGuard peers. To achieve Post-Quantum (PQ) resistance, we establish an external mutually authenticated control channel built on the TLS 1.3 handshake and layered on top of TCP, UDP, or QUIC. Its key establishment includes Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). An auxiliary shared secret is derived from the exported keying material of the resulting session and injected into WireGuard’s native Pre-Shared Key (PSK) interface; this derivation is identical for all three transports. To support scalable deployment, the control channel is authenticated with X.509 certificates issued by a Public Key Infrastructure (PKI), using the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) for PQ certificate signing. We develop a Tamarin model of the composition layer and symbolically analyze the secrecy, binding, and provisioning-order properties of the interface between TLS 1.3 handshake and WireGuard, identifying the critical conditions necessary for secure deployment. Finally, we evaluate the design to quantify handshake latency and CPU time for classical, pure PQ and hybrid key establishment, classical and ML-DSA certificates, and the three transports, comparing it against an existing PQ WireGuard baseline achieving state-of-the-art results.

Authenticated Encryption with Associated Data (AEAD) provides confidentiality and integrity, but traditional security notions do not prevent ciphertexts from decrypting correctly under multiple keys. This motivates committing security, which requires ciphertexts to bind to their encryption inputs uniquely. Recent analyses revealed commitment failures in several forkcipher-based AEAD schemes, leaving open the question of whether these failures are inherent to forkciphers or design specific. We provide a comprehensive committing security analysis of existing forkcipher-based AEAD constructions, filling this gap by establishing both negative and positive results. Our analysis shows that while some designs inherently fail to achieve strong commitment, others achieve meaningful commitment guarantees, demonstrating that forkciphers can serve as a foundation for committing-secure AEAD schemes. We derive tight bounds for commitment notions for existing constructions. As a key technical contribution, we formalize a forkcipher-based hash construction and prove its collision resistance, which serves as a foundation for our security analysis.

Cryptographic software, with its inherent flexibility and adaptability, has become essential for meeting today’s rapidly evolving security requirements, despite offering lower performance than dedicated hardware accelerators. However, Side-Channel Analysis (SCA) complicates its secure execution on physical hardware, making robust protection a central challenge. While the masking countermeasure offers provable security guarantees in theory, its effectiveness is often undermined by the processor’s micro-architecture. In response, formal adversary models have been adapted to account for micro-architectural leakage under generic (but over-conservative) assumptions on the hardware. Consequently, achieving security under such a generic model requires compilers to produce less performant software. To bridge this gap, secure hardware-software co-design assumes a precisely specified hardware leakage behavior, enabling the specification of constraints for secure compilation. While this approach reduces the overhead required to counteract these effects, it does not entirely remove it. This work follows a more fundamental paradigm: instead of managing leakage in software, we aim at eliminating it at its source. Conceptually, we propose architectural changes to general-purpose processors at the Register-Transfer Level (RTL) that remove the root causes of micro-architectural leakages. The application of these changes enables the secure execution of masked software without introducing micro-architectural leakage under the Robust but Relaxed (RR) d-probing model, thereby removing the need for complex, security-aware compilers and hardware-specific workarounds in the software. While our countermeasures can be applied to many micro-architectures, we formally prove the security of each countermeasure individually and integrate them into the Ibex processor, whose security we evaluate as a whole through tool-assisted leakage assessment of the full netlist and physical experiments on a Field Programmable Gate Array (FPGA).

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.

We study the hardness of finding permutation automorphisms of linear codes. We look into three main problems: $\mathsf{AUT}$, $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$ which, respectively, ask to find a non-trivial automorphism, a generating set and the order of the automorphism group. We give polynomial time reductions from $\mathsf{AUT}$ to $\mathsf{ISO}$ (the problem of finding a permutation isomorphism between two linear codes), and from $\mathsf{ISO}$ to $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$. This shows that $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$ are unlikely to be easy in the worst case, since all known solvers for $\mathsf{ISO}$ take exponential time if the hull dimension (the subspace given by the intersection between the code and its dual) is large enough. Furthermore, we give a reduction from $\mathsf{AUT}$-$\mathsf{Gen}$ to the problem of finding generators for the automorphism group of a graph, which we refer to as $\mathsf{GraphAUT}$-$\mathsf{Gen}$. Up to some polynomial factors, the reduction runs in time $O(n^{h})$, with $n$ being the code length and $h$ the hull dimension: for $h = O\big(\log(n)\big)$, this implies that $\mathsf{AUT}$-$\mathsf{Gen}$ can be solved in worst case quasi-polynomial time. We also give a simpler version of the reduction, running in time which is exponential in the worst case (arguably, only for rather contrived codes), even for small $h$. However, heuristically, the algorithm is on average extremely efficient for small $h$. We use it as a concrete solver and show that a proof-of-concept implementation is significantly faster than the built-in implementations of Leon's and Feulner's algorithms provided by $\texttt{Magma}$ and $\texttt{Sagemath}$.

Card Payment Terminals commonly use tamper sensing meshes to deter physical attacks on devices handling sensitive data such as cryptographic keys. Although their use of such meshes is frequently referenced in research literature, the public record contains little research on their construction. Addressing this gap, in this paper we present the first comprehensive analysis of the practical implementation of tamper sensing meshes across a wide range of payment terminals, and some other devices such as ATM key pads and a data center HSM. We provide detailed photos of critical features. Based on our observations, we construct a taxonomy of mesh construction techniques. Our analysis reveals that most commercial devices use surprisingly simple construction techniques, and their structure size rarely approaches manufacturing limits. Based on our analysis, we identify a concise set of design patterns for the construction of secure tamper sensing meshes. We conclude that designing tamper sensing meshes that exceed the industrial state of the art is viable even using inexpensive and easily available manufacturing processes. Our set of design recommendations creates a foundation for both the practical tamper sensing mesh implementations and for future research into their design. Our results enable researchers to base test specimens on concrete evidence of industrial practice.

Lattice-based post-quantum cryptography (PQC) and fully homomorphic encryption (FHE) rely heavily on the number theoretic transform (NTT) for efficient polynomial multiplication. While GPUs and FPGAs have been widely explored for NTT acceleration, neural processing units (NPUs), a rapidly growing class of AI accelerators, remain largely unexplored for cryptographic workloads. In this work, we develop a methodology for accelerating the NTT on NPUs, using AMD’s AI Engine (AIE) architecture as a representative NPU to develop and benchmark it. At its core is manual loop fission, in which large and complex loops are split into smaller primitives, enabling highly efficient software pipelining and avoiding memory stalls or register spilling. Applying it, we develop efficient Barrett reduction primitives and use these to construct three high-throughput, low-latency NTT implementations (radix-2, radix-4, and radix-8), achieving significant performance gains over the AIE compiler and prior literature. On AMD’s first-generation AIE specifically, we achieve speedups of $8.27\times$ to $13.2\times$ in throughput and $2.44\times$ to $10.3\times$ in latency per AIE tile in comparison with prior work. Our implementations support arbitrary NTT-friendly moduli and polynomial sizes up to degree 4096 for 14-bit moduli and 2048 for 30-bit moduli. Finally, we discuss the portability of our techniques to other NPU architectures, and identify which architectural features are most beneficial for NTT acceleration.

Blind signatures let a user obtain a signature by interacting with an issuer that controls the signing key, while the issuer never sees the message. They form the basis of anonymous credentials, which are the centerpiece of privacy-preserving digital identification to be deployed widely in the coming years. Existing plausibly quantum-secure blind signatures rely on bespoke cryptographic constructions, instead of standardized ones. This is dissatisfying from a cryptographic perspective, and also leads to practical issues: secret signing keys are often stored in secure elements, in which case only signature algorithms supported by certified secure elements can be the basis for deployed protocols. We give the first blind signature whose issuer runs a NIST-standardized post-quantum signature scheme unmodified. Issuance is just an ML-DSA signature on a commitment, and the blind signature is a zero-knowledge proof of knowledge, using the VOLE-in-the-head zero-knowledge proof system, of the ML-DSA signature. Security reduces to the EUF-CMA security of ML-DSA and to the proof system, with no new assumptions. A blind signature is about $1$ MB and takes under a second to produce and half a second to verify. Issuer-hiding and selective disclosure of signed attributes can easily be added on top for a few tens of kilobytes, at a proof size essentially independent of how many issuers the list names. Underlying the construction is edaBitE, a novel batch consistency check between binary and prime-field commitments. In a non-interactive proof, the existing edaBits checks it replaces would be the single largest item in the blind signature. We believe that edaBitE is of independent interest.

Anonymous credentials are seeing widespread deployment. Notably, the European Commission plans to roll out age-verification solutions based on anonymous credentials by the end of 2026. Similarly, Google open-sourced Longfellow, a zero-knowledge proof system that lifts the standardized mobile Driver License framework into a full-fledged anonymous credentials, and is currently being integrated with Google Wallet. Any secure deployment of anonymous credentials must address two major challenges: 1) provide guarantees against credential sharing, and 2) support proof-of-personhood. The standard approach adopted by the industry to address both is device binding, which is mandatory for mDL and was only recently formalized for anonymous credentials by Friedrichs et al. (Eurocrypt '26). Simply put, the idea is to have the user's phone Secure Element sign a fresh challenge from the verifier, and to prove knowledge of this signature in zero-knowledge at each credential presentation. To date, all existing approaches, including Vega (S&P '26), have only considered non-post-quantum solutions based on legacy signature schemes. Crucial for near-term deployments and adoption is to work with standardized post-quantum signature schemes, such as ML-DSA, which were not designed for privacy. Because of this, solutions based on general non-interactive zero-knowledge proof systems (e.g., Longfellow) appear to be needed. This genericity, however, requires proving complex statements, significantly impacting proving time. In this work, we present a modular device binding protocol tailored to work with ML-DSA. We avoid the pitfalls of the generic approach by leveraging the structure of ML-DSA resulting in an efficient solution, but retaining the security underlying the post-quantum standard. Our most efficient variants additionally rely on a weak-MLWR assumption for unlinkability, which can be removed at the cost of lower efficiency. While tailored for ML-DSA and requiring no modification to the FIPS~204 signing interface, our solution is modular enough to be integrated with different anonymous credential schemes, allowing real-world solutions to pick the most efficient building blocks. To demonstrate the feasibility of our solution, we provide a proof-of-concept implementation.

Integral distinguishers can reveal more than a zero-sum property: the number of ones in an output component may be divisible by a high power of $2$, rather than merely being even. To exploit this divisibility, we relate linear, integral, differential-linear, and restricted differential sums through two-way conversions with explicit divisibility guarantees and data complexity, recovering established links as special cases. We derive exact random-permutation probabilities and rigorous bounds to quantify the distinguishing strength while accounting for dependencies between output conditions. To discover these properties, we develop automated MILP/SAT models that use complete-round Walsh coefficients or combine Walsh and ultrametric representations to obtain stronger bounds. These weighted models prove finite divisibility even when compatible trails exist, beyond what trail-existence tests alone can establish. For differential-linear sums, we show that combining differential and linear propagation with local DLCT zeros can give false zero-correlation claims. We address this limitation with exact mix-basis models that establish zero correlation and finite divisibility. To complement these symbolic methods, we provide a black-box algorithm using exact histograms and the fast Walsh-Hadamard transform to search all output masks for selected input conditions and identify zeros and finite divisibility properties. Our MILP/SAT models significantly improve the divisibility bounds reported by Beyne and Verbauwhede in 674 cases across the SIMON family, as well as for PRESENT, without trail enumeration and at unchanged data complexity, e.g., from $2^5$ to $2^{11}$ on 9-round SIMON32 and from $2^6$ to $2^{22}$ on 10-round SIMON48. To our knowledge, we are the first to prove higher divisibility for 8-round SPECK and for BEANIE, with new bounds for GIFT-64 and Ascon and exact counts for SKINNY-64. Our black-box searches reveal new properties on RC5, ChiLow-32, KeeLoq, and KATAN32, including output-bit combinations missed by single-bit searches, and lead us to introduce probabilistic divisibility.

The Syndrome Decoding Problem (SDP) is a fundamental mathematical problem underlying code-based cryptography, which is considered a promising candidate for post-quantum cryptography. The Regular Syndrome Decoding Problem (RSDP) is a variant of the SDP in which the error vector follows a specific block-wise structure. Recent developments in RSDP-based cryptographic schemes have led to a wider variety of parameter settings, making it increasingly important to evaluate the complexity of solving the RSDP over a broad range of parameters. One of the main approaches to solving the RSDP is the algebraic approach, which transforms a given RSDP instance into a polynomial system and solves it using algebraic techniques such as the XL algorithm. In this work, we construct and analyze algebraic algorithms for the RSDP by combining and extending techniques used in existing algebraic approaches. Our algorithms mainly follow the framework of the hybrid algorithm proposed by Wang et al., while allowing an arbitrary solving degree $d$ in the application of the XL algorithm. We further consider two variants: an XFL-based method that combines partial Gaussian elimination with variable guessing, and a WXL-based method that exploits the sparsity of the Macaulay matrix. Our complexity analysis for various parameter settings shows that, for some fixed values of $n$ and $k$, the WXL-based variant using a larger solving degree $d>2$ is particularly efficient when the block size $\beta$ is sufficiently small, while the original hybrid algorithm becomes more efficient as $\beta$ increases.

We show how far Pollard rho can be accelerated on current NVIDIA GPUs by rebuilding its field arithmetic around the hardware, with the Certicom challenge ECC2K-130, the Koblitz curve $y^2+xy=x^3+1$ over $\mathbb{F}_{2^{131}}$ with an expected cost of $2^{60.9}$ iterations, as the benchmark. None of the speedup comes from changing the algorithm. It comes from a packed normal-basis representation in which every Frobenius power is a permutation network instead of a chain of squarings; from the carry-less multiply that CUDA 13.3 exposes in PTX (clmad), which forms a 131-bit product in six instructions; from three-input logic instructions for everything around it; and from a batch size, launch geometry and compact tiled state chosen by measurement against the pipes they load. Across sixteen paired steps, each held to a rule written down before it ran, these take one RTX PRO 6000 Blackwell from a $0.85$ billion iterations per second bitsliced control to $14.64$ in the audited campaign build, a $17.2\times$ gain (representation and arithmetic $6.3\times$, geometry $1.5\times$, memory layout $1.3\times$, clmad $1.2\times$), and a later build reaches $15.88$. That is about $230$ times the best published 2010 GPU kernel per card and puts the whole challenge under five GPU-years: five cards expect a solution within a year, a thousand in about three days. The gains depend on the die. clmad issues ten to eighteen times faster per SM-clock on the data-centre parts than on the workstation part, so the same change can win on one Blackwell part and lose on another; we report twelve GPUs from Turing to Blackwell per card, per SM and per dollar, and the CPU instruction sets that play the same role. Upper bounds derived from measured pipe rates leave about $1.5\times$ of headroom on one RTX PRO 6000, at $24$–$26$ billion iterations per second for any walk with one addition per step. The same levers applied to Pollard rho on NIST P-256 and P-384 on the same card give $1.52\times$ and $2.61\times$, to $1.632$ and $0.548$ billion iterations per second, which still leaves P-256 about $6\cdot10^{21}$ card-years away. We also separate the $\sigma$-walk from a table walk whose $20.08$ was measured under a cycle rule later found unsound (the exact rule runs at $8.24$), measure the walk constant at $2^{60.91}$–$2^{60.92}$ iterations, and report an FPGA engine at $8.25$ billion iterations per second on one AWS F2 and a campaign that walked $2^{56.68}$ iterations, $5.4\%$ of the expected work. Every number cites an evidence record; the code, data, evidence and a Dockerfile whose image starts the ECC2K-130 walk are at https://github.com/aburan28/rho-blackwell. None of this improves on the generic-group bound, and we do not claim that it does.

Merkle trees are the standard way to obtain logarithmic-size, logarithmic-time inclusion proofs over a large dataset, but they require a tree-shaped hash structure distinct from the ordinary, linear (Merkle--Damg\aa rd) hashing that most deployed systems -- including Bitcoin's own transaction and witness hashing -- actually perform. We present FlatMerkle, a construction that achieves the same asymptotic guarantees, $O(\log N)$ proof size and $O(\log N)$ verification time, over a single ordinary linear hash stream, by periodically re-injecting the hash function's own past internal states (``checkpoints'') back into the stream as ordinary message content. The result is a flat byte sequence whose digest is a single, unmodified invocation of the underlying hash function -- syntactically an ordinary digest of an ordinary byte string, not a distinguishable commitment format -- while still supporting compact inclusion proofs for any element, and compact proofs that a published file is malformed, so that an honest party can always answer a malicious committer in logarithmic space. We give the recursive construction, a closed-form formula locating any element in the structured stream, worked examples with illustrations, a security reduction to free-start collision resistance of the hash function's compression step, an optimal element-size analysis for both a flexible toy primitive and real SHA-256, a batched multi-element proof construction, a measured construction-speed comparison against Merkle trees, a concrete application to committing data inside a Bitcoin transaction annex (BIP-341), a design sketch using that application as a data-availability layer for an optimistic Bitcoin rollup, a from-scratch gas-cost comparison, on Ethereum, Rootstock, and Arbitrum, of an in-contract FlatMerkle commitment against an in-contract Merkle tree, tracing the three chains' differing verdicts to specific protocol design choices rather than to anything intrinsic to either construction, and a comparison against the closest prior art we are aware of, authenticated append-only skip lists.

Federated optimization enables collaborative learning over decentralized data but is accompanied by significant privacy risks due to the exchange of model updates. While differential privacy (DP) provides formal protection, optimization accuracy is often degraded, and robustness becomes particularly limited in the presence of Byzantine agents. A Byzantine-robust, differentially private federated SGD algorithm, DPF-SGD, is proposed, in which private step sizes are integrated with a DP noise–decay schedule to regulate gradient updates. To further enhance robustness, a privacy-preserving comparative elimination (PPCE) filter is developed to suppress Byzantine contributions during aggregation while preserving privacy guarantees. Almost sure convergence to the global optimum under ϵ-differential privacy is established, despite persistent noise and adversarial behavior. Experiments on synthetic and MNIST datasets demonstrate oneto two-order-of-magnitude reductions in final optimization error relative to DP baselines.

Bitcoin (BTC) is the largest crypto asset, yet the Bitcoin blockchain offers few applications in which BTC can be used. A standard approach to make BTC useful is bridging: BTC is deposited on the Bitcoin chain and a wrapped asset is minted on a chain such as Ethereum, where it can be used in smart contract applications. Unfortunately, all Bitcoin bridges to date require trust assumptions on a centralized party or a committee running the bridge to enable withdrawals of the deposited BTC, including state-of-the-art BitVM bridges. In this paper, we observe that while bridges are application-agnostic, most BTC holders are interested in collateral-based applications, where BTC is deposited as collateral, and only the depositor or a set of known counterparties can withdraw the asset. For this class of applications, we propose a primitive, Trustless Bitcoin Vaults, that guarantees that the BTC depositor or the counterparties can withdraw the deposited BTC following only the logic of the application smart contract without trusting any third party. We present a protocol that achieves the security guarantees of this primitive and instantiate it for a lending application where the deposited BTC is used as collateral to borrow against a set of liquidators on the Aave v4 smart contracts on Ethereum. Our mainnet experiments show that at the current Bitcoin price and fee rate, a deposit costs about \$0.7 in fees while a withdrawal costs at most \$7.7. Our construction is built on recent advances in efficient proof verification for Bitcoin.

The paper is currently under embargo and will be released by the end of October 2026.

Rising privacy concerns around large language models have accelerated research in private Transformer inference (PTI). Synthesizing the empirical claims in this line of research, however, is hindered by multi-dimensional cryptographic progress and inconsistent evaluation contracts. In this work, we systematize the field by constructing an empirical graph of 62 PTI systems, mapping system attributes to node features and evaluation compatibility to edges. A three-tiered analysis of this graph illuminates the state of private inference. Node-level attribution shows that cryptographic progress drives performance gains across most systems, yet always co-occurs with other factors (model fidelity, hardware, cost accounting). Edge-level auditing shows that only 1 of 1891 candidate system pairs is directly comparable under shared assumptions. Finally, graph-level analysis shows that the scaling frontier of private inference has plateaued at 13B parameters and projects the cost of deploying current PTI techniques on production-scale Transformers. Overall, this graph-based framework equips the community to evaluate PTI claims transparently and channel technical speedups into deployment-scale private inference.

Batched threshold encryption (BTE) enables a committee of servers to jointly decrypt any chosen subset of ciphertexts from a large pool, while all remaining ciphertexts stay private. BTE is a key building block for encrypted mempools, where transactions are encrypted until block inclusion to mitigate maximal extractable value (MEV). We give a new tree-based BTE construction from two simple building blocks which support additive homomorphism: a symmetric-key encryption scheme that is homomorphic over key and message space, and a thresholdizable public-key encryption scheme that is homomorphic over message space. These building blocks can be instantiated under a wide variety of assumptions including DDH, DCR, LWR and even LWE for post-quantum security. In our scheme, each ciphertext is associated with an index from an appropriate index space. We implement the DDH-based instantiation. Given an aggregated batch of 1,000 messages over a small 1024 sized index space, each server performs about 41~ms of single-thread computation, including a 100-of-300 threshold decryption. We also partially implement an RLWE-based post-quantum instantiation over a \(2^{128}\) sized index space for negligible collision probability among indices. A batch of 1024 messages uses approximately 0.89 MB per ciphertext and 20 seconds of single-thread decryption per server.

The HM-QCT protocol, presented by Mazzoncini et al. in 2025, uses a unique feature of quantum information to achieve quantum key distribution (QKD) with secret-key rates beyond standard constructions. The protocol has been designed in the hybrid quantum–computational time-lock (QCT) security model which imposes two independent (but related) restrictions on the attacker: (1) a computationally secure encryption scheme which a successful attacker must break within a narrow timeframe and (2) an assumption that the attacker can only store quantum information with low fidelity. We first review the protocol and its two-assumption model by presenting, in explicit form, the two natural “harvest now, decrypt later” strategies against it, one using quantum memory and one using classical memory. We show how each is excluded by exactly one of the two assumptions, so that harvesting resistance rests on their conjunction and on the presumed existence of a technological gap: the adversary's quantum memory must decohere much faster than the time it takes to break the short-term encryption. Finally, we introduce HM-PRF, a variant that replaces the short-term encryption with a pseudorandom function (PRF), evaluated locally. By eliminating the transmission of enciphered classical information, the adversary does not need to race an impending expiry event. We compare the security of our construction against the original and argue that our PRF-based assumption yields a more realistic adversary. It simply requires the existence of one-way functions rather than a predicted lasting limitation of quantum computation and memory technology.

We introduce Leakage-Resilient Incompressible cryptography, which simultaneously addresses two variants of side-channel attacks that have been tackled in theoretical cryptography. Leakage-resilience seeks to provide security against an adversary who learns a part of the secret-key and the entire ciphertext or signature; conversely, incompressible cryptography provides security against an adversary who learns the entire secret-key, but only a part of the ciphertext or signature. However, constructions in either of these security models can fail against an attack in the other model. In this work, we define a new model of security that subsumes both leakage-resilient cryptography and incompressible cryptography, and we present several non-trivial positive and negative results. On the positive side, first we present a transformation from incompressible symmetric-key encryption (SKE) to leakage-resilient incompressible SKE in the information-theoretic setting. Next, as one of our main results, we construct a leakage-resilient incompressible public-key encryption (PKE), combining an incompressible SKE and a new primitive that we call leakage-resilient non-committing key encapsulation mechanism (LR-NC-KEM). While an information-theoretic incompressible SKE suitable for use in both these constructions already exists in the literature (Dziembowski, CRYPTO 2006), we present a new construction achieving ciphertext-rate $\frac{1}{2}$ and compression-rate $\frac{1}{2}$, using an appropriate notion of invertible extractors; this leads to corresponding improvements in the final parameters we obtain in these constructions. We also construct a leakage-resilient incompressible signature scheme in the classical random oracle model, assuming $(\mathsf{DCR}\text{ or }\mathsf{LWE})$ and the Decisional Linear assumption, with signature-rate and compression-rate $1-o(1)$ and leakage-rate $1$. On the negative side, we show barriers to significantly improving the parameters we obtain, by showing impossibility of basing the security of such improved schemes on blackbox reductions. Apart from the general framework and the specific results we obtain, some of the intermediate tools that we define and instantiate, like LR-NC-KEM and invertible extractors, may be of independent interest.

In this paper, we present a novel framework for cube attacks named cube attacks with elimination strategy. The core idea is to find specific key conditions and cubes such that their superpolies under these key conditions can be efficiently computed. By recovering these conditional superpolies, we can solve the corresponding equation system and thereby retrieve key information. If a sufficient number of such key conditions can be found, the attack can be extended to a larger key space. To apply this framework in practical attacks, we propose the following techniques. First, we propose a nested coefficient solver that combines variable substitution and symbolic computation to efficiently recover superpolies, and present the conditional monomial prediction technique to rapidly recover conditional superpolies. Second, by combining numeric mapping with monomial prediction techniques, we propose an automated cube search algorithm that is capable of generating a large number of good cubes for attacks. Finally, we develop two kinds of testing methods, which are used to efficiently extract substantial key information from large-scale equation systems. To illustrate the power of our techniques, we apply them to Trivium. As a result, for 840 rounds of Trivium, a practical key recovery attack is mounted with complexity below $2^{55}$ and a success rate 77.8\%. For 845 rounds, we present a practical key recovery attack with complexity below $2^{56}$ and a success rate 98.1\% for $2^{80} \times 59.1\%$ keys. For 855 rounds, we present a theoretical weak-key recovery attack for $2^{74}$ keys. To the best of our knowledge, these are the best practical and theoretical attacks on Trivium. The improvements in the number of rounds reached are 13 for practical attacks and 4 for theoretical attacks, respectively.

Chats do not always unfold in a single clear order. Two users may send messages before information about either message reaches the other sender. Such messages are concurrent, but most instant messengers provide no way for users to recognize this relationship. Chen and Fischlin (Eurocrypt 2024) studied this limitation in the two-user setting, showing that Signal does not expose enough information to recover the context in which a message was sent; they proposed a fix. We study group chats, where a user may need to reason about ordering and concurrency among other users' messages. This can become a security problem when network delays or adversarial interference cause an authentic message to be shown in a misleading context. Event ordering is a classical problem; Lamport clocks and vector clocks are standard starting points. Secure messaging needs a different treatment because communication is asynchronous, bandwidth is limited, and added latency is undesirable. To address the problem under these constraints, we introduce causal awareness: the ability of a receiver to reconstruct a specified part of the causal context in which an accepted message was sent. Senders transmit records of what they have sent and received. Receivers verify these records and compare them with their own. We develop a framework of correctness and security notions for causal awareness in group chats. Our definitions are parameterized by how much causal information receivers must recover. We give baseline constructions and prove their properties. We also introduce checkpoint-aided and server-aided variants of the framework and prove that, in each, our notions of correctness and integrity imply causal awareness. We discuss how causal information could be surfaced in a messenger's user interface.

This paper investigates functional correctness and masterkey reconstruction in explicitly constructed rectified linear unit (ReLU) implementations of Camellia-128, Camellia-192, and Camellia-256. Exact neural realizations of Boolean gates, S-box selectors, and bit permutations provide a framework for reproducing Camellia on binary inputs. We present a component-wise correctness argument and report known-answer-test agreement for Camellia-128. We then analyze how selected whitening and round-key quantities determine the external master key through public key-schedule identities. Inverse rotations of suitable subkey pairs recover the required key components, whereas prewhitening-key recovery alone is insufficient for complete reconstruction of the longer keys. Under explicitly constructed synthetic internal-oracle access, symmetric real-valued perturbations identify target subkey bits, requiring 128 and 256 query pairs for the coordinate-wise Camellia-128 and Camellia-256 procedures, respectively. A separate Camellia-192 experiment validates deterministic key-schedule inversion under direct access to DNN-generated round keys. Across 1,000 independently sampled master keys per variant, all three procedures achieved exact recovery in every trial, yielding 3,000 successful recoveries out of 3,000 trials, with zero recovery failures and no Camellia-192 complement-consistency failures. These results validate conditional master-key reconstruction under the specified internal-access models and highlight the distinction between binary functional correctness and security under stronger access assumptions. They do not establish plaintext/ciphertext-only attacks against standard Camellia.

Sorting in secure computation has been studied almost as long as there have been implementations of multi-party computation (Wang et al., AsiaCCS'10). More recent advances include completely secure implementations (revealing nothing other than the list size) that have used Quicksort (Araki et al., CCS'21) and radix sort (Asharov et al., CCS'22). For the first time, we extensively compare the two variants across a range of parameters and for both honest- and dishonest-majority computation. We then apply secure sorting to improve sparse matrix multiplication without oblivious RAM based on recent work by Damie et al. (CODASPY'26). Our main contribution here is to produce an output in the same format as the inputs to the multiplication. This is needed for repeated multiplication of graph adjacency matrices, which we use to find cycles in graphs. Such cycles have been associated with money laundering, and this also applies to another graph pattern dubbed scatter-gather, which we can detect with the same approach. Our work therefore can be applied to privacy-preserving anti-money laundering detection.

FIPS 204 Table 1 gives the expected number of iterations of the ML-DSA signing loop (ML-DSA.Sign_internal, Algorithm 7), citing CRYSTALS-Dilithium Equation (5). That equation covers only the validity checks on line 23 ($\lVert z \rVert_\infty$ and $\lVert r_0 \rVert_\infty$) and omits the two encoding-correctness checks on line 28 ($\lVert c \cdot t_0 \rVert_\infty$ and the hint weight), a scoping distinction the Dilithium specification states explicitly and FIPS 204 does not reproduce. We give a complete accounting of all four conditions. The $z$ check on line 23 is computed exactly by counting; the $c \cdot t_0$ term follows a closed-form Irwin-Hall tail, restating a peer-reviewed result by Yan, Luo and Wang; the hint-weight term's per-coefficient probability, conditioned on line 23 having passed, does have a closed form, but the tail of the sum over $256k$ such coefficients does not, since their probabilities are unequal, random, and correlated with each other, so we give the conditioned per-coefficient probability in closed form and estimate its tail by Monte Carlo. The corrected expected iteration counts are 4.36, 5.14 and 3.91 for ML-DSA-44, -65 and -87, matching a real end-to-end measurement to within 0.14% and already reflected in NIST's own errata to FIPS 204.

Stateful hash-based signatures fail badly when a one-time key signs twice, as happens when the signer's state is lost or rolled back. We study what a second signature reveals in a broad class of hash-based schemes whose key is a tree of hash chains. In this class, a message selects a set of tree nodes that covers every leaf exactly once, together with a position on the chain of each selected node, and the signature reveals the chain values at those positions. For the whole class, we prove that the values derivable from several signatures are exactly the union of those derivable from each signature alone, and we bound forgery after $b$ signatures in the classical random-oracle model by a combinatorial coverage exponent $\lambda_b$, also when the signer grinds a counter. We then present CUTS (Chained Uniform-sum Tree Signatures), a member of the class built on one binary tree, in which both the selected nodes and their chain positions depend on the message, with the positions summing to a fixed value $S$. Signature length and verification cost are fixed by the parameters and do not depend on the tree height. For CUTS, we compute the two-use coverage exactly as one coefficient of a polynomial and derive deterministic lower bounds on $\lambda_2$; one parameter set with 1 424-byte signatures has $\lambda_2\ge128.6$. A counter variant, CUTS+C, trades a short counter and extra signing work for a proven grinding gain of $g$ bits in the coverage term.

We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following. (1) There is an absolute constant $c_{\mathrm{bh}}<1/2$ such that, for $k\ge c_{\mathrm{bh}}n$, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was $0.668n$. (2) For every fixed $0<\delta<1/2$ and $k\ge(1/2+\delta)n$, Shamir sharing is resilient to $\left\lfloor\frac{\delta}{24}\log_2 n\right\rfloor$ bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on $\delta$. (3) For every fixed threshold rate $c>0$ and $k\ge cn$, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to $\eta_c\log_2 p$ bits, for a constant $\eta_c>0$. All three results follow from one analytic framework, which we develop for generalized Reed--Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron--Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.

Zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are increasingly used within larger cryptographic protocols, making security under composition essential. Generic compilation to Universal Composability (UC) requires straight-line, black-box extraction while preserving succinctness and controlling prover cost. We introduce verifiable reconstructible straightline codes (VRSCs), a primitive that separates public hiding, transcript-based reconstruction, binding, and proof non-rerandomizability. This abstraction exposes a missing security requirement in the witness-succinct UC compiler of Ganesh et al. (EUROCRYPT 2023). Permuting previously revealed evaluation openings produces a fresh accepting proof with non-negligible probability without violating non-extrapolation, invalidating the claimed simulation argument. Proof non-rerandomizability captures this attack at the certificate level. Our construction prevents transfers between repetitions through verifier-enforced disjoint evaluation domains. We formulate a generic UC lifting theorem in terms of VRSCs and give a pairing-based instantiation using a Fischlin-style search over authenticated codeword symbols. Structured Reed--Solomon encoding and jointly computed KZG openings reduce certificate-generation work from quadratic to \(O_{\lambda}(n\log n)\), where \(n\) is the witness size. Only a linear-time encoding check enters the underlying SNARK circuit. To our knowledge, this is the first generic UC lifting compiler that simultaneously achieves quasi-linear prover overhead and constant additional proof size and verification work with respect to the witness size.

The results in this paper establish the genericity of some properties of the ideals and varieties generated by UOV public keys, in particular the equidimensionality of the UOV varieties and the radicality of public key ideals. These genericity results justify the various regularity assumptions that are made on polynomial systems of equations arising in the cryptanalysis of UOV and its variants. We also provide examples in the recent literature showing how genericity questions arise in crypt- analysis and why genericity should be taken into consideration when de- signing cryptographic schemes. Lastly, we perform a retrospective study of various cryptographic schemes through the viewangle of genericity. We identify several cases in which non-genericity led to the cryptanaly- sis of the scheme, but also provide a counter-example of a scheme whose non-genericity does not seem easy to exploit.

Almost perfect nonlinear (APN) functions provide optimal resistance to differential cryptanalysis in characteristic two, and constructing new infinite families inequivalent to the known ones remains an important problem in the study of cryptographic functions. We introduce extended biprojective functions, obtained by augmenting biprojective polynomials with truncated trace terms, and establish a new infinite family of quadratic APN functions. To investigate these constructions, we develop an efficient APN test based on the ranks of binary matrices and employ it in exhaustive searches in dimensions up to 28. Using ortho-derivative differential spectra to distinguish CCZ-equivalence classes, we identify APN functions inequivalent to known families and uncover a systematic pattern across dimensions, leading to conjectures on further infinite families of quadratic APN functions.

In secure multiparty computation (MPC), modulus conversion turns a sharing of a value $x$ modulo $q$ into a sharing of the same value modulo $t$, without leaking anything about $x$. One important application of modulus conversion is in threshold decryption for lattice-based cryptosystems, where a sharing modulo the ciphertext modulus has to be moved to the plaintext modulus before it can be opened. The most efficient protocols so far (Damgård et al., Asiacrypt 2026) are in the preprocessing model, assume $x$ is bounded away from $q$ by a constant factor and take two rounds for a prime target modulus, three rounds for arbitrary moduli, and one round when all moduli are 2-powers. We improve upon this by constructing three new modulus conversion protocols in the preprocessing model: - Our first conversion protocol takes a single round for arbitrary moduli, consisting of just one opening. - Our second conversion protocol is a variant of the first protocol, where in the preprocessing most of the secure multiplications are replaced by private inputs, which are checked in a batch using fully linear interactive oracle proofs (FLIOPs). This makes the preprocessing cheaper (amortized over a batch of conversions) when the number $N$ of parties is small. This comes at the cost of making the bound on $x$ a factor $N$ stronger. - Our third conversion protocol avoids the bound on $x$ altogether but takes two rounds. All our protocols are stated in the arithmetic black box (ABB) model, so they can run on top of a wide variety of MPC protocols, inheriting their corruption threshold and security model. To allow the third conversion protocol to run in two rounds, we construct the first one-round comparison protocol in the ABB model for comparing a bitwise shared $n$-bit value against a public threshold with polynomial-size preprocessing. Concretely, the preprocessing size is $\mathcal O(n^2)$ in general, and $\mathcal O(n^2 / \log n)$ in our case where the secret value is fixed in preprocessing. We also construct constant-round ABB protocols without preprocessing for computing symmetric functions and comparisons of values shared bitwise modulo powers of arbitrary primes (e.g., $2^k$), at communication quasi-linear in the number of input bits. Previously, this required either a sufficiently large prime or polynomially larger communication. Finally, we give an impossibility result for non-interactive modulus conversion, demonstrating that a single round is optimal: unless $t$ divides $q$, every non-interactive conversion for inputs $x < q/\beta$ is incorrect with probability at least $\approx 1/(4\beta)$.

Threshold implementations (TIs) are now an established class of side-channel countermeasures. Their underlying idea is simple and compelling: under mild, practical assumptions, they provide protection against glitches and allow composability. Yet our understanding of one-stage TIs with a minimal number of shares remains limited, both for cryptographically relevant families—particularly power functions—and for concrete small functions. In particular, until now, except for Feistel-constructions, no optimal TI had been found for families of mathematically well-structured and cryptographically non-trivial functions, especially power functions. In small dimensions, many functions - particularly cryptographically interesting ones — were not known to admit an optimal TI. This was especially true for the 4-bit S-boxes frequently used in practical lightweight ciphers. Optimal refers to share-optimal, direct one-stage, uniform, first-order TI. Here, we introduce new families of TIs, including the first infinite families of cryptographically nontrivial power permutations. Moreover, every four-bit permutation of algebraic degree t admits a direct, uniform TI with t+1 shares and no fresh randomness. Those results prove several previous conjectures and claims wrong. Since such permutations are widely used in symmetric ciphers, our constructions offer new implementation options.

We recover the long-term key of a first-order masked Kyber768 implementation on an ARM Cortex-M4 from about 2200 decapsulation power traces, using only authentic ciphertexts that pass ciphertext-validity checks. The secret is freshly shared before every decapsulation, and the attack combines weak second-order leakage from both shares. Under the evaluated leakage model, even exact Hamming weights of both shares provide about 97% less mutual information about a decryption-noise coefficient than the exact Hamming weight of the unmasked coefficient. A profiled neural network estimates Hamming-weight distributions for the two arithmetic shares of each noisy message coefficient. We combine these distributions into likelihoods on the decryption noise, which is a known affine function of the secret and the public-key error. A belief-propagation (BP) solver accumulates these likelihoods across traces, preserving their non-Gaussian shapes while approximating the aggregate interference from other key coordinates by a Gaussian. An Onsager correction from approximate message passing corrects for feedback between each factor and the current beliefs. The solver recovers all 1536 secret and error coefficients without lattice reduction. At the evaluated trace budgets, least squares performs no better than the all-zero estimate, and a greedy inequality solver fails even with exact Hamming weights. The evaluated primal-lattice cascade does not reduce the trace requirement: below BP's recovery threshold, its output remains too diffuse to enable practical lattice recovery. At 2000 traces, BP-derived hints lower the estimated BKZ block size from 624 to 505, leaving the lattice attack impractical.

Modern electronic systems are becoming increas- ingly complex and must satisfy demanding performance, power, and area (PPA) constraints. Consider for instance artificial intelligence chips, aiming at datacenters running LLMs or at automotive perception, which manipulate massive data streams. Beyond performance considerations, these systems must also provide increasingly strong security and dependability guaran- tees. Indeed, when electronic systems are based on chiplets, for instance, the supply chain gets longer and therefore brings a larger number of threats. Also, those systems are very versatile, in that they can run varied multi-tenant applications. Therefore, defining what security features are required in this context with numerous stakes is not trivial. Existing scholarly research is very relevant when the security problem is well defined. The resulting scientific papers accord- ingly dig very deep: this modus operandi has proved productive in exploring new problems, and actually allowed to come up with innovative solutions. For instance, in the field of side-channel attacks, varied mitigations alongside with metrics to evaluate them have been devised. Increasing sophistication resulted from this research, as external considerations have been injected into the problem (typically, aspects such as attack order, impact of combinatorial glitches, etc.). Therefore, we face today the question of selecting the most suitable technology amongst the proliferation of state-of-the-art techniques. In addition, in complex systems, we encounter another prob- lem, namely that of defining the security problem(s). A fruitful approach in this respect is a risk based approach. Specifically, the application of a risk-oriented methodology allows to reason on the security rationale. It proceeds as follows. First, the system missions are listed. Then for each of them, the necessary assets are deduced. A threat analysis allows to identify how assets are threatened, and eventually, security requirements can be enunciated. At this stage, the task of matching relevant countermeasures becomes straightforward. This paper illustrates the methodology by deriving security specifications for datacenter and automotive chiplets. The considered missions are (secure) provisioning, trimming, debugging, booting, and remote attestation.

For public-key encryption with keyword search (PEKS), chosen-ciphertext attack (CCA) security has been studied in settings where an adversary is allowed to access the test oracle. Notably, the CHK transformation (Canetti, Halevi, and Katz, EUROCRYPT 2004) does not yield CCA-secure PEKS. To address this limitation, Abdalla, Bellare, and Neven (TCC 2010/JoC 2018) proposed a generic construction of CCA-secure PEKS from CCA-secure anonymous and weakly robust identity-based encryption. However, CCA security alone is insufficient to resist keyword-guessing attacks (KGAs) arising from trapdoor leakage in PEKS. To mitigate KGAs, public-key authenticated encryption with keyword search (PAEKS) has been studied. In particular, Li and Boyen (IACR CiC 2024) proposed a generic construction of PAEKS. In this paper, we propose a generic transformation that converts a PAEKS scheme into a CCTA-secure one, where CCTA denotes security against chosen-ciphertext and trapdoor attacks. Our transformation can be viewed as a variant of the CHK transformation. The key observation is that, unlike in PEKS, the receiver in PAEKS identifies and specifies the sender when generating a trapdoor, enabling keywords to be used as tags. The transformation directly upgrades PAEKS instantiations obtained via the Li-Boyen generic construction under various assumptions to CCTA-secure schemes. As a result, we obtain the first fully CCTA-secure PAEKS schemes from both pairings and lattices. As an additional benefit, the transformation improves search efficiency. By leveraging verification keys embedded in ciphertexts and trapdoors, sender-receiver matching can be performed without cryptographic computation, for example, by using hash tables. Consequently, for a trapdoor associated with a particular sender, the search complexity measured in cryptographic operations becomes independent of the number of senders and is essentially the same as that of PEKS. Although improving efficiency is not the primary goal of the transformation, this benefit is of independent interest.

Succinct Non-Interactive Arguments of Knowledge (SNARKs) for NP allow a prover to prove knowledge of a witness of an NP relation to a verifier with a short proof. The primary goal of a (static) SNARK is to make verification cheap: the proof should be short, and the verifier's work should be minimal. However, recent work has also focused on making SNARKs more prover-efficient: cheap verification should ideally not come at the cost of large prover overhead. One avenue for achieving prover efficiency is via Dynamic SNARKs, which allow a prover to efficiently update the proof when the witness is updated. For example, one may use a SNARK to issue a proof of a query being performed correctly on a database, and then issue a new proof of the query once the database is updated. If these updates are small compared to the size of the witness (only a single entry of a large database is updated), then the prover should ideally be able to use the old proof to generate a new proof in time proportional to the distance between the old and the new witness. While some constructions of dynamic SNARKs for NP have been recently proposed by Wang et al. [Eurocrypt 2026] and Zhang et al. [Eurocrypt 2026], they have many limitations, such as lack of post-quantum security, dependence on a setup by a trusted third-party, and poor asymptotic and concrete efficiency. In this work, we present a compiler for constructing a dynamic SNARK for Plonkish constraints (which capture arbitrary NP computations) by using a static SNARK for NP and a vector commitment scheme as black boxes. When instantiated with a state-of-the-art hash-based SNARK and Merkle trees, the compiler yields a dynamic SNARK that is post-quantum secure in the QROM, has a transparent setup, and achieves $O(n)$ initial prover time and $O(k \log^2 n)$ update prover time, with succinct proofs and verification, where $k$ is the Hamming distance between the old and new instance-witness pairs. Our Ligerito-based implementation achieves cumulative prover speedups of $147\times$ and $11.7\times$ over a static HyperPlonk baseline for 10,000 successive one-gate updates and 1,000 successive 128-gate updates, respectively, on a $2^{23}$-gate circuit, including the full dynamic initialization cost.

Building on the wedge-attack framework of Ding, Li, and Tao , we reformulate the Schur-Macaulay matrix approach of Merz and Ran in polynomial terms and develop a unified treatment using truncated polynomial algebras over fields of positive characteristic $p$. By working in $p$-truncated polynomial algebras, our formulation applies to the Unbalanced Oil and Vinegar (UOV) problem over arbitrary finite fields. Divided powers and transfer relations yield additional public relations within the ideal-inclusion framework, leading to quotient-dimension criteria for recovering graded components of the hidden oil-space ideal. As an application, we analyze the third-round QR-UOV parameter sets and obtain lower estimates of attack complexity for some of them.

The succinct LWE (CRYPTO~'24) and decomposed LWE (CRYPTO~'25) assumptions are two recently introduced variants of the celebrated LWE problem, known to imply the existence of numerous new cryptographic primitives. Yet, the hardness of these problems has thus far remained poorly understood, since there is no known reduction to LWE. In this work, we study these lattice problems from a foundational perspective. Our main technical contribution is a worst-case-to-average-case reduction from \emph{superlattice SVP} (SuperSVP) to succinct SIS. We introduce SuperSVP as a variant of SVP for general lattices in which the solver is additionally given, as a hint, a short basis for a related superlattice. Combining this result with our quantum reduction from succinct SIS to succinct LWE, which is an analog of Regev's SIS-to-LWE reduction, and with our search-to-decision reduction establishes worst-case hardness for succinct LWE. Finally, we show that succinct and decomposed LWE are equivalent, extending this conclusion to decomposed LWE. Overall, our work places succinct and decomposed LWE on firmer theoretical ground and, as a direct consequence, establishes the \emph{worst-case} hardness of a variety of cryptographic primitives, known to be implied by these assumptions.

ML-KEM is a lattice-based IND-CCA secure key encapsulation mechanism (KEM) standardized by NIST in FIPS 203. ML-KEM achieves chosen-ciphertext security by applying the Fujisaki-Okamoto (FO) transformation to an IND-CPA secure public key encryption (PKE) scheme. The FO transformation uses de-randomization and re-encryption to ensure ciphertext non-malleability, but because ML-KEM's underlying PKE encryption subroutine is slower than the decryption subroutine, ML-KEM's decapsulation performance is dominated by re-encryption. In this paper, we revisit the ``encrypt-then-MAC'' paradigm as a generic KEM transformation: the PKE ciphertext is authenticated by a message authentication code (MAC) whose key is derived from the PKE plaintext. We prove that the transformation achieves IND-CCA security in the random oracle model when the underlying PKE is one-way under plaintext-checking attack (OW-PCA), and we introduce a fine-grained security notion, one-wayness under $q$-bounded plaintext-checking attack (OW-$q$PCA), under which the transformation achieves IND-$q$CCA security. In contrast to the tag-based IND-1CCA transformations of Huguenin-Dumittan and Vaudenay (Eurocrypt 2022), whose tag is a random-oracle hash of the plaintext and the entire ciphertext, our transformation applies the random oracle only to the short PKE plaintext, while the long ciphertext is processed by a standard-model MAC that needs only to be one-time existentially unforgeable. We present ML-KEM-EtM, an IND-$q$CCA secure KEM derived from applying the encrypt-then-MAC transformation to the PKE subroutines of ML-KEM, and McElieceEtM, an instantiation with Classic McEliece that achieves full IND-CCA security under the conjectured OW-PCA security of its Niederreiter PKE. We implement ML-KEM-EtM with a wide selection of MACs including Poly1305, GMAC, CMAC, and KMAC256. At the cost of minimal increase in encapsulation CPU cycle count and ciphertext size, ML-KEM-EtM achieves a substantial reduction of the decapsulation CPU cycle count.

In September 2026, an AI produced a Lean proof of Fermat's Last Theorem in eleven days, and AI provers have started on cryptography. Within a few years, an AI may hand you a machine-checked proof that Signal is secure. You won't need to read it, because Lean will have checked every step. What Lean can't check is whether the theorem says what you think it says. That depends on its definitions, which the AI will also have written at length for that one proof. This already happens. A Lean library's security theorem for Schnorr signatures passed the checker, yet as written it held for every adversary and so promised nothing. When proofs are cheap, the scarce resource is a person who can read what was proved. I argue that we should build high-level cryptographic languages for that person. A protocol's owners should write its model themselves, short enough for one or two people to read. Every claim the language makes should rest on a checked theorem. And definitions of protocol goals such as forward secrecy should be built in: a small set, versioned and agreed in public the way we agree on AES, so that a property's name means the same thing in every report. Today it may not: on a one-page Verifpal model, two of five verdicts would flip under other standard definitions, with neither answer wrong. Agreeing on definitions will take years of public argument that better provers can't shorten, so we should start now.

Fault attacks exploit transient hardware faults to bypass software-level security checks in embedded processors. Processor-level redundancy can detect such faults, but duplicating the whole processor is costly for resource-constrained devices. This paper proposes Staggered Instruction-Fetch Duplication (SIFD), a lightweight processor-level countermeasure based on instruction-fetch redundancy. SIFD fetches each instruction twice in consecutive cycles, while fetching two different instructions in every fetch cycle. This staggered schedule detects inconsistent fetch results without full processor duplication, compiler support, or cryptographic hardware. We implement SIFD on a custom RV32I processor and evaluate it on an Artix-7 FPGA using clock fault injection (CFI) and electromagnetic fault injection (EMFI). SIFD increases slice utilization by 15.0% and execution time by 16.3%. It reduces the attack success rate from 0.86% to below 0.01% under CFI and from 0.32% to 0.13% under EMFI. It also detects 73.18% of CFI attempts and 11.44% of EMFI attempts. These results indicate that SIFD can convert many fault effects into explicit detections and reduce successful fault-injection outcomes, especially under CFI.

Post-quantum signature schemes require efficient implementations to be viable in practice. MQOM, a third-round candidate in NIST’s additional call for digital signatures, is a promising target for SIMD optimization. This work leverages a transpose-enabled paired-matrix trick to develop a vectorized implementation of MQOM v2.1, corresponding to the Round-2 specification, with reduced wasted SIMD work and memory traffic. We evaluate MQOM v2.1 on Arm NEON, x86 AVX2, and x86 AVX-512, covering key generation, signing, verification, and memory; peak dynamic memory falls by up to 39.43%. We also include supplementary MQOM v3 experiments to assess how the matrix-layout optimization transfers to the Round-3 code.

Privacy-preserving credential systems typically focus on data protection during the presentation phase, overlooking potential privacy threats during issuance. A malicious issuer could use the non-minimal information it obtains to deny issuance selectively. Such a denial, going beyond the eligibility policy, is a form of censorship. In this work, we revisit the security of anonymous credential systems to protect users from malicious issuers during credential issuance. We first highlight the limitations of existing definitions and introduce a security model capturing censorship resistance. Next, we present a round-optimal (i.e., one message per party) construction built from blind signatures and specifically tailored for selective disclosure in the presentation phase. Finally, we present CRACS, an instantiation of our construction, deployable within the European Digital Identity Wallet (EUDIW) framework. CRACS improves on the current reference implementation of the EUDIW, maintaining selective disclosure and yielding unlinkability between presentation and issuance sessions in addition to censorship resistance. Unlike prior work, CRACS confines advanced cryptography to issuance, leaving secure elements, the standardized credential formats, signature schemes, and presentation mechanisms untouched. It can therefore be deployed incrementally alongside current EUDIW implementations, issuer by issuer and user by user, with no change for verifiers.

We introduce Confidential Error-correcting Codes (CECs), a new cryptographic primitive that enables reliable decoding from perturbed codewords while preserving message confidentiality. We formalize this primitive through three security properties: confidentiality, robustness, and soundness. To realize this goal, we develop a general framework for constructing CECs based on a Randomness-Security Separation (RSS) structure, which first encodes a nonce to introduce randomness and then masks the encoded payload with a pseudorandom function. Based on our RSS framework, we instantiate CECs, called Conc-CEC, using concatenated Reed-Muller and Reed-Solomon codes. The resulting Conc-CEC admits provable guarantees for all three properties. Notably, compared to PRCs (CRYPTO'24), another recent cryptographic primitive with error-correcting capability, CECs achieve significantly stronger concrete security guarantees under practical parameter settings. As a primary application of CECs, we further present CECMark, a watermarking scheme for AI-generated images. Our experiments on real-world generative image models show that CECMark consistently outperforms state-of-the-art watermarking methods, including Gaussian Shading (CVPR'24), PRCMark (ICLR'25), and T2SMark (NeurIPS'25). In particular, CECMark achieves higher robustness across all 56 evaluated perturbations and ensures a false positive rate below $10^{-5}$ without introducing side effects. Taken together, our work lays a novel cryptographic foundation for trustworthy watermarking schemes that, for the first time, unify provable security guarantees with strong practical reliability.

Non-interactive batch arguments (BARGs) for $\mathsf{NP}$ enable proving the validity of $k$ $\mathsf{NP}$ statements with a proof whose size is independent of $k$. Threshold BARGs are a natural generalization that enables proving that at least $t$ out of $k$ statements are valid. Unfortunately, existing threshold BARG constructions have the drawback that the size of the common reference string (CRS) grows polynomially with $k$. This is the case even when the statements have a short description (e.g., when considering index languages). Moreover, other than constructions based on indistinguishability obfuscation ($i\mathcal{O}$), prior constructions could only achieve computational soundness. In this work, we construct the first threshold BARG with statistical soundness for an expressive class of trapdoor threshold languages from either circular-secure fully homomorphic encryption or from witness encryption in combination with the learning with errors assumption. Moreover and importantly for our applications, the size of the CRS only scales polylogarithmically with $k$. Next, we combine our threshold BARG with a new technique for sampling pseudorandom permutations in order to build weighted threshold signatures with a statistical unforgeability guarantee. Then, in combination with witness encryption, we obtain a weighted threshold encryption scheme that supports $\lambda$-bit weights. Decryption is entirely non-interactive in our setting. Previously, such a scheme was only known from $i\mathcal{O}$. If we additionally work in the random oracle model, then we obtain a weighted threshold encryption scheme that supports arbitrary weights with silent setup. In the silent setup model, users choose their own public/secret keys and no longer need to rely on a central authority to generate and issue decryption keys.

Doubly-Efficient Lookup Arguments are specialized argument systems that enable succinctly proving the correctness of a batch of $k$ lookup accesses to a large table $\textbf{x}$ in time proportional to $k$ and sublinear in $|\textbf{x}|$. All existing such schemes suffer from one of the following limitations. Either they rely on elliptic-curve-based assumptions for their security, hence they are not secure against quantum adversaries, or are rather impractical, as they rely on algorithms for fast polynomial evaluations (that are mostly of theoretical interest), or operate over fields of small characteristic---making them incompatible with most modern argument systems. In this work, we use tensor codes to construct transparent and post-quantum secure updatable doubly-efficient lookup arguments that asymptotically outperform all existing schemes with the same properties, in terms of prover time and/or preprocessing. By further optimizing this approach for a specific type of two-dimensional tensor codes, we build TenseUp, a concretely efficient lookup argument that, as shown in our experiments, has comparable or even better performance than state-of-the-art non-post-quantum secure prior doubly-efficient lookup arguments. As an independent contribution, we propose a general-purpose compiler for building dynamic SNARKs from any ``static'' SNARK, via judicious use of updatable doubly efficient lookup arguments to store and access witness updates. Applying our compiler with different SNARKs and lookup arguments can lead to different novel results; e.g., combining a hash-based SNARK with our lookup arguments yields the first transparent and post-quantum secure dynamic SNARK.

Zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) are foundational cryptographic primitives enabling privacy-preserving and verifiable computation. However, most existing zkSNARK constructions rely on strong trust assumptions—typically a fully trusted setup—which undermines their applicability in adversarial or decentralized environments. Although transparent zkSNARKs remove this assumption, they typically do not satisfy strong composability guarantees such as Universal Composability (UC). In this work, we present the first framework for constructing UC-secure zkSNARKs under weaker trust assumptions, based on a new primitive called Key-Updatable Polynomial Commitments (KU-pCom). This primitive enables publicly verifiable commitment-key updates, requiring only one honest update rather than a fully trusted setup. Our compiler transforms any Simulation-Extractable zkSNARK into a UC-secure variant by composing it with a KU-pCom scheme. We instantiate our framework in two settings: (1) using the structured, trusted setup of the KZG commitment scheme, and (2) an instantiation based on the lattice-based commitment scheme of Hwang et al. (Crypto 2024). We implement both instantiations and provide an end-to-end benchmark of UC-secure zkSNARKs with succinctness. Compared to prior UC-secure NIZKs that sacrifice succinctness (e.g., Abdolmaleki et al., CSF 2024), our work demonstrates that UC security, succinctness, and practical efficiency can be simultaneously achieved, establishing a new foundation for succinct, composable proof systems under weaker trust assumptions.

We construct public-coin, succinct, zero-knowledge interactive arguments for NP relations decided by time-$T$, space-$S$ random-access machines. Assuming the existence of collision-resistant hash functions, our arguments give a frontier of tradeoffs between prover time and space, and proof size. We follow the streaming PIOP+PCS framework of Block et al. (TCC 2020, CRYPTO 2021), reducing the problem of constructing time- and space-efficient arguments to time- and space-efficient streaming multilinear polynomial commitment schemes (MLPCS). We develop two code-based streaming MLPCS inspired by Brakedown (CRYPTO 2023) and BaseFold (CRYPTO 2024), implementing each scheme when additionally given succinct access to the underlying encoding matrices. We instantiate this framework assuming row-sparse, column-sparse, and Reed-Solomon encoders, then apply a generic PIOP + MLPCS compiler to obtain our (zero-knowledge) time- and space-efficient arguments. Finally, as all our protocols are public-coin, applying Fiat-Shamir yields time- and space-efficient (zk)SNARKs from symmetric-key primitives (i.e., collision-resistant hashing). Our Brakedown-based constructions have \(O(\log T)\) rounds and \(\widetilde O(\sqrt T)\)-size proofs and verification time, with two complementary prover profiles: (i) \(\widetilde O(S)\) space (which is optimal) and \(\widetilde O(T^{3/2})\) time, and (ii) \(\widetilde O(T)\) time (nearly optimal) and \(\widetilde O(S+\sqrt T)\) space. Our BaseFold-based constructions achieve $\mathrm{polylog}(T)$ proof size and verification time with \(O(\log T)\) rounds. We again obtain two complementary prover profiles: (i) an encoder parameterized construction with \(\widetilde O(T+T_{\mathrm{Enc}})\) time and \(\widetilde O(S + S_{\mathrm{Enc}})\) space, where \(T_{\mathrm{Enc}}, S_{\mathrm{Enc}}\) are the running time and space of a streaming log-space encoder for a suitable linear code, and (ii) an unconditional sub-quadratic instantiation \(\widetilde O(T^{3/2})\) time and \(\widetilde O(S+\sqrt T)\) space.

Asynchronous verifiable secret sharing (AVSS) allows a dealer to distribute a secret among parties while preserving privacy and consistent reconstruction, despite Byzantine faults and arbitrary message delays. It is a fundamental building block for Byzantine agreement, distributed key generation, and secure multiparty computation. Packed AVSS protocols share many secrets together to reduce communication per secret. The best known AVSS protocols achieve quadratic communication while sharing linearly many secrets. In particular, Bingo (Abraham et al., CRYPTO 2023) shares a batch of $\Theta(k)$ secrets among $k$ parties using $O(\lambda k^2)$ words of communication, while also achieving adaptive security, but relies on assumptions that are not post-quantum secure. Known post-quantum alternatives have higher worst-case communication for comparable batch sizes or require substantially larger batches to achieve linear amortized communication. We present Lattice Bingo, a lattice-based packed AVSS protocol with quadratic communication and linear packing. For every constant $\epsilon>0$, it shares $\Theta(k)$ secrets among $k\geq(3+\epsilon)f$ parties, tolerates $f$ Byzantine parties, and uses $O(k^2\operatorname{poly}(\lambda))$ words of communication. It additionally achieves one-shot adaptive secrecy: the adversary may adaptively choose its corruption and reconstruction requests based on the public transcript observed so far, but must submit these requests together in a single batch. Our main technical contribution is a commitment scheme for two-dimensional linear codes based on the PowerBASIS assumption. We combine PowerBASIS commitments with the linear code based secret sharing of Applebaum, Nir, and Pinkas, replacing the Reed–Solomon encoding and KZG commitments used in Bingo. Our commitment supports proof interpolation, enabling parties to recover missing shares and their opening proofs. It additionally achieves a notion that we call one-shot simulation hiding. Together, these properties allow us to adapt Bingo’s framework to obtain Lattice Bingo with the same efficiency and one-shot adaptive security.

The Falcon digital signature scheme, under standardization as FN-DSA, requires real-number arithmetic during signing, with its security dependent on numerical precision. Recently, De Almeida Braga et al. (CRYPTO 2026) showed that Falcon-512 can sign in 64.64 fixed-point arithmetic on 64-bit hosts. In this work, we present the first fixed-point FN-DSA signer for microcontrollers, using 32.64 arithmetic in constant-time Cortex-M4 assembly for Falcon-512 and Falcon-1024. Although a straightforward fixed-point implementation is less precise than double precision, our new techniques successfully restore precision. They keep reciprocals, inverse square roots and small constants wide and round once at the consumer. We evaluate them with known techniques on both arithmetics and both degrees. Our signer needs around $45\%$ fewer cycles than double-precision emulation for Falcon-512 Falcon-1024, and its measured precision supports $2^{99.7}$ $2^{96.7}$ queries per key, against $2^{61.5}$ $2^{58.7}$ for double precision and the target of $2^{64}$. Our $12$-byte words raise signing RAM from $59n$ to $83n$ bytes. We also show which implementation choices lift double-precision c-fn-dsa above $2^{64}$ while making it faster. We derive key generation bounds for Falcon-1024, accepting $72.3\%$ of keys where the Falcon-512 values accept $8.5\%$, and provide recommendations for the fixed-point FN-DSA that NIST plans.

Recently, the Institute of Commercial Cryptography Standards (ICCS) launched the Next Generation Commercial Cryptographic Algorithm Program (NGCC), which includes a standardization process for cryptographic hash functions. In this note, we analyze the mode of operation of Duet, one of the hash-function candidates. Duet is a permutation-based hash function directly inspired by the Alternating Sponge (ASP). Both constructions use two permutations on $b=r+c$ bits, split into an outer part of $r$ bits and an inner part of $c$ bits. We first present a distinguisher against ASP requiring $\mathcal{O}(2^r)$ permutation queries, which contradicts the claimed indifferentiability bound in a non-trivial parameter regime. We then introduce a distinguisher and a state-recovery attack against Duet. Both attacks require only a constant number of $h$-bit output blocks, with $h\leq c$, and $\mathcal{O}(2^{r+c-h})$ permutation queries. These attacks do not affect the claimed collision or preimage resistance, but they distinguish Duet's multi-block output from random, with consequences if Duet is used as a XOF or a KDF; state recovery also enables length extension.

We prove expansion properties of superspecial isogeny graphs in dimension $g \geq 2$, including arbitrary level structure. In particular, we provide explicit bounds for the spectral gap, and a fine characterization of obstructions created by level structures (disconnectedness and periodicity). Without the level structure (the only case which was previously studied), our bounds dramatically improve the state of the art. These isogenies in dimension greater than one have become increasingly important in isogeny-based cryptography, and previous works have already conjectured consequences of their expansion properties. We present several applications of our result: we transform conjectural predecessors into rigorous algorithms, and we give the first algorithm for computing endomorphism rings of superspecial principally polarized abelian varieties in arbitrary dimension, with complexity $\tilde O(p^{g-1})$.

At CRYPTO 2016, Cogliati and Seurin proposed EWCDM as a nonce-based MAC construction making two block cipher calls and one almost-XOR-universal (AXU) hash evaluation and achieving beyond-birthday-bound (BBB) security. They noticed that a simplified variant of EWCDM named Encrypted Wegman--Carter (EWC) admits a birthday distinguishing attack. Later, at CRYPTO 2017, Mennink and Neves proposed EWCDMD, the dual of EWCDM, as a new candidate BBB-secure MAC, but at EUROCRYPT 2020 Nandi proposed a birthday distinguishing attack against EWCDMD. However, the distinguishing attacks did not yield forgeries, and whether EWC and EWCDMD have BBB unforgeability (or MAC security) remains open. We prove beyond-birthday unforgeability for EWC and EWCDMD and answer this long-standing open problem positively. Using an $n$-bit block cipher and an $O(2^{-n})$-AXU hash family, we prove that both constructions are secure up to $2^{5n/6}$ MAC queries and nearly $2^n$ verification queries, in the nonce-respecting setting. To bypass the birthday distinguishing attacks, our proofs directly analyze forgery events using auxiliary experiments indexed by hash values and messages. For EWC, we additionally employ conditional permutation analysis and collision multiplicity bounds with KL divergence, whereas for EWCDMD we use Hellinger distance and Fourier analysis.

The isogeny graphs of superspecial abelian surfaces with maximal real multiplication were first studied by Charles, Goren, and Lauter in 2009, when they constructed the RM-CGL hash function on these graphs and proved that they are Ramanujan. As a consequence, these graphs enjoy optimal expansion properties, which are either absent or difficult to establish in other higher-dimensional isogeny graphs. In this paper, we take a closer look at these graphs from a cryptographic perspective, and attempt to demonstrate that they are the natural generalization of the supersingular $\ell$-isogeny graph to dimension two. To this end, we tackle two algorithmic problems: We design and implement the RM-KLPT algorithm to solve the algebraic pathfinding problem in these isogeny graphs by solving a norm equation in ideals of a quaternion algebra over a real quadratic field. Further, we revisit the RM-CGL hash function, provide a proof-of-concept implementation, and showcase that knowledge of the initial surface's algebraic description leads to a second-preimage attack on the hash function through our RM-KLPT algorithm. RM-KLPT resembles the one-dimensional KLPT algorithm much more closely than KLPT$^2$ does. This is due to the existence of a higher-dimensional analogue of the Deuring correspondence in the RM setting, which yields significantly shorter paths ($\sim p^{3}$) compared to KLPT$^2$. Finally, we conclude by discussing potential cryptographic constructions that may be built from RM-KLPT.

We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{\kappa+o(1)}$, for any fixed $\kappa>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = \Omega(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+\omega(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/\sigma)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $\sigma$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $\sigma/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $\sigma$, and $q$), or had complexity that scaled polynomially with either $\sigma$ or the largest prime factor of $q$.

Many hash-based proof systems check that committed words are close to Reed–Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few exceptional challenges. Such gaps are known above the Johnson threshold, about $\sqrt\rho$ for rate $\rho$, and extending them below it would shrink proofs. Recent work does so in large characteristic, but not over binary fields, where some of the fastest proof systems run. We show that beyond-Johnson proximity gaps fail over binary fields. Our first construction applies to any additive domain (a binary linear subspace) filling a constant fraction of a containing binary field. Over a suitable extension challenge field and at rate $1/4$, it gives two words that can simultaneously match codewords on at most $25\%$ of the positions, while their combinations approach the $50\%$ Johnson threshold for superpolynomially many challenges. This rules out any $\mathrm{poly}(N)/|\mathbb F|$ bound on the exceptional probability below Johnson. On Binius64's domain (length $2^{27}$, $128$-bit challenges), the combination reaches $49.4\%$ agreement with probability above $2^{-30}$. The construction also rules out polynomial-size decoding lists below Johnson: one word agrees with superpolynomially many codewords at agreement approaching $50\%$, whereas earlier superpolynomial lists needed the rate, or the agreement–rate gap, to vanish. Our second and third constructions cover every additive domain, including the sparse domains used by LeanVM and Flock. At rate $1/16$, the second gives $(N-1)(N-2)/6$ exceptional challenges at the Johnson threshold itself, when the domain lies in a proper subfield of the challenge field. For domains larger than $2^{20}$, this rules out even $90$ bits of soundness from a single beyond-Johnson proximity-gap check over a $128$-bit challenge field. The third construction trades agreement for larger exception counts: at rate $1/2$ and length $2^{22}$, its combinations reach $53.125\%$ agreement from common agreement $50\%$, with probability at least $2^{-20}$ over a $192$-bit challenge field. Finally, at every fixed rate, some constant agreement above the rate makes every challenge exceptional, over $\mathrm{poly}(N)$-size challenge fields. All of our results are formally verified in Lean.

We describe the design, implementation, and experimental evaluation of Magnetar, a transparent proof system for RV64I program executions (i.e., a zkVM). Magnetar is the first zkVM to simultaneously satisfy the following three properties: 1. General-purpose proving. Magnetar proves programs compiled to the general-purpose RV64I ISA. An implementation of the Ethereum Virtual Machine (EVM) written in Rust or Go can therefore run inside Magnetar, yielding a zkEVM for proving executions of existing EVM smart contracts. 2. Hash-based, post-quantum security. Magnetar’s cryptographic security is rooted in standard hash functions (e.g., SHA-256 or SHA-3). 3. Efficient recursion. Magnetar’s verification work is dominated by evaluating standard hash functions. Magnetar’s proof engine, BinarySpartan, is well-suited for such bit-oriented computations, so verifying a proof is itself an efficient proving workload. Unlike prior general-purpose zkVMs, Magnetar does not rely on circuit-friendly algebraic hash functions such as Poseidon or Poseidon2, elliptic-curve or lattice assumptions, or a conjectured Reed–Solomon proximity gap. Even prior zkVMs commonly described as hash-based rely on elliptic-curve or lattice assumptions in their core proving machinery, provide only about 100 bits of security, or rest on conjectured soundness; some do more than one of these. Finally, we implement Magnetar in Rust and experimentally evaluate it. We find that, at 120 bits of provable security and with 12 performance cores on an M4 Max MacBook Pro, Magnetar proves 2^{22}-cycle executions at 7.2–8.7 million cycles per second, with proofs of about 600 KiB that verify in 11–13 ms. Across 15 application workloads, Magnetar’s proving throughput is 24–66× that of SP1 Hypercube, a hash-and-more-based zkVM; 12–37× that of Jolt-Dory, a curve-based zkVM; and 6–20× that of Jolt-Akita, a lattice-based zkVM, with geometric-mean speedups of about 39×, 18×, and 9.6×, respectively. An optimized Magnetar proves 222-cycle executions at 9.5–12.8 million cycles per second, which increases each geometric-mean speedup by about 1.3×. Magnetar’s proofs are about 4.6× smaller than SP1 Hypercube’s; Jolt’s proofs are under 100 KiB, but they rely on elliptic-curve or lattice assumptions.

Verifiable Computation on Encrypted Data (vCOED) enables clients to outsource computation while providing both privacy and integrity. A promising vCOED paradigm is blind proofs, which use homomorphic encryption (HE) to evaluate verifiable computation (VC) proofs on encrypted data. Despite their efficiency, blind proofs do not provide strong client privacy: a malicious server can exploit reaction attacks to learn information about the client's inputs, intermediate values or final outputs. Our work addresses this limitation by introducing Homomorphic Encryption over Random Encodings (HERE). We formalize a new security notion, indistinguishability under chosen-plaintext attacks in the presence of an equality oracle over encodings (IND-CPA-E). We prove that combining IND-CPA-E-secure HERE schemes with blind proofs that verify computation over the encodings yields vCOED protocols with strong client privacy. We then instantiate a HERE scheme for functions of bounded degree $d$, using Shamir secret sharing at $(d+1)$ evaluation points under $(d+1)$ distinct HE keys. Finally, we demonstrate the concrete efficiency of our approach through an application to matrix-vector multiplication (MVM), a linear computation corresponding to $d=1$. The proof overhead (i.e. the ratio of the vCOED prover runtime to the homomorphic MVM runtime) in our combined vCOED protocol is as low as $2\times$, as demonstrated in our prototype implementation.

We present conceptually simple and practically efficient constructions of a verifiable random function (VRF) that fulfills strong notions of unbiasability recently introduced by Giunta and Stewart (Eurocrypt 2024). Unbiasability is a crucial property for many applications of VRFs such as leader election in proof-of-stake blockchains. The only previous constructions provide heuristic security in the random oracle model or rely on the decisional Diffie–Hellman assumption with preprocessing which incurs significant overhead. In contrast, our compiler turns any VRF into an unbiasable VRF in the standard model (without any setup) using only symmetric-key primitives; and thus only with negligible computational overhead. Underlying our approach, we provide a generic black-box reduction for unbiasability of VRFs that incurs subexponential loss. Additionally, under a mild (verifiable) requirement on the underlying VRF we also show a novel non-black-box reduction that incurs only polynomial loss. This non-black-box technique allows us to replace the folklore "VUF-then-Hash" heuristic with a provably secure "Hash-then-VRF" construction at virtually no cost. In particular, if the underlying VRF hashes its input, our transformation requires only a single evaluation of a hardcore function, e.g. parity of the input (plus a PRF evaluation for full security).

Ducas, Engelberts and Loyer (CRYPTO 2025) turned Wagner's generalized birthday algorithm into a provable subexponential-time Gaussian sampler for unstructured short integer solutions. Recent preprints of Han, Gao and Hu, and of Chen, Jiang, Wang and Zhang, obtain low-sample decision learning-with-errors algorithms from this framework. We extend it to module matrices over power-of-two cyclotomic rings, for every residue degree of the prime modulus. For fixed module ranks $k,\ell\ge1$, let $n=kd$, $m=(k+\ell)d$, and suppose $\ln(q/\sqrt n)=(\ln n)^{b+o(1)}$. For every fixed $b,c,\xi>0$, we solve Module-SIS with coefficient infinity-norm bound $q/(\ln n)^c$ in worst-case time and space $2^{(1/(2b)+\xi)n/\ln\ln n}$. For matrix-independent errors satisfying $\|e\|\le\sigma\sqrt m$ with probability $1-o(1)$ and $\ln(2+\sigma)=(\ln n)^{a+o(1)}$, $0\le a<b$, decision and search Module-LWE take $2^{(1/(2(b-a))+\xi)n/\ln\ln n}$. Success is $1-o(1)$ using only the given $k+\ell$ ring samples; error coordinates need not be independent. The structural ingredient is a Chinese-remainder-support uncertainty bound: the loss of randomness of sparse dual labels is compensated by an arithmetic lower bound on their length. Scalar row perturbations give search over the base field, and small integer shears remove a singular-block loss. Projection, the Han--Gao--Hu martingale analysis, and a finite enumeration sampler give a common algorithmic framework. We also prove sample-preserving scalar search-LWE and narrow Module-LWE algorithms. In particular, for polynomial prime $q=n^{\kappa+o(1)}$, $\kappa>1/2$, one ring sample and growing rank suffice for decision and search in time and space $2^{(1/2+\xi)n/\ln\ln n}$ when the sample supplies $(1+o(1))n/\ln\ln n$ scalar responses. Here ``narrow'' restricts both secret and error. Separate heuristic estimates in the model of Ducas, Engelberts and Loyer suggest that Wagner-style attacks do not reach the NIST security targets of ML-KEM and ML-DSA.

Oblivious RAM (ORAM) allows a trusted client to access (encrypted) data stored in untrusted memory, such that the access patterns reveal nothing about the data or the queries. It is well-known that any ORAM scheme must suffer from a logarithmic overhead. More precisely stated, each request must incur $\Omega(\log_B N)$ block transfers on average, where $N$ is the size of the logical memory and $B$ is the block size of the oblivious implementation. Moreover, the same lower bound extends to oblivious Search Trees (ST). For upper bounds, however, we have been long stuck with a $(\log_B N)^2$ curse on two fronts: (1) Log-squared curse for statistically secure ORAMs: although optimality is known for computationally secure ORAMs for $B = \Theta(1)$ or $B \geq \log^{1+\epsilon} N$ (where $\epsilon > 0$ is an arbitrarily small constant), progress has been stagnant when it comes to statistical security. (2) Log-squared curse for oblivious search trees: for search trees, we do not know how to overcome the log-squared curse even when allowing computational assumptions. In this paper, we break this long-standing log-squared curse for both oblivious search trees and statistically secure ORAM on broad parameter regimes: (1) Our first result gives an optimal, statistically secure ORAM with $O(\log_B N)$ cost as long as $B \geq \log^{1+\epsilon} N$. (2) Our second result gives an optimal, statistically secure oblivious search tree with $O(\log_B N)$ cost when $B \geq \log^{2+\epsilon} N$, matching the performance of the best known non-oblivious search trees in this parameter region. Notably, this means that for search trees, we can get obliviousness for free! The assumptions on $B$ required to achieve optimality are standard and mild. They not only coincide with the standard wide cache-line assumption prevalent in the classical algorithms literature, but also align well with the hardware-enclave architectures that employ oblivious algorithms in practice, such as the implementations of Signal and Meta.

Individual cryptography (Dziembowski et al. Crypto'23) and complete knowledge (Kelkar et al. CCS'24) aim at constructing protocols that ensure that some individual party must know a secret value in the clear, and so the computation cannot have been “outsourced” to an MPC computation. Two central primitives are proofs of complete (or individual) knowledge, which enforce that some party actually knows the secret witness, and secret sharing with snitching, which enforces that whenever the secret is reconstructed, some party must learn a certificate of this fact. The instantiations proposed by both papers (Crypto'23 and CCS'24) ensure that to compute a proof or reconstruct the shared secret, a large number of hash function evaluations is necessary. Thus, at least one party must compute many of these “in the clear” (and not via MPC) and from the hash function inputs one can extract the secret (in the random oracle model). In practice, they suggest using Bitcoin mining hardware. Sequential proofs of complete knowledge have recently been proposed, which use proofs of sequential work to enforce that the hashes are performed sequentially. As a consequence, it suffices to require a much smaller number of hashes, and thus such primitives can be implemented on standard hardware. Unfortunately, this approach does not work for primitives like secret sharing, as one would need to efficiently sample the challenge for the sequential computation together with its solution. In this work, we leverage ideas from time-lock puzzles to overcome this issue. We construct secret sharing with snitching and encryption with self-incriminating proofs where reconstruction/decryption is sequential. The security of our scheme relies on a new knowledge assumption, which informally states that whenever parties that hold secret shares of an RSA modulus N=pq jointly compute 2^2^T N for some large T (too large to perform a sequential computation of length T in MPC), then at least one of them must have learned a multiple of N.

Linear correctors reduce the bias of random bits via parity (XOR), but their guarantees are known mostly for independent bits, an assumption violated by many physical entropy sources. We give a general, exact formula for the parity bias of dependent bits from a (hidden, possibly non-homogeneous) Markov chain, as a product of twisted transfer kernels. Under next-bit unpredictability, i.e. conditional bias at most $\beta$, the decay is governed by $\beta$ itself: sharp for a one-bit context, $|\mathrm{bias}|\le\beta^{\lceil n/2\rceil}$, and \emph{near-optimal} for an $m$-bit context, within a factor $3^{1/3}\approx1.44$ of the best possible per-bit rate, which is at least $\beta^{1/(m+1)}$ (attained by a noisy LFSR) and asymptotically equal to it as $\beta\to0$. Against the best previous bound (Zhou and Bruck, ISIT 2011) we \emph{correct the exponent} and \emph{tighten the bound on $n$ bits by a factor of about $2^{\lfloor(n-1)/2\rfloor}/\beta$}, with a matching construction. The decay is non-monotone, so a corrector should be certified at every operating length, or via the envelope $\beta^{\lceil n/2\rceil}$. Finally, bounded memory is necessary: if unpredictability is imposed on the full history, XOR-ing does not reduce the bias at all.

Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. Threshold implementation (TI), introduced by Nikova et al. in 2006, was proposed to resist differential power analysis side-channel attack on hardware implementations of block ciphers and eliminate information leakage due to glitches. For a function of algebraic degree $t\ge 2$, a TI requires at least $t+1$ shares. However, achieving this bound without fresh randomness is challenging, and we refer to such TIs as optimal. While a universal construction using $t+2$ shares is available, attaining the $t+1$ lower bound depends on the target permutation. In this paper, we present four constructions for optimal TIs of bijective S-boxes. We first demonstrate how adjoining identity coordinate functions enables optimal TIs, and then prove that $\mathcal{Q}_{30}^5$ admits optimal TIs. Second, we derive a matrix criterion for a class of quadratic permutations with optimal TIs, which covers all known examples, and can yield new $6$-bit quadratic classes with optimal TIs. Third, we introduce a weighted interpolation construction, which yields power permutations admitting optimal TIs, thereby providing counterexamples to the conjecture by Piccione et al. in 2023 that nonlinear power permutations cannot meet the $t+1$ lower bound. Finally, we present a derivative-uniform framework. Although this construction is not algebraic-degree-preserving for TIs and comes at a high cost of implementation, it is of significant theoretical interest and enables us to prove that every $4$-bit cubic permutation admits optimal TIs.

Motivated by recent constructions and barriers in secret sharing, we study multislice functions. These functions, parametrized by a width parameter $w$, take the value 0 on inputs of Hamming weight below a base value $k$, 1 on inputs of weight above $k+w$, and are monotone in between. We first investigate formulas over multislice gates, which generalize the formulas over slices model (Applebaum et al., TOCT 2026). We prove that, although multislices compute complicated functions, they do not help in computing the worst-case function when $w\ll n$; that is, there is an explicit monotone function such that for every $w$, every formula over multislice gates of width $w$ that computes it, regardless of its depth and gate fan-in, has size $2^{\Omega\left(n/((w+1)\log^2 n)\right)}$. Our lower bound is based on a randomized Karchmer-Wigderson protocol for multislices that can be amortized across the formula. As a complementary result, we show how to realize multislices using slice gates, i.e., multislice gates of width 0; the construction uses a simple peeling recursion. Consequently, every width-$w$ multislice on $n$ variables has a formula over slice gates of size at most $2n^{w+1}$ and depth $(w+1)$. The same construction allows to compute multislices with small monotone real formulas and circuits, two models introduced by Pudl\'ak (J. Symb. Log., 1997) in the context of proof complexity. This result also has an application to secret sharing: it yields, for sufficiently long secrets, multilinear secret-sharing schemes for width-$w$ multislices with maximal information ratio $n^{O(w+1)}$, which is polynomial for every fixed $w$. In addition, we prove that an explicit access structure requires shares of size $2^{\Omega(n)}$ in every secret-sharing scheme from a family of schemes that captures all currently known constructions for general access structures with share size $2^{cn+o(n)}$, for $c<1$. Our proof goes through an exponential lower bound on the size of formulas over so-called CDS gates and ideal linear gates.

Bleichenbacher's 1998 padding oracle attack against RSA PKCS#1 v1.5 has resurfaced repeatedly over the past decades, especially in TLS. Although modern browsers prefer TLS 1.3, many servers and clients still permit RSA key exchange for backward compatibility, enabling active network attackers to decrypt recorded sessions. Still, practical man-in-the-middle attacks remain challenging. The classical attack narrows the plaintext interval from the top down, spending many queries on secret-independent padding bytes before reaching the PreMasterSecret in the low-order 46 bytes of the RSA plaintext. As a result, prior attacks required multiple vulnerable servers in parallel to avoid connection timeouts. In this paper, we present Reverse-Bleichenbacher, a novel variant of the Bleichenbacher algorithm. In contrast to all previous Bleichenbacher-style algorithms, our algorithm recovers the least significant bytes first and terminates the search as soon as the target secret is recovered. When the secret occupies only a fraction of the plaintext, as with the TLS PreMasterSecret, this significantly reduces the number of required queries. Together with improved trimmers and a coverage-optimized search, this reduces the median number of oracle queries from 11.428 to 1801 against a standards-conforming PKCS#1 v1.5 oracle with 2048-bit keys, with an overall success rate of 84.8 %. Crucially, under realistic single-server conditions (a 2.6 ms median round-trip time we observe to vulnerable hosts and 2 round trips per query) 68.3% of all runs finish within a 30s timeout, compared with none of the prior algorithms. To remain feasible at higher latency, we parallelize independent queries: at 20 ms round-trip time, batching reduces the median end-to-end runtime from 59.3s to 8.3s, at the cost of additional queries. We identify 640 vulnerable domains in the Tranco Top 1 Million, many behind Alibaba Cloud load balancers. We demonstrate end-to-end impact on real software distribution channels: a man-in-the-middle attacker can inject malicious updates and achieve remote code execution on a victim device.

In cryptographic algorithms based on groups in which the discrete logarithm is supposed to be hard, it is frequent to perform polynomial arithmetic in the exponent of group elements. This old technique has become a critical operation in many recent advanced protocols, mostly related to commitments and zero-knowledge proofs, where polynomials of high degrees are involved. Number Theoretic Transform (NTT) techniques in the exponent are often implemented to gain speed. However, they require roots of unity to exist in the field GF(q) where q is the order of the group. In this work, we propose algorithms that preserve the quasi-linear complexity of the Fourier Transforms, even when no root of unity are available. For this, we develop a formalism for the algebraic structure of polynomials with coefficients in a group, that allows us to adapt asymptotically fast polynomial multiplication algorithms to the case of arithmetic in the exponent. In particular, we design an algorithm inspired by the Schönhage-Strassen algorithm, which runs about twice slower than NTT but does not require any arithmetic property on the order of the group. We explain how this can be adapted to batched KZG commitment proofs and the Bayer-Groth verifiable mixnet used in e-voting.

Fully Homomorphic Encryption for RAM programs (RAM-FHE), introduced by Hamlin, Holmgren, Weiss, and Wichs (Crypto 2019), allows a server to evaluate a RAM program on encrypted data at a per-step cost sublinear in the memory size $N$, whereas standard FHE must read the entire memory for every memory access. In a celebrated work, Lin, Mook, and Wichs (STOC 2023) gave the first, and to date the only, construction from a concrete assumption, namely Ring-LWE. In this work, we construct a RAM-FHE scheme from plain LWE that evaluates each step of a RAM program in $o(N/\log N)$ time. While the scheme is barely sublinear, even such a slight saving over the linear cost of standard FHE was not known to be achievable from unstructured, plain LWE. As Lin, Mook, and Wichs did, we build RAM-FHE by extending a Doubly-Efficient Private Information Retrieval (DEPIR) scheme. Since the only DEPIR from plain LWE, due to Lee (Crypto 2026), relies on a Common Reference String (CRS) that is incompatible with the extension, we show how to remove the CRS and obtain a DEPIR from plain LWE in the standard model, which may be of independent interest.

The distinguishing variant $\Delta$LIP of the Lattice Isomorphism Problem underlies the security proofs of a growing family of lattice-based schemes. As the special genus is the strongest efficiently computable invariant of a lattice, such a proof may replace the lattice used by the scheme with a random lattice of the same genus. This raises the question of how hard lattice problems actually are on such random lattices. We answer it, under GRH, with a worst-case to average-case reduction inside any special genus $\mathcal{G}$ of Hermitian lattices of fixed rank $r \geq 2$ over a cyclotomic field $K$ of degree $d$: for each of $\mathrm{(H)SVP}$, $\mathrm{HCVP}$, $(\Delta)\mathrm{BDD}$, $\mathrm{DSP}$ and $\mathrm{DGS}$, solving the problem on a random class of $\mathcal{G}$, drawn from its natural distribution, is as hard as solving it on the worst-case lattice of $\mathcal{G}$, at the cost of a factor $p = \mathrm{poly}(d) \cdot {\det}_{\mathbb{Q}}(\Lambda)^{O_r(1)/d}$ in the approximation factor. The reduction is a random walk on the Kneser $\mathfrak{p}$-neighbour graph of $\mathcal{G}$: neighbours stay close enough to transfer problem instances, while the walk equidistributes quickly, a fact we deduce from spectral bounds for the associated Hecke operators. As an application we give a direct and tight security proof for a minimal LIP-based KEM, resting on two independent assumptions: that the lattice it uses is indistinguishable from a random lattice of its genus, and that $\Delta$BDD is hard on that genus. Unlike existing LIP-based proofs, this requires neither an ad-hoc lattice of the form $q\Lambda \oplus (q+1)\Lambda$, nor the tightness loss caused by the dense sublattice such proofs rely on.

We present KIFA (Kernel-based Integral Fault Analysis), an integral fault attack framework that mines its balanced properties with the kernel-based miner of Hwang et al. in place of Mixed Integer Linear Programming (MILP). The miner handles only small input structures fixed in advance, and a fault model provides exactly such structures. For DEFAULT, we present attacks at fault penetration (FP) $9$ under a random-position nibble fault and FP $10$ under a random-position byte fault, beyond the prior best integral fault attack at FP $8$. They leave a single master-key candidate under the simple key schedule and reduce the key space to $2^{64}$ under the rotating key schedule. For GIFT-128, we present the first integral fault attacks, at FP $7$ and $8$, against the prior best of $5$. For GIFT-64, we extend the prior best FP $6$ to $7$ with a byte fault, leaving $2^{32}$ master-key candidates. For BAKSHEESH, we extend the prior best FP $7$ to $8$, also when the fault position is uncontrolled.

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their sets without revealing any additional information and has found numerous applications. The approximate matching required by various applications has led to the development of Fuzzy PSI (FPSI), a variant of PSI that identifies approximate intersection elements under a public distance threshold \(\delta\). Reducing computation and communication costs remains an important challenge for FPSI. In this paper, we present a new FPSI protocol, called Mercury, which achieves logarithmic computation and communication complexity with respect to threshold \(\delta\). Our protocol exploits the correlation of the intersection and the point pairs held by the parties, and efficiently identifies the neighboring point pairs by a mixed protocol from homomorphic encryption and secure two-party computation using a "mask-then-compare" technique. We implemented Mercury and evaluated both its sender-private and standard FPSI variants. For balanced two-dimensional inputs, Mercury-SP achieves \(9.0\sim63.9\times\) runtime speedups and reduces communication by a factor of \(8.7\sim26.1\) across the evaluated thresholds and set sizes in the LAN setting, compared to the FPSI protocol by Dang et al. (CCS'25). In the completed unbalanced experiments, Mercury-SP achieves \(55.7\sim132.4\times\) WAN runtime speedups compared to the FPSI protocol by Piske et al. (CCS'25).

Timed cryptography captures computations that inherently require a prescribed amount of time, even in the presence of parallelism, and has emerged as a central notion due to its broad applications in both practice and theory. A natural question is how timed cryptographic primitives relate to traditional cryptography, in particular to primitives in Minicrypt. Guan and Montgomery (CRYPTO 2024) show that sequential functions do not imply one-way functions (OWFs) via black-box reductions. Their result, however, leaves open whether adding public verifiability (a substantially stronger requirement) suffices to imply OWFs. We study this question via verifiable delay functions (VDFs), which require substantial sequential time to evaluate, yet produce a unique output that is efficiently and publicly verifiable. We show that VDFs do not imply OWFs via fully black-box, relativizing reductions. Combined with prior results showing that VDFs cannot be constructed in the random oracle model, this establishes that there is no black-box implication in either direction between VDFs and OWFs. Our proof develops a new oracle separation technique that combines the random oracle with a carefully designed complexity-theoretic oracle inspired by Kolmogorov complexity.

A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM'24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms---namely, compression algorithms where the encoding process preserves the ordering of the inputs---in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS'23) that incompressibility implies next-bit pseudoentropy.)

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.

Coin-tossing protocols allow mutually distrustful parties to generate trusted randomness. While strong fairness is impossible against a corrupted majority, Chung et al. (2018) introduced cooperative-strategy-proof (CSP) fairness for multi-party coin tossing, under the assumption that each party gets utility only when the outcome matches its public preference. CSP-fairness ensures that no PPT adversary can increase the expected joint utility of the corrupted parties through deviation. Since then, a line of work (Wu et al., 2022; Thyagarajan et al., 2024; Zhang and Wu, 2025) has explored the landscape of CSP-fair coin tossing and shown that CSP-fairness can be achieved even against a corrupted majority. In this work, we study CSP-fair multi-sided coin tossing against up to $n-1$ corruptions when parties may have arbitrary utilities over the possible outcomes. Perhaps surprisingly, we show that CSP-fairness against any semi-malicious adversary corrupting up to $n-1$ parties is achievable for every full-row-rank utility matrix. Our construction can also be upgraded to fully malicious security. More generally, we introduce an abort-safe opening order condition on the utility matrix that suffices for resilience against $n-1$ corruptions. Our construction uses a public random walk whose state dynamically determines the distribution of the eventual outcome. The parties jointly generate randomness deciding each walk step using commit-and-reveal. When a party aborts, the protocol adjusts the transition distribution of the walk based on the parties' utilities. These adjustments, together with a carefully chosen opening order, prevent profitable deviations. We also identify conditions on the utility matrix under which CSP-fair coin tossing is impossible. For three parties, our positive and negative results together give a complete characterization of the utility matrices for which CSP-fairness against two corruptions is achievable.

Inner-product functional encryption (IPFE) allows the holder of a functional key for a vector $y$ to learn $\langle x,y\rangle$ from an encryption of $x$, and nothing more. Keys, however, accumulate: a coalition holding sufficiently many independent keys recovers the plaintext. We model each institution by the span $W_i\leq\F_q^n$ of its authorized key vectors and show that a coalition $I$ determines the plaintext exactly modulo $(\sum_{i\in I}W_i)^\perp$; for a uniform plaintext it learns exactly $\dim\sum_{i\in I}W_i$ field symbols. The resulting leakage function is a representable and entropic polymatroid. We then study authorization spaces of dimension $r$ whose pairwise intersections have dimension at most $h$. We prove that some coalition of size $c\geq2$ always learns at least $\min\{n,2r-h+c-2\}$ dimensions, and we give a Vandermonde-type construction in which every coalition of size $c$ learns exactly this amount, for all $c$ simultaneously. Hence the largest achievable reconstruction threshold is $n-2r+h+2$, which gives an exact tradeoff between functional diversity and collusion resistance. The optimal configuration is a sunflower, an equidistant subspace code and a generalized arc; its orthogonal complements form a generalized dual arc, and for $r=1$ it reduces to Reed--Solomon secret sharing.

Fully Homomorphic Encryption (FHE) enables one to implement low-round and low-communication complexity Multi-Party Computation (MPC) which is secure in the static malicious corruption model. By expanding on an idea presented in the full version of the FHE-based MPC protocol of Smart (IMA, 2023), we show how to completely remove the need for Zero-Knowledge Proofs-of-Knowledge in that protocol. This simplification makes the final security proof of the MPC protocol much simpler, and more modular. The new protocol makes use of an FHE scheme with an encrypted PRF functionality, and in addition to our main result we formalize the security of such encrypted PRFs and prove the construction of Deo et al. (CCS 2025) secure in this model.

We show an attack on a lattice-based blind signature proposed in Crypto'20. Formally it is a linear hash function based framework with a lattice-based instantiation. We first notice a bug in their security proof of blindness, which is overlooked these years. Then, we develop an attack under the honest key and the honest-but-curious signer setting against the blindness notion of the schemes by exploiting the coorelations between the leaves of the tree. We also discuss how to repair the scheme.

We present the first new infinite family of APN functions obtained by applying the switching construction to a known family since the introduction of the Budaghyan-Carlet-Leander family in 2009. Our construction is also the first example of an infinite APN family obtained via the switching construction from an infinite family of non-power functions. More generally, we study families of APN functions that can be obtained from the Budaghyan-Helleseth-Kaleyski family by the addition of carefully selected perturbation terms. We perturb the known family by combinations of Frobenius conjugates of the relative norm and obtain four constructions, naturally arranged into two switching pairs. One of these families is EA-equivalent to the Li-Zhou-Li-Qu family, for which our construction yields a new univariate representation. Switching it by a norm-derived Boolean term produces a second family that we prove to be APN in every dimension where the base family is defined, and we show that this family is CCZ-inequivalent to all previously known constructions. Furthermore, we investigate two other infinite families that can be switched to one another, conjecture that they are APN for infinitely many dimensions, and obtain conditions that can be used to characterize their APN-ness. The new infinite APN family and the two conjectured APN families generalize previously known sporadic APN instances in dimension 10.

Lattice agreement is a relaxed version of the standard consensus problem: correct processes need not decide the same value, but their decisions must be ``comparable''. Namely, every process proposes a value from a join semi-lattice, and correct processes decide values that (1) lie on a single chain, (2) include their own proposals, and (3) include nothing beyond what was proposed. Lattice agreement has important practical applications, as it underpins atomic snapshot objects and replicated state machines with commutative operations. Yet, the best known protocols decide in $O(\log f)$ rounds, where $f$ is an upper bound on the number of faulty processes. In this paper, we break the logarithmic barrier. Namely, we present Join-IT, a synchronous Byzantine lattice agreement protocol that tolerates $f < n/3$ Byzantine processes and decides in $O\big( \frac{\log f}{\log \log f} \big)$ rounds. Join-IT uses no cryptography whatsoever, and its guarantees thus hold against a computationally unbounded adversary. Perhaps surprisingly, Join-IT is also remarkably simple. It sequentially composes two classical primitives: gradecast, which takes three rounds, and approximate agreement, which, at the precision Join-IT requires, takes $O\big( \frac{\log f}{\log \log f} \big)$ rounds. A single local step finally turns the output of approximate agreement into comparable decisions, at no additional cost in rounds.

Hair and Sahai have recently proposed a construction of witness encryption for NP satisfying semantic security. In this short note we observe that this recent witness-encryption construction is unconditionally extractable in the generic group model. This yields a construction of extractable witness encryption without assuming subexponential soundness of SNARGs, in contrast to the recent work of Jin (eprint:2026/2063), which requires this assumption. The result in this note, moreover, complements the concurrent work of Chen and Vaikuntanathan (eprint:2026/2346), who show the same construction to be public-coin extractable under a knowledge-style assumption; our argument is unconditional, but in the GGM.

A recent work by Belohorec et al. (Crypto, 2025) shows that the well-known PST multivariate polynomial commitment scheme is black-box extractable under falsifiable assumptions. They show that a minimally modified (extended) PST is extractable under an assumption ARSDH($n$), and that the canonical PST is extractable under an assumption GARSDH($n$). Both of these assumptions are new and more specialized than the original ARSDH assumption proposed by Lipmaa et al. (Eurocrypt, 2024) to prove black-box extractability of the univariate KZG polynomial commitment. A natural question is whether these assumptions are actually stronger than the original ARSDH assumption. We answer this negatively: we show that both ARSDH($n$) and GARSDH($n$) are equivalent to the original ARSDH assumption. Secondly, we point out a gap in the proof that canonical PST is extractable under GARSDH($n$) assumption.

Oblivious RAM (ORAM) is a powerful cryptographic primitive that hides both the contents of outsourced data and the access pattern to the data. However, it offers only a restrictive array-based interface. A principal obstacle to its deployment is building an efficient oblivious dictionary upon it. To build such a dictionary, the state-of-the-art layers an oblivious AVL tree over ORAM, avoids an expensive local position map, but forces every operation to traverse a full root-to-leaf path, costing $\Theta(\log n)$ ORAM accesses. We show this trade-off to be suboptimal, particularly when deployed in a common setup within a trusted execution environment like SGX. There, a small amount of client memory can reduce the position map recursion depth to three levels or less, rendering its overhead relatively small. With low position map cost, probabilistic hash tables prevail as dictionary data structures due to their small, constant number of accesses compared to $\Theta(\log n)$ path traversal of a tree. We implement and analyze oblivious, probabilistic hash tables over Path ORAM, including several different strategies: chaining, power-of-two-choices, stash-less cuckoo, and de-amortized cuckoo hashing. Execution of these algorithms within a secure enclave requires "double obliviousness", which in turn needs strict concrete maximum cost limits for each access that current literature does not provide. We derive these concrete padding parameters bounding the hash table rebuild probability to $\le 2^{-40}$ via large-scale simulation. In an SGX deployment, our constructions outperform oblivious trees by up to $20\times$ for $\mathsf{lookup}$s and $12\times$ for $\mathsf{insert}$s.

Attribute-based credentials (ABCs) enable privacy-preserving authentication by allowing users to prove statements about certified attributes without revealing unnecessary information. However, while ABCs hide undisclosed attributes, the credential verification process inherently reveals the issuer's identity, which can leak contextual information such as a user's nationality or residency. Issuer-hiding ABCs address this by concealing the issuer during verification, but introduce a critical accountability problem: if an issuer is compromised or acts maliciously, previously accepted presentations originating from that issuer cannot be singled out without significant privacy violation and high burden on the central authority performing the inspection. We propose an issuer-inspection mechanism that enables retrospective attribution while preserving privacy. An inspection authority can release keys allowing verifiers to locally identify presentations originating from a specific compromised issuer and a defined time period, without affecting other issuers or earlier time periods. Concretely, we formalize the syntax and security requirements of issuer inspection and provide a generic construction from standard cryptographic building blocks; we further present a concrete pairing-based instantiation using Groth's randomizable structure-preserving signatures, Schnorr-style proofs and an adaptation of Gentry's anonymous identity-based encryption. Our analysis of computational and communication costs indicates that the proposed functionality remains practical for realistic parameter choices.

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

Secure weighted aggregation is essential for privacy preserving federated learning, yet existing schemes do not simultaneously provide post-quantum security, resilience to client dropouts, verifiability against malicious servers, and resistance to bounded collusion between the server and clients. This paper presents PQ-DVSA, a verifiable secure aggregation scheme that provides post-quantum security and resilience to client dropouts. PQ-DVSA protects both clients’ updated local models and aggregation weights, enables reconstruction of the aggregate mask for the active set after client dropouts, and allows clients to verify the server’s aggregation result under bounded collusion. Experimental results show that PQ-DVSA achieves learning performance comparable to exact weighted aggregation and reduces the runtime for encrypted submission at each client by up to 96% compared with SWAS, the closest existing scheme to PQ-DVSA.

Secure multiparty computation with provable identifiable selective abort (PISA), introduced by Kondi and Ravi (CCS 2025), guarantees that every honest party either obtains the computation output or a certificate that convinces any external auditor that a specific party cheated. Crucially, honest parties need not agree: some may get output while others receive evidence of cheating. In contrast, secure computation with identifiable abort (IA) requires just such unanimity; however, in the event that an honest party doesn't get output, it need merely be able to point to a cheater - not to prove their guilt. Secure computation with IA classically requires broadcast. Kondi and Ravi demonstrated that secure computation with PISA, on the other hand, can be built over point-to-point channels alone. While PISA is feasible exactly when guaranteed output delivery is, i.e. for $t < n / 2$, the best known construction over point-to-point channels requires six rounds. We settle the round complexity of PISA for all but a narrow band of thresholds. We prove that two rounds are impossible for $t \geq n /3$, even with arbitrary setup and computational assumptions; we give a three-round protocol for any $t < n/2$, which is therefore round-optimal for $n / 3 \leq t < n/2$; and we give a two-round protocol for $t < n/4$. The two-round protocol introduces a new primitive called one-or-nothing secret sharing with omissions.