Private Set Union (PSU) allows two parties to compute the union of their private sets without revealing any additional information---in particular, it hides their common elements (the intersection). Although recent years have seen significant progress under the semi-honest model, resulting in several efficient two-party PSU protocols, notable gaps remain: (1) some prior works model the semi-honest PSU functionality inaccurately, and (2) practical and scalable maliciously secure protocols are still lacking, except when relying on heavy generic techniques (e.g., FHE, GMW, or general purpose NIZK). In this paper, we address these issues directly and summarize our contributions as follows: 1. We revisit the formal definition of PSU, covering both the standard one-sided functionality (where only one party receives the output) and the two-sided variant (where both parties receive the output), refuting several flawed claims from prior work, and show that the notion of ``during-execution leakage'' was not well-defined in the literature, since the ``enhanced'' functionality is actually equivalent to the standard one. 2. We show how one of the fastest semi-honest protocols can be strengthened against malicious senders with a simple ad-hoc modification, while preserving its efficiency and simplicity. 3. As our main result, we present the first practical, concretely efficient, and maliciously secure two-sided PSU protocol, achieving at least a quadratic improvement over prior work. Along the way, we also resolve the challenge of assuring honest behavior for the hash-to-curve function in the PSU context---a task generally regarded as impractical due to the non-algebraic nature of the hash function. 4. We implement both protocols and compare them with existing schemes. Our experiments demonstrate that our maliciously secure protocols are only ${1.1\!-\!2.4}\times$ slower than the most efficient semi-honest protocols in the literature.

In this paper, we focus on the class of at least linearly homomorphic schemes such that their homomorphic addition operator is itself a linear operator over the ciphertext domain. This class of schemes, which we refer to as HELLHO schemes, notably encompasses the basic variant of most practically used FHE schemes such as BFV, BGV, CKKS and TFHE, as long as their mode of operation allows for homomorphic additions not immediately followed by bootstrapping, but also several extensions of them as well as other less mainstream proposals based on other assumptions. Although the aforementioned specific FHE are known to be CPAD insecure due to the existence of concrete attacks against them in that model, we first show by a simple argument that no HELLHO scheme can achieve CPAD security. Moving one step further, we also establish several counter-intuitive facts for the class of HELLHO schemes: for example that any CCA2 attack can be turned into a CPAD one or that, still only for this class of schemes, CCA1 security is equivalent to CPAD1 security (a strictly weaker ``CCA1-style'' variant of CPAD). Among other practical consequences, the results in this paper notably allow to show that instantiating the Dynamic Error Estimation (DEE) heuristic of Li et al. (Crypto'22) from any ``natural'' (R)LWE-based schemes cannot yield a CPAD secure scheme. As another notable consequence, we further exhibit a practical KRD attack on the DE-CKKS scheme, which is presently supported in OpenFHE. We conclude the paper by experimental results showing that this attack is able to perform a full key recovery on DE-CKKS in a matter of hours on an average laptop PC.

Gradient boosted decision trees, particularly XGBoost, are among the most effective methods for tabular data. As deployment in sensitive settings increases, cryptographic guarantees of model integrity become essential. We present ZKBoost, the first zero-knowledge proof of training (zkPoT) protocol for XGBoost, enabling model owners to prove correct training on a committed dataset without revealing data or model parameters. Naively re-executing XGBoost training in ZK would incur prohibitive costs, primarily due to the oblivious partitioning of training samples and unknown tree splits. Moreover, previous work on ZKP of training and inference had subtle security issues, such as leakage of tree topology and soundness gaps allowing cheating model providers to deviate from the correct execution of training and inference. We make two key contributions to address these challenges: (1) a generic zkPoT template for XGBoost that can be instantiated with any general-purpose ZKP backend, significantly improving prover costs compared to naive re-execution of the training process; and (2) a VOLE-based instantiation that overcomes the security issues of previous ZK proofs of training at minimal costs. To maximize efficiency, we develop a fixed-point version of XGBoost, which is particularly well suited for efficient instantiation of ZKP, and show it matches standard XGBoost accuracy to within 1\% on real-world datasets.

Idealized models such as the Random Oracle Model and the Generic Group Model underpin much of modern provable security. The Algebraic Group Model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO 2018) attempts to bridge the gap to the standard model by forcing adversaries to justify every new group element via a linear representation in its inputs, and it was leveraged in many follow-up works. Lipmaa, Parisella, and Siim (TCC 2023) strengthened this framework to the AGM with Oblivious Sampling (AGMOS), which additionally lets attackers obtain random group elements without the knowledge of their discrete logarithms, reflecting the practical availability of hashing to the group via admissible encodings. Although several works already rely on AGMOS, the security arguments are still ad hoc, and it is unclear whether an AGM proof automatically extends to this richer setting. We initiate a systematic study of this question. Our main result is a generic lifting theorem: For any assumption whose verification predicate satisfies a simple structural lifting condition, every AGM reduction remains sound in AGMOS under the Find Polynomial Representation (FPR) and Tensor Oracle Find Representation (TOFR) assumptions. The lifting condition is met by a broad class of algebraic protocols. As illustrations, we lift from the AGM to the AGMOS (i) the knowledge soundness of KZG-like polynomial commitments and (ii) the security of the multivariate Adaptive Rational Strong Diffie–Hellman (ARSDH). Our results clarify the precise relationship between AGM and AGMOS and provide a black-box recipe for future work: once a proof is obtained in the AGM, one can often inherit AGMOS security with negligible additional effort. This both streamlines the use of AGMOS in forthcoming work and reinforces the confidence that schemes proven secure in the AGM remain robust when oblivious sampling is available.

Plonk is one of the most influential and widely used zk-SNARKs, with proofs of constant size (0.5 kB), sublinear verification time, and circuit-independent setup. All prior security analyses of Plonk—of both knowledge soundness and zero knowledge (ZK)—are in the random-oracle model (ROM), which recent work has shown to be especially problematic in the context of proof systems. Moreover, a security proof in the ROM does not justify using a system recursively, a powerful technique currently used e.g. in "zk-rollups." We show that for analyzing Plonk, the ROM can be avoided when making the "zero-testing" (ZT) assumption on the used hash function (and the commitment scheme). ZT is a non-interactive, falsifiable hardness assumption. Assuming ZT, we prove Plonk knowledge-sound in the algebraic group model (AGM) and computationally ZK in the standard model. Using Plonk recursively can now be justified in the recursive AGM. To increase confidence in ZT, we prove that it holds in the ROM assuming the used commitment scheme is binding. Moreover, when using KZG commitments in the generic group model we show that collision resistance of the hash function implies ZT.

LLM-based agents, which interleave large language model inference with external tool calls, are increasingly deployed in high-stakes settings. In real-world deployments, each model inference and provider-hosted tool execute behind the provider's API. Even when the agent loop runs on the user's device, these provider-executed steps still remain opaque to the user. This opacity creates an end-to-end integrity gap: a malicious provider may substitute the advertised model or fabricate tool observations to steer subsequent agent behavior. Existing zero-knowledge proof systems for LLMs prove only the Transformer computation of a single inference, leaving the rest of the inference pipeline, long-form autoregressive generation, and external tool interactions outside the proof. We present zkAgent, the first SNARK system for verifiable agent execution. zkAgent proves the complete inference pipeline, from token-to-embedding lookup and positional encoding to Transformer computation and decoding. It further binds each tool observation to an authenticated execution via zkTLS or zkVM subproofs, yielding a single end-to-end proof. To scale beyond per-token proving, we introduce one-shot transcript proving: by exploiting the Transformer's causal attention mask, zkAgent proves an entire multi-step agent transcript in a single forward pass, avoiding the substantial overhead incurred by one-proof-per-token generation. We make this batched proof sound with a weight-dependent quantization scheme that is both input-independent and unconditionally complete. On GPT-2 with a 512-token transcript, zkAgent achieves a $1047.4\times$ prover speedup over the state of the art (zkGPT, USENIX Security'25), amortizing to $0.30$s/token. On a real-world coding-assistant execution, zkAgent completes end-to-end proving in $93.18$s with $1.63$s verification, making verifiable agent execution practical.

Cloud-based Large Language Model (LLM) inference processes sensitive user inputs, yet current deployments offer limited confidentiality guarantees. Fully Homomorphic Encryption (FHE) can provide strong privacy, but it clashes with transformer architectures, where rigid ciphertext packing demands expensive rotations, and deep polynomial circuits for nonlinearities necessitate costly bootstrapping. Although recent work has reported promising speed-ups, maintaining model accuracy is a challenge. We address these issues with ELLMo, a packing- and depth-aware encrypted transformer design. ELLMo introduces a novel matrix multiplication algorithm to reduce the ciphertext rotations. Further, head-split and merge steps are fused into this new algorithm at no additional cost. To reduce the depth of nonlinear layers, our contributions, Statistical-max Softmax and DelayNorm, help bypass deep comparison trees and homomorphic divisions to reduce bootstrapping by up to 46%. On encrypted BERT-Tiny, ELLMo achieves a $1.4\times$ speedup over state-of-the-art baselines with 0-1.5% accuracy loss across SST-2, MRPC, and RTE downstream tasks.

Efficient evaluation of multivariate polynomials over finite spaces is an important problem in algebraic cryptanalysis, particularly in exhaustive-search attacks on multivariate public-key cryptosystems. Existing fast exhaustive-search techniques, including those of Bouillaguet et al. (CHES 2010), Dinur (EUROCRYPT 2021), and Furue and Takagi (PQCrypto 2023), mainly target the complete space $\mathbb F_q^n$, whereas many cryptanalytic applications require evaluation only over structured subsets. Recently, Liu et al. proposed a memory-efficient algorithm for evaluating degree-$d$ polynomials over product Hamming balls \[ B(\textbf{\textit{n}},\textbf{\textit{w}})=B(n_s,w_s)\times\cdots\times B(n_1,w_1)\subseteq\mathbb F_2^n, \] where $\sum_{i=1}^{s}n_i=n$ and $B(n_i,w_i) \subseteq \mathbb F_2^{n_i} $ denotes the set of vectors of length $n_i$ and having at most $w_i$ nonzero coordinates. In this work, we extend this structured-subset paradigm by developing a unified derivative-based framework, comprising initialization and evaluation phases, first over prime fields $\mathbb F_q$ and subsequently over arbitrary finite fields $\mathbb F_{q^\rho}$ through basis expansion. We derive two initialization methods with time complexities $\mathcal O(nrM)$ and $\mathcal O(rM^2)$, where $M\leq\min\{\binom{n+d}{d},q^n\}$ and $r=\min\{d,q-1\}$. After initialization, evaluation over $B(\textbf{\textit{n}},\textbf{\textit{w}})$ requires $\mathcal O(d|B(\textbf{\textit{n}},\textbf{\textit{w}})|)$ arithmetic operations, apart from a linear setup cost. The corresponding overall memory bounds are $\mathcal O((M+r^2)\log q+n\log(nq))$ and $\mathcal O(((d+1)M+r^2)\log q+n\log(nq))$, respectively, and are independent of the number of evaluated points.

The past few years have witnessed the growing importance of pseudorandom correlation generators (PCGs) for generating correlated randomness with sublinear communication. To date, quasi-linear time PCGs for oblivious linear evaluation (OLE) over arbitrary finite fields have been constructed under either Ring-LPN or Quasi-Abelian syndrome decoding (QA-SD) assumptions, with a throughput of millions of OLEs per second demonstrated, in particular, for binary field. However, many modern MPC protocols deal with large prime fields, in which existing PCGs suffer from a significant efficiency gap due to a quasi-linear number of {\em multiplications} involved in FFT (Fast Fourier Transform) algorithms. Moreover, FFT typically relies on FFT-friendly fields that contain large smooth multiplicative subgroups, and therefore are not well suited to popular fields, such as Mersenne prime fields. In this work, we close the gap by leveraging the well-known Walsh-Hadamard transform (WHT) in the context of QA-SD based PCGs. Although WHT is still a quasi-linear time algorithm as normal FFTs, no multiplication is needed — addition and subtraction suffice. Since multiplications over a prime field $\mathbb{F}_p$ typically incur an $O(\log{p})$ overhead over additions, our scheme that avoids a large number of multiplications perfectly fits the large prime field setting. Experimental results show that WHT is at least one magnitude faster than FFT over a $64$-bit smooth prime field. Consequently, our PCG achieves $27,000$ OLE per second over a $64$-bit prime field. This is the first full implementation of PCG for OLE over arbitrary large prime fields that we are aware of. We then build PCG for vector-OLE over arbitrary large prime fields from QA-SD assumptions, and fully implement it using the $\mathsf{libOTe}$ library. We achieve a throughput of over $5$ million vector-OLEs per second over a $64$-bit prime field, roughly four times faster than state-of-the-art PCGs from either expand-accumulate (EA) codes (Boyle et al., CRYPTO 2022), or expand-convolute (EC) codes (Raghuraman et al., CRYPTO 2023).

We present HyperFrog, a lattice-based Key Encapsulation Mechanism (KEM) targeting post-quantum security levels. The construction instantiates a variant of the Learning With Errors (LWE) problem in which the secret vector is derived from high-genus topological structures embedded in a three-dimensional grid. Unlike standard LWE schemes that draw secrets from uniform or Gaussian distributions, HyperFrog uses a topology-mining procedure to generate sparse binary secret keys corresponding to connected subgraphs with cyclomatic number (genus) >= 8, introducing geometric constraints while preserving combinatorial hardness. To achieve practical robustness, the scheme applies the Fujisaki-Okamoto (FO) transform, attaining IND-CCA2 security under standard assumptions. The reference implementation, internally codenamed "Topological Obsidian", includes a constant-time decoding routine based on branchless arithmetic to eliminate secret-dependent control flow during decryption and re-encryption. We provide benchmark results on an AMD Ryzen 9 5950X implementation using AVX2 vectorization for polynomial arithmetic, and demonstrate the integration of the KEM into a high-performance AES-256-GCM hybrid encryption pipeline.

Hash-based signature (HBS) schemes, including LMS, XMSS, and SPHINCS+, have become crucial components of post-quantum cryptography. LMS and XMSS are stateful schemes, while SPHINCS+ is stateless, which can be applied in different scenarios. A variety of hash operations in these schemes lead to complex input/output patterns for the hash cores. In this paper, we present an efficient and configurable hardware architecture that supports key generation and signing for all three schemes. Their complex procedural flows are abstracted into 11 shared and parameterized tasks under a unified control module, avoiding controller state blow-up. Driven by hierarchical counters, this approach maximizes resource reuse and preserves scalability, occupying only 17\% of the total LUTs. Moreover, the design employs two hash cores with unroll-2 scheduling, which are experimentally validated to strike a favorable balance between area and time. We further introduce an asymmetric dual-path hash input logic (HIL) for each of them: a dedicated parallel lane for the high-frequency One-Time Signature (OTS) task and a flexible padding-shifter for all other tasks. This eliminates wide multiplexers and achieves a superior area-time balance. On Artix-7 FPGA, our unified design occupies 24.2k LUTs/13.7k FFs/16.5 BRAMs. Compared to state-of-the-art single-scheme designs, our architecture achieves up to $4.12\times/10.92\times$ lower Area-Time Product (ATP) for LMS/XMSS signing and $2.47\times/6.61\times$ lower ATP for key generation. More importantly, we provide a flexible, efficient, and scalable hardware foundation for the diverse practical deployments of HBS.

Zero-knowledge proofs of knowledge of isogenies constitute a key building block in the design of isogeny-based signature schemes and have numerous other practical applications. A recent line of work investigated such proofs based on generic proof systems, e.g., zk-SNARKs, along with a suitable arithmetization and in particular rank-1 constraint systems (R1CS). Cong, Lai and Levin (ACNS'23) considered proving the knowledge of an isogeny of degree $2^k$ between supersingular elliptic curves via modular polynomial relations. Recently, den Hollander et al. (CRYPTO'25) have shown that the use of canonical modular polynomials instead of the classical ones allows to improve on the number of constraints for the same types of isogenies, and further allows to extend this approach to isogenies of higher (though limited) degrees. Another recent work by Levin and Pedersen (ASIACRYPT'25) showed that switching from modular polynomials to radical isogeny formulas also leads to significant improvements (at least for the case of the prime $\ell=2$). A natural question that remained open is whether sticking with the modular polynomial-based approach, but switching to other candidates of modular polynomials, and in particular Atkin and Weber polynomials, is possible and gives improvements and flexibility. In this paper we show that the use of the Atkin modular polynomials enables the use of degrees not covered by existing works and improves the number of constraints for $\ell > 2$ by up to $27\%$, while the Weber polynomials allow up to $39\%$ sparser constraint systems than the current state of the art. As in our prior work on canonical modular polynomials, the adaption of well-known results to the Atkin and Weber modular polynomials also requires some technical work, especially when going to positive characteristic. To this end we expand and optimize our previous resultant-based methodology, resulting in much simpler proofs for our multiplicity theorems.

Every formally verified system embeds a verification boundary: the interface between code with machine-checked proofs and code that is trusted without them. We study what happens when this boundary is not communicated clearly. Through a case study of CE Labs's libcrux and hpke-rs cryptographic libraries, we present thirteen vulnerabilities that escaped formal verification. Nine reside in unverified code, including a cross-backend endianness bug that caused real decryption failures in Signal's post-quantum ratchet, a missing mandatory X25519 validation, nonce reuse via integer overflow, and two FIPS~204 specification violations in the ML-DSA verifier. Four reside in formally verified specification and proof code: in ML-KEM, a wrong decompression constant, a missing inverse NTT, and a false serialization proof; in ML-DSA, a wrong multiplication specification that renders axiomatized AVX2 proofs unsound. From these findings, we develop a taxonomy of five verification boundary failure types, a lightweight auditing methodology for detecting them, and a comparative analysis with AWS's verified libcrypto. The same failure types arise in both projects, but their management---through systematic documentation, proof execution in CI, and clear scope communication---varies significantly. We call the gap between verification claims and verification reality "verification theatre", and propose concrete practices for closing it.

We present an active attack against the PEARL-SCALLOP group action. Modelling Alice as an oracle that outputs the action by a secret ideal class on suitably chosen oriented elliptic curves, we show how to recover the secret using a handful of oracle calls (four for the parameter set targeting a security level equivalent to CSIDH-1024), by reducing to the computation of moderately-sized group action discrete logarithms. The key ingredient to the attack is to employ curves with non-primitive orientations inherent to the PEARL-SCALLOP construction. We provide methods for public-key validation — that is, for deciding whether a given orientation is primitive — and discuss their practicality.

Threshold ECDSA has become a crucial security component in blockchain and decentralized systems, as it mitigates the risk of a single point of failure. Following the multiplicative-to-additive approach, the state-of-the-art threshold ECDSA (Doerner et al. in S&P24) requires only three rounds but has \( O(n) \) outgoing communication complexity. Based on threshold CL encryption, Wong et al. (in NDSS24) proposed the first scheme with constant outgoing communication; however, their scheme requires at least four rounds. We bridge this gap by introducing a three-round threshold ECDSA scheme with constant outgoing communication based on threshold CL encryption. Additionally, we enhance our basic scheme with robustness while maintaining the number of communication rounds, albeit at the cost of non-constant outgoing communication. Our implementation demonstrates that the basic scheme achieves optimal runtime and communication costs, while the robust variant reduces the communication rounds required by Wong et al.'s scheme, incurring only a small additional cost in small-scale settings.

Threshold signatures allow multiple parties to sign a common message by collaborating. More specifically, in a $(t,n)-$threshold signature scheme, at least $t$ out of $n$ parties must collaborate to sign a message. In particular, solving linear systems shared among some parties is a problem that naturally arises in threshold cryptography, and this paper proposes three algorithms for a set of parties to solve a shared linear system $Ax = b$ in finite fields of low characteristic. The first two algorithms securely compute the determinant of a shared matrix using recent theoretical results on Newton's polynomials and by adapting an algorithm by Samuelson and Berkowitz. From these results, two algorithms can be deduced to solve the corresponding linear system. On the other hand, the third is a modification of an existing state-of-the-art algorithm. Although pre-quantum threshold signature algorithms have been extensively studied, the state of the art in the creation of post-quantum threshold algorithms remains sparse. In particular, few papers have studied the creation of a threshold algorithm based on UOV, despite the simplicity of the scheme. The new algorithms presented in this paper enable other threshold instantiations of UOV and UOV-based schemes.

Inspired by a recent paper from Shanghai Jiao Tong University and China Telecom Quantum Information Technology Group [1]—which demonstrated a full break of the KAZ algorithm family submitted to Malaysia’s MySEAL 2.0 standardization—we focus specifically on its signature component. Within the same core theoretical framework, we have observed a subtle inaccuracy in the formula given in the original work. While this does not prevent the final private-key recovery via lattice reduction, it leads to incorrect derivation of the intermediate sensitive signature data e₁ and e₂. Building on this observation, we propose a refined lattice construction that successfully reproduces the original attack while eliminating the need for an additional step: computing the greatest common divisor (GCD) between the signature component S₂ and the modulus ϕ(N). This new construction is equally capable of recovering the private key using two signatures.

We initiate the study of basing the hardness of hinted ISIS problems (i.e. with trapdoor information, or ‘hints’) on the previously conjectured space-time hardness of lattice problems without hints. We present two main results. 1. If there exists an efficient algorithm for hinted ISIS that outputs solutions a constant factor longer than the hints, then there exists a single-exponential time and polynomial memory zero-centred spherical Gaussian sampler solving hinted SIS with norm a constant factor shorter than the hints. 2. Assume the existence of a chain of algorithms for hinted ISIS each taking as input Gaussian hints whose norms decrease by a constant factor at each step in the chain, then there exists a single-exponential time and polynomial memory algorithm for SIS with norm a quasilinear factor from optimal. The existence of such hinted ISIS solvers implies single-exponential time and polynomial memory algorithms for worst-case lattice problems, contradicting a conjecture by Lombardi and Vaikuntanathan (CRYPTO’20) and all known algorithms. This suggests that hinted ISIS is hard. Apart from advancing our understanding of hinted lattice problems, an immediate consequence is that signing the same message twice in GPV-style [Gentry–Peikert–Vaikuntanathan, STOC’08] schemes (without salting or derandomisation) likely does not compromise unforgeability. Also, cryptanalytic attempts on the One-More-ISIS problem [Agrawal–Kirshanova–Stehlé-Yadav, CCS’22] likely will need to overcome the conjectured space-time hardness of lattices.

Covenants and ZKP verification directly on Bitcoin L1 have long been regarded as infeasible due to the limited expressiveness of Bitcoin Script and the absence of covenant-enabling opcodes such as OP_CAT, OP_CTV, OP_VAULT or OP_CSFS. These limitations have prevented the realization of zkRollups, trustless bridges, and programmable vaults natively on Bitcoin. This work introduces Bitcoin PIPEs v2, an upgrade to the original Bitcoin PIPEs approach focusing on emulating missing covenant functionality practically without requiring a soft fork. At its core, a PIPE v2 uses a witness encryption (WE) scheme to lock a Bitcoin private key under an NP statement. The key (and thus the ability to spend the associated coins) can be recovered only by a participant who provides a valid witness (e.g., a SNARK proof) satisfying that statement. Once unlocked, the mechanism outputs a standard Schnorr signature indistinguishable from any other Bitcoin signature. From Bitcoin’s perspective, transactions appear entirely ordinary; yet they are cryptographically guaranteed to enforce arbitrary off-chain logic. We formalize how PIPEs v2 enable arbitrary spending conditions on Bitcoin by enforcing predicates on signatures through cryptography, without requiring any consensus changes. We introduce a new primitive, the Witness Signature (WS), which captures conditional signing under hard relations. We show that a PIPE instantiated with a WE scheme and a standard digital signature scheme enables programmable covenants and SNARK-verifiable conditions on Bitcoin—entirely without soft forks, trusted parties, or interactive fraud-proof mechanisms such as those used in BitVM constructions. Finally, we explore Arithmetic Affine Determinant Program (AADP)-based witness encryption as a concrete and promising research direction for realizing PIPEs. AADPs provide an explicit arithmetic framework for enforcing SNARK-verifiable NP predicates within the PIPE architecture. This work presents a new, second-generation construction of PIPEs (PIPEs v2) for Bitcoin, extending and replacing the earlier formulation proposed in [Kom24].

This work presents several algorithms to perform operations in the quaternion ideals and orders stemming from the Deuring correspondence. While most of the desired operations can be solved with generic linear algebra, we show that they can be performed much more efficiently while maintaining a strict control over the size of the integers involved. This allows us to obtain a very efficient implementation with fixed sized integers of the effective Deuring correspondence. We apply our new algorithms to improve greatly the practical performances of a recent algorithm by Corte-Real Santos, Eriksen, Leroux, Meyer and Panny to evaluate modular polynomials. Our new implementation, including several other improvements, runs 20 times faster than before for the level ℓ = 11681. The Deuring correspondence also plays a central role in the most recent developments in isogeny-based cryptography, and in particular in the SQIsign signature scheme submitted to the NIST PQC competition. After the latest progresses, it appears that fixed-sized efficient quaternion operations is one of the main missing feature of the most recent implementations of SQIsign. We believe that several of our new algorithms could be very useful for that.

We study succinct non-interactive arguments of proximity (SNAP), which allow a prover to convince a verifier that a statement is true through a short message. Moreover, the verifier reads only a sublinear number of bits of the statement, and soundness is required to hold against polynomial-time adversaries when the statement is $\epsilon$-far from any true statements. SNAPs can be seen as the natural analog of property testing in the context of succinct non-interactive arguments (SNARGs). We obtain both positive and negative results for SNAPs. - Adaptive SNAPs for P and NP: For any $\epsilon \in (0, 1)$, we construct the first adaptively sound SNAPs for P with $\epsilon$-proximity based on standard assumptions: LWE or subexponential DDH or DLIN over bilinear maps. Our proof size, verifier’s query complexity, and verification time are $n^{1/2 + o(1)}\cdot \mathsf{poly}(\lambda)$, where $n$ is the length of the statement and $\lambda$ is the security parameter. By additionally assuming sub-exponentially secure indistinguishability obfuscation, we upgrade this result to SNAPs for NP with essentially the same parameters. Previously, we only had non-adaptively sound SNAPs for P in the designated verifier setting with $O(n^{1-\delta})$ proof size, query complexity, and verification time for some constant $\delta > 0$. - Lower Bound: We show that our parameters in the adaptive soundness setting are nearly optimal, up to an $n^{o(1)} \cdot \mathsf{poly}(\lambda)$ factor: in any adaptive SNAP for P, the product of proof size and verifier query complexity must be $\Omega(n)$. Our lower bound is unconditional. - Fully Succinct Non-adaptive SNAPs for NP: For any constant $\epsilon \in (0, 1)$, we construct the first non-adaptively sound SNAPs for NP with $\epsilon$-proximity, based on learning with errors and indistinguishability obfuscation. The proof size, verifier’s query complexity, and verification time in our constructions are fixed polynomials in the security parameter. We also show that restricting such SNAPs to just P would already imply non-adaptively sound SNARGs for NP. Central to our SNAP constructions is a new notion of commitment of proximity, which enables sublinear-time verification of the commitment. To derive our unconditional lower bound, we adopt and generalize theorems from oracle-presampling techniques in the random oracle literature. Both techniques may be of independent interest.

Secure Multiparty Computation (MPC) enables distributed parties to jointly evaluate functions on their combined datasets while preserving individual data confidentiality. Although MPC protocols and frameworks have achieved significant performance improvements in recent years, particularly for complex workloads like secure neural network inference, systematic standardization and benchmarking of these frameworks remain underexplored. This work comprehensively analyzes over 50 MPC applications to identify the core algorithmic structure most common in real-world MPC applications. From this analysis, we derive six reference use cases and implement these across four state-of-the-art MPC frameworks: HPMPC, MPyC, MP-SPDZ, and MOTION. We develop an open-source benchmarking framework that evaluates these implementations under varying network conditions, including bandwidth constraints, latency, packet loss, and input sizes. Our work presents the first systematic cross-framework evaluation of MPC performance based on real-world use cases across diverse network conditions and MPC security models. Thus, our comprehensive analysis yields novel insights into practical MPC performance and provides evidence-based recommendations for framework selection across different operational contexts.

In non-synchronous networks, partitioning arguments show that $t$-resilient protocols among $n$ processes can typically not guarantee safety when the number of malicious processes $f$ is $\geq n - 2t$. This fragility motivates augmenting such protocols with accountability schemes to deter safety violations. So far however, such schemes have been limited in their verifiability, scalability or privacy. This paper presents $\tau_{zk\text{-}scr}$, a universal compiler that circumvents such limitations. The compiler transforms any protocol $\mathcal{P}$, that is secure against semi-honest crash-failure adversaries, into a Byzantine-tolerant, accountable counterpart $\bar{\mathcal{P}}$. Essentially, we devise $\tau_{zk\text{-}scr}$ by deconstructing the celebrated CLOS compiler (STOC 2002), observing that each resulting component is ``easily accountable'', and globally propagating the accountability through the reconstruction. The guarantees provided by $\tau_{zk\text{-}scr}$ are defined with respect to a resilience threshold $t_{\epsilon} = \lceil n (\frac{1}{3}-\epsilon) \rceil - 1$, for any $\epsilon \geq 0$. $\bar{\mathcal{P}}$ preserves the hyperproperties of $\mathcal{P}$, including privacy, input-independence, correctness, and output delivery, whenever $f \leq t_{\epsilon}$. If $f > t_{\epsilon}$, then either: (1) $\bar{\mathcal{P}}$ emulates $\mathcal{P}$, in the sense that all its hypersafety properties are preserved, though output delivery may not occur; or (2) all correct processes obtain externally verifiable proofs of misbehavior involving a significant subset of faulty parties. By adjusting its parameters, $\tau_{zk\text{-}scr}$ achieves various trade-offs. Assuming a transparent setup, for any strictly positive constant $\epsilon \in \Omega(1)$, the most efficient instantiation provides security against a 1-delayed-adaptive adversary (i.e., where corruption decisions are postponed just long enough to allow messages in transit to be delivered) with $o(n^2)$ multiplicative communication overhead. Our results are formalized and proven following the Accountable Universal Composability (AUC) blueprint (S&P 2023), an extension of UC designed to support modular analysis of accountability guarantees.

In a $(t,n)$-threshold secret sharing scheme, secrecy holds as long as fewer than $t$ servers collude. If $f < t$ parties are corrupt and they sell their shares, there is no mechanism to hold them accountable in classical secret sharing schemes. Goyal–Song–Srinivasan [CRYPTO'21] introduced Traceable Secret Sharing ($\mathsf{TSS}$) and later Boneh–Partap–Rotem [CRYPTO'24] made it practical: $f<t$ corrupt servers produce a reconstruction box $\mathcal{R}$ that, given $t-f$ extra shares, outputs the secret. The task is to trace $\mathcal{R}$ back to the corrupted servers, given black-box access to $\mathcal{R}$. Prior works on $\mathsf{TSS}$ rely on a designated tracer with private trace keys for tracing and/or verification. We remove the dependence on any designated tracer and propose Collaborative Traceable Secret Sharing ($\mathsf{CTSS}$), which eliminates the private trace key and the private verification key. Instead, tracing requires collaboration from a threshold number of parties, and verification is fully public. We define the $\mathsf{CTSS}$ framework, along with its security notions, and present two efficient collaborative traceable secret sharing schemes based on the classical Shamir and Blakley schemes. Both achieve secrecy, traceability, and non-imputability, with minimal share size overhead and polynomial-time tracing effectively eliminating the need for a designated tracing authority.

Chameleon hash functions are trapdoor hashes that allow authorized adaptations while preserving security against outsiders. They appear in chameleon signatures, sanitizable and redactable structures, and several ledger mechanisms, yet the literature remains scattered. To our knowledge, no prior work has offered a dedicated survey or SoK on CHFs. This paper provides the first unified account, covering 1998 to 2025. We build a usable overview instead of a taxonomy dump. We collect the published constructions into a compact dataset that records underlying assumptions, trapdoor arrangements, and target security notions, and we place these results on a timeline from 1998 to 2025 to show how definitions and design choices evolved. We then provide simple maps that let the reader pivot between authorization models, trapdoor structure, and functional or algebraic features, keeping comparisons focused and avoiding unnecessary parameter detail. The result is a reference for making informed choices in real deployments. We end with a short set of future roads we believe are worth exploring, drawn from the gaps we observed and aimed at aligning CHF design with practical constraints and follow-up studies.

Nudge is a recommender system with cryptographic privacy. A Nudge deployment consists of three infrastructure servers and many users, who retrieve/rate items from a large data set (e.g., videos, posts, businesses). Periodically, the Nudge servers collect ratings from users in secret-shared form, then run a three-party computation to train a lightweight recommender model on users’ private ratings. Finally, the servers deliver personalized recommendations to each user. At every step, Nudge reveals nothing to the servers about any user’s preferences beyond the aggregate model itself. User privacy holds against an adversary that compromises the entire secret state of one server. The technical core of Nudge is a new, three-party protocol for matrix factorization. On the Netflix data set with half a million users and ten thousand items, Nudge (running on three 192-core servers on a local-area network) privately learns a recommender model in 50 mins with 40 GB of server-to-server communication. On a standard quality benchmark (nDCG@20), Nudge scores 0.29 out of 1.0, on par with non-private matrix factorization and just shy of non-private neural recommenders, which score 0.31.

Originally introduced as a machine learning problem in 1991, model extraction was explicitly cast as a cryptanalytic challenge at CRYPTO 2020 and has since gained increasing prominence in this context. While early work focused on ReLU-based neural networks, recent studies have investigated model extraction in the raw-output setting for PReLU-based models. However, research on other activation functions remains largely unexplored. In modern deep learning, activation functions beyond ReLU are widely used, thereby creating a need for extraction techniques that can accommodate a wider variety of activation functions. This paper broadens the scope of model extraction by introducing a systematic framework for parameter recovery that is specifically tailored to different categories of activation functions. In addition to ReLU and PReLU, we investigate several other activation functions, including Leaky ReLU, HardTanh, ELU, and the Step function. To the best of our knowledge, this is the first study to explore model extraction for these activation functions and for PReLU-based models in the hard-label setting. We provide a detailed theoretical analysis of the properties of each activation function, propose novel attack strategies, and offer new theoretical insights. The effectiveness of our approach is demonstrated through model extraction attacks in both the raw-output and hard-label settings. Moreover, we discuss the security implications of activation functions for neural network design and explore how composite or mixed activation functions may enhance security. This work provides valuable insights into model extraction and introduces a flexible framework that may have meaningful implications for both the cryptographic and machine learning communities.

The Oracle Module Learning with Errors (Oracle MLWE) assumption, recently introduced by Liu et al. (Asiacrypt~2025), strengthens standard (Module) LWE by allowing masked linear leakages of the secret under an adversarially-chosen challenge matrix. This feature is used for the construction of new efficient primitives such as Oracle MLWE-based multi-message multi-recipient KEM/PKE (mmKEM/mmPKE) without requiring public-key well-formedness proofs. In this work, we present a practical cryptanalytic attack on Oracle MLWE, which we call a neighborhood search attack. Our attack exploits adversarially-chosen matrices (or maliciously generated public keys), together with the small ring dimension and small-norm secrets required for correctness, showing that rounding errors can be recovered via a bounded search, leading to recovery of the underlying MLWE secret. To demonstrate the effectiveness of our attack, we apply it against the Oracle MLWE-based mmKEM of Liu et al. (Asiacrypt~2025), proving that its recommended parameter sets do not achieve the claimed security level. We further implement the attack in SageMath and report concrete timings, showing that an adversary controlling a moderate number of recipients can recover other recipients' encapsulated keys within a few seconds on a standard PC under the proposed parameters, which were claimed to achieve a 128-bit security level.

This paper introduces a new cryptographic notion for diffusion matrices, termed the Differential Pattern Transition($\textsf{DPT}$). Building on this notion, we develop a systematic framework for describing the differential behavior of diffusion layers over multiple rounds in $\texttt{AES}$-like block ciphers. Specifically, the $\textsf{DPT}$ framework enables a finer-grained evaluation of diffusion strength against differential attacks, allowing distinctions even among matrices sharing the same branch number. Furthermore, the $\textsf{DPT}$ framework facilitates the classification of shuffle layers and assists in identifying permutation layers that maximize differential resistance. As a case study, we apply the $\textsf{DPT}$ framework to the diffusion matrices used in $\texttt{MIDORI}$, $\texttt{PRINCE}$, $\texttt{QARMA}$, and $\texttt{AES}$, as well as a lightweight MDS matrix proposed in [SS16]. The results show that $\textsf{DPT}$ provides both theoretical insights and practical guidance for the selection and design of diffusion and shuffle layers in secure and efficient block cipher constructions.

Witness encryption (WE) for general NP remains challenging to realize with practical efficiency. A natural approach is to combine WE with SNARKs to obtain succinct witnesses; however, embedding general-purpose SNARK verification into existing WE constructions leads to prohibitive overhead. We introduce arithmetic affine determinant programs (AADPs), a variant of affine determinant programs designed to natively support arithmetic constraint systems. This enables direct expression of SNARK verification. To address security challenges in the arithmetic setting, we define projectively safe constraint systems and develop algebraic gadgets that preserve this property. Using these components, we construct a WE scheme for all NP languages based on AADPs, instantiated with a tailored SNARK. Our estimates indicate ciphertext sizes on the order of hundreds of terabytes at 100-bit security, which, to the best of our knowledge, is the most efficient instantiation of WE for general NP.

Secure TransFormer Inference (STFI) for LLMs aims to protect both user inputs and model parameters. Fully Homomorphic Encryption (FHE) offers a promising approach for STFI due to its non-interactivity, which eliminates communication overhead. However, FHE-based STFI incurs significant computational costs compared to plaintext inference. Recent advancements have accelerated inference by optimizing packing strategies and reducing the number of rotations. Despite these improvements, several challenges persist, including excessive rotations in ciphertext-ciphertext matrix multiplications (CCMMs), low input/output projection throughput, and expensive maximum/inverse operations, as well as wasted storage slots and inflated ciphertext counts due to sparse packing. To address these issues, we propose STIP, an efficient and secure non-interactive transformer inference framework that incorporates three novel packing strategies: (1) Real-Imaginary Hybrid Packing (RIHP) halves the rotation costs of CCMMs by enabling the simultaneous computation of two output results within the real and imaginary components; (2) Dual-Head Packing (DHP) maps adjacent heads to the real and imaginary components, doubling the throughput of attention projections; and (3) Adaptive Multi-Column Packing (AMCP) packs multiple heads into a single ciphertext, maximizing slot occupancy to reduce the total ciphertext count and thereby enhance computational parallelism. Moreover, for non-linear layers, we employ the Gaussian Kernel instead of Softmax, eliminating the need for maximum value searches and inverse operations, supported by a column-packed RIHP-based L2-norm algorithm. We reformulate LayerNorm into an inverse-free form by exploiting scale-invariance. Experimental results on a GPU show that STIP achieves approximately 1.6× speedup over the SOTA scheme Euston (S&P '26) on BERT-base, LLAMA-3-8B, and GPT-2-1.5B.

We propose Eidolon, a post-quantum signature scheme grounded in the NP-complete $k$-colorability problem. Our construction generalizes the Goldreich–Micali–Wigderson zero-knowledge protocol to arbitrary $k \geq 3$, applies the Fiat–Shamir transform, and uses Merkle-tree commitments to compress signatures from $O(tn)$ to $O(t \log n)$. We generate instances by planting a coloring while aiming to preserve the statistical profile of random graphs. We present an empirical security analysis of such a scheme against both classical solvers (ILP, DSatur) and a custom graph neural network (GNN) attacker. Experiments show that for $n \geq 60$, neither approach is able to recover a valid coloring matching the planted solution, suggesting that well-engineered $k$-coloring instances can resist the considered classical and learning-based cryptanalytic approaches. These experiments indicate that the constructed instances resist the attacks considered in our evaluation.

This paper introduces a generalized cryptanalytic framework for RSA and its variants, systematizing existing attacks while revealing a wide class of structural weaknesses independent of the private exponent's size. While traditional analyses exploit the key equation $ed \equiv 1 \pmod{(p-1)(q-1)}$ or its extensions like $ed \equiv 1 \pmod{(p^n-1)(q^n-1)}$ for a given RSA modulus $N=pq$ and its public exponent $e$, we unify these approaches by investigating the more general algebraic property defined by the congruence $eu \equiv 1 \pmod{(p^n-a)(q^n-b)}$, where $a$, $b$, and $u$ are unknown small integer parameters. Using Coppersmith's method with unravelled linearization, we demonstrate that the modulus $N$ can be factored in polynomial time if such a relation exists for parameters within a new, rigorously derived bound. Our framework not only unifies and generalizes several well-known attacks (retrieving their bounds as special cases when $a=b=1$) but also significantly expands the set of weak keys. We show that an RSA instance secure against all previous small private exponent attacks may still be broken if its public key possesses this hidden algebraic structure. This work serves as a comprehensive security analysis, highlighting a new family of weak keys that future cryptographic designs should avoid.

In this paper, we study the problem of sampling random supersingular elliptic curves with unknown endomorphism rings. This problem has recently gained considerable attention as many isogeny-based cryptographic protocols require such ``secure'' curves for instantation, while existing methods achieve this only in a trusted-setup setting. We present the first provable quantum polynomial-time algorithms for sampling such curves with high probability, one of which is based on an algorithm of Booher et. al. One variant runs heuristically in $\tilde{O}(\log^{6.5} p)$ quantum gate complexity, and in $\tilde{O}(\log^{20} p)$ under the Generalized Riemann Hypothesis, and outputs a curve that is provably secure assuming quantum average-case hardness of the endomorphism ring problem. Another variant samples uniform $\mathcal O$-oriented curves with unknown endomorphism rings, for any imaginary quadratic order $\mathcal O$, with security based on the quantum average-hardness of Vectorization problem. When accompanied by an interactive quantum computation verification protocol, our algorithms provide a secure instantiation of the CGL hash function and related primitives and show quantum advantage over classical algorithms. Our analysis relies on a new spectral delocalization result for supersingular $\ell$-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture and provide numerical evidence for complete eigenvector delocalization. We also prove a stronger $\varepsilon$-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction.

Blockchains have achieved substantial progress in scalability and fault tolerance, yet they remain fundamentally limited in confidentiality, hindering adoption by businesses, communities, and individuals who require privacy-preserving computations. Existing zero-knowledge (ZK) solutions provide partial privacy guarantees but struggle with performance and composability, especially for multi-party computations over shared private state. In this work, we introduce gcVM, a novel extension to the Ethereum Virtual Machine (EVM) that integrates garbled-circuit-based secure multi-party computation to enable general-purpose, privacy-preserving computation on-chain. gcVM allows transactional interactions between untrusted parties while balancing the transparency of public blockchains with strong confidentiality. Our implementation demonstrates up to 83 confidential transactions per second (cTPS) on standard cloud instances, with projected enhancements expected to scale throughput to approximately 500 cTPS—two to three orders of magnitude faster than comparable FHE-based solutions. gcVM is compatible with existing EVM tooling, provides public auditability, and requires no trusted hardware, offering a practical and efficient platform for privacy-centric blockchain applications across finance, governance, and decentralized services.

We will improve the best known lower bound of the $r$-th order nonlinearity of Boolean function for $r > 2$ via algebraic immunity

Recurrent neural networks (RNNs) play an important role in time series modeling, signal processing, and resource constrained applications. Their parameters encode valuable functionality and constitute proprietary intellectual property. Cryptanalytic extraction tests whether black box queries reveal functionally equivalent parameters. Such analysis is important for assessing the security of deployed RNNs. However, prior cryptanalytic attacks mainly target feedforward networks such as fully connected networks (FCNs) and convolutional neural networks (CNNs). RNNs reuse their recurrent parameters at every time step, which existing extraction pipelines do not address. We present cryptanalytic extraction of ReLU RNNs, including single-layer and stacked (a.k.a. multi-layer) RNNs, in both the hard-label and raw-output settings. To the best of our knowledge, this is the first such extraction. Using controlled inputs, we construct equivalent feedforward models whose depths depend on the number of recurrent layers, independently of the sequence length. However, parameter recovery from the equivalent models may yield recurrent weights with incompatible neuron orderings and positive scalings for the previous and current hidden states. We develop recurrent parameter alignment to make these transformations consistent and enable parameter reuse across time. Stacked RNNs are harder, because one equivalent model contains coupled branches, which prevent direct use of FCN sign recovery and complicate signature recovery. We therefore further develop two techniques, recurrent parameter recovery and folded bias difference. The former uses the recovered input weights to guide clustering and recover the remaining recurrent parameters, including their signs. The latter handles neurons that are otherwise difficult to recover. We demonstrate end-to-end extraction across five RNN architectures with up to three recurrent layers in both observation settings. An additional raw-output experiment extends the sequence length from 20 to 1024 using the same target parameters.

Spoed is an authenticated encryption scheme based on compression functions. We show that Spoed fails to achieve its claimed security guarantees with respect to both integrity and confidentiality. In particular, we present a universal forgery attack that succeeds with probability one using only a single encryption query and a single decryption query. The attack exploits a structural weakness in the feedback mechanism of Spoed, allowing internal inputs of the underlying pseudorandom function to coincide during verification. We further show that the same weakness enables efficient plaintext-recovery attacks, permitting recovery of almost the entire plaintext with at most two decryption queries, depending on the associated-data length. We explain why the original security proof of Spoed fails, and identify the mismatch between the collision events used in the H-coefficient analysis and the schemes actual behavior. Finally, we propose a minimally modified variant, fSpoed, and prove that it achieves the originally claimed security bounds under standard assumptions.

Private Set Union (PSU) enables two parties holding private sets $X$ and $Y$ to compute their union $X\cup Y$ without revealing anything else. Enhanced PSU (ePSU) further eliminates during-execution leakage, but existing constructions are limited to exact matching. This restriction is inadequate for many real-world applications involving noisy data, approximate representations, or feature embeddings, where similarity is naturally defined via distance metric rather than strict equality. In this work, we introduce fuzzy ePSU, a new cryptographic primitive that supports distance-based union while preserving the no during-execution leakage guarantee of ePSU. Given a distance metric $\mathsf{dist}(\cdot,\cdot)$ and a threshold $\delta$, fuzzy ePSU allows the receiver to learn exactly those sender items whose distance to all receiver items exceeds $\delta$, thereby computing a fuzzy union of the two sets. We present two concrete fuzzy ePSU constructions instantiated over different metric spaces. For the Hamming space, we design a protocol based on a new primitive called Fuzzy Oblivious Non-Membership Conditional Randomness Generation (FOnMCRG), achieving linear complexity in the input set sizes and $\delta$. For the Minkowski space, we introduce Fuzzy Permuted Non-Membership Conditional Randomness Generation (FpnMCRG), which combines fuzzy mapping with hashing-to-bin techniques and achieves (quasi-)linear complexity in the input sizes and dimension. We implement our protocols and evaluate their performance in both metric spaces. For input sets of size $2^{12}$, our Hamming-space protocol incurs about 79.990~MB of communication and 70.686~s of runtime with $\delta=4$. In the Minkowski space with $\{1,2,\infty\}$-norm, dimension $d=10$, and $\delta=30$, it incurs 388.137--689.889~MB of communication and 347.082--483.328~s of runtime.

We propose Curve5453 and Curve6071, two Montgomery curves over the Crandall prime $2^{545}-3$ and Mersenne prime $2^{607}-1$, respectively, providing 271 and 302 bits of classical security. Comprehensive security analysis shows Curve6071 passes all verifiable SafeCurves criteria, while Curve5453 passes all except completeness. We develop TMVP-optimized field multiplication tailored to the arithmetic structure of these primes for 10-limb representations on 64-bit architectures, achieving $12.0\%$ and $20.4\%$ speedups over the closest alternative. ARM64 benchmarks show scalar multiplication completing in 871,898 and 895,028 cycles, respectively, competitive with existing lower-security alternatives such as E-521 (259-bit security) while delivering higher security levels. These curves address a critical gap for hybrid post-quantum constructions requiring classical security commensurate with quantum-resistant components, blockchain systems with decades-long security requirements, and specialized deployments where implementation robustness and enhanced classical security are essential---providing the first SafeCurves-compliant alternatives beyond 260 bits with demonstrated practical performance on modern architectures.

In the past decade and largely in response to the NIST standardization effort for post-quantum cryptography, many new designs for digital signatures have been proposed. Among those, the FAEST digital signature scheme (Baum et al., CRYPTO 2023) stands out due to its interesting security-performance trade-off. It only relies on well-tested symmetric-key cryptographic primitives, as it constructs a digital signature from a zero-knowledge (ZK) proof of knowledge of an AES key. To achieve this, it uses the VOLE-in-the-Head ZK proof system which relies only on pseudorandom generator (PRG) and hash function calls. FAEST simultaneously has relatively small signature size and competitive sign and verify times. In this work, we improve both the security and practical efficiency of FAEST. We improve the main computational bottleneck of the original construction by replacing hash function calls in the underlying vector commitment scheme with calls to an AES-based PRG. At the same time, we also improve the signature size by revisiting the evaluation of the AES block cipher in ZK. We use observations from Galois Theory to compress the size of the witness (and thus signature), due to the algebraic nature of the AES S-Box. We implemented our new construction, and our benchmarks show that its sign and verify times reduce up to $50\%$ over the state-of-the-art while achieving the same security and smaller signatures. Finally, we analyze our resulting signature scheme both in the Quantum Random Oracle Model (QROM) and its classical analogue. To achieve concretely good security bounds, we devise a new classical proof for FAEST based on Renyi divergence techniques. We construct a QROM analogue and present a new Fiat-Shamir transform which is applicable to VOLE-in-the-Head-based signature schemes.

A recent “dimension padding” note proposes a structural countermeasure to linear inversion in a dual-public-key code-based encryption construction. The note argues that padding makes the private parity structure non-identifiable from the public key and suggests phrasing security in terms of this non-identifiability. This comment points out that non-identifiability of a particular trapdoor representation does not prevent message recovery. In the padded construction, the public relations used for decryption remain linear constraints. Any solution to these public constraints suffices to recover the encryption randomness and then the plaintext by linear algebra. Consequently, public-key-only decryption remains polynomial-time

Modern system-on-chips (SoCs) are becoming prone to numerous security vulnerabilities due to their ever-growing complexity and size. Therefore, a comprehensive security verification framework is needed at the very early stage of the SoC design lifecycle. The datapath of a complex SoC design may be vulnerable to information leakage and data integrity issues. The designers might be unaware of hidden information flow paths present in a particular SoC design at the pre-silicon stage, which can eventually lead to severe data breaches. Hence, it is crucial to develop a novel framework that comprehensively identifies the presence of such paths. Moreover, novel mathematical metrics need to be formulated to perform an exhaustive quantitative assessment of the detected information leakage paths. It will assist designers in quantifying the security risk level associated with these data propagation paths, ultimately making them aware of the potential implications of these leakage paths. In this paper, we propose an information flow verification framework that utilizes a combination of static and formal methodologies to identify information flow paths based on a mathematical metric for quantifying the security risk level of the detected paths. Our experiments across numerous open-source designs, varying in size and complexity, demonstrate the efficacy of the proposed framework for identifying severe information leakage and data integrity issues at the pre-silicon stage of the design lifecycle

Recent years have witnessed significant progress in first-order hardware masking of AES. However, most of the work focus on the optimizations over solely one of the metrics: chip area, latency or randomness. The optimizations for one metric often leads to increasing overheads of the other metrics. Consequently, few work focus on optimizations over all three metrics of first-order AES at the same time. To bridge this gap, we introduce two compact round-based first-order AES-128 encryption implementations with the latency of 31 cycles and 40 cycles, respectively. They are provably secure in the glitch-extended probing model with relatively low consumption of randomness. To achieve this, we first introduce a method to design first-order low-latency $d+1$ TI (Threshold Implementations) for multi-output Boolean functions with a latency of only one clock cycle. Moreover, the random bits used in the low-latency TI cancels out in the expressions of output shares, which enables the applications of a COTG-based concept to significantly reduce the randomness consumption. Finally, we apply our method to design first-order implementations for AES-128 with two shares, which allows the designs to be compact. As a result, our implementations achieve a excellent trade-off over latency, area, and randomness. Compared to the 10-cycle and 20-cycle AES-128 implementations provided respectively in TCHES 2020 and TCHES 2025, the area and randomness demands of our implementations are significantly less. We also use formal verification tools, PROLEAD, and TLVA to validate the security of our designs for S-Box and round-based AES-128 implementations, respectively.

Homomorphic Encryption (HE) provides strong data privacy for cloud services but at the cost of prohibitive computational overhead. While GPUs have emerged as a practical platform for accelerating HE, there remains an order-of-magnitude energy-efficiency gap compared to specialized (but expensive) HE ASICs. This paper explores an alternate direction: leveraging existing AI accelerators, like Google's TPUs with coarse-grained compute and memory architectures, to offer a path toward ASIC-level energy efficiency for HE. However, this architectural paradigm creates a fundamental mismatch with SoTA HE algorithms designed for GPUs. These algorithms rely heavily on: (1) high-precision (32-bit) integer arithmetic to now run on a TPU's low-throughput vector unit, leaving its high-throughput low-precision (8-bit) matrix engine (MXU) idle, and (2) fine-grained data permutations that are inefficient on the TPU's coarse-grained memory subsystem. Consequently, porting GPU-optimized HE libraries to TPUs results in severe resource under-utilization and performance degradation. To tackle above challenges, we introduce CROSS, a compiler framework that systematically transforms HE workloads to align with the TPU's architecture. CROSS makes two key contributions: (1) Basis-Aligned Transformation (BAT), a novel technique that converts high-precision modular arithmetic into dense, low-precision (INT8) matrix multiplications, unlocking and improving the utilization of TPU's MXU for HE, and (2) Memory-Aligned Transformation (MAT), which eliminates costly runtime data reordering by embedding reordering into compute kernels through offline parameter transformation. CROSS (TPU v6e) achieves higher throughput per watt on NTT and HE operators than WarpDrive, FIDESlib, FAB, HEAP, and Cheddar, establishing AI ASIC as the SotA efficient platform for HE operators. Code: https://github.com/EfficientPPML/CROSS

Nearly all existing SNARK systems are optimized for arithmetic over finite fields. Using them to prove statements involving ring arithmetic, which underlies lattice-based cryptography and fully homomorphic encryption (FHE), incurs substantial overhead. Consequently, practical deployments of FHE often rely on the \textit{honest-but-curious} assumptions, leaving a gap in the verifiability of the FHE computation. Several recent works have explored zero-knowledge proofs tailored to lattice-based schemes, yet still suffer from high prover costs and limited scalability. In this work, we introduce Dinocchio, the first distributed SNARK for rings with constant proof size and constant verification time. For a setting with $m$ sub-provers, Dinocchio achieves an approximately $m$-fold speedup in prover time compared to Rinocchio (JoC'23), while preserving the constant verification time independent of $m$. We demonstrate the practicality of Dinocchio through matrix multiplication, which is a crucial building block to large-scale lattice-based applications. With matrices of size $2^{12} \times 2^{12}$, the corresponding arithmetic circuit contains $\sim2^{32}$ constraints, which is beyond the reach of all existing works. Our microbenchmarks show that Dinocchio can generate a succinct proof in around $9.23$ hours with $128$ sub-provers, more than $108\times$ faster than the prior work, and the verifier completes the verification in under $16$ seconds.

Anonymous communication is essential for secure and private interactions over public networks. Existing solutions that provide provable anonymity rely on the so-called simple I/O setting, where every participant sends and receives the same number of messages, masking their true communication pattern. The only known way to enforce this setting is through dialing protocols. Such protocols establish pairwise conversations, but each recipient inevitably learns who attempted to contact them, violating sender anonymity, the guaranty that even the recipient cannot determine who attempted to contact them. In this work, we introduce the notion of enhanced dialing protocols, a broad class of protocols that enforce the simple I/O setting. We also initiate the first formal study of such protocols with respect to sender anonymity. We introduce a framework that captures three key properties: security, correctness, and fairness. Within this framework, we present Fusion, a protocol that achieves perfect correctness and fairness while incurring only unavoidable leakage, and Fusion+, a differentially private variant that reduces this leakage at the cost of some correctness. Through theoretical analysis, we quantify the fundamental trade-off between privacy and correctness in Fusion+. Note: This is the full version of the paper that has been accepted to appear at IEEE CSF 2026.

The Fujisaki-Okamoto transform is a popular solution to design post- quantum public key encryption schemes, or key encapsulation mechanisms. In order to ensure security against chosen-ciphertext attacks, it checks the validity of ciphertexts by re-encrypting decrypted messages. This operation in turn leads to severe side- channel weaknesses, because the re-encrypted messages can be made key-dependent. Hence, distinguishing them thanks to leakage is sufficient to extract (long-term) secret key information. As a result, recent works suggested to ensure the validity of ciphertexts by other means than re-encryption. For now, the main candidate for this purpose, integrated in the Polka encryption scheme (PKC 2023) and analyzed more generically by Hövelmanns et al. (EUROCRYPT 2025), is to use continuous norm checks through the decryption process. In this paper, we evaluate the extent to which replacing the FO-transform by such norm checks helps resistance against leakage. Negatively, we exhibit new attack vectors that were not anticipated in previous (heuristic) analyzes. Positively, we observe that the removal of the FO-transform nevertheless reduces the attack surface and we identify possible tracks to further minimize it. Overall, our results therefore shed light on the challenge of designing post-quantum public-key encryption schemes, or key encapsulation mechanisms, that can be efficiently protected against side-channel attacks. We hope they can inform theory about leakage sources that could be better taken over by design, to develop new schemes allowing a scarcer use of implementation-level countermeasures.

In this work, we present Hachi, a concretely efficient multilinear polynomial commitment scheme that offers succinct proof sizes of $\mathrm{poly}(\ell,\lambda)$ and achieves a “square-root” verifier time complexity of $\tilde{O}(\sqrt{2^\ell \lambda})$ for $\ell$-variate polynomials under the Module-SIS assumption. Compared to the current state-of-the-art scheme, Greyhound (CRYPTO~2024), Hachi provides an asymptotic improvement of $\tilde{O}(\lambda)$ in verification time, which translates into a practical 12.5-fold speedup, while maintaining compact proofs of approximately $55$ KB. To improve the verification time, we adopt the sumcheck protocol. Note that the standard sumcheck has efficiency bottlenecks for lattice-based constructions, since lattice operations are usually performed over power-of-two cyclotomic rings $\mathbf{R}_{q} := \mathbb{Z}_q[X]/(X^d + 1)$. To address this challenge, we provide a novel approach that integrates Greyhound with the ring-switching idea proposed by Huang, Mao and Zhang (ePrint 2025). Surprisingly, under this approach, the verifier does not need to perform any multiplication over $\mathbf{R}_{q}$, enabling a much faster verification time. This technique could be of independent interest for building lattice-based SNARKs, particularly for achieving faster verification. As a separate contribution, we introduce a generic reduction that converts polynomial evaluation proofs over extension fields $\mathbb{F}_{q^k}$ (under suitable parameter regimes) into equivalent statements over cyclotomic rings $\mathbf{R}_{q}$. This reduction is compatible with existing lattice-based polynomial commitment schemes and can be integrated as a modular enhancement to broaden applicability to statements over extension fields.

The Module Learning With Errors (MLWE) problem is the fundamental hardness assumption underlying the key encapsulation and signature schemes ML-KEM and ML-DSA, which have been selected by NIST for post-quantum cryptography standardization. Understanding its quantum hardness is crucial for assessing the security of these standardized schemes. Inspired by the equivalence between LWE and Extrapolated Dihedral Cosets Problem (EDCP) in [Brakerski, Kirshanova, Stehlé and Wen, PKC 2018], we show that the MLWE problem is as hard as a structured variant of the EDCP, which we refer to as the Integer Polynomial Module EDCP(IP-M-EDCP). This extension from EDCP to IP-M-EDCP relies crucially on the algebraic structure of the ring underlying MLWE: the extrapolation depends not only on the noise rate, but also on the ring’s degree. In fact, an IP-M-EDCP state forms a superposition over an exponential (in ring degree) number of possibilities. Our equivalence result holds for MLWE defined over power-of-two cyclotomic rings with constant module rank, a setting of particular relevance in cryptographic applications. Moreover, we present a reduction from IP-M-EDCP to EDCP. Therefore, to analyze the quantum hardness of MLWE, it may be advantageous to study IP-M-EDCP, which might be easier than EDCP.

In this work, we present a practical fault-injection attack against the current Unbalanced Oil and Vinegar signature scheme non-deterministic implementation that enables complete secret key recovery from a single faulty signature, given one prior fault-free signature. By applying fault injection to disrupt the mixing of the vinegar and oil components during signature generation, the secret key can be recovered directly from the faulty signature. We validate the attack experimentally on a real device using an electromagnetic fault injection setup, establishing the required glitch in practice rather than through simulation. Our experimental results indicate that a single execution of the attack achieves a success rate exceeding 90%. Furthermore, we demonstrate the real-world feasibility of the attack by transferring the attack parameters to an architecturally equivalent target, requiring only minor recalibration. To the best of our knowledge, this is the first work to demonstrate an electromagnetic fault-injection attack in the context of multivariate-based signature schemes. Additionally, we discuss possible countermeasures to protect implementations of UOV-based schemes against such physical attacks.

Recent interest in fully homomorphic encryption (FHE) has motivated efforts to develop faster and more efficient homomorphic logic circuits. Currently, Torus FHE (TFHE) provides the fastest gate-level bootstrapping and enables homomorphic evaluation over encrypted bits. Prior works typically utilize standard Computer Aided Design (CAD) tools to synthesize TFHE-amenable gate-level netlists. However, the logic resynthesis and technology mapping stages of these tools are designed for reducing area and power rather than bootstrapped gates, which leads to suboptimal netlists for homomorphic execution. In this work, we introduce BOLT, a TFHE-amenable CAD synthesis framework that explicitly targets reductions in bootstrapping depth. BOLT employs a bootstrapping-aware logic resynthesis stage to rewrite sub-networks in the input netlist into functionally equivalent forms that can be evaluated with a single bootstrapping operation. Following this, our bootstrapping-aware technology mapping stage incorporates a custom simulated annealing-based scheduler to decide whether each transformed sub-network should replace its original counterpart immediately or be deferred to enable better future opportunities. Through extensive evaluation on standard benchmark circuits, BOLT achieves significant improvements in homomorphic evaluation time, delivering $8\times$ speedup over the current state-of-the-art and $31\times$ speedup over prior work on FHEW-like schemes.

At EUROCRYPT 2020, Hosoyamada and Sasaki obtained the first dedicated quantum collision attacks on hash functions reaching more rounds than the classical ones. Indeed, as the speedup of generic quantum collision search is less than quadratic, an attack based on Grover's search may become comparatively more efficient in the quantum setting. In this paper, we focus on collision attacks on double-block length hash functions, and more precisely the Hirose compression function (HCF). At ToSC 2021, Chauhan et al. found a 10-round free-start collision attack on HCF-AES-256. At ToSC 2024, Lee and Hong corrected its complexity analysis. However, these two works are superseded by another result of Hirose and Kuwakado (IMACC 2021), which shows that for any $2n$-bit HCF hash function, a quantum free-start collision attack of complexity $\mathcal{O}(2^{n/2})$ exists. While both the works of Chauhan et al. and Lee and Hong are above this generic complexity, we find that a classical attack from Chen et al. (IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2016) translates to a 9-round quantum attack on HCF-AES-256. Next, we study the security of HCF against quantum collision attacks (not free-start). We use a generic strategy that transforms a partial preimage attack into a quantum collision attack, and give several applications on HCF hash functions: a 6-round attack on AES-256 and a 15-round attack on Romulus-H (based on Skinny), both exceeding the reach of classical attacks.

Side-channel attacks (SCAs) represent an important threat for the implementation of cryptographic algorithms. These attacks exploit the information leakage found in the physical magnitudes of hardware devices (e.g. current draw, electromagnetic emanation). Threshold Implementations (TIs) aim to mitigate SCAs by implementing a modified version of the algorithm that operates over randomized shares of its input and intermediate values. This strategy relies on the possibility of splitting the algorithm to be protected into sub-functions that satisfy certain properties about their dependence structure on the randomized shares. Non-complete set coverings (NCSCs) are combinatorial objects that can provide this dependence structure and guide the design of TIs. Given the desired order of protection $d$ and the algebraic degree $t$ of the functions to be implemented, for an NCSC to be useful, its cardinality $r$ should be small and similar to the number of input shares $s$. This work contributes to the study of NCSCs for efficient TIs by finding smaller coverings and proving novel theoretical bounds on their cardinality. We present a new NCSC for the case $t=3,d=2$ that is optimal and NCSCs for the cases $t=3,d=3$ and $t=4,d=2$ whose sizes are close to the lower bounds. We also present new combinatorial properties of these coverings and an algorithm for the search of small NCSCs.

In november 2024, the Ethereum foundation (EF) issued a bounty program with challenges on Poseidon and Poseidon2. The goal of these challenges is to find CICO solutions on different round-reduced instances of Poseidon and Poseidon2, defined on different prime fields. We denote the four main instances Poseidon-256, Poseidon2-64, Poseidon2-31m and Poseidon2-31k. In the challenges, the goal is to solve CICO-1 for Poseidon-256 and Poseidon-64, and CICO-2 for Poseidon-31m and Poseidon-31k. We found CICO solutions to the first 3 proposed instances of Poseidon2-31m and Poseidon2-31k, along with solutions for the first two Poseidon-256 instances. These solutions have been confirmed to be correct and eligible for bounty by the Ethereum fundation, except for the first instance of Poseidon-256, which was claimed by another team before us. In order to solve the instances of Poseidon2-31m and Poseidon2-31k, we used a new resultant-based approach, whereas our attacks on Poseidon-256 only relies on already-known univariate root finding.

NAT is widely assumed to conceal the private IP addresses of internal clients from both off-path attackers within the same LAN and external observers. We show that this assumption does not hold. We present a novel off-path deanonymization attack that infers the private IP addresses of NATed clients engaged in active TCP connections with a remote server. Our attack builds on known NAT behaviors in real-world Wi-Fi routers, such as port preservation, insufficient reverse-path validation, and the absence of TCP window tracking, previously shown to enable off-path TCP hijacking. By inferring a NATed client’s private IP address, our attack defeats the anonymity commonly attributed to NAT, creating a persistent privacy leak that enables deanonymization and user profiling. We validate the attack on 6 Wi-Fi routers and 2 real-world Wi-Fi networks using SSH and HTTP/HTTPS traffic over TCP, finding that 5 of the 6 routers and both networks are vulnerable.

We study the cryptographic properties of sums of commutators of quaternions modulo $q$. We show that for certain parameters, the distribution of the sum of commutators of uniformly random elements with elements sampled from a discrete Gaussian is statistically close to uniform. We also give reductions from worst-case lattice problems such as SIVP to SIS-style problems defined using commutators on structured quaternionic lattices. Together these results indicate one-wayness and collision resistance of the sum-of-commutators function, under worst-case assumptions on lattices. We use this to develop a linearly homomorphic commitment scheme, dubbed `ABBA', which in many cases can be substituted for the widely-used Ajtai commitment scheme. We demonstrate the utility of the properties of commutation by replacing the Ajtai commitments used in Neo (a state-of-the-art folding scheme from lattices) with ABBA commitments, obtaining a 25% commitment size reduction and an almost equally efficient scheme.

Bridges, protocols that enforce a state transition on a destination ledger conditioned on an event on a source ledger, are central to modern DeFi. Conventional designs implicitly assume the source ledger event is publicly observable, an assumption that breaks with Layer-2 payment channels such as the Lightning Network, where state updates occur off-chain between counterparties and are invisible to others. This state of affairs advocates for new bridge designs for this setting. This paper introduces OptiBridge, a bridge between a payment channel (e.g., Lightning Network) and a smart-contract blockchain (e.g., Ethereum) that preserves safety and liveness without adding trust assumptions and remains fully compatible with existing Lightning and Ethereum stacks. OptiBridge follows an optimistic path in the common case: two honest channel peers materialize the intended state on the destination chain by revealing a pre-agreed secret. To handle faults and adversarial behavior, OptiBridge provides a dispute path orchestrated by a more expressive contract that is deployed {only on demand}. An implementation demonstrates substantial cost savings in the optimistic case: compared to Alba (NDSS’25), the optimistic contract deployment uses $\sim 73\%$ less gas ($1.22$M vs. $4.51$M), and proof submission costs $40{,}107$ vs. $253{,}566$ gas; when disputes arise, the dispute contract deployment costs $2{,}785{,}514$ gas and the core dispute call is cheaper ($196{,}438$ vs.$515{,}860$). Our analysis shows that rational users strictly prefer the optimistic path, whereas the dispute mechanism prevents coin theft and imposes higher fees and delays on the deviator.

We present a new generic approach to extend proof techniques in the quantum random oracle model (QROM) — such as query-recording and reprogramming — to the quantum random permutation model (QRPM). Our framework involves simulating bidirectional-query random permutation oracles using Feistel constructions to port the QROM features for the underlying random round functions to the overall Feistel-simulated QRP. We then demonstrate the power of our framework by: • Obtaining a tighter than state-of-the-art lower bound for the query extrapolation problem — a variant of which was studied by Boneh and Zhandry (Eurocrypt 2013) in the QROM — in the bidirectional QRPM, as well as recovering a meaningful lower bound for the double-sided zero search problem (Unruh, Asiacrypt 2023). • Proving the adaptive zero-knowledge property of NIZKs derived from a recent variant of the Fiat-Shamir transform — called duplex-sponge Fiat-Shamir (Chiesa and Orrù, TCC 2025) which is deployed in the wild — in a post-quantum setting against non-uniform adversaries with preprocessing capabilities. All in all, our work illustrates how the “Feistel toolkit” effectively bridges the QROM-QRPM gap by not only achieving the standard QROM techniques of query-recording and reprogramming techniques for QRPs, but also unlocking new state-of-the-art features such as proving non-uniform security in the QRPM.

A blind signature scheme is an interactive protocol that enables a user to obtain a signature on a message without revealing any information about the message–signature pair to the signer. Despite more than 40 years of research, all existing constructions suffer from at least two of the following limitations. 1. The protocol is not round-optimal, requiring more than two messages to be exchanged during the signature phase. 2. There is only game-based security and/or lack of composability with global and observable setup (i.e., there is a need for trusted parameters or to program random oracles). 3. Security (unlike regular signatures) is based on demanding hardness assumptions, especially when considering quantum attacks. In this work, we show how to blindly sign a message, simultaneously overcoming all of the above three limitations. Specifically, we construct a Universally Composable (UC), two-round (optimal) blind signature protocol that relies only on one-way functions (optimal), without trusted parameters. The only deviation from the plain model is the need for a global non-programmable random oracle (NPRO). Nicely, our scheme can be instantiated from a variety of assumptions believed to be post-quantum secure (e.g., AES). A central technical component of our scheme is the construction of a novel commitment scheme that enjoys a special (mild) form of composability, which may be of independent interest. We also discuss a concrete instantiation of our scheme that is suitable for practical applications.

Recently, the notion of dynamic zk-SNARKs was introduced. A dynamic zk-SNARK augments a standard zk-SNARK with an efficient update algorithm. Given a valid source statement-witness pair $(x,w)$ together with a verifying proof $p$, and a valid target statement-witness pair $(x',w')$, the update algorithm outputs a verifying proof $p'$ for $(x',w')$. Crucially, $p'$ is not recomputed from scratch; instead, the update algorithm takes time roughly proportional to the Hamming distance between $(x,w)$ and $(x',w')$, analogous to how dynamic data structures update the result of a computation after a small change. In this paper, we initiate the study of designated-verifier dynamic zk-SNARKs: dynamic zk-SNARKs in which only a designated verifier, holding secret verification state, can be convinced by a proof. Following recent advances in designated-verifier zk-SNARKs---such as efficient post-quantum designated verifier SNARKs (CCS 2021) and designated verifier SNARKs with very small proofs (CRYPTO 2025)---we construct a designated-verifier dynamic zk-SNARK with $O(\log n)$ update time, constant proof size, and concrete efficiency. Our construction significantly outperforms Dynalog (both asymptotically and concretely), the only publicly verifiable dynamic zk-SNARK with polylogarithmic update time (Wang et al., 2024). The concrete efficiency of our construction enables, for the first time, an efficient implementation of a dynamic proof of index: Given a digest $d$ of an arbitrary set and a digest $d'$ of its sorted index (e.g., binary search tree), we produce a SNARK proof certifying the consistency of $d$ and $d'$. More importantly, this proof can be updated in sublinear time when the underlying set changes---for example, when an element is modified or inserted, potentially altering the sorted order. We demonstrate applications of designated-verifier dynamic proofs of index to verifiable dynamic database outsourcing, where a client outsources a database and later maintains verifiable indices for efficient query answering, even under arbitrary database updates.

In the formal verification of complexity-theoretic properties of cryptography, researchers have traditionally attempted to capture ``overwhelming truth'' (satisfaction with all but negligible probability) via satisfaction on individual traces of probabilistic execution. However, this approach introduces significant complexity when quantification is present: satisfaction of existential quantification over traces often produces witnesses---such as nonce-guessing oracles---that, without further constraints, may not correspond to meaningful global objects like PPT algorithms respecting causal structure. This discrepancy creates significant obstacles when attempting to combine trace properties, such as reachability, with properties that are defined on non-negligible sets such as computability, or global properties, such as algorithmic indistinguishability. We resolve this by shifting from defining local satisfaction as satisfaction on individual traces to a semantics based on ever-decreasing non-negligible sets. We demonstrate that the logical key to this unification lies in first-order modal logic S4 with \emph{non-negligible sets} as possible worlds, rather than the propositional S5 fragment with \emph{traces} as possible worlds suggested in previous investigations by the Squirrel Prover team. By introducing a PPT computational first-order S4 Kripke semantics and adopting Fitting's embedding for trace properties, we provide a unified quantified treatment of overwhelming truth for trace properties and indistinguishability, together with a first-order calculus, $\mathsf{BC}^+$, whose sole modal operator is the overwhelming-truth bracket $[\,\cdot\,]$. The calculus is sound and, on its fragment, derives exactly the theorems of first-order S4 with persistence; computational completeness holds on the fragment; cut elimination holds propositionally, while at first order every cut is confined to an optimal Barcan shape. We show that Fitting's embedding naturally accommodates the higher-order quantification used in the Squirrel prover by interpreting function types as sorts in a many-sorted first-order logic; this reduces the need for the specialized \texttt{const} predicate and its associated structural restrictions. Finally, using our findings, we present a hybrid semantics for CryptoVampire that eliminates the need for bounded Skolemization.

In this paper, we examine the One-time signature scheme using run-length encoding, as proposed by Steinwandt et al., under the scenario where an adversary is allowed to obtain signatures on two messages before attempting to forge a signature on a third message. Our analysis follows the line of security discussion presented by Groot Bruinderink et al. in their paper “Oops, I Did It Again – Security of One-Time Signatures under Two-Message Attacks.” By considering various attack models and different strategies, we estimate both the attack complexity and the probability of forging a signature. Our results indicate that the signature scheme performs well under a two-message attack, making it an interesting candidate for a few-time signature scheme. Few-time signature schemes such as HORS are a fundamental building block of stateless hash-based signature schemes.

Traditional Proof-of-Work protocols face structural limits in transaction throughput, as scaling block capacity within a serial verification model introduces severe propagation delays and elevates orphan block rates. To address this classical constraint, this paper proposes an asynchronous pipeline consensus architecture that decouples mining initiation from full transaction verification. By embedding a 6-byte compressed UTXO identifier list within an agile Compact Block, nodes can initiate mining on subsequent blocks with reduced delay. This mechanism shifts data latency from a rigid physical bottleneck to a configurable declaration status, introducing a flexible validation framework. Network designers can thereby adjust the dissemination window—defined by the pipeline depth k and mining interval—to adapt to varying block sizes under the Nakamoto security model. Furthermore, we introduce a Dual-Coinbase mechanism that removes mandatory inter-block freezing, thereby unlocking the full potential of the pipeline parameter k and demonstrating applicability to alternative consensus architectures such as PoS, BFT, and DAG. This study establishes a backward-compatible upgrade path for high-performance decentralized ledgers by demonstrating that blockchain scalability can be optimized through the strategic configuration of its minimal consensus payload.

Post-quantum migration must balance two risks: future quantum breaks of classical cryptography and residual uncertainty in newly standardized post-quantum cryptography (PQC). Hybrid Key Encapsulation Mechanisms (KEMs) hedge by combining a classical and a PQC component. Prior work shows that optimized combiners may omit large public inputs from the final key-derivation step, but only if the derived key remains bound to the ciphertext transcript and, in multi-target settings, to the intended recipient; otherwise ciphertext manipulation and cross-recipient amortization at the KDF layer can increase an adversary’s concrete advantage. In practice, these requirements are often conflated, leading either to unsafe secret-only schedules or to unnecessary hashing of large transcripts. We distill practitioner-facing, interface-level guidance by separating ciphertext-to-secret binding from multi-target security, and by adopting ciphertext second-preimage resistance (C2PRI) as a checkable criterion under deployed encodings. We apply this perspective to X-Wing, a hybrid combining ML-KEM with an X25519-based DH-to-KEM under consideration as an IETF Internet-Draft. Under the deployed raw-output interface, we show how distinct classical ciphertexts can yield the same shared secret, motivating hashing of the classical ciphertext in the outer KDF and clarifying when recipient public-key context is needed in multi-target deployments. We also show that similar issues arise for other widely deployed elliptic-curve Diffie–Hellman (ECDH) APIs, including P-256, when they export only partial point information. Finally, we summarize when ciphertext hashing can be omitted, including canonical prime-order abstractions such as Ristretto255 and designs that internalize transcript context via per-component hashing, as in HPKE Diffie–Hellman-based KEM (DHKEM) profiles.

Neural network model extraction attacks pose a serious threat to the intellectual property of deep learning models. While most prior work focuses on Fully Connected Networks (FCNs), effective extraction of Convolutional Neural Networks (CNNs) remains underexplored, particularly in the hard-label setting. In this work, we propose the first systematic method for the recovery of complete CNN parameters in such conditions. By reformulating convolutional layers as sparse Block Toeplitz with Toeplitz Blocks (BTTB) matrices, we extend the model extraction attack method from FCNs to CNNs. The proposed method supports both one- and two-dimensional CNNs, handling scenarios with multiple kernels, multi-channel structures, and average pooling. To enhance computational efficiency and scalability, a kernel-centric clustering algorithm is proposed to exploit kernel parameter sharing, and a Singular Value Decomposition (SVD)-based acceleration strategy is adopted to address the computational cost of large sample sets. Moreover, we perform experiments to demonstrate that our method accurately and efficiently extracts CNN parameters, including multi-channel, multi-kernel and average-pooling layers, with a worst-case relative error of $2^{-17.75}$ and up to $2^{9.26}$ speedup, and recover large models LeNet-5 within practical runtime.

Efficiently masking multiplications in software is a long standing and extensively studied problem. A variety of gadgets have been proposed to perform these multiplications, each offering different trade-offs between efficiency and security. However, almost all existing solutions rely on arithmetic masking, in which multiplications cannot be naturally protected. In this work, we introduce two novel gadgets, named A2S and S2A, that enable conversions between arithmetic masking and Shamir’s Secret Sharing (SSS)-based masking. With this approach, multiplications can be performed naturally and securely in a sharewise manner. We prove that our gadgets achieve SNI security, which provides security guarantees and straightforward composability. Moreover, we demonstrate that composing them with multiplication yields PINI security. We then provide a detailed complexity analysis and discuss the contexts where our gadgets are most relevant. As a case study, we apply them to the MQOM post-quantum signature scheme, a candidate in the second round of the NIST additional post-quantum digital signature standardization process. When computing the sensitive multiplications in MQOM, for masking order t = 1, our approach reduces the number of multiplications, additions, and randomness requirements by 31%, 71%, and 60%, respectively, compared to the state of the art, while incurring only small additional memory overhead. We further show that these gains not only hold but actually increase as the masking order grows. Our results demonstrate that arithmetic-to-SSS conversions provide an effective and scalable path toward efficient masked implementations, making them particularly attractive for postquantum cryptography.

We demonstrate a general and efficient technique to Hensel-lift a solution to a system of ($p$‑adically analytic) equations which may be given implicitly in the form of an efficient evaluation algorithm. Contrary to textbook Hensel lifting, we do not require the equations to be represented explicitly; indeed, our main application uses the method for a system of equations that can be exponentially larger than its representation as an arithmetic circuit: we show how to compute traces of separable elliptic-curve endomorphisms over a finite field $\mathbb{F}_q$ by constructing an approximate lift to $\mathbb{Z}_q$. Our examples include endomorphisms represented as a chain of Vélu, √élu, modular, or radical isogenies, as well as HD‑embedded endomorphisms. The resulting trace-computation algorithm outperforms the state of the art both asymptotically and concretely.

Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form "I am at a location L." Although secure position verification cannot be achieved with classical protocols (even with computational assumptions), they are feasible with quantum protocols. In this paper we introduce the notion of zero-knowledge position verification, which generalizes position verification in two ways: 1. enabling entities to prove more sophisticated statements about their locations at different times (for example, "I was NOT near location L at noon yesterday"). 2. maintaining privacy for any other detail about their true location besides the statement they are proving. We construct zero-knowledge position verification from standard position verification and post-quantum one-way functions. The central tool in our construction is a primitive we call position commitments, which allow entities to privately commit to their physical position in a particular moment, which is then revealed at some later time.

The primary goal of Anamorphic encryption ($\mathsf{AE}$), introduced at Eurocrypt 2022, is to enable private communication even in highly adversarial settings, such as when an adversarial $\textit {dictator}$ "legally" confiscates a user's secret keys (compromising the receiver's privacy) and/or coerces users into sending specific messages (compromising the sender's privacy). To achieve this, $\mathsf{AE}$ embeds hidden additional messages within seemingly innocuous ciphertexts where the sender and receiver comply with the dictator's demands and, in doing so, $\mathsf{AE}$ uncovers novel structural properties of encryption mechanisms. One methodology that extends the capability of a ciphertext is to embed the hidden anamorphic message in the randomness used in encryption. However, not all schemes reveal this randomness as part of the decryption process! Here, we unveil a conceptually simple yet general new methodology that achieves $\mathsf{AE}$. It is based on the concept of $\textit {Trapdoor-Aided Randomness Recovery}$ by which one can generate special key pairs $(\mathsf{pk},\mathsf{sk})$ that are still indistinguishable from honestly generated key pairs but possess an associated trapdoor $\mathsf{td}$ that first allows for randomness extraction from a ciphertext (and nothing more). Secondly, importantly and differently from prior proposals, the new trapdoor should be different from and computationally independent of "the decryption trapdoor key." Primarily, this new methodology allows for a generic construction of $\textit{public-key}~\mathsf{AE}$ which is a notion introduced at Crypto 24, where, to date, the only known public-key anamorphism relied on a specific CCA encryption scheme. Note that public-key $\mathsf{AE}$ eliminates the need for a preliminary private interaction between the receiver and the sender, thus greatly extending the applicability of anamorphism. In addition to obtaining public-key anamorphism, the new methodology, in turn, generically allows for extended anamorphic properties: Specifically and significantly, the methodology allows protections against a dictator that may ask for the randomness employed by the sender. We then show concrete instantiations of the above methodology based on known lattice-based schemes. Specifically, due to the new methodology, we give efficient anamorphic versions of the Dual Regev scheme and the Lindner-Peikert scheme. Technically, we first define a new problem, called $\textit{randomness finding}~(\mathsf{RFinding})$, which requires that even if the adversary obtains the receiver's secret key, then, while it can decrypt, it cannot fully recover the randomness from the ciphertext. Secondly, we reduce the standard LWE assumptions to the hardness of $\mathsf{RFinding}$ for both schemes. Notably, in both schemes we achieve public-key anamorphism utilizing the "trapdoor techniques for lattices" introduced by Micciancio and Peikert at Eurocrypt 2012.

We present the first formally verified implementation of a hash-based signature scheme that is linked to a machine-checked proof of security. Specifically, we provide reference implementations of XMSS and XMSS$^{\textrm{MT}}$ written in Jasmin, targeting the AMD64 architecture. Beyond the implementations, we provide formal EasyCrypt specifications of XMSS and XMSS$^{\textrm{MT}}$, transcribed from RFC~8391, and prove that our implementations adhere to these specifications. Furthermore, for XMSS, we give a machine-checked proof that our specification of RFC~8391 refines the abstract specification proven secure in EasyCrypt by Barbosa, Dupressoir, Grégoire, Hülsing, Meijers and Strub [CRYPTO'23]. In particular, we prove the security of our specification via a reduction, demonstrating that breaking our specification contradicts the [CRYPTO'23] result for our instantiation. Consequently, our implementation is not only functionally correct, but also adheres to a specification that is proven secure. The core technical challenge in our work resides in bridging low-level implementations of TreeHash algorithms with high-level functional specifications used in the pre-existing formalization.

Homomorphic Signatures (HS) enable the authentication of data that has been processed by an untrusted party, allowing a verifier to check the correctness of a computation without access to the original signed inputs. Since their introduction, HS have evolved from algebraically restricted linear schemes to expressive non-linear and Fully Homomorphic Signature (FHS) constructions, spanning diverse cryptographic assumptions and security models. This paper presents a Systematization of Knowledge (SoK) on homomorphic signatures. We organize existing schemes along key dimensions including functional expressiveness, underlying cryptographic primitives, security notions (selective vs. adaptive, single-key vs. multi-key), and privacy guarantees such as context hiding. This unified perspective highlights a fundamental shift from algebraic constructions toward proof-based and post-quantum designs, as well as the growing importance of Multi-Key Homomorphic Signatures (MKHS) for decentralized settings. We conclude by identifying open problems and emerging directions that must be addressed to bridge the gap between theoretical HS constructions and practical verifiable computation.

We show how to improve rank-metric solvers when certain side information (hints) about the secret is available. Concretely, we adapt the kernel search algorithm for MinRank and the GRS algorithm for the Rank Syndrome Decoding problem when some entries in the rank decomposition of the error matrix are known. This setting is motivated by side-channel leakage and cryptographic applications: Mirath and RYDE, two signature candidates in the NIST post-quantum competition, rely on these problems and employ secret keys in this decomposed form. As a main technical ingredient, we give an optimal procedure for guessing a subspace containing the row space of a systematic matrix given only partial knowledge of its entries. Further, we describe a profiling side-channel attack on the reference implementation of Mirath to demonstrate the plausibility of obtaining such hints.

Masking is the standard defense against power-based side-channel analysis (SCA) for cryptographic software, in which sensitive variables are split into independent shares. Although prior work often attributes leakage to microarchitectural effects, architectural interactions alone can already introduce subtle leaks that remain poorly understood. In this work, we propose ISALeak, a target-agnostic framework for analyzing full masked implementations to precisely identify and attribute the root causes of side-channel leakage at the instruction-set (ISA) level. ISALeak complements statistical tests such as TVLA by not only detecting leakage, but also localizing and explaining its source. We evaluate our approach on masked AES and masked Ascon across multiple compiler versions and optimizations. Using power measurements from ASIC (PicoRV32) and FPGA (Ibex) RISC-V cores, we show that 20-40% of the leaks detected by TVLA for masked AES originate from architectural register interactions. For masked Ascon, 17-23% of the observed leakage likewise stems from ISA-level effects and consistently manifests in physical power traces.

Threshold ECDSA has been an active research topic in recent years, driven by its wide-ranging applications, particularly in blockchain domains. In these real-world applications, robustness is a critical requirement. It ensures that a signature is successfully generated as long as $t+1$ honest parties are present, regardless of malicious behavior from others. Existing robust constructions generally fall into two categories: those based on threshold linearly homomorphic encryption (TLHE) and those leveraging the Multiplicative-to-Additive (MtA) paradigm. The TLHE-based approach (e.g., WMC24 in NDSS'24) achieves constant sending communication per party but incurs an expensive online phase. In contrast, the MtA-based approach (e.g., TX25 in S\&P'25) is online-friendly, requiring only elliptic-curve group operations during the online phase. However, it has the drawback of requiring $O(n)$ sending communication per party when $n$ parties are involved. In this work, we propose ARES, a robust threshold ECDSA scheme designed to reduce both communication and computational overhead within the online-friendly MtA framework. To improve the communication efficiency of TX25, we propose verifiable non-interactive multiplication (VNIM), a new primitive which endows standard non-interactive multiplication with public verifiability. Simultaneously, we leverage super-invertible matrices and packed secret sharing to amortize the overall costs. Specifically, when setting the packing parameter of packed secret sharing to $\ell = 1$ (i.e., without secret packing), ARES exhibits linear communication complexity while already achieving an approximately $50\%$ improvement over TX25. When configuring $\ell = t/3$ with $t \ge 12$, ARES achieves lower communication overhead than WMC24, requiring a constant $\approx 4.5\text{ KB}$ per party. Furthermore, setting $\ell = t/2$ reduces the amortized communication cost to roughly $3\text{ KB}$ per party. On the other hand, amortizing across $\ell$ signatures incurs a trade-off by increasing the required party size by $\ell$.

Arithmetic correlations represent the extension of classical correlations into the with-carry setting and serve as a critical performance criterion for pseudorandom sequences constructed via feedback with carry shift registers. The arithemetic correlation values should be as small as possible for application perspective. This paper establishes a sufficient condition for $N$-ary sequences to have ideal arithmetic correlation. Based on this characterization, it is demonstrated that $N$-ary $\ell$-sequences with a prime connection integer $p$ satisfying $p\equiv1(\textup{mod}\:N)$ exhibit ideal arithmetic correlation. Furthermore, under the condition $N^{p-1}\not\equiv1(\textup{mod}\:p^{2})$, this result is extended to the case where the connection integer is a prime power. Additionally, an upper bound is established for the arithmetic crosscorrelation of binary sequences derived from Fermat quotients with coprime periods.

The Merkle-Damgård construction (in its strengthened form as used in SHA-256 and SHA-512, the untruncated members of SHA-2) is not classically indifferentiable from a Variable-Input-Length (VIL) random oracle because of the length-extension attack. Nevertheless, Dodis, Ristenpart, and Shrimpton showed that Merkle-Damgård is publicly indifferentiable, a weaker notion that still justifies replacing a VIL random oracle by Merkle-Damgård in many security proofs when all inputs to a random oracle are public (e.g., Fiat-Shamir and full-domain-hash signatures). In this paper, we show that this replacement fails in the post-quantum setting: (Strengthened) Merkle-Damgård is not publicly indifferentiable from a VIL random oracle against quantum distinguishers with superposition access to the underlying primitive (while construction queries remain classical), even if the compression function is ideally random. We first formalize post-quantum public indifferentiability so that the corresponding composition theorem extends to the quantum random oracle model. We also introduce a post-quantum version of sequential indifferentiability, an even weaker notion. We then prove that (strengthened) Merkle-Damgård satisfies neither notion by showing that an explicit quantum distinguisher achieves non-negligible advantage against any efficient simulator, using Zhandry's compressed-oracle technique. We thus obtain an explicit, conjecture-free separation between an indifferentiability-style notion in the classical setting and its post-quantum analogue.

This paper presents a formal framework for decentralized identity (DID), which achieves both minimal disclosure and session unlinkability under public verifiability. We instantiate this framework as PrivDID. In PrivDID, a user can prove a predicate about a committed attribute via a single ring signature, thereby hiding in an anonymity set dynamically selected from the public ledger. PrivDID builds on Pedersen commitments and binary-range encodings, and is proven secure in the random oracle model. It is fully W3C-compliant and requires no trusted setup. Implementation shows practical efficiency in storage, communication, and computation, confirming real-world feasibility.

Censorship resistance and high throughput are two key benefits of modern multi-proposer BFT protocols. However, in existing designs these two properties are at odds: censorship resistance is typically achieved through duplicating transactions, which in turn harms throughput. This leaves open the question of whether it is possible to improve both properties simultaneously. In this paper, we formally study the trade-offs between censorship resistance and throughput in multi-proposer BFT protocols, where up to $f$ parties may be Byzantine. We present a model for the transaction assignment process, which allows us to classify assignment protocols into meaningful categories. Using this model, we establish fundamental tradeoffs between censorship resistance and throughput. We show that under well-defined conditions, any deterministic transaction assignment protocol that achieves optimal throughput must suffer from $f$ rounds of censorship delay; any deterministic assignment protocol that guarantees every transaction is committed within a constant number of rounds must suffer a factor of $f$ loss in throughput relative to the optimal baseline. On the positive side, we propose and analyze new transaction-assignment protocols that enable flexible choices among throughput–censorship tradeoffs spanning the full spectrum dictated by our lower bounds. In particular, we give a protocol that achieves $\log f$ censorship delay while paying only a factor-2 throughput loss relative to the state-of-the-art MirBFT (EuroSys’23), which incurs $f$ rounds of censorship delay. We further propose randomized assignment protocols that provably break both the deterministic lower bound for the censorship delay and throughput in expectation. All assignment protocols discussed can be integrated with existing multi-proposer protocols within our model as add-ons without modifying the consensus.

This short paper formally specifies and analyzes the UG hybrid KEM construction from the IRTF CFRG’s recent draft on hybrid (post-quantum/traditional) KEMs. The UG construction is an optimized hybrid of a Diffie-Hellman (DH)-based KEM in a nominal group and a generic IND-CCA KEM. The main optimization is that the group elements derived in the DH-based KEM are “inlined” in the key derivation, saving unnecessary hashing. We perform two security analyses of the UG construction: one shows UG is IND-CCA even if the generic IND-CCA KEM is broken; the other complementary analysis shows UG is IND-CCA even if the DH assumptions in the nominal group are broken (by, e.g., a cryptographically-relevant quantum computer).

This work extends the methodology of the Class Elimination Attack (CEA) and the Reference Identities (RI/GRI) used in cryptanalysis for its application to block ciphers like AES and complex SPN variants. Probabilistic results concerning the partitioned key space are generalized to algebraic structures defined over finite fields $ \mathbb{F}_{2^n} $, linking them to the cipher's diffusion and confusion properties. Theorems establishing upper bounds for the expected number of classes to explore as a function of the diffusion capacity are proposed, and a parameterized complexity analysis is provided. The results offer a theoretical framework for evaluating the resistance of symmetric ciphers against attacks based on genetic algorithms and partition optimization.

Masking, the primary countermeasure against differential power attacks, guarantees formal security under abstract execution models that are violated in modern micro-architectures. Meanwhile, processors with out-of-order micro-architectures are increasingly used for high-assurance tasks, yet their physical side-channel leakage remains poorly characterized, hindering side-channel security on such platforms. In this work, we present the first empirical study of physical power side-channel leakage on out-of-order cores. Through practical lab experiments, we identify and validate multiple micro-architectural leakage sources that undermine software masking: register renaming reintroduces register overwrites beyond software control; forwarding leaks through the common data bus, with less impact on security order than in-order forwarding; and concurrent instructions leaks through coupling, with affected instructions determined at runtime. We demonstrate that runtime scheduling and dynamic resource allocation undermine software-only mitigations. To address this, we propose countermeasures that shift part of the responsibility to hardware and require security by design. We further demonstrate that these effects are exploitable in practice by breaking the security of a theoretically secure software-masked lattice-based post-quantum implementation on an out-of-order core. Finally, we find that clock frequency significantly affects leakage of software-masked implementations. This makes security unstable across frequencies and suggests that cryptographic software should be constrained to verified frequencies.

Accordion modes have experienced a surge in popularity, partially motivated by the recent NIST Accordion modes project. None of the existing practical constructions is leakage-resilient by default. In this work, we design a leakage-resilient Accordion mode. We start by presenting a generic analysis of the Encode-then-Encipher (EtE) framework in the leakage-resilient setting, assuming the enciphering is a leakage-resilient STPRP (STPRPl2). We show that the resulting security, while strong, suffers from some limitations. Next, we introduce Motte-and-Bailey, a general framework for building leakage-resilient accordion modes, in the spirit of the PIV construction. Motte-and-Bailey, or MaB for short, is a leveled construction, requiring light assumptions on most of its components to guarantee good STPRPl2, CIML2 and CCAMl2 security. In particular, we require two fully protected calls to a TBC, a collision-resistant hash function (with unbounded or light leakage), and an ideal leakage-resilient PRG, secure against single-trace attacks. Additionally, we present particular instantiations, Qaitbay and Alicante. In Qaitbay the PRG and the hash function are replaced by the Sponge function, while an independent TBC is used for the leak-free calls. Alicante makes use of an ideal cipher, and uses the MDPH hash function and the 2PRG construction, while the leak-free calls are implemented using independent calls to the ideal cipher. We also give three flavours of how to instantiate the TBC inside Qaitbay. Last but not least, we show how to strengthen MaB, Qaitbay and Alicante to also achieve CCAmL2.

Since 2009, the cryptographic community has its eyes fixed on automatic tools based on solvers to help the cryptanalysts trying to attack symmetric cryptographic schemes. Among those automatic tools, TAGADA is dedicated to search for a particular kind of cryptanalysis called differential cryptanalysis. It is of major importance for the cryptographic community to have automatic tools dedicated to the analysis of security of symmetric key primitives to be convince about what symmetric key schemes should be used and what symmetric key schemes should not be used. In this paper, we will see how to extend TAGADA from differential cryptanalysis to boomerang cryptanalysis which is an important kind of attacks in symmetric key cryptography. We will also compare our tool with the two existing ones dedicated to boomerang distinguishers proposed by Hadipour et al. and Derbez et al.

We show reductions and equivalences between various problems related to the computation of the endomorphism ring of principally polarised superspecial abelian surfaces. Problems considered are the computation of the Ibukiyama-Katsura-Oort matrix and computation of unpolarised isomoprhisms between superspecial abelian surfaces.

Decentralized identity is revolutionizing secure digital interactions by giving users control over their personal data. Anonymous credentials (ACs) are fundamental to this paradigm, yet their practical application is hindered by significant usability and efficiency challenges. Existing AC systems often struggle with limitations in predicate expressiveness, privacy protection, and incompatibility with widely adopted legacy signatures based on recommended curves. To overcome these obstacles, this paper introduces a novel AC system named Re2creds. Re2creds establishes a new paradigm of reusable credential presentation, which drastically cuts computational costs by allowing the core of a presentation to be reused across multiple sessions with only lightweight updates. Furthermore, Re2creds incorporates a proof combination mechanism that efficiently supports legacy signatures by moving the most computationally intensive cryptographic operations outside the arithmetic circuit. This approach makes it practical to use credentials based on NIST-recommended curves, removing a critical barrier to real-world adoption. We demonstrate Re2creds’ security properties through a refined UC ideal functionality, accompanied by rigorous proofs. Experimental evaluations demonstrate significant performance improvements over existing schemes: credential generation time decreases by more than 50% when derivingfrom an existing presentation. Additionally, Re2creds makes the presentation of legacy signatures feasible compared to other ACs, which takes less than 1s for a BLS signature based on BN254.

We introduce a simple pairing-based vector commitment with subvector opening where, after a one-time preprocessing, the prover can open a subvector of size $\ell$ in linear time. Our focus is on practically relevant solutions compatible with already deployed setups—specifically, the powers-of-$\tau$ setup used by KZG and many popular SNARKs. We achieve substantial concrete speedups over aSVC (Tomescu et al., SCN 2020), the state of the art in deployable subvector commitments with $O(\ell \log^2 \ell)$ prover and verifier time: our opening is over $60\times$ faster on subvectors of any size; on large subvectors ($\ell \approx$ 64K) our opening and verification achieve $\approx 4000\times$ and $170\times$ speedups respectively (and four times as much with parallelism). Our main result is a construction where: - A commitment is a single $\mathbb{G}_2$ element; a proof is a single $\mathbb{G}_1$ element; - Opening requires $\ell$ point additions in $\mathbb{G}_1$; - Verification is dominated by $2\ell$ $\mathbb{G}_1$ operations. We also describe two variants of our main design that are directly compatible with deployed schemes and where the commitment is a $\mathbb{G}_1$ element; these two schemes show similar speedups over prior work. We additionally support cross-commitment and distributed aggregation, and provide an open-source implementation.

To enhance the diversity of basic hard problems underlying post-quantum cryptography (PQC) schemes, NIST launched an additional call for PQC signatures in 2023. Among numerous candidate schemes, several code-based ones, which have successfully advanced to the second round, are constructed by applying the Fiat--Shamir transform to the parallel repetition of a (relatively low soundness) commit-and-prove sigma protocol similar to the Stern identification scheme. In Fiat--Shamir-based signatures, it is well-known that key material will be leaked if an attacker can somehow obtain what amounts, in the sigma protocol, to the responses to different challenges with respect to the same commitment. This idea is for example at the basis of a famous differential fault attack against deterministic Fiat--Shamir-based signatures like EdDSA. It is usually difficult to mount a fault injection attack based on that principle against a properly randomized Fiat--Shamir-based scheme however (at least with single faults): since commitment collisions are ruled out, it typically involves obtaining the responses to multiple challenges with respect to the same commitment within a single execution of the signature, which is often impossible by construction (e.g., because the extra information will not fit in a single signature, or because it is hard to force the computation of both responses). Due to the comparative inefficiency of signatures based on Stern-like protocols with parallel repetition, candidate constructions are led to use clever compression techniques to reduce signature size, in a way that increases the attack surface for physical attacks. In this paper, we demonstrate this against the LESS signature scheme, which uses so-called GGM trees for signature compression. We propose a simple fault attack on the construction of a binary array used to build the GGM tree, and show that a small number of faulty signatures suffice for full key recovery. We provide a thorough mathematical model of the attack as well as extensive experimental validation with glitch attacks on a ChipWhisperer board, showing that, depending on the target parameter set and the precise fault model we consider, full key recovery can very often be achieved with just one or two faulty signatures, and never more than a couple hundred even in the least favorable scenario for the attacker.

Falcon is a lattice-based signature scheme that has been selected as a standard in NIST post-quantum cryptography standardization project. The trapdoor generation process of Falcon amounts to generating two polynomials, $f$ and $g$, that satisfy certain conditions to achieve a quality parameter $\alpha$ as small as possible, because smaller $\alpha$ usually leads to higher security levels and shorter signatures. The original approach to generate NTRU trapdoors, proposed by Ducas, Lyubashevsky, and Prest (ASIACRYPT 2014), is based on trial-and-repeat, which generates $f$ and $g$ with small Gaussian coefficients and tests whether they satisfy the condition or not. If not, the process is repeated. In practice, $\alpha$ is chosen as 1.17 because it is the smallest value that keeps the number of repetitions relatively small. A recent work by Espitau et al. (ASIACRYPT 2023) proposed a new approach to generate NTRU trapdoors: instead of using trial-and-repeat, sample $f$ and $g$ in the Fourier domain that satisfies the targeted quality and map them back to ring elements. In principle, the idea of Fourier sampling applies to Falcon itself as well, but the sampling region in the Fourier domain for Falcon has a distinct, less elegant geometric shape, which makes sampling more challenging. In this paper, we adopt Markov Chain Monte Carlo (MCMC) methods for sampling. The core idea is to start from an arbitrary point within the target region and perform random walks until the point approximates a random sample from the desired distribution. Specifically, we use Gibbs sampler with Fourier sampling to generate Falcon trapdoors. Our approach allows us to achieve \(\alpha\) values arbitrarily close to 1 efficiently, whereas the original trial-and-repeat method would require impractically many repetitions (far exceeding trillions) to reach even \(\alpha = 1.04\). In particular, Falcon-512 currently falls short of the NIST level one requirement of 128 bits, but our method effectively mitigates this gap. Furthermore, our approach eliminates the need for discrete Gaussian sampling, which is challenging to implement and secure. Instead, our method relies solely on uniform sampling over an interval, simplifying the implementation and improving efficiency.

The Functional Decomposition Problem (FDP) involves expressing a given set of multivariate polynomials as a composition of simpler polynomials. Traditional methods, such as Faugère-Perret’s AlgoFDP and its generalized variant MultiComPoly, rely on Gröbner basis computations on ideals generated from derivatives of composed polynomials h = f ◦ g, where f and g are called left-factor and right-factor of h, respectively. The computational cost of these methods increases significantly with both the number of variables and the degrees of the component polynomials in f and g, and their existing complexity estimates are not sufficiently precise. This paper presents two algorithmic improvements to FDP. First, we replace Gröbner basis computation with Gauss–Jordan elimination (GJE) to convert the coefficient matrix into its reduced row-echelon form (RREF), offering a clearer formulation of a key step in MultiComPoly. The resulting algorithm, named RREFComPoly, integrates this change. Additionally, by using exact binomials in place of original binomial approximations and refining the estimation of a critical parameter, we achieve a tighter complexity bound than that of MultiComPoly. Our second and more impactful contribution, PartComPoly, inverts the conventional FDP workflow. Instead of directly recovering the vector space spanned by the component polynomials of g, PartComPoly first uses a localization strategy to recover f and partial information of g with RREFComPoly, and then iteratively reconstructs g by solving a series of linear systems derived from the obtained f and partial information of g. This inversion dramatically reduces computational complexity and expands the solvable domain of FDP, making previously intractable instances – such as those which were claimed to be not computationally exploitable in [1, page 175] – computationally tractable for the first time. Our experiments have confirmed the correctness and validity of both algorithms RREFComPoly and PartComPoly.

The devastating attacks against SIDH (Supersingular Isogeny Diffie-Hellman) have popularised the practical use of isogenies of dimension $2$ and above in cryptography. Though this effort was primarily focused on dimension 2, $4$-dimensional isogenies, have been used in several isogeny-based cryptographic constructions including SQIsignHD, SQIPrime, (qt-)Pegasis and MIKE. These isogenies are also interesting for number theoretic applications related to higher dimensional isogeny graphs. In 2024, a work by Pierrick Dartois introduced algorithms to compute efficiently chains of $2$-isogenies with Mumford's level $2$ theta coordinates in all dimensions, focusing on cryptographic applications in dimension $4$. In this paper, we improve Dartois' results by providing a simpler and faster method to compute generic isogenies in any dimension, and new computation and evaluation algorithms adapted to gluing isogenies from a product of four elliptic curves, with techniques that generalise a previous work by Max Duparc in dimension $2$. Unlike previous algorithms by Dartois, the algorithms we propose are both easy to implement and naturally constant time. We apply our results to propose the first constant time C implementation of a $4$-dimensional chain of $2$-isogenies, adapted to the qt-Pegasis algorithm and running in less than $25$ ms for a $500$ bit prime. With our new gluing evaluation method, we are able to work fully over $\mathbb{F}_p$ instead of $\mathbb{F}_{p^2}$, allowing further efficiency gains. Indeed, our new formulae accelerate the proof of concept SageMath implementation of qt-Pegasis by up to 19 % for a $500$ bit prime.

The celebrated work of Impagliazzo and Rudich (STOC'89) provides an oracle separation between those primitives implied by a random oracle (RO) and those that imply key agreement and public-key cryptography. For the last 36 years, this result seemed to cleanly separate two worlds: Minicrypt, which is often described as what can be achieved from only ROs, and Cryptomania, which is a world where public-key cryptography exists. This work presents a natural primitive, called an oblivious interactive hash function (OIHF), and shows the following: (1) OIHFs can be constructed from ROs. (2) OIHFs can be constructed from oblivious transfer (OT), and hence they are implied by various well-studied public-key-style assumptions. (3) The existence of an OIHF implies OT, via a non-black-box reduction. Point (1) places the primitive into Minicrypt, point (2) implies that numerous well-studied standard-model complexity assumptions imply that OIHFs exist, and point (3) shows that this primitive circumvents the barrier imposed by Impagliazzo and Rudich. Our results show that a protocol constructible in Minicrypt implies OT. However, this *does not* imply that OT can be constructed from RO; indeed, Impagliazzo/Rudich shows this is impossible. Our non-black-box reduction is well-defined only for standard-model OIHFs, i.e. ones that do not use RO, and at present we can only construct standard-model OIHF in Cryptomania. This is to say that we do not propose an OT protocol that can be constructed from a cryptographic hash function. Rather, our results call into question the value of the random oracle model as an idealization of Minicrypt, and they question where the boundaries of Minicrypt lie.

Fully Homomorphic Encryption (FHE) is a powerful primitive which allows a computationally weak client to outsource computation to a powerful server while maintaining privacy. However, FHE typically suffers from high ciphertext expansion, meaning that the amount of data the client has to send to the server increases by many orders of magnitude after it is encrypted. To solve this problem, the approach known as transciphering consists in combining symmetric encryption with FHE. The most common choice of cipher in this context is the AES, which has been used as a benchmark for transciphering. However, although FHE is typically post-quantum secure, existing transciphering protocols only use AES-128, failing thus to offer security against quantum adversaries. In this work, we construct transciphering protocols based on standard ciphers that offer post-quantum security. For this, we propose algorithms to efficiently evaluate the ChaCha cipher with FHE. We notice that ChaCha is a well-established cipher which even has a standardized version in TLS offering 256 bits of security against classic attackers, thus, 128 bits of security in the quantum world. We show that our solutions have both better latency and throughput than the state-of-the-art transciphering protocol based on AES. Namely, compared with an extended (128-bit PQ secure) version of Hippogryph (Belaïd et al., IACR CiC 2025), in single-core experiments, our running times are up to 11.7 times faster while our throughput is more than 50 times higher.

Succinct zero-knowledge machine learning (zkML) uses zk succinct non-interactive arguments of knowledge (zkSNARKs) to prove neural-network (NN) computations with logarithmic-size proofs. However, general-purpose zkSNARKs do not scale in zkML because compiling matrix-heavy NNs into arithmetic circuits is memory-prohibitive. Existing zkML methods rely on rank-1 constraint systems (R1CS) to hide NN architectures while retaining succinctness. Removing circuit-based representations, it has remained unclear how to hide NN architectures without sacrificing succinctness. Motivated by this gap, we introduce matrix-circuit satisfiability (Mat-Circ-SAT) and a high-dimensional variant of R1CS, termed high-dimensional R1CS (HD-R1CS), for Mat-Circ-SAT. Architecturally, HD-R1CS encodes NN architectures via sparse matrices whose dimensions scale with the number of matrices, rather than with the total number of scalar entries, as in R1CS. Notably, we present zkSMART (zero-knowledge sparse matrix argument via restructuring transform) as a zkSNARK protocol for HD-R1CS. Compared to Evalyn (Asiacrypt '25), which hides the NN architecture using the proof-of-proof technique, zkSMART performs better in concrete prover time for deep NNs. More precisely, for NN computations with $M$ matrices of size $n \times n$, we achieve $O(n^2 M)$ prover time, $O(\log(nM))$ proof size and verifier time, and $O(n^2 M)$ RAM usage with a small constant factor. Such asymptotic efficiency enables our protocol to scale to NNs with up to a billion parameters.

In this work we study quantitative existence results for genus-$2$ curves over $\mathbb{Q}$ whose Jacobians have Mordell-Weil rank at least $1$ or $2$, ordering the curves by the naive height of their integral Weierstrass models. We use geometric techniques to show that asymptotically the Jacobians of almost all integral models with two rational points at infinity have rank $r \geq 1$. Since there are $\asymp X^{\frac{13}{2}}$ such models among the $X^7$ curves $y^2=f(x)$ of height $\leq X$, this yields a lower bound of logarithmic density $13/14$ for the subset of rank $r \geq 1$. We further present a large explicit subfamily where Jacobians have ranks $r \geq 2$, yielding an unconditional logarithmic density of at least $5/7$. Independently, we give a construction of genus-$2$ curves with split Jacobian and rank $2$, producing a subfamily of logarithmic density at least $ 2/21$. Finally, we analyze quadratic and biquadratic twist families in the split-Jacobian setting, obtaining a positive proportion of rank-$2$ twists. These results have implications for Regev's quantum algorithm in hyperelliptic curve cryptography.

Blind signatures (Chaum, CRYPTO 82) are important building blocks in many privacy-preserving applications, such as anonymous credentials or e-cash schemes. Recent years saw a strong interest in building Blind signatures from post-quantum assumptions, primarily from lattices. While performance has improved, no construction has reached practical efficiency in terms of computation and communication. The state of the art requires at least $20$ KB size of communication for each showing of a lattice-based Blind signature to a verifier, and more than $100$ ms in prover time. In this work, we propose an alternative direction with a plausibly post-quantum Blind signature scheme called PoMFRIT. It builds on top of the VOLE-in-the-head Zero-Knowledge proof system (Baum et al. CRYPTO 2023), which we combine with the MAYO digital signature scheme (Beullens, SAC 2021). We implement multiple versions of PoMFRIT to demonstrate security and performance trade-offs, and provide detailed benchmarks of our constructions. Signature issuance requires \(0.45\) KB communication for Blind signatures of size \(6.7\) KB. Showing a Blind signature can be done in $<76$ ms even for a conservative construction with $128$ bit security. As a building block for our Blind signature scheme, we implement the first VOLE-in-the-head proof for hash functions in the SHA-3 family, which we consider of independent interest.

Specified as part of the (standard, optional) M extension, the mul and mulhu instructions reflect support for unsigned integer multiplication in RISC-V base Instruction Set Architectures (ISAs) such as RV32I and RV64I: given w-bit integers x and y for a word size w, they respectively produce the less- and more-significant w bits of the (2 · w)-bit product r = x × y. This typically minimal, and hence RISC-like form contrasts sharply with many alternative ISAs. For example, ARMv7-M includes a rich set of multiply and multiply-accumulate instructions; these cater for a wide variety of important use-cases in cryptography, where multi-precision integer arithmetic is often a central requirement. In this paper, we explore the extension of RV32I and RV64I, i.e., an Instruction Set Extension (ISE), with richer support for unsigned integer multiplication. Our design has three central features: 1) it includes dedicated carry propagation and multiply-accumulate instructions, 2) those instructions allow flexible selection of the radix (thus catering for reduced- and full-radix representations), and 3) the design can be considered for any w, and so uniformly across both RV32I and RV64I. A headline outcome of our evaluation is that, for X25519-based scalar multiplication, use of the ISE affords 1.5× and 1.6× improvement for full- and reduced-radix cases, respectively, on RV32I, and 1.3× and 1.7× improvement for full- and reduced-radix cases, respectively, on RV64I.

The Beneš network can be utilised to apply a single permutation to different inputs repeatedly. We present novel generalisations of Bernstein's formulae for the control bits of a Beneš network and from them derive an iterative control bit setting algorithm. We provide verified proofs of our formulae and prototype a a provably correct implementation in the Lean language and theorem prover. We develop and evaluate portable and vectorised implementations of our algorithm in the C programming language. Our implementation utilising Intel's Advanced Vector eXtensions 2 feature reduces execution latency by 25% compared to the equivalent implementation in the libmceliece software library.

This paper improves quantum circuits for realizing Shor's algorithm on elliptic curves. We present optimized quantum point addition circuits that focus on reducing circuit depth at the cost of using more qubits. Our implementation includes in-place and out-of-place point additions, considering both affine and projective coordinates, respectively. This significantly reduces the circuit depth and achieves about 58%-82% improvement in the qubit count $-$ \(T\)-depth product and 43%-87% improvement in the qubit count $-$ full depth product over previous works, including those of M. Roetteler et al. (Asiacrypt 2017) and T. Häner et al. (PQCrypto 2020). Based on these circuits, we construct Shor's algorithm and evaluate the post-quantum security of elliptic curve cryptography. Under the MAXDEPTH constraint proposed by NIST, which limits the maximum circuit depth to $2^{40}$, the maximum depth in our work is ${2^{28.9}}$ for the P-521 curve. For the total gate count and full depth product, a metric defined by NIST for evaluating quantum attack resistance, the maximum complexity for the same curve is ${2^{65.6}}$, far below the post-quantum security level~1 requirement of $2^{157}$. Beyond these logical analyses, we estimate the fault-tolerant costs (i.e., at the level of physical resources) for breaking elliptic curve cryptography. As one of our results, the P-224 curve (comparable to RSA-2048 in classical security) can be broken in 1.4 minutes using about 107 million physical qubits, or in 14.3 hours using about 670000 physical qubits.

Large Language Models (LLMs) are increasingly deployed as cloud services, raising practical concerns about the confidentiality of user prompts and generated completions. In this paper, we survey privacy-preserving inference solutions for Transformer-based LLMs with the explicit goal of supporting operational choices in real-world deployments. We adopt a strong operational notion of privacy: only the client can read the prompt and the corresponding completion, end to end. The review is organised around the main families of Privacy-Enhancing Technologies (PETs). For each family, we examine representative systems and how they address key bottlenecks in confidential LLM inference, such as non-linear layers and autoregressive decoding. We then compare these approaches in terms of trust assumptions, scalability, and deployment maturity. This comparison characterises the current practical landscape of privacy-preserving LLM inference and motivates a trust-minimising deployment trajectory: from TEE-based solutions that enable large-scale confidential inference today; through crypto-augmented designs that reduce reliance on hardware trust at higher computational cost; toward Fully Homomorphic Encryption as a principled long-term endpoint for non-interactive confidentiality.