This paper presents a new fuzzy private set intersection (FPSI) protocol, a two-party protocol to securely identify similar items across private sets. Our design departs from the prevailing separation-based paradigm---e.g., ``apart by $2\delta$'' or the disjoint projection assumption---which either incurs exponential overhead in dimensionality or requires high dimensionality to justify the assumption. Instead, we address this tension by explicitly allowing collisions within $\delta$-balls, but requiring that their multiplicity be bounded per axis. We formalize this new structural property as $C$-max collision. We theoretically analyze its plausibility on several common distributions, e.g., the uniform distribution, and real datasets, and provide an efficient algorithm to verify this assumption. Under the $C$-max collision property, we propose an efficient FPSI protocol for $\ell_{\infty}$ distance that supports both low- and high-dimensional regimes. Our construction is based on a novel abstraction that views FPSI as an oblivious intersection of membership tags, which natively handles axis-wise matching multiplicity. We capture its requirements through a new functionality called oblivious selected set intersection, along with its instantiation based on symmetric key techniques. Assuming the $C$-max collision property on the receiver's set, our protocol achieves computation/communication complexities scaling linearly with both parties' set sizes for a fixed $C$. We implement our protocol and conduct extensive evaluation. While a direct comparison is infeasible, ours achieves online efficiency comparable to state-of-the-art separation-based FPSI protocols in both low- and high-dimensional regimes.

Lattice-based polynomial commitment schemes (PCSs) promise post-quantum SNARKs with two properties that elliptic curves provide and hash-based schemes, today's deployed post-quantum default, do not: concretely small proofs and commitment time proportional to the number of nonzero entries in the committed polynomial rather than its length. The second property is essential to Twist and Shout (CRYPTO 2026), the fastest known memory-checking arguments and a core component of the Jolt zero-knowledge virtual machine (zkVM): their prover commits to enormous polynomials that are almost entirely zero. Yet despite a wave of recent work, existing lattice-based PCSs achieve at most two of the three properties that deployment demands: small proof size, fast verification, and soundness from standard assumptions such as Module-SIS. We present Akita, a lattice-based PCS that achieves all three. We improve on the square-root-time verifier of Hachi (ePrint 2026), our direct predecessor, through a new setup offloading technique: the public setup matrices are committed ahead of time, and the verifier's work in processing them is deferred and proved against these commitments. For any fixed $K\ge2$, this reduces verification time to $\widetilde O_{K,\lambda}(N^{1/K})$ while preserving $\widetilde O_{K,\lambda}(\log N)$ proof size, $\widetilde O_{K,\lambda}(N)$ prover time, and security from standard Module-SIS. We also optimize every fold from root to tail and iterate the fold to completion. This includes an optimized digit range check, relation-specific ring dimensions and subring challenges, complementary methods for embedding field evaluations and checking ring relations, commitments compressed to $128$ bytes each, and exact Euclidean norm checks for tighter Module-SIS parameters. Beyond the core protocol, Akita provides the capabilities needed for deployment in a zkVM: batched openings of separately committed polynomials, low-communication distributed proving, and an offline planner for selecting secure parameters under configurable cost objectives. We implement Akita in Rust and benchmark it against existing lattice-based and hash-based PCSs. Across these benchmarks, Akita produces proofs of only $58$–$68$ KB, matching Greyhound's when both schemes are calibrated to the same lattice-security target, while verifying $22.1\times$ to $108.7\times$ faster. Akita's prover uses the least memory: beyond storing the polynomial itself, its memory overhead grows sublinearly in the polynomial size. We also integrate Akita into Jolt. For every program size we evaluate, Jolt-with-Akita achieves a $2.2\times$ to $4.2\times$ prover speedup and $2.8\times$ to $8.5\times$ verifier speedup over Jolt-with-Dory, while producing comparable proof sizes, with every proof below $100$ KB.

Despite decades of cryptographic advances, electronic cash (e-cash) remains largely confined to payments and lacks the broader decentralized financial applications built around cryptocurrencies. As a step toward broadening its application layer, we present an issuer-independent e-cash exchange in which a liquidity provider holds inventories of two independently issued e-cash currencies and users trade between them without requiring either issuer to participate in individual swaps. Our design combines a blockchain settlement layer, which automates the exchange and makes its execution publicly verifiable, with an exchange-compatible e-cash protocol. Classical e-cash must be adapted to this setting in two respects: payments must become publicly verifiable by the exchange, and the additional privacy risks created by public execution must be addressed. We formalize these new privacy requirements and construct a compact e-cash realization with publicly verifiable payments and aggregate anonymous reissue. We prove the security and privacy properties of the resulting exchange protocol under the stated cryptographic and issuer-functionality assumptions.

The sumcheck protocol, a ubiquitous component of modern proof-systems, enables proving the sum of evaluations of a low-degree multivariate polynomial. In theory, sumcheck has been generalized from polynomials to (tensors of) any multiplication code, a code whose pointwise products of codewords lie in a related product code. All practical systems nonetheless specifically use polynomials. For proof-systems over binary fields that target Boolean circuits, this choice has a real cost: the product of two binary messages under Reed--Solomon is no longer binary. As a result, the prover's work in the first, and most expensive, round of sumcheck (the so-called univariate skip) grows by a logarithmic factor. We present a new concrete multiplication code based on algebraic geometry that is binary-preserving: the product of two encoded binary messages is again a binary message. Specifically, we construct an explicit multiplication code over $\mathbb{F}_{2^{128}}$ that carries $64$-bit messages to binary product messages of length $222$, and whose product code has relative distance greater than $1-2^{-119}$. The part of the product message that the prover actually sends in sumcheck is more than $3 \times$ smaller than with Reed--Solomon, as used in practice. The code comes from a genus-$95$ curve over $\mathbb{F}_2$ with $64$ rational points, built as a $(\mathbb{Z}/2)^3$ Artin--Schreier cover of a genus-$4$ curve. We implemented the resulting protocol, which we call the AG skip, inside the Flock proof-system. For $2^{32}$ constraints, it speeds up the skip round by $2.36\times$ and the whole zerocheck, which was the prover's most expensive component, by $1.65\times$.

In a single secret leader election (SSLE) protocol, all parties collectively and obliviously elect one leader. Parties other than the selected leader should not be able to learn the identity of the leader unless it is revealed by the leader itself. The problem is first formalized by Boneh et al. (AFT 2020), and the first concretely feasible lattice-based SSLE with proof-of-concept implementations, $\mathsf{Qelect}$, was recently introduced by Wang and Zhang (USENIX 2025). In this work, we present $\mathsf{Relect}$, an efficient SSLE protocol, based on the Ring Learning with Error assumption. We build it by leveraging the algebraic structure of the underlying threshold Fully Homomorphic Encryption (FHE) and by designing tailored homomorphic circuits. Compared to prior works, $\mathsf{Relect}$ (1) achieves substantially higher efficiency and (2) removes the strong environment assumption in $\mathsf{Qelect}$ (a trusted setup), while allowing dynamic leader selection for each round. Concretely, for $32$ -- $2048$ parties, our local FHE computation runtime (a major efficiency bottleneck for SSLE) achieves $7.15$ -- $42.4\times$ faster than $\mathsf{Qelect}$ for a single thread and $7.10$ -- $48\times$ faster for 16 threads. Furthermore, we show that for the same parameters, our communication cost is also $1.14$ -- $2\times$ smaller. As mentioned, this is achieved while removing the trusted setup. In terms of end-to-end runtime, following $\mathsf{Qelect}$, we tested $2$ -- $128$ parties. We show that under the LAN setting, $\mathsf{Relect}$ is $2.77$ -- $345\times$ faster than $\mathsf{Qelect}$ per round. Under the WAN setting, $\mathsf{Relect}$ is $1.94$ to $17.2\times$ faster than $\mathsf{Qelect}$. Note that these performance gains are all achieved while removing the trusted assumption and achieving dynamic leader selection for each round.

Facilitating value transfers with a scriptless chain is a longstanding problem in cryptography. We present a cross-chain messaging and value transfer protocol that maintains game-theoretic atomicity even when one party is operating on a chain which is fully scriptless, such as shielded Zcash, which has no scripting capabilities at all and requires transactions to be virtually identical. The observation is that consensus protocols which utilise segregated witness schemes to ensure transaction ID unmalleability (such as ZIP 244 in Zcash, SegWit in Bitcoin) segregate transaction data from the transaction witness component (which is the part that is actually signed). The transaction identifier is, therefore, a virtually collision-resistant commitment to the effects intended by the transaction, computable before signing, and in many chains, even without the knowledge of the signer. A contract on another chain can therefore recompute a future transaction ID from the few fields it needs to see, such as the recipient, the value and the expiry, while every other part of the transaction arrives as an opaque digest. It learns that any transaction with this ID has the agreed effect, without learning anything about the sender and without the recipient signing anything. An optional zero-knowledge layer hides the recipient and value as well. Combined with a light client for the settlement chain on the Turing-complete chain, this yields fully trustless verification that a shielded payment occurred, with no validator consortium or multisig that can be hacked or stalled.

Anonymous credentials enable privacy preserving authentication, but their transferability motivates binding each credential to a key protected by a secure element (SE). Such binding should preserve privacy even when the SE is remote or corrupted: every presentation must require fresh SE participation without revealing its context to the SE (Friedrichs et al., EC'26). Existing context-blind device-bound constructions rely on classical assumptions, whereas existing plausibly post-quantum anonymous credentials do not provide this functionality. We give a modular construction of context-blind device-bound anonymous credentials from a position-binding vector commitment, a signature scheme, a round-optimal blind signature, and a non-interactive zero-knowledge argument. We prove correctness, one-more unforgeability, unlinkability against a colluding issuer, verifier, and fully corrupted SE, and SE-obliviousness. We instantiate the construction with the CAPSS framework (Feneuil and Rivain, TCHES'26), Griffin/Jive Merkle commitments, and proofs of the complete presentation relation. For 16 attributes and four disclosures, using the Ligero-based proof backend from Longfellow (Frigo and shelat, CiC'26) yields a presentation taking 2.60 s on the user side and 0.29 s to verify, with a 506.11 KB proof. We also evaluate an Aurora backend for the same relation. We complement these measurements with published results to explore the proof-size/proving-time trade-offs offered by alternative transparent, plausibly post-quantum proof systems for relations of comparable size. To the best of our knowledge, this is the first concrete construction and evaluation of context-blind device-bound anonymous credentials assembled entirely from plausibly post-quantum components.

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

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

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

Symbolic formal verification of cryptographic protocols based on the Dolev-Yao (DY) attacker model—an active attacker with full network control and perfect cryptography—is well-established for finding design-level logical flaws in cryptographic protocols. Building on this, Dolev-Yao Fuzzing (DYF) enriches fuzzing with this attacker model to uncover logical bugs at the implementation level. In contrast to bit-level fuzzers (e.g., AFL), DYF leverages a formal model of messages and cryptography to generate structured, adversarial executions, such as replaying and re-signing a modified payload. However, a significant limitation of DYF is the requirement to precisely model properties to check at runtime (e.g., session parameter agreement). Defining these properties is labor-intensive and inherently non-exhaustive, often necessitating complex instrumentation of the Programs Under Test. Consequently, typically only a subset of logical attacks is detected. We address this limitation by introducing Differential Dolev-Yao Fuzzing (DDYF) based on a differential oracle to compare executions across different protocol implementations. By interpreting discrepancies through the DY model, it identifies semantic differences indicative of bugs or vulnerabilities, effectively minimizing false positives. We propose a generic design for DDYF, implement it within the PUFFIN DY fuzzer, and evaluate it on four major TLS implementations and two SSH implementations. Our results demonstrate that DDYF can detect vulnerabilities that evade state-of-the-art fuzzers, specifically those requiring DY attacker capabilities (missed by bit-level differential fuzzers) or complex objective oracles (missed by DYF). DDYF also uncovered numerous new RFC violations in OpenSSL, BoringSSL, wolfSSL, LibreSSL, libssh, and wolfSSH, which are by-design hardly detectable with non-differential oracles.

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

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

The Matter protocol has emerged as the leading standard for secure IoT interoperability, backed by major vendors such as Apple, Google, Amazon, Samsung, and others. With millions of Matter devices already deployed, its security guarantees are critical to the safety of modern IoT ecosystems. This paper presents the first in-depth analysis of Matter's key establishment protocols: Passcode-Authenticated Session Establishment (PASE) and Certificate-Authenticated Session Establishment (CASE), which are based on the well-studied SPAKE2+ and SIGMA, respectively. We first perform a specification-level security analysis of PASE and CASE, comparing Matter's design choices against the original SPAKE2+ and SIGMA protocols. This reveals weaknesses such as low-entropy setup passcodes, static per-device salts, and weak PBKDF2 parameters. Next, to assess how such weaknesses manifest in practice, we analyse a certified Matter codebase and find that critical safeguards such as limiting failed pairing attempts are not enforced. All identified vulnerabilities were responsibly disclosed and have been patched. We then complement our analysis by formally verifying PASE, CASE, CASE Resumption, and the original SPAKE2+ and SIGMA protocols. In particular, we show in the symbolic model that the security of Matter's lightweight session re-establishment mechanism (CASE Resumption), used for the vast majority of Matter sessions, rests entirely on the secrecy of an ephemeral key generated by an IoT device. Building on all three stages, we construct proof-of-concept attacks and evaluate their feasibility under Matter's own threat model. Our results invalidate several countermeasures specified in Matter's threat model, including protections for threats classified as ``High Risk''. Overall, our work shows that strong cryptographic building blocks alone are insufficient unless the surrounding protocol and deployment rules are equally rigorously specified and tested at the standard level.

Secure multiparty computation (MPC) is a key enabling technology for privacy-preserving applications. To achieve low latency after inputs are provided, many efficient protocols utilize preprocessing, and the landscape of preprocessing approaches is growing and diverse. Some recent works use variants of function-dependent preprocessing, leveraging additional knowledge on the function to be computed for even better performance. While the existing literature primarily focuses on performance, it is mostly overlooked that there exist different kinds of function dependence and what practical implications they have. We systematize the different flavors of function dependence, relating them to practical requirements beyond efficiency.

We present $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$ -- the first SNARKs that simultaneously achieve linear-time prover, sublogarithmic proof size, logarithmic verifier, and also feature updatable setups. Our constructions are provably secure in the Random Oracle Model (ROM) and the Algebraic Group Model (AGM). As a core technical contribution (possibly of independent interest), we reduce the communication complexity of the classical sumcheck protocol for multivariate polynomials from logarithmic to sublogarithmic, while retaining linear prover complexity. For degree $d$ multivariate polynomials in $\mu$ variables which can be decomposed into $\ell$ multilinear polynomials, our protocol achieves $O(\ell + d\log\log n)$ communication and $O(n)$ prover cost for $n = 2^\mu$. Our protocol leverages recently proposed multilinear polynomial commitment schemes (PCS) with linear-time prover and constant proof size. Multivariate sumcheck is a key ingredient in the design of several prover-efficient SNARKs, such as Spartan (Crypto '20), HyperPlonk (Eurocrypt '23), MicroSpartan (S&P '25), Hyrax (S&P '18), Libra (Crypto '19), Gemini (Eurocrypt '22), Virgo (S&P '20) etc. All of these SNARKs incur $\Omega(\log n)$ proof size, with the smallest concrete proof sizes ranging from 5KB-10KB for circuit sizes in the range of $2^{20}$-$2^{30}$. We compile variants of the Spartan and HyperPlonk multilinear PIOPs with our improved sumcheck to realize two new SNARKs, namely $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$, that support R1CS and Plonkish constraints, respectively. Both of them achieve $O(n)$ prover, $O(\log\log n)$ proof size, and $O(\log n)$ verifier, while avoiding proof recursion and non-black-box use of cryptographic primitives. We implement $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$, and compare their performances with several state-of-the-art prover-efficient SNARKs. For circuits of size $2^{30}$, $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$ achieve proof sizes of 1.9 KB and 2.4 KB, respectively, which are 2.4-3.6x smaller than the most compact prover-efficient SNARKs, while achieving comparable prover costs.

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

Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some certification authority. We propose a generic and efficient compiler that transforms any linear secret sharing based honest-majority MPC protocol into one with input authentication. Our compiler incurs significantly lower computational costs and competitive communication overheads when compared to the best existing solutions, while entirely avoiding the (potentially expensive) protocol-specific techniques and pre-processing requirements that are inherent to these solutions. For $n$-party honest majority MPC protocols with abort security where each party has $\ell$ inputs, our compiler incurs $O(n\log \ell)$ communication overall and a computational overhead of $O(\ell)$ group exponentiations per party (the corresponding overheads for the most efficient existing solution are $O(n^2)$ and $O(\ell n)$). Finally, for a corruption threshold $t<n/3$, our compiler preserves the stronger identifiable abort security of the underlying MPC protocol. No existing solution for authenticated MPC achieves this regardless of the corruption threshold. Along the way, we make several technical contributions that are of independent interest. This includes the notion of distributed proofs of knowledge and concrete realizations of the same for several relations of interest, such as proving knowledge of many popularly used digital signature schemes, and proving knowledge of opening of a Pedersen commitment.

Secure three-party computation with an honest majority is among the most efficient secure computation settings and is widely used in practice. However, achieving malicious security incurs significant overhead, often an order of magnitude higher than semi-honest protocols. Covert security provides a security–efficiency trade-off by detecting malicious behavior with a certain probability (e.g., $50\%$), deterring rational adversaries. Existing covert protocols mainly target two-party or dishonest-majority settings, with little work on efficient honest-majority three-party solutions. We present $\mathsf{ECHO}$, a family of concretely efficient protocols for covertly secure honest-majority three-party computation. We explore the design space of cheating detection and identification, and develop optimized protocols for both arithmetic and Boolean circuits, targeting different performance goals such as low latency and reduced communication. For arithmetic circuits over rings, our asymmetric-MAC-based protocol achieves an online phase only $1.26\times$ slower than the semi-honest baseline and over $5.59\times$ faster than malicious security. For Boolean circuits, our method improves over the best malicious protocol by $5\times$. We also applied $\mathsf{ECHO}$ on practical PPML tasks. $\mathsf{ECHO}$ approaches semi-honest performance while providing up to $8\times$ speedup over malicious security.

Finding shortest paths in graphs is a fundamental combinatorial optimization problem with numerous applications, e.g., in graph centrality measures, computational biology, and business process analysis. To address privacy constraints in such applications, Secure Multi-Party Computation (SMPC) protocols can compute the lengths of shortest paths on secret-shared graphs. Many such protocols have been proposed in the past, but they only compute the lengths of the shortest paths and not the paths themselves. In this paper, we close this gap by proposing two SMPC protocols that output secret-shared shortest paths. The first composes sub-protocols to calculate predecessors, to follow them, and to reorder wrongly positioned padding. Our second protocol optimizes the predecessor-following by decomposing it into sub-functionalities and proposing new sub-protocols for each. Further, the padding-reorder is replaced by a graph transformation. We evaluate our protocols across multiple network and security settings. Our optimized predecessor-following is up to 23 times faster than prior art, and our graph transformation is orders of magnitude faster than the padding-reorder. Overall, our second protocol is 5% to 49% faster than the first protocol due to the predecessor-calculation dominating the runtime on large graphs. Finally, we introduce a novel demultiplex protocol that, in fast networks, outperforms prior protocols on vector sizes up to 500, and on all evaluated vector sizes in slow networks. Due to the ubiquity of demultiplexes, this protocol is of independent interest.

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

Proving MIPS32 execution requires preserving branch-delay semantics while controlling the cost of heterogeneous instruction constraints. We present Ziren, a production zkVM for MIPS32r2 that supports 77 user-mode integer instructions and has proved Ethereum mainnet blocks end to end. Its arithmetisation embeds the program-counter pair in per-opcode instruction frames, eliminating the central CPU table. Each shard is proved with a single lookup argument, a zerocheck and a jagged commitment opened through batched WHIR; recursive aggregation uses an enumerated verifying-key allowlist. We mechanically extract 104 determinism theorems from the prover’s constraint description and discharge them in Lean 4. The kernel-checked proofs cover 57 of the core machine’s 62 chips, including precompiles, and establish unique outputs for fixed inputs under the declared lookup-table assumptions. The exclusions are three preprocessed tables and two SHA-256 control chips. We also formulate a cost model that separates trace cells and bus interactions per guest instruction from hardware-dependent proving throughput, accounting for instruction frames, shard-boundary memory rows and precompile expansion. On the evaluated Ethereum blocks, warm proving throughput reaches 12.0 MHz on one NVIDIA RTX 5090 GPU and 75.8 MHz on eight. Each proof stage has more than 100 bits of interactive soundness; a union bound for a tree with 149 core-schedule proofs and one root gives 93.5 bits of interactive composite security. End-to-end knowledge soundness remains conditional on five stated hypotheses, including enforcement of the recursion relation and computational binding of the cross-shard digest. No numerical security bound is established for that digest; the interactive estimates therefore do not quantify the full security of the deployed non-interactive proof.

Secure multi-party computation (MPC) enables privacy-preserving tasks such as auctions and voting. In practice, more than half of the parties may collude, making security against a dishonest majority desirable. Unfortunately, dishonest-majority MPC suffers from high communication and can achieve only abort security. For instance, in an auction, an adversary may abort after learning the outcome and rerun the protocol with a higher bid. Helper-aided MPC mitigates these limitations by introducing a semi-honest, non-colluding helper, a model that naturally fits settings with a central governing or coordinating entity and provides strong guarantees even when up to $n-1$ parties are malicious. The model assumes that the adversary can either semi-honestly corrupt the helper or maliciously corrupt up to $n-1$ parties (excluding the helper). While existing helper-aided protocols are fair i.e. either all parties receive the output or none do; they still allow the adversary to abort without any penalty and deny output to all parties. This behavior is undesirable in practice, as parties may incur the cost of computation without receiving the output. In this work, we design efficient helper-aided MPC protocols that achieve identifiable fairness: either all parties obtain the output, or—if an abort occurs—no party receives the output, and the honest parties identify at least one common cheater. We propose two protocols, $\mathsf{Alhena}$ for synchronous networks and $\mathsf{Wasat}$ for asynchronous networks which provide the stronger guarantee of identifiable fairness compared to the state-of-the-art fair protocols $\mathsf{Asterisk}$ (Kamarkar et al. IEEE S&P 2024) and $\mathsf{Castor}$ (Kamarkar et al. IEEE S&P 2026) in the respective network settings. Our experiments show that, in the online phase, $\mathsf{Alhena}$ and $\mathsf{Wasat}$ achieves speedups of $4-12.5\times$ and $2.5-5\times$ over $\mathsf{Asterisk}$ and $\mathsf{Castor}$ respectively. Furthermore, in the preprocessing phase, $\mathsf{Wasat}$ exhibits speedup of $\approx 3\times$ over $\mathsf{Castor}$. Notably, our protocols are designed in such a way that the online performance remains unaffected by active misbehaviour.

Private Information Retrieval (PIR) allows a client to retrieve an entry from a public database without revealing the entry of interest. Standard PIR, however, requires the server to perform expensive computation that is linear in the database size per client query. To reduce this online cost, Online-Offline PIR (OO-PIR) was proposed, allowing the client to precompute a query-independent hint table that enables sublinear online query complexity. Unfortunately, existing OO-PIR protocols require either a non-colluding two-server setting or a single-server setting with expensive periodic preprocessing, where the entire hint table must be rebuilt after a limited number of online queries. This results in extremely high bandwidth or computation overhead. We present ESCAPE, a novel OO-PIR protocol for the single-server setting that completely eliminates the expensive periodic preprocessing, supporting unlimited online queries in sublinear time with low constant response bandwidth. The core innovation in ESCAPE lies in reconciling a new hint sampling strategy with Linearly Homomorphic Encryption (LHE) to conceal the correlation between any hint and any online query, while allowing the consumed hint to be refreshed on the fly in sublinear time. We design a random sampling structure that aligns with deterministic, precomputable linear functions, enabling the protocol to exploit the streamlined preprocessing of efficient LHE instantiations. We fully implement ESCAPE, evaluate it on large-scale databases, and release our implementation as open source. Experimental results show that ESCAPE radically reduces end-to-end latency to under a second for 1-8 TiB database sizes and 8-16 KiB entries, achieving up to two orders of magnitude lower bandwidth and up to three orders of magnitude lower computation than state-of-the-art PIR.

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

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

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

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

Basically, public-key searchable encryption schemes require a linear search time with respect to the total number of ciphertexts. Xu, Wu, Wang, Susilo, Domingo-Ferrer, and Jin (IEEE Transactions on Information Forensics and Security, 2015) introduced Searchable Public-Key Ciphertexts with Hidden Structure (SPCHS). In SPCHS, ciphertexts associated with the same keyword are linked through a hidden structure that can be revealed using a trapdoor. This enables efficient extraction of matching ciphertexts and achieves optimal asymptotic search efficiency by traversing only the result set. However, a drawback of the SPCHS scheme and its subsequent works is that they are all pairing-based or rely on identity-based encryption (IBE) as a foundational component. To improve efficiency, this paper proposes a generic construction of SPCHS. Our core building block is Non-Interactive Key Exchange (NIKE), and the remaining components are symmetric-key primitives, namely secret-key encryption and a pseudorandom function (PRF). In particular, our search algorithm depends solely on these symmetric-key primitives and is independent of any public-key primitives. We implement the most efficient instantiation of the generic construction using Diffie-Hellman NIKE, an HMAC-based PRF, and AES. Our evaluation demonstrates that the search time of the DH-based instantiation is over 250 times faster than that of the asymmetric pairing-based scheme by Wang et al. (IEEE Transactions on Industrial Informatics, 2020). Moreover, we reduce the ciphertext size by a factor of approximately 10. In addition to this practical contribution of significantly improving efficiency, the proposed generic construction also makes a theoretical contribution by enabling the realization of the first set of post-quantum SPCHS schemes based on lattices, isogenies, and codes.

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

Verifiable Secret Sharing (VSS) ensures consistent sharing and correct reconstruction, but does not identify the shareholders involved. Traceable Secret Sharing (TSS) expands secret sharing with two guarantees: $\textit{traceability}$, which identifies the makers of a reconstruction box through black-box queries; and $\textit{non-imputability}$, which prevents false accusations against honest shareholders. However, full traceability is practically expensive: existing Shamir-based schemes require multiple carefully chosen queries to a $\textit{stateless}$ reconstruction box. Moreover, Goyal et al. (ePrint 2025/1980) show that the strongest form of black-box tracing is incompatible with simultaneously achieving non-imputability and tracer secrecy. We introduce $\textit{Accountable VSS}$ (Acc-VSS), a practical extension of VSS that achieves the next-best goal: $\textit{accountability}$, a strict relaxation of traceability requiring that (i) the contributors to every accepted reconstruction be publicly identifiable from its transcript with a $\textit{single}$ query, and (ii) no honest shareholder be falsely accused, even by an adversary holding all other shares. Accountability thus replaces black-box, multi-query tracing with a transcript check executable by any external verifier or smart-contract judge. In this paper, (i) we give a generic transformation from any computationally secure Shamir-based VSS to Acc-VSS, adding only one field element per share; it uses a long-term identity secret to each share and a conjunctive NIZK to bind partial reconstructions to the shareholder and the dealer's commitments; (ii) we instantiate it with Feldman and Pedersen VSS and prove the security of both schemes; (iii) we prove a self-contained $\textit{single-query}$ impossibility lemma motivating our relaxation; and (iv) we show how Acc-VSS uniformly yields accountable threshold ElGamal decryption, Schnorr/FROST signing, and distributed key generation. For the benchmarked VSS-based threshold-decryption protocol, accountability adds at most $20.3\%$ end-to-end overhead for $n=20$ and less than $6\%$ for $n=100$. Encrypted mempools, end-to-end-verifiable e-voting tallies, and validator-slashing in proof-of-stake systems all reduce to this framework.

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

Oblivious Transfer (OT) is a fundamental cryptographic primitive and a core building block for many multiparty cryptographic protocols. While existing OT extension techniques achieve excellent asymptotic efficiency for very large batches, their performance degrades when the total number of OTs is only moderate, since the cost of generating the required base OTs is no longer effectively amortized. In this work, we close this gap by presenting OT constructions that achieve square-root communication complexity for batched OT generation. Concretely, our most efficient protocol generates ell random OTs using O(lambda sqrt(ell)) bits of communication, where lambda is the security parameter. Our constructions are inspired by recent advances in homomorphic secret sharing and techniques for distributed discrete logarithm computation, and explore complementary points in the design space. The first construction is based on the Damgård-Jurik cryptosystem and standard assumptions, at the cost of a one-time trusted setup. The second eliminates the need for trusted setup, relying instead on a power-DDH assumption over prime-order groups. For 128-bit security, our schemes require approximately 2.6 KiB and 1.25 KiB of communication, respectively, to generate 128 random OTs, including the hash key in the power-DDH construction. Our best construction outperforms existing OT extension techniques for batch sizes of up to 32,768 OTs.

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

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

Most existing multiparty computation (MPC) protocols assume static and equal participation. All computing parties can dedicate resources and stay online for the entire computation, and they have equal influence on computation correctness and security (i.e., they are equally hard to corrupt). Supporting dynamic participation, so parties can join/leave at will, and associating weights to these parties reflecting their trust level, are essential to enable MPC in contemporary emerging applications. Existing solutions addressed these issues separately at varying security levels, and attempting to combine them while addressing malicious security raises several challenges and open questions. In this paper, we close this gap and develop maliciously-secure MPC protocols that support weighted participation in both static and dynamic (or fluid) settings. In particular, we extend prior work on weighted ramp secret sharing (WRSS) to support verifiability and proactivity, which could be of independent interest. Then, we show how to perform arithmetic operations over weighted shares in a verifiable way, thus enabling maliciously-secure weighted MPC with guaranteed output delivery under static participation. Utilizing the proactivity feature of our secret sharing scheme, we develop a state handover protocol and employ it to support dynamic participation in committee-based MPC with the same security guarantees. Both protocols are synchronous and assume honest majority. To the best of our knowledge, our work is the first to support both weighted and dynamic participation in MPC.

A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret unit vector across two or more parties. Despite growing ubiquity within applications and notable research efforts, the best 2-party DPF construction to date remains the tree-based construction from (Boyle et al, CCS'16), with no significantly new approaches since. We present a new framework for 2-party DPF construction, which applies in the setting of feasible (polynomial-size) domains. This captures in particular all DPF applications in which the keys are expanded to the full domain. Our approach is motivated by a strengthened notion we put forth, of programmable DPF (PDPF): in which a short, input-independent "offline" key can be reused for sharing many point functions. * PDPF from OWF: We construct a PDPF for feasible domains from the minimal assumption that one-way functions exist, where the second "online" key size is polylogarithmic in the domain size $N$. Our approach offers multiple new efficiency features and applications: * Privately puncturable PRFs: Our PDPF gives the first OWF-based privately puncturable PRFs (for feasible domains) with sublinear keys. * $O(1)$-round distributed DPF Gen: We obtain a (standard) DPF with polylog-size keys that admits an analog of Doerner-shelat (CCS'17) distributed key generation, requiring only $O(1)$ rounds (versus $\log N$). * PCG with 1 short key: Compressing useful correlations for secure computation, where one key is of minimal size. This provides up to exponential communication savings in some application scenarios.

We present an identity-based blind signature scheme built on the SM9 Chinese national cryptographic standard. The scheme outputs standard SM9 signatures, removes all online pairing operations through a single setup-time pre-computation, and adds only one user-side exponentiation to achieve blindness. We prove two properties rigorously: \emph{restricted target-identity unforgeability} (RTU) under the $Q$-BCAA1 assumption, and \emph{computational blindness} against a malicious signer in the random oracle model (ROM), where the signer is given the final signatures and still cannot link them to its protocol views. We state clearly that RTU is strictly weaker than the standard one-more unforgeability (OMU) notion for blind signatures: RTU forbids signing queries on the target identity and is therefore meaningful only when that identity encodes a fresh, one-time issuance context, as occurs in coin-, ballot-, and credential-issuance protocols. The $Q$-BCAA1 assumption is the inversion-type assumption that matches the SM9 private-key structure $d_{\ID}=[s/(s+\tau)]P_1$; it lets the reduction answer adaptive key-extraction queries without any decisional (Gap) oracle. We give a partial-blind extension with a formal partial-blindness model, discuss implementation requirements, and compare costs against prior SM9-based proposals.

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

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

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

Abstract. Recently, Dupin and Abelard [11] proposed a broadcast encryption scheme, outperforming the Complete Subtree-based and Subset Difference broadcast encryption in terms of encryption cost and bandwidth requirement. However, Dupin and Abelard acknowledge that the worst-case bound for bandwidth requirement of Complete Subtree approach can be reached in their scheme as well. In this paper, we answer the call to further reduce this bandwidth bottleneck. We first provide concrete analysis to show how this worst-case upper-bound is reached from particular Boolean functions. Our proof on [11]’s worst-case complexity demonstrates and shows that those Boolean functions, out of all 2^2^l possible Boolean functions of n variables, produces the worst-case upper-bound. Then we present two improved broadcast encryption schemes to significantly reduce this worst-case bandwidth consumption for further optimization of Dupin and Abelard’s technique. Our proposed ADC-BE suite, composed of two primitives, AD-BE and AC-BE, can significantly optimize this worst-case complexity from O(n/2) down to O(1) for a system of n users. This is efficient especially for large number of users in the system. Our schemes combines the algebraic normal form, disjunctive normal form, and conjunctive normal form to optimize a Boolean function to its minimized representation. Furthermore, our approaches support full range of Boolean functions without any restrictions, i.e., general access structures. This is more versatile than monotone access structure, where the group attribute policy is solely restrained to the Boolean clauses without bit-inversion nor negation. Last but not least, both AD-BE and AC-BE can be straightforwardly extended to post-quantum broadcast encryption schemes as the underlying hardness depends on one-way function, e.g., secure hash function.

Zero-knowledge proof (ZKP) schemes enable a prover to convince a verifier of the validity of a statement without revealing the underlying secret. These schemes have found extensive applications in secure communications, privacy-preserving transactions and blockchain technologies. However, the computational cost of proof generation remains a major obstacle to practical deployment. Although various acceleration techniques have been proposed, they often rely on specialized hardware that may not be locally available. A promising yet underexplored alternative is to offload computation to a more powerful third party, such as a cloud server, in a secure and efficient manner. Rather than outsourcing the entire proof generation process, selectively offloading the most computationally intensive operations offers greater flexibility and simplicity. In this work, we propose a secure outsourcing scheme for multi-scalar multiplication (MSM), which is the most computationally expensive operation in many widely used ZKP protocols. Our scheme enables users to delegate MSM computations to a server while preserving the confidentiality of the secret inputs (i.e., the scalars) and allowing verification of the server’s output. Our performance analysis shows that the proposed scheme significantly reduces the computational burden on the user while imposing only minimal overhead on the server.

We present a new framework for constructing practically efficient publicly verifiable secret sharing (PVSS) with $non-interactive$ $dealers$, in that the dealer may go offline after sending a single message, and is not involved in the share verification process. We use identity-based encryption (IBE) and commitments as the main ingredients and avoid expensive zero-knowledge proofs. By instantiating them with post-quantum secure schemes, a lattice-based IBE and a hash-based commitment, we obtain our first construction: a post-quantum secure PVSS with non-interactive dealers that outperforms the prior lattice-based practical construction by Gentry et al. [Eurocrypt 2022]. However, to enable the aggregation of PVSS transcripts (which facilitates many additional applications such as secure voting), we propose our second construction by replacing hash-based commitments with Pedersen's homomorphic commitments. While this does not achieve full-fledged post-quantum security (as Pedersen's scheme is not quantum safe), it still provides privacy against a post-quantum adversary. We prove the security of this construction in a new model, which we call long-lasting security. This model guarantees that the protocol is secure in the present (pre-quantum era) while maintaining privacy in the long term (post-quantum era). This new model is of independent interest for constructing efficient schemes that are resilient to the harvest-now-decrypt-later line of attacks. In this model, we propose a blockchain-compatible secure voting scheme using our PVSS scheme. Our PVSS schemes demonstrate practical efficiency: our post-quantum PVSS shares a secret among $1024$ receivers in $667$~ms and verifies the dealing in $<5$ ms, and communicates $4.4$MB, overall whereas the state of the art [Gentry et al., Eurocrypt 2022] communicates $251$MB and requires $2060$s for dealing the secret.

Verifiable computation systems often need to prove large matrix multiplication statements, but a direct SNARK arithmetization of a \(k \times k\) product requires \(\mathcal{O}(k^3)\) constraints. Freivalds' randomized check reduces the algebraic computation to vector-matrix products, but proving those products inside a SNARK still costs \(\mathcal{O}(k^2)\) constraints. We present LAMP, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing over linear error-correcting codes. The prover commits to encoded matrices and intermediate vectors before the sampled query positions are derived. The CP-SNARK circuit then checks only the sampled codeword positions and commits to the values used inside the circuit, while Merkle openings and CP-Link proofs ensure consistency between the in-circuit witnesses and the externally committed values. We prove soundness for this committed-input setting under the soundness of the SNARK backend, the binding of the commitments, the correctness of the CP-Link checks, and the relative distance and unique-decoding radius of the Reed--Solomon code. For a fixed number \(t\) of sampled positions, the main in-circuit SNARK relation has \(\mathcal{O}(tk+E_{\mathsf{code}})\) constraints, with additional \(\mathcal{O}(t\log n)+E_{\mathsf{link}}(k,t)\) backend work for Merkle openings and CP-Link checks. We implement LAMP in Go and compare it with a Freivalds-based SNARK circuit. In the matrix benchmark at \(k=2^{12}\), LAMP reduces the constraint count by \(9.68\times\) and shortens proof generation time by \(5.81\times\); verification remains approximately \(0.13\,\text{s}\) across the measured range.

Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S\&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced cryptographic protocols, namely password-authenticated key exchange (PAKE) and oblivious transfer (OT), by relying only on idealized symmetric-key primitives. They have become leading candidates for practically-implementable PAKE and OT due to (1) their simplicity, (2) their plug-and-play nature, allowing for flexibility in the choice of KEM, and (3) existing proofs of UC-security (in the classical adversarial model). Due to point (2) above, these compilers yield attractive candidates for efficient post-quantum PAKE and OT, especially given the recent post-quantum KEM standardization efforts. This motivates the question of whether the (UC-)security of these compilers translates to the quantum adversarial model. In this work, we show that it does not. In particular, we prove that a general family of (O)EKE protocols, as well as Masny-Rindal OT, are not UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. To establish UC-insecurity, we devise an adversarial strategy that provably thwarts any attempt by the simulator to extract its input (the password in the case of PAKE, and the receiver's choice bit in the case of OT). These are the first naturally-occurring/non-contrived cryptographic protocols that are known to be secure in the (classical) ROM but provably insecure in the QROM. To complement these negative results, we establish that both compilers yield certain notions of game-based security. In the PAKE setting, we consider OEKE instantiated with the ``2-Feistel'' cipher, and prove its stand-alone game-based security in the quantum random oracle model. We view these results as a proof of concept that security of (O)EKE and Masny-Rindal OT can yet be redeemed in the quantum setting, though we caution that the situation will be more subtle than in the classical setting due to the breakdown of simulation-based security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.

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

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

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

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

The 2019 edition of ITU-T X.509 adds three certificate extensions, colloquially called the Catalyst extensions, that let a single certificate carry a second, alternative public key and issuer signature beside the native ones, as a backwards-compatible path for migrating a public-key infrastructure to post-quantum cryptography (PQC). This paper collects the known problems of this multiple cryptographic algorithms (MCA) mechanism and adds several findings of its own. The central and previously known weakness is that a quantum attacker who recovers a single traditional certification-authority key can replace any certificate in a chain by a traditional-only one that a relying party still accepts. We give a precise attack model with a sub-CA and an end-entity-forgery variant to emphasize the inherent problem and propose three mitigating policies for relying parties which offer different degrees of protection and interoperability. As an example, we verify empirically that the susceptibility to this downgrade attack is present in the wolfSSL cryptographic library as a natural consequence. Our further findings concern the construction itself and details of the specification. For one, we analyze the formal violations of EUF-CMA that arise due to the possibility of re-purposing the extension signature to the established signed data format in X.509, which is formally manifest as soon as the alternative key in the extension is also certified as a native key. We show that several further aspects in the ITU-T mechanism remain undefined, which potentially leads to divergent behaviour of clients, and point out that a certificate accepted on its alternative signature alone, as allowed per ITU-T specification, can be invalid under RFC~5280 and potentially exposes an application to arbitrary injected data and even modified signatures chaining it to a certificate chosen by a non-quantum attacker in the positively validated certificate chain.

In a widely publicized recent announcement, Google established a formal 2029 deadline for completing its post-quantum cryptography (PQC) migration---one that deliberately preempts the 2035 deadline set by NIST and the US federal government to complete the deprecation of classical public-key algorithms. Google cited faster-than-expected progress across three fronts: quantum computing hardware development; quantum error correction; and revised estimates of the resources required for quantum computers to break current cryptographic schemes; as motivation for setting an ambitious internal target ahead of the regulatory horizon. This tightened deadline places particular pressure on existing cryptographic protocols that rely on classical key exchange primitives for secure communication. Our work aims to ease this transition by constructing a unified, formally analyzed security framework for migrating classical key exchange constructions to their post-quantum counterparts.

Succinct proofs for arithmetic modulo powers of two are crucial for verifying machine-word computations in practice. However, designing SNARKs over such rings is challenging, since they lack the algebraic properties that common SNARKs over fields rely on to achieve negligible soundness error. Existing approaches either work over Galois rings, whose arithmetic is expensive, or lift the statement to the integers and prove it over a large random prime field, which is also several times slower than the structured primes used in practice. We present $\mathsf{Rotor}$, an efficient SNARK for circuits over $\mathbb Z_{2^k}$. Unlike prior work, $\mathsf{Rotor}$ operates natively over power-of-two rings and derives its soundness from three levels of ring precision. To prove statements over $\mathbb Z_{2^k}$, we first construct a sumcheck-style interactive oracle proof with tensor queries over a larger ring $\mathbb Z_{2^m}$. We then establish a weakened proximity gap for linear codes, in which proximity testing over a still larger ring $\mathbb Z_{2^\ell}$ ensures that the underlying vectors are close to the code after reduction to $\mathbb Z_{2^m}$. This yields a Brakedown-style commitment with tensor evaluation proofs over $\mathbb Z_{2^m}$. In both cases, a sufficiently large gap between the precisions guarantees negligible soundness error. Finally, we introduce compatible commitments, which link ring witnesses to their binary-field representations and enable permutation checks over fields to verify permutations over $\mathbb Z_{2^k}$, completing the construction of $\mathsf{Rotor}$.

Secure multiparty computation (MPC) allows a set of parties to jointly compute a function while keeping their inputs private. Classical MPC protocols assume either a synchronous or an asynchronous network. Synchronous protocols tolerate more corrupted parties but rely on a timing bound, while asynchronous protocols make no timing assumptions but handle fewer corruptions. The network-agnostic model aims to combine the advantages of both. It requires security without knowing in advance whether the network is synchronous or asynchronous, guaranteeing resilience against up to $t_s$ corruptions in the synchronous case and $t_a$ corruptions in the asynchronous case. The optimal corruption threshold for perfect security has been established as $n = 2\max(t_s, t_a) + \max(2t_a, t_s) + 1$, but prior work either falls short of this threshold or requires exponential local computation. In this work, we present the first perfectly secure network-agnostic MPC protocol with polynomial communication and computation complexity under the optimal threshold. Our protocol achieves expected communication complexity $\mathcal{O}((|C|n + (D+C_I)n^2 + n^6)\log n)$ bits for a circuit of size $|C|$ over a finite field $\mathbb{F}$ of size $\mathcal{O}(n)$, depth $D$, and input size $C_I$. Our main technical contribution is a compiler that generates Beaver triples in the network-agnostic setting using synchronous and asynchronous triple-generation protocols in a black-box way. Beyond the cost of the underlying protocols, it only requires $\mathcal{O}(n^2)$ instances of network-agnostic Byzantine agreement.

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

As zero-knowledge proofs are used in real-world systems, they face threats such as resetting attacks, where an attacker manipulates the prover's randomness. While resettable security has been studied for interactive protocols, whether modern non-interactive systems such as zkSNARKs remain secure under resets is still unclear. This work provides the first systematic study of resettable security for NIZK arguments with three main contributions: - New Definition: We define strong resettable NIZK (srNIZK), which captures adversaries that can selectively reset the prover's randomness, so that some parts are reused while others are generated afresh. This goes beyond the whole-tape resets considered in standard rZK and is motivated by fault injection on secure hardware and incomplete state restoration in virtualized environments. - Concrete Attacks: We demonstrate that widely used NIZK constructions are vulnerable to resetting attacks. We show witness-recovery attacks against (i) Fiat-Shamir-compiled $\Sigma$-protocols (e.g., Schnorr), (ii) succinct proof systems using independently sampled masks (e.g., PLONK and Bulletproofs), and (iii) salted Fiat-Shamir compilations of a broad class of interactive arguments. - Generic Defense: Our simple compiler transforms any NIZK into an srNIZK by modifying only randomness generation, using a pseudorandom function (PRF) secure under partial key resets. This prevents resetting attacks without changing proof size or verification. Our results demonstrate that resetting attacks must be considered in NIZK systems, and provide a simple defense with minor prover overhead.

We design a novel robust secret-sharing scheme in the honest-majority setting for $n$ parties that allows constant communication per opening per party when amortized over $\Theta(n)$ simultaneous openings. We attain this scheme by a novel application of list decoding of folded Reed-Solomon codes. This was stated as an open problem by Escudero and Fehr (2023), who could obtain this amortized complexity only for $\Theta(n^2)$ simultaneous openings. Additionally, the dealing of such shares for a random value in a finite field $\mathbb{F}$ can itself be done using an honest-majority MPC protocol using only $O(n^2)$ multiplications between Shamir-shared values. This allows us to build an offline-online fully-secure (GOD) honest-majority MPC protocol, which has a fast online stage with amortized communication cost only $O(n)$ per multiplication gate (assuming the circuit has width $\Omega(n)$) and with no additional overhead, and an offline preprocessing stage with incremental communication cost only $O(n^3)$ per multiplication gate. This improves the previous best protocol in this setting by Escudero and Fehr (2023), which required the circuit to have width $\Omega(n^2)$. Further, the earlier scheme had an incremental preprocessing cost of $O(n^4)$ per multiplication gate. Due to requiring non-responsive rounds, the online stage of these protocols may still be concretely far less efficient than the online stage of the offline-online BGW protocol. Since the BGW protocol only provides security against fewer than $n/3$ malicious parties, we also devise a novel MPC protocol that boosts the BGW protocol's correctness threshold to $n/2$, while maintaining privacy and robustness thresholds at $n/3$, and with minimal online overhead. This is useful in applications, such as elections and auctions, where certification of a correct result is paramount. To achieve this correctness against fewer than $n/2$ malicious parties and to keep the pre-processing cost low, we use our novel robust honest-majority secret-sharing scheme, but only once during a final SPDZ-style attestation.

While decentralized identity management systems strive for autonomy, most still rely on centralized mechanisms (e.g., phone numbers or government-issued IDs) to achieve Sybil resistance and prevent fake identity attacks. This article proposes a novel approach for decentralized identity management that ensures robust Sybil resistance, unlike the systems currently in widespread use. Our approach is based on a social graph of connected users. The main novelty resides in pairwise mutual facial biometric verification for connected users and anti-Sybil social graph analysis. By leveraging blockchain technology, zero-knowledge proofs, and privacy-preserving smart contract platforms, the system ensures the uniqueness, anonymity, and privacy of registered users without relying on centralized authorities. We implemented a proof-of-concept prototype of our approach using fast Plonky2 zero-knowledge proofs and evaluated its functionality through simulations on heterogeneous social graph models with 1000 entities. To the best of our knowledge, this is the first work to propose a Sybil-resistant identity system that neither sacrifices decentralization nor privacy and does not rely on any centralized credential issuers.

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

Anonymity guarantees of privacy-oriented cryptocurrencies are garnering negative attention from lawmakers who view them as antinomic to accountability. Having recognized their potential for innovation, however, regulators may not want to outright ban privacy coins but instead seek a middle ground where financial oversight is effective, and still some privacy is maintained. Mature designs, such as Zcash, Monero, or Firo, are expected to facilitate this through so-called viewing keys that can be disclosed to third parties for the purpose of supervision. This paper studies which privacy guarantees continue to hold once they have been. In doing so, it fills the gap in provable anonymity guarantees for Zcash and Firo under the compromise of the incoming viewing key, but nevertheless shows that malicious parties may happily surrender all their viewing keys and still find very efficient ways of evading financial monitoring. Of independent interest are several shortcomings identified in the prevailing security arguments for Monero.

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

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

Secure multi-party computation (MPC) enables $N$ parties to jointly evaluate any function over their private inputs while preserving confidentiality. While decades of research have produced concretely efficient protocols for small to moderate numbers of participants, scaling MPC to thousands of parties remains a central challenge. Most of the existing approaches either incur per-party costs linear in $N$, due to pairwise computations, or rely on heavy cryptographic tools such as homomorphic encryption, which introduces prohibitive overheads when evaluating Boolean circuits. In this work, we introduce a new lightweight approach to designing semi-honest MPC protocols with per-party, per-gate computation and communication costs that are independent of $N$. Our construction leverages the Sparse Learning Parity with Noise (Sparse LPN) assumption in the random oracle model to achieve per-gate costs of $O(k^2 \cdot c(\lambda))$ computation and $O(c(\lambda))$ communication, where $k$ is the sparsity parameter for the Sparse LPN assumption and $c(\lambda)$ is an arbitrarily small super-constant in the security parameter $\lambda$. Assuming Sparse LPN remains hard for any super-constant sparsity, this yields the first semi-honest MPC protocol in the dishonest-majority setting with per-party, per-gate costs bounded by an arbitrarily small super-constant overhead in $\lambda$. Structurally, our MPC instantiates a Beaver-style MPC with the required correlations generated efficiently. Departing from prior approaches that generate Beaver triples either silently (Boyle et al., 2019; 2020; 2022) or through homomorphic computation (Damgård et al., 2012), our focus is on efficiently generating a weaker correlation. In particular, using Sparse LPN we show that if we relax the correctness requirement in generating random Beaver triples to permit a tunably small inverse-polynomial error probability, such triples can be silently generated with arbitrarily small super-constant per-party computation. We then show that such correlations can be used in an efficient online phase similar to Beaver's protocol (with a tiny super-constant factor blow-up in communication).

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

We advance the study of best-possible security guarantees of two-round secure multiparty computation in the plain model. While Goel et al. (TCC '21) showed the infeasibility of Identifiable Abort in two rounds in the plain model with a standard honest majority (i.e. $t < n/2$), the effect of relaxing the setting to an honest supermajority has not been established. In this work, we close this gap. When $t < n/3$, we show that two rounds are sufficient to achieve identifiable abort. Notably, ours is the first two-round general-purpose MPC construction in the plain model tolerating more than one corruption that achieves a guarantee stronger than unanimous abort. We obtain our construction via a new compiler that lifts any protocol with unanimous abort to one that achieves identifiable abort. A core building block for our compiler is Oblivious Public Transfer with Intermediaries (OPTI), a new primitive that we introduce which may be of independent interest.

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

DAG-based Byzantine fault-tolerant (BFT) consensus lets all validators propose concurrently, and uncertified designs such as Mysticeti skip per-block certification to achieve low latency. In existing partially synchronous round-based DAGs that use only hashing and standard signatures, however, every block references a quorum of previous-round blocks, so block metadata grows linearly with the committee size and, even in the happy case, the metadata communicated per round grows cubically. We present Bluestreak, a partially synchronous uncertified DAG BFT protocol that sparsifies block metadata using only hashing and standard signatures. A non-leader block carries at most two references, to its author's previous block and, optionally, to the previous leader; the leader reference is a vote. It may also name the leader of two rounds earlier as certified, a claim that its author has seen $2f+1$ votes for it. Only the single leader block per round references the latest block it knows from each validator, so committing it orders their chains. Because a sparse ancestry cannot justify the claims it carries, a node references a block only after verifying every claim in the block's history, and a pull-based pacemaker fetches the blocks and votes it is missing. We prove safety and liveness under partial synchrony and show that, in the happy case, block metadata amortized over a round is constant, per-round metadata communication is quadratic in the committee size, and, under idealized timing, the average end-to-end latency equals Mysticeti's: 4.5 message delays. In experiments with emulated ten-region wide-area delays, Bluestreak cuts average block metadata from Mysticeti's 13 KB to about 320 bytes at 400 validators, and matches or beats its median end-to-end latency at every committee size from 10 to 400.

Threshold signatures are widely deployed in decentralized asset custody and blockchain infrastructure to eliminate single points of failure. In these systems, an attacker can adaptively corrupt committee members based on public membership and protocol transcripts. Recent cryptanalysis shows this threat is concrete: schemes exposing per-party key commitments enable practical forgeries for committees of roughly 200 signers at the cost of just one minute of the global Bitcoin hashrate. While a new generation of signing schemes defeats this attack by hiding individual key shares, every distributed key generation (DKG) protocol used in practice exposes this information, voiding the adaptive security of any scheme built on top. Trusted dealers avoid the leakage but reintroduce the single point of failure that threshold cryptography exists to eliminate. True adaptive security must therefore span both key generation and signing. We present Janus, the first DKG suite to achieve this end-to-end guarantee. Janus serves as a drop-in replacement for a trusted dealer in threshold schemes, hiding all key shares while outputting a standard DLog public key compatible with existing verifiers, wallets, and smart contracts. Assuming secure erasures, we prove security against an adaptive adversary that corrupts members mid-protocol and controls a dishonest majority. We also show that Janus directly supports a variety of DLog-based primitives, including threshold Schnorr signatures and oblivious pseudorandom functions. Our suite includes Janus2R, which achieves an unbiased key in two rounds, and Janus1R, which completes within a single round by tolerating an additive key shift. When a node misbehaves, both variants generate a 259-byte universally verifiable proof for automated on-chain slashing, and both naturally allow committees to proactively refresh their shares without changing the public key. Our open-source Rust implementation completes key generation for a 16-node intercontinental committee in 310 ms and scales to 512 nodes.

We present Quintus, information-theoretic BFT protocols for tolerating $f < n/5$ Byzantine faults among $n$ parties. We present two protocols: The first protocol, Quintus-Fixed, is in a fixed view regime where views advance at a cadence $3\Delta$ time. This protocol incurs a good-case latency of $2\delta$ time where $\delta$ indicates actual network delay and message complexity of $O(n^2)$ in a view. The second protocol, Quintus-Responsive, is an optimistically responsive protocol with good-case latency of $2\delta$ time, $O(n^2)$ message complexity, and $2\Delta + 2\delta$ worst-case view latency where $\Delta$ denotes a pessimistic network delay parameter under synchrony.

Batch Private Information Retrieval (Batch PIR) allows a client to privately retrieve multiple entries from a public database while amortizing query costs. However, concretely efficient schemes typically rely on per-client server state, such as client-specific evaluation keys, which makes queries linkable across sessions and complicates deployment. In this work, we initiate the study of doubly-stateless Batch PIR, where the server stores no per-client state and the client maintains no database-dependent hint. For this model, we construct a communication-efficient scheme that substantially reduces communication compared with the natural baseline of adapting off-the-shelf Batch PIR schemes by sending fresh evaluation keys with each batch query. The core technical ingredient is a single-key RLWE unpacking procedure that replaces the traditional tree-based approach, which requires logarithmically many Galois keys, with a linear walk over a cyclic Galois subgroup requiring only a single Galois key.

We define an asynchronous ledger service ($\mathsf{AsyncLS}$) in the IITM-based universal composability (iUC) framework. The wallet-based service exposes a general state machine for a decentralized ledger-based application through registration, reads of committed application state, authenticated submission, and status queries with immutable final results. Each logical request binds the user's authorization to a finalized checkpoint and the applicable execution context. A confirmed outcome identifies the first eligible transaction and records application success or rejection. Strict expiry requires complete processing beyond the eligible height window with no recorded outcome, and certifies that the request has no application effect. We construct a protocol $\mathbf{\Pi}_{\mathsf{AsyncLS}}$ that realizes the ideal service using four components: Wallet, Relay, Adapter, and Replay. The proof separates the service construction from the implementations of Relay and Adapter while preserving ledger, clock, authentication, and setup interactions. We prove realization for the trusted and local implementations under their respective execution and trust assumptions. We use the service to construct an ORDI interactive payment and a parameterized execution layer above transaction ordering. These examples distinguish the ledger interaction protocol from the application state and effects exposed by the service. Each use requires the stated authorization, setup, ledger, clock, authentication, and ledger-effect assumptions.

Deploying Secure Multiparty Computation (MPC) to operate on data from real world sources requires many connective elements that have not received much attention in the literature. One prominent example is that MPC protocols typically assume conveniently structured data, whereas data in the real world comes in formats that are meant to be handled by string parsing engines. In this work, we give a new constant round protocol for securely parsing secret shared strings into an MPC-friendly format, built upon secure shuffle as a key primitive. Secure shuffle applies a permutation to a list while keeping both the permutation and the underlying data secret-shared at all times. While highly efficient protocols exist in the semi-honest setting, achieving malicious security has incurred significant overhead in both rounds and communication. We present Truffle, a new three-party shuffle protocol that is secure against one active corruption to bridge this gap. Truffle achieves an amortised round complexity that for the first time matches the state-of-the-art semi-honest protocol, while incurring only sublinear communication overhead. The core technique that underlies Truffle is a novel distributed verifier zero-knowledge proof that checks the correctness of a putative shuffle. We implement Truffle and show via benchmarks that it is performant enough to handle real application data. Beyond parsing secret shared data, secure shuffle finds applications in graph analytics, anonymous communication, Distributed Oblivious RAM, aggregate statistics, and secure sorting, each of which stand to benefit from the improvement that Truffle provides.

Oblivious Message Retrieval (OMR) enables recipients to retrieve messages from an untrusted server without revealing which messages correspond to them. OMR is useful for privacy-preserving systems such as anonymous messaging and blockchains. Existing constructions are inherently built in the public-key setting and use Fully Homomorphic Encryption (FHE) to allow a detector to scan a public bulletin board and produce a compact encrypted digest containing only relevant messages. However, this design incurs a major practical limitation: sender-published signals are large (hundreds of kilobytes), leading to significant bandwidth, storage, and on-chain costs. In this work, we explore the efficiency gains achievable by moving to a private, stateful setting, and introduce stateful OMR, a new model in which senders and receivers maintain lightweight private state to enable more efficient anonymous communication. Based on this model, we design StOMR, a protocol that significantly reduces the size of sender signals compared to prior approaches. To support the required shared state, we further introduce an OMR Key Encapsulation Mechanism (OMR-KEM), which allows users to privately establish shared state and instantiate stateful OMR without out-of-band channels. We implement StOMR in C++ and evaluate it against the state-of-the-art systems PerfOMR (USENIX Security '24), SophOMR (USENIX Security '26), and InstantOMR (USENIX Security '26). Our results show that StOMR preserves detector performance while achieving a signal size approximately 550×, 650×, and 178× smaller than PerfOMR, SophOMR, and InstantOMR, respectively.

Endowing Bitcoin with the ability to verify succinct proofs has been a longstanding problem with important applications such as scaling Bitcoin and allowing the Bitcoin asset to be used in other blockchains trustlessly. It is a challenging problem due to the lack of expressiveness in the Bitcoin scripting language and the small Bitcoin block space. BitVM2 is the state-of-the-art verification protocol for Bitcoin used in several mainnets and testnets, but it suffers from very high on-chain Bitcoin transaction fees in the unhappy path (over $14,000 in a recent experiment). Recent research BitVM3 dramatically reduces this on-chain cost by using a garbled SNARK verifier circuit to shift most of the verification off-chain, but each garbled circuit is 42 Gibytes in size, so the off-chain storage and setup costs are huge. This paper introduces BABE, a new proof verification protocol on Bitcoin, which preserves BitVM3's savings of on-chain costs but reduces its off-chain storage and setup costs by three orders of magnitude. BABE uses a witness encryption scheme for linear pairing relations to verify Groth16 proofs. Since Groth16 verification involves non-linear pairings, this witness encryption scheme is augmented with a secure two-party computation protocol implemented using a very efficient garbled circuit for scalar multiplication on elliptic curves. The design of this garbled circuit builds on a recent work, Argo MAC, which gives an efficient garbling scheme to compute homomorphic MACs on such curves.

Anonymous authentication schemes allow a user to prove they have been authorized by some issuer, without revealing any additional information about the user's identity. Two variants are currently seeing strong real-world interest. Anonymous tokens (ATs) allow one-time proofs of authorization, e.g., for privacy-preserving rate limiting as currently being pursued in the MoLE effort at the IETF. Anonymous credentials (ACs) incorporate attributes that can be selectively disclosed in an unbounded number of proofs; these underpin digital-identity systems such as the European Digital Identity (EUDI) wallet. Both anonymous tokens and credentials are envisioned as being deployed in systems with multiple issuers. In standard schemes, proofs reveal which issuer authorized a user, leaking more information than necessary and shrinking a user's anonymity set. To address this, there has been significant recent interest in issuer-hiding schemes that only reveal that the authorizing issuer lies in a specified policy set. We present generic constructions of issuer-hiding ATs/ACs based on key-randomizable signatures that give rise to several efficient instantiations. Specifically, we show efficient issuer-hiding ATs based on the Tessaro–Zhu blind-signature scheme, and efficient issuer-hiding ACs (without policy keys) compatible with existing BBS-based schemes.

We construct the first (conjectured) post-quantum Time Lock Puzzle (TLP) from isogenies. Our construction avoids setup/preprocessing and achieves non-trivial efficiency, where puzzle generation runs in time $\sqrt{T}$ . We prove security in the quantum random oracle model (QROM) under a new conjecture about the sequentiality of isogeny pushforward computations, for which we provide a thorough justification. The only other (conjectured) post-quantum TLP constructions rely on heavy cryptographic machinery from lattice-based assumptions. We also provide, to the best of our knowledge, the first proof-of-concept implementation of a candidate post-quantum TLP. On an Apple M3 CPU, for a one-hour target delay, total puzzle generation, including setup, takes 2.9 minutes serially and 100.5 seconds with four generation workers. Our experiments demonstrate the practicality of the complete design and show that the quadratic gap between puzzle generation and solving in theory also translates into a meaningful concrete separation. As a stepping stone towards our main result, we provide a new TLP from isogenies in the preprocessing model from a combination of the sequentiality of isogeny walks in the $F_{p^2}$ graph and the hardness of computational Diffie-Hellman (CDH) over cyclic prime-order groups. This improves the assumptions underlying the only known TLP from isogenies in the preprocessing model, which required pairing based assumptions instead of just discrete log. We further adapt this construction to achieve non-trivial efficiency of $\sqrt{T}$ in puzzle generation without setup/preprocessing.

We introduce MULTISS, a distributed storage protocol over multiple remote Quantum Key Distribution (QKD) networks that ensures long-term data confidentiality. MULTISS is designed to combine several QKD networks, as QKD links are inherently limited in range, and to connect these networks through classical cryptographic channels. It relies on a hierarchical secret sharing scheme that makes certain shares mandatory for the reconstruction of the original secret. Hence, MULTISS offers a secure distributed storage solution in a scenario that is compatible with the current deployment of quantum networks. We prove that MULTISS preserves the confidentiality of stored data even if an adversary (i) gains full access to all nodes of a subset of the QKD networks, or (ii) records all classical communications between distant QKD networks and compromises them at a later stage. We show that it provides strictly stronger security guarantees than existing QKD-storage protocols. Our protocol also includes a procedure to update the shares without reconstructing the original data. In addition, we provide a recovery mechanism that tolerates the complete compromise of some QKD networks. We further introduce a variant of the protocol, called the local-mode, that minimizes the communication overhead of the recovery procedure when deployed over specific network topologies.

The European Digital Identity Wallet (EUDI Wallet) is currently adopting ECDSA-based signed credentials as part of its core architecture, which raised concerns that such designs inherently lack plausible deniability compared to authenticated-channel approaches such as the German electronic identity card. This paper revisits this perceived trade-off and argues that it is not a property of signature schemes themselves, but of the credential presentation protocol. We show that standard cryptographic techniques - specifically lightweight OR-proofs over the native ECDSA verification equation - can be used to transform signed credential presentations into non-transferable, verifier-bound transcripts. Our contribution is not a new cryptographic primitive, but a careful instantiation of well-established techniques within the EUDI context, showing that deniability can be added to signed credentials while preserving their deployment advantages.

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

Secure coin-tossing is typically modeled as an input-less functionality, where parties with no private inputs jointly generate a fair coin. In the dishonest majority setting, however, a strongly fair coin-tossing protocol is impossible. To circumvent this barrier, recent work has adopted the weaker notion of game-theoretic fairness, where adversaries are rational parties with preferences for specific outcomes, seeking to bias the coin in their favor. Yet these preferences may encode secret information, making prior protocols that assume preferences are public, fundamentally incompatible with privacy. We initiate a comprehensive study of privacy-preserving game-theoretically fair coin-tossing, where the preferences of honest parties remain private. We propose a simulation-based security framework and a new ideal functionality that reconciles both preference-privacy and game-theoretic fairness. A key ingredient is a certifying authority that authenticates each party’s preference and publishes only aggregate statistics, preventing misreporting while hiding parties' preferences. The functionality guarantees that every honest party receives an output: either a uniform coin; or, if an adversary deviates, a coin that strictly decreases the adversarial coalition's expected utility. Within this framework, we construct a protocol realizing our ideal functionality under standard cryptographic assumptions that works for both binary and general $m$-sided coin-tossing. Our schemes tolerate the same optimal (or nearly optimal) corruption thresholds as the best known protocols with public preferences (Wu-Asharov-Shi, EUROCRYPT '22; Thyagarajan-Wu-Soni, CRYPTO '24). Technically, our protocols combine authenticated preferences with an anonymous communication layer that decouples identities from preference-dependent actions, together with a deviation-penalty mechanism that enforces game-theoretic fairness. Our work is the first to reconcile game-theoretic fairness with preference privacy, offering new definitional tools and efficient protocols for rational multi-party computation in dishonest majority settings.

Consider an asynchronous network of $n$ validators in which Byzantine validators hold less than one third of the stake. In erasure-coded reliable broadcast, validators relay fragments of the sender's message. A validator's relay-upload cost is the amount of fragment data it transmits outside the sender's initial dispersal. Assigning each validator a number of fragments proportional to its stake makes the heaviest validators relay far more data than the rest. We show that this imbalance is unnecessary. We give Balanced CT and Balanced MiniCast, adaptations of Cachin-Tessaro (CT) and MiniCast (Locher and Shoup, EUROCRYPT 2025) that retain stake-weighted voting but assign one fragment to each validator, giving every honest validator the same relay-upload bound. Their maximum relay-upload costs depend on how few validators can exceed one third of the total stake for CT, or two thirds for MiniCast. Stake skew can amplify MiniCast's advantage beyond the approximately twofold improvement in equal-stake networks. For the real-world Monad distribution with $n=200$, the leading maximum relay-upload costs, as multiples of the message size, are approximately $72.2$ for CT with proportional assignment, $8.7$ for Balanced CT, and $2.2$ for Balanced MiniCast. The balanced constructions pay for their low maximum cost with a higher total relay-upload cost. To reduce that total while retaining a prescribed maximum-cost bound, we give a new Capped Swiper heuristic. On eight real-world stake distributions, with at most $4n$ fragments per code, it lowers total relay-upload cost by 19-81% for CT and 16-71% for MiniCast relative to their balanced counterparts, while keeping maximum relay-upload cost at most 10% higher. We also give sender-aware variants of both constructions in which the sender relays no fragment data, reducing its per-broadcast burden.

While public blockchains provide transparent and auditable transaction histories, they inherently compromise user privacy. Existing privacy-enhancing protocols, such as those deployed on Ethereum, typically rely on succinct zero-knowledge proofs (zk-SNARKs) to obscure the transaction graph. However, implementing comparable cryptographic guarantees on high-throughput blockchains like Algorand is challenging due to strict per-call execution budgets and the state contention introduced by global Merkle accumulators. This paper presents Obscura, a decentralized, non-custodial privacy protocol tailored for constrained smart contract environments. Obscura achieves transaction anonymity using Linkable Spontaneous Anonymous Group (LSAG) signatures over the BN254 elliptic curve, verified entirely on-chain. To overcome limitations of the Algorand Virtual Machine (AVM), we introduce a novel state model that leverages Algorand's Box Storage for $O(1)$ commitment membership checks, eliminating the need for global Merkle accumulators, and a dynamic opcode-budget expansion mechanism via pooled inner application calls. Our implementation demonstrates that signer-ambiguous privacy is practical and efficient on Algorand without relying on trusted setups or succinct proofs. Obscura provides a robust privacy layer for transparent ledgers, bridging the gap between high-throughput blockchain architectures and the dual requirements of cryptographic privacy and selective auditability.

HAWK is a lattice-based hash-and-sign signature scheme that was a third round candidate in the NIST additional call for post-quantum signatures. It has short signatures and keys, as well as fast and portable signing and verification. However, in response to a highly-publicized AI-driven cryptanalytic result that reduced its security (roughly doubling the required dimension to achieve a given security level), the authors de- cided to withdraw from the competition. The need to increase parameters was seen as limiting the size advantage of HAWK compared to the already selected lattice schemes ML-DSA and Falcon, which was one of its primary selling points along- side speed and the lack of floating-point arithmetic. In this paper, we identify another attractive aspect of the HAWK design that is not affected by the AI attack and has been overlooked so far: its surprising friendliness to multi- party computation (MPC). Indeed, HAWK signing can be achieved in a generic way from a small collection of basic composable MPC functionalities (like integer multiplication, uniform random generation, etc.) in such a way that instanti- ating those functionalities using MPC protocols with given security properties (semi-honest vs. malicious, honest vs. dis- honest majority, etc.) yields a secure protocol for MPC signing with those same properties. As a result, we obtain Kettle, a UC-secure threshold signa- ture protocol that outputs specification-compliant HAWK sig- natures and scales to an arbitrary number of parties. It offers essentially the shortest signature size so far for a lattice-based threshold signature, while achieving significantly lower round complexity and online communication cost than other thresh- old protocols built from pre-existing, non-threshold lattice- based signatures (like ML-DSA and Falcon): as low as 2 online rounds (a dozen rounds total) and 2 kB online com- munication per party, depending on the specific setting and optimization choices. We also provide a proof-of-concept implementation of our approach in the MP-SPDZ framework, which can be instanti- ated with any number of parties, any threshold, and a variety of security properties.

In anonymous broadcast encryption, a ciphertext hides both the message and the set of recipients. In the general case, a lower bound of Kiayias and Samari forces the ciphertext to grow linearly with the number of recipients, a bound already met by the trivial per-recipient solution. The bounded universe is the setting where anonymous broadcast becomes concise, even asymptotically optimal and as efficient as the underlying public-key encryption. Far from a mere restriction, it is the building block for anamorphic communication against a dictator, where one must reach many (but boundedly many) recipients covertly, as put forth in the DPPY scheme at Eurocrypt '25. DPPY is, however, secret-key anamorphic encryption, where the broadcast layer itself must be hidden. Even a public-key variant does not suffice against a strong adversary, since a per-recipient public key lets a dictator ask for the matching secret key. This motivates hiding identities directly, with no recipient public key published, leading to identity-based anonymous broadcast in the bounded model, the focus of this paper. Technically, projective sampling (Ling, Phan, Stehlé and Steinfeld, LPSS, CRYPTO ’14), the tool underlying concise anonymous broadcast encryption, offers no key extraction: private keys cannot be produced from a projected key fixed in advance. We introduce trapdoor projective sampling that reverses the order of key generation in projective sampling: projected keys are fixed first as hashes of identities and compatible private keys are then preimage-sampled with a trapdoor. Adding a trapdoor is always a challenging objective, and we achieve it by showing that the LPSS projection space can be made far narrower - from m×(m−n) down to m×2n - without breaking the k-LWE security argument, and it is exactly at this width that the projection matrix can be generated with a trapdoor. We formalise the notion of trapdoor projective sampling with new security requirements, instantiate it from k-LWE, and obtain an identity-based anonymous broadcast whose ciphertext is as in LPSS, DPPY schemes. We also extend it to an unbounded identity universe under static corruption, with target sets kept bounded and adaptive.

In this paper, we propose Titan, an efficient polynomial commitment scheme (PCS) with transparent setup. It achieves commitment time of $O(n)$, evaluation time of $O(\sqrt{n})$ while the proof size and verification scales as $O(\sqrt[4]{n})$. Titan features an order of magnitude smaller proof sizes than hash based PCS, while featuring a significantly more efficient prover and verifier compared to state of the art group based schemes like Dory and Hyrax. To achieve this balance, Titan borrows two-tiered commitments from Dory, and realizes outer commitment using interactive protocols of proximity (IOPP) over groups, such as Basefold and WHIR, instead of expensive bilinear pairings. This allows Titan to be instantiated over general curves with discrete-log hardness such as Pasta Curves, instead of requiring pairing friendly curves. We compile a variant of Spartan protocol for R1CS with Titan PCS to realize a SNARK. Our SNARK construction preserves the prover efficiency of the existing Spartan protocol, while improving proof size and verification quadratically from $O(\sqrt{n})$ to $O(\sqrt[4]{n})$. Concretely, for circuits of size $\geq 2^{22}$ this results in around $3\times$ more efficient proof size and verification. Our blueprint of combining IOPPs over groups with Pedersen style inner commitments is of independent interest, as are several optimizations towards efficiently realizing WHIR IOPP over prime-order groups.

We introduce BitZ, a hash-based Polynomial Commitment Scheme (PCS) for committing to multilinear polynomials $\mathbf{f}$ with coefficients in an arbitrary finitely generated ring $S$, e.g.\ a finite field $\mathbb{F}$, the integers $\mathbb{Z}$, a cyclotomic ring, etc. Moreover, given another arbitrary ring $R$ and a ring homomorphism $\psi:S\to R$, BitZ then proves evaluation claims over $R$ for the polynomial $\psi(\mathbf{f})$. BitZ's costs depend almost exclusively on the number of bits in the coefficients of $\mathbf{f}$, and not on $S$, $R$ or $\psi$. Moreover, BitZ provides range checks (or more generally, bit-size checks) essentially for free. BitZ can thus be used as a PCS in essentially any proof system. We do so to build a SNARK, called BitZ-SNARK, for integer polynomial constraints, following the fingerprinting technique of Campanelli and Hall-Andersen, where one commits over $\mathbb{Z}$ and proves the constraints over a random prime field $\mathbb{F}_q$, i.e. BitZ is deployed with $S=\mathbb{Z}$, $R=\mathbb{F}_q$, and $\psi$ reduction modulo $q$. BitZ applies equally to other ring-based proof systems, or field-based ones. To commit to $\mathbf{f}$, BitZ first decomposes $\mathbf{f}$ into a string of bits, and then commits to it over a binary field $\mathbb{F}_{2^{\nu}}$, in packed form. The scheme then proves the linear claim on $\psi(\mathbf{f})$ over the arbitrary ring $R$, even though it committed to the bits forming $\mathbf{f}$ over a binary field. We implement BitZ-SNARK and use it to prove, among others, SHA-256 hashing followed by ECDSA signature verification; RSA modular exponentiation and Poseidon hashing; integer multiplication; and SHA-256 hashing followed by multiplication modulo $2^{32}$, consistently obtaining better performance than prior approaches on most tasks. As an example, we achieve a throughput of $9$ million proved 32-bit integer multiplications per second on a MacBook Air M5 24 GB (10 threads, CPU-only) with proof sizes under $200$ kB. We prove a SHA-256 hash of a $2$ kB ($2^5$ compressions) message followed by a P-256 ECDSA signature verification with $32$ ms and $3.1$ ms prover and verifier time, respectively, and with a proof of $65$ kB, single-threaded. With $10$ threads the times are $17$ ms and $3.7$ ms.

In this paper, we propose an understanding of classical Sigma protocols (as denoted by $\Sigma$-protocols in the literature) through the lens of the MPC-in-the-head (MPCitH) paradigm. We seek not to construct new schemes, but to build a formal bridge connecting these two foundational areas. While many elegant yet foundational Sigma-protocols were introduced decades ago as standalone algebraic or combinatorial interactive proofs, reconsidering them via the modern aspect of (extended) MPCitH significantly enhances our cryptographic insight into their underlying structures. We present a formal mapping that translates classical commitment-challenge-and-response into the internal views of virtual parties, communicating via private point-to-point or public broadcast channels, secret-sharing schemes, commitments, and MPC consistency/correctness checks. By deconstructing algebraic schemes as linear secret-sharing protocols over public channels and combinatorial schemes as discrete threshold MPC instances over private/public channels, we isolate the exact structural reasons why their soundness and efficiency characteristics diverge. The protocols include: - Algebraic schemes: Schnorr, Okamoto, Chaum-Pedersen, Guillou-Quisquater, GMR for QR and discrete log over an unknown-order group. - Combinatorial schemes: Stern, GMW for Graph 3-Coloring, and Graph Isomorphism, among others. Although reinterpreting these already elegant, classic proofs using a heavy-weight machinery like MPCitH might seem redundant, it deepens our understanding of their underlying design principles.

In real-world applications of SNARKs, non-native arithmetic, the emulation of computation outside of the specified SNARK field, is a key bottleneck. It introduces large overheads, and proof system designers often resort to non-standard SNARK-friendly hash-functions or other means like elliptic curve cycles to mitigate its costs. Besides performance concerns, non-native circuit arithmetization is also a major cause of implementation errors. In a collection of 27 critical bugs in real world ZK systems (0xPARC/zkbugtracker), 9 were related to non-native arithmetization. We tackle these challenges by constructing a minimal overhead SNARK for integer computation that generically handles non-native arithmetic. We follow the recipe of Zaratan (PKC 26), which proves an integer relation such as $a\cdot b = c + u\cdot m$ by fingerprinting---reducing it to the same relation but over a randomly sampled prime field. Realizing this recipe requires an integer mod-PCS that commits to integer polynomials and opens their evaluations modulo a random prime, which is crucially chosen after the underlying PCS's setup and commitment phases. Our central contribution is Limber, the first practical integer mod-PCS construction that asymptotically has $o(1)$ multiplicative commitment overhead and can be instantiated with any standard field polynomial commitment scheme, including ones over small fields. Combining Limber with a PIOP for integer R1CS over the random prime yields our SNARK. We demonstrate its practicality by implementing our scheme and showing that we can prove an RSA accumulator benchmark $15$-$30\times$ faster than circuit-based approaches, and non-native Poseidon2 hashing $24\times$ faster.

Binary codes used in correlation generation and proof systems need strong distance, fast ordinary and transposed encoding, and regular memory access. We introduce Single-Permutation INterleaved (SPIN) codes, combining a blockwise outer encoder, one global interleaver, and a recursive inner. Our main result is a Structured SPIN family with rate $1/2$ and $O(N)$ bit operations for ordinary and transposed encoding at its native output lengths $N$. With probability $1-o(1)$ over the random choice of the code, its minimum distance exceeds $0.11N$. The proof combines outer spectrum bounds with an analysis of structured support spreading and recursive state mixing. We formally verify these distance and rate guarantees in Lean. For finite lengths, a BCH-derived outer constituent and a fixed recursive inner give rate $1/2$ and relative distance greater than $0.10$, with setup-failure probability below $2^{-40}$. We certify this bound at message lengths $2^{16}$, $2^{18}$, $2^{20}$, $2^{22}$, and $2^{24}$ using rigorous spectrum inequalities, without assuming the constituent's exact weight spectrum. For pseudorandom correlation generators (PCGs), SPIN's transposed encoder computes $2^{20}$ $128$-bit correlation blocks in about $9.3$\,ms on one Ryzen 9 7950X thread after precomputation. This is approximately $3.4\times$ faster than the original rate-$1/2$ BAA codes of Kolesnikov et al.\ (CRYPTO 2026). Ordinary encoding has similar cost. With a precomputed code, libOTe's regular-noise Silent OT sender achieves $89.0$ million hashed OTs per second on one core, in batches of $2^{18}$. Timings exclude initial setup, base-correlation generation, and network transport. We also use SPIN in a Brakedown-style polynomial commitment scheme and integrate it into Flock. Commitment and one opening of $512$\,MiB take $509$\,ms on one core, with a 100-bit interactive fixed-matrix testing target; this excludes code-setup failure, extraction, and Fiat-shamir reductions. Within an optimized Flock implementation, replacing Ligerito with SPIN--Brakedown improves prover throughput by $1.63$--$2.29\times$ at the measured workloads, with larger proofs and slower verification. The comparison gives both backends the applicable shared implementation optimizations.

We construct fast linear codes over large fields using addition-only encoders and variants with small integer coefficients. A local precode is followed by rounds of a random permutation and a scan, a linear recurrence with a short feedback window. At dimension $2^{20}$, rate $1/2$, and $p=2^{128}-159$, two plain accumulators (unweighted prefix sums) give relative distance above $11.7\%$, except with probability below $2^{-49.64}$ over the sampling of the encoder. A binary subset-sum precode instead gives distance above $12.56\%$, except with probability below $2^{-22.05}$. These addition-only encoders use fewer than $6.8125n$ and $3.3125n$ field additions, respectively, for output length $n$. Both exceed the binary rate-$1/2$ Gilbert--Varshamov benchmark. The proof counts the supports and ranks of the zero equations a codeword must satisfy, retaining the dependence between cancellations. Coefficient size and scan width extend the tradeoff. On one core, with a common implementation and setup failure below $2^{-40}$, encoding time ranges from $12.171$ ms at proved distance above $11.7\%$ to $32.342$ ms above $42.987\%$. A coefficient-independent upper bound limits every encoder with two width-one scans after the Newton precode to $39.6855\%$. The distance and setup-failure bounds hold over $\mathbb F_p$ and every finite extension, covering all nonzero messages after setup. Timings are for $\mathbb F_p$. Extension preserves distance exactly because the encoder coefficients lie in the prime subfield. Changing characteristic requires a separate argument; we give field-transfer results in both directions, including counterexamples.

We prove that Expand--Accumulate (EA) codes approach the Gilbert--Varshamov (GV) distance as the code length grows. The result holds over the binary field and every fixed finite field. At fixed rate, encoding uses $O(n\log n)$ expected field operations, with a tunable inverse-polynomial probability of sampling a bad code. Fixed-memory wrapped binary Expand--Convolute (EC) codes satisfy the same guarantee. Allowing $O(n\log^2 n)$ expected field operations makes sampling failure negligible in the code length. These codes combine a sparse random linear map with an invertible recursive map. Our analysis uses exact input--output weight enumerators in place of the earlier concentration bounds. It also gives tighter constants in the logarithmic expected degree. For EA-based pseudorandom correlation functions, these bounds improve the degree--distance tradeoff that controls local evaluation cost. Separately, we obtain finite-length bounds at small degrees by replacing independent incidence with regional regularity. At rate one half, a two-sided regular EC ensemble with left/right degrees $10/5$ and memory $15$ reaches $99.99\%$ of the binary GV distance. The probability of sampling a generator below this distance is less than $2^{-32.49}$. We extend the construction to finite fields using independent nonzero edge labels and full-field convolution coefficients. These coefficients mix field components; scalar extension of a binary matrix does not. Over $\F_{2^{128}}$, degrees $24/12$ with memory $5$ reach $98.41\%$ of the rate-one-half GV distance with sampling failure below $2^{-45.03}$; degrees $26/13$ with memory $4$ reach the same distance with failure below $2^{-135.20}$. Every finite claim is certified with outward-rounded interval arithmetic. The results concern minimum distance of sampled ensembles; they do not provide a decoder or a complete protocol-security proof.

We give fully distributed multi-point function (DMPF) constructions that share a sparse map over a domain of size $N$. Setup takes secret-shared indices; each later expansion takes new payloads for those indices and returns shares of the map. Our main construction, Waterfall Cuckoo, samples public hashes before assigning the inputs to bins. An occupancy scan followed by bounded repair finds the assignment; a hidden permutation conceals it during routing. Sparse DPFs then provide $4N$ or $3N$ leaf work per expansion, replacing the $tN$ work of $t$ independent DPFs. We prove correctness and semi-honest simulation in the ideal-subprotocol model, with an explicit routing-error bound. For the random sparse supports in Ring-LPN PCGs, we also give Reverse Cuckoo, a $2N$-expansion specialization. It programs hashes around a hidden placement and leaks information about the support: in the ideal hash model, outputs are weighted by their number of valid placements. We characterize the idealized leakage, state the additional decisional Ring-LPN assumption, and evaluate leakage-aware decoding attacks. A separate analysis bounds the concrete hash evaluator's batch correctness error below $2^{-40}$ at ring degree $2^{20}$ with the support-rejection filter specified in the analysis. Our measurements use a variant of this specialized Reverse-Cuckoo pipeline without support rejection or AES rekeying, and with different mask, permutation, and evaluator-seed sampling rules. At degree $2^{20}$ it produces 1.81 million Goldilocks-field OLEs per second, with 12.99 MB communicated per expansion. Against the reported FHE baseline at the same field and degree, these figures give $6.57\times$ higher throughput and $13.60\times$ lower expansion communication. Setup costs and comparisons with the sum-of-DPFs baseline are reported separately. Waterfall's costs are modeled; gains for other fields, rings, and PCG constructions remain application-dependent.

Verifiable Secret Sharing (VSS) allows a dealer to distribute a secret among $n$ parties so that each can verify their share's validity, and any qualified subset can reconstruct the secret. Publicly Verifiable Secret Sharing (PVSS) extends VSS by enabling anyone to verify the correctness of distributed shares. Both VSS and PVSS schemes are core building blocks in many cryptographic applications. We introduce a $k$-batched and $l$-packed extension of $\Pi$, a unified framework from PKC 2025 for Shamir-based computational VSS in the synchronous setting with optimal resilience. Our framework enables the sharing and verification of $l\times k$ secrets in a single protocol execution, offering a tunable trade-off between efficiency and robustness: the $k$-batched, non-packed variant ($l=1$) improves performance while maintaining optimal resilience, whereas the $k$-batched, $l$-packed variant achieves even greater efficiency at the cost of slightly reduced fault tolerance. Using this framework, we construct several Batched and Packed (BP) VSS and PVSS schemes that significantly reduce both computational and communication costs for the dealer and parties. When sharing many secrets, two of our VSS schemes and our PVSS scheme perform almost as efficiently as plain Shamir sharing. For example, when sharing more than 100 secrets, the overhead of our hash-based BP-VSS is below 3%, for our BP-VSS with information-theoretic privacy it remains around 8%, and for our BP-PVSS it is under 1%. These results show that verifiability in Shamir secret sharing can be achieved in post-quantum and large-scale settings with negligible overhead for the dealer. Our proposed BP-PVSS scheme is the first that can achieve these properties and outperforms existing state-of-the-art protocols. We discuss several applications and, as a concrete case study, use our BP-PVSS scheme to revisit the ALBATROSS randomness generation protocol from ASIACRYPT 2020, yielding a more efficient variant.

Secure multi-party computation (MPC) considers the problem of securely computing a function across $n$ parties such that no adversary controlling $t$ corrupted parties may learn any additional information beyond the function output. For information-theoretic security in the honest majority setting, recent works have made tremendous progress in reducing the MPC communication costs for large circuits obtaining as low as $\tilde{O}(|C|)$ total communication. To date, all information-theoretic MPC protocols require an additive $\tilde{\Omega}(n^2)$ communication independent of the circuit size that becomes the dominant cost for small circuits. In this work, we consider the problem of building more efficient information-theoretic MPC protocols with $o(n^2)$ communication for small circuits. For corruption threshold $t< (1/2-\epsilon)\cdot n$, we present an information-theoretic MPC protocol secure against adaptive and malicious adversaries with subquadratic communication for a wide range of circuits, including those in which the number of input parties $I$ satisfies $|I| = o(n)$, circuit size $|C| = o(n^{1.5}/|I|)$, and circuit depth $\mathsf{depth}(C) = o(n)$; for example, $|C| = o(n^{3/4})$ and $|I| = o(n^{3/4})$ input parties. To our knowledge, this is the first information-theoretic MPC protocol with $o(n^2)$ communication for a wide-range of circuit classes. Furthermore, we note the requirement of sublinear input parties $|I| = o(n)$ is necessary to obtain $o(n^2)$ communication due to the $\Omega(|I| \cdot n)$ lower bound by Damgård {\em et al.} [EUROCRYPT'16]. To obtain our new MPC protocol, we develop new techniques for key MPC subroutines including randomness generation, player virtualization and output reconstruction with $o(n^2)$ communication leveraging the sublinear number of input parties, $|I| = o(n)$, and randomized output distribution with unpredictable communication patterns. Finally, we also prove a separation showing that $o(n^2)$ communication MPC is impossible for adversaries with stronger than standard adaptive rushing capabilities even for constant-size circuits.

Homomorphic secret sharing (HSS) enables non-interactive distributed evaluation of functions on secret-shared inputs. While two-party HSS is well understood, multiparty constructions remain limited in expressiveness and efficiency. We present a general framework for constructing multiparty HSS from two-party semi-private HSS (which in turn can be instantiated using distributed discrete logarithms) via a new party virtualization paradigm. In a semi-private HSS, some designated inputs may be fully known to specific servers, while the remaining inputs remain hidden. Starting from two-party semi-private schemes, we obtain $N$-party semi-private HSS supporting compositions of polynomial computations and restricted multiplication straight-line programs, for $N = O(\log \lambda / \log \log \lambda)$. We further upgrade semi-private HSS to fully private HSS for functions of polynomial degree and polynomially bounded Waring rank. As a consequence, we obtain multiparty distributed point functions with key size polynomial in $\lambda$ and $\log |D|$, for a domain $D$ of superpolynomial size. When the underlying two-party scheme supports offline/online sharing, the resulting multiparty DPFs are programmable. Our framework admits instantiations under standard assumptions including DCR and class-group assumptions.

Training machine learning models in untrusted clouds requires strong guarantees of confidentiality, integrity, and correctness, while remaining scalable and resilient to node churn. These challenges are further amplified in emerging agentic AI systems, where autonomous and distributed learning components require trustworthy coordination and secure state management across heterogeneous cloud environments. Existing Trusted Execution Environments (TEEs) lack scalability and remain vulnerable to side-channel attacks for large workloads, while pure secure multi-party computation (MPC) approaches incur prohibitive overhead in practice. SENTRA (Secure ENclave-based TRaining Architecture) addresses these challenges through a hybrid architecture that combines TEEs, secret sharing, and communication-efficient MPC with system level mechanisms that secure the entire training lifecycle. SENTRA introduces a scalable collective attestation protocol that verifies all participating enclaves and enforces hardware exclusivity before any node may store or process secret shares. Training data and model parameters are stored as secret shares in a versioned enclave-backed key–value store (KVS), providing rollback protection and consistent state under adversarial conditions. SENTRA further supports dynamic, fault tolerant membership through Dynamic Proactive Secret Sharing (DPSS)-based resharing, safe packed-MPC computation under degree bounds, and adaptive handling of node failures. Evaluation of a prototype implementation shows that SENTRA achieves up to 8.89 samples/s throughput and 1.29× faster training than the CrypTen baseline in software-only mode. In hardware-enclave mode, SENTRA incurs only an 8.3% performance overhead while providing memory-isolated confidentiality, fault-tolerant membership management, rollback protection, and recovery from node failures in approximately 8 seconds.

Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communication) attack if the adversary can hold an exponentially large amount of preshared entanglement. Somewhat surprisingly, we show that we can circumvent this barrier in the idealized continuous-time model, where time is represented by a real-valued parameter and challenge messages can be sent at a time sampled uniformly from a real interval. In this model, we give a BB84-based protocol that remains secure against any finite coalition of LOCC adversaries with arbitrary finite (possibly exponential) quantum storage and entanglement. Our construction can also be instantiated in the discrete-time model. Even though the previous impossibility results apply, we are able to obtain an information-theoretic QPV protocol in which the honest parties' total resources (communication and storage) can be significantly smaller than the adversarial resource bound. In fact, we can achieve any desired polynomial gap between honest parties and adversarial resources. To our knowledge, all previous protocols in the literature required resources of the honest parties to be at least as large as the adversarial entanglement. Interestingly, the resource gap between the honest and adversarial party resources in our protocol depends on how precisely time can be measured. As the precision of the best-known clock improves with further research, the resource gap in our protocol keeps increasing. In particular, the adversarial resource bound keeps increasing while the honest parties' resources remain largely the same. We call this the "I sleep, you work" paradigm.

We introduce new pseudorandom correlation generators (PCGs) for matrix triples: shares of triples $(A,B,A\cdot B)$ where $A,B$ are random matrices over $\mathbb{F}^{n\times n}$ for a field $\mathbb{F}$ and an integer $n$. Matrix triples are consumed in a wide variety of secure computation protocols that involve matrix arithmetic, which occurs commonly in settings such as privacy-preserving machine-learning and statistics, threshold cryptography, secure linear algebra, and more. Previous PCGs for matrix triples are inefficient: their seed grows at least linearly in the matrix dimension, and their expansion is slow. In this work, we introduce two new PCGs with improved performances: 1. Our first construction, inspired by the recent work of (Gentry and Lee, Crypto 2026) on FHE for matrix arithmetic, relies on the quasi-abelian syndrome decoding (QASD) assumption introduced in (Bombar et al., Crypto 2023), an assumption which has since received a significant amount of attention. Our PCG generates $N$ matrix triples over $\mathbb{F}^{n\times n}$ from a seed of size $poly(\lambda,\log n,\log N)$ using $\Theta(n^3\log(n^3N))$ field operations per triple, removing the linear dependency on $n$ from the seed compared to previous works. 2. Our second construction is more mathematically involved, and builds upon an elegant and surprising connection with the Weyl-Pauli twisted algebra, a mathematical structure originally studied in (Weyl, Zeitschrift für Physik, 1927) in the context of quantum kinematics. Our PCG relies on a new variant of the QASD assumption over the Weyl-Pauli twisted group algebra and exhibits impressive performances: it has the same seed size as our first construction and generates $N$ matrix triples at a cost only a small constant time larger than the cost of computing $N$ matrix triples in the clear. We complement our results with an in-depth study of our new twisted QASD assumption and demonstrate the benefits of our PCGs in concrete applications such as privacy-preserving machine learning and threshold MAYO.

We address the problem of proving the validity of computation on ciphertexts of homomorphic encryption (HE) schemes, a feature that enables outsourcing of data and computation while ensuring both data privacy and integrity. We propose a new solution that handles computations in RingLWE-based schemes, particularly the CKKS scheme for approximate arithmetic. Our approach efficiently handles ciphertext arithmetic in the polynomial ring $R_q$ without emulation overhead and manages ciphertexts maintenance operations, such as modulus switching, key switching, and rescaling, with small cost. Our main result is a succinct argument that efficiently handles arithmetic computations and range checks over the ring $R_q$. To build this argument system, we construct new polynomial interactive oracle proofs (PIOPs) and multilinear polynomial commitments supporting polynomials over $R_q$, unlike prior work which focused on finite fields. We validate the concrete complexity of our approach through implementation and experimentation. Compared to the current state-of-the-art on verifiable HE for RNS schemes, we present similar performance for small circuits while being able to efficiently scale to larger ones, which was a major challenge for previous constructions as it requires verifying procedures such as relinearization.

Threshold fully homomorphic encryption distributes decryption authority among multiple parties, but achieving strong security can significantly increase the required ciphertext modulus and the size of each decryption response. Existing parameter analyses typically focus on threshold decryption alone. In particular, the recent work of Kim et al. (KLL$^+$26) analyzes correctness and strong simulation security of partial decryption without covering distributed key generation (DKG). When the parties generate the keys themselves, the DKG and partial-decryption protocols must satisfy their respective correctness and security requirements. We revisit correctness and simulation-security requirements for threshold decryption when it is composed with DKG. We then introduce Jambon, which applies deterministic rounding to partial decryptions to further reduce the modulus used for decryption responses. The composed security bound accounts separately for setup and decryption errors. We prove exact recovery for BFV and extend the approach to CKKS under an additional condition. Under the stated temporary-HE assumptions and resource hybrids, we establish universally composable security with strong threshold privacy against static malicious corruption in the random-oracle model. We prove security for the DKG and its composition with verifiable partial decryption. Under the stated algebraic and statistical parameters, Jambon's numerical decryption responses are at least $60\%$ smaller than the native responses of the updated KLL$^+$26 strong-security construction at every threshold considered for $256$, $512$, and $1024$ parties. This comparison uses the specified sufficient bounds and excludes proof and setup traffic.