ePrint Updates
LightNews LightNews
eprint.ing.bot
ePrint Updates
@eprint.ing.bot
1K followers 1 following 5.6K posts
Unofficial bot tracking the IACR Cryptology ePrint Archive (eprint.iacr.org). Maintained by @str4d.xyz.

Currently only posts about new papers. Author names are linkified to Bluesky accounts (cryptography.social); contact maintainer for inclusion/removal.
Posts Replies Media Videos
eprint.ing.bot
Linear Secret-shared Shuffle with Malicious Security (Samuel Dittmer, Rohit Nema, Rafail Ostrovsky) ia.cr/2025/2137
Abstract. Securely shuffling a secret-shared list is a vital sub-protocol in numerous applications, including secure sorting, secure list merging, secure graph proessing, oblivious RAM, and anonymous broadcast. We demonstrate how to convert the folklore constant-round protocol for secure shuffling, which employs a delegated Fisher-Yates shuffle using rerandomizable encryption, into a maliciously secure constant-round protocol. This gives the first protocol that has a linear end-to-end time for a two-party secret-shared shuffle with malicious security. We prove the security of our protocol under the “linear-only” assumption on the homomorphic encryption system. We also demonstrate that another assumption, namely weak predicability, is sufficient and that it is both weaker than the linear-only assumption and sufficient for security.
November 22, 2025 at 11:49 PM
eprint.ing.bot
The Latency Cost Of Censorship Resistance (Ittai Abraham, Yuval Efron, Ling Ren) ia.cr/2025/2136
Abstract. On the road to eliminating censorship from modern blockchain protocols, recent work in consensus has explored protocol design choices that delegate the duty of block assembly away from a single consensus leader and instead to multiple parties, referred to as includers. As opposed to the traditional leader-based approach, which guarantees transaction inclusion in a block produced by the next correct leader, the multiple includer approach allows blockchain protocols to provide a strong censorship-resistance property for users: A timely submitted transaction is guaranteed to be included in the next confirmed block, regardless of the leader’s behavior. Such a guarantee, however, comes at the cost of 2 additional rounds of latency to block confirmation, compared to the leader-based approach. Is this cost necessary? We introduce the Censorship Resistant Byzantine Broadcast (CRBB) problem, a one-shot variant that distills the core functionality underlying the multiple-includer design paradigm. We then provide a full characterization, both in synchrony and partial synchrony, of the achievable latency of CRBB in executions with a correct leader, which is the most relevant case to practice. Our main result is an inherent latency cost of two additional rounds compared to the classic Byzantine Broadcast (BB) problem. For example, synchronous protocols for CRBB require 4 rounds whenever BB requires 2 rounds. Similarly, up to a small constant in the resilience, partial synchrony protocols for CRBB require 5 rounds whenever BB requires 3 rounds. Image showing part 2 of abstract.
November 22, 2025 at 11:49 PM
eprint.ing.bot
Robust Elections and More: Fast MPC in the Preprocessing Model (Charanjit S. Jutla, Nathan Manohar, Arnab Roy) ia.cr/2025/2135
Abstract. In this paper, we present an MPC protocol in the preprocessing model with essentially the same concrete online communication and rounds as the state-of-the-art MPC protocols such as online-BGW (with precomputed Beaver tuples) for t < n/3 malicious corruptions. However, our protocol additionally guarantees robustness and correctness against up to t < n/2 malicious corruptions while the privacy threshold remains at n/3. This is particularly useful in settings (e.g. commodity/stock market auctions, national elections, IACR elections) where it is paramount that the correct outcome is certified, while maintaining the best possible online speed. In addition, this honest-majority correctness allows us to use optimistic Berlekamp-Welch decoding in contrast to BGW. Moreover, just like online-BGW, our protocol is responsive until a final attestation phase. We also give a complementary verifiable input-sharing scheme for the multi-client distributed-server setting which satisfies both robustness and correctness against up to t < n/2 malicious servers. This is accomplished by having the servers first run a preprocessing phase that does not involve the clients. The novelty of this input-sharing scheme is that a client only interacts for one round, and hence need not be online, which, again, is highly desirable in applications such as elections/auctions. We prove our results in the universally-composable model with statistical security against static corruptions. Our protocol is achieved by combining global authenticators of SPDZ with an augmented Reed-Solomon code in a novel manner. This augmented code enables honest-majority decoding of degree n/2 Reed-Solomon codes. Our particular augmentation (often referred to as robust sharing) has the additional property that the preprocessing phase can generate this augmented sharing with a factor n speedup over prior information-theoretic robust sharing schemes. Image showing part 2 of abstract.
November 22, 2025 at 11:49 PM
eprint.ing.bot
Non-Interactive Threshold Mercurial Signatures with Applications to Threshold DAC (Scott Griffy, Nicholas Jankovic, Anna Lysyanskaya, Arup Mondal) ia.cr/2025/2134
Abstract. In a mercurial signature, a signer signs a representative m of an equivalence class of messages on behalf of a representative pk of an equivalence class of public keys, receiving the signature σ. One can then transform σ into a signature σ′ on an equivalent (to m) message m′ under an equivalent (to pk) public key pk′. Mercurial signatures are helpful in constructing delegatable anonymous credentials: their privacy properties enable straightforward randomization of a credential chain, hiding the identity of each signer while preserving the authenticity of the overall credential. Unfortunately, without trusted setup, known constructions of mercurial signatures satisfy only a weak form of this privacy property. Specifically, an adversary who is responsible for a link in a delegation chain—and thus knows its corresponding secret key—will be able to recognize this link even after the chain has been randomized. To address this issue, Abe et al. (Asiacrypt 2024) proposed (interactive) threshold mercurial signatures (TMS), which remove the reliance on a single trusted signer by distributing the signing capability among multiple parties, none of whom knows the signing key. However, this contribution was far from practical, as it required the signers to interact with each other during the signing process. In this work, we define and realize non-interactive TMS, where each participant non-interactively computes its contribution to the threshold mercurial signature. Our construction also substantially reduces the overall communication complexity. It uses the mercurial signature scheme of Mir et al. (CCS 2023) as a starting point. Further, we introduce threshold delegatable anonymous credentials (TDAC) and use a non-interactive TMS to construct them. Image showing part 2 of abstract.
November 22, 2025 at 11:49 PM
eprint.ing.bot
Byzantine Broadcast with Unknown Participants (Wonseok Choi, Ran Cohen, Juan Garay, Nikos Skoumios, Vassilis Zikas) ia.cr/2025/2133
Abstract. A sender wishes to consistently broadcast a message on the dark web, so that whoever is around and active will agree on it even when the sender is malicious. No assumptions on the number of honest parties, or blockchain-style “tricks”—like balanced resource-allocation (e.g., hashing power or stake ownership)—can be made. The above is an instance of Byzantine broadcast (BB) in the unknown-participants setting (“UP Broadcast” for short). Despite four decades of extensive research on dishonest-majority BB, all existing approaches (e.g., the well-known Dolev-Strong protocol) fail to solve this problem, as they crucially rely on knowing the number of protocol participants—or the make blockchain-style assumptions on available resources. The challenge, which might appear as an inherent limitation, is that without any such assumption malicious parties can join the protocol at any point during its execution, making it arduous for other parties to terminate without violating consistency. So one might wonder: Is this even possible? In this work, we provide the first definitions of UP Broadcast that incorporate both static and dynamic participation and corruption of arbitrary many parties. Interestingly, even formally defining the problem turns out to be non-trivial as one needs to deviate from the model used in classical BB approaches. We then provide the strongest possible (and in our opinion, unexpected) answer to the above question: Yes, it is! We provide a polynomial-time deterministic UP Broadcast protocol. In the process we also solve UP Interactive Consistency, which corresponds to the multi-sender version of the problem. Our constructions are in the standard, synchronous model of protocol execution, and they offer consistency and validity guarantees to every party who is present throughout the protocol execution. We next turn to the question of round complexity and prove that our protocols are optimal against adversaries who can corrupt arbitrarily many parties; this optimality applies even to randomized protocols. Finally, we ask, what if parties join in the middle of the protocol execution? We provide a negative result for unrestricted dynamic participation; on the positive side, we devise definitions that offer best-possible guarantees (also to such “late” parties), and present corresponding constructions that remain round-optimal. Image showing part 2 of abstract. Image showing part 3 of abstract.
November 22, 2025 at 11:49 PM
eprint.ing.bot
Bandwidth Efficient Partial Authorized PSI (Tjitske Ollie Koster, Francesca Falzon, Evangelia Anna Markatou) ia.cr/2025/2132
Abstract. Recent attacks on private set intersection (PSI) and PSI-like protocols have demonstrated that input privacy can be compromised when parties maliciously choose their inputs, even in protocols proven secure against malicious adversaries. To counter such attacks, Authorized PSI (APSI) introduces a judge who authorizes the elements of the parties before the intersection is computed. Falzon and Markatou (PETS 2025) proposed Partial-APSI, a privacy-preserving variant of APSI that prevents revealing the entire set to a judge. Their Partial-APSI protocol requires significant bandwidth overhead due to the use of bilinear pairings and because the judge must sign each element in the input set. In this work, we present a bandwidth-efficient Partial-APSI protocol that outperforms Falzon and Markatou, both asymptotically and empirically. For example, for sets of size 2²⁰, we require around 21× less bandwidth and are about 6× faster over a LAN network. In addition to our protocol, we model the real-world behavior of rational parties through a game-theoretic analysis. We introduce payout mechanisms for detected cheating and establish lower bounds on their values, ensuring that the best strategy for rational parties is to provide honest input. Image showing part 2 of abstract.
November 22, 2025 at 11:49 PM
eprint.ing.bot
Persistent BitTorrent Trackers (Francois Xavier Wicht, Zhengwei Tong, Shunfan Zhou, Hang Yin, Aviv Yaish) ia.cr/2025/2131
Abstract. Private BitTorrent trackers enforce upload-to-download ratios to prevent free-riding, but suffer from three critical weaknesses: reputation cannot move between trackers, centralized servers create single points of failure, and upload statistics are self-reported and unverifiable. When a tracker shuts down (whether by operator choice, technical failure, or legal action) users lose their contribution history and cannot prove their standing to new communities. We address these problems by storing reputation in smart contracts and replacing self-reports with cryptographic attestations. Receiving peers sign receipts for transferred pieces, which the tracker aggregates and verifies before updating on-chain reputation. Trackers run in Trusted Execution Environments (TEEs) to guarantee correct aggregation and prevent manipulation of state. If a tracker is unavailable, peers use an authenticated Distributed Hash Table (DHT) for discovery: the on-chain reputation acts as a Public Key Infrastructure (PKI), so peers can verify each other and maintain access control without the tracker. This design persists reputation across tracker failures and makes it portable to new instances through single-hop migration in factory-deployed contracts. We formalize the security requirements, prove correctness under standard cryptographic assumptions, and evaluate a prototype on Intel TDX. Measurements show that transfer receipts adds less than 6% overhead with typical piece sizes, and signature aggregation speeds up verification by 2.5×. Image showing part 2 of abstract.
November 21, 2025 at 2:44 PM
eprint.ing.bot
Weightwise (almost) perfectly balanced functions: t-concatenation and the general Maiorana-McFarland class (Leyla Işık, René Rodríguez-Aldama, Ajla Šehović) ia.cr/2025/2130
Abstract. The study of cryptographic criteria for Boolean functions with restricted domains has been an important topic over the last 20 years. A revived interest has sparked after the work of Carlet, Méaux and Rotella in 2017, where the authors studied cryptographic properties of restricted-domain functions and introduced the concept of weightwise perfectly balanced functions as part of the analysis of the FLIP stream cipher. Weightwise (almost) perfectly balanced functions are defined as Boolean functions that are (almost) balanced on each of the sets of vectors of the same Hamming weight. Several approaches have been considered to build new families of such functions. In this article, we present some new constructions of weightwise (almost) perfectly balanced functions via two approaches, the first class is constructed using the t-concatenation of Boolean functions, whereas the second one draws certain functions from the so-called general Maiorana-McFarland class. A generic analysis of these two classes is given, as well as explicit examples in both classes. Namely, we provide instances of functions in both classes attaining high overall nonlinearities, as well as slice nonlinearities. Notably, we present examples in 16 variables that attain some of the best overall nonlinearities, and more importantly, the highest slice nonlinearities among all of the constructions presented in the literature. Image showing part 2 of abstract.
November 21, 2025 at 2:44 PM
eprint.ing.bot
Binding Security of Explicitly-Rejecting KEMs via Plaintext Confirmation and Robust PKEs (Juliane Krämer, Yannick Münz, Patrick Struck, Maximiliane Weishäupl) ia.cr/2025/2129
Abstract. We analyse the binding properties of explicitly-rejecting key-encapsulation mechanisms (KEMs) obtained by the Fujisaki-Okamoto (FO) transform. The framework for binding notions, introduced by [CDM24], generalises robustness and collision-freeness, and was motivated by the discovery of new types of attacks against KEMs. Implicitly-rejecting FO-KEMs have already been analysed with regards to the binding notions, with [KSW25b] providing the full picture. Binding notions for explicitly-rejecting FO-KEMs have been examined only partially, leaving several gaps. Moreover, the analysis of the explicit-rejection setting must account for additional binding notions that implicitly-rejecting KEMs cannot satisfy. We give mostly positive results for the explicitly-rejecting FO transform—though many notions require further robustness assumptions on the underlying PKE. We then show that the explicit FO transform with plaintext confirmation hash (HFO) achieves all notions and requires weaker robustness assumptions. Finally, we introduce a slightly modified version of the HFO transform that achieves all binding notions without requiring any robustness of the underlying PKE. Image showing part 2 of abstract.
November 21, 2025 at 2:29 PM
eprint.ing.bot
Refined Linear Approximations for ARX Ciphers and Their Application to ChaCha (Yurie Okada, Atsuki Nagai, Atsuko Miyaji) ia.cr/2025/2128
Abstract. ARX-based ciphers such as Salsa20 and ChaCha achieve high performance using only modular addition, rotation, and XOR. While ARX constructions are widely deployed in practice, linear and differential-linear cryptanalysis often reveal non-negligible biases in their reduced-round variants. Previous work has shown that a 7-round distinguisher on ChaCha is feasible, requiring about 2²¹⁴ operations and relying on a linear approximation with a theoretical bias of 2⁻⁵³. However, such theoretical approximations significantly deviate from experimental observations. In this work, we resolve these discrepancies by introducing new fundamental linear approximations for two consecutive additions over three independent variables. We rigorously derive the exact probabilities of these approximations, demonstrating that the conventional independence assumption leads to systematic errors in bias estimation. Applying our theorem to ChaCha, we refine the probabilities of key approximations used in previous attacks. Our refined estimates closely match experimentally observed biases, reducing the gap between theory and practice. These results provide a more accurate foundation for future differential-linear cryptanalysis of ChaCha and other ARX-based designs. Image showing part 2 of abstract.
November 21, 2025 at 2:29 PM
eprint.ing.bot
Censorship-Resistant Sealed-Bid Auctions on Blockchains (Orestis Alpos, Lioba Heimbach, Kartik Nayak, Sarisht Wadhwa) ia.cr/2025/2127
Abstract. Traditional commit-and-reveal mechanisms have been used to realize sealed-bid on-chain auctions. However, these leak timing information, impose inefficient participation costs – the inclusion fee to be paid for adding the transaction on-chain – and also require multiple slots to execute the auction. Recent research investigates single-slot auctions; however, it requires a high threshold of honest parties. We present a protocol that addresses these issues. Our design combines timestamp-based certificates with censorship resistance through inclusion lists. The resulting protocol satisfies four properties, the first being a strong hiding property which consists of Value Indistinguishability, Existential Obfuscation and User Obfuscation. This not only ensures that the adversary cannot differentiate between two value of bids (as the previously defined Hiding property does in Pranav et al. [MCP]), but also that the very existence of a bid and the identity of the bidder remain obfuscated. The second property is Short-Term Censorship Resistance, ensuring that, if the underlying blockchain outputs a block, then the auction would contain bids from all honest users. The third is a new property we introduce, Auction Participation Efficiency (APE), that measures how closely on-chain outcomes resemble classical auctions in terms of costs for participating users. And the fourth property is No Free Bid Withdrawal, which disallows committed bids from being withdrawn in case the bidder changes its mind. Together, these properties yield a fair, private, and economically robust auction primitive that can be integrated into any blockchain to support secure and efficient auction execution. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
eprint.ing.bot
DPaaS: Improving Decentralization by Removing Relays in Ethereum PBS (Chenyang Liu, Ittai Abraham, Matthew Lentz, Kartik Nayak) ia.cr/2025/2126
Abstract. Proposer-Builder Separation (PBS) in Ethereum improves decentralization and scalability by offloading block construction to specialized builders. In practice, MEV-Boost implements PBS via a side-car protocol with trusted relays between proposers and builders, resulting in increased centralization as well as security (e.g., block stealing) and performance concerns. We propose Decentralized Proposer-as-a-Service (DPaaS), a deployable architecture that eliminates centralized relays while preserving backward compatibility with Ethereum’s existing consensus layer. Our insight is that we can reduce centralized trust by distributing the combined roles of the proposer and relay to a set of Proposer Entities (PEs), each running in independent Trusted Execution Environments (TEEs). For compatibility, DPaaS presents itself to Ethereum as a single validator, leveraging threshold and aggregation properties of the BLS signature scheme used in Ethereum. At the same time, DPaaS protocols ensure fair exchange between builders and proposers even in the face of a small fraction of TEE failures or partial synchrony in networks. Our evaluation, deployed across four independent cloud hosts and driven by real-world traces, shows that DPaaS achieves less than 5 ms bid processing latency and 55.75 ms latency from the end of auction to block proposal – demonstrating that DPaaS can offer security and decentralization benefits while providing strong performance. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
eprint.ing.bot
Are ideal functionalities really ideal? (Myrto Arapinis, Véronique Cortier, Hubert de Groote, Charlie Jacomme, Steve Kremer) ia.cr/2025/2125
Abstract. Ideal functionalities are used to study increasingly complex protocols within the Universal Composability framework. However, such functionalities are often complex themselves, making it difficult to assess whether they truly fulfill their promises. In this paper, we present four attacks on functionalities from various applications (e-voting, SMPC, anonymous lotteries, and smart metering), demonstrating that they do not capture the intuitively expected properties. We argue that ideal functionalities should not merely be justified secure at a high level but rigorously proven to be so. To this end, we propose a methodology that combines game-based proofs and computer-aided verification: ideal functionalities can in fact be treated as protocols, and one can use traditional game-based proofs to study them, where any game-based security property proven on the functionality does transfer to any protocol that realizes it. We also propose fixed versions of the ideal functionalities we studied, and formally define the security properties they should satisfy through a game. Finally, using Squirrel, a proof assistant for protocol security, we formally prove that the fixed functionalities verify the specified game-based security properties. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
eprint.ing.bot
SALSAA – Sumcheck-Aided Lattice-based Succinct Arguments and Applications (Shuto Kuriyama, Russell W. F. Lai, Michał Osadnik, Lorenzo Tucci) ia.cr/2025/2124
Abstract. We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, “RoK, paper, SISsors (RPS)’’ and”RoK and Roll (RnR)’’ [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT’24, ’25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by 2-3× compared to the previous quasi-linear-time norm-check in RPS/RnR, eliminating a central performance bottleneck. The sumcheck integration also allows us to natively support a wider class of relations, including rank-1 constraint systems (R1CS), which are widely used to express real-world computations. To demonstrate the versatility and efficiency of our framework, we showcase three impactful applications achieved by different RoKs (Reductions of Knowledge) compositions: (i) a lattice-based succinct argument of knowledge with a linear-time prover, achieving a verifier time of 41 ms, prover runtime of 10.61 s, and proof size of 979 KB for a witness of 2²⁸ ℤ_(q) elements; (ii) a polynomial commitment scheme with matching performance; and (iii) the first lattice-based folding scheme natively operating on ℓ₂-norm-bounded witnesses, achieving highly efficient verification in 2.28 ms and producing a proof of just 73 KB for a witness of 2²⁸ Z_(q) elements, outperforming prior works for the family of linear relations. We provide a modular, concretely efficient Rust implementation of our framework, benchmarked over cyclotomic rings with AVX-512-accelerated NTT-based arithmetic, demonstrating the practical efficiency of our approach. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
eprint.ing.bot
Dictators? Friends? Forgers. Breaking and Fixing Unforgeability Definitions for Anamorphic Signature Schemes (Joseph Jaeger, Roy Stracovsky) ia.cr/2025/2123
Abstract. Anamorphic signature schemes (KPPYZ, Crypto 2023) allow users to hide encrypted messages in signatures to allow covert communication in a hypothesized scenario where encryption is outlawed by a “dictator” but authentication is permitted. We enhance the security of anamorphic signatures by proposing two parallel notions of unforgeability which close gaps in existing security definitions. The first notion considers a dictator who wishes to forge anamorphic signatures. This notion patches a divide between the definition and a stated security goal of robustness (BGHMR, Eurocrypt 2024). We port two related BGHMR constructions to the signature scheme setting and demonstrate that, as presented, both of these and a construction from KPPYZ are insecure under an active dictator. However, two of the three can easily be modified to satisfy our definition. The second notion we propose considers a recipient who wishes to forge signatures. To motivate this notion, we identify a gap in an existing security definition from KPPYZ and present attacks that allow parties to be impersonated when using schemes erroneously deemed secure. We then formalize our new unforgeability definition to close this gap. Interestingly, while the new definition is only modestly different from the old one, the change introduces subtle technical challenges that arise when proving security. We overcome these challenges in our reanalysis of existing anamorphic signature schemes by showing they achieve our new notion when built from chosen-randomness secure signatures or with encryption that satisfies a novel ideal-model simulatability property. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
eprint.ing.bot
Adaptive Security for Constrained PRFs (Kaishuo Cheng, Joseph Jaeger) ia.cr/2025/2122
Abstract. There is a gap between the security of constrained PRFs required in some applications and the security provided by existing definitions. This gap is typically patched by only considering nonadaptive security or manually mixing the CPRF with a random oracle (implicitly constructing a new CPRF) to achieve adaptive security. We fill this gap with a new definition for constrained PRFs with strong adaptive security properties and proofs that it is achieved by practical constructions based on the cascade PRF (which generalizes the GGM construction) and AMAC. We apply the definition for analyzing searchable symmetric encryption and puncturable key wrapping.
November 21, 2025 at 2:28 PM
eprint.ing.bot
Generic and Algebraic Computation Models: When AGM Proofs Transfer to the GGM (Joseph Jaeger, Deep Inder Mohan) ia.cr/2025/2121
Abstract. The Fuchsbauer, Kiltz, and Loss (CRYPTO 2018) claim that (some) hardness results in the algebraic group model imply the same hardness results in the generic group model was recently called into question by Katz, Zhang, and Zhou (ASIACRYPT 2022). The latter gave an interpretation of the claim under which it is incorrect. We give an alternate interpretation under which it is correct, using natural frameworks for capturing generic and algebraic models for arbitrary algebraic structures. Most algebraic analyses in the literature can be captured by our frameworks, making the claim correct for them.
November 21, 2025 at 2:28 PM
eprint.ing.bot
Language-Agnostic Detection of Computation-Constraint Inconsistencies in ZKP Programs via Value Inference (Arman Kolozyan, Bram Vandenbogaerde, Janwillem Swalens, Lode Hoste, Stefanos Chaliasos, Coen De Roover) ia.cr/2025/2120
Abstract. Zero-knowledge proofs (ZKPs) allow a prover to convince a verifier of a statement’s truth without revealing any other information. In recent years, ZKPs have matured into a practical technology underpinning major applications. However, implementing ZKP programs remains challenging, as they operate over arithmetic circuits that encode the logic of both the prover and the verifier. Therefore, developers must not only express the computations for generating proofs, but also explicitly specify the constraints for verification. As recent studies have shown, this decoupling may lead to critical ZKP-specific vulnerabilities. Unfortunately, existing tools for detecting them are limited, as they: (1) are tightly coupled to specific ZKP languages, (2) are confined to the constraint level, preventing reasoning about the underlying computations, (3) target only a narrow class of bugs, and (4) suffer from scalability bottlenecks due to reliance on SMT solvers. To address these limitations, we propose a language-agnostic formal model, called the Domain Consistency Model (DCM), which captures the relationship between computations and constraints. Using this model, we provide a taxonomy of vulnerabilities based on computation-constraint mismatches, including novel subclasses overlooked by existing models. Next, we implement a lightweight automated bug detection tool, called CCC-Check, which is based on abstract interpretation. We evaluate CCC-Check on a dataset of 20 benchmark programs. Compared to the SoTA verification tool CIVER, our tool achieves a 100-1000× speedup, while maintaining a low false positive rate. Finally, using the DCM, we examine six widely adopted ZKP projects and uncover 15 previously unknown vulnerabilities. We reported these bugs to the projects’ maintainers, 13 of which have since been patched. Of these 15 vulnerabilities, 12 could not be captured by existing models. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
eprint.ing.bot
Twinkle: A family of Low-latency Schemes for Authenticated Encryption and Pointer Authentication (Jianhua Wang, Tao Huang, Shuang Wu, Zilong Liu) ia.cr/2025/2119
Abstract. In this paper, we aim to explore the design of low-latency authenticated encryption schemes particularly for memory encryption, with a focus on the temporal uniqueness property. To achieve this, we present the low-latency Pseudo-Random Function (PRF) called Twinkle with an output up to 1152 bits. Leveraging only one block of Twinkle, we developed Twinkle-AE, a specialized authenticated encryption scheme with six variants covering different cache line sizes and security requirements. We also propose Twinkle-PA, a pointer authentication algorithm, which takes a 64-bit pointer and 64-bit context as input and outputs a tag of 1 to 32 bits. We conducted thorough security evaluations of both the PRFs and these schemes, examining their robustness against various common attacks. The results of our cryptanalysis indicate that these designs successfully achieve their targeted security objectives. Hardware implementations using the FreePDK45nm library show that Twinkle-AE achieves an encryption and authentication latency of 3.83 ns for a cache line. In comparison, AES-CTR with WC-MAC scheme and Ascon-128a achieve latencies of 9.78 ns and 27.30 ns, respectively. For the pointer authentication scheme Twinkle-PA, the latency is 2.04 ns, while QARMA-64-σ₀ has a latency of 5.57 ns. Image showing part 2 of abstract.
November 21, 2025 at 2:27 PM
eprint.ing.bot
Revisiting Rational Broadcast Protocols (Shunya Otomo, Kenji Yasunaga) ia.cr/2025/2118
Abstract. A recent study by Yamashita and Yasunaga (GameSec 2023) presented a constant-round deterministic broadcast protocol secure against adversaries — those who prefer to attack without being detected. In this work, we revisit their protocol and observe that it remains secure even against a broader class of adversaries, not necessarily detection-averse. We formalize its detection mechanism as and construct broadcast protocols with local detectability that address two weaknesses of the original protocol: (1) it only guarantees weak validity, and (2) it may cause false detections. Our first protocol achieves round complexity four against rational adversaries and t + 4 against malicious adversaries, where the adversary corrupts at most t parties. Our second protocol achieves the optimal round complexity of t + 1 for malicious adversaries, while the round complexity is four against detection-averse adversaries.
November 21, 2025 at 2:27 PM
eprint.ing.bot
Revisiting Simulation Extractability in the Updatable Setting (Hamidreza Khoshakhlagh) ia.cr/2025/2117
Abstract. We revisit the notion of Simulation Extractability (SE) for SNARKs in the updatable setting. We demonstrate that existing formal definitions of SE in this setting are insufficient to guarantee the required non-malleability in real-world scenarios. Towards this, we first identify and frame a malleability vulnerability: a cross-SRS reinterpretation attack, which shows that an adversary can reuse or maul proofs across different, correlated SRSs generated through the update procedure. This is made possible because existing security definitions fail to model an adversary’s ability to observe simulated proofs relative to various derived SRSs. To close this security gap, we propose a revised and stronger security notion of Updatable Simulation Extractability (USE) which was originally defined in [GKK+22]. Our definition models a dynamic environment where the SRS is adaptively updatable by the adversary, who can also query simulation oracles for proofs under the resulting family of reachable SRSs. This captures the full extent of the adversarial capabilities observed in practice. Finally, we provide positive results for popular polynomial-IOP-based SNARKs, and show that these schemes satisfy our stronger USE notion, provided the circuit-specific SRS is securely bound into the proof transcript, e.g., via a correct implementation of the Fiat-Shamir transformation. Image showing part 2 of abstract.
November 21, 2025 at 2:12 PM
eprint.ing.bot
Oblivious Batch Updates for Bloom-Filter-based Outsourced Cryptographic Protocols (Marten van Dijk, Dandan Yuan) ia.cr/2025/2116
Abstract. In this work, we initiate the formal study of oblivious batch updates over outsourced encrypted Bloom filters, focusing on scenarios where a storage-limited sender must insert or delete batches of elements in a Bloom filter maintained on an untrusted server. Our survey identifies only two prior approaches (CCS 2008 and CCS 2012) that can be adapted to this problem. However, they either fail to provide adequate security in dynamic scenarios or incur prohibitive update costs that scale with the filter’s maximum capacity rather than the actual batch size. To address these limitations, we introduce a new cryptographic primitive, Oblivious Bloom Filter Insertion (OBFI), and propose novel constructions. At the core of our design is a novel building block, Oblivious Bucket Distribution (OBD), which enables a storage-limited sender to distribute a large array of elements, uniformly sampled from a finite domain, into small, fixed-size buckets in a data-oblivious manner determined by element order. The design of OBD is further supported by identifying and proving a new structural property of such arrays, which establishes tight and explicit probabilistic bounds on the number of elements falling within predefined subranges of the domain. Our OBFI constructions achieve adaptive data-obliviousness and ensure that batch update costs scale primarily with the batch size. Depending on the variant, the sender’s storage requirement ranges from O(λ), where λ is the security parameter, down to O(1). Finally, we demonstrate the practicality of OBFI by integrating it into representative Bloom-filter-based cryptographic protocols for Searchable Symmetric Encryption, Public-key Encryption with Keyword Search, and Outsourced Private Set Intersection, thereby obtaining batch-updatable counterparts with state-of-the-art security and performance. Image showing part 2 of abstract.
November 19, 2025 at 7:02 AM
eprint.ing.bot
Weighted Batched Threshold Encryption with Applications to Mempool Privacy (Amit Agarwal, Kushal Babel, Sourav Das, Babak Poorebrahim Gilkalaye, Arup Mondal, Benny Pinkas, Peter Rindal, Aayush Yadav) ia.cr/2025/2115
Abstract. A Batched Threshold Encryption (BTE) scheme enables a committee of servers to perform a lightweight (in terms of communication and computation) threshold decryption of an arbitrary batch of ciphertexts from a larger pool, while ensuring the privacy of ciphertexts that are outside the batch. Such a primitive has a direct application in designing encrypted mempools for MEV protection in modern blockchains. Bormet et al. (USENIX 2025) recently proposed a BTE scheme called “BEAT-MEV” which is concretely efficient for small to moderate batch sizes. In this work, we improve and extend the BEAT-MEV scheme in multiple ways. First, we improve the computational cost from quadratic to quasilinear in the batch size, thus making it practical for large batch sizes. This improvement is achieved by substituting the key-homomorphic punctured PRF used in BEAT-MEV with an FFT-friendly alternative. Second, we extend the ideas in their scheme to the weighted setting, where each server in the committee has an associated ‘weight’ value (e.g., stake weight of validators in PoS blockchains), while crucially ensuring that the communication cost remains independent of the weights. In contrast, BEAT-MEV with naive virtualization would incur communication cost linear in the total weight. Third, for handling the small failure rate inherent in BEAT-MEV scheme due to index collisions across different clients at the time of encryption, we propose a generalization of their suggested approach which offers an option to trade off between ciphertext size and server communication for a given failure rate. We implement and evaluate our scheme and compare it with BEAT-MEV to demonstrate our concrete improvement. In the unweighted setting, we improve the computational cost (without increasing the communication cost) by ≈ 6× for a batch size of 512 ciphertexts. In the weighted setting, we improve the communication cost (without compromising computation time), over BEAT-MEV with naive virtualization, by ≈ 50× for 100 validators with total stake weight 5000 distributed as per the latest Solana stake distribution. Image showing part 2 of abstract.
November 19, 2025 at 7:02 AM
eprint.ing.bot
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits (Hanlin Ren, Yichuan Wang, Yan Zhong) ia.cr/2025/2114
Abstract. Given a circuit G : {0, 1}^(n) → {0, 1}^(m) with m > n, the range avoidance problem (Avoid) asks to output a string y ∈ {0, 1}^(m) that is not in the range of G. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related to the existence of proof complexity generators — circuits G : {0, 1}^(n) → {0, 1}^(m) where m > n but for every y ∈ {0, 1}^(m), it is infeasible to prove the statement “y ∉ Range(G)” in a given propositional proof system. This paper connects these two problems with the existence of demi-bits generators, a fundamental cryptographic primitive against nondeterministic adversaries introduced by Rudich (RANDOM ’97). • We show that the existence of demi-bits generators implies Avoid is hard for nondeterministic algorithms. This resolves an open problem raised by Chen and Li (STOC ’24). Furthermore, assuming the demi-hardness of certain LPN-style generators or Goldreich’s PRG, we prove the hardness of Avoid even when the instances are constant-degree polynomials over 𝔽₂. • We show that the dual weak pigeonhole principle is unprovable in Cook’s theory PV₁ under the existence of demi-bits generators secure against AM/_(O(1)), thereby separating Jeřábek’s theory APC₁ from PV₁. Previously, Ilango, Li, and Williams (STOC ’23) obtained the same separation under different (and arguably stronger) cryptographic assumptions. • We transform demi-bits generators to proof complexity generators that are pseudo-surjective in certain parameter regime. Pseudo-surjectivity is the strongest form of hardness considered in the literature for proof complexity generators. Our constructions are inspired by the recent breakthroughs on the hardness of Avoid by Ilango, Li, and Williams (STOC ’23) and Chen and Li (STOC ’24). We use randomness extractors to significantly simplify the construction and the proof. Image showing part 2 of abstract.
November 19, 2025 at 7:02 AM
eprint.ing.bot
Single-Server Private Outsourcing of zk-SNARKs (Kasra Abbaszadeh, Hossein Hafezi, Jonathan Katz, Sarah Meiklejohn) ia.cr/2025/2113
Abstract. Succinct zero-knowledge arguments (zk-SNARKs) enable a prover to convince a verifier of the truth of a statement via a succinct and efficiently verifiable proof without revealing any additional information about the secret witness. A barrier to practical deployment of zk-SNARKs is their high proving cost. With this motivation, we study server-aided zk-SNARKs, where a client/prover outsources most of its work to a single, untrusted server while the server learns nothing about the witness or even the proof. We formalize this notion and show how to realize server-aided proving for widely deployed zk-SNARKs, including Nova, Groth16, and Plonk. The key building block underlying our designs is a new primitive, encrypted multi-scalar multiplication (EMSM), that enables private delegation of multi-scalar multiplications (MSMs). We construct an EMSM from variants of the learning parity with noise assumption in which the client does O(1) group operations, while the server’s work matches that of the plaintext MSM. We implement and evaluate our constructions. Compared to local proving, our techniques lower the client’s computation by up to 20× and reduce the proving latency by up to 9×. Image showing part 2 of abstract.
November 19, 2025 at 6:46 AM