International Association
for Cryptologic Research

Threshold signatures have received considerable attention in recent years due to ongoing standardization efforts and deployment in real-world systems. In this work, we prove the universal composability of a wide range of threshold signature schemes, including state-of-the-art protocols compatible with standard signatures used in practice, such as BLS and Schnorr signatures, as well as emerging post-quantum solutions. Importantly, we show UC security without any modifications to the existing protocols.

To this end, we design natural game-based definitions to capture different combinations of main threshold signature scheme properties, such as different levels of unforgeability, adaptive corruption, robustness, and different degrees of preprocessing. These definitions generalize prior definitional work, such as Bellare et al. (CRYPTO'22), and cover a wide range of existing schemes. Moreover, we identify and resolve gaps in prior work. We then express these properties in terms of a UC ideal functionality $\mathcal{F}\text{-}\mathtt{TS3}$. We prove that a threshold signature scheme UC-realizes $\mathcal{F}\text{-}\mathtt{TS3}$ if and only if it satisfies our game-based definitions.

This opens up the usage of (existing) threshold signature schemes in a UC setting, enabling scheme designers to formulate their protocols relative to an ideal threshold signature functionality and use the UC composition theorem to argue security given any concrete instantiation. To further support UC scheme designers and to give further guidance on UC modeling for threshold signatures, we provide additional ideal threshold signature functionalities $\mathcal{F}\text{-}\mathtt{TS2}$, $\mathcal{F}\text{-}\mathtt{TS1}$, $\mathcal{F}\text{-}\mathtt{TSSync2}$, and $\mathcal{F}\text{-}\mathtt{TSSync1}$, which capture fewer properties than $\mathcal{F}\text{-}\mathtt{TS3}$ but are more convenient to use. $\mathcal{F}\text{-}\mathtt{TS2}$, $\mathcal{F}\text{-}\mathtt{TS1}$, $\mathcal{F}\text{-}\mathtt{TSSync2}$, $\mathcal{F}\text{-}\mathtt{TSSync1}$ can also be UC-realized by schemes proven secure according to our game-based definitions.

Through this work, we show that composable security does not require sacrificing performance, but it does require rigor when setting up game-based definitions and ideal functionalities.

End-to-end encryption guarantees message confidentiality but does not hide metadata such as communication patterns among senders and recipients, or their identities. Oblivious Message Retrieval (OMR) is a cryptographic protocol that enables servers to assist recipients in retrieving their messages from a database without learning the mapping between messages and recipients, thereby protecting such metadata.

This paper investigates two central questions of OMR: (1) What is the precise relationship between OMR and the better-studied primitive of Private Information Retrieval (PIR)? (2) Can OMR schemes achieve concrete efficiency comparable to state-of-the-art PIR protocols?

We show that OMR with a property we call strong detection-key-unlinkability is at least as hard as PIR, and that existing OMR constructions already satisfy this property. This PIR-to-OMR reduction has low overhead, suggesting that OMR cannot be made substantially more efficient than PIR.

We then present $\mathsf{UnifOMR}$, which achieves $20\times$ to $1080\times$ faster server runtime over the state-of-the-art $\mathsf{SophOMR}$ under practical parameter settings. For $2^{19}$ messages of 612 bytes each, $\mathsf{UnifOMR}$ completes in only ${\sim}25$ seconds with 4 MB of communication, compared to $>1250$ seconds and 260 KB for $\mathsf{SophOMR}$. These gains come with two trade-offs: an asymptotically linear digest size (albeit with small constants), and two rounds of interaction between the detector and the client.

Furthermore, crucially, $\mathsf{UnifOMR}$ uses batch PIR as a black-box component, which in our experiments accounts for $50$--$92\%$ of the server runtime. Thus, $\mathsf{UnifOMR}$ nearly matches the aforementioned lower bound concretely (for databases of $2^{16}$ to $2^{23}$ messages, each with $612$ to $3060$ bytes), given the status quo of batch PIR.

A non-interactive secure computation (NISC) protocol allows a client with input $x$ and a server with input $y$ to compute $f(x,y)$ using a single message from the client and a single response from the server. The protocol is called succinct if the size of the server’s message depends only on the output length and is independent of the size of $y$ and the complexity of $f$. In the semi-honest setting, succinct NISC is known from fully homomorphic encryption (FHE). In contrast, malicious security is currently known only from non-standard assumptions, such as SNARKs for NP.

In this work, we construct maliciously secure succinct NISC protocols for natural and widely studied functionalities from standard assumptions, namely, FHE and batch arguments (BARGs). Our first result is a protocol for private set membership (PSM): the client holds an element $x$, the server holds a large set $S$, and the function outputs $1$ if and only if $x \in S$. We then give several generalizations: - Dictionary lookup: The server holds a dictionary $D$ of key–value pairs, the client’s input is a key $k$, and the output is $D[k]$. - Verifiable dictionary lookup: The server’s dictionary must additionally satisfy a predicate $P$, computable by a read-once machine with small state. - UP search: The client input is an instance $x$, and the output is $D[w]$, where $w$ is the unique witness for $x$ under some UP relation.

Our protocols achieve split-simulation security against a malicious server and standard security against a malicious client. Split-simulation is a relaxation of the standard real-ideal paradigm, where correctness of the client’s output and indistinguishability of the server’s view are guaranteed separately.

At the heart of our results lies a new simulation technique in which the server’s large input is extracted piece by piece and reconstructed into a coherent input. This reconstruction is enabled by a new monotone coupling argument based on Strassen’s theorem.

In this paper, we propose Titan, an efficient polynomial commitment scheme (PCS) with transparent setup. It achieves commitment time of $O(n)$, evaluation time of $O(\sqrt{n})$ while the proof size and verification scales as $O(\sqrt[4]{n})$. Titan features an order of magnitude smaller proof sizes than hash based PCS, while featuring a significantly more efficient prover and verifier compared to state of the art group based schemes like Dory and Hyrax. To achieve this balance, Titan borrows two-tiered commitments from Dory, and realizes outer commitment using interactive protocols of proximity (IOPP) over groups, specifically WHIR, instead of expensive bilinear pairings. This allows Titan to be instantiated over general curves with discrete-log hardness such as Pasta Curves, instead of requiring pairing friendly curves.

We compile a variant of Spartan protocol for R1CS with Titan PCS to realize a new SNARK, which we call TitanSnark. Our construction TitanSnark preserves the prover efficiency of the existing Spartan protocol, while improving proof size and verification quadratically from $O(\sqrt{n})$ to $O(\sqrt[4]{n})$. Concretely, for circuits of size $\geq 2^{22}$ this results in around $3\times$ more efficient proof size and verification.

Our blueprint of combining IOPPs over groups with Pedersen style inner commitments is of independent interest, as are several optimizations towards efficiently realizing WHIR IOPP over prime-order groups.

Gradient boosted decision trees (GBDTs) are among the most effective models for tabular data and are widely used in domains such as finance, healthcare, and risk assessment. As these models are increasingly trained and served by external providers, clients need a way to check that a prediction or a model update was produced by the claimed training pipeline. At the same time, the provider may need to keep the training data and model parameters private. This makes zero-knowledge proofs for GBDT training and inference a natural tool for accountable machine learning.

Existing constructions for proving GBDT training typically rely on generic ZKP compilers. They build a certification circuit that checks the forest against the training data, and then prove the circuit execution. This leads to high prover cost. On the other hand, a more direct approach to decompose proof of training into algebraic constraints inevitably introduces many auxiliary witnesses to assist proving. Proving these constraints separately could result in a huge amount of independent auxiliary commitments, whose committing and opening could dominate both proof size and prover time. Batching these constraints is also difficult because they come from different stages of training and have potentially different witness shapes and sizes, which are committed over different domains.

We present \textsc{Terrae}, a zero-knowledge proof system for quantized GBDT training and inference based on KZG polynomial commitments. \textsc{Terrae} avoids both dependency on proving circuit computation and proving each constraint separately by leveraging the structure of GBDT training and novelly batching the constraints. We introduce two batching techniques: domain-lifting batching for linear constraints and interleaving batching for non-linear constraints. Both techniques work over differently-sized domains and reduce many constraints to a single claim without introducing extra polynomial commitments. We also design a histogram proof that proves the correctness of converting sample-wise data into its frequency representation, which may be of independent interest. Our evaluation shows that, compared with prior approaches, \textsc{Terrae} significantly reduces proof-generation time while adding only a small proof-size overhead.

PRISM (PKC25) is a hash-and-sign signature scheme whose security relies on the hardness of computing large-prime-degree isogenies originating from a curve of unknown endomorphism ring. In PRISM, the degree of such isogenies is obtained by hashing messages onto a set of large odd integers that pass a primality test.

In this work, we investigate the impact of the choice of primality test on the security of PRISM. We first show that when a weak primality test is used, the assumption underlying the security proof in the standard model does not hold. We then extend our analysis to the assumption used in the security proof in the (quantum) random oracle model. In this setting, we argue that the Miller-Rabin test suffices and estimate the minimal number of iterations required for PRISM to achieve the desired security level, thus minimising signing costs.

Communication locality of an $n$-party protocol measures the maximum degree of the communication graph induced by the protocol execution. While secure multi-party computation (MPC) with small, sublinear locality exists in the static-corruption setting, this goal seems nearly paradoxical in the adaptive-corruption setting: Even against fail-stop adversaries, small neighbour sets of honest parties lie vulnerable to identification and corruption.

Surprisingly, Chandran et al. [ITCS '15] showed that for a single MPC execution, sublinear locality and adaptive security can be simultaneously achieved, assuming honest-to-honest channels are hidden from the adversary. Their solution works in the ``hidden-graph model,'' where a fresh, initially hidden, low-degree graph is being used in each round. In turn, the combined degree grows with every round---inherently limiting the approach to a single-shot MPC execution, and sublinear total rounds. This raises the following question, which is the focus of our work:

Is it possible to maintain sublinear locality over an unbounded number of executions facing adaptive adversaries?

In this work, we provide an affirmative answer in two settings:

First, we consider semi-honest adversaries and information-theoretic security, and construct reusable MPC with polylog($n$) locality.

Second, we consider fail-stop adversaries and computational security, and construct reusable MPC with $\tilde O(n^{2/3})$ locality.

Our results are obtained by devising low-locality protocols while hiding important information about the graph topology, enabling the parties to reuse a single hidden graph. As an independent contribution, this serves as new results for adaptively secure topology-hiding computation (Moran, Orlov, Richelson [TCC '15]).

We propose a costless platform for fair exchange based on smart contracts to favor economic inclusion. Our smart contract is minimal, as most of communication is done offchain. The smart contract costs are covered by incentivized sponsors. Our protocol is a knowledge-coin exchange: it allows to exchange a digital item, characterized by an automatically verifiable description, against a payment in cryptocurrency. The exchange is fair in the sense that either both parties receive what they expect (the exchange completes) or both parties lose nothing (the exchange is canceled). We ensure a costless transaction in cancelation cases, and a transaction with pre-determined fee if it completes. We also ensure privacy of the transaction. Our protocol offers an improvement compared to OptiSwap: we can work with any description function. The complexity is never higher and sometimes significantly smaller. Namely, the worst case complexity is logarithmic instead of being linear. Furthermore, we introduce sponsoring as an enabler for economic inclusion.

In this work, we cryptanalyse the post-quantum signature scheme AIMer v2.1, which is one of the winners of the Korean Post-Quantum Cryptography competition (KpqC), and whose earlier version was a candidate in the US NIST's additional post-quantum digital signatures call. We show that AIM2, the underlying symmetric-key primitive, is not secure up to the claimed level by developing and applying a new algebraic attack framework based on extended linearization over a univariate polynomial ring and a novel algorithm for finding a null vector of a polynomial matrix. In particular misuse scenarios, such as reused-key or related-key settings, our attacks become practically feasible, allowing experimental verification and benchmarking. We also evaluate the approach on the RAIN block cipher used in the Rainier post-quantum signature scheme and obtain improved attacks, although not threatening its claimed security.

Convolutional neural network parameters are valuable intellectual property, yet many APIs expose only top-1 labels and assume hidden logits limit parameter recovery. Prior cryptanalytic extraction can recover functionally equivalent ReLU MLPs, but CNNs introduce weight sharing, parallel critical hyperplanes, coupled spatial perturbations, and channel-sign ambiguity. This paper presents an end-to-end hard-label extraction attack for known-architecture ReLU CNN classifiers with average pooling. The main algorithmic contribution is channel-level recovery with SVGR-guided retained-candidate discrete optimization under a retained-candidate assumption. The attack locates dual points on decision and activation boundaries, recovers shared channel signatures with SVD, resolves channel signs, and peels layers while absorbing ReLU scale factors into later linear layers. Across evaluated 1D MNIST, 2D MNIST, and RGB CIFAR-10 variants, extraction reaches 100% prediction fidelity. Moreover, the evaluation demonstrates downstream security implications: extracted watermarked CNNs preserve behavior-level ownership evidence. Furthermore, the recovered models can be wrapped with deterministic triggers without erasing retained watermark signals, creating risk for both owners and downstream users. These results demonstrate that hiding logits alone does not protect parameters for this CNN family once architecture information is available. The anonymous artifact is available for review at https://anonymous.4open.science/r/cnn_hard_label_extraction-83F4.

Designing threshold lattice-based FHE schemes remains challenging due to the noise leakage that may occur during distributed decryption. The mainstream approach to avoid this consists of relying on noise flooding or smudging techniques. However, using these techniques comes at the cost of the much larger parameters required to ensure reliable decryption, and they are not easily applicable to schemes with smaller ciphertext moduli such as TFHE. In this paper, we demonstrate that smudging can be avoided for LWE-based FHE schemes, such as TFHE, by using a correct Linear Homomorphic Encryption (LHE) scheme, like Paillier, to encrypt the $b$-term of an LWE pair obtained after completing a homomorphic computation and sanitizing the resulting ciphertext. The key intuition is that, because the b-term of the LWE pair is not revealed to the decrypting parties, noise leakage is no longer an issue (with sanitization ensuring noise/message independence). We then instantiate this approach using TFHE as the baseline LWE scheme as well as the Tiresias threshold variant of Paillier. We prove the resulting construction, denoted thPLWE, is IND-CPA secure under static corruption and adaptive queries (Scor-Adp-IND-CPA) under the assumption that Tiresias achieves the same. We then provide experimental results to assess the practicality of the approach and compare it to other recent works.

Although automated symbolic protocol verification has proven valuable and effective, current approaches begin to reach their limits: While small protocols can be analyzed automatically, the most complex case studies often require substantial expert time and resources. There have been many attempts to solve this problem by compositional verification, but they rely on unrealistic protocol assumptions and do not support real-world security properties like Forward Secrecy.

In this work, we enable compositional symbolic analysis for real-world security protocols with respect to modern security properties. We develop a composition result in the Applied π-Calculus that holds even in the presence of attackers capable of dynamic corruption if the protocols satisfy a disjointness requirement.

We demonstrate the applicability and effectiveness of our result on the composition of a data exchange protocol with a Diffie-Hellman key exchange and a compositional analysis of Forward Secrecy in TLS 1.3 within the scope of RFC 8446 and the ECH extension. While monolithic analyses of TLS 1.3 with ECH fail to deliver a result in 10% of cases, all compositional analyses succeed. Additionally, runtime decreases by 71% and memory usage by 86% on average.

Mechanized cryptographic proofs face a long-standing trade-off between assurance and expressiveness. Existing foundational frameworks, which reduce every proof step to the kernel of a general-purpose proof assistant, offer a small, auditable trusted base, but struggle to model the oracle manipulations and rewinding arguments pervasive in modern cryptography. They also tend to lack the tactic infrastructure of specialized, non-foundational tools like EasyCrypt.

We present VCVio, a foundational framework in Lean 4 that closes both gaps with established ideas from programming-language theory: algebraic effects and handlers on the oracle side, and a modular relational program logic on the tactic side. Concretely, a computation with oracle access is the free monad over the polynomial functor determined by the oracle specification, exposing its interaction history as an explicit syntax tree. Caching, logging, reprogramming, and seed pre-sampling become handler combinators; rewinding reduces to deterministic transcript replay without any internal adversary state.

On top of the oracle core, VCVio provides two reusable layers. We extend the recent Loom framework (POPL 2026) to the relational setting, yielding a single tactic framework that handles both unary and relational probabilistic reasoning. Alongside this, our treatment of state-separating proofs achieves compositional separation by typing, whereas Nominal SSProve recovers it by quotienting locations modulo alpha equivalence.

We exercise this stack on three case studies: a random-oracle commitment scheme; the Bellare--Neven forking lemma, mechanized without the rewindability axioms used in the recent EasyCrypt formalization by Firsov and Janků; and the Schnorr signature scheme establishing EUF-CMA security. A significant share of our development used LLM coding agents and external automated proof-search systems; we report on the workflows, successes, and failure modes as a data point in LLM-assisted theorem proving.

DAG-based Byzantine fault-tolerant (BFT) consensus protocols achieve high throughput by allowing many validators to propose concurrently, but scaling them to large committees remains challenging. In a committee of $n$ validators, up to $f$ of which may be Byzantine ($n = 3f{+}1$), dense round-based DAG designs require each block to reference at least $2f{+}1$ blocks from the previous round. This yields $O(n)$ metadata per block, $O(n^2)$ metadata per round, and $O(n^3)$ metadata bytes transmitted per round under all-to-all dissemination, increasing bandwidth and processing costs and making metadata, rather than payload, the latency bottleneck.

We present Bluestreak, a sparse uncertified DAG BFT consensus protocol that keeps non-leader blocks constant-size (in $n$) and concentrates committee-scale ancestry in a single leader block per round, yielding constant \emph{average} metadata per block as committees grow. Bluestreak combines this sparse block format with a new leader commit rule co-designed for the sparse DAG and a new pull-based pacemaker, and we prove safety and liveness under partial synchrony using only collision-resistant hashes and standard digital signatures.

We implement and evaluate Bluestreak under wide-area latency spanning ten geo-distributed regions. Bluestreak scales from 10 to 400 validators on commodity 4-vCPU instances with sub-second WAN latency throughout (${\approx}\,470$ ms at $n{=}10$, ${\approx}\,720$ ms at $n{=}400$), keeping average per-block metadata constant at ${\approx}\,320$ bytes. At $n{=}120$, Bluestreak sustains ${\approx}\,220$k tx/s with LSM-tree storage and ${\approx}\,400$k tx/s with WAL-based storage, both at sub-second latency.

Substitution-permutation networks (SPNs) are the most popular construction method for block ciphers and sponge permutations. Basically, we can divide SPNs into two groups by considering their diffusion layer profiles: bit-wise versus byte-wise (or nibble-wise) diffusion. In this paper, we suitably combine both approaches and present a more efficient and flexible construction that achieves a combination of small S-boxes, linear layers consisting only of XOR operations and bit permutations, and a small number of rounds. As concrete results, we present the family SEFA of several lightweight and flexible block ciphers, AEADs, and cryptographic hash functions, including:

* SEFA-128/256: A TFHE-friendly block cipher with 128-bit block, 256-bit key, using 4-bit S-boxes, through 16 rounds.

* SEFA-512/256: A wide-block AEAD suitable for encrypting 256-bit blocks with 256-bit keys, using 8-bit S-boxes, through 16 and 10 rounds.

* SEFA-1536: A hash function using sponge construction with a 1536-bit state permutation including 8-bit S-boxes and 12 rounds.

We analyze the security from several attack perspectives. Also, we present hardware implementation results, along with comprehensive performance benchmarks, to demonstrate performance and flexibility.

There are two kinds of cryptographic group actions: restricted and unrestricted. While unrestricted actions like (qt-)PEGASIS are needed for more advanced constructions, restricted ones like dCTIDH are sufficient for instantiating a NIKE and usually much more efficient.

In this work, we propose CORAL, a significantly faster algorithm to evaluate the same action as (qt-)PEGASIS, but in a restricted fashion; CORAL only computes two-dimensional $2$-isogenies to evaluate the action and outperforms both recent unrestricted (KLaPoTi, (qt-)PEGASIS) and (restricted) CSIDH-based approaches (SQALE, dCTIDH). In essence, CORAL trades off unrestrictedness for efficiency.

Our unoptimised C implementation evaluates a group-action in 240 ms with a 2032-bit prime. When used to construct a non-interactive key exchange, CORAL yields an actively secure post-quantum NIKE with compact public keys (e.g. 256 bytes for 2032-bit primes).

ML-DSA is a lattice-based signature scheme that has recently been standardized by NIST as FIPS 204. Among the many subroutines used by ML-DSA are the high bits (Hb) and low bits (Lb) functions, which, as their name suggest, return only the higher bits or the lower bits of some integer. Recently, Seck and Roux-Langlois (IACR CiC 2025) conjectured that the high bits of a sum of two integers t and r can be expressed as the sum of the high bits of each integer, plus an error term that can take at most seven different values. In this paper, we study the properties of the functions Hb and Lb and we prove that the conjecture of Seck and Roux-Langlois holds. In addition, we provide a complete characterization of the error term. As an application, we explain how these properties can be used to design lattice-based signature schemes with advanced features.

Rotating leader Byzantine fault-tolerant (BFT) protocols, also known as protocols in the leader-speaks-once (LSO) model, have become a topic of interest with the rise of blockchains. Many recent efforts have been made to lower the latency and simplify the design. However, existing works often sacrifice expected latency (latency when failures might occur) to enjoy higher good-case latency.

In this work, we present a generic approach to building rotating leader BFT protocols that are both simple and fast. We present two variants: HumBird-1, a synchronous BFT under the $f

The selfish-mining literature has progressively lowered the hashrate threshold at which a rational Bitcoin miner strictly profits by deviating from the honest protocol, from Eyal and Sirer's 25% down to single digits under richer attacker models. Two such models remain unreconciled: Gervais et al. (CCS 2016) parameterize network-layer adversaries through an eclipse fraction omega and an honest-only stale rate o, but assume constant block rewards; WeRLman (IEEE S&P 2023) models fee-rich rewards through a deep-RL solver, but assumes a network-clean attacker. An adversary that exploits both surfaces has not been analyzed.

We present the first joint analysis. We formulate a Markov decision process that integrates Gervais's network-layer channels with WeRLman's whale-transaction tracking, solve it at a 5.7 x 10^8 state truncation, and anchor the construction by reduction to each prior model at the appropriate parameter limit.

Our threat model targets a state-level adversary with per-block routing influence over a meaningful fraction of honest hash power, not an attacker who eclipses individual nodes. Under this model, the joint threshold collapses far below either single-channel result. At L = 3, the F=10 baseline (no network channels) crosses at alpha = 13.2%; a 10% eclipse fraction alone drops it to 2.6%, a 10% stale rate alone to 4.8%, and both channels together to 1.4%. At L = 5 the joint configuration drops further to 0.9%, an at least 15x collapse. An analytical lemma accounts for the interaction: the honest-chain growth probability factors as (1 - alpha - omega)(1 - o), isolating a cross-term omega * o that is a property of the joint transition kernel itself. The cross-term is structural, not a training artifact, and its presence implies that mitigations targeting only one channel leave the joint contribution structurally present whenever the other channel is non-zero.

The security of decentralized asset custody and blockchain consensus increasingly relies on threshold signatures to eliminate single points of failure. In these high-stakes environments, static security models are an insufficient theoretical abstraction. Real-world blockchain deployments demand adaptive security to ensure protocols remain secure against adversaries who reactively compromise participants based on observed network traffic and protocol state.

While the NIST standardization effort and Bitcoin’s Taproot (BIP340) upgrade have accelerated interest in adaptively secure threshold Schnorr signatures, a threshold system is only as secure as its setup phase. In decentralized settings, this necessitates a Distributed Key Generation (DKG) protocol to eliminate reliance on a trusted dealer. However, a critical gap remains: current DKG protocols are incompatible with the specific key structures required by promising schemes (EUROCRYPT'26). Furthermore, a result from CRYPTO'25 demonstrated that unique key commitments necessitate a non-falsifiable assumption for adaptive security. To avoid non-standard assumptions, DKG protocols must be key-share hiding, a property existing DKGs fail to provide.

We close this gap by proposing two novel DKG protocols that support identifiable abort and tolerate a dishonest majority and prove them secure under new ideal functionalities in the UC framework. Our first protocol achieves optimal round complexity via a single broadcast round at the cost of allowing adversarial bias, while our second protocol eliminates the bias in two rounds. In addition, the protocols provide a proactive key refresh mechanism that allows long-lived decentralized networks to refresh internal key material periodically. This enables the system to recover from transient node compromises without the operational burden of rotating the underlying public key. Our evaluation demonstrates that these constructions are practically efficient, incurring minimal communication and computation overhead for modern high-throughput architectures.