RingCT signatures are essential components of Ring Confidential Transaction (RingCT) schemes on blockchain platforms, enabling anonymous transaction spending and significantly impacting the scalability of these schemes. This paper makes two primary contributions: We provide the first thorough analysis of a recently developed Any-out-of-N proof in the discrete logarithm (DLOG) setting and the associated RingCT scheme, introduced by ZGSX23 (S&P '23). The proof conceals the number of the secrets to offer greater anonymity than K-out-of-N proofs and uses an efficient "K-Weight" technique for its construction. However, we identify for the first time several limitations of using Any-out-of-N proofs, such as increased transaction sizes, heightened cryptographic complexities and potential security risks. These limitations prevent them from effectively mitigating the longstanding scalability bottleneck. We then continue to explore the potential of using K-out-of-N proofs to enhance scalability of RingCT schemes. Our primary innovation is a new DLOG-based RingCT signature that integrates a refined "K-Weight"-based K-out-of-N proof and an entirely new tag proof. The latter is the first to efficiently enable the linkability of RingCT signatures derived from the former, effectively resisting double-spending attacks. Finally, we identify and patch a linkability flaw in ZGSX23's signature. We benchmark our scheme against this patched one to show that our scheme achieves a boost in scalability, marking a promising step forward.

Fuzzy PSI is a variant of PSI, which on input a set of points from the receiver and sender respectively, allows the receiver to learn which of the sender's points lie within a threshold distance $\delta$ under a specific distance metric. Baarsen and Pu (EUROCRYPT'24) first proposed efficient fuzzy PSI protocols for general $L_{p}$ distances (where $p \in [1, \infty]$) in $d$-dimensional space, achieving communication complexity linear in the input size, $\delta$, and $2^d d$. However, they leave open the question of whether the prefix technique of Chakraborti et al. (USENIX Security'23) can further reduce the communication complexity of their fuzzy PSI protocols in both low and high dimensions. In this work, we thoroughly explore using the prefix technique to reduce the complexity of fuzzy PSI. First, we propose fuzzy matching protocols for $L_{\infty}$ and $L_p$ distances, where the communication complexity is improved from $O(\delta d)$ to $O(\log\delta\, d)$ for $L_\infty$, and from $O(\delta^p)$ to $O((\log \delta)^d p)$ for $L_p$ distance. By applying our fuzzy matching protocol in conjunction with spatial hashing, we propose fuzzy PSI protocols for low-dimensional space. For high-dimensional space, we present the first fuzzy PSI protocols achieving communication and computation complexity that scales logarithmically in $\delta$ and linearly in dimension $d$ and input set sizes. We implement our fuzzy PSI protocols and compare them with state-of-the-art protocols. Experimental results demonstrate that our protocols achieve superior performance for large $\delta$: for input size $N=2^8$, $d=5$, and $\delta=256$, our protocol requires $10$--$36\times$ less running time and $3$--$4.5\times$ lower communication than existing protocols.

The SPDM (Security Protocol and Data Model) protocol is a standard under development by the DMTF consortium, and supported by major industry players including Broadcom, Cisco, Dell, Google, HP, IBM, Intel, and NVIDIA. SPDM 1.2 is a complex protocol that aims to provide platform security, for example for communicating hardware components or cloud computing scenarios. SPDM is the core security mechanism of PCI Express (PCIe) and Compute Express Link (CXL). In this work, we provide the first holistic, formal analysis of SPDM 1.2: we model the full protocol flow of SPDM considering all of its modes – especially the complex interaction between its different key-exchange modes – in the framework of the Tamarin prover, making our resulting model one of the most complex Tamarin models to date. To our surprise, Tamarin finds a cross-protocol attack that allows a network attacker to completely break authentication of the pre-shared key mode. We implemented our attack on the SPDM reference implementation, and reported the issue to the SPDM developers. DMTF registered our attack as a CVE with CVSS rating 9 (critical). We propose a fix and develop the first formal symbolic proof using the Tamarin prover for the fixed SPDM 1.2 protocol as a whole. The resulting model of the main modes and their interactions is highly complex, and we develop supporting lemmas to enable proving properties in the Tamarin prover, including the absence of all cross-protocol attacks. Our fix has been incorporated into both the reference implementation and the newest version of the standard. Our results highlight the need for a holistic analysis of other internet standards and the importance of providing generalized security guarantees across entire protocols.

Garbled Circuits (GCs) and Fully Homomorphic Encryption (FHE) are state-of-the-art general-purpose primitives allowing a client to securely outsource the storage and processing of sensitive private data to an untrusted third party cloud server. GCs provide data privacy and function privacy while being efficient, but suffer from non-reusability of its translation tables. On the other extreme, FHE enables arbitrary encrypted computation ensuring data-privacy but suffers from huge computation overhead and limited scalability. Here, we explore the following question- Can encrypted computation guaranteeing data privacy be enabled through use of encrypted lookup tables (like GC) that are reusable for practically large circuits? Such a solution will retain the efficiency of GCs (because of encrypted table lookups); and while it cannot achieve unbounded reusability (like FHE, because of the inclination on computation rather than lookups), an interesting question is whether its reusability bound can be made sufficient for practically large circuits. In this work, we propose Symmetric Encrypted Computation (SEC), the first practically efficient and provably secure lookup-based construction that supports reusable evaluations of arbitrary Boolean circuits over symmetrically encrypted data, while ensuring data-privacy guarantees. With a single setup of encrypted look-up tables, SEC supports O(k) re-evaluations of the same circuit of size n (for client controlled k (≥ n)). Such reusability improves upon GC and is asymptotically large enough to scale to practical deployments of realistic circuits; also note that SEC completely bypasses bootstrapping, thereby being more efficient than FHE. This is achieved by relying on purely symmetric-key crypto-primitives by extending and generalizing the functional capabilities of Searchable Symmetric Encryption (SSE), while inheriting its desirable performance benefits. Reusability through SSE without leakage is ensured in SEC by the design choice to treat a generic 2-input Boolean gate as a 3-input encrypted query, with the third input randomizing access patterns across reuse. We provide a concrete construction of SEC and analyze its security with respect to a rigorous leakage profile. We also experimentally validate its practical efficiency. SEC outperforms state-of-the-art FHE schemes (such as Torus FHE) substantially. We further showcase the scalability of SEC for functions with multi-bit inputs via experiments performing encrypted evaluation of the entire AES-128 circuit, as well as the max-pooling layers of AlexNet architecture. For both sets of experiments, SEC outperforms state-of-the-art unaccelerated FHE implementations by 1000× in terms of processing time, while incurring 250× lower storage.

Program obfuscation aims to hide the inner workings of a program while preserving its functionality. In the quantum setting, recent works have obtained obfuscation schemes for specialized classes of quantum circuits. For instance, Bartusek, Brakerski, and Vaikuntanathan (STOC 2024) constructed a quantum state obfuscation scheme, which supports the obfuscation of quantum programs represented as quantum states for pseudo-deterministic quantum programs with classical inputs and outputs in the classical oracle model. In this work, we improve upon existing results by constructing the first quantum state obfuscation scheme for unitary (or approximately unitary) quantum programs supporting quantum inputs and outputs in the classical oracle model. At the core of our obfuscation scheme are two novel ingredients: a functional quantum authentication scheme that allows key holders to learn specific functions of the authenticated quantum state with simulation-based security, and a compiler that represents an arbitrary quantum circuit as a projective linear-plus-measurement quantum program described by a sequence of non-adaptive Clifford gates interleaved with adaptive and compatible measurements.

Goyal and Goyal demonstrated that extractable witness encryption, when combined with smart-contract equipped proof-of-stake blockchains, can yield powerful cryptographic primitives such as one-time programs and pay-to-use programs. However, no standard model construction for extractable witness encryption is known, and instantiations from alternatives like indistinguishability obfuscation are highly inefficient. This paper circumvents the need for extractable witness encryption by combining signature-based witness encryption (Döttling et al.) with witness encryption for KZG commitments (Fleischhacker et al.). Inspired by Goyal et al., we introduce $T+1$-Extractable Witness Encryption for Blockchains ($T+1$-eWEB), a novel primitive that encrypts a secret, making its decryption contingent upon the subsequent block's state. Leveraging $T+1$-eWEBs, we then build a conditional one-time memory, leading to a $T+1$ one-time program ($T+1$-OTP) also conditional on the next block's state.

Threshold symmetric encryption (TSE) [DiSE, CCS 2018], provides a practical decentralized solution for symmetric encryption by distributing the secret-key at all times, thus avoiding a single point of attack or failure. TSE was further enhanced [ATSE, CCS 2021] by an amortization which enables a ``more privileged'' client to encrypt bulk records by interacting only once with the key servers, while decryption must be performed individually for each record, potentially by a ``less privileged'' client. However, a typical enterprise generates data once and queries it several times for various data analysis; i.e., enterprise workloads are often decryption heavy! ATSE does not meet the bar for this setting because of linear interaction / computation (in the number of records to be decrypted) -- our experiments show that ATSE provides a sub-par throughput of a few hundred records/sec. Our work starts with an observation that a large and useful class of analytics queries access some time-windowed sequence of database records (e.g. log entries or user transactions). Can we offer faster decryption for such access patterns, without compromising the benefits of prior schemes? To that end, we build a new TSE scheme that allows for both encryption and decryption with flexible granularity, in that a client's interactions with the key servers is at most logarithmic in the number of records. Our idea is to employ a binary-tree structure, where one interaction is needed to decrypt all ciphertexts in a sub-tree, and thus only log-many for any arbitrary sub-sequence. Our scheme incorporates ideas from binary-tree encryption by Canetti et al. [Eurocrypt 2003] and carefully combines that with Merkle-tree commitments. We show that our scheme satisfies all essential TSE properties, such as correctness, privacy and authenticity for our notion, formalized as hierarchical threshold symmetric-key encryption (HiSE). Our analysis relies on a well-known XDH assumption and a new assumption, that we call $\ell$-masked BDDH, over asymmetric bilinear pairing in the programmable random oracle model. We also show that our new assumption holds in the generic group model. Our extensive implementation shows 10-65$\times$ improvement in latency and throughput over ATSE. HiSE can decrypt over 6K records/sec on server-grade hardware, but the logarithmic overhead in encryption (not decryption) only lets us encrypt up to 3K records/sec (about 4.5x slowdown) and incurs roughly 500 bytes of ciphertext expansion per record -- while reducing this penalty is an important future work, we believe HiSE offers an acceptable practical trade-off in practice.

The development of quantum computing technology poses a serious and credible threat to modern public-key cryptography, which is a pillar of secure communications. Post quantum cryptographic (PQC) algorithms can protect against this threat, but key establishment protocols supporting PQC algorithms pose non-trivial overhead costs. Prior proposals have pointed to the use of strategic traditional/PQC protocol combinations as a means of balancing performance and security, namely as an amortization of PQC overhead. This work provides the first benchmarking of this method within the context of the Messaging Layer Security (MLS) protocol. Comparative metrics include group size, CPU cycles, bytes, and runtime. The results show substantial overhead savings across the board when compared to a simple post-quantum cipher suite use, and marginal increase over traditional cipher suite performance when amortized. At small group sizes such as 1-to-1 channels, the method performs comparably to MLS using a traditional cipher suite. This work shows viability of deploying PQC solutions for constrained settings and and achieving PQC security with efficiency.

Authenticated garbling, introduced by Wang et al., CCS'17, is a leading paradigm for achieving constant-round maliciously-secure 2PC. In this work, we upgrade authenticated garbling to efficiently support tensor gates (introduced in the context of semi-honest garbling by Heath et al., CCS'21) using the one-hot garbling technique. Our maliciously-secure garbled tensor gate computes $\boldsymbol {x}\otimes \boldsymbol{y}$ for $\boldsymbol{x}\in \{0,1\}^n,\boldsymbol{y} \in \{0,1\}^m$ with $O(n+m)\kappa + O(nm)$ bits of communication, where $\kappa$ is the computational security parameter and $n,m$ are logarithmic in $\kappa$. This improves the best prior constant-round maliciously secure approach, which incurs $O(nm)\kappa$ communication. Our protocol is concretely efficient and improves over state-of-the-art for applications including integer multiplication, matrix multiplication, and more. We benchmark the online phase of our protocol and observe a $5.41\times$ improvement in communication and $3.35\times$ improvement in wall clock time when computing a $128\times 128$ bit tensor product.

Dittmer, Ishai and Ostrovsky (ITC'21) proposed {\em line-point zero-knowledge proof} (LPZK), a simple ``commit-and-prove'' system, motivated by practical protocols for compressing correlated pseudorandomness used in secure multiparty computation (MPC). Typically, LPZK admits concretely efficient ZK protocols with a streaming, linear time prover, {\em but a linear size proof}. A natural question raised in the context is how far can we go in minimizing the proof size, while maintaining the prover efficiency. Though a recent work by Lin, Xing and Yao (ASIACRYPT'24) gives an interactive LPZK with a sublinear proof size $O(n+d^2\log{|\mathcal{C}|})$, it is still far from being {\em succinct}, where $n,d,|\mathcal{C}|$ are referred to as input size, circuit depth, and circuit size, respectively. In this work, we beat the proof size barrier and propose {\em succinct LPZK arguments}, by distilling techniques from orthogonal studies on homomorphic secret sharing and succinct garbling. Specifically, under variants of group/lattice-based assumptions, we show the followings: i) There exist succinct LPZK arguments with common reference string (CRS) size $O(n^{2/3})$, proof size $O(n^{2/3})$, prover time $O(n^{4/3}+|\mathcal{C}|)$, verification time $O(n+|\mathcal{C}|)$, and negligible soundness error, where both the prover and the verifier executions and be run in a streaming fashion. ii) The above proof size can be further optimized to $O(1)$, at the cost of a larger CRS size $O(n)$, and prover time increased to $O(n^{2}+|\mathcal{C}|)$. In general, our succinct LPZK arguments pave a new way for building designated-verifier zero-knowledge succinct non-interactive arguments of knowledge (dv-zkSNARKs), and new interesting features (e.g., streaming, constant sized proof with CRS size not proportional to the circuit size) are obtained for the first time along the way.

The majority of modern e2e private applications face scalability issues that limit their functionality, broader adoption, and overall user experience. Some of them organize private groups as a set of peer-to-peer chats, which leads to an overall quadratic complexity in the size of group communication and a linear time complexity in the number of members for encryption. Others apply more scalable group key establishment constructions (such as ART), but at the same time, they do not support verifiable and concurrent updates. In this paper, we introduce the 0-ART protocol, which aims to address the aforementioned issues by (1) verifiable group operations; (2) a causal tree construction allowing for multiple concurrent updates and efficient member removal; (3) anonymous credentials, making privacy in the group available while keeping operations authentic. We implemented the 0-ART framework and applied it to a decentralized collaborative work application. According to our benchmark, executing the most complex operation (performing the provable $\mathsf{AddMember}$ operation in a group of size $2^{20}$) takes 1.57 seconds on the user's device and $24$Kb of proof size.

As anonymous social networks continue to grow in popularity, they raise serious challenges around abuse, misinformation, and harmful behavior. While traditional de-anonymization techniques can address misuse, they often come at the cost of user privacy. Protecting honest users' privacy while keeping malicious ones accountable remains a complex challenge. A promising alternative is conditional deanonymization, where anonymity is lifted only when abuse is collectively reported and verified by an authority. In this work, we present a new cryptographic framework for conditional de-anonymization that preserves user anonymity unless a threshold number of validated abuse reports is reached. Our design leverages threshold cryptography to ensure that de-anonymization can only be triggered under well-defined, collectively enforced conditions—resisting false reports, misuse, and collusion. We formalize the model and provide a generic construction from standard cryptographic primitives, proving strong security guarantees even in the presence of adversarial authorities or malicious users. To illustrate its viability, we also propose a concrete instantiation based on lattice-based assumptions, making it a compelling candidate for post-quantum settings.

General-purpose probabilistic proof systems operate on programs expressed as systems of arithmetic constraints—an unfriendly representation. There are two broad approaches in the literature to turning friendlier, high-level programs into constraints suitable for proof systems: direct translation and CPU emulation. Direct translators compile a program into highly optimized constraints; unfortunately, this process requires expressing all possible paths through the program, which results in compile times that scale with the program’s runtime rather than its size. In addition, the prover must pay the cost of every possible program path, even those untaken by a given input. In contrast, CPU emulators don’t compile programs to constraints; instead, they “execute” those programs, expressed as CPU instructions, on a CPU emulator that is itself expressed as constraints. As a result, this approach can’t perform powerful, program-specific op- timizations, and may require thousands of constraints where direct translation could use a clever handful. Worse, CPU emulators inherit an impractically expensive program state representation from the CPUs they emulate. This paper presents a compiler and proof system, CoBBl, that combines the benefits of CPU emulation and direct translation: it takes advantage of program-specific optimizations, but doesn’t pay for an unnecessary state representation or unexecuted computation. COBBL outper- forms CirC, a state-of-the-art direct translator, by $1–30\times$ on compile time and $26–350\times$ on prover time, and outperforms Jolt, a state-of-the-art CPU emulator, on prover time by $1.1– 1.8\times$ on Jolt-friendly benchmarks, and up to $100\times$ on other benchmarks.

Privacy Pass is an anonymous authentication protocol which was initially designed by Davidson et al. (PETS’18) to reduce the number of CAPTCHAs that TOR users must solve. It issues single-use authentication tokens with anonymous and unlinkable redemption guarantees. The issuer and verifier of the protocol share a symmetric key, and tokens are privately verifiable. The protocol has sparked interest from both academia and industry, which led to an Internet Engineering Task Force (IETF) standard. While Davidson et al. formally analyzed the original protocol, the IETF standard introduces several changes to their protocol. Thus, the standardized version’s formal security remains unexamined. We fill this gap by analyzing the IETF standard’s privately verifiable Privacy Pass protocol. In particular, there are two main discrepancies between the analyzed and standardized version: First, the IETF version introduces a redemption context, that can be used for blindly embedding a validity period into the Privacy Pass tokens. We show that this variant has significant differences to public metadata extension that has been proposed for the same purpose in the literature. Redemption context offers better privacy and security than public metadata. We capture both stronger guarantees through game-based security definitions and show that the currently considered one-more unforgeability notion for Privacy Pass is insufficient when a redemption context is used. Thus, we propose a new property, targeted context unforgeability, and prove its incomparability to one-more unforgeability. Second, Davidson et al. focused on a concrete Diffie-Hellman based construction, whereas the IETF version is built generically from a verifiable oblivious pseudorandom function (VOPRF). Further, the analyzed protocol omitted the full redemption phase needed to prevent double-spending. We prove that the generic IETF construction satisfies the desired security and privacy guarantees covering the full life-cycle of tokens. Our analysis relies on natural security properties of VOPRFs, providing compatibility with any secure VOPRF instantiation. This enables crypto agility, e.g., allowing to switch to efficient quantum-safe VOPRFs when they become available.

We present the first complete adaptively secure asynchronous MPC protocol for the YOSO (You Speak Only Once) setting. In contrast to many previous MPC constructions in the YOSO model, we provide a full stack implementation that does MPC, role assignment and total order broadcast. Therefore, our construction is also the first to provide adaptively secure asynchronous total order broadcast and MPC that is sub-quadratic in the number of parties and does not require threshold fully homomorphic encryption. Instead, our protocols rely on threshold additively homomorphic Paillier encryption. Our total-order broadcast protocol is optimal in the message length, implying that the amortized complexity of a secure multiplication is linear in the number of parties.

Card-based cryptography is a research area for realizing cryptographic functionality, such as secure multiparty computation and zero-knowledge proofs, by using a deck of physical cards and/or other non-electrical tools. Motivated by zero-knowledge proofs for solutions in pencil puzzles, there is a direction of recent studies on card-based protocols to verify connectivity of a set of cells or edges on lattice-shaped boards. In this paper, we generalize the problem to counting connected components of a subset of the vertex set on any graph, and propose a card-based protocol for the problem.

Differential privacy (DP) is a fundamental technique used in machine learning (ML) training for protecting the privacy of sensitive individual user data. In the past few years, a new approach for combining prior-based Local Differential Privacy (LDP) mechanisms with a relaxed DP criterion, known as Label DP, has shown great promise in increasing the utility of the final trained model without compromising on the DP privacy budget. In this work, we identify a crucial privacy gap in the current implementations of these prior-based LDP mechanisms, namely the leakage of sensitive priors. We address the challenge of implementing such LDP mechanisms without leaking any information about the priors while preserving the efficiency and accuracy of the current insecure implementations. To that end, we design simple and efficient secure two-party computation (2PC) protocols for addressing this challenge, implement them, and perform end-to-end testing on standard datasets such as MNIST, CIFAR-10. Our empirical results indicate that the added security benefit essentially comes almost for free in the sense that the gap between the current insecure implementations and our proposed secure version, in terms of run-time overhead and accuracy degradation, is minimal. E.g., for CIFAR-10, with strong DP privacy parameter, the additional runtime due to 2PC is $\approx 3.9\%$ over WAN with $0.4\%$ decrease in accuracy over an insecure (non-2PC) approach.

Zero-knowledge succinct arguments of knowledge (zkSNARK) provide short privacy-preserving proofs for general NP problems. Public verifiability of zkSNARK protocols is a desirable property, where the proof can be verified by anyone once generated. Designated-verifier zero-knowledge is useful when it is necessary that only one or a few individuals should have access to the verification result. All zkSNARK schemes are either fully publicly verifiable or can be verified by a designated verifier with a secret verification key. In this work, we propose a new notion of a hybrid verification mechanism. Here, the prover generates a proof that can be verified by a designated verifier. For this proof, the designated verifier can generate auxiliary information with its secret key. The combination of this proof and the auxiliary information allows any public verifier to verify the proof without any other information. We also introduce necessary security notions and mechanisms to identify a cheating designated verifier or the prover. Our hybrid verification zkSNARK construction is based on module lattices and adapts the zkSNARK construction by Ishai et al. (CCS 2021). In this construction, the designated verifier is required only once after proof generation to create the publicly verifiable proof. Our construction achieves a small constant-size proof and fast verification time, which is linear in the statement size.

The proposed $\mathsf{SL\text{-}DNSSEC}$ protocol (AsiaCCS'25) uses a quantum-safe KEM and a MAC to perform signature-less $\mathsf{(SL)}$ DNSSEC validations in a single UDP query / response style. In this paper, we give a formal analysis of $\mathsf{SL\text{-}DNSSEC}$ in the reductionist model.

We extend the concept of access control for functional encryption, introduced by Abdalla et al. (ASIACRYPT 2020), to function-revealing encryption (Joy and Passelègue, SCN 2018). Here “access control” means that function evaluation is only possible when a specified access policy is met. Specifically, we introduce access-controlled inner product function-revealing encryption (AC-IPFRE) and give two applications. On the theoretical side, we use AC-IPFRE to show that function-hiding inner-product functional encryption (FH-IPFE), introduced by Bishop et al. (ASIACRYPT 2015), is equivalent to IPFRE. To show this, we in particular generically construct AC-IPFRE from IPFRE for the “non-zero inner-product” (NZIP) access policy. This result uses an effective version of Lagrange’s Four Square Theorem. One consequence of this result is that lower bounds by Ünal (EUROCRYPT 2020) suggest that, as for FH-IPFE, bilinear pairings will be needed to build IPFRE. On the practical side, we build an outsourced approximate nearest-neighbor (ANN) search protocol and mitigate its leakage via AC-IPFRE. For this, we construct a practical AC-IPFRE scheme in the generic bilinear group model for a specific access policy for ANN search. To this end, we show that techniques of Wee (TCC 2020) implicitly give the most practical FH-IPFE scheme to date. We implement the resulting outsourced ANN search protocol and report on its performance. Of independent interest, we show AC-IPFRE for NZIP implies attribute-hiding small-universe AC-IPFRE for arbitrary access policies. Previous work on access control for FE did not achieve attribute hiding. Overall, our results demonstrate that AC-IPFRE is of both theoretical and practical interest and set the stage for future work in the area.

Blind signatures have become a cornerstone for privacy-sensitive applications such as digital cash, anonymous credentials, and electronic voting. The elliptic curve variant of the Digital Signature Algorithm (ECDSA) is widely adopted due to its efficiency in resource-constrained environments, such as mobile devices and blockchain systems. Building blind ECDSA is hence a natural goal. One presents the first such construction relying solely on the ECDSA assumption. Despite the inherent complexities in integrating blindness with ECDSA, we design a protocol that ensures both unforgeability and blindness without introducing new computational assumptions and ensuring concurrent security. It involves zero-knowledge proofs based on the MPC-in-the-head paradigm for complex statements combining relations on encrypted elliptic curve points, their coordinates, and discrete logarithms.

The reliable broadcast protocol with the best communication complexity for long messages to date is the MiniCast protocol of Locher & Shoup (2024). To reliably broadcast a message m to n parties, MiniCast has communication complexity ~ 1.5|m|n when the size |m| of m is large. However, the round complexity of MiniCast is 4, which is worse than the 3 rounds of the classical protocol of Bracha. We give a new reliable broadcast protocol whose communication complexity is essentially the same as that of MiniCast, but whose round complexity is just 3. For large |m|, the communication complexity of our new protocol is essentially optimal (for 3-round protocols with sufficiently well-balanced communication). Like MiniCast, our new protocol does not rely on any cryptography other than hash functions. We also give two new 2-round protocols that rely on signatures. The communication complexity of the first protocol is also ~ 1.5|m| n, unless the sender provably misbehaves, in which case its communication complexity may degrade to at most ~ 2|m|n. The communication complexity of the second protocol is ~ 1.5|m|n, even in the worst case, but (unlike our other protocols) the communication is unbalanced.

Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zkSNARKs) lead to proofs that can be succinctly verified but require huge computational resources to generate. Prior systems outsource proof generation either through public delegation, which reveals the witness to the third party, or, more preferably, private delegation that keeps the witness hidden using multiparty computation (MPC). However, current private delegation schemes struggle with scalability and efficiency due to MPC inefficiencies, poor resource utilization, and suboptimal design of zkSNARK protocols. In this paper, we introduce DFS, a new zkSNARK that is delegation-friendly for both public and private scenarios. Prior work focused on optimizing the MPC protocols for existing zkSNARKs, while DFS uses co-design between MPC and zkSNARK so that the protocol is efficient for both distributed computing and MPC. In particular, DFS achieves linear prover time and logarithmic verification cost in the non-delegated setting. For private delegation, DFS introduces a scheme with zero communication overhead in MPC and achieves malicious security for free, which results in logarithmic overall communication; while prior work required linear communication. Our evaluation shows that DFS is as efficient as state-of-the-art zkSNARKs in public delegation; when used for private delegation, it scales better than previous work. In particular, for $2^{24}$ constraints, the total communication of DFS is less than $500$KB, while prior work incurs $300$GB, which is linear to the circuit size. Additionally, we identify and address a security flaw in prior work, EOS (USENIX'23).

Mental Poker enables two players to play card games at a distance without having a physical deck of cards at hand, as long as they have reliable trapdoor permutations or access to Oblivious Transfer (OT). OT itself can be stored and extended using just a one-way function. We examine whether Mental Poker can be extended from initial hands of ordinary physical poker. On the theoretical side, this work establishes OT amplification/extraction as a cryptographic primitive using asymmetrically-viewed fully-randomizing permutations. On the pragmatic, it is naturally related to ``card cryptography'' although in a very restricted sense: 52-card deck protocols using fully scrambling shuffles. While secret-key exchange protocols make strong use of full shuffles, full shuffles are avoided in 2PC/AND/Solitaire card settings because of detrimental over-randomization. Within those domains, this work explains decades-old impossibility conjectures in certain circumstances. More positively, we provide several practical and information-theoretically secure ways to establish base OTs from 5-Card Draw over ordinary decks at rates sufficient to establish a foothold for indefinite Mental Poker extension in just an afternoon of play.

We propose Pool: a conceptually simple post-quantum (PQ) oblivious pseudorandom function (OPRF) protocol, that is round-optimal (with input-independent preprocessing), practically efficient, and has security based on the well-understood hardness of the learning with rounding (LWR) problem. Specifically, our design permits oblivious computation of the LWR-based pseudorandom function $F_{\mathsf{sk}}(x) = \lceil H(x)^{\top} \cdot \mathsf{sk} \rfloor_{q,p}$, for random oracle $H: \{0,1\}^* \mapsto \mathbb{Z}_q^n$ and uniformly chosen $\mathsf{sk} \in \{0,1\}^n$. For 128-bits of semi-honest security, the Pool OPRF has an online communication cost of 11.9~kB, and a computational runtime of less than 2~ms on a single thread (via an open-source software implementation). This is more efficient (in either online communication cost or runtime) than constructions from well-known PQ PRFs, and is competitive even with constructions that only conjecture PQ security on lesser-known assumptions. As a result, our design gives high-performance, post-quantum variants of established OPRF applications in multi-party computation and private set operation protocols.

A Private Simultaneous Messages (PSM) protocol is a secure multiparty computation protocol with a minimal interaction pattern, which allows input parties sharing common randomness to securely reveal the output of a function by sending messages only once to an external party. Since existing PSM protocols for arbitrary functions have exponentially large communication complexity in the number $n$ of parties, it is important to explore efficient protocols by focusing on special functions of practical use. In this paper, we study the communication efficiency of PSM protocols for symmetric functions, which provide many useful functionalities for real-world applications. We present a new $n$-party PSM protocol for symmetric functions with communication complexity $n^{2d/3+O(1)}$, where $d$ is the size of the input domain of each party. Our protocol improves the currently best known communication complexity of $n^{d+O(1)}$. As applications to other related models, we show that our novel protocol implies improved communication complexity of ad-hoc PSM, where only a subset of parties actually send messages, and also leads to a more communication-efficient robust PSM protocol, which is secure against collusion of the external party and input parties. The extension to ad-hoc PSM is not a straightforward application of the previous transformation but includes an optimization technique based on the symmetry of functions.

In this work, we investigate whether the cost of two-party ECDSA signing can be brought within the realm of plain ECDSA signing. We answer the question in the affirmative for the case of communication complexity, by means of a new signing protocol. Our protocol consumes bandwidth linear in the security parameter, and hence the size of an ECDSA signature. Our scheme makes only blackbox use of generic tools---Oblivious Transfer during key generation, and any Pseudorandom Function when signing. While computation complexity is not asymptotically optimal, benchmarks of our protocol confirm that concrete costs are the lowest known for ECDSA signing. Our protocol is therefore the most concretely efficient in the literature on all fronts: bandwidth, computation, and rounds. On a technical level, our protocol is enabled by a novel Pseudorandom Correlation Function (PCF) for the Vector Oblivious Linear Evaluation correlation over a large ring. The PCF relies on one-way functions alone, and may be of independent interest. Our scheme supports standard extensions, such as pre-signing, and including backup servers for key shares in a $(2,n)$ configuration.

We propose Ilyazh-Web3E2E, a post-quantum hybrid messaging protocol combining classical and PQ-secure KEMs with forward secrecy and robust rekeying. The design augments the Double Ratchet model with hybrid key encapsulation (X25519 + ML-KEM), digital authentication (Ed25519 + ML-DSA), and re-encapsulation-based ratcheting for long-lived Web3 identity protection. The protocol emphasizes forward secrecy, post-compromise security, and decentralized identities. We sketch IND-CCA and AKE security arguments, present a concrete wire format, and provide comparisons with PQXDH and PQ3.

Function Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: $O(\sqrt{N})$ key sizes (with $N$, the function domain size) and/or exponential factors in the key size. We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with $O(\sqrt[3]{N})$ key size. Our benchmark highlights key sizes up to $10\times$ smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions.

Homomorphic secret sharing (HSS) is a powerful cryptographic primitive that enables efficient, low-communication secure computation without the use of fully homomorphic encryption. Public-key HSS is a well-known variant that supports inputs from multiple parties, but all parties must agree on a joint public key before any party can encode their inputs, requiring extra rounds of communication in applications. Recently, Couteau et al. (EUROCRYPT 2025) constructed multi-key HSS (MKHSS)—a new primitive which allows parties to encode their inputs under independent keys—under the DCR assumption. MKHSS assumes only a reusable common reference string, without the need for prior interactions between parties or a public-key infrastructure. In this paper, we construct and implement the first concretely-efficient MKHSS scheme under the same assumptions used by Couteau et al. Using an algorithmic insight that reduces the largest modulus in Couteau et al. from $N^4$ to $N^2$, our optimized implementation can homomorphically multiply inputs in 5.0 milliseconds—while an implementation of Couteau et al. requires 224.6 milliseconds—thereby achieving a $45\times$ speedup. A powerful application of MKHSS is to realize attribute-based non-interactive key exchange (ANIKE), which generalizes password-authenticated key exchange (PAKE) to arbitrary attribute policies. ANIKE is currently only known from MKHSS and in this paper we show the first practical instantiation of ANIKE for two concrete predicate types with applications to geolocation-based key exchange and fuzzy PAKE. We use our implementation to evaluate the first concretely-efficient ANIKE schemes for a range of practically useful policies. Using our implementation, two parties can perform a geolocation-based key exchange in under one second and a fuzzy PAKE on an 8-word passphrase in a few seconds for realistic parameters, on a single core, achieving a roughly $30 \times$ speedup over Couteau et al. for both applications.

In anonymous token protocols, clients obtain access tokens by proving eligibility for the usage of a resource and later get access to the resource by redeeming the token. The server verifying eligibility and providing the resource cannot link the token issuance to its redemption. To prevent ineligible clients from accessing resources, it is crucial to prevent the transfer or sale of tokens. Durak et al. (CCS'24) propose binding tokens to valuable insurance secrets, which must be known to redeem the tokens. The value of the insurance secret deters the vendor from transferring the secret to the token buyer, who cannot redeem the token without the secret. However, the authors do not consider scenarios, where the token vendor assists the buyer during token redemption. Their construction, therefore, falls short to guarantee non-transferability when facing a vendor-aided token redemption. We address this gap by introducing the concept of anonymous tokens with betrayability. Our notion ensures that a token buyer, that is able to redeem a bought token, either knows the insurance secret or is able to betray the vendor in a vendor-aided redemption. The betrayal allows the buyer to steal the insurance secret without being detected. This way, we make the support in the token redemption equivalent to a transfer of the insurance secret and, hence, inherit the transfer deterrence of the insurance secret even when considering a vendor-aided token redemption. We formalize our new security notion, present a protocol for anonymous tokens with betrayability, prove its security, and provide an implementation and experimental evaluation.

Despite active research on secret-sharing schemes for arbitrary access structures for more than 35 years, we do not understand their share size $-$ the best known upper bound for an arbitrary n-party access structure is $2^{O(n)}$ while the best known lower bound is $\Omega(n/\log(n))$. Consistent with our knowledge, the share size can be anywhere between these bounds. To better understand this question, one can study specific families of secret-sharing schemes. For example, linear secret-sharing schemes, in which the sharing and reconstruction are computed by linear mappings, have been studied in many papers, e.g., it is known that they require shares of size at least $2^{0.5n}$. Secret-sharing schemes in which the sharing and/or reconstruction are computed by low-degree polynomials have been recently studied by Paskin-Cherniavsky and Radune [ITC 2020] and by Beimel, Othman, and Peter [CRYPTO 2021]. It was shown that secret-sharing schemes with sharing and reconstruction computed by polynomials of degree 2 are more efficient than linear schemes (i.e., schemes in which the sharing and reconstruction are computed by polynomials of degree one). Prior to our work, it was not known if using polynomials of higher degree can reduce the share size. We show that this is indeed the case, i.e., we construct secret-sharing schemes with reconstruction by degree-$d$ polynomials, where as the reconstruction degree $d$ increases, the share size for arbitrary access structures decreases. As a step in our construction, we construct conditional disclosure of secrets (CDS) protocols. For example, we construct 2-server CDS protocols for functions $f : [N ] \times [N ] \to \{0, 1\}$ with reconstruction computed by degree-d polynomials with message size $N^{O(\log \log d/ \log d)}$. Combining our results with a lower bound of Beimel et al. [CRYPTO 2021], we show that increasing the degree of the reconstruction function in CDS protocols provably reduces the message size. To construct our schemes, we define sparse matching vectors, show constructions of such vectors, and design CDS protocols and secret-sharing schemes with degree-$d$ reconstruction from sparse matching vectors.

We propose CA-MCPQ, a context-aware post-quantum-secure extension of the Model Context Protocol (MCP). Unlike standard MCP, which leaves authentication, encryption, and authorization optional or implementation-specific, CA-MCPQ elevates them to mandatory protocol-level mechanisms. The design incorporates post-quantum mutual authentication, KEM-derived session keys, and authenticated sequencing to ensure session integrity and prevent replay. Role-based access control is enforced, while token-based authentication is eliminated entirely. AI dynamically infers the required security tier from contextual information and negotiates compatible PQC algorithms; each response returns a reliability score that quantifies alignment with the requested security level. This architecture addresses critical vulnerabilities of MCP—including token misuse, session hijacking, impersonation, and quantum attack—while preserving interoperability. Notably, our evaluation shows that the cryptographic and transport overheads are negligible compared to model computation, confirming that strong post-quantum assurances can be achieved without degrading system performance. Overall, CA-MCPQ provides a practical path toward secure-by-design AI agent ecosystems and lays the groundwork for future extensions such as agent–agent secure coordination.

Proving the validity of ballots is a central element of verifiable elections. Such proofs can however create challenges when one desires to make a protocol receipt-free. We explore the challenges raised by validity proofs in the context of protocols where threshold receipt-freeness is obtained by secret sharing an encryption of a vote between multiple authorities. In such contexts, previous solutions verified the validity of votes by decrypting them after passing them through a mix-net. This approach however creates subtle privacy risks, especially when invalid votes leak structural patterns that threaten receipt-freeness. We propose a different approach of threshold receipt-free voting in which authorities re-randomize ballot shares then jointly compute a ZK proof of ballot validity before letting the ballots enter a (possibly homomorphic) tallying phase. Our approach keeps the voter computational costs limited while offering verifiability and improving the ballot privacy of previous solutions. We present two protocols that enable a group of servers to verify and publicly prove that encrypted votes satisfy some validity properties: Minimix, which preserves prior voter-side behavior with minimal overhead, and Homorand, which requires voters to submit auxiliary data to facilitate validation over large vote domains. We show how to use our two protocols within a threshold receipt-free voting framework. We provide formal security proofs and efficiency analyses to illustrate trade-offs in our designs.

Threshold Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data, while distributing the decryption capability across multiple parties. A primary application of interest is low-communication multi-party computation (MPC), which benefits from a fast and secure threshold FHE decryption protocol. Several works have addressed this problem, but all existing solutions rely on "noise flooding" for security. This incurs significant overhead and necessitates large parameters in practice, making it unsuitable for many real-world deployments. Some constructions have somewhat better efficiency, but at the cost of weaker, non-simulation-based security definitions, which limits their usability and composability. In this work, we propose a novel threshold FHE decryption protocol that avoids "noise flooding" altogether, and provides simulation-based security. Rather than masking the underlying ciphertext noise, our technique securely removes it via an efficient MPC rounding procedure. The cost of this MPC is mitigated by an offline/online design that preprocesses special gates for secure comparisons in the offline phase, and has low communication and computation in the online phase. This approach is of independent interest, and should also benefit other MPC protocols (e.g., secure machine learning) that make heavy use of non-linear comparison operations. We prove our protocol secure in the Universal Composability (UC) framework, and it can be generally instantiated for a variety of adversary models (e.g., security-with-abort against a dishonest majority, or guaranteed output delivery with honest majority). Compared to the state of the art, our protocol offers significant gains both in the adversary model (i.e., dishonest vs. honest majority) and practical performance: empirically, our online phase obtains approximately 20,000$\times$ better throughput, and up to a 37$\times$ improvement in latency.

Efficient Verifiable Private Information Retrieval (vPIR) protocols, and more generally Verifiable Linearly Homomorphic Encryption (vLHE), suffer from high client storage. VeriSimplePIR (USENIX Security 2024), the state-of-the-art vPIR protocol, requires clients to persistently maintain over 1 GiB of local storage to privately access an 8 GiB remote database. We present a new vPIR protocol that reduces the client state by orders of magnitude while preserving online latency. In our protocol, clients only need to store 512 KiB for an 8 GiB database, achieving a 2000× improvement. Our vPIR protocol is built over our new vLHE scheme. Unlike VeriSimplePIR, our scheme doesn’t use random oracles and relies only on standard lattice assumptions - (R)LWE and SIS. These improvements come at a 2.5× cost in server throughput over VeriSimplePIR. Despite this throughput overhead, we achieve a comparable online latency to VeriSimplePIR by implementing several optimizations including query-level preprocessing. We also introduce the notion of covert vPIR (cvPIR), where stateful clients enjoy full vPIR security, while even stateless clients benefit from covert security against a malicious server.

We present DualMatrix, a zkSNARK solution for large-scale matrix multiplication. Classical zkSNARK protocols typically underperform in data analytic contexts, hampered by the large size of datasets and the superlinear nature of matrix multiplication. DualMatrix excels in its scalability. The prover time of DualMatrix scales linearly with respect to the number of non-zero elements in the input matrices. For $n \times n$ matrix multiplication with $N$ non-zero elements across three input matrices, DualMatrix employs a structured reference string (SRS) of size $O(n)$, and achieves RAM usage of $O(N+n)$, transcript size of $O(\log n)$, prover time of $O(N+n)$, and verifier time of $O(\log n)$. The prover time, notably at $O(N+n)$ and surpassing all existing protocols, includes $O(N+n)$ field multiplications and $O(n)$ exponentiations and pairings within bilinear groups. These efficiencies make DualMatrix effective for linear algebra on large matrices common in real-world applications. We evaluated DualMatrix with $2^{15} \times 2^{15}$ input matrices each containing $1G$ non-zero integers, which necessitate $32T$ integer multiplications in naive matrix multiplication. DualMatrix recorded prover and verifier times of $150.84$s and $0.56$s, respectively. When applied to $1M \times 1M$ sparse matrices each containing $1G$ non-zero integers, it demonstrated prover and verifier times of $1,384.45$s and $0.67$s. Our approach outperforms current zkSNARK solutions by successfully handling the large matrix multiplication task in experiment. We extend matrix operations from field matrices to group matrices, formalizing group matrix algebra. This mathematical advancement brings notable symmetries beneficial for high-dimensional elliptic curve cryptography. By leveraging the bilinear properties of our group matrix algebra in the context of the two-tier commitment scheme, DualMatrix achieves efficiency gains over previous matrix multiplication arguments. To accomplish this, we extend and enhance Bulletproofs to construct an inner product argument featuring a transparent setup and logarithmic verifier time.

This paper introduces the first multilinear polynomial commitment scheme (PCS) over Galois rings achieving $\bigO{\log^2 n}$ verification cost. It achieves $\bigO{n\log n}$ committing time and $\bigO{n}$ evaluation opening prover time. This PCS can be used to construct zero-knowledge proofs for arithmetic circuits over Galois rings, facilitating verifiable computation in applications requiring proofs of polynomial ring operations (e.g., verifiable fully homomorphic encryption). First we construct random foldable linear codes over Galois rings with sufficient code distance and present a distance preservation theorem over Galois rings. Second we extend the $\textsf{Basefold}$ commitment (Zeilberger et al., Crypto 2024) to multilinear polynomials over Galois rings. Our approach reduces proof size and verifier time from $\bigO{\sqrt{n}}$ to $\bigO{\log^2 n}$ compared to Wei et al., PKC 2025. Furthermore, we give a batched multipoint openning protocol for evaluation phase that collapses the proof size and verifier time of $N$ polynomials at $M$ points from $\bigO{NM \log^2 n}$ to $\bigO{\log^2 n}$, prover time from $\bigO{NMn}$ to $\bigO{n}$, further enhancing efficiency.

Distributed Point Functions (DPFs) enable sharing secret point functions across multiple parties, supporting privacy-preserving technologies such as Private Information Retrieval, and anonymous communications. While 2-party PRG-based schemes with logarithmic key sizes have been known for a decade, extending these solutions to multi-party settings has proven challenging. In particular, PRG-based multi-party DPFs have historically struggled with practicality due to key sizes growing exponentially with the number of parties and the field size. Our work addresses this efficiency bottleneck by optimizing the PRG-based multi-party DPF scheme of Boyle et al. (EUROCRYPT'15). By leveraging the honest-majority assumption, we eliminate the exponential factor present in this scheme. Our construction is the first PRG-based multi-party DPF scheme with practical key sizes, and provides key up to $3\times$ smaller than the best known multi-party DPF. This work demonstrates that with careful optimization, PRG-based multi-party DPFs can achieve practical performances, and even obtain top performances.

Keccak, the hash function at the core of the Ethereum ecosystem, is computationally expensive to reason about in SNARK circuits, creating a critical bottleneck in the ability of the ZK ecosystem to reason about blockchain state. The recent state-of-the-art in proving Keccak permutations relies on proof systems that can perform lookup arguments, which—while exhibiting better performance than directly proving the hash operations in circuit—still typically require tens of thousands of constraints to prove a single keccak-f permutation. This paper introduces a new method, termed keccacheck, which builds upon sum-check with influence from GKR to create circuits that can batch-verify Keccak permutations with fewer than 4000 constraints per instance. Keccacheck achieves this by exploiting the logarithmic scaling of recursive verification of the sum-check protocol, reducing the computational cost of verifying large enough batches to be only slightly higher than evaluating the multilinear extension of the input and output states. Its performance becomes competitive for a batch containing 16 permutations and offers more than a 10x cost reduction for batches of 512 or more permutations. This approach enables new levels of efficiency for the ZK ecosystem, providing the performant storage proofs that are essential to light clients, cross-chain bridges, privacy-focused protocols, and roll-ups.

Many foundational results in the literature of consensus follow the Dolev-Yao model (FOCS '81), which treats digital signatures as ideal objects with perfect correctness and unforgeability. However, no work has yet formalized an ideal signature scheme that is both suitable for this methodology and possible to instantiate, or a composition theorem that ensures security when instantiating it cryptographically. The Universal Composition (UC) framework would ensure composition if we could specify an ideal functionality for signatures and prove it UC-realizable. Unfortunately, all signature functionalities heretofore proposed are problematic when used to construct higher-level protocols: either the functionality internally computes a computationally secure signature, and therefore higher-level protocols must rely upon computational assumptions, or else the functionality introduces a new attack surface that does not exist when the functionality is realized. As a consequence, no consensus protocol has ever been analyzed in a modular way using existing ideal signature functionalities. We propose a new unstoppable ideal functionality for signatures that is UC-realized exactly by the set of standard EUF-CMA signature schemes that are consistent and linear time. No adversary can prevent honest parties from obtaining perfectly ideal signature services from our functionality. We showcase its usefulness by presenting the first modular analysis of the Dolev-Strong broadcast protocol (SICOMP '83). Our result can be interpreted as a step toward a sound realization of the Dolev-Yao methodology. We also generalize our result to the threshold setting.

A Doubly Efficient Private Information Retrieval (DEPIR) is defined as a Private Information Retrieval (PIR) scheme with both near-linear server-side preprocessing time and sublinear query time. For many years, it has been a strong open question to devise a DEPIR scheme from standard assumptions. Very recently, Lin et al. (STOC '23) devised the first single-server DEPIR scheme from standard assumptions. However, their work left one major question open: can we build a DEPIR scheme in the multi-server setting, without relying on heavy cryptographic machinery? In this work, we discuss two different settings for multi-server DEPIR. In the non-colluding, non-communicating servers setting, we propose the first doubly efficient multi-server PIR scheme. Our scheme is information-theoretic. For a database of size $N$, our scheme allows servers to answer an infinite number of client queries in $N^{o(1)}$ time, after a single preprocessing phase which takes $N^{1+o(1)}$ time. Our result is only a $N^{o(1)}$ factor from the lower bound proven by Persiano and Yeo (SODA '22) for this setting. In addition, we devise a second information-theoretic PIR scheme in this setting which pushes the state of the art for the setting where the number of servers is more constrained. It achieves equally fast query times as our first scheme above, and a preprocessing time of $N^{2+o(1)}$. This scheme uses $O(\log N)$ servers. Both schemes don't require any cryptographic primitives. Furthermore, in the setting where the servers are additionally allowed to communicate and keep a global state (which is similarly required by PIR allowing database updates), we show a family of information-theoretic DEPIR schemes which achieve $N\mathsf{polylog} N$ preprocessing time, and $\log^3 N$ communication and server time, for any number of servers $k$ greater than three. We also discuss how introducing more servers or computational assumptions in this setting may improve the concrete efficiency of the PIR. This setting of communicating servers requires online communication between servers to answer queries, in contrast to the standard multi-server PIR setting where servers only communicate to coordinate the database contents and do not communicate at query time.

Multiparty computation (MPC) is a topic of growing interest for privacy-preserving computation tasks. A few MPC libraries have been developed, and newer protocols are regularly proposed to reduce the latency overhead, improve scalability, and achieve strong termination guarantees. However, most current MPC protocols are designed and implemented assuming network synchrony: in theory, they assume that all messages are delivered within a known time bound, while for experimental analysis, most assume all nodes to be honest, such that the time bounds are never deployed. While deploying MPC systems in the wild and trying to minimize the latency, network synchrony is indeed a strong assumption to make: natural adverse network conditions can break the safety and/or liveness of the protocol due to simply delayed messages. Asynchronous MPC (AMPC) protocols can overcome the challenge as they do not assume fixed time bounds for message delivery delays; however, AMPC faces a natural threshold barrier of 2/3rd honest majority and introduces significant computation and/or communication overheads. This work aims to achieve the best-of-both network models by designing a practical AMPC protocol that has stronger resilience guarantees matching those for synchronous MPC. We achieve this by adopting the emerging helper-aided model, and designing protocols that achieve fairness not only in the simple honest majority setting but also in the dishonest majority setting. Our protocols follow the standard preprocessing-online paradigm, enabling a lightweight and fast input-dependent online phase. In the honest majority setting, our protocol relies solely on lightweight cryptographic operations. In the dishonest majority setting, the protocol requires oblivious transfer (OT) during preprocessing, which we prove is necessary in this setting. We implement our constructions and provide a thorough performance comparison with state-of-the-art MPC protocols in the helper-aided model. Our experiments demonstrate that our protocols substantially outperform the state-of-the-art helper-aided MPC scheme, while being significantly more resilient to network delays.

Transformer-based models like BERT and GPT have achieved state-of-the-art performance across a wide range of AI tasks but raise serious privacy concerns when deployed as cloud inference services. To address this, secure multi-party computation (MPC) is commonly employed, encrypting both user inputs and model parameters to enable inference without revealing any private information. However, existing MPC-based secure transformer inference protocols are predominantly designed under the semi-honest security model. Extending these protocols to support malicious security remains a significant challenge, primarily due to the substantial overhead introduced by securely evaluating complex non-linear functions required for adversarial resilience. We introduce Mosformer, the first maliciously secure three-party (3PC) inference framework that efficiently supports large transformers such as BERT and GPT. We first design constant-round comparison and lookup table protocols with malicious security, leveraging verifiable distributed point functions (VDPFs). Building on these, we develop a suite of 3PC protocols for efficient and secure evaluation of complex non-linear functions in transformers. Together with optimized modulus conversion, our approach substantially reduces the overhead of secure transformer inference while preserving model accuracy. Experimental results on the vanilla transformer block show that Mosformer achieves up to a $5.3\times$ speedup and a $4.3\times$ reduction in communication over prior maliciously secure protocols. Despite offering stronger security guarantees, Mosformer achieves comparable or even superior online performance to state-of-the-art semi-honest 2PC and 3PC frameworks, including BOLT (Oakland 2024), BumbleBee (NDSS 2025), SHAFT (NDSS 2025), and Ditto (ICML 2024), on full-scale models such as BERT and GPT-2.

Solving a long-standing open problem, Faonio, Fiore, and Russo proved that the widely used Plonk zk-SNARK is simulation extractable. However, their proof assumes both the random oracle model (ROM) and the algebraic group model. We prove that the same holds in the ROM under falsifiable assumptions. We combine the template of Faust et al., who proved that simulation extractability follows from knowledge soundness, (weak) unique response, and trapdoorless zero-knowledge, with the recent result of Lipmaa, Parisella, and Siim (Crypto 2025), who proved that Plonk has knowledge soundness in the ROM under falsifiable assumptions. For this, we prove that Plonk satisfies new variants of the weak unique response and trapdoorless zero-knowledge properties. We prove that several commonly used gadgets, like the linearization trick, are not trapdoorless zero-knowledge when considered as independent commit-and-prove zk-SNARKs.

We suggest post quantum secure protocol based on pseudorandom walk on infinite q-regular forest D(q) where q = 2^m, m > 1. Correspondents share positive integer n, pseudorandom tuple from (Fq) ^n and two pseudorandom input words in the alphabet F_q of length O(1). They use the group of cubic multivariate transformations of the vector space of points of D(q) induced by walks on the forest of even length as the platform for the implementation of modified Twisted Diffie-Hellman protocol of Noncommutative Cryptography based on the complexity of the Conjugacy Power Problem. The output of the protocol is a vector from (F_q)^n. In fact the action of the group on the partition set of the bipartite homomorphic image D(n, q) of the forest is used. Correspondents elaborate the collision vector in time O(n^2) in the case when the length of input words is O(1) and the size of private integer parameters is O(n). If length of the input words is also O(n) then the complexity of protocol will be O(n^3). We suggest also the obfuscation of the scheme with hidden graph of the 1complexity O(n^5) for which the output of the algorithm is a symbolic cubic transformation F of (Fq)^n. It can be used symbiotically with the symmetric encryption via the adding to the ciphertext from (F_q)^n the vector F(b_1, b_2, . . . , b_n) where the tuple (b_1, b_2, . . . , b_n) of pseudorandom nature is known publicly.

Recent progress on zero-knowledge proofs (ZKPs) based on vector oblivious linear evaluation (VOLE) offers a promising paradigm for scaling ZKPs over extremely large statements. In particular, VOLE-based ZK is currently the best choice in terms of end-to-end execution time. However, VOLE-based ZK incurs high communication overhead — it usually scales linearly with the circuit size. To mitigate this, existing literature considers VOLE-based ZK over structured statements. In this work, we focus on the batched disjunctive statement — $\mathcal{P}$ and $\mathcal{V}$ agree on $B$ fan-in $2$ circuits $\mathcal{C}_1, \ldots, \mathcal{C}_{B}$ over a field $\mathbb{F}$; each circuit is of size $C$ with $n_{\mathit{in}}$ inputs. $\mathcal{P}$'s goal is to demonstrate the knowledge of $R$ witnesses $(\mathit{id}_j \in [B]$, $\boldsymbol{w}_j \in \mathbb{F}^{n_{\mathit{in}}})$ for each $j \in [R]$ s.t. $\forall j \in [R], \mathcal{C}_{\mathit{id}_j}(\boldsymbol{w}_j) = 0$ where neither $\boldsymbol{w}_j$ nor $\mathit{id}_j$ is revealed. Batched disjunctive statements are effective, e.g., in emulating the CPU execution inside ZK. Note, the naïve solution results in a circuit of size $\mathcal{O}(RBC)$. To prove such a statement using VOLE-based ZK, the prior state-of-the-art protocol $\mathsf{Antman}$ (Weng et al., CCS'22) incurred $\mathcal{O}(BC + R)$ communication by additionally relying on AHE, whereas $\mathsf{Batchman}$ (Yang et al., CCS'23) achieved $\mathcal{O}(RC + B)$ communication using only VOLE. In this work, we combine these two protocols non-trivially and present a novel protocol $\mathsf{Justvengers}$ — targeting the batched disjunctive statement — that incurs only $\mathcal{O}(R + B + C)$ communication and $\mathcal{O}(BC + (B + C)R\log R)$ computation for prover, using AHE and VOLE. As in Antman, Justvengers requires an AHE scheme that achieves linear targeted malleability, which is a non-falsifiable assumption.

Private Simultaneous Messages (PSM) is a kind of secure multiparty computation with minimal interaction pattern and minimal security requirement. A PSM protocol is said to be with universal reconstruction for a given function family if the algorithm of the referee (the output party) is independent of a function to be computed and the referee cannot infer the function from a protocol execution. In a recent work by Eriguchi and Shinagawa (EUROCRYPT 2025), the authors proposed a compiler to obtain a PSM protocol for symmetric functions from PSM protocols with universal reconstruction for symmetric functions with smaller domains. The authors also constructed the latter PSM protocols with universal reconstruction, by which the former PSM protocol achieves communication complexity better than the previously known protocols. In this paper, we construct the latter PSM protocols with universal reconstruction for symmetric functions more efficiently; the communication complexity is exponentially (in the input range) smaller than the protocols by Eriguchi and Shinagawa. As a consequence, we also obtain a PSM protocol (and also an ad-hoc PSM protocol and a robust PSM protocol) for symmetric functions that is more efficient than their protocol. Technically, a main ingredient of their protocols is a linear and injective encoding of histograms for the input elements, and our improvement is realized by finding a more efficient encoding of the histograms.

We give the first constructions of multiparty pseudorandom correlation generators, distributed point functions, and (negligible-error) homomorphic secret sharing for constant-degree polynomials for any number of parties without using LWE or iO. Our constructions are proven secure under the combination of LPN with dimension $n$, $2n$ samples, and noise rate $n^{\varepsilon-1}$ for a small constant $\varepsilon$, and MQ with $n$ variables and $n^{1+\delta}$ equations. As applications of our results, we obtain from the same assumptions secure multiparty computation protocols with sublinear communication and silent preprocessing, as well as private information retrieval for $M$ servers and size-$\lambda^d$ databases with optimal download rate and client-to-server communication $M^d\cdot \lambda^3$.

It is often desirable to break cryptographic primitives into two components: an input-independent offline component, and a cheap online component used when inputs arrive. Security of such online/offline primitives must be proved in the input-adaptive setting: the adversary chooses its input adaptively, based on what it sees in the offline-phase. Proving security in the input-adaptive setting can be difficult, particularly when one wishes to achieve simulation security and avoid idealized objects like a random oracle (RO). This work proposes a framework for reasoning about input-adaptive primitives: adaptive distributional security (ADS). Roughly, an ADS primitive provides security when it is used with inputs drawn from one of two distributions that are themselves hard to distinguish. ADS is useful as a framework for the following reasons: - An ADS definition can often circumvent impossibility results imposed on the corresponding simulation-based definition. This allows us to decrease the online-cost of primitives, albeit by using a weaker notion of security. - With care, one can typically upgrade an ADS-secure object into a simulation-secure object (by increasing cost in the online-phase). - ADS is robust, in the sense that (1) it enables a form of composition and (2) interesting ADS primitives are highly interconnected in terms of which objects imply which other objects. - Many useful ADS-secure objects are plausibly secure from straightforward symmetric-key cryptography. We start by defining the notion of an ADS encryption (ADE) scheme. A notion of input-adaptive encryption can be easily achieved from RO, and the ADE definition can be understood as capturing the concrete property provided by RO that is sufficient to achieve input-adaptivity. From there, we use ADE to achieve ADS variants of garbled circuits and oblivious transfer, to achieve simulation-secure garbled circuits, oblivious transfer, and two-party computation, and prove interconnectedness of these primitives. In sum, this results in a family of objects with extremely cheap online-cost.

Payment channels are a cornerstone of a scalable blockchain infrastructure that enables transacting parties to lock assets on the blockchain and perform rapid off-chain updates with minimal latency and overhead. These protocols dramatically reduce on-chain interaction and improve throughput, with blockchain consensus only invoked in the event of disputes or final closure. While widely adopted in single-chain settings—such as in the Lightning Network for Bitcoin—existing constructions have several limitations, in particular they suffer from at least one of the following limitations: 1) No cross-chain. They do not enable fast trading of assets that reside on multiple isolated blockchains. 2) Non-optimal round complexity. The off-chain round complexity is not optimal (i.e., parties require more than two rounds to update the channel). 3) No bitcoin compatibility. They require a more advanced scripting language that prevents cross-chain interaction between chains that only have a simple (Bitcoin-like) scripting language. In this work, we introduce a novel payment channel protocol that breaks through all the above limitations. Our construction supports bidirectional, multiasset, and off-chain interaction across an arbitrary set of blockchains, where each update of the channel requires the parties to send only one message each. Our protocol is fully compatible with Bitcoin and can be deployed on chains with only minimal scripting capabilities, making it broadly applicable to real-world blockchain networks. Crucially, our design ensures atomic settlement across blockchains without relying on trusted intermediaries. We formally prove the security of our protocol together with a novel definition of the cross-chain payment channel that we introduce. Finally, we empirically validate our protocol, showing the minimal costs that our payment channel incurs in the setting where two parties make multiple exchanges of assets that reside on three different blockchains.

Proving statements over integers is crucial in modern cryptographic protocols because certain computations, such as range proofs and Diophantine satisfiability, are more efficiently expressed over integers. Currently, the prevailing approach to achieve this is to convert the integer relations into statements tractable for proof systems over a finite field $\mathbb{Z}_p$. However, finding these corresponding tractable statements over $\mathbb{Z}_p$ is not always straightforward, and in practical schemes, the conversion often introduces computational overheads. Therefore, there is a growing interest in proving the statements directly over integers. Due to the significant applicability of inner-product arguments (IPA) in constructing succinct proof systems, in this work, we extend them to work natively in the integer setting. We introduce and construct inner-product commitment schemes over integers that allow a prover to open two committed integer vectors to a claimed inner product. The commitment size is constant and the verification proof size is logarithmic in the vector length. The construction significantly improves the slackness parameter of witness extraction, surpassing the existing state-of-the-art approach. Our construction is based on the folding techniques for Pedersen commitments defined originally over $\mathbb{Z}_p$. We develop general-purpose techniques to make it work properly over $\mathbb{Z}$, which may be of independent interest. Building upon our IPAs, we first present a novel batchable argument of knowledge of nonnegativity of exponents that can be used to further reduce the proof size of Dew-PCS (Arun et al., PKC 2023). Second, we present a construction for range proofs that allows for extremely efficient batch verification of a large number of range proofs over much larger intervals. We also provide a succinct zero-knowledge argument of knowledge with a logarithmic-size proof for more general arithmetic circuit satisfiability over integers.

We revisit multi-server Private Information Retrieval (PIR), where the client interacts with $S$ non-colluding servers. Ideally, we want a *scalable* family of multi-server PIR schemes where all the performance metrics of the scheme decrease as $S$ increases. However, no prior work achieved scalability under any setting, and any hardness assumption. In this paper we construct new multi-server, information-theoretically secure *scalable* PIR schemes for three natural settings. First, we give a construction where all the performance metrics scale at equal rate. Second, we give a scalable construction that minimizes the per-query bandwidth. Third, we give a scalable construction that minimizes the per-query online bottleneck cost (the maximum of the bandwidth and computation). For the first two settings, our constructions are *doubly efficient* with only a super-constant number of servers. In comparison, the best known prior works in the information-theoretic setting required super-logarithmically many servers to achieve the doubly efficient notion. Our techniques for achieving scalable PIR also enable us to advance the state of the art in the polynomial space setting. In this setting, we show how to improve the space consumption of prior works by a polynomial factor while preserving all other metrics. Further, we show a new balancing technique that allows us to further minimize the bandwidth per query by trading off the computation and server space, thus enabling a more smooth tradeoff between the metrics and generalizing the design space.

A distributed OPRF enables a client to evaluate a pseudo-random function on a client-chosen input using a distributed key shared among multiple servers, ensuring that the servers learn nothing about the input or output, while the client learns nothing about the key. We present a post-quantum OPRF suitable for a distributed server setting, requiring only two rounds of communication between the client and servers, with server-to-server communication limited to a pre-computation phase. Our approach leverages the Legendre PRF, computed through a single MPC multiplication and opening during the online phase. We introduce a novel MPC technique that achieves multiplication and opening in one round using replicated secret sharing (RSS) in a malicious adversarial model. This allows for the quantum-secure, verifiable evaluation of the Legendre OPRF against malicious adversaries under a threshold assumption, without requiring inter-server communication. Beyond the Legendre PRF, this method is also of interest for general MPC operations. To our knowledge, our distributed OPRF (dOPRF) is the first post-quantum construction with these properties. We compare our approach to state-of-the-art MPC solutions and provide an implementation of our proposed dOPRF, benchmarking it against existing OPRF constructions. In our comparison, our dOPRF protocol demonstrates superior efficiency.

Random Allocation - the random assignment of the data to the parties- is a well-studied topic in the analysis of medical or judicial data, and the context of resource distribution. Random allocation reduces the chance of bias or corruption in the relevant applications, which makes the results more reliable. This is done by preventing a special or pre-planned assignment of the data to accommodate the assessment toward the desired results. This paper provides the first formal syntax and security notion of a random allocation scheme. Based on our new security notions of anonymity, confidentiality, and data-integrity, random allocation can cover more applications, such as the distributed audit system, where the confidentiality of data and the anonymity of auditors are of paramount importance. Our protocol allows the parties to stay anonymous during the concurrent executions of the protocol, even if they have revealed themselves at a certain execution. The revelation property gives the possibility to the parties to claim certain advantages/faults at the end of a protocol-execution (without breaking the data-privacy or anonymity in other protocol-executions). We instantiate our syntax and prove the security based on simple cryptographic components and assumptions such as the Diffie-Hellman assumption, in the random oracle model.

Pseudorandom correlation generators (PCGs) have been popular in generating a huge amount of correlated randomness, a critical resource in secure computation. However, existing PCGs are memory-consuming and not friendly to resource-constrained devices. Even for moderate devices, the need for large memory can also be a disadvantage in applications like zero-knowledge proofs or large-scale secure computation. In this paper, we propose a malicious streaming PCG (sPCG), which generates a bounded number of tuples of subfield vector oblivious linear evaluation (sVOLE) on-the-fly, each with sublinear memory and computation. 1. We propose an efficient protocol that replaces the relaxed distributed comparison function in the best pseudorandom correlation function (PCF) for sVOLE (CRYPTO'22), which has the same streaming features for any polynomial number of tuples. With this protocol, our sPCG is doubly efficient in memory and the computation per sVOLE. Moreover, we augment the black-box distributed setup to malicious security and yield 4x communication improvement. Our sPCG can be extended to a more efficient sVOLE PCF with the same improvements in memory and computation, and a 2x faster malicious non-black-box distributed setup. 2. We present a practical attack on the Learning Parity with Noise (LPN) assumption for expand-accumulate codes with regular noise, revealing that some previous parameters provide around 14~22 bits of security over binary noises, far below the target 128 bits. To address this, we introduce a low-Hamming-weight noise distribution to withstand the attack. We then derive some updated LPN parameters with the new noise distribution, restoring 128-bit security and reducing the noise-related computation and communication. 3. We provide an implementation of our sPCG for the special case of correlated oblivious transfer (COT). In addition to the improvements over the best PCF, our sPCG can have a comparable end-to-end performance to Ferret (CCS'20) and the PCG from expand-convolute codes (CRYPTO'23), two state-of-the-art PCGs, with the advantage of being able to produce 10 million COTs on-the-fly and reducing the memory from 337 MB and 624 MB to 20 MB, respectively.

OPC UA is a standardized Industrial Control System (ICS) protocol, deployed in critical infrastructures, that aims to ensure security. The forthcoming version 1.05 includes major changes in the underlying cryptographic design, including a Diffie-Hellmann based key exchange, as opposed to the previous RSA based version. Version 1.05 is supposed to offer stronger security, including Perfect Forward Secrecy (PFS). We perform a formal security analysis of the security protocols specified in OPC UA v1.05 and v1.04, for the RSA-based and the new DH-based mode, using the state-of-the-art symbolic protocol verifier ProVerif. Compared to previous studies, our model is much more comprehensive, including the new protocol version, combination of the different sub-protocols for establishing secure channels, sessions and their management, covering a large range of possible configurations. This results in one of the largest models ever studied in ProVerif raising many challenges related to its verification mainly due to the complexity of the state machine. We discuss how we mitigated this complexity to obtain meaningful analysis results. Our analysis uncovered several new vulnerabilities, that have been reported to and acknowledged by the OPC Foundation. We designed and proposed provably secure fixes, most of which are included in the upcoming version of the standard.

Artificial Intelligence as a Service (AIaaS) enables users to query a model hosted by a service provider and receive inference results from a pre-trained model. Although AIaaS makes artificial intelligence more accessible, particularly for resource-limited users, it also raises verifiability and privacy concerns for the client and server, respectively. While zero-knowledge proof techniques can address these concerns simultaneously, they incur high proving costs due to the non-linear operations involved in AI inference and suffer from precision loss because they rely on fixed-point representations to model real numbers. In this work, we present ZIP, an efficient and precise commit and prove zero-knowledge SNARK for AIaaS inference (both linear and non-linear layers) that natively supports IEEE-754 double-precision floating-point semantics while addressing reliability and privacy challenges inherent in AIaaS. At its core, ZIP introduces a novel relative-error-driven technique that efficiently proves the correctness of complex non-linear layers in AI inference computations without any loss of precision, and hardens existing lookup-table and range proofs with novel arithmetic constraints to defend against malicious provers. We implement ZIP and evaluate it on standard datasets (e.g., MNIST, UTKFace, and SST-2). Our experimental results show, for non-linear activation functions, ZIP reduces circuit size by up to three orders of magnitude while maintaining the full precision required by modern AI workloads.

One-round secure computation is generally believed impossible due to the residual function attack: any honest-but-curious participant can replay the protocol in their head changing their input, and learn, in this way, a new output. Inputless functionalities are among the few that are immune to this problem. This paper studies one-round, multi-party computation protocols (MPC) that implement the most natural inputless functionality: one that generates a random sample from a fixed distribution. These are called distributed samplers. At Eurocrypt 2022, Abram, Scholl and Yakoubov showed how to build this primitive in the semi-honest model with dishonest majority. In this work, we give a lower bound for constructing distributed samplers with a malicious adversary in the standard model. More in detail, we show that for any construction in the stand-alone model with black-box simulation, even with a CRS and honest majority, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Our proof is based on an entropic argument, drawing a new connection between computationally secure MPC, information theory and learning theory.

The lattice isomorphism problem (LIP) asks, given two lattices $\Lambda_0$ and $\Lambda_1$, to decide whether there exists an orthogonal linear map from $\Lambda_0$ to $\Lambda_1$. In this work, we show that the hardness of (a circular variant of) LIP implies the existence of a fully-homomorphic encryption scheme for all classical and quantum circuits. Prior to our work, LIP was only known to imply the existence of basic cryptographic primitives, such as public-key encryption or digital signatures.

CKKS is a homomorphic encryption (HE) scheme that supports approximate arithmetic over complex numbers. While it is widely used in privacy-preserving machine learning (PPML) protocols, the approximate nature of the scheme makes it challenging to formally define the security guarantees of those protocols. In particular, in a sender-receiver protocol, where the sender performs homomorphic evaluation using a private circuit, characterizing the sender's privacy remains an important open problem. Moreover, there are currently no known methods for handling malicious receivers due to the absence of a zero-knowledge argument of knowledge (ZKAoK) for the CKKS scheme. In this paper, we address these open challenges. First, we introduce a new security definition, called differentially private homomorphic evaluation (DPHE), to formalize sender privacy in CKKS-based protocols. Next, we present a general compilation method that transforms a plain CKKS protocol into a DPHE protocol. Finally, we construct a zero-knowledge argument of knowledge (ZKAoK) for CKKS to achieve the DPHE property in the presence of malicious receivers, and provide concrete benchmarks of our ZKAoK implementation. To the best of our knowledge, this is the first work to formally address security and privacy issues in CKKS-based protocols through the lens of differential privacy. We also remark that our ZKAoK is the first construction to ensure the well-formedness of CKKS public keys and ciphertexts.

Despite several known idiosyncrasies separating the synchronous and the asynchronous models, asynchronous secure multi-party computation (MPC) protocols demonstrate high-level similarities to synchronous MPC, both in design philosophy and abstract structure. As such, a coveted, albeit elusive, desideratum is to devise automatic translators (e.g., protocol compilers) of feasibility and efficiency results from one model to the other. In this work, we demonstrate new challenges associated with this goal. Specifically, we study the case of parallel composition in the asynchronous setting. We provide formal definitions of this composition operation in the UC framework, which, somewhat surprisingly, have been missing from the literature. Using these definitions, we then turn to charting the feasibility landscape of asynchronous parallel composition. We first prove strong impossibility results for composition operators that do not assume knowledge of the functions and/or the protocols that are being composed. These results draw a grim feasibility picture, which is in sharp contrast with the synchronous model, and highlight the question: Is asynchronous parallel composition even a realistic goal? To answer the above (in the affirmative), we provide conditions on the composed protocols that enable a useful form of asynchronous parallel composition, as it turns out to be common in existing constructions.

In our work, we introduce BATTLE, Bonded Adversarial TournamenT with Logarithmic Escalation, a tournament-style protocol that solves multiparty disputes with simultaneous assertions such that (i) bounds honest asserter capital requirements to a constant minimum initial capital and (ii) resolves any number $C$ of concurrent challenges in $\mathcal{O}(\log C)$ dispute rounds, by reinvesting dispute rewards to fund subsequent rounds (progressive buy-ins) (iii) can be realized on a stateful (Quasi)Turing-complete smart-contract enabled blockchain. BATTLE solves a set of conflicting assertions by creating a tournament with two phases: (1) a bracket among competing asserters with one dispute per party per round, and (2) a challenger phase against the winning assertion where the asserter engages in increasing number of simultaneous disputes each round.

We introduce ChipmunkRing, a practical post-quantum ring signature construction tailored for blockchain environments. Building on our Chipmunk lattice-based cryptographic framework, this implementation delivers compact digital signatures ranging from 20.5 to 279.7KB, with rapid signing operations completing in 1.1-15.1ms and efficient validation processes requiring only 0.4-4.5ms for participant groups of 2-64 members. The cornerstone of our approach is Acorn Verification—a streamlined zero-knowledge protocol that supersedes the classical Fiat-Shamir methodology. This innovation enables linear O(n) authentication complexity using concise 96-byte cryptographic proofs per participant, yielding a remarkable 17.7× performance enhancement for 32-member rings when compared to conventional techniques. Our work includes preliminary security estimates indicating approximately 112-bit security against known quantum algorithms (NIST Level 5, see Section~\ref{sec:quantum-security}), extensive computational benchmarking, and comprehensive support for both standard anonymity sets and collaborative threshold constructions with flexible participation requirements.

Recent developments in the field of Dynamic Searchable Symmetric Encryption (DSSE) with forward and backward privacy have attracted much attention from both research and industrial communities. However, most DSSE schemes with forward and backward privacy schemes only support single keyword queries, which impedes its prevalence in practice. Although some forward and backward private DSSE schemes with expressive queries (e.g., conjunctive queries) have been introduced, their backward privacy either essentially corresponds to single keyword queries or forward privacy is not comprehensive. In addition, the deletion of many DSSE schemes is achieved by addition paired with a deletion mark (i.e., lazy deletion). To address these problems, we present two novel DSSE schemes with conjunctive queries (termed \texttt{SDSSE-CQ} and \texttt{SDSSE-CQ-S}), which achieve both forward and backward privacy. To analyze their security, we present two new levels of backward privacy (named Type-O and Type-O$^-$, more and more secure), which give a more comprehensive understanding of the leakages of conjunctive queries in the \texttt{OXT} framework. Eventually, the security analysis and experimental evaluations show that the proposed schemes achieve better security with reasonable computation and communication increase.

Multi-signature schemes are crucial for secure operations in digital wallets and escrow services within smart contract platforms, particularly in the emerging post-quantum era. Existing post-quantum multi-signature constructions either do not address the stringent requirements of the Quantum Random Oracle Model (QROM) or fail to achieve practical efficiency due to suboptimal parameter choices. In this paper, we present a novel multi-signature scheme designed to be secure in the QROM and optimized for practical use. Our scheme operates over the polynomial ring $\mathbb{Z}_q[X]/(x^n+1)$ with $q \equiv 1 \pmod{2n}$, enabling full splitting of the ring and allowing for efficient polynomial arithmetic via the Number Theoretic Transform (NTT). This structure not only ensures post-quantum security but also bridges the gap between theoretical constructs and real-world implementation needs. We further propose a new hardness assumption, which is termed $\nu$-{\sf SelfTargetMSIS}, extending {\sf SelfTargetMSIS} (Eurocrypt 2018) to accommodate multiple challenge targets. We prove its security in the QROM and leverage it to construct a secure and efficient multi-signature scheme. Our approach avoids the limitations of previous techniques, reduces security loss in the reduction, and results in a more compact and practical scheme suitable for deployment in post-quantum cryptographic systems.

Incrementally verifiable computation (IVC) is a powerful cryptographic primitive, particularly suited for proving long-running machine computations. Previous work shows that IVC can be constructed by recursively composing SNARKs. Unfortunately, theoretical challenges limit the provable security of known IVC constructions. Recursive composition may quickly lead to a blowup in extraction time and may require arithmetic circuits to enforce constraints about random oracle calls. Furthermore, composition presents a practical challenge: proofs are often expressed in a form that is not friendly to the arithmetic circuits that produce them. To mitigate the theoretical challenges, we present the Open-and-Sign Random Oracle Model (osROM) as an extension to the signed random oracle of Chiesa and Tromer (ICS '10). This model, while strictly harder to instantiate than the Random Oracle Model, allows the design of protocols that can efficiently verify calls to the oracle and support straight-line extractors. As a result, IVC constructions in the osROM can be shown to have provable security for polynomial depths of computation. Under our new model, we construct a framework to build secure IVC schemes from simple non-interactive reductions of knowledge. Our construction natively supports cycles of elliptic curves in the style of Ben-Sasson et al. (CRYPTO '14), thus answering the practical challenge outlined above. Finally, we analyze the HyperNova (CRYPTO '24) IVC scheme in the osROM and show that it is secure over a two-cycle of elliptic curves, for polynomial depths of computation.

The fundamental assumption in $t$-out-of-$n$ threshold encryption is that the adversary can only corrupt fewer than $t$ parties. However, this may be unrealistic in practical scenarios where shareholders could have financial incentives to collude. Boneh, Partap, and Rotem (Crypto'24) addressed the case where $t$ or more shareholders collude, adding a traceability mechanism to identify at least one colluder. Their constructions require a trusted dealer to distribute secret shares, but it is unclear how to achieve traceability without this trusted party. Since threshold encryption aims to avoid a single point of failure, a natural question is whether we can construct an efficient, traceable threshold encryption scheme without relying on a trusted dealer. This paper presents two dealerless, traceable threshold encryption constructions by extending the PLBE primitive of Boneh et al. (Eurocrypt'06) and combining it with the silent setup threshold encryption construction of Garg et al. (Crypto'24). Our first construction achieves an amortized ciphertext size of $O(1)$ (for $O(n)$ ciphertexts), and the second achieves constant ciphertext size in the worst case but with a less efficient preprocessing phase. Both have constant secret key sizes and require no interaction between parties. A limitation of Boneh et al.’s constructions is that they only guarantee identifying one colluder, leaving the problem of tracing more traitors unsolved. We address this by applying a technique to our first construction that enables tracing up to $t$ traitors.

Cryptographic protocols often make honesty assumptions---e.g., fewer than $t$ out of $n$ participants are adversarial. In practice, these assumptions can be hard to ensure, particularly given monetary incentives for participants to collude and deviate from the protocol. In this work, we explore combining techniques from cryptography and mechanism design to discourage collusion. We formalize protocols in which colluders submit a cryptographic proof to whistleblow against their co-conspirators, revealing the dishonest behavior publicly. We provide general results on the cryptographic feasibility, and show how whistleblowing fits a number of applications including secret sharing, randomness beacons, and anonymous credentials. We also introduce smart collusion---a new model for players to collude. Analogous to blockchain smart contracts, smart collusion allows colluding parties to arbitrarily coordinate and impose penalties on defectors (e.g., those that blow the whistle). We show that unconditional security is impossible against smart colluders even when whistleblowing is anonymous and can identify all colluding players. On the positive side, we construct a whistleblowing protocol that requires only a small deposit and can protect against smart collusion even with roughly $t$ times larger deposit.

Garbled Circuits (GC) are a foundational primitive for secure two-party computation (2PC). Garbled Private Information Retrieval (GPIR) is a GC technique for looking up a public array or database (DB) on a private index unknown to either party. GPIR immediately enables GC evaluation of functions implemented as a publicly known lookup table (LUT). However, GPIR is costly. It can be realized by a linear scan, by adapting Garbled RAM, by stacking GC branches implementing access to table elements, and, most recently, via the GC lookup table scheme logrow (Heath et al., Eurocrypt 2024). For an $N$-row DB lookup of $m$-bit rows, logrow has computation cost $\approx O(N m \kappa)$ and communication cost $O(m(\log N \cdot \kappa + N))$. This makes logrow practical only for tables up to about $2^{15}$ rows. We propose Toss, a new efficient GPIR protocol with dramatically reduced bandwidth consumption—an especially scarce resource in MPC—both asymptotically and concretely. Our communication cost is $O\!\left(\sqrt{N}\, m \sqrt{\kappa}\right)$ with a small constant, which is sublinear in both $N$ and the security parameter $\kappa$. Our computation cost is $O\!\left(N m \kappa + \bigl(\sqrt{N/\kappa}\, m + N\bigr) c_\kappa \right)$, where $c_\kappa$ is the cost of a hash evaluation. This computation cost is comparable to, or slightly lower than, that of logrow. In concrete terms, for a $2^{20}$-row LUT of 8-bit items, we achieve more than a $31\times$ reduction in communication compared to logrow. On a laptop over a 100 Mbps channel, throughput increases from approximately $10.6$ lookups/s to $81$ lookups/s, a $>7.5\times$ improvement. On a 10 Mbps channel, Toss achieves more than $28\times$ better throughput. The improvement grows with $N$; for example, for $N=2^{25}$ and $m=32$, the gain exceeds $512\times$. Toss builds on stacked garbling (SGC) and logrow, incorporating multiple low-level optimizations and requiring a reworking of their internals and interfaces. We emphasize that constructing GPIR directly from SGC incurs logarithmic computational overhead, which decreases throughput in typical “laptop + LAN” testbeds. Our design avoids this pitfall. We implement Toss and report on its performance, demonstrating its substantial communication savings and practical efficiency.

Data availability sampling (DAS) enables clients to verify availability of data without downloading it entirely. This concept is crucial to Ethereum's roadmap. An instantiation of this concept, known as PeerDAS, relies at its core on a variant of KZG polynomial commitments and is set to be integrated into Ethereum. To assess the security of PeerDAS, Wagner and Zapico (ePrint 2024) provided a formal analysis, proving its security as a cryptographic primitive. However, their proof relies on the algebraic group model - an idealized framework known to be uninstantiable (Zhandry, CRYPTO 2022). In this work, we establish the security of \peerdas in the standard model under falsifiable assumptions. Specifically, we eliminate reliance on the algebraic group model and instead base our proof on the ARSDH assumption (Lipmaa et al., EUROCRYPT 2024), thus strengthening the theoretical foundations of PeerDAS and enhancing confidence in its security.

We introduce a new transparent zero-knowledge argument system that will significantly reduce the size of the polynomial commitment scheme (PCS) that needs to be evaluated relative to the circuit size. In our protocol, committed input parameters are transformed into a format that the verifier can process directly, so the output of the circuit polynomial at some evaluation point can be directly computed by the verifier instead of asking the prover to run the expensive PCS protocol on circuit polynomial(s) as big as the circuit size. In the default setting, the prover runtime cost for group exponentiation operations is only the square root of the degree ($\sqrt{p_d}$) of the polynomial the circuit generates. This direct computation approach brings many additional benefits. For example, it allows inputs and outputs of a circuit to be in the same commitment format. This will open up new use cases such as creating an openly accessible database with data perfectly hidden using commitments, but still allowing anyone to validate updates to the data with zero-knowledge.  Our benchmark result shows our approach can significantly improve both proving and verification speed over the state-of-the-art by one order of magnitude for all types of circuits of any depth, while keeping the communication cost competitive. (code is included in the attachment file). Our approach also allows our protocol to be made memory-efficient while being non-interactive. The theoretical memory cost of our protocol is $O(b + s)$, where $s = b = \sqrt{p_d}$ in the default setting.

This work addresses the inherent issues of high latency in blockchains and low scalability in traditional consensus protocols. We present pod, a novel notion of consensus whose first priority is to achieve the physically-optimal latency of $2\delta$, or one round-trip, i.e., requiring only one network trip (duration $\delta$) for writing a transaction and one for reading it. To accomplish this, we first eliminate inter-replica communication. Instead, clients send transactions directly to all replicas, which independently process transactions and append them to local logs. Replicas assigns a timestamp and a sequence number to each transaction in their logs, allowing clients to extract valuable metadata about the transactions and the system state. Later on, clients retrieve these logs and extract transactions (and associated metadata) from them. Necessarily, this construction achieves weaker properties than a total-order broadcast protocol, due to existing lower bounds. Our work models the primitive of pod and defines its security properties. We then show pod-core, a protocol that satisfies properties such as transaction confirmation within $2\delta$, censorship resistance against Byzantine replicas, and accountability for safety violations. We show that single-shot auctions can be realized using the pod notion and observe that it is also sufficient for other popular applications.

Passwords remain the dominant form of authentication on the Internet. The rise of single sign-on (SSO) services has centralized password storage, increasing the devastating impact of potential attacks and underscoring the need for secure storage mechanisms. A decade ago, Facebook introduced a novel approach to password security, later formalized in Pythia by Everspaugh et al. (USENIX'15), which proposed the concept of password hardening. The primary motivation behind these advances is to achieve provable security against offline brute-force attacks. This work initiated significant follow-on research (CCS'16, USENIX'17), including Password-Hardened Encryption (PHE) (USENIX'18, CCS'20), which was introduced shortly thereafter. Virgil Security commercializes PHE as a software-as-a-service solution and integrates it into its messenger platform to enhance security. In this paper, we revisit PHE and provide both negative and positive contributions. First, we identify a critical weakness in the original design and present a practical cryptographic attack that enables offline brute-force attacks -- the very threat PHE was designed to mitigate. This weakness stems from a flawed security model that fails to account for real-world attack scenarios and the interaction of security properties with key rotation, a mechanism designed to enhance security by periodically updating keys. Our analysis shows how the independent treatment of security properties in the original model leaves PHE vulnerable. We demonstrate the feasibility of the attack by extracting passwords in seconds that were secured by the commercialized but open-source PHE provided by Virgil Security. On the positive side, we propose a novel, highly efficient construction that addresses these shortcomings, resulting in the first practical PHE scheme that achieves security in a realistic setting. We introduce a refined security model that accurately captures the challenges of practical deployments, and prove that our construction meets these requirements. Finally, we provide a comprehensive evaluation of the proposed scheme, demonstrating its robustness and performance.

In Diffie–Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie–Hellman key exchange in the group action framework (Brassard–Yung, Crypto'90; Ji–Qiao–Song–Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.

Transparent verification allows voters to directly identify their vote in cleartext in the final tally result. Both Selene and Hyperion offer this simple and intuitive verification method, and at the same time allow for coercion to be mitigated under the assumption that tally servers can privately notify voters of the keying material needed for verification. Subsequently, a voter can generate fake keying material to deceive a coercer. In this paper, we propose Surtr, a new scheme that enables transparent verification without requiring a private notification channel. This approach strengthens coercion mitigation, since a coercer can monitor the notification channel, and simplifies the process by eliminating the need for voters to generate fake keying material for the coercer.

Sublinear proof sizes have recently become feasible in verifiable machine learning (VML), yet no approach achieves the trio of strictly linear prover time, logarithmic proof size and verification time, and architecture privacy. Hurdles persist because we lack a succinct commitment to the full neural network and a framework for heterogeneous models, leaving verification dependent on architecture knowledge. Existing limits motivate our new approach: a unified proof-composition framework that casts VML as the design of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for matrix computations. Representing neural networks with linear and non-linear layers as a directed acyclic graph of atomic matrix operations enables topology-aware composition without revealing the graph. Modeled this way, we split proving into a reduction layer and a compression layer that attests to the reduction with a proof of proof. At the reduction layer, inspired by reduction of knowledge (Crypto '23), root-node proofs are reduced to leaf-node proofs under an interface standardized for heterogeneous linear and non-linear operations. Next, a recursive zkSNARK compresses the transcript into a single proof while preserving architecture privacy. Complexity-wise, for a matrix expression with $M$ atomic operations on $n \times n$ matrices, the prover runs in $O(M n^2)$ time while proof size and verification time are $O(\log(M n))$, outperforming known VML systems. Honed for this framework, we formalize relations directly in matrices or vectors---a more intuitive form for VML than traditional polynomials. Our LiteBullet proof, an inner-product proof built on folding and its connection to sumcheck (Crypto '21), yields a polynomial-free alternative. With these ingredients, we reconcile heterogeneity, zero knowledge, succinctness, and architecture privacy in a single VML system.

In an attempt to fix the defects of the definition of forward security for Symmetric Searchable Encryption (SSE) schemes, Amjad et al. [2] proposed injection security. This new security property is strictly stronger than most security properties known to date, which makes it particularly challenging to design schemes meeting its requirements. In this work, we show how it is possible to use trees to decorrelate the modification of an index from its effects, hence achieving injection security. In addition to being conceptually simple, our scheme features non-interactive, stateless and mutation-free search operations that allow supporting concurrent readers easily. Finally, the proposed reference implementation is efficient: both Insert and Search operations execute in milliseconds even when operating on an index with up to a million entries and volumes up to a thousand.

Authenticated Key Exchange (AKE) establishes shared ('symmetric') cryptographic keys which are essential for secure online communication. AKE protocols can be constructed from public-key cryptography like Key Encapsulation Mechanisms (KEMs). Another approach is to use Quantum Key Distribution (QKD) to establish a symmetric key, which uses quantum communication. Combining post-quantum AKE and QKD appropriately may provide security against quantum attacks even if only one of the two approaches turns out to be secure. We provide an extensive review of existing security analyses for combined AKE and their formal security models, and identify some gaps in their treatment of QKD key IDs. In particular, improper handling of QKD key IDs leads to Dependent-Key attacks on AKE. As our main conceptual contribution, we model QKD as an oracle that closely resembles the standard ETSI 014 QKD interface. We demonstrate the usability of our QKD oracle for cryptographic security analyses by integrating it into a prominent security model for AKE, called CK+ model, thereby obtaining a security model for combined AKE that catches Dependent-Key attacks. In this model, we formally prove security of a new protocol that combines QKD with a triple-KEM handshake. This is the first provably secure hybrid protocol that maintains information-theoretic security of QKD.

Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an es- tablished technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a fundamental component in the practical construction of HE-based multi-party computation (MPC) protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by multiple (possibly malicious) parties, which may require additional security assumptions that have been so far overlooked in the HHE literature. In this paper, we formalize this issue as a security against related-key attacks (RKA) problem and provide efficient solutions for it. We start by presenting an efficient method for homomorphically evaluating Mixed-Filter-Permutator (MFP) ciphers in leveled mode, enabling speedups of up to thousands of times compared to previous literature. For the multi-party scenario, we focus specifically on the Margrethe cipher (Hoffmann et al., INDOCRYPT 2023). We show that, contrary to other commonly used HHE ciphers (e.g. FLIP), Margrethe is out-of-the-box secure for any protocols that allow malicious parties to learn up to two related key streams, enabling security for the vast majority of static MPC protocols. For other cases, we quantify the loss of security based on the number of related key streams (which often depends on the number of malicious parties and specific protocol). Performance-wise, our implementation of Margrethe takes just 3.9 ms to transcipher 4 bit messages, being significantly faster than the state of the art in terms of latency.

We examine Multi-Party Computation protocols in the active-security-with-abort setting for $Q_2$ access structures over small and large finite fields $F_p$ and over rings $Z_{p^k}$. We give general protocols which work for any $Q_2$ access structure which is realised by a multiplicative Extended Span Program. We generalize a number of techniques and protocols from various papers and compare the different methodologies. In particular we examine the expected communication cost per multiplication gate when the protocols are instantiated with different access structures.

This paper presents a structured literature review of ongoing global efforts to integrate post-quantum cryptography (PQC) into widely deployed communication and identity protocols. We analyze current readiness, standardization initiatives, hybrid cryptographic approaches, and deployment challenges across multiple layers of the protocol stack, including TLS, SSH, VPNs, certificate infrastructure, and messaging protocols. The report also discusses hybrid cryptographic strategies, current deployment efforts, and the technical challenges facing real-world implementation, including performance, interoperability, and resistance to side-channel attacks. With insights from recent research, industry trials, and open source tools, the report aims to provide a clear and accessible overview of the growing role of PQC in securing the future of digital communication. We aim to guide researchers, developers, and policymakers in understanding the state of PQC integration and encourage broader involvement in the testing, implementation, and evaluation of next-generation cryptographic solutions.

We present Trout (Two-ROUnd Threshold), the \textit{first} distributed two-round ECDSA signing protocol for arbitrary thresholds. Trout has constant upload bandwidth per-party and processing time linear in the amount of participants. Moreover, Trout achieves the Identifiable Abort (IA) property, which means that if the protocol cannot terminate due to a failure, parties can attribute the failure to a specific party. We achieve this without a trusted setup. Our protocol relies on linear-homomorphic encryptions and commitments over class groups. To obtain our result, we leverage the recent construction of an exponent-VRF (Boneh et al., Eurocrypt 2025) and a novel protocol to multiply an encrypted value with a committed value and simultaneously decrypt it, which we call "scaled decryption". We believe that this protocol may be of independent interest. Our protocol has a very low communication cost of just 6.5 KB sent per party. Furthermore, we implemented our protocol in Rust and provide benchmarks for various configurations, showing its practicality even for 100 parties. Our implementation includes a constant-time variant which, to the best of our knowledge, is the first of its kind for class-group-based threshold ECDSA protocols.

Message authentication (MA) in the Short Authenticated String (SAS) model, defined by Vaudenay, allows for authenticating arbitrary messages sent over an insecure channel as long as the sender can also transmit to the receiver a short authenticated message, e.g. d = 20 bits. The flagship application of SAS-MA is Authenticated Key Exchange (AKE) in the SAS model (SAS-AKE), which allows parties communicating over insecure network to establish a secure channel without prior source of trust except an ability to exchange d-bit authenticated strings. SAS-AKE is applicable e.g. for device pairing, i.e. creating secure channels between devices capable of displaying d-bit values, e.g. encoded as decimal strings, verified by a human operator, or to secure messaging applications like Signal or WhatsApp, where such short values can be read off by participants who trust each others’ voices. A string of works showed light-weight SAS-MA schemes, using only symmetric-key crypto and 3 communication flows, which is optimal. This was extended to group SAS-(M)MA, for (mutual) message authentication among any number of parties, using two simultaneous flows. We show a new two simultaneous flows SAS-(M)MA protocol, based on Verifiable Random Functions (VRF), with a novel property that the first flow, which consists of exchanging VRF public keys, can be re-used in multiple SAS-MA instances. Moreover, instantiated with ECVRF, these keys have the same form $vk = g^{sk}$ as Diffie-Hellman keys exchanged in DH-based (A)KE protocols like X3DH. We show that X3DH keys can be re-used in our SAS-MA, implying SAS-AKE which adds a minimal overhead of a single flow to X3DH. Crucially, while X3DH is secure only if participants’ public keys are certified by a shared source of trust, e.g. a Public Key Infrastructure (PKI) or a trusted Key Distribution Center (KDC) ran by Signal or WhatsApp, if X3DH is amended by our SAS-AKE then the established channel is secure even if PKI or KDC is compromised, assuming trust in user-assisted authentication of short d-bit strings.

Succinct Non-interactive Arguments of Knowledge(SNARKs) have gained widespread application due to their succinct proof size and efficient verification. However, they face significant scalability limitations in proof generation for large-scale circuits. To address this challenge, distributing the prover's computation across multiple nodes has emerged as a promising solution. Existing distributed SNARK constructions rely on distributed polynomial commitments, requiring each prover to perform computationally intensive group operations during the polynomial commitment opening phase. In this paper, we propose a novel distributed SNARK system constructed by compiling distributed PIOP with additively homomorphic polynomial commitment, rather than distributed polynomial commitment. The core technical component is distributed SumFold, which folds multiple sum-check instances into one. After the folding process, only one prover is required to perform polynomial commitment openings. It facilitates compilation with SamaritanPCS, which is a recently proposed additively homomorphic multilinear polynomial commitment scheme. The resulting SNARK system is specifically optimized for data-parallel circuits. Compared to prior HyperPlonk-based distributed proof systems (e.g., Hyperpianist and Cirrus), our construction achieves improvements in both proof size and prover time. We implement our protocol and conduct a comprehensive comparison with HyperPianist with 8 machines. Our system achieves shorter proof and 4.1~4.9× speedup in prover time, while maintaining comparable verification efficiency.

Much work has been done recently on developing password-authenticated key exchange (PAKE) mechanisms with post-quantum security. However, modern guidance recommends the use of hybrid schemes—schemes which rely on the combined hardness of a post-quantum assumption, e.g., Learning with Errors (LWE), and a more traditional assumption, e.g., decisional Diffie-Hellman. To date, there is no known hybrid PAKE construction, let alone a general method for achieving such. In this paper, we present two efficient PAKE combiners—algorithms that take two PAKEs satisfying mild assumptions, and output a third PAKE with combined security properties—and prove these combiners secure in the Universal Composability (UC) model. Our sequential combiner, instantiated with efficient existing PAKEs such as CPace (built on Diffie-Hellman-type assumptions) and CAKE (built on lattice assumptions), yields the first known hybrid PAKE.

As large language models are increasingly deployed in cloud environments, privacy concerns have become a significant issue. To address this challenge, we present THOR, a non-interactive framework for secure transformer inference using homomorphic encryption. We first propose efficient matrix multiplication algorithms based on diagonal-major encoding and compact ciphertext packing. We extend these basic algorithms to support plaintext-ciphertext matrix multiplication (PC-MM) using parallel submatrix computation and ciphertext-ciphertext multiplication (CC-MM) with a baby-step giant-step strategy. We also design efficient evaluation strategies for non-linear functions such as softmax, LayerNorm, GELU, and Tanh, by integrating advanced approximation techniques with adaptive iterative methods. Our matrix multiplication algorithms outperform state-of-the-art methods, achieving up to 5.3$\times$ speedup in PC-MM for $\mathbb{R}^{768\times 768}\times \mathbb{R}^{768\times 128}$ over BOLT (Pang et al., IEEE S&P 2024) and 9.7$\times$ in CC-MM for $12\times (\mathbb{R}^{64\times 128}\times \mathbb{R}^{128\times 128})$ over Powerformer (Park et al., Preprint). THOR enables secure inference on the BERT-base model with 128 tokens in 10 minutes on a single GPU, while maintaining comparable accuracy on GLUE tasks.

Password-Hardened Encryption (PHE) protects against offline brute-force attacks by involving an external ratelimiter that enforces rate-limited decryption without learning passwords or keys. Threshold Password-Hardened Encryption (TPHE), introduced by Brost et al. (CCS’20), distributes this trust among multiple ratelimiters. Despite its promise, the security foundations of TPHE remain unclear. We make three contributions: (1) We uncover a flaw in the proof of Brost et al.’s TPHE scheme, which invalidates its claimed security and leaves the guarantees of existing constructions uncertain; (2) We provide the first universal composability (UC) formalization of PHE and TPHE, unifying previous fragmented models and supporting key rotation, an essential feature for long-term security and related primitives such as updatable encryption; (3) We present the first provably secure TPHE scheme, which is both round-optimal and UC-secure, thus composable in real-world settings; and we implement and evaluate our protocol, demonstrating practical efficiency that outperforms prior work in realistic WAN scenarios.

Modern data analytics requires computing functions on streams of data points from many users that are challenging to calculate, due to both the high scale and nontrivial nature of the computation at hand. The need for data privacy complicates this matter further, as general-purpose privacy-enhancing technologies face limitations in at least scalability or utility. Existing work has attempted to improve this by designing purpose-built protocols for the use case of Private Stream Aggregation; however, prior work lacks the ability to compute more general aggregative functions without the assumption of trusted parties or hardware. In this work, we present PPSA, a protocol that performs Private Polynomial Stream Aggregation, allowing the private computation of any polynomial function on user data streams even in the presence of an untrusted aggregator. Unlike previous state-of-the-art approaches, PPSA enables secure aggregation beyond simple summations without relying on trusted hardware; it utilizes only tools from cryptography and differential privacy. Our experiments show that PPSA has low latency during the encryption and aggregation processes with an encryption latency of 10.5 ms and aggregation latency of 21.6 ms for 1000 users, which are up to 138$\times$ faster than the state-of-the-art prior work.

We study “send this data to that device now” exchanges under an active network adversary without PKI or pre-shared secrets. We model a human-verifiable out-of-band channel for comparing short codes as a first-class UC functionality. Building on this, we give two commitment-style protocols, a one-sided and a mutual one, that are direct UC equivalents of MANA-IV and prove they realize authenticated channels with explicit misbinding parameter \(\varepsilon=2^{-t}\). We then compose SAS-based authentication with standard KEM/DEM encryption to obtain a UC-secure message-transfer functionality, preserving the explicit \(\varepsilon\) under composition, and we detail practical instantiations over signatures or MACs. Complementing the theory, we systematize real-world tooling: popular file-transfer utilities either form unauthenticated WebRTC/DTLS channels or use PAKE “one-code” designs that couple rendezvous and a longer password string but none deploy a session-bound SAS. Our approach decouples rendezvous from authentication and reduces the out-of-band burden to comparing a short \(t\)-bit string. We also sketch an RO-free variant (coin-flip plus non-malleable commitments) with the same user interface.

Secure multi party computation protocols (MPC) translating between arithmetic and binary data types have recently gained attraction which is introduced by Rotaru and Wood in 2019, called daBit, and improved by Escudero et. al. called edaBits. EdaBits are simply secret shares in arithmetic domain and bit decomposition of the arithmetic share is the binary form the secret shares. These protocols are preprocessing for MPC protocols in order to improve efficiency. Furthermore, fluid MPC setting, introduced by Choudhuri, Goel, Green, Jain and Kaptchuk in 2021, is a framework which the parties, called dynamic parties, do not have be online throughout the whole process. Fluid MPC framework is still has to be worked and conventional protocols and techniques has to be adapted for it. Our work introduces an edaBits protocol specifically designed for the fluid MPC setting under a four-party honest-majority model. The protocol, which consists of eight subprotocols, achieves security against an honest majority and departs slightly from the traditional cut-and-choose paradigm. It attains linear memory and time complexity, as well as constant communication complexity. Finally, we demonstrate two applications that employ edaBits within the fluid MPC framework under the semi-honest adversary model.

In this work, we introduce Rayls, a new central bank digital currency (CBDC) design that provides privacy, high performance, and regulatory compliance. In our construction, commercial banks each run their own (private) ledger and are connected to an underlying decentralized programmable blockchain via a relayer. We also introduce a novel protocol that allows for efficient anonymous transactions between banks, which we call Enygma. Our design is `quantum-private' as a quantum adversary is not able to infer any information (i.e., payer, payee, amounts) about the transactions that take place in the network. We achieve high performance in cross-bank settlement via the use of ZK-SNARKs and 'double' batching. Concretely, our transactions consist of a set of commitments and a zero-knowledge proof. As a result, each transaction can pay more than 1 bank at once and, secondly, each of these individual commitments can contain aggregated transfers from multiple users. For example, bank A transfers $1M to a different bank B and that amount is actually a sum of multiple users making transfers to bank B. Commercial banks can then enforce regulatory rules locally within their ledgers. Our system is in production with one of the largest clearing houses in the world and is currently being explored in a CBDC pilot.

In this work, we introduce an upgrade to Rayls, a novel central bank digital currency (CBDC) design that provides privacy, high performance, and regulatory compliance. In the Rayls construction, commercial banks each run their own (private) ledger and are connected to an underlying decentralized programmable blockchain via a relayer. We introduce an improved and more efficient protocol that allows for efficient anonymous transactions between banks, which is (still) called Enygma. Our design is 'quantum-private' as a quantum adversary is not able to infer any information (i.e., payer, payee, amounts) about the transactions that take place in the network. One of the main improvements of this work is that the design is now completely quantum-secure except for the current use of ZK-SNARKs. We note, however, that this is modular and can simply be updated as desired. We achieve high performance in cross-bank settlement via the use of ZK-SNARKs and 'double' batching and an optimized ZK implementation, with a prover time three times faster than the initial implementation and a cheaper on-chain verifier. Our transactions consist of a set of commitments and a zero-knowledge proof. As a result, each transaction can pay more than 1 bank at once and, secondly, each of these individual commitments can contain aggregated transfers from multiple users. For example, bank A transfers $1M to a different bank B and that amount is actually a sum of multiple users making transfers to bank B. Commercial banks can then enforce regulatory rules locally within their ledgers. Our system is in production with one of the largest clearing houses in the world and is currently being explored in a CBDC pilot.

Hashing to elliptic curve groups is a fundamental operation used in many cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, they are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs, while BLS signatures are used in proof of stake protocols. In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly such that one can efficiently generate succinct proofs of correctness. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs. We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports non-deterministic map-to-curve choices making them more efficient in constraint programming frameworks and enabling efficient integration into zero-knowledge proofs. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM). Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over $23\times$ fewer constraints than the best hash-to-elliptic-curve-group alternatives, and, enables $50$-$100\times$ faster proving times at scale.

Provable security is a cornerstone of modern cryptography, aiming to provide formal and precise security guarantees. However, for various reasons, security proofs are not always properly verified, possibly leading to unwarranted security claims and, in the worst case, deployment of insecure constructions. To further enhance trust and assurance, machine-checked cryptography makes these proofs more formal and rigorous. Unfortunately, the complexity of writing machine-verifiable proofs remains prohibitively high in many interesting use-cases. In this paper, we investigate the sources of this complexity, specifically examining how the style of security definitions influences the difficulty of constructing machine-verifiable proofs in the context of game-playing security. Concretely, we present a new security proof for the generic construction of a PKAE scheme from a NIKE and AE scheme, written in a code-based, game-playing style à la Bellare and Rogaway, and compare it to the same proof written in the style of state-separating proofs, a methodology for developing modular game-playing security proofs. Additionally, we explore a third “blended” style designed to avoid anticipated difficulties with the formalization. Our findings suggest that the choice of definition style impacts proof complexity—including, we argue, in detailed pen-and-paper proofs—with trade-offs depending on the proof writer’s goals.

Verifiable random access machines (vRAMs) serve as a foundational model for expressing complex computations with provable security guarantees, serving applications in areas such as secure electronic voting, financial auditing, and privacy-preserving smart contracts. However, no existing vRAM provides distributed obliviousness, a critical need in scenarios where multiple provers seek to prevent disclosure against both other provers and the verifiers, because existing solutions struggle with a paradigm mismatch between MPC and ZKP that limits the development of practical multi-prover ZKP front-ends. This gap arises because MPC protocols are optimized for minimal computation, whereas ZKPs require a complete trace for proving. Furthermore, adapting RAM designs is also challenging, as vRAMs are not built for the high costs of oblivious execution and existing DORAMs lack public verifiability. To address these challenges, we introduce CompatCircuit, the first multi-prover ZKP front-end implementation to our knowledge, designed to bridge this gap. CompatCircuit integrates collaborative zkSNARKs with novel MPC protocols, unifying computation and verification into a single compatible circuit paradigm. Building upon CompatCircuit, we present VDORAM, the first publicly verifiable distributed oblivious RAM. VDORAM reconciles the high communication latency of online MPC with the complexity of offline proof generation, resulting in a RAM design that balances these competing demands. We have implemented CompatCircuit and VDORAM in approximately 15,000 lines of code, demonstrating their practical feasibility through extensive experiments, including micro-benchmarks, comparative analysis, and program examples.

Clouds have replaced most local backup systems as they offer strong availability and reliability guarantees. Clouds, however, are not (and should not be) used as backup for cryptographic secrets. Cryptographic secrets might control financial assets (e.g., crypto wallets), hence, storing such secrets on the cloud corresponds to sharing ownership of the financial assets with the cloud, and makes the cloud a more attractive target for insider attacks. Can we have the best of the two worlds, where a user, Alice, can conveniently store a copy of her cryptographic secrets on the cloud and she is the only one who can recover them (without trusting any entity)? Can she do so even when she loses her devices and forgets all credentials, while at the same time retaining full ownership of her secrets? In this paper, we provide a cloud-based secret-recovery mechanism where confidentiality is always guaranteed when Alice has not lost her credentials, even in the presence of a malicious cloud. If Alice loses all her credentials, she can still recover her secrets (in most circumstances). This is in contrast with all previous work that relies on the assumption that Alice remembers some authentication secret. We prove our system secure in the Universally Composable framework. Further, we implement our protocols and evaluate their performance.

Fair multi-party coin toss protocols are fundamental to many cryptographic applications. While Cleve's celebrated result (STOC'86) showed that strong fairness is impossible against half-sized coalitions, recent works have explored a relaxed notion of fairness called Cooperative-Strategy-Proofness (CSP-fairness). CSP-fairness ensures that no coalition has an incentive to deviate from the protocol. Previous research has established the feasibility of CSP-fairness against majority-sized coalitions, but these results focused on specific preference structures where each player prefers exactly one outcome out of all possible choices. In contrast, real-world scenarios often involve players with more complicated preference structures, rather than simple binary choices. In this work, we initiate the study of CSP-fair multi-party coin toss protocols that accommodate arbitrary preference profiles, where each player may have an unstructured utility distribution over all possible outcomes. We demonstrate that CSP-fairness is attainable against majority-sized coalitions even under arbitrary preferences. In particular, we give the following results: \begin{itemize} \item We give a reduction from achieving CSP-fairness for arbitrary preference profiles to achieving CSP-fairness for structured split-bet profiles, where each player distributes the same amount of total utility across all outcomes. \item We present two CSP-fair protocols: (1) a \emph{size-based protocol}, which defends against majority-sized coalitions, and (2) a \emph{bets-based protocol}, which defends against coalitions controlling a majority of the total utilities. \item Additionally, we establish an impossibility result for CSP-fair binary coin toss with split-bet preferences, showing that our protocols are nearly optimal. \end{itemize}

Unprotected cryptographic implementations are vulnerable to implementation attacks, such as passive side-channel attacks and active fault injection attacks. Recently, countermeasures like polynomial masking and duplicated masking have been introduced to protect implementations against combined attacks that exploit leakage and faults simultaneously. While duplicated masking requires $O(t * e)$ shares to resist an adversary capable of probing $t$ values and faulting $e$ values, polynomial masking requires only $O(t + e)$ shares, which is particularly beneficial for affine computation. At CHES'$24$, Arnold et al. showed how to further improve the efficiency of polynomial masking in the presence of combined attacks by embedding two secrets into one polynomial sharing. This essentially reduces the complexity of previous constructions by half. The authors also observed that using techniques from packed secret sharing (Grosso et al., CHES'$13$) cannot easily achieve combined resilience to encode an arbitrary number of secrets in one polynomial encoding. In this work, we resolve these challenges and show that it is possible to embed an arbitrary number of secrets in one encoding and propose gadgets that are secure against combined attacks. We present two constructions that are generic and significantly improve the computational and randomness complexity of existing compilers, such as the laOla compiler presented by Berndt et al. at CRYPTO'$23$ and its improvement by Arnold et al. For example, for an AES evaluation that protects against $t$ probes and $e$ faults, we improve the randomness complexity of the state-of-the-art construction when $t+e>3$, leading to an improvement of up to a factor of $2.41$.

The inherent presence of large-scale quantum computers is deemed to threaten the traditional public-key cryptographic systems. As a result, NIST has necessitated the development of post-quantum cryptography (PQC) algorithms. Isogeny-based schemes have compact key sizes; however, there have been some fundamental vulnerabilities in the smooth-degree isogeny systems. Therefore, the literature has concentrated its efforts on higher-dimensional isogenies of non-smooth degrees. In this work, we present POKE-KEM, a key encapsulation mechanism (KEM) derived from the POKE public-key encryption (PKE) scheme via a Fujisaki-Okamoto (FO) transformation with its corresponding optimized security levels during transformation. Despite POKE’s efficiency advantages, its current formulation provides only IND-CPA security, limiting practical deployment where adaptive chosen-ciphertext security is essential. The resulting POKE-KEM construction achieves IND-CCA security under the computational hardness of the C-POKE problem in both the random oracle model (ROM) and quantum random oracle model (QROM). Our implementation demonstrates significant practical advantages across all NIST security levels (128, 192, and 256 bits), supporting the practical viability of POKE-KEM for post-quantum cryptographic deployments. We provide a comprehensive security analysis including formal proofs of correctness, rigidity, and IND-CCA security. Our underlying construction leverages the difficulty of recovering isogenies with unknown, non-smooth degrees, resistant to known quantum attacks