[continued from previous message]
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.
## 2025/233
* Title: Anamorphic Resistant Encryption: the Good, the Bad and the Ugly
* Authors: Davide Carnemolla, Dario Catalano, Emanuele Giunta, Francesco Migliaro
* [Permalink](
https://eprint.iacr.org/2025/233)
* [Download](
https://eprint.iacr.org/2025/233.pdf)
### Abstract
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.
## 2025/234
* Title: Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators
* Authors: Joseph Bonneau, Jessica Chen, Miranda Christ, Ioanna Karantaidou
* [Permalink](
https://eprint.iacr.org/2025/234)
* [Download](
https://eprint.iacr.org/2025/234.pdf)
### Abstract
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.
## 2025/235
* Title: Doubly Efficient Cryptography: Commitments, Arguments and RAM MPC
* Authors: Wei-Kai Lin, Ethan Mook, Daniel Wichs
* [Permalink](
https://eprint.iacr.org/2025/235)
* [Download](
https://eprint.iacr.org/2025/235.pdf)
### Abstract
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.
## 2025/236
* Title: Diamond iO: A Straightforward Construction of Indistinguishability Obfuscation from Lattices
* Authors: Sora Suegami, Enrico Bottazzi
* [Permalink](
https://eprint.iacr.org/2025/236)
* [Download](
https://eprint.iacr.org/2025/236.pdf)
### Abstract
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.
## 2025/237
* Title: UC-Security of Encrypted Key Exchange: A Tutorial
* Authors: Jiayu Xu
* [Permalink](
https://eprint.iacr.org/2025/237)
* [Download](
https://eprint.iacr.org/2025/237.pdf)
### Abstract
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.
## 2025/238
* Title: On the Power of Polynomial Preprocessing: Proving Computations in Sublinear Time, and More
* Authors: Matteo Campanelli, Mario Carrillo, Ignacio Cascudo, Dario Fiore, Danilo Francati, Rosario Gennaro
* [Permalink](
https://eprint.iacr.org/2025/238)
* [Download](
https://eprint.iacr.org/2025/238.pdf)
### Abstract
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).
## 2025/239
* Title: DART: Decentralized, Anonymous, and Regulation-friendly Tokenization
* Authors: Amirreza Sarencheh, Hamidreza Khoshakhlagh, Alireza Kavousi, Aggelos Kiayias
* [Permalink](
https://eprint.iacr.org/2025/239)
* [Download](
https://eprint.iacr.org/2025/239.pdf)
### Abstract
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.
## 2025/240
* Title: Robust Non-Interactive Zero-Knowledge Combiners
* Authors: Michele Ciampi, Lorenzo Magliocco, Daniele Venturi, Yu Xia
* [Permalink](
https://eprint.iacr.org/2025/240)
* [Download](
https://eprint.iacr.org/2025/240.pdf)
### Abstract
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$.
## 2025/241
* Title: IBE-IBE: Intent-Based Execution through Identity-Based Encryption and Auctions
* Authors: Peyman Momeni, Fig Smith
* [Permalink](
https://eprint.iacr.org/2025/241)
* [Download](
https://eprint.iacr.org/2025/241.pdf)
### Abstract
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).
## 2025/242
* Title: Rational Secret Sharing with Competition
* Authors: Tiantian Gong, Zeyu Liu
* [Permalink](
https://eprint.iacr.org/2025/242)
* [Download](
https://eprint.iacr.org/2025/242.pdf)
### Abstract
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.
## 2025/243
* Title: K-Linkable Ring Signatures and Applications in Generalized Voting
* Authors: Wonseok Choi, Xinagyu Liu, Lirong Xia, Vassilis Zikas
* [Permalink](
https://eprint.iacr.org/2025/243)
* [Download](
https://eprint.iacr.org/2025/243.pdf)
### Abstract
$\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.
## 2025/244
* Title: Provable Speedups for SVP Approximation Under Random Local Blocks
* Authors: Jianwei Li
* [Permalink](
https://eprint.iacr.org/2025/244)
* [Download](
https://eprint.iacr.org/2025/244.pdf)
### Abstract
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.
## 2025/245
* Title: Silent Circuit Relinearisation: Sublinear-Size (Boolean and Arithmetic) Garbled Circuits from DCR
* Authors: Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
* [Permalink](
https://eprint.iacr.org/2025/245)
* [Download](
https://eprint.iacr.org/2025/245.pdf)
### Abstract
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.
## 2025/246
* Title: Towards Optimal Early Stopping Agreement Protocols
* Authors: Fatima Elsheimy, Julian Loss, Charalampos Papamanthou
* [Permalink](
https://eprint.iacr.org/2025/246)
* [Download](
https://eprint.iacr.org/2025/246.pdf)
### Abstract
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<n$ many corruptions. The lower bound on the round
complexity for such protocols is known to be $\min\{f+2, t+1\}$ many rounds. In this work, we substantially improve the state of the art for cryptographic early stopping protocols in the honest majority setting where $t<n/2$. In this scenario, the best
known protocol due to Elsheimy, Loss, and Papamanthou (ASIACRYPT `24) achieves a round complexity of $(1+\epsilon)\cdot f$ for some constant $0<\epsilon<1$. We begin by introducing an improvement to the Elsheimy et al. approach which can be used to
obtain the first polynomial-time early stopping agreement protocols in the $t<n/2$ corruption regime which achieve a complexity of $f+O(\sqrt{f})$. We then instantiate our generic framework with refined components to obtain a very concretely efficient
protocol with a round complexity of only $f + 6\lceil\sqrt{f}\rceil+6$ and polynomial communication complexity. Finally, we show that it is possible to come within one round of the optimal round complexity by presenting a broadcast protocol based on the
exponential information gathering approach, which achieves a round complexity of $\min\{f + 3, t + 1\}$, albeit with exponential communication complexity.
## 2025/247
* Title: LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems
* Authors: Dan Boneh, Binyi Chen
* [Permalink](
https://eprint.iacr.org/2025/247)
* [Download](
https://eprint.iacr.org/2025/247.pdf)
### Abstract
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.
## 2025/248
* Title: New Exchanged Boomerang Distinguishers for 5-Round AES
* Authors: Hanbeom Shin, Seonkyu Kim, Dongjae Lee, Deukjo Hong, Jaechul Sung, Seokhie Hong
* [Permalink](
https://eprint.iacr.org/2025/248)
* [Download](
https://eprint.iacr.org/2025/248.pdf)
### Abstract
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.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)