International Association
for Cryptologic Research

We study the round-complexity of secure multi-party computation (MPC) in the post-quantum regime where honest parties and communication channels are classical but the adversary can be a quantum machine. Our focus is on the $\mathit{fully}$ black-box setting where both the construction as well as the security reduction are black-box in nature. In this context, Chia, Chung, Liu, and Yamakawa [FOCS'22] demonstrated the infeasibility of achieving standard simulation-based security within constant rounds, unless $\mathbf{NP} \subseteq \mathbf{BQP}$. This outcome leaves crucial feasibility questions unresolved. Specifically, it remains unknown whether black-box constructions are achievable within polynomial rounds; additionally, the existence of constant-round constructions with respect to $\epsilon$-$\mathit{simulation}$, a relaxed yet useful alternative to the standard simulation notion, remains unestablished.

This work provides positive answers to the aforementioned questions. We introduce the first black-box construction for post-quantum MPC in polynomial rounds, from the minimal assumption of post-quantum semi-honest oblivious transfers. In the two-party scenario, our construction requires only $\omega(1)$ rounds. These results have already found application in the oracle separation between classical-communication quantum MPC and $\mathbf{P} = \mathbf{NP}$ in the recent work of Kretschmer, Qian, and Tal [STOC'25].

As for $\epsilon$-simulation, Chia, Chung, Liang, and Yamakawa [CRYPTO'22] resolved the issue for the two-party setting, leaving the general multi-party setting as an open question. We complete the picture by presenting the first black-box and constant-round construction in the multi-party setting. Our construction can be instantiated using various standard post-quantum primitives including lossy public-key encryption, linearly homomorphic public-key encryption, or dense cryptosystems.

En route, we obtain a black-box and constant-round post-quantum commitment that achieves a weaker version of the standard 1-many non-malleability, from the minimal assumption of post-quantum one-way functions. Besides its utility in our post-quantum MPC construction, this commitment scheme also reduces the assumption used in the lower bound of quantum parallel repetition recently established by Bostanci, Qian, Spooner, and Yuen [STOC'24]. We anticipate that it will find more applications in the future.

The rapid advancement of quantum computing has ushered in a new era of post-quantum cryptography, urgently demanding quantum-resistant digital signatures to secure modern communications and transactions. Among NIST-standardized candidates, Falcon—a compact lattice-based signature scheme—stands out for its suitability in size-sensitive applications. In this paper, we present cuFalcon, a high-throughput GPU implementation of Falcon that addresses its computational bottlenecks through adaptive parallel strategies. At the operational level, we optimize Falcon key components for GPU architectures through memory-efficient FFT, adaptive parallel ffSampling, and a compact computation mode. For signature-level optimization, we implement three versions of cuFalcon: the raw key version, the expanded key version, and the balanced version, which achieves a trade-off between efficiency and memory usage. Additionally, we design batch processing, streaming mechanisms, and memory pooling to handle multiple signature tasks efficiently. Ultimately, performance evaluations show significant improvements, with the raw key version achieving 172k signatures per second and the expanded key version reaching 201k. Compared to the raw key version, the balanced version achieves a 7% improvement in throughput, while compared to the expanded key version, it reduces memory usage by 70%. Furthermore, our raw key version implementation outperforms the reference implementation by 36.75 $\times$ and achieves a 2.94$\times$ speedup over the state-of-the-art GPU implementation.

In block ciphers, the attacker should not be able to distinguish a block cipher from a random permutation, making the existence of a distinguisher important. Cryptanalysis of the reduced-round variants of block ciphers is also important in cryptographic design. AES is the most widely used block cipher, and currently, the best-known distinguisher for 5-round AES has a data and time complexity of $2^{29.95}$ with a success probability of 55\%. In this paper, we propose the fully active exchanged boomerang and multiple exchanged boomerang distinguishers for 5-round AES, based on the retracing boomerang key-recovery attack. The fully active exchanged boomerang distinguisher utilizes the probability that either each byte of the diagonal of the returned plaintext pair is fully active, or the diagonal is inactive for all diagonals. This probability is very high, but we enhance it using the friends pair technique to distinguish a block cipher from a random permutation. The multiple exchanged boomerang distinguisher utilizes the fact that there are three trails where the probability of one diagonal of the returned plaintext pair being inactive is higher than the random probability, and one trail where it is equal to the random probability. This 5-round distinguisher has a complexity of $2^{27.08}$ and a success probability of 82\%, which represents a new best-known result for the secret-key distinguisher on 5-round AES.

Folding is a technique for building efficient succinct proof systems. Many existing folding protocols rely on the discrete-log based Pedersen commitment scheme, and are therefore not post-quantum secure and require a large (256-bit) field. Recently, Boneh and Chen constructed LatticeFold, a folding protocol using lattice-based commitments which is plausibly post-quantum secure and can operate with small (64-bit) fields. For knowledge soundness, LatticeFold requires the prover to provide a range proof on all the input witnesses using bit-decomposition, and this slows down the prover. In this work we present LatticeFold+, a very different lattice-based folding protocol that improves on LatticeFold in every respect: the prover is five to ten times faster, the verification circuit is simpler, and the folding proofs are shorter. To do so we develop two novel lattice techniques. First, we develop a new purely algebraic range proof which is much more efficient than the one in LatticeFold, and may be of independent interest. We further shrink the proof using double commitments (commitments of commitments). Second, we show how to fold statements about double commitments using a new sumcheck-based transformation.

Early stopping agreement protocols guarantee termination based on the actual number of malicious parties, $f \leq t$, encountered during execution, rather than assuming the worst-case scenario of $t

We introduce a general template for building garbled circuits with low communication, under the decisional composite residuosity (DCR) assumption. For the case of layered Boolean circuits, we can garble a circuit of size $s$ with communication proportional to $O(s/\log\log s)$ bits, plus an additive factor that is polynomial in the security parameter. For layered arithmetic circuits with $B$-bounded integer computation, we obtain a similar result: the garbled arithmetic circuit has size $O(s/\log\log s) \cdot (\lambda + \log B)$ bits, where $\lambda$ is the security parameter. These are the first constructions of general-purpose, garbled circuits with sublinear size, without relying on heavy tools like indistinguishability obfuscation or attribute-based and fully homomorphic encryption.

To achieve these results, our main technical tool is a new construction of a form of homomorphic secret sharing where some of the inputs are semi-private, that is, known to one of the evaluating parties. Through a new relinearisation technique that allows performing arbitrary additions and multiplications on semi-private shares, we build such an HSS scheme that supports evaluating any function of the form $C(x) \cdot C'(y)$, where $C$ is any polynomially-sized circuit applied to the semi-private input $y$, and $C'$ is a restricted-multiplication (or, NC1) circuit applied to the private input $x$. This significantly broadens the expressiveness of prior known HSS constructions.

We point out if assuming every local block appearing in the slide reduction algorithms [ALNS20] is `random' (as usual in the cryptographic background), then the combination of the slide reduction algorithms [ALNS20] and Pouly-Shen 's algorithm [PoSh24] yields exponentially faster provably correct algorithms for $\delta$-approximate SVP for all approximation factors $n^{1/2+\varepsilon} \leq \delta \leq n^{O(1)}$, which is the regime most relevant for cryptography.

$\textit{Linkable ring signatures}$ (LRS) allow a user to sign anonymously on behalf of a ring, while maintaining linkability—two signatures from the same signer are publicly identified, i.e., linked. This linkability makes LRS suitable to prevent double-voting in classical, $\textit{plurality}$ voting protocols—each voter casts one vote and the candidate with the most votes wins the election.

Several voting scenarios rely on (generalized) rules rather than plurality. For example, in $\textit{ranked voting}$, voters submit a ranking of the candidates, and the outcome is a function of these rankings. Such generalized voting rules are common in social choice theory, and have recently found their way into blockchain governance, e.g., for prioritizing (voting on) proposed (candidate) projects. However, unlike plurality voting, using LRS for voters to sign their votes (rankings) does not guarantee vote privacy as one can observe the rankings of each individual voter, which, depending on the scoring rule, is more information than what the outcome of the election offers.

We introduce $k$-$\textit{linkable ring signatures}$ ($k$-LRS) as a primitive for simultaneously achieving anonymity and privacy in generalized voting. A $k$-LRS scheme has the following properties: ($k$-)$\textit{Anonymity}$: a user can sign anonymously (on behalf of the ring) up to $k$ times, so that even an unbounded adversary cannot link his signatures. ($k$-)$\textit{Linkability}$: If any signer signs more than $k$ times, all his signatures are publicly linked $\textit{(individual $k$-linkability)}$; and, any set of $c$ signers cannot generate more than $k\cdot c$ unlinked signatures $\textit{(collective $k$-linkability)}$.

We provide two constructions of $k$-LRS: one is from the DDH, and the other is from SIS (hence post-quantum). Finally, we show how $k$-LRS can be applied to a broad range of voting rules, including $\textit{score voting}$, $\textit{multi-voting}$, and $\textit{Borda}$. Our protocols are non-interactive voting—each voter just posts a message on a bulletin board—which highlights the potential of $k$-LRS in blockchain-governance scenarios.

The rational secret sharing problem (RSS) considers incentivizing rational parties to share their received information to reconstruct a correctly shared secret. Halpern and Teague (STOC'04) demonstrate that solving the RSS problem deterministically with explicitly bounded runtime is impossible, if parties prefer learning the secret than not learning, and they prefer fewer other parties to learn.

To overcome this impossibility result, we propose RSS with competition. We consider a slightly different yet sensible preference profile: Each party prefers to learn the secret early and prefers fewer parties learning before them. This preference profile changes the information-hiding dynamics among parties in prior works: First, those who have learned the secret are indifferent towards or even prefer informing others later; second, the competition to learn the secret earlier among different access groups in the access structure facilitates information sharing inside an access group. As a result, we are able to construct the first deterministic RSS algorithm that terminates in at most two rounds. Additionally, our construction does not employ any cryptographic machinery (being fully game-theoretic and using the underlying secret-sharing scheme as a black-box) nor requires the knowledge of the parties' exact utility function. Furthermore, we consider general access structures.

This paper introduces a decentralized and leaderless sealed bid auction model for dynamic pricing of intents across blockchain networks. We leverage Multi-Party Computation (MPC) and Identity-Based Encryption (IBE) to improve pricing while ensuring fairness and decentralization. By addressing the vulnerabilities of current centralized or static pricing mechanisms, our approach fosters transparent, secure, and competitive price discovery. We further enhance the confidentiality of intents through Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Trusted Execution Environments (TEE). Our novel methodology mitigates the risks of frontrunning and centralization while preserving the rapid settlement times essential to decentralized finance (DeFi).

A $t$-out-of-$n$ robust non-interactive zero-knowledge (NIZK) combiner is a construction that, given access to $n$ candidate instantiations of a NIZK for some language, itself implements a NIZK for the same language. Moreover, the combiner is secure, assuming at least $t$ of the given candidates are secure. In this work, we provide the first definition of combiners for NIZK, and prove that no robust NIZK combiner exists assuming $t \le \lfloor n/2 \rfloor$ (unless the polynomial hierarchy collapses).

On the positive side, we provide different constructions of robust NIZK combiners for $t > \lfloor n/2 \rfloor$. In particular, we show how to obtain:

1) A black-box combiner working for a special class of {\em homomorphic} languages where $n,t$ are polynomial and $t > \lfloor n/2 \rfloor$.

2) A non-black-box combiner working for any language, where $n,t$ are constant and $t > \lfloor n/2 \rfloor$.

3) A non-black-box combiner working for any language, where $n,t$ are polynomial and $t > \lfloor 2n/3 \rfloor$.

We introduce DART, a fully anonymous, account-based payment system designed to address a comprehensive set of real-world considerations, including regulatory compliance, while achieving constant transaction size. DART supports multiple asset types, enabling users to issue on-chain assets such as tokenized real-world assets. It ensures confidentiality and anonymity by concealing asset types, transaction amounts, balances, and the identities of both senders and receivers, while guaranteeing unlinkability between transactions. Our design provides a mechanism for asset-specific auditing. Issuers can designate asset-specific auditors for the assets they issue, with the system preserving the privacy of the auditor’s identity to achieve asset type privacy. Only the designated auditor is authorized to decrypt transactions related to their associated asset, and users efficiently prove the association between the (hidden) asset type and the (hidden) designated auditor in their transactions.

DART supports non-interactive payments, allowing an online sender to submit a transaction even when the receiver is offline, while still incorporating a receiver affirmation mechanism that captures the real-world compliance consideration where the receiver must confirm (or deny) an incoming transaction. To the best of our knowledge, this is the first scheme of this kind in the permissionless setting. To accommodate all eventualities, DART also incorporates a reversibility mechanism, enabling senders to reclaim funds from pending transactions if the receiver’s affirmation is not yet provided. Finally, it offers a privacy-preserving proof of balance (per asset type) mechanism.

Our system achieves full anonymity while supporting concurrent incoming and outgoing transactions, resolving a common issue that plagues many account-based anonymous systems. We further demonstrate how our system supports multi-party transactions, allowing payment to multiple receivers in one transaction efficiently. We provide a full formal model in the Universal Composition (UC) setting, as well as a UC protocol realization.

Cryptographic proof systems enable a verifier to be convinced of of a computation's correctness without re-executing it; common efficiency requirements include both succinct proofs and fast verification. In this work we put forth the general study of cryptographic proof systems with sublinear proving time (after a preprocessing). Prior work has achieved sublinear proving only for limited computational settings (e.g., vector commitments and lookup arguments), relying on specific assumptions or through non-black-box use of cryptographic primitives. In this work we lift many of these limitations through the systematic study of a specific object: polynomial commitments (PC) with sublinear proving time, a choice motivated by the crucial role that PC play in the design of efficient cryptographic schemes. Our main result is a simple construction of a PC with sublinear prover based on any vector commitment scheme (VC) and any preprocessing technique for fast polynomial evaluation. We prove that this PC satisfies evaluation binding, which is the standard security notion for PC, and show how to expand our construction to achieve the stronger notion of knowledge soundness (extractability). The first application of our result is a construction of "index-efficient" SNARKs meaning that the prover is sublinear, after preprocessing, in the size of the index (i.e., the NP-relation describing the proven statement). Our main technical contribution is a method to transform a class of standard Polynomial Interactive Oracle Proofs (PIOPs) into index-efficient PIOPs. Our construction of index-efficient SNARKs makes black-box use of such index-efficient PIOPs and a PC with sublinear prover. As a corollary, this yields the first lookup argument for unstructured tables in which the prover is sublinear in the size of the table, while making only black-box use of a VC and thus allowing instantiations from generic assumptions such as collision-resistant hash functions. Prior lookup arguments with sublinear provers were only known with non-black-box use of cryptographic primitives, or from pairings. Finally, our last application is a transformation that builds UC-secure SNARKs from simulation-extractable ones, with an approximately linear overhead in proving time (as opposed to quadratic in prior work).

Password-Authenticated Key Exchange (PAKE) is a type of key exchange protocols secure against man-in-the-middle adversaries, in the setting where the two parties only agree upon a low-entropy "password" in advance. The first and arguably most well-studied PAKE protocol is Encrypted Key Exchange (EKE) (Bellovin and Marritt, 1992), and the standard security notion for PAKE is in the Universal Composability (UC) framework (Canetti et al., 2005). While the UC-security of EKE has been "folklore" knowledge for many years, a satisfactory formal proof has long been elusive.

In this work, we present a UC-security proof for the most common instantiation of EKE, which is based on hashed Diffie–Hellman. Our proof is in the random oracle + ideal cipher models, and under the computational Diffie–Hellman assumption. We thoroughly discuss the UC-security definition for PAKE, subtleties and pitfalls in the security proof, how to write a UC proof, and flaws in existing works; along the way we also present some philosophical discussions on security definitions and security proofs in general. In this way, we hope to draw attention to several understudied, underexplained or underappreciated aspects of the UC-security of EKE.

This tutorial can be viewed as a simplified version of the recent work by Januzelli, Roy and Xu (2025); however, we completely rewrite most of the materials there to make them much more approachable to beginners who have just learned the UC framework.

Indistinguishability obfuscation (iO) has seen remarkable theoretical progress, yet it remains impractical due to its high complexity and inefficiency. A common bottleneck in recent iO schemes is the reliance on bootstrapping techniques from functional encryption (FE) into iO, which requires recursively invoking the FE encryption algorithm for each input bit—creating a significant barrier to practical iO schemes.

In this work, we propose diamond iO, a new lattice-based iO construction that replaces the costly recursive encryption process with lightweight matrix operations. Our construction is proven secure under the learning with errors (LWE) and evasive LWE assumptions, as well as our new assumption—all-product LWE—in the pseudorandom oracle model. By leveraging the FE scheme for pseudorandom functionalities introduced by Agrawal et al. (ePrint’24) in a non-black-box manner, we remove the reliance on prior FE-to-iO bootstrapping techniques and thereby significantly reduce complexity. A remaining challenge is to reduce our new assumption to standard assumptions such as LWE, further advancing the goal of a practical and sound iO construction.

Can a sender commit to a long input without even reading all of it? Can a prover convince a verifier that an NP statement holds without even reading the entire witness? Can a set of parties run a multiparty computation (MPC) protocol in the RAM model, without necessarily even reading their entire inputs? We show how to construct such "doubly efficient" schemes in a setting where parties can preprocess their input offline, but subsequently they can engage in many different protocol executions over this input in sublinear online time. We do so in the plain model, without any common setup. Our constructions rely on doubly efficient private information retrieval (DEPIR) as a building block and can be instantiated based on Ring LWE.

In more detail, we begin by constructing doubly efficient (interactive) commitments, where the sender preprocesses the input offline, and can later commit to this input to arbitrary receivers in sublinear online time. Moreover, the sender can open individual bits of the committed input in sublinear time. We then use these commitments to implement doubly succinct (interactive) arguments, where the prover preprocesses the statement/witness offline, and can subsequently run many proof protocols to convince arbitrary verifiers of the statement's validity in sublinear online time. Furthermore, we augment these to get a doubly efficient "commit, prove and locally open" protocol, where the prover can commit to a long preprocessed input, prove that it satisfies some global property, and locally open individual bits, all in sublinear time. Finally, we leverage these tools to construct a RAM-MPC with malicious security in the plain model. Each party individually preprocesses its input offline, and can then run arbitrary MPC executions over this input with arbitrary other parties. The online run-time of each MPC execution is only proportional to the RAM run-time of the underlying program, that can be sublinear in the input size.

We study append-only set commitments with efficient updates and inclusion proofs, or cryptographic accumulators. In particular, we examine how often the inclusion proofs (or witnesses) for individual items must change as new items are added to the accumulated set. Using a compression argument, we show unconditionally that to accumulate a set of $n$ items, any construction with a succinct commitment ($O(\lambda \text{ polylog} \ n)$ storage) must induce at least $\omega(n)$ total witness updates as $n$ items are sequentially added. In a certain regime, we strengthen this bound to $\Omega(n \log n/\log \log n)$ total witness updates. These lower bounds hold not just in the worst case, but with overwhelming probability over a random choice of the accumulated set. Our results show that a close variant of the Merkle Mountain range, an elegant construction that has become popular in practice, is essentially optimal.

Anamorphic encryption (AE), introduced by Persiano, Phan and Yung at Eurocrypt 22, allows to establish secure communication in scenarios where users might be forced to hand over their decryption keys to some hostile authority. Over the last few years, several work have improved our understanding of the primitive by proposing novel realizations, new security notions and studying inherent limitations. This work makes progress, mainly, on this last line of research. We show concrete realizations of so-called Anamorphic Resistant Encryption (ARE, for short). These are (public key) encryption schemes that, provably, cannot be turned anamorphic. We also show that, under certain conditions, anamorphic encryption turns out to be equivalent to algorithm substitution attacks. This result allows to positively reinterpret our AREs as PKE schemes provably resistant to subversion attacks. To the best of our knowledge, these seem to be the first IND-CPA secure schemes that achieve subversion resistance without trust assumptions or non-black-box decomposition techniques. Our two AREs heavily rely, among other things, on a direct usage of extremely lossy functions: here the lossyness property is used in the constructions, rather than just in the proofs. The first construction is in the public parameters model and also requires iO. The second construction eliminates the need of both public parameters and iO, but is in the random oracle and relies on the novel concept of robust extremely lossy functions with group structure, a primitive that we define and (show how to) realize in this paper.

In this paper, we present a constant-round actively secure two-party computation protocol with small communication based on the ring learning with errors (RLWE) assumption with key-dependent message security. Our result builds on the recent BitGC protocol by Liu, Wang, Yang, and Yu (Eurocrypt 2025) with communication of one bit per gate for semi-honest security. First, we achieve a different manner of distributed garbling, where the global correlation is secret-shared among the two parties. The garbler always and only holds the garbled labels corresponding to the wire values when all inputs are zero, while the evaluator holds the labels corresponding to the real evaluation. In the second phase, we run an authentication protocol that requires some extra communication, which allows two parties to check the correct computation of each gate by treating the ciphertext as commitments, now that the global key is distributed. For layered circuits, the extra communication for authentication is $o(1)$ bits per gate, resulting in total communication of $1+o(1)$ bits per gate. For generic circuits, the extra communication cost can be $1$ bit per gate in the worst case, and thus, the total communication cost would be 2 bits per gate.

We show a generic compiler from KEM to (Universally Composable) PAKE in the Random Oracle Model (ROM) and without requiring an Ideal Cipher. The compiler is akin to Encrypted Key Exchange (EKE) by Bellovin-Merritt, but following the work of McQuoid et al. it uses only a 2-round Feistel to password-encrypt a KEM public key. The resulting PAKE incurs only insignificant cost overhead over the underlying KEM, and it is a secure UC PAKE if KEM is secure and key-anonymous under the Plaintext-Checking Attack (PCA).

Several KEM-to-PAKE compilers were shown recently, secure under the OW-PCA and ANO-PCA assumptions on KEM, but all used an Ideal Cipher in addition to ROM. While there are techniques for emulating ROM against quantum attackers, it is currently unknown how to extend many of such techniques to the Ideal Cipher Model. Consequently, doing without the Ideal Cipher in protocol design makes the resulting construction a more plausible candidate for post-quantum secure PAKE if instantiated with post-quantum PCA-secure and anonymous KEM, such as the ML-KEM standard itself.

Our construction and proofs build on many of the ideas underlying the KEM-to-PAKE compiler using 2-round Feistel given by McQuoid et al, but our protocol is more efficient and our proofs address limitations in the analysis therein.