This paper presents Heli, a system that lets a pair of servers collect aggregate statistics about private client-held data without learning anything more about any individual client's data. Like prior systems, Heli protects client privacy against a malicious server, protects correctness against misbehaving clients, and supports common statistical functions: average, variance, and more. Heli's innovation is that only one of the servers (the "heavy server") needs to do per-run work proportional to the number of clients; the other server (the "light server") does work sublinear in the number of clients, after a one-time setup phase. As a result, a computationally limited party, such as a low-budget non-profit, could potentially serve as the second server for a Heli deployment with millions of clients. Heli relies on a new cryptographic primitive, aggregation-only encryption, that allows computing certain restricted functions on many clients' encrypted data. In a deployment with ten million clients, in which the servers privately compute the sum of 32 client-held 1-bit integers, Heli's heavy server does 84,000 core-s of work and the light server does 8 core-ms of work. Compared with prior work, the heavy server does 34$\times$ more computation, but the light server does 150,000$\times$ less.

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

We present $\mathsf{Protoss}$, a new balanced PAKE protocol with optimal communication efficiency. Messages are only 160 bits long and the computational complexity is lower than all previous approaches. Our protocol is proven secure in the random oracle model and features a security proof in a strong security model with multiple parties and multiple sessions, while allowing for generous attack queries including multiple $\mathsf{Test}$-queries. Moreover, the proof is in the practically relevant single-bit model (that is harder to achieve than the multiple-bit model) and tightly reduces to the Strong Square Diffie-Hellman assumption (SSQRDH). This allows for very efficient, theoretically-sound instantiations and tight compositions with symmetric primitives.

Cryptographic accumulators based on groups of unknown order (GUO) provide constant-size set membership proofs. For security purposes, existing works require first encoding set elements via division-intractable (DI) hash functions, typically instantiated as random oracles that destroy any algebraic structure. This confines GUO-based accumulators to a purely set-membership role, making them "incompatible" with various existing cryptographic proof techniques over committed integers in the same groups as the GUO, such as constant-size proofs of exponentiation and modular exponent relations. We introduce the notion of morphic accumulators, which replaces the DI hash with a discrete logarithm encoding $H_g(x) = g^x$, mapping set elements to a group before accumulation. We prove, under a variant of the subset product assumption in the generic group model, that this encoding is inherently division intractable, achieving the same security guarantee as random-oracle DI hashes, while simultaneously being a group homomorphism: accumulated elements retain their group-algebraic relationships. This resolves a fundamental tension between compact representation and algebraic structure: the accumulator serves simultaneously as a binding commitment to a set and as a substrate for homomorphic computation over its elements. Morphic accumulators yield asymptotically optimal constructions across multiple domains: range proofs with $O(n)$ prover time, $O(1)$ proof size, $O(1)$ verification with transparent setups (the first scheme to simultaneously achieve these optimal bounds); polynomial commitments with $O(n)$ prover and $O(1)$ proof size, resolving the cubic bottleneck in prior constant-proof-size GUO-based schemes; and the first linkable ring signatures with $O(1)$ signature size, transparent setup, $O(n)$ offline signing and $O(1)$ online signing.

Two post-quantum upgrades to TLS 1.3 are being standardized in parallel: a hybrid key exchange (already deployed) that runs an elliptic-curve Diffie-Hellman exchange alongside ML-KEM, and a standalone mode that uses ML-KEM on its own. The Internet-Draft draft-usama-tls-risks-of-mlkem points out that the machine-checked symbolic proofs of TLS 1.3 rely on the commutativity of Diffie-Hellman, which ML-KEM does not share: a key encapsulation mechanism is asymmetric, one endpoint generating a key pair and the other encapsulating against it. The existing proofs therefore no longer apply, a new one is needed, and the draft argues that hybrids should be preferred. We supply that proof. We extend the reftls ProVerif models with a faithful, non-commutative KEM and analyze classical (EC)DHE, standalone ML-KEM, and the hybrid together, as unbounded concurrent sessions against a single active attacker free to break any cryptographic component. The central result is a sharp and tight contrast in robustness: standalone ML-KEM is a single point of failure, secure only while ML-KEM itself is unbroken, whereas the hybrid stays secure as long as either of its components survives: an attacker must break both, in one session, to learn anything. This single point of failure reaches authentication as well as confidentiality: with the sole key-exchange secret exposed and no secret pre-shared key salting the key schedule, the server Finished message becomes forgeable, so a client can complete a handshake that no server completed, while the hybrid stays safe unless both components break. The three modes also interoperate without ever confusing one another's keys, so migrating from (EC)DHE to a hybrid is a strict improvement. Two further experiments address the draft's remaining concerns: reusing an ML-KEM key forfeits the forward secrecy that an ephemeral key preserves, and a principal acting as both initiator and responder exposes no role-confusion attack arising from the asymmetry. At the symbolic level, and under stated assumptions, the analysis substantiates the draft's case for preferring hybrid key exchange.

We present a post-quantum commitment scheme based on kernel-tagged punctured Richelot isogeny walks on superspecial genus-2 Jacobians. The puncturing rule skips every step landing in the product locus, detected by I10 = 0, so honest executions remain in the Jacobian locus and avoid the entry point of known product-locus attacks. Each opening is encoded as a deterministic non-backtracking walk together with a kernel tag recording its action on a small public auxiliary torsion basis. The tag is verified as part of the opening and is kept explicit throughout the security analysis. In particular, scalar-related collisions force equality of the ordered kernel sequence and hence equality of the tag, so any nontrivial binding attack yields a short non-scalar endomorphism. Using spectral bounds for the Richelot graph, we show that puncturing preserves rapid mixing for logarithmic walk lengths, which yields statistical hiding for the tagged punctured scheme. We therefore reduce binding to the Short Richelot Endomorphism Problem (SREP), relate SREP to the One-Endomorphism Problem and, under a standard KLPT2 -style heuristic, to the endomorphism-ring problem. A SageMath prototype based on (2, 2)-Kummer isogenies indicates practical performance at standard security levels.

Unbiased, unpredictable, and publicly verifiable randomness is essential for a wide range of blockchain-based Web3 applications. Verifiable Random Functions (VRFs) naturally satisfy these requirements. For practical deployment, however, a VRF scheme must support efficient key generation and allow multiple evaluations across different blockchain rounds. In this work, we present a post-quantum secure, key-updatable VRF construction built from symmetric cryptographic primitives, including hash functions and pseudorandom generators (PRGs). The core of our design is a quantum-secure Extended Merkle Signature Scheme (XMSS) structured over multiple layers. We reorganize the XMSS framework in a systematic way to integrate it seamlessly into our VRF construction. Compared to existing approaches, our scheme offers improved key generation efficiency while enabling multiple evaluations from a single secret–verification key pair.

Private information retrieval (PIR) allows to privately read a chosen bit from an $N$-bit database $x$ with $o(N)$ bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing $x$ into an encoded database $\hat x$, it suffices to access only $polylog(N)$ bits of $\hat x$ per query. This requires $|\hat x|\ge N\cdot polylog(N)$, and even larger server circuit size. We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding $\hat x$ depends on a client's short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with $O(N^\epsilon)$ communication, for any constant $\epsilon>0$, from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR. Under a new conjecture related to the hardness of learning a hidden linear subspace of $\mathbb{F}_2^n$ with noise, we construct sk-PIR with similar communication and encoding size $|\hat x|=(1+\epsilon)\cdot N$ in which the server is implemented by a Boolean circuit of size $(4+\epsilon)\cdot N$. This is close to optimal, and the first candidate single-server PIR scheme with linear circuit complexity.

Blockchain mempool transparency fuels Maximal Extractable Value (MEV), where attackers can front-run, back-run, and reorder transactions as soon as they appear. Encrypted mempools aim to delay the release of information until block commitment, yet nearly all existing designs rely on a trusted decryption committee. This creates two structural problems. First, committee members hold decryption material by design, so a colluding threshold can reconstruct the decryption key and learn transactions before block commitment. Second, once such a committee becomes malicious, honest parties have no easy in-protocol way to recover: restoring privacy for future epochs requires an external intervention such as a hard fork that replaces the committee and rotates the long-lived cryptographic material. In this work, we ask whether encrypted mempools can instead use proof-of-work to realize an open and recoverable decryption committee. We then introduce DecryptChain, a permissionless proof-of-work encrypted mempool in which decryption authority is not assigned to persistent identities or long-lived key shares. Instead, decryption is continuously re-contested through public computational work. Even if an adversary successfully breaches one epoch, it gains no reusable secret for future epochs; honest parties can always re-enter and recover the decryption process by contributing sufficient work. DecryptChain decouples block production from decryption, enabling it to operate as a Layer-2 timely decryption service on any underlying blockchain while preserving eventual decryption for committed on-chain encrypted transactions.

The communication complexity of unconditionally Secure Multi-Party Computation (MPC) protocols has been studied by a series of works in the honest-majority setting. For evaluating an arbitrary Boolean circuit, the state-of-the-art MPC protocol by Goyal et al. (Crypto 2021 and Crypto 2022) achieves the total communication cost of $O(\log n)$ bits per gate, where $n$ is the number of parties. In this work, we present the first unconditional MPC protocol for any Boolean circuit with communication of $O(1)$ bits per gate. We first construct an unconditionally secure protocol in the presence of semi-honest adversaries, and then strengthen it to guarantee security against malicious adversaries with the same communication efficiency.

Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in the same setting. In contrast, ACS has optimal constructions with quadratic communication complexity based on bilinear map assumptions. In this paper, we bridge this gap by introducing a nearly optimal ACS, which, assuming a common coin oracle, relies on the blackbox use of collision-resistant hash functions. It exhibits $\widetilde{\mathcal{O}}(n^2)$ communication complexity, expected constant round complexity, and security against adaptive adversaries who can corrupt up to $n/3$ nodes and perform “after-the-fact-removal” attacks. At the core of our new ACS is the first nearly optimal hash-based asynchronous Multi-valued Validated Byzantine Agreement (MVBA). To reduce cubic communication while avoiding heavy cryptographic tools, we introduce a new design paradigm with several novel components. This paradigm also enables an information-theoretic MVBA construction, whose communication complexity is higher than its hash-based counterpart but still quadratic. We give standard treatment of those using the conventional property based definitions. We also define and analyze our MVBA and components within the UC-framework, facilitating their modular use in broader applications, particularly in AMPC.

The Learning with Errors (LWE) problem is a fundamental hardness assumption underlying most fully homomorphic encryption (FHE) schemes. Given the close relationship between the Learning with Rounding (LWR) and LWE problems, several cryptographic constructions have also been developed based on LWR. In particular, LWR-based schemes often benefit from simpler and more efficient implementations, as they eliminate the need for explicit Gaussian error sampling. Despite these advantages, relatively few FHE constructions in the literature are based on the LWR assumption. At AsiaCCS 2025, Goyal and Gangopadhyay proposed a multi-key FHE (MKFHE) scheme based on LWR that adopts a public-key extension mechanism rather than the conventional ciphertext-extension paradigm. The authors also identified the development of a ring-based analogue as an open future direction. In this work, we present two Ring-LWR-based MKFHE constructions that can be viewed as ring analogues of the LWR-based MKFHE scheme of Goyal and Gangopadhyay. To the best of our knowledge, these are the first MKFHE schemes based on the Ring-LWR assumption. Compared with existing Ring-LWE-based multi-key constructions, our schemes achieve improved compactness in terms of storage and communication costs. We provide concrete parameterizations supporting circuits of varying multiplicative depths and present a proof-of-concept implementation to validate our claims.

The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime $q$ and the prover simply replies with an efficient representation of an isogeny of degree $q$ from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. Our optimized C implementation of the signature scheme shows that signing is roughly $1.8\times$ faster than all SQIsign variants, whereas verification is $1.4\times$ times slower. The sizes of the public key and signature are comparable to existing schemes. Latest version: PRISM with a pinch of salt: Simple, Efficient and Strongly Unforgeable Signatures from Isogenies, from the same authors, is an extended and updated version of the present article. It is available at https://eprint.iacr.org/2026/443.

In high-volume online services—such as privacy-preserving CAPTCHA bypass or metered paywalls—service providers must filter malicious traffic without compromising user privacy. Anonymous tokens with private metadata (ATPM) address this by embedding a hidden bit into a user's token; for example, indicating whether the user is suspected of being a bot. However, existing ATPM constructions are limited by high communication complexity, requiring a fresh interaction with the issuer for every single token. Furthermore, they lack support for fine-grained policy requirements, preventing service providers from verifying user attributes (such as age or subscription status) without stripping away anonymity. In this work, we bridge this gap by introducing SMA2RT (Secret-Metadata Attribute-based Anonymous Rate-limited Tokens). For the first time in the hidden-metadata context, our construction supports selective attribute disclosure, thereby bridging the gap between the anonymous credentials and anonymous tokens literatures. Our construction leverages signatures on equivalence classes (SEQ) to achieve an "issue once, spend N times" capability. This allows a user to interact with the issuer only once to obtain a master credential and subsequently derive up to N unlinkable, valid tokens locally, without further online communication. This significantly reduces server load and network latency, making the scheme practical for real-time web applications. Each derived token preserves the issuer's hidden metadata bit and supports selective disclosure of the user's attributes.

Consensus protocols in the partially synchronous setting face a fundamental trade-off: achieving optimal Byzantine fault tolerance requires a good-case latency of at least three rounds, while committing in fewer than three rounds generally entails reduced resilience. Even optimistic protocols such as SBFT (DSN'19), FaB (TDSC'06), and Kudzu (DISC'25) achieve an optimistic good-case latency of two rounds under favorable conditions, but only at the cost of reduced fault tolerance. In this work, we introduce Hydrangea, a partially synchronous state machine replication protocol that combines low latency with improved fault resilience. Let $f$ denote the maximum number of tolerated Byzantine faults, $c$ the maximum number of tolerated crash faults, and $k \ge 0$ a tunable parameter. For a system of $n = 3f + 2c + k + 1$ parties, Hydrangea achieves an optimistic good-case latency of two rounds when the total number of faulty parties (Byzantine or crash) is at most $p = \lfloor \frac{c + k}{2} \rfloor$. In more adversarial settings, with up to $f$ Byzantine faults and $c$ crash faults, it guarantees a good-case latency of three rounds. We further prove a matching lower bound: no protocol can achieve a two-round optimistic commit under this fault model if $p > \lfloor \frac{c + k + 2}{2} \rfloor$. Our experimental evaluation on geo-distributed deployments demonstrates that Hydrangea consistently achieves substantially lower latency than state-of-the-art protocols in both Byzantine-only and Byzantine–crash fault models, while also delivering modest improvements in throughput.

Decentralized governance plays a critical role in blockchain communities, allowing stakeholders to shape the evolution of platforms such as Cardano, Gitcoin, Aragon, and MakerDAO through distributed voting on proposed projects in order to support the most beneficial of them. In this context, numerous voting protocols for decentralized decision-making have been developed, enabling secure and verifiable voting on individual projects (proposals). However, these protocols are not designed to support more advanced models such as quadratic voting (QV), where the voting power, defined as the square root of a voter’s stake, must be distributed among the selected by voter projects. Simply executing multiple instances of a single-choice voting scheme in parallel is insufficient, as it can not enforce correct voting power splitting. To address this, we propose an efficient blockchain-based voting protocol that supports liquid democracy under the QV model, while ensuring voter privacy, fairness and verifiability of the voting results. In our scheme, voters can delegate their votes to trusted representatives (delegates), while having the ability to distribute their voting power across selected projects. We model our protocol in the Universal Composability framework and formally prove its UC-security under the Decisional Diffie–Hellman (DDH) assumption. To evaluate the performance of our protocol, we developed a prototype implementation and conducted performance testing. The results show that the size and processing time of a delegate’s ballot scale linearly with the number of projects, while a voter’s ballot scales linearly with both the number of projects and the number of available delegation options. In a representative setting with 64 voters, 128 delegates and 128 projects, the overall traffic amounts to approximately 2.7 MB per voted project, confirming the practicality of our protocol for modern blockchain-based governance systems.

In this work, we introduce a more efficient post-quantum oblivious PRF (OPRF) design, called LeOPaRd. Our proposal is round-optimal and supports verifiability and partial obliviousness, all of which are important for practical applications. The main technical novelty of our work is a new method for computing samples of MLWE (Module Learning With Errors) in a two-party setting. To do this, we introduce a new family of (interactive) lattice problems, called MLWE-PRF with re-use (MLWE-PRF-RU). Here, the adversary is given a mix of MLWE and PRF samples where each PRF error is dependent on an adversarially-chosen matrix and the MLWE error. We rigorously study the hardness of MLWE-PRF-RU and provide a reduction from the standard MLWE to MLWE-PRF-RU, establishing a strong security foundation. We believe MLWE-PRF-RU problem family and the intermediate security reductions we introduce along the way can be of independent interest for other interactive protocols. LeOPaRd exploits this MLWE-PRF-RU assumption to realize a lattice-based OPRF design without relying on heavy machinery such as noise flooding and fully homomorphic encryption used in earlier works. LeOPaRd can feature around 138 KB total communication, compared to 300+ KB in earlier works, while also achieving about 2x reduction in online communication compared to the prior state-of-the-art result. We also identify gaps in some existing constructions and models, and propose appropriate fixes.

Modern cryptography relies on the intractability of computational problems. We present an approach to building cryptography from a new source of hardness: \emph{proving mathematical theorems}. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural, assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krajíček and Pudlák [J. Symb. Log. '89]. Our construction is a simple variant of the SNARG construction of Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was proven only for a subclass of NP, we prove its soundness for all of NP under our assumption. At the heart of our result is the observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Jeřábek's theory $\mathsf{APC}_1$ [J. Symb. Log. '07], a weak theory of bounded arithmetic.

Message Authentication in the Short Authenticated String model (SAS-MA) allows Alice and Bob to establish a secure channel without trust in any third party, as long as they can exchange short authenticated strings, e.g. 20 bits. In a recent paper, Gu et al. [17] showed a SAS-MA scheme based on Verifiable Random Functions (VRF), which can utilize the ephemeral keys sent in the X3DH Authenticated Key Exchange (AKE), allowing for extending X3DH to SAS-MA with minimal round complexity and no changes to X3DH key distribution. X3DH is used in many messaging apps, including WhatsApp and Signal, and a SAS-MA extension of X3DH would allow app users to authenticate their connections without trust in PKI or the app’s Key Distribution Center (KDC), as long as they can exchange short authenticated strings (SAS), using out of band authenticated channels. However, a major motivation behind using X3DH as an AKE is its deniability property, i.e. that an X3DH transcript cannot serve as a proof that either Alice or Bob established a secure connection with each other. The VRF-based SAS-MA extension of X3DH of [17] violates deniability, essentially because a VRF is a signature. We show an alternative SAS-MA scheme which offers the same ease of integration with X3DH as the VRF-based SAS-MA of [17], but it (almost) maintains the deniability of X3DH. The proposal is based on a private VRF (PVRF), which allows only ‘designated-verifier’ verification of correctness. We show a low-cost PVRF variant of ECVRF, and we show that X3DH extended by our PVRF-based SAS-MA adds human-centric no-trust-in-KDC authentication to X3DH while preserving the deniability properties of X3DH.

Censorship has always existed, serving both to prevent harms and to inflict them by chilling speech, suppressing organizing, and withholding inconvenient facts and ideas; most technical work aims to prevent all forms of censorship --- the "good", the "bad", and everything in between. We study the complementary, rarely explored goal of making any censorship attempt transparent. We formalize censorship-evident publishing systems (CEPS), protocols that force both overt and covert takedowns to yield transferable evidence. We also provide a CEPS instantiation with Streisand, a proof-of-concept deployment that combines a blockchain-backed timestamp oracle, private information retrieval (PIR)-based anonymous queries to prevent extraction attempts from being conspicuous, and probabilistic Merkle-witness retrieval to produce compact censorship proofs. We present performance evaluations on a 1.3 GiB Enron-derived dataset with regex-based PII redaction to model realistic censorship, and demonstrate that a background daemon can detect heavy censorship after a small number of post-censorship queries, making Streisand an effective auditing mechanism rather than interactive file retrieval. We also discuss design trade-offs (proof size vs. computation, PIR sufficiency vs. necessity), scalability limits, and how CEPS complements existing transparency practices, with Streisand as a starting point for CEPS deployments.

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this paper, we introduce a new isogeny-based signature scheme, $\Delta$-SQIsign, which represents a significant departure from existing isogeny-based signatures including SQIsign. The key distinction in our scheme lies in its use of the degree of isogeny as a challenge within the underlying $\Sigma$-protocol. Then, the prover outputs an isogeny of the given degree as a response. To construct such a scheme, we introduce a new algorithm, called $\Delta$-KLPT, which is a variant of GeneralizedKLPT. Similar to GeneralizedKLPT, our algorithm outputs an ideal equivalent to a given ideal with a fixed norm; however, under certain conditions, it can produce an ideal of smaller norm than GeneralizedKLPT.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic key, where the only information shared in advance is a low-entropy password. The first efficient PAKE protocol whose security does not rely on the random oracle model is the one by Katz, Ostrovsky and Yung (KOY, EUROCRYPT 2001). Unfortunately, the KOY protocol has only been proven secure in the game-based setting, and it is unclear whether KOY is secure in the stronger Universal Composability (UC) framework, which is the current security standard for PAKE. In this work, we present a thorough study of the UC-security of KOY. Our contributions are two-fold: 1. We formally prove that the KOY protocol is not UC-secure; 2. We then show that the UC-security of KOY holds in the Algebraic Group Model, under the Decisional Square Diffie-Hellman (DSDH) assumption. Overall, we characterize the exact conditions under which KOY is UC-secure. Interestingly, the DSDH assumption is stronger than DDH under which KOY can be proven game-based secure, which reveals some subtle gaps between the two PAKE security notions that have never been studied.

We initiate study on how to build a rigorous, cryptographic foundation for *proofs of personhood* - convincing, privacy-preserving evidence that a digital participant is a real, unique, and reputable human, optionally with authenticated attributes such as age or institutional affiliation. Towards this goal, we introduce a framework based on two types of credentials: *personhood credentials* (PHCs), issued by trusted authorities to attest to uniqueness and basic attributes, and *verifiable relationship credentials* (VRCs), issued peer-to-peer to capture reputation and real-world interactions. We formalize ideal functionalities that capture desirable security and privacy notions for proofs of personhood, including Sybil-resistance, authenticated personhood, and unlinkability across contexts. Finally, we then give efficient cryptographic constructions that realize these functionalities by combining PHCs, VRCs, and zero-knowledge proofs. Our results suggest that a scalable, Sybil-resistant, and decentralized proof-of-personhood layer can serve as a reusable trust substrate for a wide range of online economic, social, and civic applications.

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with $O(n^2)$ communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with $O(n^2)$ communication and $O(1)$ rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with $O(n^{2+1/k})$ communication and $O(k)$ rounds for a tunable parameter $k\leq \log{n}$. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase. In this work, we resolve this open problem by presenting the first ADKG protocol that achieves $O(n^2)$ communication and $O(1)$ rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to $f < n/3$ parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most $f$ edges in an $n$-node $m$-edge $D$-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in $n$) for any $f$. This is in contrast to the exponential or polynomial dependence on $f$ in prior works. Our main results are: Secure broadcast algorithm, for sending an $O(\log n)$-bit message, that runs in $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{3/2})$ messages. This matches the state-of-the-art bounds for \emph{insecure} broadcast by [Ghaffari and Kuhn, and Gmyr and Pandurangan, DISC 2018]. Our bounds also improve over the $\tilde{O}(D+\sqrt{f n})$-round complexity and $\tilde{O}(\sqrt{f n}\cdot m)$ message complexity of secure broadcast by [Hitron, Parter and Yogev, DISC 2022]. Secure MST algorithm with sublinear round and subcubic message complexities that improve over the algorithm by [Hitron, Parter and Yogev, ITCS 2023] in the entire regime. In particular, when $f=\Theta(n)$, we improve the round complexity from $\tilde O(n^{3/2})$ to $\tilde O(n^{2/3})$, and the message complexity from $\tilde O(n^{3})$ to $\tilde O(n^{7/3})$. Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger's sampling, tree packing and sparse recovery sketches.

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

Proximity testing is crucial to location-privacy applications, from discovering nearby friends to enabling UAV collision avoidance. In such settings, users must determine proximity without revealing their exact locations. This motivates privacy-preserving proximity testing (PPPT) protocols revealing only if the proximity condition holds, while hiding both parties’ inputs. However, most existing PPPT protocols rely on strong assumptions (e.g., non-colluding servers) or require simultaneous interaction, limiting their practicality. Moreover, they typically define proximity using metric distances (e.g., Euclidean distance), failing to support richer membership queries for complex regions like buildings or parks. To address these, we introduce a new primitive called Geometric Fuzzy Matching (GFM), which generalizes fuzzy matching to arbitrary $n$-dimensional regions. In GFM, the receiver specifies a region and learns only whether the sender’s location lies within it, without revealing either party’s input. This approach captures both classical distance-based proximity checks (for any Minkowski $\ell_p$ norm, $1 \leq p \leq \infty$), as well as membership tests for complex regions, providing a unified framework for diverse proximity queries. In low-dimensional settings, our protocol improves on distance-based checks compared to state-of-the-art van Baarsen et al. (EUROCRYPT 2024) for $\ell_\infty$ and maintains stable practical efficiency for $\ell_p$ norms under large distance thresholds or for $p \geq 4$, where previous approaches quickly become computationally prohibitive. It is also the first to support fuzzy matching over arbitrary geometric regions, enabling proximity queries in complex spaces. Our implementation confirms these results and demonstrates the protocol’s efficiency and applicability across diverse PPPT scenarios.

We propose a new private telemetry system for computing t-heavy hitters in the STAR (Davidson et al., CCS 2022) and POPSTAR (Li et al., USENIX 2024) model. In this setting, each client generates a report with the assistance of a lightweight Randomness Server and submits it to a central Aggregation Server, which can then locally compute only the heavy hitters. As compared to STAR and POPSTAR---which reveal either the full (pseudonymized) frequency histogram or a complex function of it---our protocol reduces leakage: the Aggregation Server learns non-heavy-hitter values only if their frequency exceeds a well-defined threshold. Additionally, while STAR and POPSTAR are insecure in the face of an Aggregation Server that colludes with clients, our protocol provides optimal security against such a colluding server. To achieve these privacy guarantees, our protocol efficiently adapts multi-dealer secret sharing (Eldridge et al., USENIX 2024) to the STAR/POPSTAR model and introduces a novel oblivious secret-share sampling protocol to ensure security against a colluding Aggregation Server. We implement and benchmark the performance of our protocol and find that it is practical for a number of use cases. Moreover, we show that it supports a tunable three-way tradeoff between correctness, efficiency and privacy.

We present the first constant-expected-latency protocols for Interactive Consistency (IC), also known as Parallel Byzantine Broadcast, that achieve either: (1) security in dishonest majority, namely $t \leq (1-\varepsilon)n$ for any constant $\varepsilon\in \Omega(1)$; or (2) quadratic communication $O\!\left(n^2(L_{in}+\kappa)\right)$ in honest majority (i.e., $\varepsilon >1/2$). In IC, $n$ processes must agree on a vector that maps every honest process to its input of size $L_{in}$, despite up to $t$ dishonest (Byzantine) processes that may collude and behave arbitrarily. IC is the strongest one-shot distributed task: by fully determining the honest input configuration, it subsumes every other solvable one-shot task in the same model. Moreover, most multiparty computation protocols rely on IC as a building block. These guarantees are qualitatively optimal. First, Garay, Katz, Koo, and Ostrovsky (FOCS~2007) rule out constant-round protocols unless the honest fraction is constant. Second, Pease, Shostak, and Lamport (JACM~1980) rule out setup-free information-theoretic solutions once $n\leq 3t$. Thus, to overcome this barrier, we rely on cryptographic objects of size $\kappa$, obtaining correctness with all but negligible probability in $\kappa$ against any adversary running in time polynomial in $\kappa$. This includes digital signatures, for which the corresponding public keys must be published on a bulletin-board public key infrastructure before the protocol begins. Third, IC trivially requires \(\Omega(n^2L_{in})\) communication, since every honest process must learn the inputs of all honest processes. Our results follow from a single generic compiler that transforms any constant-expected-latency Byzantine Broadcast protocol into an IC protocol with the same latency profile.

Generative AI and advanced editing tools enable malicious actors to create high-quality fake images that can propagate fraud, attack reputations, and manipulate elections. We analyze security properties of the Coalition for Content Provenance and Authenticity (C2PA) digital provenance system, which binds cryptographic assertions of provenance to a digital asset, helping users judge its origin. We analyze three C2PA components: specifications (Version 2.2), selected claim validator implementations, and conformance program (Version 0.1). We state C2PA's security goals (tamper-evidence of claims and weak file integrity), identify essential additional goals (timestamp agreement, validator consistency, and strong file integrity), review major policies, examine composition with RFC 3161 trusted timestamps, and carry out the first formal-methods analysis of the core protocols. We show that the specifications and conforming implementations fail to achieve both claimed and essential security goals. Our formal-methods analysis reveals that generators and validators fail to agree on the signature's trusted timestamp, enabling timestamp alterations that cast doubt on provenance. Inadequate certificate revocation policies cause conforming validators to accept manifests signed with known-compromised certificates, violating all security goals. Conforming validators produce inconsistent results; the exclusion range enables undetectable alterations; and the conformance program certifies products without technical review or defined requirements. Our results show that C2PA does not yet provide the guarantees required for reliable deployment. We suggest concrete improvements, some of which were adopted in the Pixel 10 Pro and C2PA Version 2.3.

Anonymous-credential schemes allow users to obtain credentials on various attributes, and then use those credentials to give unlinkable proofs about the values of some attributes without leaking anything about others. They have recently received interest from companies including Google, Apple, and Cloudflare, and are being actively evaluated both at the IETF and in the EU. Anonymous credentials based on BBS signatures are a leading candidate for standardization. In some natural applications of anonymous credentials, it is beneficial to hide even the issuer of a credential, beyond revealing the fact that the issuer is in some pre-determined set specified by a verifier. Sanders and Traoré recently showed a construction of such issuer-hiding anonymous credentials based on the Pointcheval–Sanders signature scheme. In this work we show how to achieve issuer hiding for BBS-based anonymous credentials. Our construction satisfies a notion of everlasting issuer-hiding anonymity, and is unforgeable in the generic group model. It can be integrated into existing standards, and has several efficiency advantages compared to prior work.

We introduce DASTE, a decentralized encryption primitive for auditable access control in settings where users independently generate public keys, register them on an immutable ledger, and decrypt only through collaboration. In DASTE, a sender encrypts under an access structure (e.g., an access tree / LSSS) whose leaves are concrete registered public keys selected at encryption time. A ciphertext can therefore be opened only by a qualifying coalition of registered key holders that jointly reconstructs the masking secret. DASTE is designed for dynamic policy-governed environments in which access conditions may need to change after encryption. To support this, we provide ciphertext-only policy evolution operations, including semantically neutral insertion, threshold escalation, subtree revocation, and ciphertext rerandomization, that update ciphertexts without reissuing user secret keys and without requiring plaintext access. We give two instantiations: a classical discrete-log-based construction, included as a conceptual baseline, and a post-quantum construction based on decisional Ring-LWE. For the RLWE construction, we prove coalition-bounded IND-CPA security via a standard hybrid argument. Together, these results yield a ledger-anchored, access-structured, post-quantum threshold encryption framework suitable for decentralized key management and governance-oriented decryption workflows.

Unbiased and unpredictable randomness is a backbone of Web3 security, yet current Distributed Verifiable Random Function designs often entail a trade-off between performance and privacy. While established protocols like GLOW-DVRF achieve constant-size proofs, they rely on computationally expensive bilinear pairings that impose significant gas overhead in on-chain environments. Existing output-privacy frameworks, such as FlexiRand, are currently limited by the same expensive pairing-based operations that have high on-chain verification costs. In this paper, we present IcyVeil, an output-private DVRF that conjoins the architecture of FlexiRand with the pairing-free efficiency of Icy-DVRF. By integrating a blinding/unblinding mechanism directly into a FROST-inspired preprocessing scheme, IcyVeil enables users to mask inputs with a private nonce while the distributed committee generates partial evaluations and NIZK proofs over the veiled values. This approach eliminates the high cost of bilinear pairings during verification and maintains constant-size proofs. By adopting the pairing-free architecture of Icy-DVRF, IcyVeil inherits a 43% reduction in on-chain gas costs compared to conventional pairing-based protocols, establishing a scalable and cost-effective primitive for latency-sensitive applications such as decentralized gaming and asynchronous reward distribution.

We introduce $\textit{Miraidon}$, a new family of MinRank-based post-quantum signature schemes built from a novel zero-knowledge proof system. Our primary construction, $\textit{Miraidon-S}$, is a digital signature scheme with competitive public key and signature sizes, improved soundness parameters, and security based on the hardness of the MinRank problem. Building on this framework, we further construct $\textit{Miraidon-RS}$, a ring signature scheme, and introduce $\textit{Miraidon-LRS}$, the first linkable ring signature scheme based on the MinRank problem. We present concrete parameters and comparisons with contemporary lattice- and code-based ring and linkable ring signatures, showing that MinRank provides a promising foundation for efficient advanced post-quantum signature primitives.

We present $\textsf{Jindo}$, a new lattice-based polynomial commitment scheme (PCS) optimized for client-side proving, which requires fast prover performance while supporting evaluation hiding and flexible parameter regimes. To achieve this, we build $\textsf{Jindo}$ on the previous lattice-based PCSs $\textsf{CELPC}$ (CRYPTO'24) and $\textsf{Greyhound}$ (CRYPTO'24), which exhibit fast proving performance but have several limitations for client-side proving. We resolve these limitations by developing a new polynomial evaluation protocol that supports multilinear polynomials, diverse field choices, sublinear masking overhead for evaluation hiding, and cube-root verification and communication complexity. Our implementation shows that $\textsf{Jindo}$ improves upon $\textsf{CELPC}$ by about an order of magnitude across all metrics, including proof generation, verification, and proof size. Compared with the recent evaluation hiding code-based PCS $\textsf{PIP-FRI}$ (USENIX'26), $\textsf{Jindo}$ provides an order of magnitude faster proof generation while yielding similar verification and communication costs. Furthermore, when compiling the PIOP of $\textsf{Buckler}$ (CCS'25) to prove the validity of an RLWE sample, $\textsf{Jindo}$ outperforms $\textsf{CELPC}$ by an order of magnitude across all metrics. Compared with $\textsf{Lazer}$ (CCS'24) for proving the same lattice relation, $\textsf{Jindo}$ achieves an order of magnitude faster proof generation and two orders of magnitude faster verification.

We introduce baseSPIDER and SPIDER, private information retrieval (PIR) schemes that embody two technical advancements. The baseSPIDER protocol operates with a single server and a stateful client that performs pre-processing and stores hints for future queries. In this setting, baseSPIDER introduces a new approach that matches the asymptotically optimal communication complexity of state-of-the-art schemes while improving constant factors--an advantage that is particularly significant for databases with large entries. In addition, baseSPIDER offers a conceptually simpler design relative to prior protocols. SPIDER operates over a default database interface and requires no cooperation from the server at any stage. To our knowledge, SPIDER is the first single-server PIR construction of this design, achieving privacy without specialized APIs, auxiliary server state, or protocol-specific interaction beyond conventional indexed access. SPIDER is built via a simple transformation of baseSPIDER to the default server setting, eliminating deployment barriers and enabling immediate applicability to existing systems. This transformation can be applied more broadly to three recent PIR solutions, adapting them for use in the default-server paradigm and yielding solutions of independent interest. SPIDER compares to the resulting modified solutions by exhibiting a simpler design while incurring higher client computational work.

A garbling scheme encodes a function and an input into two independent artifacts from which the output can be recovered, but nothing else is revealed. This clean separation between function and input has made garbling one of the most versatile primitives in cryptography. Yet it hides an asymmetry that has gone largely unexamined: while the input is cryptographically protected, the function is fully exposed to whoever performs the garbling. As garbling is increasingly deployed in settings where garbling is delegated to untrusted infrastructure, published on public ledgers, or distributed among multiple parties, this asymmetry becomes a fundamental barrier. The function, which may encode proprietary models, confidential policies, or sensitive decision logic, is leaked unconditionally to the garbling server. We introduce oblivious garbling, a new paradigm that closes this gap. In our framework, the garbler receives only a designated leakage of the circuit and remains oblivious to everything else. We present the first construction instantiating this notion where the leakage is the circuit topology alone, achieving linear complexity with no blow-up in the size of the garbled circuit. The construction extends to the malicious setting with no asymptotic overhead. Beyond its theoretical contribution, oblivious garbling has immediate practical consequences: it enables outsourced garbling without function exposure, garbling on untrusted hardware without leaking proprietary logic, and a multi-party garbling protocol in which no garbling party learns the function, all without resorting to universal circuits.

The Fischlin transform yields non-interactive zero-knowledge proofs with straight-line extractability in the classical random oracle model. This is done by forcing a prover to generate multiple accepting transcripts through a proof-of-work mechanism. Whether the Fischlin transform is straight-line extractable against quantum adversaries has remained open due to the difficulty of reasoning about the likelihood of query transcripts in the quantum-accessible random oracle model (QROM), even when using the compressed oracle methodology. In this work, we prove that the Fischlin transform remains straight-line extractable in the QROM, via an extractor based on the compressed oracle. This establishes the post-quantum security of the Fischlin transform, providing a post-quantum straight-line extractable NIZK alternative to Pass’ transform with smaller proof size. Our techniques include tail bounds for sums of independent random variables and for martingales as well as symmetrization, query amplitude and quantum union bound arguments.

Threshold cryptography distributes trust among multiple parties by enabling joint cryptographic operations without reconstructing secret keys. While post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are highly generic, recent impossibility results show that their thresholdization either incurs prohibitive distributed symmetric computations or leads to signature sizes growing with the number of signers. Achieving practical tradeoffs in this setting remains challenging. In this paper, we propose a generic framework for threshold MPCitH signatures based on Merkle-tree commitments. Our approach adapts the PIOP+PCS paradigm to the distributed setting by introducing and instantiating the notion of threshold polynomial commitment schemes (TPCS). We present a generic compiler combining a PIOP, a TPCS, and an arithmetic black box into a threshold signature scheme, and prove its unforgeability from the security of its components. We further provide a concrete Merkle-tree-based TPCS achieving moderate signature-size overhead, as low as 200 bytes per signer at the 128-bit security level. This is to be compared with an overhead of roughly 2 kB per signer for the previously suggested approach to thresholdize MPC-in-the-Head based on GGM trees. By compiling this TPCS with a standard PIOP, we obtain a generic threshold signature scheme from any hard problem or one-way function, which we showcase MQ-based and AES-based instantiations.

Pre-constructed Publicly Verifiable Secret Sharing (PPVSS) extends conventional Publicly Verifiable Secret Sharing (PVSS) by requiring the dealer to publish a commitment or encryption of the shared secret, enabling more efficient and versatile constructions for a variety of cryptographic protocols. In this paper, we further enhance this paradigm by introducing Packed Pre-constructed PVSS (3PVSS), which allows a dealer to encode multiple secrets within a single polynomial while maintaining the pre-constructability property. We present two constructions of 3PVSS schemes. In the first construction, the dealer publishes a single commitment to all shared secrets, providing a compact representation that is particularly suitable for applications requiring efficient communication. In the second construction, the dealer publishes individual commitments to each secret, enabling greater flexibility in applications that require independent verification of multiple shared values. Both schemes preserve the key advantages of PPVSS, including the optimistic reconstruction approach enabled by pre-constructability. We demonstrate that these two variants naturally support different applications. Using the first 3PVSS construction, we revisit the ALBATROSS randomness generation protocol proposed by Cascudo and David (ASIACRYPT 2020) and present a more efficient variant with reduced computation and communication costs. As an application of the second construction, we extend the universally verifiable e-voting protocol recently proposed by Baghery, Knapen, Nicolas, and Rahimi (ACNS 2025) to support multi-candidate elections, while preserving universal verifiability. Our results show that the resulting protocols outperform their original counterparts in terms of efficiency.

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

This paper introduces AuditPay, a novel mechanism for blockchain mixers that enables controlled oversight through an ``auditing budget.’’ Auditors may monitor up to a budgeted number of addresses per epoch (e.g., an hour or a day), without revealing to users which addresses are monitored. Unlike traditional approaches that require users to voluntarily disclose viewing keys to trusted gatekeepers, AuditPay cryptographically enforces auditing compliance while preserving privacy for non-monitored user addresses and without introducing additional trust assumptions. At the core of AuditPay’s design is a selective encryption mechanism coupled with an efficient audit-key encoding scheme, enforced by a lightweight zero-knowledge proof. Users encrypt audit-relevant information under an audit key, which permits decryption only if the payment is to (or, alternatively, from) an address selected by the auditor for monitoring. We implement AuditPay as an Ethereum-based payment mixer and show through experiments on our prototype that its performance and gas-cost overheads are modest, providing a practical solution for balancing payment oversight with user privacy.

Private Set Union (PSU) enables two parties to compute the union of their private sets without revealing anything beyond the union itself. Existing PSU protocols remain much slower than private set intersection (PSI), often by a factor of around $30\times$. In this work, we present the first PSU protocol based on Invertible Bloom Lookup Tables (IBLTs), introducing a fundamentally new framework that departs from traditional, inefficient approaches. Our protocol exploits structural invariants between each party’s IBLTs and their union to compute the union efficiently without explicitly constructing a combined IBLT. Central to our approach is the notion of union peelability, which allows union elements to be recovered directly from the original IBLTs. We securely implement this functionality using only Oblivious Transfer (OT) and Oblivious Pseudorandom Function (OPRF) for equality checks, ensuring no information beyond the union is leaked. As a result, for set sizes ranging from $2^{14}$ to $2^{20}$, our protocol achieves a runtime of $0.08$ to $2.95$ seconds in the LAN setting, which is comparable to state-of-the-art PSI. We also show substantial speedups over prior PSU work—up to $10\times$ faster in LAN settings and consistently faster in WAN scenarios—while maintaining linear computation and communication complexity with small constants.

Large Language Models (LLMs) are frontier deep learning systems that have achieved remarkable success across a wide range of AI services. However, their substantial computational and memory requirements make them difficult to deploy and run on local hardware. Due to these resource requirements, users often rely on untrusted cloud infrastructure providers to perform model inference. However, outsourcing introduces the challenge of verifying that the returned output is the genuine result of the specified model. In this work, we present DeepProve, the first system to enable efficient end-to-end verification of full LLM inference (i.e., for all generated tokens of a prompt) on untrusted cloud servers using zero-knowledge proofs (ZKPs). In contrast, prior work either provides only a proof-of-concept partial implementation for a single token (zkGPT, USENIX'25), or focuses exclusively on specific components of the inference pipeline, such as Softmax (zkLLM, CCS'24). DeepProve achieves end-to-end verification by certifying the correctness of the output sequence rather than encoding the expensive inference computation in-circuit, an approach that would require either circuit size quadratic in the sequence length or costly in-circuit modelling of RAM operations. The core building blocks of DeepProve are sum-check protocol and lookup arguments, which enable efficient proof of correctness of all operators needed for GPT-2 and Gemma 3, such as multi-head attention and layer normalization for GPT-2, and grouped-query attention, root mean square normalization, and rotary positional embeddings for Gemma 3. Our evaluation shows that DeepProve can prove inference of GPT-2 and Gemma 3 at approximately 174 and 86 tokens per minute, respectively, which is 20-60 faster than the state of the art, without any significant loss in accuracy. Verification takes only 1 to 3.7 seconds. By distributing proof computation across multiple nodes, DeepProve can further improve the prover time while reducing the memory requirements for individual machines. With distributed proving, DeepProve can scale the throughput to 1855 tokens per minute. Our work represents the first full system for end-to-end LLM inference verification, thus paving the way for secure and trustworthy AI services.

End-to-end encryption (E2EE) provides strong confidentiality guarantees to users by preventing service providers from accessing their data. At the same time, it introduces new operational challenges, most notably the restoration of an E2EE-protected backup on a new device after loss of the original device. In recent years, major instant messengers have deployed increasingly sophisticated key-retrieval schemes for encrypted backups, ranging from simple recovery codes to designs that depend on trusted hardware or advanced cryptographic primitives such as oblivious pseudorandom functions (OPRFs), threshold OPRFs, and secret sharing. While recent work has largely emphasized stronger cryptographic guarantees, the practical costs and trust assumptions implied by hardware dependencies and complex primitives are often not made explicit. We present a structured framework for the comparative evaluation of E2EE backup key-retrieval schemes across usability, deployability, and security properties, and apply it to simple recovery codes, real-world deployments, and recent proposals from the literature, explicitly distinguishing recovery that depends on user-chosen low-entropy secrets from recovery using high-entropy material. Our evaluation shows that schemes whose recovery ultimately relies on user-chosen low-entropy secrets can provide substantially weaker resistance against large-scale adversaries than an approach using simple recovery codes. Even when assuming high-entropy recovery secrets, many recovery protocol designs introduce additional trust assumptions and potential single points of failure (e.g., compromise of specialized components or trusted setups) that can amplify the impact of large-scale adversaries. Overall, our results highlight that added system complexity often trades off against limited security gains under realistic threat models, motivating clearer accounting of cost and distribution of trust in future designs.

We present a Byzantine agreement protocol to address the inefficiencies inherent in multi-valued Byzantine agreement protocols, i.e., a version of the Byzantine agreement protocol where every party broadcasts its request, and at the end of the protocol, every party agrees on one of the party’s requests. The protocol we present is a validated asynchronous Byzantine agreement protocol, i.e., a party’s request must be validated by some external validity property before it is proposed for agreement. Differently from most of the MVBA protocols, we allow only a subset of total parties to broadcast their requests instead of all, and we make the subset selection stochastic each time the parties choose to broadcast a new set of requests. Then, at the time of the agreement, we choose a party from the selected subset, and the parties reach an agreement on the selected party’s broadcast. Extensive theoretical analysis shows that this approach can produce efficient output regarding messages and computation overhead, but the protocol is time-consuming.

Minimizing round complexity is a central goal in secure Multi-Party Computation (MPC), particularly for deployment on high-latency networks. While constant-round protocols with concrete efficiency have been constructed, they are typically designed for Boolean circuits and each gate incurs a bandwidth cost linear in the security parameter. Moreover, for arithmetic-heavy applications such as privacy-preserving machine learning and statistical analysis, compiling arithmetic operations into Boolean gates incurs another substantial overhead in circuit size and communication. Conversely, existing arithmetic MPC protocols, such as SPDZ, require interaction rounds proportional to the circuit depth, imposing significant latency. In this work, we bridge this gap by presenting the first concretely-efficient maliciously-secure MPC protocol that achieves both constant-round and constant-rate communication, where the rate is defined as the bandwidth cost per party divided by the number of gates and the size of the values each gate operates on. Our protocol computes over bounded integers and is secure against a static, malicious adversary corrupting up to $n-1$ parties. The protocol is built upon the arithmetic garbling framework of Ball et al. (Eurocrypt 2023) and follows the BMR template, assuming the Decisional Composite Residuosity for the garbling phase and Learning Parity with Noise for preprocessing. We evaluate our protocol on matrix-vector multiplication, a fundamental operation for data analysis. For standard computation parameters, we reduce communication bandwidth by $101\times$ to $247\times$ and improves end-to-end runtime by $4.4\times$ to $10.7\times$ compared to state-of-the-art constant-round Boolean MPC baselines, even when accounting for the overhead of a full bit-decomposition on the output vector.

Publicly verifiable secret sharing (PVSS) is a fundamental primitive in threshold cryptography that allows a dealer to share a secret $S$ among a set of $n$ parties via a publicly verifiable transcript. Any subset of $t+1$ parties can then use their individual shares to reconstruct the full secret $S$, whereas $t$ or fewer shares give no information about $S$. As such, the secret $S$ remains hidden from an adversary that corrupts up to $t$ parties. Recently, Bacho and Loss (CCS 2023) gave the first proof of any PVSS scheme under an adaptive adversary. However, their security proof relies on strong and non-standard assumptions such as the algebraic group model (AGM) and the hardness of the one-more discrete logarithm (OMDL) problem. In particular, any protocol (e.g., distributed randomness beacon or distributed key generation) that makes use of a PVSS scheme either inherits these limitations or is not provably adaptively secure. In this work, we present for the first time an adaptively secure PVSS scheme from well-established assumptions. In more detail, we provide two PVSS schemes with different properties. Our first scheme works over any pairing-free cyclic group and its security relies on the decisional Diffie-Hellman (DDH) assumption. Our second scheme works over an asymmetric pairing group, its security relies on the DDH and the co-computational Diffie-Hellman (co-CDH) assumption, and has the particularly valuable feature of aggregatability, which allows the aggregation of multiple PVSS transcripts into a single transcript while preserving verifiability. Notably, both our schemes are highly efficient, non-interactive, and work in the established plain public key model. These properties along with their provable adaptive security make them suitable candidates as building block in higher-level distributed protocols that aim to minimize communication.

Quantum key distribution (QKD) enables the exchange of information-theoretically secure symmetric keys, but is fundamentally limited in range. Existing long-distance QKD networks rely on trusted relay nodes, any one of which can compromise the entire key. We propose a key-transport protocol that removes this trust assumption by combining proactive secret sharing with one-time pad encryption over pairwise QKD links. At each layer of relay nodes, shares are reshared so that corruptions across different layers cannot be combined; security depends only on the maximum number of corruptions within any single layer, not on the total number of corrupted nodes. We formalize a game-based security model for layered secret transport, identify a cross-layer attack that affects a prior construction, and prove our protocol information-theoretically secure against a semi-honest adversary corrupting up to $t{-}1$ nodes per layer.

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

Authenticated Private Information Retrieval (Authenticated PIR) allows the client to retrieve the desired database entry without revealing any information about the query, while safely aborting if malicious behavior by the server is detected (presented in USENIX '23). However, two key challenges remain: existing single-server authenticated PIR schemes with sublinear online communication have not yet been clearly and fully implemented; incremental updates to the digest introduce unnecessary overhead. In this paper, we implement the previously outlined idea and present two complete and concrete single-server authenticated PIR schemes with $O(\sqrt{N})$ online communication, namely LWE-AuthPIR and DDH-AuthPIR, along with detailed security proofs. Furthermore, we introduce the notion of single-server authenticated and incremental PIR and propose a corresponding concrete construction, LWE-AuthIncPIR. LWE-AuthIncPIR supports immediate updates to individual entries and integrates a communication-efficient row aggregation for periodic update scenarios. When 1\%-8\% of the entries in a 1GB database are modified, LWE-AuthIncPIR reduces offline preprocessing computation by 19-88$\times$ compared to previous incremental update method. In the password breach detection, LWE-AuthIncPIR achieves a 67$\times$ reduction in preprocessing time and a 2.9$\times$ reduction in communication overhead.

Proof-carrying data (PCD) is a powerful paradigm for verifying distributed computations. Each node in the computation produces a proof that can be checked efficiently, regardless of how complex the overall computation is. As PCDs—and their special case, incrementally verifiable computation (IVC)—gain wider adoption, it becomes crucial to understand how robust they are against malleability attacks. In particular, it remains completely unexplored whether recursive proof systems satisfy simulation extractability (SIM-EXT)—a property ensuring non-malleability and composability. This work provides the first systematic study of simulation extractability for PCD. We begin by observing that the standard SIM-EXT notion for non-recursive zkSNARKs does not directly extend to PCD/IVC settings. To address this, we propose a new definition of SIM-EXT tailored to proof-carrying data that accounts for their idiosyncratic features. Using this framework, we prove two general results: (1) that a simulation-extractable SNARK implies a simulation-extractable PCD when used recursively, and (2) that more lightweight PCD constructions—built from a (not necessarily succinct) argument of knowledge (NARK) combined with a split-accumulation scheme—also achieve SIM-EXT of PCD by requiring SIM-EXT only from the underlying NARK. Our results show that many modern PCD systems are already simulation-extractable by design.

We construct protocols for oblivious pseudorandom functions (OPRFs) based on alternating moduli assumptions in the "Crypto Dark Matter" paradigm (Boneh et al, TCC 2016). Prior OPRFs based on this type of assumption were only secure against a semi-honest adversary. We show how to obtain maliciously secure protocols, by leveraging new cut-and-choose techniques for generating correlated randomness based on vector oblivious linear evaluation (VOLE), which allow efficient conversions between different moduli in zero-knowledge and secure two-party computation. Compared with the state-of-the-art GOLD OPRF (Yang et al, S&P 2025), our construction has a faster online phase in all settings, as well as overall better efficiency in the small-batch setting. Furthermore, our construction supports obtaining a secret-shared output, and can be extended to handle secret-shared inputs. This opens up additional applications in variants of private set intersection and secure database operations.

We construct succinct arguments of knowledge for computations over the ring of integers $\mathbb{Z}$ ($\mathbb{Z}$NARKs). Our motivation stems both from the theoretical challenge of developing general techniques for arguments over the integers and their practical applications. For example, many natural applications can be viewed as special cases of proving over $\mathbb{Z}$—e.g. cryptographic primitives based on RSA groups or Ring-LWE; field emulation and field "switching"; arbitrary-precision arithmetic. Moreover, $\mathbb{Z}$NARKs can support arbitrary mixing and matching of these settings within the same computation, which is not easily possible with solutions tailored to a specific arithmetic. Unlike prior works targeting $\mathbb{Z}$ or $\mathbb{Z}_{2^k}$, we avoid most of the complexities involved in extracting over these rings directly. Instead, we introduce a general, simpler theoretical framework for building succinct arguments over $\mathbb{Z}$, one which allows protocol designers to reuse existing SNARK techniques. This is possible thanks to our key technique—fingerprinting, a form of arithmetic hashing—for "bootstrapping" protocols over the integers from existing systems over prime fields (e.g., multilinear-flavored ones, such as Spartan). The resulting protocol can then be compiled into a cryptographic argument via a novel kind of polynomial commitment allowing queries to a multivariate integer polynomial modulo an arbitrary prime $q$. We show how to instantiate our framework and obtain a concrete scheme, $\mathbb{Z}$aratan. This is the first construction in literature being _fully_ succinct over integer computations, i.e., with short proofs and fast verification even when the witness consists of large integers.

This work studies the security and constructions of correlation robust (CR) hash functions in secure multi-party computation (MPC). Existing definitions of CR hashing are all game-based (i.e., no simulator to achieve programmability or extractability), but MPC protocols are proven secure in the simulation-based models including both stand-alone and universal composability models. We found that for some MPC protocols, e.g., TinyOT-like authenticated-triple generation protocols and correlated oblivious transfer (COT) extension protocols, such a mismatch could lead to a gap in security proofs, even for the semi-honest adversary and stand-alone model. To bridge the gap, we introduce a simulation-based security notion for CR hash functions to allow secure composition. Instead of building from scratch, we introduce such a simulator to a wide class of existing ideal-cipher-based CR hashing constructions, and derive the security bound from their original game-based CR security. This enables us to obtain an efficient CR hashing construction making just one call to a blockcipher, and is much more efficient than the construction from a random oracle used in previous TinyOT-like protocols. We showcase the utility of the new CR notion in easing security proofs and mitigating the risk of errors on two classes of protocols: (1) authenticated-triple generation protocols in the TinyOT family with a countermeasure; (2) COT extension protocols with bootstrapped iterations.

Correlation robust hash function (CRHF) is an important class of building blocks that have found applications in many cryptographic applications, including various protocols for zero-knowledge (ZK) proof, circuit garbling, vector oblivious linear evaluation (VOLE), etc. It offers more efficient instantiations from block ciphers as compared to cryptographic hash functions like SHA-3. State-of-the-art instantiations work provide near-optimal security in the ideal cipher model that can in turn be efficiently instantiated using AES, which is standardized and provides instruction-level acceleration. However, since AES is only available for 128-bit block size, they cannot be generalized beyond 128-bit security while enjoying the same level of efficiency. In this paper, we fill this gap by constructing a new multi-instance tweakable circular CRHF (miTCCR) from AES, supporting up to 256-bit security. Since miTCCR is the most general notion of CRHF, it directly leads to numerous applications. 1. The state-of-the-art optimization of GGM tree (Eurocrypt'23), which builds on circular CRHF as a black box, can be instantiated with our construction, boosting its security strength, as well as the security of the VOLE-ZK protocols building on top, from 128 bits to 256 bits. 2. With a new extractability notion, we use the miTCCR hash to instantiate the leaf commitment in an all-but-one vector commitment scheme, which is a core primitive of post-quantum digital signature schemes and ZK in the VOLE-in-the-Head framework. Experiments show that our technique could reduce the end-to-end signing/verification time of FAEST (resp. FAEST-EM) by 13.1%~40.4% / 15.2%~46.4% (resp. 1.5%~25.0% / 2.9%~24.2%). 3. The multi-instance-secure half-gates garbling scheme (Crypto'20) uses miTCCR as a black box. Our construction can strengthen its security as well as the security of constant-round multiparty computation building on half-gates to 246-bit.

The study of efficient multi-party computation (MPC) has been a central focus of cryptographic research, leading to a broad range of techniques across diverse practical models. However, the vast majority of this work assumes reliable communication channels and largely ignores network-level noise, a fundamental characteristic of modern communication systems. In this work we study information-theoretic MPC over noisy networks in the multi-party setting. We construct an $n$-party MPC protocol that is secure against semi-honest adversaries corrupting a majority of the parties assuming all communication is carried over BSC channels with a fixed bit-flip probability. Our construction incurs only constant-factor communication overhead compared to the underlying MPC protocol over noiseless channels: specifically, it computes any circuit $C$ with communication complexity $O(n^2(|C|+\kappa))$, where $\kappa$ is a statistical security parameter. This substantially improves the naive approach, which can only guarantee super-linear communication, namely, $O(n^2|C|(\kappa+\log |C|))$. To achieve this result, we introduce a novel multi-party interactive coding scheme tailored to cryptographic protocols that rely on correlated randomness. We show that combining this coding scheme with the classical GMW protocol yields a noise-resilient MPC protocol that preserves its security guarantees while incurring only linear overhead. A central technical challenge we address is a subtle correctness issue that arises in the simulation of protocols with correlated randomness: without careful synchronization, different parties may use inconsistent correlated randomness for what is logically the same protocol step, causing the computation to fail even in the absence of noise. Our novel interactive coding scheme ensures that all parties use consistent correlated randomness in every simulated round of the MPC. Surprisingly, this issue also affects the two-party simulation over noisy channels [Gelles, Paskin-Cherniavsky, and Zikas, SCN’18], leaving an unaddressed gap in its analysis. Our techniques provide a way to resolve this gap.

Adaptor signatures are a foundational fairness primitive for blockchain applications. They enhance blockchain functionality by enabling applications such as atomic swaps, payment channels, and other fair-exchange protocols. At a high level, they allow a buyer to produce a pre-signature tied to a public statement, which a seller holding a corresponding witness can adapt into a valid signature. Once this signature is posted on-chain, the seller obtains payment, while the buyer can extract the witness from the finalized signature. Existing practical adaptor signature constructions are predominantly tied to discrete-logarithm-based signatures, such as ECDSA and Schnorr, reflecting their widespread use in current blockchain deployments. However, the threat of Shor's algorithm and the broader transition toward post-quantum cryptography raise the question of whether adaptor functionality can also be realized efficiently for post-quantum signature schemes. In this work, we answer this question for a broad class of signatures based on cryptographic group actions. Building on efficient MPC-in-the-Head-style group-action signatures, we obtain adaptor functionality through small modifications, yielding a general framework for adaptor signatures from arbitrary group actions. In particular, our construction supports selling group-action discrete logarithms, which in certain parameter regimes correspond to the secret keys of the underlying signature scheme. We further discuss concrete instantiations from several group-action families, including those underlying schemes such as CSI-FiSh, LESS, MEDS, and ALTEQ, and present a modular proof-of-concept implementation. We obtain a ~25kB pre-signature with ~100ms pre-signing time for LESS, MEDS and ALTEQ, while a ~4kB pre-signature with ~3.6s pre-signing time for CSI-FiSh.

Digilocker is a key component of India's Digital Public Infrastructure, enabling secure digital storage, retrieval, and sharing of government-issued documents. Given its large-scale deployment and reliance on protocols such as OAuth 2.0 with PKCE, HMAC-based API authentication, digital signatures, and encrypted storage, rigorous security assurance is essential which can not be be ensured through conventional testing alone. In this work, we present a formal modeling and verification of DigiLocker’s authentication and document-handling workflows using the Tamarin Prover. We model the OAuth 2.0 authorization code flow with PKCE, issuer-based document retrieval mechanisms (PullURI and PullDoc), document push workflows, and self-upload with encrypted storage under the Dolev–Yao adversary model. We formally specify and verify key security properties, including token secrecy, authorization code uniqueness, PKCE binding, document authenticity, integrity, confidentiality, and key management. Our results show that DigiLocker’s protocol design satisfies these properties under ideal assumptions. However, controlled credential-leak scenarios demonstrate that compromise of sensitive values such as API keys or digilockerids can lead to exploitable attack traces. This study highlights the value of formal verification in strengthening security guarantees for large-scale e-governance systems.

A fully shuffled permutation of four cards suffices to implement 1-of-2 Oblivious Transfer at a rate of one transfer per shuffle. After dealing two cards to Alice and one to Bob, Alice deterministically selects item from a threefold partition of the edges of a tetrahedron, at which point OT is established. Unlike decades of 2-player computation results employing restricted permutations (as in den Boer's groundbreaking Five Card Trick) and artificial decks with repeated symbols, the "Tetrahedral OT" is the first to achieve two-party secret computations using a fully-shuffled set of unique elements. New "tenancy" and "narrowing" techniques are developed. Design patterns and protocol generation parameters are presented, along with some insightful but less efficient choices. The geometric symmetries behind the Tetrahedral OT protocol open up connections from Oblivious Transfer to Secret Key Exchange protocols as well. Decoupling information-theoretic permutations from computational one-wayness provides systematic access to broader and novel MPC protocol design, insight and simplification.

We present new techniques for converting secret-shared values between different moduli in arithmetic MPC, without relying on bit decomposition. More concretely, our protocols convert a sharing \([x]_q\) over a source modulus \(q\) into a sharing \([x]_t\) over a target modulus \(t\), under a mild bound on the size of \(x\). We give three variants: a particularly simple protocol for power-of-two moduli, a protocol for arbitrary source modulus and prime target modulus, and a general protocol for arbitrary target modulus via an intermediate prime modulus. All variants use only a constant number of openings and a small amount of preprocessing. We present them in the arithmetic black box model, so they can be instantiated on top of any MPC protocol supporting basic modular arithmetic. As a main application, we use these techniques to construct efficient threshold decryption protocols for lattice-based fully homomorphic encryption (FHE), including BFV, BGV, and related schemes. The resulting protocols are special-purpose MPC protocols with a small constant number of rounds. They avoid noise flooding, allowing the parameters of the underlying FHE scheme to be chosen without making room for additional decryption noise. The resulting protocols achieve statistical UC security against malicious adversaries. We improve substantially on previous work on MPC-based threshold FHE decryption: as a concrete example, the state-of-the-art protocol by Zyskind et al. (ACM CCS 2025) implements decryption of the BFV scheme (with ciphertext modulus $2^{64}$), using about 17.000 bits of preprocessed correlated randomness, while we need only 63.

Post-quantum secure digital signatures based on the MPC-in-the-Head (MPCitH) paradigm, a zero-knowledge (ZK) proof-based construction, are becoming increasingly popular due to their small public key size. However, the development of techniques for protecting MPCitH-based schemes against side-channel attacks remains slow, despite them being critical for real-world deployment. In this work, we adapt the Hypercube-MPCitH framework exploiting its native use of additive secret sharing to enable inherent protection against first- and high-order differential power analysis (DPA). We first perform a sensitivity analysis of the Hypercube Syndrome Decoding in the Head (SDitH) digital signature scheme with respect to both simple and differential power analysis. Based on the insight into its side-channel sensitivity, we then propose a tweak to the signature scheme to increase its inherent resistance against DPAs by design, eliminating the need to explicitly mask large parts of the signing procedure. More specifically, this is achieved through the novel (k+1)-Hypercube ZK Protocol: the proposed tweak increases the number of hidden shares an adversary must probe to recover the secret key from one to k+1, thus achieving inherent masking order k. Typically, increasing the amount of hidden shares results in a degradation of soundness in the zero-knowledge proof and as a result increases the signature size to a point where the scheme becomes of limited practical interest. To address this, we propose a technique to select the hidden shares in a more structured and optimal fashion, by exploiting the GGM tree structure in the Hypercube-MPCitH framework. As a result, the amount of revealed seeds is reduced, thus resulting in a smaller signature size even compared to the original hypercube protocol. Finally, we implement and benchmark the proposed Hypercube-SDitH signature scheme, comparing it against the cost of traditional masking. We propose different parameter sets that explore a trade-off between computational overhead and signature size. For 3rd-order protection, our tweaked signature scheme only incurs a 35-50% overhead in computational cost, compared to an estimated overhead of 300% for a fully masked implementation, while the overhead in signature size stays relatively low (52%). Overall, we demonstrate that the proposed (k+1)-Hypercube ZK Protocol can be used to construct efficient, DPA-resistant MPCitH-based digital signatures.

Hall-Andersen, Simkin and Wagner (CiC 1:4) show how to construct data availability sampling schemes from code commitments. Later, in FRIDA (CRYPTO'24), the same authors describe a compiler that takes an interactive oracle proof of proximity (IOPP) for a code and produces a secure code commitment. Chaining both results allows to construct efficient data availability sampling schemes from IOPPs. In this short note, we give a novel security analysis that extends the results of FRIDA beyond the unique decoding radius of the code being used. This strict improvement leads to data availability sampling schemes with smaller commitments. Towards our novel analysis, we define a variant of the opening-consistency property introduced in FRIDA, which we name opening-consistency with assign. Crucially, our new property does not depend on the unique decoding radius of the code. We then show that the FRIDA compiler can be applied to IOPPs that have opening-consistency with assign to produce secure code commitments. Finally, we show that under mutual correlated agreement, the batched FRI protocol (FOCS'20) satisfies opening-consistency with assign. This latter result is enabled by a recent analysis of FRI by Garreta, Mohnblatt and Wagner (ePrint 2025/1993).

Can a relevant cryptographic primitive, when instantiated over the NIST P-256 elliptic curve, achieve a bit-security level exceeding $128$ bits? Yes. We formally prove that the well-known password-authenticated key exchange protocol $\mathsf{EKE}$, introduced by Bellovin and Merritt (S&P 1992), achieves a generic security level of $128+\frac{1}{2}\log_2(N)$ bits, where $N$ denotes the size of the password space. To prove this result, we introduce and develop a new approach for showing that breaking a cryptosystem with a prescribed advantage requires solving many instances of an underlying computational assumption. To this end, we formulate the Hidden-Target Diffie-Hellman assumption. In this assumption, the adversary is given a set of $N$ Diffie-Hellman challenge instances. The Diffie-Hellman key of one uniformly random instance is designated as the hidden target. The adversary does not know which instance is the target, but may output an arbitrary subset of candidate solutions and succeeds only if this subset contains the target. We formally prove that breaking the Hidden-Target Diffie-Hellman assumption with probability greater than $(k-1)/N$ requires solving at least $k$ of the $N$ Diffie-Hellman instances. We then show that the security of $\mathsf{EKE}$ in the ideal-cipher model is equivalent to the Hidden-Target Diffie-Hellman assumption. A somewhat surprising consequence of this equivalence is that $\mathsf{EKE}$ achieves the claimed generic security level of $128+\frac{1}{2}\log_2(N)$ bits. Moreover, the equivalence implies that $\mathsf{EKE}$ remains secure even in settings where the hardness of $\mathsf{DLOG}$ or $\mathsf{CDH}$ is weaker than expected: an adversary may still need to solve on the order of hundreds or thousands of discrete logarithm instances in order to succeed, a task that may remain infeasible even for powerful attackers, including those equipped with early quantum computers.

SAE and SAE-PK are the core security protocols introduced in the latest Wi-Fi security standard, WPA3, to protect personal networks. SAE-PK extends SAE to prevent the so-called evil twin attacks, where an attacker with the knowledge of the password attempts to impersonate a legitimate access point. In this work, we present the first provable security and privacy analysis of SAE and SAE-PK. We introduce formal models that capture their intended properties and use these models to analyze the guarantees these protocols provide. First, we identify an attack that prevents SAE from fulfilling its intended authentication guarantees. As a result, SAE can only be proven secure within a weaker security model, which we also formalize and show the proof in. To achieve the desired level of security, we propose two simple fixes, resulting in two efficient SAE protocols that we call SAEv2 and SAEv3. We prove that both protocols meet the intended security guarantees, with SAEv3 providing greater robustness. Next, we prove that SAE-PK is indeed secure against evil twin attacks, but its current design introduces a theoretical vulnerability to offline dictionary attacks, which contradicts the expected security guarantees of SAE-PK as an enhanced password-authenticated key exchange protocol. To remedy this, we show that SAE-PK can be modified with minimal changes to fully realize its desired security goals. Finally, we analyze the privacy guarantees of SAE, SAE-PK, and our proposed enhanced variants. We prove that their cryptographic core preserves the unlinkability of client devices across distinct Wi-Fi networks, if MAC address randomization is properly applied.

Zero-Knowledge Succinct Non-Interactive Arguments (zkSNARGs) are SNARGs in which the proof reveals nothing except the validity of the claim. zkSNARGs for NP can be constructed generically from SNARGs for NP using a Non-interactive Zero-knowledge (NIZK) proof, but this transformation uses either the NIZK or the SNARG in a non-black-box way. We design a new SNARGs-to-zkSNARGs transformation that is conceptually different from the NIZK+SNARG approach. Our transformation is inspired by the elegant construction of succinct interactive ZK arguments of Ishai, Mahmoody and Sahai (TCC`12) which combines a cryptographic hash function with an information theoretic ZK proof system (specifically, a Probabilistically-Checkable Proof). Our construction takes a first step towards fully black-box (BB) zkSNARG constructions: it uses the underlying SNARG as a black-box (though the other cryptographic components are used in a non-BB way). Our transformation is applicable to SNARGs for sub-classes of NP: batched NP computations (i.e., BARGs); and languages that have computational non-signaling PCPs, which contains NTISP (non-deterministic bounded space). As a corollary, we get zkBARGs for NP, and zkSNARGs for NTISP, from the Learning With Errors (LWE) assumption. Thus, our results give a scaled-down version of the zkSNARGs-to-SNARGs reduction for NP, showing that by restricting to a sub-class of NP, the zkSNARG construction can be based on standard assumptions. A main ingredient underlying our transformation is a new commitment primitive, called Hiding Somewhere-Extractable commitment (HSE), which we introduce and construct based on LWE. This commitment primitive enhances somewhere statistically-binding hash functions (Hubáček and Wichs, ITCS 2015) to also guarantee hiding, and could be of independent interest.

Electronic identification (eID) protocols and federated identity management systems play an increasingly important role in our modern society, both on the internet through services from Google and others, and through the eIDAS regulation in Europe. A key feature of eID protocols is that humans are intimately involved in the protocol, often responsible for critical security steps. Traditional security analyses of such protocols typically assume flawless user behaviour, yet widespread real-world adoption makes user mistakes inevitable. We present a framework for analysing the security of eID protocols that can model users making mistakes. It is suitable for automated analysis with Tamarin and supports fine-grained corruption modelling of protocol actors. We demonstrate the framework's utility by describing and analysing common eID protocols based on passwords, mobile applications and authentication tokens, as well as by systematically evaluating the impact of various combinations of user mistakes on security.

Anonymous whistleblowing systems allow insiders to report organizational misconduct while preserving confidentiality and anonymity. Existing systems often use Tor-based submission and encryption under a recipient public key, so the mailbox does not learn the submitter’s network address or report contents. This protection does not remove reliance on the parties that authenticate insiders or open reports. Two corruption risks remain: (1) token-issuance records held by an authentication server can be correlated with a submission to link the report to a registered insider; and (2) a recipient with unilateral plaintext access may suppress, selectively disclose, or influence the report before any accountable opening process. We present AWARE, a non-interactive whistleblowing protocol for anonymous report submission by eligible insiders and threshold opening of reports. AWARE separates identity authentication from submission: after scheduled token refresh, an eligible insider can submit a report with a locally finalized token, without contacting the authentication server at submission time. AWARE also replaces single-recipient opening with committee threshold opening: report recovery requires a threshold of committee decryption shares that pass verification. Under the stated corruption and leakage assumptions, we prove the corresponding anonymity, token unforgeability, report confidentiality before opening, and opening integrity properties. A Java implementation shows practical costs in the tested settings.

Multi-signatures allow many signers to jointly generate a single (short) signature on a message. In this context, we introduce doubly aggregatable signatures, a new primitive that consists of two sets of signers. It enables a layer-1 signer to create a succinct attestation, called the layer-1 signature, to the set of observed layer-0 signatures on the same message, and publicly aggregate many layer-1 signatures into a succinct certificate. This certificate can be verified against the public keys, the message, and a bit map of “who observed whom”. Our security model captures both the standard notion of unforgeability (i.e., the adversary cannot forge layer-0 or layer-1 signatures on behalf of honest parties), and resistance to equivocation attacks, where the adversary tries to create a layer-1 signature attesting to layer-0 signatures it has not observed. We give two concretely efficient constructions in the random-oracle model, both of which attain constant-size aggregate layer-1 signatures. The first scheme enables verification using only group additions and two pairings, but requires linear-sized layer-1 public keys per party. The second scheme achieves constant-size public keys, but requires a linear number of pairings for verification. By leveraging the random modular subset sum (RMSS) problem, both schemes attain purely algebraic verification, enabling commit-and-prove SNARKs to check succinct predicates on the bit map. A major application of doubly aggregatable signatures is incentivizing timely all-to-all vote dissemination in consensus protocols. We demonstrate the concrete efficiency of our schemes with a prototype implementation.

Suppose Alice holds a master secret key $\mathsf{sk}$ in an identity-based encryption scheme. For a given set of identities $\mathcal{I}$, Alice wants to create a short pre-decryption key that lets anyone decrypt the ciphertexts encrypted under any identity in $\mathcal{I}$ and nothing else. This problem is called batch identity-based encryption (batch IBE). When the secret key $\mathsf{sk}$ is shared among a number of decryption parties, the problem is called threshold batch identity-based encryption. This question comes up in the context of an encrypted mempool where the goal is to publish a short pre-decryption key that can be used to decrypt all ciphertexts in a block. Prior work constructed batch IBE schemes with some limitations. In this work, we construct new batch IBE and threshold batch IBE schemes. We first observe that a key-policy ABE (KP-ABE) scheme directly gives a batch IBE scheme. However, the best KP-ABE schemes happen to be lattice-based, and do not thresholdize efficiently. We then use very different techniques to construct a new lattice-based batch IBE scheme. Our construction employs a recent preimage sampler due to Waters, Wee, and Wu. Along the way, we develop a two-round protocol for preimage lattice sampling when the lattice trapdoor is secret shared among the participants.

We present a highly scalable instantiation of ZKML via proof of a verifiable decision forest inference circuit using a structured version of the GKR protocol [GKR15], [Tha13]. Through a combination of data parallel GKR over a structured improvement to [ZFZS20]'s circuit, we are able to create GKR proofs for a decision forest of 128 trees, each of height 9, over a set of 128 inputs, each with 64 features, in under 54 seconds. Notably, this represents a per-tree-per-sample proof time of just over 0.003s, representing a mere 180x prover-side blowup with respect to simply running the computation on CPU. In order to achieve this performance, we present several key optimizations, including a multi-stage claim aggregation optimization to the interpolation strategy presented within [Tha13], reducing the per-stage prover runtime from $O(m \cdot n \cdot 2^n)$ to $O(m \cdot (n - k) \cdot 2^n)$ for $m$ claims over $n$ variables, where $k$ of the variables across all claimed evaluation points are coordinate-wise identical, as well as a generalization of the linear-time prover technique from [XZZPS19] to the data parallel setting, allowing us to achieve a prover time of $O(2^{s_{i + 1} + b})$. We additionally provide benchmarks demonstrating the scalability of the approach, showing a sublinear relationship between proof time and adding additional trees to the forest and inputs to the batch, as well as highlighting the efficacy of both the claim aggregation optimization, i.e., a 40-60% improvement in proof generation time over the verifiable decision forest circuit, and the "Libra-Giraffe" algorithm, i.e., a linear relationship between proof generation time and the layer size/number of data parallel circuit copies. Our GKR prover is combined with the Ligero polynomial commitment scheme for committing to the input layer of GKR circuits, and we call the combination $\textit{Remainder}$. Our system is made fully non-interactive via Fiat-Shamir, and all benchmarks were run in a non-interactive fashion using the Poseidon [GKRRS21] hash function as the random oracle.

In this work, we study the communication complexity of MPC achieving perfect security with optimal resilience ($t<n/3$). We ask the question: ``Is it possible to build a perfectly secure MPC for arithmetic circuits of size $|C|$ with optimal resilience with communication of $o(|C|\cdot n)$ field elements?'' On the positive side, we construct a perfectly secure MPC protocol for general arithmetic circuits with communication complexity of $O(|C|)$ elements assuming preprocessing data of size $O(|C|)$, where the preprocessing data consists of packed Beaver triples over bivariate polynomials. Furthermore, we show that packed Beaver triples over bivariate polynomials can be prepared at an amortized cost of $O(1)$ elements plus $O(1)$ three-party Beaver triples per secret. On the negative side, we establish a communication lower bound proving that preparing packed Beaver triples over bivariate polynomials requires at least $\Omega(n)$ elements of communication per secret. This lower bound is derived by first proving a communication lower bound for verifying the correctness of packed Beaver triples with perfect security with abort, and then efficiently reducing the task of verifying packed Beaver triples to preparing packed Beaver triples over bivariate polynomials. To match this bound, we give a concrete construction for preparing packed Beaver triples over bivariate polynomials with $O(n)$ elements per secret, demonstrating the tightness of our lower bound. Our proof technique also extends to show that for the task of computing the inner-product of two length-$|C|$ vectors, any MPC protocol that achieves perfect security with abort requires either $\Omega(|C|\cdot n)$ elements of communication or $\Omega(|C|)$ elements of preprocessing data.

A private information retrieval (PIR) protocol allows a client to fetch any entry from single or multiple servers who hold a public database (of size $n$) while ensuring no server learns any information about the client's query. Initial works on PIR were focused on reducing the communication complexity of PIR schemes. However, standard PIR protocols are often impractical to use in applications involving large databases, due to its inherent large server-side computation complexity, that's at least linear in the database size. Hence, a line of research has focused on considering alternative PIR models that can achieve improved server complexity. The model of private information retrieval with client prepossessing has received a lot of interest beginning with the work due to Corrigan-Gibbs and Kogan (Eurocrypt 2020). In this model, the client interacts with two servers in an offline phase and it stores a local state, which it uses in the online phase to perform PIR queries. Constructions in this model achieve online client/server computation and bandwidth that's sublinear in the database size, at the cost of a one-time expensive offline phase. Till date all known constructions in this model are based on symmetric key primitives or on stronger public key assumptions like Decisional Diffie-Hellman (DDH) and Learning with Error (LWE). This work initiates the study of unconditional PIR with client prepossessing - where we avoid using any cryptographic assumptions. We present a new PIR protocol for $2t$ servers (where $t \in [2,\log_2n/2]$) with threshold 1, where client and server online computation is $\widetilde{O}(\sqrt{n})$ (the $\widetilde{O}(.)$ notation hides $\textsf{poly}\log$ factors) - matching the computation costs of other works based on cryptographic assumptions. The client storage and online communication complexity are $\widetilde{O}(n^{0.5+1/2t})$ and $\widetilde{O}(n^{1/2})$ respectively. Compared to previous works our PIR with client preprocessing protocol also has a very concretely efficient client/server online computation phase - which is dominated by xor operations, compared to cryptographic operations that are orders of magnitude slower. As a building block for our construction, we introduce a new information-theoretic primitive called \textit{privately multi-puncturable random set }(\pprs), which might be of independent interest. This new primitive can be viewed as as a generalization of privately puncturable pseudo-random set, which is the key cryptographic building block used in previous works on PIR with client preprocessing.

Bandwidth remains a major bottleneck in post-quantum cryptography, particularly for authenticated key exchange (AKE) protocols. In this work, we present DAKE, a bandwidth-efficient AKE framework built from double-KEM constructions. DAKE comes in two main versions achieving, respectively, weak and full perfect forward secrecy, as well as explicit authentication. It further admits two variants: a unilateral version, and another where a signature scheme replaces a KEM. They are proven secure in the standard model under eCKw and eCK-PFS, two strong variants of the extended Canetti–Krawczyk framework. DAKE employs a double-KEM, a primitive that encapsulates a single key under two public keys simultaneously. Such constructions can achieve smaller encapsulation sizes than two independent KEM encapsulations, offering a significant bandwidth advantage. To facilitate the design of double-KEMs compatible with DAKE, we introduce a chosen-key Fujisaki–Okamoto (CK-FO) transform proven in the QROM, which upgrades IND-CPA double-PKEs to IND-CCA double-KEMs while ensuring the one-sided chosen-key security required by DAKE. As a concrete instantiation, we propose Maul, a compact double-KEM derived from ML-KEM under the Hint-MLWE assumption. Maul reuses ciphertext components to cut encapsulation size by up to 42% compared to two parallel ML-KEMs. When instantiated with Maul, DAKE achieves overall communication reductions of about 16% (mutual authentication) and 21% (unilateral), outperforming both the double-KEM AKE of Xue et al. (ASIACRYPT 2018) and standard ML-KEM-based AKEs.

We propose a novel notion of Two-Factor Authenticated Key Exchange (TFA-KE), defined in the universal composability model (UC), which extends asymmetric PAKE (aPAKE) by a 2nd authentication factor in the form of a $t$-bit one-time code computed by a personal device based on a clock or counter. Our notion strengthens the security of standard integration of aPAKE with short authentication codes by additionally slowing down offline brute-force password search in case of server compromise by a factor of $2^t$. In other words, our TFA-KE notion uses $t$-bit authentication codes not only to improve on-line security of password authentication, as is the current practice, but also to strengthen password security on server corruption, whilst retaining the ability of aPAKE to avoid the common but deplorable practice of relying on "secure-channel" encryption for password protection. We show a generic framework for implementing TFA-KE, with two efficient instantiations. Our key enabling tool is a tight one-way function (TOWF) with an algebraic structure that allows for its evaluation on a secret-shared input. We initiate the study of such functions, and we provide two proposals which we show to be tightly one-way in the Generic Group Model. Tightness means that a function evaluation on an input sampled from domain $\mathcal{X}$ takes $\Omega(|\mathcal{X}|)$ time to invert, which in our application implies that offline password search attacks are slowed to $\Omega(|D|\cdot 2^t)$ for passwords sampled from dictionary $D$.

A UOV public key hides a distinguished linear subspace: the public-coordinate image of the central oil-coordinate subspace. In central coordinates, the homogeneous quadratic part of each UOV polynomial contains no oil-oil monomials. Consequently, for every honestly generated UOV public key, each public homogeneous quadratic form vanishes when restricted to this hidden oil subspace. We formalize the hidden oil-subspace relation and construct a Schnorr-like Sigma protocol that proves knowledge of such a subspace without revealing it. The witness consists of matrices $B,W$ satisfying $WB=I_o$ and $Q_k(Bz)\equiv 0$ for all public quadratic forms $Q_k$. The prover masks the witness linearly and responds to a challenge $c$ with $Z=A+cB$, $Y=E+cW$, yielding a protocol with computational 3-special soundness and computational honest-verifier zero knowledge. We prove a generic uniqueness theorem: in the random homogeneous UOV model, the hidden oil subspace is, with overwhelming probability, the unique $o$-dimensional common zero subspace. The uniqueness bound is explicit and negligible for UOV-type parameters. This strengthens the interpretation of the protocol as proving knowledge of the unique hidden oil subspace, rather than merely some oil-like subspace. We provide empirical observations on small parameters and discuss applications and limitations.

The Message Queuing Telemetry Transport (MQTT) protocol is highly preferable for Internet of Things (IoT) environments due to its lightweight architecture, but routing sensitive medical data through a central broker introduces severe privacy risks if the broker is untrusted or compromised. To address this, we propose secure MQTT, a high performance end to end encrypted (E2EE) protocol tailored for constrained devices that renders the broker completely blind to message payloads and incapable of man in the middle (MitM) attacks. Our design utilizes a nested AES-GCM encryption architecture that strictly separates link-level routing metadata from application layer confidentiality. To establish these secure channels efficiently, MQTT integrates MQTT v5.0 enhanced authentication key exchange mechanism via a challenge response embedding one time Broker Nonce into the Schnorr digital signatures version of HMQV key exchange protocol. This provide authenticated end to end session key derivation, that requires only a negligible computational increase over basic ECDH. The security of this proposed model has been rigorously proven using the ProVerif cryptographic verifier under the Dolev-Yao threat model, offering a highly secure, low overhead solution for modern IoT networks.

This paper formalizes the cryptographic core of the FLEX protocol and its enhanced variation FLEX2 . The analysis formalizes a minimal ledger abstraction, capturing Taproot, CSV timelocks, and reorg bounds, and defines ideal functionalities implemented as transaction-DAG and state machines. Main contributions include proving on-chain enforceability, CDS secrecy, soundness, leakage-bounded privacy, and universal composability realization under standard assumptions.

Asynchronous complete secret sharing (ACSS) and asynchronous dynamic proactive secret sharing (ADPSS) are fundamental primitives for secret sharing and resharing in modern threshold systems, such as multi-party computation, distributed key management, and blockchain. However, existing ACSS constructions that employ homomorphic commitments incur notable computational overhead, while the lightweight-computation constructions require quadratic per-secret communication, limiting scalability as the number of parties grows. ADPSS constructions inevitably inherit these inefficiencies due to their tight coupling to the commitment-based ACSS and requiring at least quadratic cross-committee communication. To break these bottlenecks, we design GoSSamer, a concretely and asymptotically efficient protocol suite, where both our ACSS and ADPSS achieve (1) lightweight computation with only hash function and symmetric encryption; (2) asymptotically optimal, linear per-secret communication; (3) optimal resilience in asynchronous networks; and (4) post-quantum security. In GoSSamer-ACSS, we propose an original-evaluation propagation paradigm for linear communication without commitment‑requiring interpolation, which further unlocks our lightweight bivariate-polynomial-based degree checking for share verification. Building on this foundation, GoSSamer‑ADPSS contributes two further techniques: a consistency verification technique that decouples the ADPSS framework from the commitment-based ACSS, and a dual-committee reconstruction technique that yields linear per-secret communication. When deployed in distributed AWS instances, GoSSamer-ACSS reduces the runtime by 95.6% compared to the linear-communication scheme hbACSS (NDSS'22) and 45.8% compared to lightweight SS24 (JoC'24). GoSSamer-ADPSS reduces the runtime by at least 67.7% compared to LongLive (Usenix Security'23). Moreover, when applied to practical distributed key management systems, the GoSSamer-ACSS-based distributed key generation is 7-11x faster than DXK+23 (Usenix Security'23), and GoSSamer-ADPSS-based key resharing reaches a throughput of 1994 keys/s across 10-node committees, compared to 85 keys/s in LongLive.

The Swiss Post voting system is one of the most advanced cryptographic voting protocols deployed for political elections, offering end-to-end verifiability and vote privacy. It provides significant documentation and independent scrutiny reports. Still, we argue that two significant pillars of trust need to be further developed. One is formal verification accompanied by machine-checked proofs. The second is security in presence of a corrupt setup component. In this work, we propose formal specifications of a simplified version of the Swiss Post voting protocol and initial verification results with the Tamarin prover. We also propose a revised protocol design that mitigates risks from a corrupt setup, and a prototype implementation of necessary zero-knowledge proofs.

We present a novel construction that applies the Ciphertext-Policy Attribute-Based Encryption paradigm in an original symmetric framework, where also the encryptor needs to have enough attributes to be able to produce a ciphertext for a given policy. The scheme is built from minimal assumptions on collision-resistant hash functions and pseudorandom functions, exploiting the properties of linear secret sharing and polynomial interpolation. Thus, it is natively Post-Quantum secure. We formally define a novel extended form for access trees, that trades a polynomial space expansion for a more predictable topological structure. This structure enhance the arithmetic possibilities of the associated secret sharing primitive. Moreover, we propose a comprehensive notation for access trees, sharing and interpolation, which may help in the study of these powerful primitives.

Designing non-interactive proof systems, such as NIZK or SNARKs, for lattice-based protocols is a well-motivated problem with numerous applications including aggregate signatures, verifiable random functions, group signatures, verifiable homomorphic encryption schemes, and others. Although many works have made efforts toward efficient lattice-based protocols, several challenges remain. In particular, a major challenge, as highlighted by Ganesh et al. (Journal of Cryptology 2023) and Zhang et al. (CCS 2025), is the algebraic gap between polynomial rings, which are typically used in lattice-based constructions, and fields, which are commonly used in the constructions of non-interactive proofs. In this paper, we introduce a novel technique called ring switching, which bridges this gap by transforming proofs over polynomial-ring arithmetic into proofs over finite fields or Galois rings with prime power modulus. Using ring switching, we construct an efficient non-interactive argument of knowledge for Ring-R1CS over $\mathbb{Z}_Q[X]/(X^N+1)$ for arbitrary prime-power moduli $Q$. Our construction achieves sublinear proof size and enables significantly faster verification by eliminating costly ring multiplications. The ring switching framework is compatible with parameter regimes used in practical lattice-based cryptosystems, including NTT-friendly and power-of-two moduli. Subsequent works building on this technique further demonstrate its efficiency, achieving substantial verification time improvements in lattice-based polynomial commitments and verifiable homomorphic encryption schemes.

Cheng and Meng (IEEE Transactions on Information Forensics and Security 2024) introduced server-aided public key authenticated encryption with keyword search (SA-PAEKS). In this short note, we give general attacks that the cloud server (tester) can obtain keyword information from both a ciphertext and a trapdoor.

Recent work on IOP-based succinct arguments has focused on developing IOPs that improve prover efficiency by relying on linear-time encodable codes. We present two new schemes for improving the efficiency of such succinct arguments: $\quad \bullet$ $\mathsf{FICS}$, an IOP of proximity for multilinear polynomial evaluation that, like prior work Blaze [EUROCRYPT 2025] achieves linear prover time, but additionally reduces the verifier oracle query complexity to $O(\lambda \log \log n + \log n)$ for codewords of length $n$. $\quad \bullet$ $\mathsf{FACS}$, an accumulation scheme for NP that achieves linear prover time and $O(\lambda)$ oracle queries per step of the accumulation. Both schemes support a large class of linear-time encodable codes, including systematic LDPC codes and tensor codes of linear-time encodable codes. We obtain our results by extending and formalizing the framework of Interactive Oracle Reductions (IORs) introduced by Ben-Sasson et al. [TCC 2019]. In particular, we develop new IORs for "codeswitching" tensor codes (Ron-Zewi and Rothblum [JACM 2024]), and also develop a new notion of knowledge soundness for IORs that allows us to easily compose IORs and to prove the security of our schemes in the non-interactive setting, even if the underlying codes are not known to be decodable in polynomial time.

Secure aggregation enables a server to learn the sum of private inputs of clients, while revealing no additional information beyond the final sum. Recent work, Willow (CRYPTO 2025) achieves one--shot secure aggregation in the single-server model with dynamic client participation. To ensure security under these features, Willow relies on an auxiliary committee to verify the correctness of the aggregation. Although this verification requires no private information---broadening the set of parties eligible to participate in the committee---the committee’s total work scales linearly with the number of clients, which poses a challenge for large-scale deployments. This linear committee cost limitation is also shared by other state-of-the-art single-server secure aggregation protocols, including Flamingo (IEEE S&P 2023) and OPA (CRYPTO 2025). In this paper, we introduce WillowFold, a secure aggregation scheme based on Willow that enables lightweight verification of the aggregation and requires only logarithmic committee cost in the number of clients. Our scheme additionally supports streaming aggregation and reduces per-client server storage to a single ID (4 bytes), rather than storing full contributions as in Willow (1.5 KB), which facilitates distributed execution of the server-side computation. Finally, we close a gap in Willow’s security proof by showing that the zero-knowledge proofs underlying the scheme must be simulation extractable in order to rule out correlated ciphertext attacks. WillowFold employs proof-carrying data (PCD)---a primitive for incremental verification of distributed computations---to achieve a lightweight verification cost. In particular, we present a concretely efficient instantiation of WillowFold using a variant of Spartan+KZH-Fold (CCS 2025) as the underlying PCD scheme. As independent contributions, we show a zero-knowledge variant of Spartan+KZH, which is the SNARK underlying Spartan+KZH-Fold, that uses logarithmic randomness, and we further prove that this variant satisfies the simulation extractability. We implement and evaluate WillowFold, showing that it supports $8$ million clients with proof size $<60$~KB and verification time under one second--a $10^{5}$-fold improvement over Willow.

We introduce Bolt, a new Multilinear Polynomial Commitment Scheme (MLPCS) designed for high-performance SNARKs. Bolt is geared towards SNARKs for large computations, in which prover speed is paramount but one can afford slightly larger proofs. The construction is based on the code-switching paradigm; our core technical contribution is a new "proof-system friendly" error-correcting code with extremely efficient encoding both asymptotically and concretely. A theory-oriented instantiation of Bolt achieves a commitment time of approximately (3+\epsilon)*N field additions plus a Merkle Tree hash computation of size (1+\epsilon)*N field elements, where N is the size of the multilinear polynomial and \epsilon>0 is arbitrarily small. The prior state-of-the-art, Blaze (Brehm et al., Eurocrypt 2025) used 8N additions and a 4N size Merkle hash. Concretely efficient instantiations of Bolt demonstrate that these asymptotic gains translate into substantial real-world speedups. Our benchmarks show that for N=2^{30} over the field GF(2^{32}) Bolt's commitment time is roughly 3-4x faster than Reed-Solomon based schemes, depending on the specific parameterization. In the slower variant, the proof-size is ~2MB. Bolt also offers better commitment time and especially proof size compared to recent linear-time schemes. For example, its commitment time is about 20% faster than Brakedown (Golovnev et al., Crypto 2023) with a 5-15x smaller proof.

Synchronous protocols are a fundamental and widely studied model in distributed computing and cryptography. In this model, protocols proceed in rounds: at the beginning of each round, parties send messages, and all messages are guaranteed to be delivered before the round ends. The standard communication complexity of a synchronous protocol measures the total number of bits transmitted throughout the execution. However, this metric does not accurately reflect the protocol’s actual running time, since it ignores the inherent parallelism of synchronous communication. In particular, multiple parties may transmit simultaneously within the same round, and the duration of a round is determined not by the total communication volume, but by the longest transmission that must occur sequentially. To capture this aspect of synchronous computation, we introduce \emph{communication-depth}, a new complexity measure for synchronous protocols. Informally, communication-depth quantifies the amount of communication that lies on the protocol’s critical path, namely, the number of bits that must be transmitted sequentially and therefore determine the protocol’s execution time. The communication-depth of a protocol is defined as the sum, over all rounds, of the cost of each round. We consider two variants of round-cost capturing different types of parallel communication the network allows. In the \emph{simultaneous-parties} model, the cost of a round is the maximum number of bits any party sends or receives during that round. In the \emph{simultaneous-channels} model, the cost of a round is the maximum number of bits transmitted over any single channel during the round. We demonstrate the usefulness of communication-depth by fully characterizing the asymptotic complexity of multivalued synchronous broadcast. Perhaps surprisingly, while protocols for $\ell$-bit inputs with asymptotic optimal communication $O(\ell n)$ have been known for a long time, current protocols only achieve communication-depth $\Theta(\ell n)$ in the simultaneous-parties model and $\Theta(\ell)$ in the simultaneous-channels model. Our results provide a complete characterization of multivalued broadcast under communication-depth for both variants. On the negative side, we show that when $n - t = O(1)$, any protocol tolerating up to $t$ corrupt parties requires communication-depth $\Omega(\ell n)$ in the simultaneous-parties model and $\Omega(\ell)$ in the simultaneous-channels model. On the positive side, we show that when $n - t = \Theta(n)$, multivalued broadcast can be achieved with communication-depth $\Theta(\ell)$ in the simultaneous-parties model and $\Theta(\ell/n)$ in the simultaneous-channels model.

Fair and free elections are the foundation of democracies and democratic processes. They require voting protocols that guarantee the integrity and verifiability of the result, as well as the private choice of each voter. Currently deployed e-voting protocols rely on traditional hardness assumptions, like the discrete logarithm problem, to provide these security guarantees. They are not post-quantum secure (pq-secure). While first proposals for pq-secure protocols exist, they are limited in the variety of voting scenarios they can support and/or in terms of efficiency. In this work, we therefore propose PQKryvos, an efficient and flexible pq-secure homomorphic e-voting protocol that can be instantiated for a wide variety of election methods and ballot formats. Our construction efficiently combines homomorphic lattice-based commitments with hash-based general-purpose proofs (GPZKPs) to ensure ballot correctness. As a pq-secure instantiation of the Kryvos framework introduced by Huber et al. (CCS 2022), PQKryvos not only provides voter privacy and (public) verifiability of the result, but additionally allows for the stronger privacy notion of public tally-hiding. Public tally-hiding ensures that only the intended election result (such as the full vote count or only the winner) is publicly revealed, while no additional information is leaked. This further improves the privacy for both voters and election candidates. PQKryvos is the first homomorphic pq-secure e-voting protocol to generically support arbitrary ballot formats and the first to provide public tally-hiding. Our implementation and evaluation of PQKryvos demonstrate that it achieves practical performance for diverse election schemes and outperforms the original pre-quantum Kryvos instantiation in some settings. Moreover, we demonstrate that by utilizing GPZKPs, existing pq-secure e-voting protocols can support additional ballot formats, can be enhanced in their tallying phase, and can be extended to publicly tally-hiding protocols.

Secret sharing under expressive access structures and public verifiability have largely been developed in separate lines of work. Generalized secret sharing (GSS) supports arbitrary monotone access structures, but relies on private channels and gives no public evidence that the dealer distributed a consistent sharing. Publicly verifiable secret sharing (PVSS), in contrast, supports public verification over insecure channels, but is fundamentally tailored to threshold policies. We introduce publicly verifiable generalized secret sharing (PVGSS), a primitive that combines arbitrary monotone access structures with non-interactive public verification of both encrypted shares and decrypted reconstruction shares. Our construction encrypts only the leaf shares of an underlying GSS instance and proves, via Schnorr-type NIZK proofs, that all ciphertexts are globally consistent with a single secret. The key technical ingredient is a GSS testing procedure that checks this global consistency from proof responses, without revealing the shares. We instantiate PVGSS from recursive Shamir secret sharing and from linear secret sharing schemes, obtaining verification complexity linear in the number of leaves of the access structure. We formalize correctness, encrypted-share verifiability, share-decryption verifiability, and IND1-secrecy, and prove security in the random oracle model under DDH, knowledge soundness of the proof systems, and privacy of the underlying GSS-on-group sharing. As an application, we show how PVGSS enables publicly accountable secret release in a decentralized exchange protocol.

Verifiable secret sharing (VSS) is a fundamental primitive for secure computation and its round complexity has been well studied. The works of Gennaro et al. [STOC'01] and Fitzi et al. [TCC'06] settled the landscape in the perfect-security setting, showing that for the optimal corruption threshold $t<n/3$, the exact round complexity is three, and for the sub-optimal corruption threshold $t<n/4$ it is two rounds. Similarly, Patra et al. [CRYPTO'09] and Kumaresan et al. [ASIACRYPT'10] settled the landscape in the statistical setting, showing that for $t<n/2$ (resp. $t<n/3$), the exact round complexity is three (resp. two). Current protocols with optimal resilience incur three rounds even when the actual number of corruptions $f$ is sub-optimal. Fix corruption threshold parameters $0\le k \le t$. We ask whether it is possible to obtain a VSS protocol that incurs two rounds when $f\le k$, and three rounds when $k<f\le t$. We show matching feasibility and impossibility results demonstrating that this is possible if and only if $3t+k < n$ for perfect security, and $2t+k < n$ for statistical security.

Topology-hiding computation (THC) enables a set of parties, communicating over an incomplete network, to execute a secure multiparty computation (MPC) protocol for securely computing a function, while also hiding the network topology from within a given class of graphs. Semi-honest THC can be achieved over arbitrary graph classes, facing an arbitrary number of corruptions, from various assumptions implying oblivious transfer (OT). These assumptions are justified by strong lower bounds, indicating that $2$-secure topology-hiding broadcast (THB) over certain diameter-$3$ graph classes requires OT, as well as $1$-secure THC over certain diameter-$2$ graph classes of variable size. While THC from weaker assumptions, such as key agreement (KA), is achievable for $t=1$ over fixed-size graphs, the case of multiple corruptions remains unclear, with no known candidate constructions. Even in the simpler, privacy-free case of THB, tolerating $t>1$ corruptions without assuming OT is only known for "friendship" graphs (which are diameter-$2$ graphs of a certain form): in fact, the latter holds information theoretically and for $t<n$. The state of the art raises two foundational questions: First, considering THC, is OT necessary for protecting against adversaries with multiple points of view in the graph? Second, considering THB, is there a zero-one law for $t>1$, where given a graph class, THB either holds unconditionally or requires OT? In this work we study these questions over graphs of diameter $2$ (in which the lower bounds requiring OT do not hold) and provide THC protocols for various graph classes supporting many corruptions assuming KA. For some of these results we obtain optimal resilience assuming KA: $t<n$ for THB and $t<n/2$ for THC. We also present new lower bounds, showing that in certain graph classes that support information-theoretic THB for $t=1$, KA is necessary for $t=2$.

The secure evaluation of Boolean functions or Secure Boolean Evaluation (SBE) is a fundamental component in this area of research. SBE allows parties to jointly compute Boolean functions without exposing their private inputs. SBE finds applications in privacy-preserving protocols and secure multi-party computations. The existing schemes need at least $(1.5\lambda+5)$-bit strings to garble an AND gate with security parameter $\lambda$, where $\lambda$ is the length of arbitrary bit strings associated with inputs $0$ and $1$. In this manuscript, we discuss how we circumvent the communication cost of non-input gates independent of $\lambda$. We present an efficient and generic two-party protocol (namely $\mathsf{BooleanEval}$) for the secure evaluation of Boolean functions by utilizing a 1-out-of-2 Oblivious Transfer (OT) as a building block. We introduce randomized Bloom filter (namely, $\mathsf{ RBF}_S$) associated with a set $S$ to compute non-input $\mathsf{AND}$ gates. Moreover, $\mathsf{BooleanEval}$ only employs hash evaluations and XOR operations as the core computational step, making it lightweight and fast. Unlike other lightweight state-of-the-art designs of SBE, $\mathsf{BooleanEval}$ avoids the use of additional cryptographic primitives, such as commitment schemes, to reduce the computational overhead.

Succinct zero-knowledge arguments (zk-SNARKs) enable a prover to convince a verifier of the truth of a statement via a succinct, efficiently verifiable proof without revealing any additional information about the witness. A barrier to the practical deployment of zk-SNARKs is their high proving cost. With this motivation, we study server-aided zk-SNARKs, where a client/prover outsources most of its work to a single, untrusted server, while the server learns nothing about the witness, the statement, or even the proof. We formalize this notion and show how to efficiently realize server-aided proving for widely deployed zk-SNARKs such as Nova, Groth16, and Plonk. The key building block underlying our designs is a new primitive, encrypted multi-scalar multiplication (EMSM), that enables private delegation of multi-scalar multiplications (MSMs). We construct an EMSM from variants of the LPN assumption in which the client does $O(1)$ group operations, while the server’s work matches that of the native plaintext MSM. We implement and evaluate our constructions. Compared to local proving, our techniques lower the client's computation by up to ${18{\times}}$ and reduce the proving latency by up to ${8{\times}}$.

Consensus among $n$ parties tolerating up to $t$ Byzantine faults requires $n > 2t$ in synchronous networks and $n > 3t$ in asynchronous networks. The higher resilience achievable in synchrony relies on a known message delay bound $\Delta$, whereas asynchronous protocols make no timing assumptions but must tolerate fewer faults. Prior work addressed this gap only partially. Some protocols achieve responsiveness under synchrony, meaning that their running time adapts to the \emph{actual} network delay, but offer no guarantees under asynchrony, while others guarantee correctness under both network conditions but sacrifice responsiveness. Only recently, Elsheimy, Kamp, Loss, and Nielsen (IACR~2026) showed for binary validated Byzantine agreement (VBA) that if $t_s$, $t_a$, and $t_r$ denote the synchronous, asynchronous, and responsiveness thresholds, respectively, then the conditions $n > 2t_s + t_a$ and $n > t_s + 2t_r$ are necessary and sufficient to simultaneously achieve asynchronous security, synchronous security, and responsiveness. While binary BA (or VBA) can be extended to multi-valued Byzantine agreement (MVBA) via standard reductions, such transformations generally incur blow-up in the communication. Whether these tight resilience conditions can be achieved for MVBA \emph{with optimal communication complexity} remained open. In this work, we resolve this question. For the aforementioned optimal thresholds, we construct an MVBA protocol that is asynchronously secure when $f \le t_a$, synchronously secure when $f \le t_s$, and responsive when $f \le t_r$, where $f$ is the actual number of corruptions. Our construction builds on Dumbo-MVBA~(Lu et al., PODC 2020) and preserves asymptotically optimal efficiency. When $n - 2t_s = \Theta(n)$, our first construction achieves $O(n^2\kappa + n\ell)$ communication for $\ell$-bit inputs and computational security parameter $\kappa$, matching the best known bounds in asynchrony of Lu et al. (PODC 2020) and the best known synchronous bounds of Shrestha et al. (FC 2025). When $n - 2t_s$ is small, we provide an alternative construction with communication $O(n^2\kappa + n\ell)$ in synchrony and $O(\lambda (n^2\kappa + n\ell))$ in asynchrony, where $\lambda$ is a statistical security parameter. Whenever $f \le t_r$, both protocols terminate in expected $O(\delta)$ time, where $\delta$ is the actual network delay; otherwise, the expected running time is $O(\Delta)$.

Threshold signatures, especially ECDSA, enhance key protection by addressing the single-point-of-failure issue. Threshold signing can be divided into offline and online phases, based on whether the message is required. Schemes with low-cost online phases are referred to as ``online-friendly". Another critical aspect of threshold ECDSA for real-world applications is robustness, which guarantees the successful completion of each signing execution whenever a threshold number $t$ of semi-honest participants is met, even in the presence of misbehaving signatories. The state-of-the-art online-friendly threshold ECDSA without robustness was developed by Doerner et al. in S\&P'24, requiring only three rounds. Recent work by Wong et al. in NDSS'23 (WMY\(^+\)23) and NDSS'24 (WMC24) achieves robustness but demands additional communication rounds (7 and 4, respectively) or incurs costly operations in the online phase, such as computations over a homomorphic encryption scheme. This paper presents the first three-round threshold ECDSA scheme with both robustness and an online-friendly design. The online phase of our scheme relies solely on several elliptic-curve group operations, which are 2 to 3 orders of magnitude less computationally intensive than those based on linearly homomorphic encryption schemes. We implement our protocol and conduct a comprehensive comparison with WMY$^+$23 and WMC24. Benchmark results show that the online phase of our scheme is $2.5\times$ faster than that of WMY$^+$23 and hundreds of times faster than that of WMC24. Lastly, we demonstrate that our techniques can be extended to construct an online-friendly and robust three-round threshold BBS+ scheme.

Garbled circuits with one-bit-per-gate communication were recently introduced by Liu et al. (BitGC, Eurocrypt 2025), Meyer et al. (Crypto 2025), and Ishai et al. (Crypto 2025). However, these works focus primarily on the theoretical communication complexity, leaving open questions about practical computational efficiency. In this paper, we present a set of optimizations that substantially improve its practical efficiency. First, we eliminate key barriers to enable SIMD support for BitGC, leading to a substantial speedup in its homomorphic operations. Second, we demonstrate that XOR gates can be garbled without any communication, improving both efficiency and simplicity. Finally, we present a computationally efficient garbling scheme that requires zero communication for XOR gates and only 5 bits per AND gate. When applied to an AES-128 circuit, our fastest garbling scheme generates a garbled circuit of just 4 KB in 2 minutes on a single CPU core.

Dynamic-committee Proactive Secret Sharing (DPSS) has gained increased attention for its ability to dynamically update the shareholder committees and refresh secret shares, even against adversaries that gradually corrupt all nodes. However, existing state-of-the-art asynchronous DPSS protocols suffer from significant $\mathcal{O}(n^3)$ message complexity and $\mathcal{O}(\lambda n^3)$ communication complexity, where $\lambda$ denotes the security parameter and $n$ is the committee size. In this paper, we distinguish optimistic-case and worst-case scenarios based on node behaviors and network conditions, thus reducing the redundant communication overhead of asynchronous DPSS. Under the trusted setup assumption, we achieved an $\mathcal{O}(n^2)$ message complexity in all scenarios. Additionally, our protocol has an $\mathcal{O}(\lambda n^2)$ communication complexity in the optimistic case, where all nodes are honest and the network is synchronous, and $\mathcal{O}(\lambda n^3)$ communication complexity in the worst case. We also propose two strategies to eliminate the strong trusted setup assumptions, and the asymptotic performance still surpasses the state-of-the-art protocols. For committee sizes of 4 to 400, the estimated concrete communication cost of our DPSS is 19--100x (resp., 8--14x) smaller in the optimistic case (resp., worst case) compared to LongLive (USENIX Security '23). Experiments in AWS show that our DPSS achieves a latency of 1.9--8 seconds for committee sizes from 4 to 64. Single-machine benchmarks reveal a (computational) runtime reduction of up to 44\%.

Threshold ECDSA signing has become a standard building block for securing cryptocurrency assets, with the protocol of Doerner, Kondi, Lee, and shelat (DKLs, IEEE S&P 2024) emerging as a leading solution due to its efficiency and widespread industry adoption. In this work, we revisit the DKLs protocol to evaluate its concrete security and implementation trade-offs: * Vector Oblivious Linear Evaluation (VOLE): We identify subtle issues in the underlying OT-based Vector Oblivious Linear Evaluation (VOLE) sub-protocol, showing that original parameter choices must be adjusted to reach intended security levels. To address this, we provide a complete analysis of three VOLE variants offering different trade-offs between bandwidth and round complexity. * Two-Party Signing: We introduce an optimized two-party signing protocol that shifts the majority of computation and communication to a message- and key-independent preprocessing phase. This results in an exceptionally efficient online phase where each party exchanges only 0.2KB, a roughly 600 times reduction in communication compared to the full protocol, without being susceptible to known ``pre-signature'' attacks. Our findings consolidate the security of the protocol while providing significant efficiency improvements for practical deployment and standardization.

Anonymous proofs of account ownership (anonymous PAOs) enable a prover to convince a verifier that the prover owns a valid account at a server without revealing their identity. Importantly, no server-side changes are required - the server does not even learn that such a proof is taking place. This functionality is particularly valuable in sensitive applications such as whistleblowing, or in settings where infrastructural changes at the server are impractical. Anonymous PAOs were first introduced by Wang et al. (IEEE S&P 2019), who realized them in the email setting via secure channel injection (SCI), a technique that requires carefully engineered multi-party computation (MPC) protocols. In this work, we propose YouChoose, a new approach to anonymous PAO that avoids MPC entirely, relying instead on the verifier to selectively forward TLS records. Compared to SCI, YouChoose is simpler, faster, and more adaptable across services. We also provide the first formal security definition for anonymous PAOs, establishing a rigorous framework for analysis and future constructions. Finally, we present a prototype implementation of YouChoose, evaluate it in the context of email and other social media accounts, showing its better performance than SCI with minimal latency overhead in practice.

Multiscalar multiplication (MSM) is a core operation in modern cryptographic systems, commonly used in various applications such as Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (ZK-SNARKs) and Homomorphic Encryption. In elliptic curve–based ZK-SNARK constructions, MSM accounts for up to 80–90\% of the total proof generation time, making its optimization critical to improving overall protocol performance. Despite significant progress in accelerating MSM through algorithmic techniques such as Pippenger’s method, existing implementations remain vulnerable to timing attacks due to irregular scalar representations and conditional operations on zero digits.\\ In this paper, we revisit the original Pippenger’s MSM algorithm, proposing novel modifications that achieve resistance to timing attacks while at the same time increasing its performance by almost 25\%. Our main contribution is a new scalar recoding algorithm that transforms conventional $q$-ary representations containing zero digits into equivalent non-zero representations. This ensures that all scalar digits are processed uniformly, eliminating timing-based side-channel leaks. Building on this recoding technique, we introduce a secure variant of Pippenger’s bucket method, that avoids zero digits. Finally, we demonstrate that employing an endomorphism-based splitting yields shorter digit expansions and further efficiency gains. To the best of our knowledge, this is the first MSM algorithm explicitly designed to mitigate timing attacks within the Pippenger bucket method framework.