We present the No IC Encryption (NICE)-PAKE, a (semi)-generic symmetric Password Authenticated Key Exchange (PAKE) framework providing a quantum-safe alternative for the Ideal Cipher (IC), utilizing simpler cryptographic components for the authentication step. To give a formal proof, we introduce the notions of A-Part Secrecy (A-SEC-CCA), Splittable Collision Freeness (A-CFR-CCA) and Public Key Uniformity (SPLIT-PKU) for splittable LWE KEMs. We show the relation of the former to the Non-uniform LWE and the Weak-Hint LWE assumptions, as well as its application to Ring and Module LWE. Finally, we show how to obtain a secure PAKE from our construction with concrete parameter choices for lattice KEMs.

The sum-check protocol serves as a fundamental building block in succinct arguments, yet its security guarantees are typically formalized in a manner intimately tied to the encompassing protocol, impeding modular analysis and design. We address this limitation by introducing a functional perspective that characterizes sum-check via the \emph{repulsive verifier property}: the verifier's output function is repelled from any polynomial whose hypercube sum differs from the claimed value. This property is intrinsic to sum-check and holds independently of any external binding mechanism or commitment scheme. Dually, we identify an \emph{attractive verifier property} inherent to the FRI protocol: provided the input word is sufficiently close to a codeword (i.e., a Reed-Solomon encoding of a polynomial), the verifier either outputs the evaluation of that polynomial at the random challenge point or aborts. These dual properties---repulsiveness and attractiveness---yield a clean, modular methodology for analyzing protocols that interleave sum-check with other components. We demonstrate the efficacy of this methodology through three applications. First, we provide a modular analysis of BaseFold that directly exploits these functional properties, circumventing the need for monolithic security arguments. Second, we show that BulletProofs can be decomposed into a repulsive sum-check and a computationally attractive component, leading to a simpler security proof. Third, we construct $\mathsf{Bird}$, a new polynomial commitment scheme that simultaneously achieves transparency, homomorphic commitments, and double efficiency by composing these functional building blocks, thereby illustrating that our approach facilitates the systematic design of novel cryptographic protocols.

Byzantine fault-tolerant (BFT) protocol from delegated committee is an approach in improving the performance and scalability of blockchains. Notable industrial examples include Delegated Proof-of-Stake (DPoS) by Tron, Polkadot, and Solana, and Proof-of-Staked-Authority (PoSA) by Binance. In these protocols, a subset of nodes is first selected to form a committee, then the committee members reach an agreement and disseminate the results to all nodes. Although these approaches allow the committee members to be rotated periodically, the security of the system is built upon a strong assumption that no committee can have more than certain fraction of faulty nodes (e.g., one-third in a partially synchronous network). In this paper, we provide a revamped two-stage design to model BFT from delegated committee without making the strong assumption. Namely, the only assumption is that in a partially synchronous network, the entire system does not have more than one-third faulty nodes. We propose rBFT, a practical BFT protocol that has a fast path where only committee members participate and a slow path where all nodes in the system are involved. We show that, not surprisingly, the fast path is extremely fast, and under reasonable assumptions such as alive-but-corrupt nodes and rational nodes, only fast path can be triggered. Meanwhile, even under conventional Byzantine failures where the slow path is triggered, our protocol is still practical enough.

The use of small fields has come to typify the design of modern, production-oriented SNARKs. In this work, we treat multilinear polynomial commitment over tiny fields. A tiny-field polynomial—in the nomenclature of Diamond and Posen (EUROCRYPT '25)—is defined over a field that has fewer elements than the polynomial itself has coefficients. We focus on multilinears over the field with just two elements. In this work, we generically reduce the problem of tiny-field commitment to that of large-field commitment. We introduce a sumcheck-based compiler—called "ring-switching"—which, upon being fed a multilinear polynomial commitment scheme over some large extension field, yields a further scheme over that field's ground field. The resulting scheme lacks embedding overhead, in that its commitment cost, on each input, equals that of the large-field scheme on each input of identical size (in bits). Its evaluation protocol's overhead is linear for the prover and logarithmic for the verifier, and is essentially optimal. Instantiating our ring-switching reduction on the BaseFold (CRYPTO '24) large-field multilinear polynomial commitment scheme—or more precisely on a characteristic-2 adaptation of that scheme that we develop at length—we obtain an extremely fast polynomial commitment scheme for bit-valued multilinears. Our scheme outperforms its state-of-the-art peers, a fact we demonstrate experimentally.

We introduce YsPIR, a single-server private information retrieval (PIR) protocol that improves upon the state-of-the-art KsPIR protocol by Luo, Liu, and Wang (CCS 2024) in server response time and offline communication. YsPIR is built on a new first-dimension folding technique, which reduces online computation time and decreases the public-key material required in the offline phase. Our approach has three main advantages. First, it enables the most resource-intensive computations to be preprocessed offline, thereby reducing online response time. Second, its offline communication is independent of the database size and remains small. Third, it maintains low communication cost even under high-throughput settings. We conduct comprehensive experiments to evaluate the concrete performance of YsPIR. The results show that YsPIR achieves approximately 1.64x higher online throughput and reduces offline communication by about 3.09x compared with KsPIR.

Protocols for Byzantine agreement are known to be constrained by relatively strong lower bounds on their optimal resilience, round complexity, and communication complexity. Crucially, though, these lower bounds do not immediately rule out the possibility of protocols that are faster and use less communication when the actual number of faults $f$ is less than the maximum number of faults $t$ that can be sustained. Early-stopping protocols terminate in a number of rounds proportional to $f$ (rather than $t$); likewise, protocols with adaptive communication incur asymptotically less communication when $f$ is less than $t$. We present a randomized, early-stopping Byzantine agreement protocol with adaptive communication complexity that terminates in $O(f+1)$ rounds with bit complexity $O((f+1)n\kappa)$ for a failure probability of $2^{-\kappa}$ in a synchronous network with $t<n/2$ faults, assuming a Public Key Infrastructure (PKI). This is achieved against a strongly adaptive adversary, i.e., the attacker can observe all messages in round $r$, then choose which parties to corrupt in round $r$, and then remove or alter the round-$r$ messages of corrupted parties.

Directive (EU) 2019/1937 mandates reporting channels that do substantially more than accept a one-shot anonymous report submission. A compliant system must protect the confidentiality of the report and the reporting person, restrict submission to entitled persons, enforce prescribed workflows under statutory deadlines, and maintain auditable records of the reporting process. Existing whistleblowing tools typically address only fragments of these requirements, often reducing the problem to an anonymous inbox or web form. To our knowledge, no existing system addresses whistleblowing's full procedural and security requirements within a single integrated design. We adopt a compliance-driven approach in which the Directive is treated as a normative source of system requirements rather than as background motivation. From Directive-mandated procedures, assets, and threats we derive, we propose a threat model, a set of security goals tailored to directive-compliant whistleblowing, and formalize the whistleblowing process. We then propose a concrete Whistleblowing System architecture that separates enrollment from reporting and builds on an Auditable Log Service (ALS) with an Identity Management Component (IMC). Our design supports report pseudonyms tied to entitled persons, controlled identity disclosure, and confidential yet accountable communication. It enforces an auditable workflow that separates procedural handling from merits-based processing and enables a practical deployment model deployable at both state and organization level that distributes trust across multiple entities, lowers adoption barriers through shared infrastructure, and supports two-level auditing of both procedural compliance and merits-based handling for dispute resolution.

Threshold public-key encryption schemes enable decryption only with the participation of enough partial secret key holders. In this article, we propose the first dedicated protocol for distributed decryption of HQC ciphertexts. This protocol is perfectly correct and does not leak any information about the shared secret key. This leads to the first threshold cryptosystem based on HQC. To this end, we present protocols for securely decoding shared erroneous words of both Reed-Muller and Reed-Solomon codes. Such decodings require to develop novel techniques for specific multiparty computations in fields of characteristic 2. For distributed Reed-Muller decoding, we develop a majority computing protocol. For distributed Reed-Solomon decoding, we propose a novel protocol for securely solving Padé approximants over shared polynomials. Beyond their immediate application to HQC, our results enable new techniques in secure distributed computation over structured algebraic objects, and may find independent applications in advanced cryptographic protocols.

Softmax is widely used in deep learning to map some representation to a probability distribution. As it is based on the exponential function, which is relatively expensive in multi-party computation, Mohassel and Zhang (S&P, 2017) proposed a simpler replacement based on ReLU (the maximum of the input and zero) to be used in secure computation. Later works (e.g., Wagh et al., PETS 2019 and 2021) used the softmax replacement not for computing the output probability distribution but for approximating the gradient in backpropagation. In this work, we analyze the two uses of the replacement and compare them to softmax, both in terms of accuracy and cost in multi-party computation. We found that the replacement only provides a significant speed-up for a one-layer network, while it always reduces accuracy, sometimes significantly. Thus, we conclude that its usefulness is limited, and one should use the original softmax function instead. We also present a novel protocol for secure exponentiation that reduces communication up to fourfold while preserving accuracy when used for softmax.

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.

Linear error-correcting codes play a crucial role in building practical non-interactive arguments of knowledge (SNARKs) with transparent setup, and plausible post-quantum security. Basically, the key to practical efficiency is a linear code with a concretely fast encoding and a high minimum distance. However, to date, none of the candidate codes achieves the best of the two worlds: codes with provable high minimum distance, e.g., Reed-Solomon codes, suffer from quasi-linear time encoding, while linear-time encodable codes, e.g., Spielman's code, have low provable minimum distance. In this work, we resolve this problem by explicitly constructing a family of Quasi-Abelian (QA) codes over {\em arbitrarily} large prime fields with concretely high minimum distance and practically efficient encoding algorithms. At the heart of our technical contribution is a fine-grained analysis on the concrete minimum distance of random QA codes of rank $1$ and index $c$ over group ring $\mathbb{F}_p[\mathbb{Z}_2^n]$. We show that in practical regimes it attains the well-known Gilbert-Varshamov bound up to a small constant gap $n/(c\log_2{p})$. Concretely, with probability $\ge1-2^{-127}$, our random QA code over a $128$-bit sized prime field with $n=20$, achieves relative minimum distance at least $0.4142,0.6070,0.7040$ for code rate $1/2,1/3,1/4$, respectively. In comparison, Spielman's code only achieves a minimum distance $0.1$ for code rate $1/2$ in the same setting by the state-of-the-art analyses. We give practically efficient encoding algorithms for QA code over $\mathbb{F}_p[\mathbb{Z}_2^n]$ by leveraging Walsh-Hadamard Transform. Specifically, for code length $c\cdot 2^n$ and rate $1/c$, our encoding only needs $cn\cdot 2^n$ additions/subtractions and $(c-1)\cdot 2^n$ multiplications over $\Fp$, which turns out to be concretely faster than Spielman's code. For encoding a message of length $2^{20}$ over a $256$-bit prime field, our QA code with rate $1/2$ only takes $250$ ms, while Spielman's code with rate $0.65, 1/2$ needs $410$ ms, $890$ ms, respectively. We then follow the framework of Brakedown (CRYPTO 2023) to build SNARKs over large prime fields from QA codes. For proving ECDSA verification over the scalar field of Curve25519 ($\approx 2^{16}$ constraints), our SNARK needs only $1.44$ second in proving, $0.08$ second in verification, and a proof size of $3.2$ MB. In comparison, Brakedown needs $1.6$ second, $0.24$ second, and $7.48$ MB, respectively.

The development of succinct non-interactive arguments of knowledge (SNARKs), which maintain a constant proof size regardless of computational complexity, has led to substantial improvements in both the scalability and privacy of verifiable computations. By enabling efficient verification of complex computations without revealing sensitive data, SNARK systems underpin modern applications ranging from privacy-focused protocols to high-performance blockchain infrastructures. This work presents a generalised specification for a Multi-Party Computation (MPC) setup ceremony designed to generate structured reference strings for non-transparent, pairing-based zk-SNARKs. Building on the MMORPG framework of Bowe, Gabizon, and Miers, we design a unified MPC protocol that accommodates multi-dimensional parameter structures required by contemporary SNARK designs. While our methodology is applicable to a broad class of structured CRS constructions, the Tokamak zk-SNARK serves as a motivating example illustrating the need for such a generalisation. The proposed ceremony supports universal and circuit-specific parameter generation, enabling reuse of CRS components across multiple instantiations while maintaining strong soundness guarantees under the presence of at least one honest participant. The protocol operates in two phases: (i) a universal ``Powers of "tau''-style phase generating parameter sets independent of circuit topology; and (ii) a circuit-specialised phase derived from a subcircuit-based universal circuit paradigm. For both phases, we formalise complete computation and verification procedures, including proof-of-knowledge mechanisms, cross-parameter consistency checks, and structured multivariate parameter updates. Optional integration of a random beacon---as in the MMORPG construction---is supported to enhance unpredictability and public auditability without altering the core security assumptions. Overall, this work provides a modular, extensible, and publicly verifiable MPC framework suitable for SNARK systems requiring structured, multi-parameter CRS generation, while Tokamak serves as a practical motivating instance of the broader methodology.

This paper presents OnionPIRv2, an efficient implementation of OnionPIR incorporating standard orthogonal techniques and engineering improvements. OnionPIR is a single-server PIR scheme that improves response size and computation cost by utilizing recent advances in somewhat homomorphic encryption (SHE) and carefully composing two lattice-based SHE schemes to control the noise growth of SHE. OnionPIRv2 achieves $3.7 \times$ response overhead for $3$ KB entries and up to $1372$ MB/s server computation throughput in our evaluation.

In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes. In this paper, we introduce DYNARK, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. DYNARK is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting, for an R1CS of size $n$, after a preprocessing of $O(n\log n)$ group operations on the original witness, it only takes $O(d)$ group operations and $O(d\log^2 d)$ field operations to update the proof for a new witness with distance $d$ from the original witness, which is nearly optimal. In the fully-dynamic setting, the update time of DYNARK is $O(d\sqrt{n\log n})$ group operations and $O(d\log^2 d)$ field operations. Both the proof size and the verifier time are $O(1)$, which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from $O(\sqrt{n})$ to $O(1)$ without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of DYNARK are faster in practice. Experimental results show that for $n=2^{20}$, after a one-time preprocessing of 74.3 seconds, it merely takes 3 milliseconds to update the proof in our semi-dynamic zkSNARK for $d=1$, and 60 milliseconds to update the proof in our fully-dynamic zkSNARK. These are 1433$\times$ and 73$\times$ faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 milliseconds. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.

The DKLs23 protocol (Doerner, Kondi, Lee and shelat, IEEE S&P '24) is a state-of-the-art multiparty ECDSA signing protocol. Due to its exceptional combination of simplicity, efficiency, and statistical UC security within an elegant hybrid model providing access to standard ideal functionalities, it is rapidly seeing widespread adoption. We provide a comprehensive security analysis of the DKLs23 protocol, showing that although it is not statistically secure as originally claimed, it is nevertheless computationally secure, and can be made statistically secure via a lightweight refinement. Our contributions are as follows: -- Statistical insecurity: Within the hybrid model utilized for the original analysis, we construct a computationally-unbounded "split-view" adversary that successfully attacks the protocol by causing two or more honest parties to output different valid signatures on the same message (specifically, signatures with independent nonces). Considering any ideal ECDSA signing functionality that outputs a single signature per session, such an attack cannot be simulated in the ideal model, and thus the protocol is not statistically secure. -- Computational security: We prove that the protocol is nevertheless computationally secure based on the assumption that ECDSA is strongly unforgeable up to sign (i.e., up to the trivial $(r, \pm s)$ malleability), as defined by Groth and Shoup (EUROCRYPT '22). Specifically, complementing our split-view attack, we show that any adversary for which the protocol's execution is distinguishable from its ideal-model simulation can be efficiently transformed into an algorithm that breaks the strong unforgeability up to sign of ECDSA. -- A refined statistically-secure protocol: Identifying the root cause of our split-view attack, we present a refined protocol that is statistically secure. Our refinement incorporates a lightweight consistency check, where each party sends a single group element as part of the protocol's third-round message. Our refinement additionally introduces a relaxed zero-sharing functionality that serves as a drop-in replacement for the original protocol's zero-sharing functionality. We show that this relaxed functionality can be unconditionally realized by a simple one-round protocol (executed in parallel with the first round of signing) without a dedicated setup or pre-shared seeds. Consequently, when paired with a compatible (e.g., Paillier-based) VOLE instantiation, this eliminates the need for long-term secure pairwise storage across the entire signing protocol.

A recent work by Hanzlik et al.~(Asiacrypt'25) introduced Tanuki, a family of blind-signature frameworks based on non-commutative cryptographic group actions. Tanuki develops new techniques to obtain concurrently secure blind signatures, and admits compact instantiations in two distinct regimes: (i) an isogeny-based instantiation from the CSI-FiSh group action with signatures of about 4.5 KB, and (ii) a code-based instantiation from LESS and the code-equivalence group action with signatures around 64 KB. To the best of our knowledge, these are the first efficient blind-signature constructions in the isogeny- and code-based settings that support concurrent executions. Despite this advance, the Tanuki frameworks rely on a non-standard and interactive assumption, namely the so-called ``one more'' vectorization assumption. Given several structural attacks and vulnerabilities discovered in various group action instantiations, relying on non-standard assumptions can raise concerns. In this work we present a new framework building upon Tanuki's techniques that achieves concurrent security while achieving better performance, and relying only on the standard group action hardness assumption, the vectorization problem (also known as the group action inversion problem). For the LESS instantiation, we apply dedicated code-based techniques to reduce signature sizes by a factor of 14.5. These improvements come with rigorous reductions to the standard problem, do not weaken the security claims, and are directly applicable to the LESS instantiations of Tanuki. As a result, our isogeny-based and code-based instantiations yield signature sizes of 8.89 and 8.84 KB, respectively, and retain concurrent security under the standard group-action inversion assumption.

Random Vector Oblivious Linear Evaluation (VOLE) correlations are a widely used backend for zero-knowledge proofs and secure computation, and can now be generated with strong concrete efficiency. Many applications, however, need correlations on the receiver’s actual input. They therefore start from random VOLE and send a linear-size derandomization vector, which remains a main communication bottleneck. We study chosen-input VOLE (CI-VOLE), where the receiver privately chooses a large vector \(\mathbf{x}\), the sender fixes \(\Delta\), and the parties obtain shares of \(\mathbf{x} \cdot \Delta\) without communicating a linear-size object. This work presents \(\textsf{LogVole}\), a concretely efficient CI-VOLE protocol with polylogarithmic end-to-end communication under Ring-LWE. The construction uses a recursive shrink/expand design: it authenticates short digests of the chosen input and then uses a succinct telescope to expand those relations back to the full vector. The protocol has \(O(\lambda \log^2(|\mathbf{x}| + m_{\mathrm{msg}}))\) one-time setup and query communication and \(O(|\mathbf{x}|/n)\) ring operations. Here, \(n\) is the underlying ring degree, \(\lambda\) is the computational security parameter, and \(m_{\mathrm{msg}}\) is the size of the shares. \(\textsf{LogVole}\) also supports a public-key non-interactive mode: for a fixed \(\Delta\), the sender publishes reusable parameters, and a receiver sends one compact \(\mathbf{x}\)-dependent message to obtain the matching VOLE shares. This gives a route to non-interactive VOLE-based ZK with polylogarithmic communication for arbitrary circuits. We also give a malicious-security extension in the random oracle model. Using \(\textsf{LogVole}\), we obtain the first concretely efficient VOLE-based ZK protocol with polylogarithmic communication for arbitrary circuits. At 128-bit computational and 40-bit statistical security, our implementation reaches 12.9 million \(\mathbb{Z}_p\) inputs/s, 9.0 million ZK multiplication gates/s on a 16-core machine, and proves \(1024 \times 1024\) matrix multiplication in about 4s with single-thread computation and 226 KB communication.

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<n/2$ assumption; HumBird-2, a partially synchronous BFT under the $f<n/3$ assumption, where $n$ is the number of replicas in the system and $f$ is the number of Byzantine failures. We show that by relaxing LSO to the leader-speaks-twice (LST) model and introducing a special uncle block field, we can significantly reduce both good-case latency and expected latency. Our experimental results show that compared to the state-of-the-art rotating leader BFT, HumBird-1 and HumBird-2 achieve up to 32% lower latency and 70% higher throughput, and 95% lower latency and 140% higher throughput, respectively.

End-to-end encryption allows data to be outsourced and stored on an untrusted server, such as in the cloud, without compromising data privacy. In the setting when this data is shared between a group of users, all members also share access to the key material used for data encryption. In existing solutions, this key material is static and not rotated when group membership changes. Thus, also removed members can decrypt shared data, precluding post-compromise security and cryptographic access control. We propose to move away from static keys and instead use a group key progression (GKP) scheme, a novel primitive that enables a dynamic group of users to agree on a persistent sequence of keys while keeping a compact local state. GKP ensures that group members can only derive keys within a certain interval of the sequence, a notion that we call interval access control (IAC), and also provides post-compromise security. Our GKP construction, called Grappa, combines continuous group key agreement (Alwen et al., 2020) with a new abstraction called an interval scheme. The latter is a symmetric-key primitive that can derive a sequence of keys from a compact state while preserving IAC. We explore different interval scheme constructions and simulate their storage and communication costs when used in group settings. The most efficient instantiation is a generalization of dual key regression (Shafagh et al., 2020), which we formalize and prove secure. Overall, our protocols offer a practical and robust solution to protect shared, persistent data.

Secure multi-party computation in permissionless settings like blockchains faces the challenge of maintaining security under adaptive corruptions. YOSO MPC (Benhamouda et al., TCC 2020; Gentry et al., Crypto 2021) addresses this through ephemeral roles, allowing committee members to speak only once before erasing state, thus preventing adaptive attacks within each role's lifetime. However, prior work on YOSO MPC relied on an honest majority within committees and required enormous committee sizes, often numbering in the thousands. In this paper, we challenge both requirements by leveraging the cryptoeconomic properties of the underlying blockchain. We introduce a mechanism for identifying parties who fail to fulfill their roles during protocol execution, using time-lock puzzles. This enables misbehaving parties to be penalized based on publicly verifiable fraud proofs, allowing for a more aggressive committee threshold. Furthermore, we propose a new sortition procedure that ensures the resulting committee always has a constant size, not just in expectation. This reduces fluctuations in committee size, enabling an even higher committee threshold. These techniques allow us to handle any constant fraction $f < 1$ of total corruptions. Finally, we refine and generalize the analysis of corruptions in YOSO protocols, obtaining tighter bounds. Combined with our other enhancements, this enables committees of around 100 parties. Our analysis yields a $70$--$80\%$ improvement over the estimates of the seminal work by Benhamouda et al. (TCC 2020). We believe our work paves the way for practical deployments of YOSO MPC protocols.

Zero-knowledge proofs allow to prove a statement while not revealing anything about the witness. In particular, non-interactive zero-knowledge (NIZK) has emerged as the preferred paradigm due to its public verifiability. However, existing NIZK protocols often suffer from high prover overhead for large statements. Conversely, designated-verifier zero-knowledge (DVZK) offers superior prover efficiency and scalability, but is restricted to a single, designated verifier. This leaves a critical gap in scenarios requiring a prover to efficiently convince a group of n verifiers without incurring massive prover overhead of non-interactive systems. To reconcile this, we focus on multi-verifier zero-knowledge (MVZK) protocols, which efficiently prove the same statement to n verifiers simultaneously. MVZK protocols inherit the prominent prover efficiency of DVZK and extend its utility to the multi-party setting. In this work, we propose a highly efficient MVZK protocol in the preprocessing model, secure against a dishonest majority. It tolerates a corrupted prover and up to n-1 corrupted verifiers, where the prover sends only a single message to verifiers, while several prior works require at least two online rounds. Furthermore, compared to the state-of-the-art 1-round protocol by Zhou et al. (PKC 2025), our protocol eliminates the extension-field multiplications from 4n to 0 over any field, achieving superior online efficiency. Experimental results demonstrate that our protocol achieves 9x faster proving and 47x faster verification when evaluating Boolean circuits with 10^4 AND gates.

An interactive aggregate signature scheme enables $n$ signers, each with their own secret/public key pair $(\mathit{sk}_i, \mathit{pk}_i)$ and message $m_i$, to collaboratively produce a single compact signature that attests that each message $m_i$ has been signed under the corresponding public key $\mathit{pk}_i$. Despite their potential for significant space and verification time savings when compared to the processing of many individual signatures, aggregate signatures have received considerably less attention than other multi-party signatures such as multi-signatures and threshold signatures. In this paper, we propose $\mathsf{DahLIAS}$, the first aggregate signature scheme with constant-size signatures based directly on discrete logarithms in pairing-free groups. Its signing protocol consists of two rounds, the first of which can be preprocessed without knowledge of the messages to be signed. An aggregate signature has the same shape as standard Schnorr signatures, and its verification time is dominated by a multi-exponentiation of size $n+1$, which achieves a $2\times$ asymptotic speedup over batch verification of $n$ individual Schnorr signatures. With its explicit support for key tweaking, a technique commonly used for advanced key derivation in cryptocurrencies, $\mathsf{DahLIAS}$ is designed to be secure in real-world applications. We prove $\mathsf{DahLIAS}$ secure in the concurrent setting with key tweaking under the algebraic one-more discrete logarithm assumption in the random oracle model.

We present PQES-AKE, a novel two-party authenticated key exchange (AKE) protocol built upon the Post-Quantum Encryption and Signcryption Scheme (PQES) introduced by Kara et al. The protocol achieves mutual authentication, session key secrecy, and forward secrecy in a post-quantum adversarial model. The central design principle of PQES-AKE is the concealment of ephemeral Diffie-Hellman (DH) keys within affine masks derived from randomness generated internally by the PQES signcryption algorithm. The security of PQES-AKE rests on three hardness assumptions, including Learning With Errors (LWE) for ciphertext confidentiality, a Secret-Base Discrete Exponentiation (SBDE) assumption for signature unforgeability, and the Computational Diffie-Hellman (CDH) assumption for session key secrecy. The protocol completes in two network rounds, with a total communication cost of approximately 627 bytes, and requires 17 modular exponentiations. A Python prototype evaluated on a commodity Intel Core i7 laptop achieves an average execution time of 6.2ms. These results confirm that PQES-AKE provides a competitive, single-primitive alternative to composite KEM-then-authenticate constructions in post-quantum secure channel establishment.

Tremendous efforts have been made to improve the efficiency of secure Multi-Party Computation (MPC), which allows n ≥ 2 parties to jointly evaluate a target function without leaking their own private inputs. It has been confirmed by previous research that Three-Party Computation (3PC) and outsourcing computations to GPUs can lead to huge performance improvement of MPC in computationally intensive tasks such as Privacy-Preserving Machine Learning (PPML). A natural question to ask is whether super-linear performance gain is possible for a linear increase in resources. In this paper, we give an affirmative answer to this question. We propose Force, an extremely efficient Four-Party Computation (4PC) system for PPML. To the best of our knowledge, each party in Force enjoys the least number of local computations, smallest graphic memory consumption and lowest data exchanges between parties. This is achieved by introducing a new sharing type X-share along with MPC protocols in privacy-preserving training and inference that are semi-honest secure in the honest-majority setting. By comparing the results with state-of-the-art research, we showcase that Force is sound and extremely efficient, as it can improve the PPML performance by a factor of 2 to 38 compared with other latest GPU-based semi-honest secure systems, such as Piranha (including SecureML, Falcon, FantasticFour), CryptGPU and CrypTen.

Private Information Retrieval (PIR) is of growing importance in privacy-preserving data access, as it enables users to retrieve information from databases without revealing their query content, thereby aligning with modern data protection and regulatory standards. State-of-the-art schemes, such as HintlessPIR and TensorPIR proposed by Li et al. at CRYPTO 2024, leverage lattice-based cryptography for efficient and privacy-preserving data retrieval. HintlessPIR achieves a communication complexity of $O(N^{1/2})$, which remains suboptimal for large databases. To further reduce communication overhead, the same work introduces TensorPIR, lowering the asymptotic complexity to $O(N^{1/3})$. However, this improvement requires larger parameters and more CRT moduli, leading to a practical communication cost that is not significantly smaller than that of HintlessPIR. In this work, we propose a new framework that rethinks the encryption strategy for the index, reducing both communication and computation costs through fewer CRT moduli. In experiments on 16 GB, 32 GB, 64 GB, and 128 GB databases, our total communication cost drops to as low as 45.5% of TensorPIR's. Theoretically, as $N$ grows, our query and answer sizes are reduced to 36.9% and 22.2% of TensorPIR's, respectively. Compared with HintlessPIR, our scheme achieves lower theoretical communication complexity, leading to substantially smaller practical communication for large $N$. Moreover, our total online time is reduced to 28.9% to 56.1% of HintlessPIR's.

Nearly all succinct proof systems express computations as algebraic constraints over a finite field. Operations not native to this field, such as bitwise manipulation, modular arithmetic, and lattice-ring operations, require an arithmetization step that can inflate the witness size by one or more orders of magnitude. We introduce Universal Constraint Systems (UCS) and Zinc$+$. The first is a relation that can express the above constraints with minimal overhead. The second is a framework for building SNARKs for UCS. Concretely, UCS consists of algebraic constraints and ideal membership predicates over multiple polynomial rings simultaneously, such as $\mathbb{F}_q[X], \mathbb{Q}[X], \mathbb{Z}[X]$, etc. Zinc$+$ SNARKs are built from 1) a PIOP for UCS, and 2) a hash-based IOPP for multilinear polynomials over $R=\mathbb{Q}[X]$ or $R=\mathbb{F}_q[X]$. For 1), we provide a general compiler that takes standard finite-field PIOPs and turns them into a PIOP for UCS. The IOPP in 2) depends on $R$: for $R=\mathbb{F}_q[X]$, we construct it via a black-box lift of any existing IOPP for $\mathbb{F}_q$, and for $R=\mathbb{Q}[X]$, we present a novel tensor IOPP design, instantiated with the new code family below. We introduce Integer Pseudo-Reed Solomon (IPRS) codes, a new family of MDS codes over $\mathbb{Q}$ and $\mathbb{Q}[X]$. While not Reed-Solomon codes, these codes have optimal MDS relative minimal distance, support efficient FFT-based encoding, and have bounded norm growth when encoding (unlike a naïve lift of Reed-Solomon codes to the integers). Our unoptimized, open-source, implementation proves 7 SHA-256 compressions followed by the multi-scalar multiplication (MSM) part of an ECDSA verification (the bulk of the work), with the following performance, benchmarked on a MacBook Air M4, without zero-knowledge: Prover time: 40.6 ms, Verifier time: 7.0 ms, Proof size: 198 KB. Zinc$+$ can be instantiated end-to-end or as a lightweight extension to any existing hash-based SNARK over~$\mathbb{F}_q$.

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.

As AI agents increasingly operate in real-world, multi-agent environments, ensuring reliable and context-aware privacy in agent communication is critical, especially to comply with evolving regulatory requirements. Traditional access controls are insufficient, as privacy risks in agentic applications often arise after access is granted; agents may use information in ways that compromise privacy, such as messaging humans, sharing context with other agents, making tool calls, persisting data, or generating arbitrary functions of private information. Existing approaches often treat privacy as a binary constraint, whether data is shareable or not, overlooking nuanced, role-specific, and computation-dependent privacy needs essential for regulatory compliance. Agents, including those based on large language models, are inherently probabilistic and heuristic. There is no formal guarantee of how an agent will behave for any query, making them ill-suited for operations critical to security. To address this, we introduce AgentCrypt, a three-tiered framework for fine-grained, secure agent communication that adds a protection layer atop any AI agent platform. AgentCrypt spans unrestricted data exchange (Level 1) to fully encrypted computation using techniques such as homomorphic encryption (Level 3). Unlike much of the recent work, our approach guarantees that the privacy of tagged data is always preserved—even when the underlying AI model makes errors. AgentCrypt ensures privacy across diverse interactions and enables computation on otherwise inaccessible data, overcoming barriers such as data silos. We implemented and tested it with Langgraph and Google ADK, demonstrating versatility across platforms. We also introduce a benchmark dataset simulating privacy-critical tasks at all privacy levels, enabling systematic evaluation and fostering the development of regulatable machine learning systems for secure agent communication and computation.

A Decentralized Autonomous Organization (DAO) is a pioneering evolution to realize a decentralized democratic governance over a blockchain. In a DAO, stakeholders usually make collective decisions through secure on-chain voting. Recently, Dark DAO (Austgen et al., arXiv:2311.03530) was proposed as a decentralized cartel that enables automated vote-buying. It attacks the inalienable authentication of a remote e-voting system by leveraging key encumbrance via MPC or TEEs, enabling a voter to pass the authentication without knowing the actual key. To defend against this new type of attack, the notions of individual knowledge (Dziembowski et al., CRYPTO '23) and complete knowledge (Kelkar et al., CCS '24) were proposed, ensuring that the prover has unencumbered knowledge of a secret. However, their solutions rely on TEEs or ASICs, which are difficult to deploy on blockchain. Inspired by the human-extractable CAPTCHA puzzles proposed by Kumarasubramanian et al. (PKC '13), we propose a new primitive called human-extractable zero-knowledge proofs of knowledge (HE-ZKPoK) as an alternative solution to Dark DAOs. Our HE-ZKPoK protocol forces the prover to solve human-extractable CAPTCHA puzzles along with completing a standard zero-knowledge proof of knowledge, avoiding the need for specialized hardware. As a result, any human entity can extract the witness merely by looking at the prover's CAPTCHA queries and the associated puzzles. With this property, we conclude that if a voter sells his vote, his secret key will be fully exposed, thus deterring voters from engaging in vote-buying.

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.

We present protocols for server-aided private set union (PSU), third-party private set difference (TP-PSD) and third-party private symmetric difference (TP-PSymD), offering both information-theoretically secure and cryptographically secure versions. In addition, we introduce variants of our TP-PSD and TP-PSymD protocols that are designed for practical deployment in settings when certain parties are resource-constrained. In a third-party setting, the receiver who obtains the output is an external inputless party with two other participating input parties. Our protocols for third-party private set operations significantly outperform those of Yeo and Ying (USENIX ’25), improving both asymptotic computational complexity and practical performance. Experimental results demonstrate substantial efficiency gains, including greatly reduced running times and scalability to much larger set sizes. Moreover, our server-aided private set union protocol is several times faster than existing state-of-the-art two-party private set union protocols.

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their private sets without revealing any additional information. Fuzzy PSI, an approximate variant of PSI, allows the receiver to learn points of the sender that are ``close" to its points. More formally, the receiver learns all $y$ in the sender's set that satisfy $dist(x,y)< \delta$ for some element $x$ in the receiver's set and threshold parameter $\delta$. Recently, there has been significant progress on Fuzzy PSI, as it allows us to realize several important applications such as password matching, facial recognition, and contact tracing in a privacy-preserving manner. However, existing Fuzzy PSI constructions make strong assumptions on the input sets, such as receiver set disjointedness or projected disjointedness. In this work, we analyze those strong assumptions from a practical viewpoint and observe a gap between theory and practice, i.e., real-world data sets do not abide to those assumptions. To bridge the gap, we first define a new relaxed and weaker assumption based on the low density of sets, demonstrate the assumption to be practical, and build a compiler that converts constructions under the strong assumption to those under the new, practical assumption. At the core of our transformation is a novel idea involving higher-dimensional lifting and coloring. Combining our transformation with current Fuzzy PSI protocols under the strong assumption yields efficient and practical Fuzzy PSI protocols. We also concretely analyze the run-time and overhead of our transformed protocols for parameters for illustrative applications, such as password matching.

A group signature scheme enables users of a group to anonymously sign messages on behalf of the group, while a designated authority can revoke anonymity when needed to ensure user accountability. Among group signature schemes, fully dynamic ones are particularly desirable as they allow new users to join and misbehaved existing users to be revoked without requiring system-wide updates. This paper introduces DGSP, a post-quantum fully dynamic group signature scheme that addresses key limitations of existing schemes like DGMT and SPHINX-in-the-Head (SITH). Leveraging the properties of ${\rm SPHINCS}^+$, DGSP achieves a superior balance between scalability and efficiency by (i) supporting up to $2^{60}$ users, (ii) requiring negligible setup time, and (iii) featuring efficient algorithms with short signatures of constant-size. Notably, while DGMT is limited to $2^{15}$ users, DGSP extends this to $2^{60}$ while keeping signatures compact—only 3.03 to 4.93 times larger than those of DGMT, yet just 0.021 to 0.004 times the size of SITH signatures. This makes DGSP a compelling solution for applications requiring both large-scale user support and signature efficiency in the post-quantum setting. Moreover, DGSP strengthens managerial accountability compared to DGMT by (i) enabling users to verify their certificates generated by the manager and (ii) ensuring public verifiability of the manager's signature attribution. Although SITH claims to support $2^{60}$ users, our analysis reveals that its opening algorithm is highly inefficient, making it impractical to handle such a large number of users. Our security analysis shows that DGSP achieves unforgeability, anonymity, and traceability in the standard model. We also provide a complete implementation of DGSP. Our experimental study exhibits that DGSP is superior over existing schemes in terms of efficiency and scalability.

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.

Verifiable Databases (VDBs) allow clients to outsource data storage without trusting the provider: a client holding only a short digest can verify any query response using a compact server-provided proof. Given the ubiquity of both databases and outsourced storage, VDBs address a fundamental need. Our work advances the state of the art in VDB design. Our main contribution is $\mathsf{qedb}$, a simple and performant construction for SQL queries based on bilinear pairings. Like some prior VDB schemes, $\mathsf{qedb}$ leverages features specific to the database setting; however, it differs from such approaches in its technical blueprint, the breadth of supported queries, and performance. Notably, it is the first scheme of its kind with proof size independent of database size and without quadratic scaling for storage or preprocessing. Compared to VDB solutions based on general-purpose proofs, $\mathsf{qedb}$ offers stronger tradeoffs in at least one of the following: provable security, proof size and verification time, or system complexity and maintainability (over an order of magnitude fewer lines of code). As additional contributions, we provide both an implementation of $\mathsf{qedb}$ and new theoretical foundations for VDB design—a new framework modeling $\textit{idealized}$ protocols for verifiable databases, which future works can use in a plug-and-play manner. Through our modular approach we can get more provably secure instantiations of $\mathsf{qedb}$ $\textit{for free}$, including a post-quantum one from lattices.

A consistent accumulator computes a digest for a dynamically-growing set of elements, with a proof of consistency of the new digest with the previous digests. Consistent accumulators are in wide use, in particular, by Certificate Transparency (CT), which is part of the Web PKI, and in blockchains. We present a significantly more efficient design for a consistent accumulator. Our design is compatible with the CT specifications; similarly to the widely-used, open-source CT implementation, it uses a Merkle tree, but much more efficiently. We provide open source implementation, security analysis and experimental evaluation showing the performance improvements.

Cryptographic commitments allow a party to commit to a value such that it is infeasible to later open that commitment to a different value. Standard commitment schemes allow the committer to outsource both the generation of the commitment and the openings to a third party. This is benign for most use cases; however, when commitments serve as cryptographic attestations of work such as storing data or relaying blocks, participants can outsource the task and still claim credit, undermining the intended economic properties of the protocol. This work initiates the study of non-delegatable commitments, a new primitive where forming a commitment requires possession of a private key, and delegating the commitment process necessarily leaks that key. We formally define the primitive and provide a generic construction from a polynomial commitment scheme in the random oracle model. Additionally, we show how this primitive can be applied to solve a variety of mechanism design problems.

In outsourcing computation to untrusted servers, one can cryptographically ensure privacy using Fully Homomorphic Encryption (FHE) or ensure integrity using Verifiable Computation (VC) such as SNARK proofs. While each is practical for some applications in isolation, efficiently composing FHE and VC into Verifiable Computing on Encrypted Data (VCoED) remains an open problem. We introduce $\mathsf{Laminate}$, the first practical method for adding integrity to BGV-style FHE, thereby achieving VCoED. Our approach combines the blind interactive proof framework with a tailored variant of the GKR proof system that avoids committing to intermediate computation states. We further introduce variants employing transcript packing and folding techniques. The resulting encrypted proofs are concretely succinct: $13$MB, compared to $1$TB in prior work, to evaluate a batch of $B=2^{14}$ instances of size $n=2^{20}$ and depth $d=32$. Asymptotically, the proof size and verifier work is $O(d \log (Bn) + N)$, compared to $\Omega(BN\log n)$ in prior work (for ring dimension $N$). Unlike prior schemes, $\mathsf{Laminate}$ utilizes the full SIMD capabilities of FHE for both the payload circuit evaluation and proof generation; adds only constant multiplicative depth on top of payload evaluation while performing $\tilde{O}(n)$ FHE operations; eliminates the need for witness reduction; and is field-agnostic. The resulting cost of adding integrity to FHE, compared to assuming honest evaluation, is ${\sim}5\times$ to ${\sim}67\times$ overhead (for circuits of size $2^{20}$), which is $>2300\times$ faster than the state-of-the-art.

In the current digital world, large organizations (sometimes referred to as tech giants) provide service to extremely large numbers of users. The service provider is often interested in computing various data analyses over the private data of its users, which in turn have their incentives to cooperate, but do not necessarily trust the service provider. In this work, we introduce the \emph{Gulliver multi-party computation model} (GMPC) to realistically capture the above scenario. The GMPC model considers a single highly powerful party, called the {\em server} or {\em Gulliver}, that is connected to $n$ users over a star topology network (alternatively formulated as a full network, where the server can block any message). The users are significantly less powerful than the server, and, in particular, should have both computation and communication complexities that are polylogarithmic in $n$. Protocols in the GMPC model should be secure against malicious adversaries that may corrupt a subset of the users and/or the server. Designing protocols in the GMPC model is a delicate task, since users can only hold information about $\operatorname{polylog}(n)$ other users (and, in particular, can only communicate with $\operatorname{polylog}(n)$ other users). In addition, the server can block any message between any pair of honest parties. Thus, reaching an agreement becomes a challenging task. Nevertheless, we design generic protocols in the GMPC model, assuming that at most $\alpha<1/8$ fraction of the users may be corrupted (in addition to the server). Our main contribution is a variant of Feige's committee election protocol [FOCS 1999] that is secure in the GMPC model. Given this tool we show: 1. Assuming fully homomorphic encryption (FHE), any computationally efficient function with $O\left(n\cdot\operatorname{polylog}(n)\right)$-size output can be securely computed in the GMPC model. 2. Any function that can be computed by a circuit of $O(\operatorname{polylog}(n))$ depth, $O\left(n\cdot\operatorname{polylog}(n)\right)$ size, and bounded fan-in and fan-out can be securely computed in the GMPC model {\em without assuming FHE}. 3. In particular, {\em sorting} can be securely computed in the GMPC model without assuming FHE. This has important applications for the {\emph shuffle model of differential privacy}, and resolves an open question of Bell et al. [CCS 2020].

We introduce BlindReview, an anonymous and end-to-end verifiable peer review system that cryptographically guarantees both privacy and auditability throughout the reviewing process. We formally define these security properties and provide rigorous proofs that BlindReview satisfies them. We also present an implementation demonstrating our protocol’s practicality. This work serves as a foundation for verifiable and privacy-preserving peer review, offering a concrete solution to enhance transparency and reduce bias in the academic peer review process.

Fair exchange protocols on blockchain enable atomic exchange of digital goods and cryptocurrency between untrusted parties. Two prominent protocols, Zero-Knowledge Contingent Payment (ZKCP) and FairSwap, guarantee fairness: either both parties receive the expected items (digital goods and cryptocurrency) or neither does. However, both protocols lack accountability: when an exchange terminates abnormally, the protocol cannot identify which party caused the failure. This lack of accountability undermines the applicability of fair exchange protocols in decentralized settings. To fill this gap, we identify the common accountability issue in both protocols and revise them by adding signature exchange and chaining. We formally define the revised protocols in the universal composability framework and provide a proof sketch, and measure the computational overhead of the revised protocols in our implementation and experiment.

Smart-ID is a signing and authentication service available to residents of Belgium, Estonia, Iceland, Latvia and Lithuania. Such smartphone-based signing service delivers the usability of software keys with security guarantees of ID-cards by relying on a remote server to compensate for weak device protection. Security of current Smart-ID relies on multi-prime server-supported RSA, password-authenticated key shares and clone detection mechanism. Unfortunately, the security properties of the underlying protocol (Buldas et al. ESORICS 2017) have been specified only in ``game-based'' manner. In other words, there are no guarantees for the protocol being secure in concurrent setting. We remedy this shortcoming by presenting two ideal functionalities $\mathcal{F}^{\textsf{gSpl}}$ and $\mathcal{F}_{\textsf{Sig}}^{\textsf{Spl}}$ for server-supported signing in Universal Composability model. We show that improved RSA server-supported protocol realizes $\mathcal{F}^{\textsf{gSpl}}$ and give practical example of server-supported ECDSA protocol realizing $\mathcal{F}_{\textsf{ECDSA}}^{\textsf{Spl}}$.

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE, it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. However, many works use specific constructions reliant on the behaviour of a particular scheme and do not consider security against colluding servers and parties. In this work, we present a new framework that is secure against collusion between servers and parties and allows the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 40-99.9% compared to the MKFHE FINAL scheme, FINALLY, 8-71% compared to the static AKÖ scheme, and 65-70% compared to the Park-Rovira scheme. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75-99.7%.

Proof of Assets (PoA) protocols enable custodians to prove ownership of digital assets without revealing their account addresses or corresponding balances. While existing PoA protocols focused on either private or public balances, hybrid-state blockchains such as the Aztec Network involve both. In these systems, private balances are managed by encrypted notes that work similarly to the UTXO model, with only commitments stored on-chain. We present a PoA protocol that supports hybrid balances by combining public-state membership proofs with proofs of ownership over private notes. Since a custodian may control multiple accounts and numerous notes, we employ hierarchical proof-carrying data via recursive zk-SNARK, enabling scalable proving and efficient batch verification. We implement our system using the Noir DSL with the UltraHonk proving backend, and evaluate the performance.

Multi-point function secret sharing (FSS) is a building block for pseudo-random correlation generators used in the novel silent correlation generation methods for various secure multi-party computation applications. However, the main construction used so far is the naive approach to combining several point functions. In this paper, we propose an efficient and natural generalisation of the point function FSS scheme of Boyle et al. 2016 using a tree structure, a pseudorandom generator and systems of linear equations. We propose a new notion of distributed random multi-point function. Our construction splits the distributed multi-point function scheme into a random multi-point function scheme and an algorithm to transform a random output into the desired output value. The resulting scheme, which we call SLAMP-FSS, improves upon the state of the art in terms of calls to a pseudorandom generator (PRG).

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.

End-to-end encrypted applications protect user data by ensuring that user secrets are only available on client devices. However, if a user loses all of their devices, they need a way to recover their data using only a short password. To realize a password-based secret recovery system resilient to brute-force attacks, prior works relied on secure hardware or a few non-colluding servers. In this work, we take a conceptually different approach that distributes trust across the many clients already in the system, while using the server only as an orchestrator without relying on it for privacy. To achieve this, we design and implement Chorus, a secret recovery system that employs ephemeral committees, each consisting of approximately a thousand clients, to provide strong privacy with high scalability. Committees change frequently in Chorus, typically on the order of a few minutes, to severely limit an attacker's ability to compromise clients on a committee. We design Chorus for unreliable, resource-constrained clients and show that the per-client overhead decreases as more clients join the system. Assuming each user performs recovery once a year, the expected per-client overhead in Chorus is under $30$ s of computation on a mobile device and $13.2$ MB of communication, both incurred only once every four months in a configuration with $100$M clients, up to $50$M of which may be offline and at most $10$M may be compromised. To achieve this performance, we contribute two key techniques: (i) a password-based secret recovery scheme that confines expensive committee interactions to infrequent, latency-tolerant operations, and (ii) a non-interactive verifiable secret-sharing scheme that reduces client overhead by two orders of magnitude by delegating computation to the server.

The fastest asynchronous (block-chained) consensus protocols, a.k.a. BFT SMR, follow a design that dates back at least to AMS (Podc'19). AMS compiles any responsive consensus, $\Pi$, based on rotating proposers, into an asynchronous consensus. It is tempting to instantiate AMS with $\Pi$ equal to the fastest-known proposer-based consensus with quadratic complexity, which is 2-phase Hotstuff (2HS, Podc'19). However, we demonstrate a lack of liveness of AMS(2HS). The fastest known chained consensus, called 2-chain VABA (Podc'21 and FC'22), is a tweak of AMS intended to circumvent the livelessness of AMS(2HS). We describe attacks on its consistency and liveness, leading to the conclusion that the AMS approach is hopeless with 2HS. We introduce a new design, called 2PAC ({2-phase} asynchronous consensus), which modifies both the AMS design and the voting rule of the compiled consensus $\Pi$. Of independent interest, we then address the issue that, in all previous approaches (2-chain VABA, Cordial Miners (DISC'23), GradedDAG, LightDAG) a block pipelined by a leader in the middle of the view had almost twice larger latency than the non-pipelined block. We introduce a fast decision mechanism which decides the pipelined block (and all non-leader blocks referred to within) with even smaller latency than the non-pipelined block in a wide set of scenarios (even with faults and message reorderings). Instantiated over 2PAC it gives ``s2PAC''. Instantiating s2PAC with the appropriate modifications of, respectively, 2HS, and a DAG-ified version of Jolteon* (in production by Aptos), we obtain the fastest asynchronous consensus in their respective complexity classes: s2PAC$^\text{lean}$ (in $O(n^2)$, i.e., quadratic) and s2PAC$^\text{BIG}$-DAG ($O(n^3)$, i.e., cubic). Our large-scale experiments confirm their superiority over the state of the art, i.e., a chained version of (sMVBA, CCS'22) in $O(n^2)$; and (GradedDAG, SRDS'23) in $O(n^3)$.

Trustworthy federated learning requires both update privacy and aggregate integrity. While secure aggregation protects the confidentiality of client updates, it does not prevent a malicious server from tampering with the final aggregate. Existing verifiable schemes typically address this limitation by introducing separate integrity-verification layers, such as zero-knowledge proofs, homomorphic hashes, and commitmentbased mechanisms. However, these approaches either require clients to remain online after uploading their updates for additional verification or recovery procedures, or incur substantial computation overhead that scales linearly with the model dimension. To address these limitations, we propose SealAgg, a one-shot verifiable secure aggregation framework that simultaneously guarantees update confidentiality and aggregate integrity against a malicious server. SealAgg allows clients to disconnect immediately after uploading their updates and introduces an aggregatenative auditing mechanism that enables lightweight integrity verification without a separate costly verification pipeline. Specifically, each client embeds dual hidden finite-field linear projections and a context-binding heartbeat value into its update before encryption, so that the audit material is co-aggregated with the gradients along the same path. Moreover, we design an asymmetric three-server architecture that confines integrity validation entirely to the server side, thereby fully supporting one-shot client participation. We provide formal analyses of the correctness and security of SealAgg. Extensive experiments show that SealAgg achieves practical end-to-end efficiency, incurs only a small auditing overhead relative to the total cost, and outperforms state-of-the-art schemes.

Hash-based SNARKs are arguably the most prominent and widely deployed class of transparent SNARKs, owing to desirable properties such as plausible post-quantum security and the avoidance of public-key cryptography. The key ingredients in the construction of hash-based SNARKs are an error-correcting code and an Interactive Oracle Proof of Proximity (IOPP) for that code. A particularly desirable property for hash-based SNARKs is field-agnosticism, i.e., the ability to natively prove statements over arbitrary fields (of sufficient size). We advance the study of field-agnostic hash-based SNARKs as follows: $\bullet{}$ We introduce a new family of linear-time encodable field-agnostic error-correcting codes called Encode-Repeat-Accumulate (ERA) codes. These codes achieve a strong trade-off between encoding time and relative distance, the two properties that largely determine the commitment time and proof size of the resulting hash-based SNARK. We also show that ERA codes are efficiently codeswitchable (Ron-Zewi and Rothblum [JACM 2024]), i.e., we can efficiently reduce the task of checking the proximity of a word to an ERA code to checking the proximity of a related word to an arbitrary code. $\bullet{}$ We present an IOPP for (interleaved) ERA codes that leverages their fast encoding time, strong distance guarantees, and efficient codeswitchability to achieve concretely small query complexity (and hence small proof size in the resulting hash-based SNARK) while maintaining good prover efficiency.

We give the first rigorous $O(1)/|F|$ FRI commit-phase soundness bound for plain Reed–Solomon above the Johnson radius — the central open question in the proximity-gap line, made urgent by the late-2025 disproof of the up-to-capacity conjecture (Crites–Stewart; BCHKS; Diamond–Gruen). The bound is proved via a structural mechanism new to the proximity-gap literature: the action–orbit symmetry on the cyclic FRI evaluation domain (five-line proof, no correlated agreement, no character sums, no list-decoding). The construction is unconditional for sparse adversary inputs; for general inputs it reduces to a single sparse-worst-case dominance conjecture (Q2), consistent with every adversarial construction in the proximity-gap literature, including Arnon–Boneh–Fenzi (ABF) Lemma 6.13, Crites–Stewart, and BCHKS. Deployment consequence. Plugged into the ABF §6.3 deployment instance at 128-bit security, the bound halves the rigorous STARK proof size on plain Reed–Solomon: 79.8 KiB against ABF's smallest deployable candidates — 161.4 KiB on interleaved RS ($2.0\times$ larger) and 281.2 KiB on folded RS ($3.5\times$ larger), both requiring strictly stronger code-class assumptions. Production STARK L2s (Starknet's Cairo pipeline, Plonky3-based rollups, the next generation of zkVMs) ship plain RS today without a rigorous above-Johnson bound for it; our work is the first deployment-scale rigorous construction on plain RS at 128-bit security — no protocol modification, no new hardness assumption, no change of code family. Mathematical depth. A separate universal extension to the $(3k/2, 2k)$ family of arising pencils reduces to a single named open problem in number theory (Q1): the non-vanishing of an explicit norm $\mathrm{Norm}_{K_d/\mathbb{Q}}(F_d(\alpha)) \neq 0$ on a class-field extension of $\mathbb{Q}[\sqrt{-D}]$, $D = 83{,}860{,}066{,}393{,}667$, with Hilbert class field of degree $\sim 3.4 \times 10^6$. The problem is settled rigorously over $\mathbb{Q}$ at $d \in \{4, 8\}$ (exact rational norm at $d=4$; multi-threaded msolve at $d=8$) and connects our work to classical questions in cyclotomic number theory and Hecke L-value non-vanishing.

Anonymous messaging systems, such as privacy-preserving blockchains and private messaging applications, need to protect recipient privacy: ensuring no linkage between the recipient and the message. This raises the question: how can untrusted servers assist in delivering the pertinent messages to each recipient, without requiring the recipient to linearly scan all messages or revealing the intended recipient of each message? Oblivious message retrieval (OMR), a recently proposed primitive, addresses this issue by using homomorphic encryption in the single-server setting. This work introduces $\mathsf{InstantOMR}$, a novel OMR scheme that combines TFHE functional bootstrapping with standard RLWE operations in a hybrid design, achieving significant improvements in both latency and parallelizability compared to prior BFV-based schemes. We propose a two-layer bootstrapping architecture and hybrid use of TFHE and regular RLWE homomorphic operations for $\mathsf{InstantOMR}$. Our implementation, using the $\mathsf{Primus}$-$\mathsf{fhe}$ library (and estimates based on $\mathsf{TFHE}$-$\mathsf{rs}$), demonstrates that $\mathsf{InstantOMR}$ offers the following key advantages: - Low latency: $\mathsf{InstantOMR}$ achieves ${\sim} 860\times$ lower latency than $\mathsf{SophOMR}$, the state-of-the-art single-server OMR construction. This translates directly into reduced recipient waiting time (by the same factor) in the streaming setting, where the detector processes incoming messages on-the-fly and returns a digest immediately upon the recipient becoming online. - Optimal parallelizability: $\mathsf{InstantOMR}$ scales near-optimally with available CPU cores (by processing messages independently), so for high core counts, it is faster than SophOMR (whose parallelism is constrained by its reliance on BFV).

We prove the first unconditional soundness theorem above the Johnson bound for FRI, STIR, and WHIR — the proximity-testing protocols underlying every deployed STARK, zkVM, and FRI-based system on Ethereum's roadmap. For $\mathrm{RS}[F, L, k]$ with $k = 2^m$ and $L$ admitting a fixed-point-free involution (standard for deployed FRI, in either characteristic), for every $\delta \in (\delta_J,\, 1-\rho)$: $$\varepsilon_{\mathrm{FRI}} \;\leq\; \frac{nR}{|F|} \;+\; \left(1 - \frac{\delta}{2}\right)^{\!q}.$$ Three results. (A) The bound above, via threshold halving from Rothblum–Vadhan–Wigderson (STOC 2013); the protocol, prover messages, and verifier checks are unchanged — only the query parameter is recalibrated. The argument enters the unique-decoding regime after one round, where BCIKS locks the distance, making it immune to any open-zone counterexample. (B) The ${\sim}2{\times}$ query overhead is optimal within the correlated-agreement (CA) framework: $\varepsilon_{\mathrm{ca}}(C, \delta, \delta) = \binom{n}{w}/|F|$, tight for large fields, exponential in the code length, and vacuous at FRI scale. (C) First $p$-dependent list-size bounds: $\mathbb{E}[M] = \binom{n}{w}/p^c$ at all codimension excesses $c \geq 1$; a sub-Poisson Bernstein tail at $c = 2$; and a phase-diagram conjecture at $c \geq 3$ (the deployment regime) predicting a linear $M_{\mathrm{true}} \leq \lfloor (2D-1)/c \rfloor$. Impact for Ethereum. Every deployed and proposed FRI-based system — SP1, RISC Zero, Plonky3, the ${\sim}30$ zkVMs on EthProofs, Stwo (Mersenne31 / circle FRI), the planned post-quantum signature aggregation layer — now has a positive proven soundness floor in the open zone above Johnson, replacing a conjecture whose up-to-capacity form was disproved in late 2025 by Crites–Stewart and independently by Kambiré. The cost is a factor ${\sim}2$ in queries; the bound holds in characteristic 2 via additive folding, on the unit circle via the Stwo coupling, and compiles to non-interactive knowledge soundness via Fiat–Shamir and DEEP. The half-threshold CA bound is formally verified in Lean 4 with Mathlib.

Verifiable Computation on Encrypted Data (VCoED) addresses the computational integrity gap in Fully Homomorphic Encryption (FHE). While recent protocols have made significant strides in making VCoED feasible, server-side proof generation remains computationally intensive, often requiring hours for a modest $2^{20}$-gate payload circuit (e.g., 2.27 hours for Phalanx, 9.26 hours for Blind Fractal). Moreover, most existing schemes lack support for payload circuits that are homomorphically executed with SIMD operations. In this work, we present Lasagne, a new efficient VCoED scheme for BGV/BFV-type FHE schemes. Lasagne offers the following: 1. It supports multiplicative layered payload circuits and allows them to be homomorphically evaluated under SIMD message encoding, which aligns with the requirements of practical FHE deployment. 2. It achieves efficient prover time while maintaining acceptable communication/verification overhead, and supports flexible parameters choosing to trade off prover time and communication overhead. For a 16-layer, $2^{20}$-gate payload circuit, Lasagne generates a 30 MB proof in just 6–12 minutes(single core), achieving an $11\times$–$23\times$ speedup over Phalanx (2.27 hours, 61.4 MB). When the payload natively supports SIMD execution ($2^4$ slots), the proving time further reduces to 4–5 minutes (a $27\times$–$34\times$ speedup). We instantiate Lasagne for a face recognition application built on FHE. Empirical results confirm the validity of our time estimates and the practical viability of the scheme.

Users who wish to interact with blockchains typically engage with only a small number of decentralized applications (dApps) whose state they need to monitor. However, securely and trustlessly tracking the state of even a single dApp currently requires running a full client, which independently downloads and verifies the entire blockchain, re-executes all transactions, and reconstructs the global state. Operating a full client contrasts sharply with the traditional client–server paradigm, where clients retrieve only the data they need, and becomes increasingly difficult to sustain as blockchains' throughput increases. Light clients do not offer a viable alternative: while they are more resource-efficient thanks to their use of succinct proofs, they can verify only limited information about the ledger and its state and rely on additional trust assumptions for this. As a result, a gap emerges in the blockchain client design space: enabling secure and verifiable monitoring of dApp state, isolating the workload of a given dApp from the workload of the entire chain. To bridge this gap, we introduce a sparse client, a new type of blockchain client that only downloads the transactions that modify the state of a specific dApp and only computes and stores the dApp state, isolating the dApp's workload from the one of the entire chain. We also present Sunfish, a secure sparse client protocol available in two variants: one off-the-shelf compatible with Ethereum Virtual Machine (EVM)-based blockchains and one virtually compatible with any chain. We also introduce an event client, a special case of sparse clients that only tracks a particular stream of events emitted by a dApp. We benchmark sparse and event clients against a full client by implementing prototypes for Ethereum. Our results show that our sparse and event clients respectively save 66% and 85% operating cost when compared to a full node.

Identity-Based Encryption (IBE) schemes were introduced to simplify public-key infrastructure by using any arbitrary strings as public keys. However, a longstanding criticism of IBE is the trade-off inherent in the ``key escrow'' problem: the design of IBE ensures that the authority possesses a master secret key that allows it to generate secret keys for any identity and, consequently, decrypt any ciphertext. While concepts such as Blind IBE and Accountable Authority IBE attempt to mitigate this trust assumption, they fall short of fully preventing a malicious authority from passively decrypting user traffic. A major improvement was proposed by Mitrokotsa \etal where they formalized a stronger notion called Oblivious IBE, where the authority cannot decrypt a ciphertext without brute-forcing the identity space. However, their construction inherently needs a composite group approach and offers no generic methodology. In this work, we present the first generic compiler that transforms any blind IBE into an oblivious IBE. Our transformation establishes a fundamental connection between blindness during key extraction and obliviousness during encryption. We prove that by combining a blind IBE with a hash function which takes input over the identity space, we can force the authority to search exhaustively for the recipient's identity to decrypt. To demonstrate the versatility and practical impact of our compiler, we propose two primary instantiations in the random oracle model: the first oblivious IBE in a prime order group and a post-quantum Oblivious IBE based on lattice assumptions (inspired by a variant of GPV). In addition, we make slight modifications to get our initial instantiation to function in the standard model.

Fungible tokens on public blockchains expose all balances and transfer amounts in the clear, which is incompatible with the financial privacy required by many real-world applications. We present Merces a confidential token contract that hides user balances and transaction amounts while preserving on-chain verifiability. The core idea is to store secret shares of balances within a decentralized MPC network, while only commitments are published to a smart contract. Thereby, Merces is capable of translating any existing token (e.g., any ERC20 token) into a confidential version. Deposits, withdrawals, and transfers are computed privately within the MPC network, which generates a collaborative SNARK (CoSNARK) to prove the validity of each state transition. In particular, the proof ensures that on-chain commitments are updated consistently and that the sender has sufficient funds. In this paper we give a full formalization of our construction in the Universal Composability (UC) framework, provide rigorous security proofs, and describe a concrete instantiation using Groth16 over BN254 with Poseidon2-based commitments. We further provide a complete end-to-end implementation, accompanied by extensive benchmarks and discussion of a working demo: our system achieves over 300 transactions per second, including proof generation, while requiring only minimal client-side computation.

A lookup argument is a cryptographic primitive that allows a prover to convince verifiers that every element of a private query vector belongs to a public table vector without disclosing the underlying data. It can enforce correct instruction execution in zero-knowledge virtual machines and serve as an important supplement to zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). However, existing lookup argument protocols operate exclusively in the single-prover setting and do not address the requirements of collaborative zkSNARKs, in which multiple parties jointly generate proofs over additively secret-shared data while preserving privacy from both other provers and verifiers. This work presents MPlookup, the first multi-party lookup argument protocol for collaborative zkSNARKs. MPlookup achieves quasilinear $O(N \log^2 N)$ complexity through four oblivious sorting operations together with a multi-point polynomial evaluation performed entirely over secret shares. We introduce a multi-point evaluation protocol in the distributed oblivious polynomial evaluation setting, constructed via oblivious subproduct tree construction and oblivious polynomial division with private divisors. We prove that the protocol satisfies obliviousness, completeness, soundness, and zero-knowledge. We implement MPlookup as an open-source Rust library, built upon the collaborative zkSNARKs framework and the CompatCircuit arithmetic black box. Our evaluation confirms a performance improvement over an $O(N^2)$ baseline while remaining competitive given the obliviousness requirement.

A practical acceleration framework for CKKS homomorphic encryption is proposed, in which multiplication-heavy sub-circuits are evaluated by adding encrypted log-magnitudes rather than multiplying ciphertexts. This logarithmic-number-system (LNS) representation consumes no multiplicative levels; a lightweight interactive refresh operation re-enters the linear CKKS domain whenever additive accumulation is required, avoiding bootstrapping entirely. Three execution strategies---an automatic planner, a client-side accumulation variant, and a server-side re-encryption variant---are mechanized in an OpenFHE-based runtime under 128-bit classical security and evaluated on a deep multiplication chain and an attention-like pipeline across three network environments. On the attention pipeline, the linear baseline requires a ring degree of 65,536 and about 2.9 GB of public-context material, whereas LNS operates at a ring degree of 8,192 with about 50 MB---a 58x context reduction yielding 22-36x end-to-end speedup and up to 46x payload reduction. On the multiplication chain the gap widens with depth, from about 10x speedup and 26x payload reduction at L=8 matrices, to 35x and 98x at L=20, because LNS context requirements are decoupled from multiplicative depth while the linear baseline must escalate its ring degree to maintain accuracy and security.

In this paper a novel key refresh architecture using multiple independent third-party refreshers, to eliminate the centralized trust required by single-dealer approaches, is presented. Each refresher independently maintains and refreshes a split of its share, distributing fragments to signing parties asynchronously without coordination. This eliminates the need for coordinated interaction required by committee-based refresh protocols, avoiding substantial communication overhead and synchronization complexity. The architectural separation, where signing parties never participate in refresh and refreshing parties never participate in signing, enables efficient proactive security without disrupting operational availability. The proposed design does not require all refreshers to participate in each refresh operation. Unavailable refreshers are not excluded from the protocol, only malicious ones that deviate from protocol rules. This provides graceful degradation: the system maintains confidentiality even when all refreshers are compromised (requiring only one honest signing party) and achieves proactive security with minimal participation (requiring only one honest refresher between compromise events). This approach extends the period between costly on-chain key rotations by maintaining security through continuous off-chain refresh. Key rotation should be carried out when very few honest refreshers remain. Security under various adversarial scenarios is proven, including malicious refreshers, cross-epoch compromises, and denial-of-service attacks, demonstrating $O(k)$ communication per refresh for k participating refreshers versus $O(n^2)$ for committee-based protocols. The proposed approach is particularly suited for high-availability systems requiring frequent or continuous key refresh, including cryptocurrency wallets and distributed key management.

The transition to post-quantum cryptography (PQC) is essential to safeguard networked systems against future quantum-enabled adversaries. While recent standardisation efforts have introduced PQC algorithms such as ML-KEM into protocols like TLS 1.3, verifying their correct deployment in realworld systems remains a challenge. Existing approaches rely on configuration-level inspection or high-level cryptographic libraries, which do not reflect actual runtime behaviour. This paper presents a novel methodology for detecting postquantum and hybrid TLS key exchange mechanisms through direct inspection of raw TLS handshake records. By parsing ServerHello messages at the byte level and extracting keyshare group identifiers from the key share extension, the proposed approach enables accurate classification of endpoints into CLASSICAL_ONLY, PQC_ONLY, and HYBRID_CONFIRMED states. We implement the methodology within a prototype compliance system and evaluate it across 38 production endpoints and a controlled three-node cloud testbed spanning two validation phases. Phase 1 reveals that all three testbed nodes — including a PQC-capable application server — are correctly classified as CLASSICAL_ONLY, exposing an application-layer versus transport-layer mismatch invisible to configuration auditing. Phase 2, following an OQS-capable TLS frontend upgrade, produces a confirmed HYBRID_CONFIRMED result with group 0x11EC (X25519MLKEM768) on the same physical server, achieving 100% target accuracy across all three nodes. We further document a critical false positive failure mode in naive string-matching approaches and validate correct four-state classification under known ground-truth conditions. Unlike prior work, this approach provides verifiable, evidence-based assessment of cryptographic posture, enabling reliable auditing of PQC readiness.

Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without the user revealing any extra information about themselves. For example, a user who has received a digital passport credential can prove their “age is $>18$” without revealing any other attributes such as their name or date of birth. Despite their clear application to privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale. Part of the difficulty arises because schemes in the literature, such as BBS+, use new cryptographic primitives that require system-wide changes to existing issuer infrastructure. In addition, issuers often require digital identity credentials to be device-bound by incorporating the device’s secure element into the presentation flow. As a result, schemes like BBS+ require updates to the hardware on every user's device. We propose new ZK techniques which enable the construction of an anonymous credential scheme for the legacy Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme. By adding efficient ZK arguments for statements about SHA-256 and document parsing for ISO-standardized identity formats, we construct the first ZK proof of posession of a credential that can be deployed without changing any issuer processes, without changes to mobile devices, and without requiring non-standard cryptographic assumptions. Furthermore, our proof system itself only relies on SHA-256 as its complexity assumption. Producing ZK proofs about ECDSA signatures has been a bottleneck for other ZK proof systems because standardized curves such as P256 use finite fields which do not support efficient number theoretic transforms. We overcome this bottleneck by designing a ZK proof system around sumcheck and the Ligero argument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA. Our proofs for ECDSA can be generated in as little as $\approx20$ms. When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, our system can generate a zero-knowledge proof for the MDOC presentation flow in a few hundred ms on mobile devices. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.

Exact fixed-point multiplication over $\mathbb{Z}_{2^k}$ is a fundamental primitive for secure fixed-point arithmetic. However, in the honest-majority, maliciously secure 3PC setting, no prior work simultaneously provides cross-ring compatibility, exact semantics, and malicious security within this efficient framework. In this paper, we address this gap by showing that the core cross-ring bottlenecks, namely exact signed truncation and signed extension, share a unified algebraic structure. Based on this insight, we propose a general \textbf{quotient-correction framework} that reduces complex non-linear cross-ring operations to a highly efficient \textbf{2-bit bounded-quotient extraction} problem. We instantiate this framework to construct maliciously secure protocols for exact truncation and extension. By sequentially composing these primitives with standard in-ring multiplication, we realize the first end-to-end exact fixed-point multiplication protocol that satisfies all aforementioned requirements in the replicated 3PC setting. We also present optimized variants under relaxed guarantees (e.g., 1-ULP error) that offer superior performance trade-offs. We formalize our constructions within the Universal Composability (UC) framework and provide rigorous security proofs. Theoretical analysis and experimental results demonstrate that our approach achieves practical online efficiency while maintaining exact semantics and malicious security, overcoming the limitations of prior baselines regarding security assumptions, input domains, or output precision.

We present a new generalization of (zk-)SNARKs specifically designed for the application domain of safety-critical control systems. These need to be protected against adversarial tampering as well as non-malicious but unintended system failures due to random faults in components. Our SNARKs combine two additional features at the same time. Besides the verification of correct computation, they also allow, first, the verification of input data authenticity. Specifically, a verifier can confirm that the input to the computation originated from a trusted source. Second, our SNARKs support verification of stateful computations across multiple rounds, ensuring that the output of the current round correctly depends on the internal state of the previous round. Our focus is on concrete practicality, so we abstain from arithmetizing hash functions or signatures in our SNARKs. Rather, we modify the internals of an existing SNARK to extend its functionality. We implement and benchmark our new SNARKs in a sample scenario of a real-time high-integrity flight control system. With our construction, prover runtime improves significantly over the baseline by a factor of 90. Verification time increases by 36%, but is less than comparable approaches that do not arithmetize hash functions or signatures.

The transition from classical public-key cryptography to post-quantum cryptography introduces protocol-level risks that are not fully addressed by configuration review, performance benchmarking, or endpoint reachability testing. Under the current abstraction, deployments may appear operationally correct while still permitting secrecy, authentication, or forward-secrecy violations at the protocol level. This paper presents a topology-driven symbolic verification workflow that translates distributed-system communication graphs into Tamarin models for analysis under the Dolev--Yao adversary model. The workflow derives protocol roles, communication constraints, and migration policies from a graph-based deployment representation, producing .spthy models and associated lemmas for executability, secrecy, authentication, and forward secrecy. A canonical topology representation is used to ensure deterministic model generation from semantically equivalent graph inputs. Experimental evaluation across five scenarios indicates that the framework produces discriminative symbolic outcomes rather than uniform failure reports. A registration-only control scenario verifies all reported lemmas, while the remaining scenarios exhibit two distinct falsification patterns: secrecy and forward-secrecy failures in three scenarios, and authentication failure in one scenario. These results indicate that symbolic verification provides a complementary assurance layer for post-quantum migration analysis and can reveal protocol-level risks that are not observable through operational testing alone.

We study the problem of provably-secure format-preserving authenticated encryption scheme for images, where decryption is successful even when ciphertexts undergo compression. This novel primitive offers users more control and privacy when sharing and storing images on social media and other photo-centric, compressing platforms like Facebook and Google Photos. Since compression is usually lossy, we cannot expect the decrypted image to be identical to the original. But we want the decrypted image to be visually as close to the original image as possible. There is a vast number of works on image encryption, mostly in the signal processing community, but they do not provide formal security analyses. We formally define security, covering the goals of image confidentiality and integrity. While we first treat the problem generically, we are particularly interested in the construction for the most common compression format, JPEG. We design a scheme for JPEG compression using the standard symmetric cryptographic tools and special pre- and post-processing. We formally assess the security guarantees provided by the construction, discuss how to select the parameters using empirical experiments, and study performance of our scheme in terms of computational efficiency and decryption quality. We also build a browser plug-in that helps users store and share photos privately.

PLONK is a zk-SNARK system by Gabizon, Williamson, and Ciobotaru with proofs of constant size (0.5 KB) and sublinear verification time. Its setup is circuit-independent supporting proofs of arbitrary statements up to a certain size bound. Although deployed in several real-world applications, PLONK's zero-knowledge property had only been argued informally. Consequently, we were able to find and fix a vulnerability in its original specification, leading to an update of PLONK in eprint version 20220629:105924. In this work, we construct a simulator for the patched version of PLONK and prove that it achieves statistical zero knowledge. Furthermore, we give an attack on the previous version of PLONK showing that it does not even satisfy the weaker notion of (statistical) witness indistinguishability.

Collecting statistics from users of software and online services is crucial to improve service quality, yet obtaining such insights while preserving individual privacy remains a challenge. Function secret sharing (FSS) is a promising tool for this problem. However, FSS-based solutions still face several challenges for streaming analytics, where messages are continuously sent, and secure computation tasks are repeatedly performed over incoming messages. We introduce a new cryptographic primitive called streaming function secret sharing (SFSS), a new variant of FSS that is particularly suitable for secure computation over streaming messages. We formalize SFSS and propose concrete constructions, including SFSS for point functions, predicate functions, and feasibility results for generic functions. SFSS powers several promising applications in a simple and modular fashion, including conditional transciphering, policy-hiding aggregation, and attribute-hiding aggregation. In particular, our SFSS formalization and constructions identify security flaws and efficiency bottlenecks in existing solutions, and SFSS-powered solutions achieve the expected security goal with asymptotically and concretely better efficiency and/or enhanced functionality.

Private Set Intersection (PSI) has been widely studied, deployed, and demonstrated on static datasets. In this work, we investigate the problem of designing efficient and secure updatable PSIs in the honest-but-curious model by adopting the approach of executing a small number of PSIs over smaller sets instead of one PSI over the entire updated sets. We first identify that existing constructions suffer from privacy leakages and further propose to mitigate them thanks to the use of circuit PSIs, which are variants of PSI protocols that output the secret shares of the intersection instead of outputting the resulting intersection, combined with secure shuffling when needed. We construct a generic framework for PSI over updated sets and show that this framework can easily be extended to a protocol that outputs the cardinality of the intersection instead of the intersection itself.

Secure backups are the Achilles' Heel of the E2EE ecosystem if they do not provide the same strong security properties as the E2EE messaging systems they support. They constitute a set of servers that, if compromised, would expose nearly all user messages. Unfortunately, state-of-the-art and deployed secure backup systems fail to consider forward secrecy and post-compromise security of these servers as first-order design constraints. Additionally, some proposals, in limited deployment, implicitly rely on the PKIs of trusted execution environments in order to provide security, creating a small number of keys whose compromise would be catastrophic. We develop an elegant, efficient, and simple secure backup system that naturally addresses these issues by regularly rotating backup servers, each of which samples independent key material. To make this approach scalable, we design a silent backup procedure, reducing server load compared to state-of-the-art designs while providing improved security. Our design can be trivially extended to incorporate \emph{social key recovery}, enabling more flexible deployment configurations. We carefully prove the security of our construction and benchmark it to show that it is deployment-ready. Our approach works on commodity hardware making it deployable without the resources needed for WhatsApp or Apple's Encrypted Backups.

Verifiable Random Functions (VRFs) provide publicly verifiable pseudorandomness uniquely determined by a secret key and an input. While widely used in decentralized protocols, standard VRF verification reveals the signer's identity, exposing them to targeted adversarial disruption once their eligibility is known. We study Ring VRFs(RVRFs), which allow a member of a public key set (a ring) to publish a VRF value along with a proof of correct generation while hiding the signer's index within the set. We formalize an algorithmic RVRF interface that binds the ring into the evaluated input to prevent cross-ring reuse and ring grinding (i.e., the malicious selection of a specific ring configuration to manipulate the pseudorandom outcome). Diverging from existing UC-based treatments, we propose a comprehensive suite of game-based security notions tailored to verifiable randomness under anonymity: correctness, anonymity, pseudorandomness, and a novel corruption-aware uniqueness notion called $T$-uniqueness. Our main technical result is a modular compiler that transforms any provable VRF into an RVRF by proving a one-out-of-many statement for the induced ring relation. We instantiate the OR layer via an optimized Fiat--Shamir OR (FS-OR) composition in the random oracle model, where the prover utilizes prover-side simulation for all non-witness branches and completes the witness branch only after a global consistency constraint is fixed. Focusing on post-quantum resilience, we provide concrete instantiations of our RVRF framework based on two state-of-the-art lattice VRFs: the long-term lattice VRF $\mathsf{LaV}$ by Esgin et al. (Crypto'23) and the few-time lattice VRF $\mathsf{LB}\text{-}\mathsf{VRF}$ by Esgin et al. (FC'19). We provide a detailed analysis of concrete parameters across various ring sizes for both constructions and perform a comprehensive side-by-side comparison of their communication costs and security trade-offs. Our instantiations are modular, with their security reducing cleanly to (i) the base VRF's correctness, pseudorandomness, and per-key uniqueness, and (ii) standard FS-OR properties (simulatability and extractability).

Secure messaging groups in applications such as Signal, Telegram, and Whatsapp are nowadays used for rapid and widespread dissemination of information to large groups of people. This is common even in sensitive contexts, involving the organisation of protests, activist groups, and internal company dialogues, for instance. Manual administration of who has access to such groups quickly becomes infeasible, in the presence of even hundreds of members. We construct a practical, privacy-preserving reputation protocol, that automates the approval of new group members based on their reputation amongst the existing membership. We prove security against malicious adversaries in a single-server model, with no further trust assumptions required, while supporting arbitrary reputation calculations even when almost all group members are offline (as is likely). We demonstrate the practicality of the approach experimentally: for groups of size 50 (resp. 500), admitting a user that received 40 (resp. 80) scores requires 1312.2 KiB (resp. 13086.3 KiB) of communication, and 3.4 s (resp. 42.3 s) of single-threaded computation. While our protocol design matches existing secure messaging applications, we believe it can have value in distributed reputation computation beyond this problem setting.

Private Set Union (PSU) protocol allows parties, each holding an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomorphic encryption (AHE) can avoid the leakage. However, the AHE-based PSU protocols are far from being practical. To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE-based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our performance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023), which also suffers from the unnecessary leakage.

In this work, we introduce the concept of Obliviously Checkable Secret-Carrying Puzzles (OxSP) and build proof-friendly Garbled Circuits (GCs) to enable their practical implementation. OxSPs allow one to publicly pose puzzles and verify purported solutions received in response, keeping the desired parts of the puzzles and the responses hidden. We show how OxSPs can be based on Garbled Circuits (GCs). However, this requires ZK-SNARK proofs of correctness of garbling. We note that combining existing GC and ZK-SNARK constructions results in very large computational costs for the OxSP solvers. Our main technical contribution is to design a new proof-friendly GC construction which cuts down the cost of generating a proof of correct garbling to almost a third, without resorting to non-standard cryptographic assumptions. Beyond its use in OxSP, we expect our proof-friendly GCs to be of significant independent interest, as a tool for auditable secure 2-party computation.

Cleve (STOC 86) shows that an honest majority is necessary for MPC with guaranteed output delivery. In this paper, we show that while an honest majority is indeed necessary, its involvement can be minimal. We demonstrate an MPC protocol with guaranteed output delivery, the majority of which is executed by a sequence of committees with dishonest majority; we leverage one committee with an honest majority, each member of which does work independent of the circuit size. Our protocol has the desirable property that every participant speaks only once (YOSO, Crypto 2021). As a building block of independent interest, we introduce public computation, which is essentially privacy-free MPC with guaranteed output delivery (akin to smart contracts realized on blockchains). We instantiate public computation on a public bulletin board in three different ways (with different assumption / round / space utilization trade-offs).

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.

A $t$-out-of-$n$ robust non-interactive zero-knowledge (NIZK) combiner is a construction that, given access to $n$ candidate instantiations of a NIZK for some language, itself implements a NIZK for the same language. Moreover, the combiner is secure, assuming at least $t$ of the given candidates are secure. In this work, we provide the first definition of combiners for NIZK, and prove that no robust NIZK combiner exists assuming $t \le \lfloor n/2 \rfloor$ (unless the polynomial hierarchy collapses). On the positive side, we provide different constructions of robust NIZK combiners for $t > \lfloor n/2 \rfloor$. In particular, we show how to obtain: 1) A black-box combiner working for a special class of {\em homomorphic} languages where $n,t$ are polynomial and $t > \lfloor n/2 \rfloor$. 2) A non-black-box combiner working for any language, where $n,t$ are constant and $t > \lfloor n/2 \rfloor$. 3) A non-black-box combiner working for any language, where $n,t$ are polynomial and $t > \lfloor 2n/3 \rfloor$.

Homomorphic Encryption (HE) enables computation on encrypted data while preserving privacy. We explore its application in the multi-party setting, where data is stored in the cloud under several distinct keys. For $n$ parties, Multi-Key HE (MKHE) supports such scenarios but incurs $O(n)$ space and computational overhead, making it impractical for large-scale use. Conversely, Multi-Party HE (MPHE) achieves constant $O(1)$ overhead but is typically limited by a static group structure: ciphertexts are traditionally tied to a fixed set of parties, which poses challenges for dynamically joining new members or reusing existing ciphertexts for different party sets. To address these limitations, we first construct a Dynamic MPHE (dMPHE) scheme that allows new parties to join, while the original parties are not required to remain online. Our construction bridges the gap between existing MPHE and MKHE frameworks while achieving superior efficiency compared to prior dynamic MPHE attempts. Building on this, we introduce Reusable Dynamic MPHE (rdMPHE), a new primitive that simultaneously supports dynamicity and ciphertext reusability. We implement both schemes based on the RLWE assumption. Our analyzes and experiments demonstrate that rdMPHE maintains $O(1)$ efficiency while overcoming the scalability and static constraints of previous MKHE and MPHE. To support open research, our code has been made publicly available.

The plausible threat of a Cryptographically Relevant Quantum Computer (CRQC) has rightly stimulated a move away from traditional methods of asymmetric cryptography to new post-quantum secure equivalents. Digital signature is the cryptographic primitive that authenticates an internet server’s identity by signing each certificate in an X.509 certificate chain. A suggested response to the CRQC threat is to deploy a hybrid classical/post-quantum digital signature, combining a traditional tried-and-tested scheme with a post-quantum alternative, where certificates are signed using both methods. Here we propose a fused signature scheme that adopts the same approach, but introduces minimal friction into existing TLS architectures

Evaluating the usefulness of data before purchase is essential when obtaining data for high-quality machine learning models, yet both model builders and data providers are often unwilling to reveal their proprietary assets. We present PrivaDE, a privacy-preserving protocol that allows a model owner and a data owner to jointly compute a utility score for a candidate dataset without fully exposing model parameters, raw features, or labels. PrivaDE provides strong security against malicious behavior and can be integrated into blockchain-based marketplaces, where smart contracts enforce fair execution and payment. To make the protocol practical, we propose optimizations to enable efficient secure model inference, and a model-agnostic scoring method that uses only a small, representative subset of the data while still reflecting its impact on downstream training. Evaluation shows that PrivaDE performs data evaluation effectively, achieving online runtimes within 15 minutes even for models with millions of parameters. Our work lays the foundation for fair and automated data marketplaces in decentralized machine learning ecosystems.

This paper presents the first high-order fully-shared masking construction for MQOM v2.1, a candidate in NIST's additional digital signature standardization process. We provide a baseline high-order masked signing design for MQOM v2.1, prove its security in the standard probing leakage model, and validate the implementation through a comprehensive TVLA campaign. To mitigate the online-time bottleneck in masked signing, we further introduce an optional Rijndael LUT-based acceleration mode that decouples offline precomputation from online signing. Although this accelerated mode incurs higher offline time and memory costs, it can run during idle periods and significantly reduce online signing latency. We implement and benchmark all 36 MQOM v2.1 signing variants over GF(2), GF(16), and GF(256), and report comprehensive performance and leakage-evaluation results for both the baseline and accelerated designs.

The Double Ratchet (DR) protocol is a core security component of several end-to-end encrypted communications services, primarily Signal Messenger, WhatsApp, and Facebook Messenger, servicing billions of users. In this work, we provide the first formal analysis of the DR covering all of its features, including out-of-order message arrivals. This analysis is highly automated, allows for all possible key compromises and notably proves Post-Compromise Security (PCS). We also provide partial results for the security of more complex protocol variants, these being the extension of the DR with encrypted headers, and composition with PQXDH as the initial key-exchange. Our analysis uncovered three attacks on the protocol, two of which we confirmed to be present in the main implementation, and a third which exists in the specification. Each of these attacks weakened or broke Forward Secrecy, and are to the best of our knowledge the first such known attacks. In each case, the issues were reported to the Signal developers and subsequently fixed. Overall, our analysis provides new guarantees of the security of Signal Messenger, and demonstrates the high level of security provided by the DR under a variety of strong threat models.

After more than four decades of research, multi-party computation (MPC) has achieved remarkable success in handling 2-variable multiplication and comparison-based functions (e.g., ReLU) with practical efficiency. However, for general non-linear functions—such as multiplication of many variables, power, exponential, trigonometric functions, sigmoid, softmax, and GeLU—no native MPC algorithm exists as Beaver-based mutiplication that is constant-round, scalable and exact. Existing solutions rely on either polynomial approximations (trading precision for efficiency), iterative multi-round protocols like Multiplication-to-Addition (M2A) conversion (requiring \(\log_2 k\) rounds for \(k\) parties), or Function Secret Sharing (FSS) with lookup tables (introducing quantization errors and large storage, mainly limited to 2-4 parties). These approaches suffer from fundamental trade-offs among accuracy, communication rounds, and scalability. In this work, we propose a unified \emph{mask-broadcast-unmask} design pattern that enables constant-round, scalable and \emph{approximation-free} evaluation of a wide range of non-linear functions. Our contributions include: \begin{itemize} \item A \textbf{general multiplication} protocol for \(k\) variables in \emph{one round} with optimal \(O(kn)\) communication. When \(k=2\), it reduces to the classic Beaver triple multiplication; when each secret has only one non-zero share and \(k=2\), it becomes the well-known M2A protocol. \item \textbf{Power functions} (\(x^k\)) in one round. \item \textbf{Trigonometric functions} (\(\sin x, \cos x\)) and \textbf{exponential functions} (\(a^x\)) in 4 rounds. \item \textbf{Sigmoid, softmax} in 6 rounds. \end{itemize} All these protocols are provably secure in the semi-honest model, support arbitrary number of parties, introduce \textbf{no approximation error} beyond plaintext floating-point rounding, and require only constant communication rounds (1–6) independent of function complexity. Furthermore, by restricting the random mask to a suitable range (e.g., $0 \le r <2^l-2^{l_x}$), we can reduce the rounds from 1-6 to 1-3. This work fills the long-standing gap for general non-linear functions in standard MPC settings, making privacy-preserving machine learning more practical for modern DNNs.

The sum-check protocol underpins SNARKs with the fastest known provers. For an $n$-variate polynomial $g$ defined over a finite field $\mathbb{F}$, the protocol enables an untrusted prover to convince a verifier of the sum of all evaluations of $g$ over a product set $H^n$ with $H \subset \mathbb{F}$. The standard choice for $H^n$ is the Boolean hypercube $\{0,1\}^n$, which serves as a natural interpolating set for multilinear polynomials. We propose a projective variant of the sum-check protocol, obtained by changing the interpolating set from $\{0,1\}^n$ to the infinity hypercube $\{0,\infty\}^n$. Under a suitable notion of evaluation at $\infty$, evaluating a multilinear polynomial at a point in $\{0,\infty\}^n$ directly extracts its corresponding monomial coefficient. This projective viewpoint is a near-drop-in replacement for applications of sum-check, requiring only local changes to polynomial representations, round identities, and evaluation formulas. It yields a ${\approx}\,10\%$ end-to-end speedup for the sum-check prover on BN254 and on a pseudo-Mersenne 128-bit prime field, against a fair baseline. It eliminates all field subtractions when binding a multilinear polynomial, and for structured polynomials such as equality and less-than, the projective interpolants admit evaluation procedures with fewer field operations. Moreover, the monomial-coefficient form aligns naturally with polynomial commitment schemes like WHIR, removing a basis mismatch that these schemes otherwise need to work around. Finally, we describe an optimization for sum-check over $\approx 256$-bit prime fields. When targeting $\approx 128$ bits of security, it suffices to sample challenges from a subset of size $\approx 2^{128}$. We show that a suitable choice of this subset, interpreted as upper-limb values in Montgomery form, yields a $1.92\times$ speedup for field multiplication. Combined with the projective binding formula, this gives a $1.82\times$ speedup for sum-check binding (a key component of fast sum-check proving).

This paper introduces a logarithmic-size membership proof, Lin2Selector, obtained by iterating a new OR-reduction step, formalized as a standalone argument Lin2Xor. Our main technical contribution is the Lin2-Xor lemma, which establishes the required special soundness for this reduction and thereby enables a clean proof that Lin2Selector is a zero-knowledge argument of knowledge. As an application, we instantiate two setup-free linkable ring signatures via the Fiat–Shamir transform in the ROM: minimalistic L2S-LRS, of length 2(log n)+4 group/scalar elements, and multisignature-friendly L2S-LRS-MS, of length 2(log n)+5, supporting an LSAG-style key image. Both schemes rely only on the standard DLR/DDH assumptions in a black-box prime-order group and allow efficient verification dominated by a single multi-exponentiation, enabling standard batching optimizations. The OR-reduction step Lin2Xor suggests a natural generalization to higher arity. This may enable even more compact one-out-of-many proofs/signatures with lengths approaching (log n)+O(log log n), as well as compact k-out-of-many variants; we leave these as open directions.

Batched threshold encryption (BTE) enables a committee of servers to jointly decrypt any chosen subset of ciphertexts from a large pool, while all remaining ciphertexts stay private. BTE is a key building block for encrypted mempools, where transactions are encrypted until block inclusion to mitigate maximal extractable value (MEV). Existing epochless BTE constructions either require user-chosen ciphertext indices that create coordination and censorship concerns or are computationally inefficient. In this paper, we present BTX, a simple and concretely efficient BTE construction that is both epochless and collision-free: encryption does not require a user-chosen batch index. Our scheme achieves the shortest ciphertext size among all known BTE constructions having the same size as a standard elgamal ciphertext. By making the scheme amenable to FFT, we reduce the decryption cost to $O(B\log B)$ group exponentiations and $O(B)$ pairings, where $B$ is the size of the dynamically chosen batch of ciphertexts. We implement BTX and two baselines in a shared, aggressively optimized C++ codebase over BLS12-381 with AVX-512 vectorization, FFT-based backends where applicable, and additional low-level engineering throughout. At batch size $B = 512$, using a single core, BTX requires approximately $598$ ms total for decryption, compared with $1197$ ms for the FFT optimized version of partial-fraction evaluation baseline of Boneh et al., an overall $2.0\times$ improvement.

Searchable Symmetric Encryption (SSE) schemes enable efficient keyword searches over encrypted documents at the cost of some leakage. An SSE scheme is said to be system-wide secure if it resists cryptanalysis by an adversary with access to leakage from retrieval of both encrypted indices and encrypted documents. The vast majority of state-of-the-art SSE schemes are, in fact, not system-wide secure (Gui et al., IEEE S&P 2023). Currently, the only efficient system-wide secure SSE scheme is SWiSSSE (Gui et al., PoPETS 2024). However, SWiSSSE requires a client state that is updated per query (which hinders adoption in various practical settings), and its leakage is hard to characterize precisely (thus making security analysis harder). In this paper, we present DDR-SSE – a practically efficient, system-wide secure SSE scheme that only requires a static client state, and has a simple leakage profile. Technically, we introduce a novel encrypted document retrieval scheme that uses duplicated document storage and randomized document retrieval to suppress access pattern leakage without compromising on practical efficiency. A remarkable feature of our scheme is its conceptual simplicity (unlike SWiSSSE, which uses an extremely involved document retrieval mechanism). We present a simulation-based security proof for DDR-SSE with respect to a rigorously formal system-wide leakage profile. Through extensive leakage cryptanalysis, we establish that DDR-SSE is resilient to query reconstruction attacks (even under “unrealistically” strong attack assumptions). Finally, we benchmark a prototype implementation of DDR-SSE and show that it scales smoothly to large databases of the size seen in real-world applications.

Polynomial commitment schemes (PCS) are a fundamental building block of modern proof systems. As proof system applications scale to increasingly large workloads, distributed PCS become essential for reducing prover time and memory pressure. Among existing PCS constructions, code-based PCS achieve significantly better concrete prover performance than group-based schemes by avoiding expensive elliptic-curve operations and operating over small-characteristic fields. However, despite these advantages, code-based PCS are notoriously difficult to distribute. In this work, we present LigeSIS, the first distribution-friendly code-based multilinear PCS. LigeSIS achieves sublinear cross-node communication while keeping the final proof size independent of the number of machines. Our key insight is to replace Merkle-tree hashing with a homomorphic subset-sum hash over Goldilocks64, enabling algebraic aggregation of partial commitments produced by different nodes. To make this approach practical, we further introduce a preprocessing-accelerated subset-sum hash that reduces hashing overhead by up to $8\times$. Our evaluation shows that, on a single node, LigeSIS achieves performance comparable to the state-of-the-art RS-based PCS WHIR (Eurocrypt’25). In distributed settings, LigeSIS exhibits near-linear scalability in prover time. Compared with distributed MKZG (S\&P’25), LigeSIS achieves a $24 \times$ improvement in prover time. Compared with PIP (Security’26), LigeSIS reduces cross-node communication by up to $20\times$.

Blind signatures are a central tool for privacy-preserving protocols. They allow users to obtain signatures from a signer without the signer seeing the signed message. For instance, it enables electronic cash: signatures correspond to coins which can be issued by the bank in a privacy-preserving manner via blind signing. To mitigate the risk of key compromise, threshold blind signatures allow the distribution of the signing key amongst N parties. While recent works have focused on improving the security of this primitive in the classical setting, no construction is known to date in the post-quantum setting. We present the first construction of a threshold blind signature secure in the post-quantum setting, based on lattices. We prove its security under an interactive variant of the SIS assumption introduced in [Agrawal et al., CCS’22]. Our construction has a reasonable overhead of a factor of roughly 1.4 X to 2.5 X in signature size over comparable non-threshold blind signatures over lattices under heuristic but natural assumptions.

The advent of quantum computing poses a fundamental threat to classical cryptographic assumptions. While algorithms such as RSA and Elliptic-Curve Cryptography are secure against classical adversaries, they would be efficiently broken by a sufficiently powerful quantum adversary. Yet, despite rapid industrial and academic progress, the timeline for achieving a Cryptographically Relevant Quantum Computer (CRQC) remains uncertain and opaque. In this work, we propose a mechanism to monitor quantum capabilities through economic incentives. We introduce QCAP, a trustless distributed protocol for deploying a quantum canary address alert. QCAP enables the creation of publicly auditable cryptographic challenges whose solutions would reveal the existence of quantum computers capable of breaking the Elliptic Curve Discrete Logarithm problem. The protocol is decentralized, secure, efficient, and verifiable, featuring adjustable difficulty and native Bitcoin compatibility. A proof-of-concept implementation demonstrates the feasibility of QCAP as a Bitcoin-based early-warning system for the emergence of quantum computational power.

Reed–Solomon (RS) codes underpin a wide range of cryptographic protocols, from verifiable secret sharing (VSS) to blockchain data availability (DA). An RS code commitment enables a prover to distribute codeword fragments among many parties while allowing each recipient to verify that its fragment is consistent with a RS code. Existing constructions either rely on homomorphic polynomial commitments, which incur redundant commitments and expensive group operations, or use FRI-based interactive proofs, which achieve fast proving but suffer from prohibitively large communication. We present UltraProofs, a new RS code commitment framework that achieves linear-time proof generation while remaining compatible with any multilinear polynomial commitment. Our key technical contribution is an evaluation-consolidation protocol that reduces $n$ evaluation proofs at distinct RS points to a single randomized evaluation, eliminating redundant commitments and removing the need for homomorphic structure. We further design a tailored multilinear PCS, LightLigero, which achieves $O(\lambda \log n)$ proof size and maintains $O(n \log n)$ prover time. UltraProofs attains asymptotically optimal prover complexity with concrete speedups in practice: in VSS, it reduces prover time by $2.4\times$ and proof size by $4\times$ compared to HydraProofs (S&P'25); in DA, it cuts per-node communication by up to $2{\sim}5\times$ relative to FRIDA (Crypto'24) while retaining similar prover cost. By decoupling verifiable RS encoding from any specific PCS instantiation, UltraProofs provides a flexible, efficient, and modular foundation for large-scale verifiable storage and distributed cryptographic systems.

Several modern applications, such as Signal or WireGuard, use efficient Noise-like implicit authentication key exchanges that require only a small number of exponentiations and two interactions. These protocols have been proven to be secure under the 'strong Diffie–Hellman' (SDH) assumption in the random oracle model (ROM). At ESORICS 2021, Ramacher, Slamanig and Weninger presented an extension to the implicit authenticated key exchange security model, which enables strong privacy properties to be captured in addition to key-secrecy, including man-in-the-middle privacy (ensuring privacy even if a session is interrupted) and forward privacy. They also proposed a protocol to instantiate their model. In this paper, we present an efficient Noise-like protocol that achieve privacy in this model. Our protocol is as efficient as Noise-like protocols that do not guarantee privacy in terms of exponentiations. Moreover, our protocol requires three interactions, which is optimal for this privacy model. It is also more efficient than the ESORICS 2021 protocol in terms of both exponentiations and interactions. Finally, we propose another round-optimal protocol, slightly less efficient in terms of exponentiations, but secure under the CDH assumption in the ROM.

Non-malleable codes allow a sender to transmit a message to a receiver, while providing a ``best-possible'' integrity guarantee to ensure that no attacker---who cannot already decode the message---can meaningfully tamper the message in transit. If tampered, the received message should either be invalid or unrelated to the original message. Non-malleable time-lock puzzles (TLPs) are a special case of non-malleable codes for bounded polynomial-depth tampering with very efficient encoding. In this work, we give generic techniques for constructing non-malleable codes and non-malleable TLPs with improved rate, which captures the ratio of a message's length to its encoding length. A key contribution of our work is identifying a security notion for non-malleability, which we term ``CCA-hiding'', sufficient for our compilers. CCA-hiding is a relaxation of CCA-security for encryption or commitments to the fine-grained setting of codes, and requires that the encoded message remains hidden, even given a decoding oracle for any other codeword. Intriguingly, CCA-hiding does not imply non-malleability in the fine-grained setting, as is the case for encryption and commitments. Using our new techniques, we give the following constructions: -- Rate-1 CCA-hiding TLPs in the plain model. -- Rate-1 non-malleable codes for bounded polynomial-depth tampering in the auxiliary-input random oracle model (AI-ROM). -- Rate-(1/2) non-malleable TLPs in the AI-ROM.

Threshold Schnorr signatures enable $t$-out-of-$n$ parties to collaboratively produce signatures that are indistinguishable from standard Schnorr signatures, ensuring compatibility with existing verification systems. While static-secure constructions are well understood and achieve optimal round complexity, obtaining full adaptive security - withstanding up to $t-1$ dynamic corruptions under standard assumptions has proven elusive: Recent impossibility results (CRYPTO’25) either rule out known proof techniques for widely deployed schemes or require speculative assumptions and idealized models, while positive examples achieving full adaptivity from falsifiable assumptions incur higher round complexity (EUROCRYPT’25, CRYPTO’25). We overcome these barriers with the first round-optimal threshold Schnorr signature scheme that, under a slightly relaxed security model, achieves full adaptive security from DDH in the random oracle model. Our model is relaxed in the sense that the adversary may adaptively corrupt parties at any time, but each signer must refresh part of their public key after a fixed number of signing queries. These updates are executed via lightweight, succinct, stateless tokens, preserving the aggregated signature format. Our construction is enabled by a new proof technique, equivocal deterministic nonce derivation, which may be of independent interest.

Designing dynamic searchable symmetric encryption (DSSE) supporting conjunctive keyword queries over encrypted document collections is an important research area. Unfortunately, state-of-the-art conjunctive DSSE schemes such as ODXT (Patranabis et al., NDSS '21), and SDSSE-CQ and its variants (Zuo et al., PoPETS '25) either fail to achieve the desired levels of security (in particular, forward and/or backward privacy), or incur prohibitively large communication requirements and client-side computational overheads, which is undesirable for practical applications. In addition, all known conjunctive DSSE schemes that are both forward and backward private are quantum-broken due to their inherent reliance on discrete log-hard, prime-order cyclic groups. In this paper, we address the open question of designing practically efficient, low-leakage, forward and backward private conjunctive DSSE with small communication requirements and small client-side overheads. Towards this goal, we introduce the first systematic and rigorously formal notions of backward privacy for conjunctive queries that naturally extend the corresponding notions of backward privacy for single-keyword DSSE. Next, as our main contribution, we propose a new framework for conjunctive DSSE called fp-GA-ODXT that improves upon both ODXT and SDSSE-CQ-variants by achieving full-fledged forward privacy and strong backward privacy guarantees, while incurring small client-side computation and low communication overheads. We then demonstrate two instantiations of our fp-GA-ODXT framework: 1) A concretely efficient, classically secure instance based on discrete log-hard groups and an RSA-based trapdoor permutation, which we implement and benchmark. Our experiments demonstrate that we achieve smaller communication overheads and client-side computation for both updates and conjunctive searches as compared to both ODXT and SDSSE-CQ-variants. These come at the cost of a mild increase in server computation (which we view as an acceptable tradeoff in practice). 2) A post-quantum instantiation based on lattices and isogenies of supersingular elliptic curves, thus solving the longstanding open question of designing asymptotically efficient, forward and backward private conjunctive DSSE schemes with post-quantum security.

AI agents and custodial services are increasingly being entrusted as intermediaries to conduct transactions on behalf of institutions. The stakes are high: The digital asset market is projected to exceed \$16 trillion by 2030, where exchanges often involve proprietary, time-sensitive goods. Although industry efforts like Google’s Agent-to-Payments (AP2) protocol standardize how agents authorize payments, they leave open the core challenge of fair exchange: ensuring that a buyer obtains the asset if and only if the seller is compensated without exposing sensitive information. We introduce proxy adaptor signatures (PAS), a new cryptographic primitive that enables fair exchange through delegation without sacrificing atomicity or privacy. A stateless buyer issues a single request and does not need to manage long-term cryptographic secrets while proxies complete the exchange with a seller. The seller is guaranteed payment if the buyer can later reconstruct the purchased witness; meanwhile, the proxies remain oblivious to the witness throughout the protocol. We formalize PAS under a threshold model that tolerates the collusion of up to $t-1$ proxies. We also present an efficient construction from standard primitives that is compatible with Bitcoin, Cardano, and Ethereum. Finally, we evaluate a Rust implementation that supports up to 30 proxies. Our prototype is concretely efficient: buyer and seller computations take place in microseconds, proxy operations in milliseconds, and on-chain costs are equivalent to those of a standard transaction without fair exchange.

A proof of knowledge certifies that the prover “knows” a secret. This property is established by the existence of an extractor that, given access to the prover, can extract the secret. Unfortunately, this does not imply that a single entity has access to the secret in the clear, as it may be secret-shared among several parties and the proof computed using multiparty computation (MPC), or the secret may be embedded in a trusted execution environment (TEE) that only allows limited access to it. Often, the ability to encumber a secret in this way breaks the security of a system; vote selling in e-voting schemes is one example. To address this, two recent papers introduced the notions of “Proofs of Complete Knowledge” (PoCK) [Kelkar et al., CCS’24] and “Individual Cryptography” [Dziembowski et al., CRYPTO’23]. While the goals and constructions in those works differ, both rely on the same key idea to prevent encumbrance. To compute a proof, the prover must evaluate a hash function on a huge number of inputs. One then assumes that only a fraction of those can be encumbered, while for the rest the prover must know the inputs in the clear, and these clear inputs are sufficient to extract the secret. Computing a huge number of hashes is a challenge even for an honest prover (who has the secret in the clear), so those works suggest using outdated Bitcoin mining hardware to make the scheme practical. By forcing the prover to evaluate the hashes in a sequential manner, we could get meaningful security against encumbrance with far fewer hashes, especially against MPC, where round complexity is a major bottleneck. As a concrete instantiation of this idea, we define and construct Sequential Proofs of Complete Knowledge (SPoCK). Our construction uses the PoCK of Kelkar et al. (which are based on Fischlin’s straight-line extractable proofs of knowledge). The computation of this PoCK is then embedded into the computation of the Proof of Sequential Work from [Cohen&Pietrzak, EUROCRYPT’18]. SPoCK thus have the potential to enable complete-knowledge or individual-cryptography primitives where honest parties can use standard hardware. We also propose a variant of this scheme that requires a large amount of memory throughout the evaluation, providing better security also against TEEs.

A verifiable delay function (VDF), introduced by Boneh et al. [CRYPTO’18], on input $(x,T)$ produces an output $(y,\pi)$ where computing $y$ requires $T$ inherently sequential steps, and $\pi$ is a proof certifying correctness. VDFs have found numerous applications, and many of these rely on the assumption that honest parties can evaluate the VDF nearly as fast as adversaries. To support this assumption, significant effort has been invested in developing dedicated VDF hardware (ASICs). However, such devices are expensive and produced in limited quantities, leaving only a small number of parties with access to fast VDF evaluation. A natural workaround is to offer “VDFs as a service,” where a server equipped with specialized hardware evaluates instances on behalf of clients. This approach, however, is unsuitable when the VDF input must remain private. In this work, we introduce and construct blind VDFs, enabling secure VDF outsourcing without revealing the input. Inspired by blind signatures, our protocol allows a client to transform an input $x$ into a blinded instance $\alpha$, which is evaluated by the server. The server returns a result $\beta$, from this and its local state, the client can unblind to recover the correct output $(y,\pi)$, while the server learns nothing about $x$. We realize this notion by constructing a blinded version of Pietrzak’s VDF [ITCS’19]. In the original scheme, computing $y$ requires $T$ sequential steps, while generating the proof $\pi$ can be done in $O(T/S)$ parallel time using $O(S)$ space (e.g., $O(\sqrt{T})$ time and space). In our blind variant, the server performs the $T$ sequential steps and sends $O(S)$ data to the client, who completes the unblinding in $O(T/S)$ time. By allowing slightly more interaction, we obtain a protocol where the client’s work is small, while the server performs essentially the same computation as in the unblinded VDF.

We propose the first collaborative SNARK based on error-correcting codes that is scalable, i.e., the proof computation overhead is distributed among the $N$ provers. As a starting point, we introduce the notion of $(t,l)$-zero-knowledge collaborative codes that ensure that, when collaboratively computing a codeword over a distributed message, no coalition of up to $t$ corrupted parties learns any additional information about the message, even having queried up to $l$ codeword positions. We show that tensor codes consisting of the composition of two Reed-Solomon codes satisfy our definition, while also being foldable. We then propose a collaborative interactive oracle proof of proximity (coIOPP) for testing codeword closeness in our code, show how it can be made a zero-knowledge IOPP using randomness logarithmic in the size of the message (as opposed to linear with prior approaches), and we use it to construct a coIOPP for multi-linear polynomial evaluation. To compile our coIOPPs into non-interactive arguments, we prove that a natural extension of the compiler of Ben-Sasson-Chiesa-Spooner~(TCC 2016) in the collaborative setting preserves round-by-round (knowledge) soundness against quantum adversaries, which may be of independent interest for future work in collaborative SNARKs. Finally, we use an optimized collaborative version of the Spartan PIOP to build the first transparent and post-quantum secure scalable collaborative SNARK. Our experimental evaluation demonstrates that our scheme consistently outperforms the best existing (non-post-quantum secure) scalable collaborative SNARKs, both in end-to-end prover time and in total communication among provers, for all tested configurations.