From Newsgroup: sci.crypt

## In this issue
1. [2023/219] Sieving for large twin smooth integers using single ...
2. [2025/884] $k$-out-of-$n$ Proofs and Application to Privacy- ...
3. [2025/1602] Attacks on PRISM-id via Torsion over Small ...
4. [2025/2108] The Grain Family of Stream Ciphers: an Abstraction, ...
5. [2025/2109] Secure Lookup Tables: Faster, Leaner, and More General
6. [2025/2110] A note on mutual correlated agreement for Reed- ...
7. [2025/2111] SoK: Secure Computation over Secret Shares
8. [2025/2112] Sharing the Mask: TFHE bootstrapping on Packed Messages
9. [2025/2113] Single-Server Private Outsourcing of zk-SNARKs
10. [2025/2114] Hardness of Range Avoidance and Proof Complexity ...
11. [2025/2115] Weighted Batched Threshold Encryption with ...
12. [2025/2116] Oblivious Batch Updates for Bloom-Filter-based ...
13. [2025/2117] Revisiting Simulation Extractability in the ...
14. [2025/2118] Revisiting Rational Broadcast Protocols
15. [2025/2119] Twinkle: A family of Low-latency Schemes for ...
16. [2025/2120] Language-Agnostic Detection of Computation- ...
17. [2025/2121] Generic and Algebraic Computation Models: When AGM ...
18. [2025/2122] Adaptive Security for Constrained PRFs
19. [2025/2123] Dictators? Friends? Forgers. Breaking and Fixing ...
20. [2025/2124] SALSAA rCo Sumcheck-Aided Lattice-based Succinct ...
21. [2025/2125] Are ideal functionalities really ideal?
22. [2025/2126] DPaaS: Improving Decentralization by Removing ...
23. [2025/2127] Censorship-Resistant Sealed-Bid Auctions on Blockchains
24. [2025/2129] Binding Security of Explicitly-Rejecting KEMs via ...
25. [2025/2130] Weightwise (almost) perfectly balanced functions: ...
26. [2025/2131] Persistent BitTorrent Trackers
27. [2025/2132] Bandwidth Efficient Partial Authorized PSI
28. [2025/2133] Byzantine Broadcast with Unknown Participants
29. [2025/2134] Non-Interactive Threshold Mercurial Signatures with ...
30. [2025/2135] Robust Elections and More: Fast MPC in the ...
31. [2025/2136] The Latency Cost Of Censorship Resistance
32. [2025/2137] Linear Secret-shared Shuffle with Malicious Security
## 2023/219
* Title: Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott
* Authors: Knud Ahrens
* [Permalink](https://eprint.iacr.org/2023/219)
* [Download](https://eprint.iacr.org/2023/219.pdf)
### Abstract
In the isogeny-based track of post-quantum cryptography, optimal instances of the signature scheme SQISign rely on primes $p$ such that $p\pm1$ is smooth. In 2021 a new approach to find those numbers was discovered using solutions to the Prouhet-Tarry-Escott (PTE) problem. With these solutions we can sieve for smooth integers $A$ and $B$ with a difference of $|A-B|=C$ fixed by the solution. Then some $2A/C$ and $2B/C$ are smooth integers hopefully enclosing a prime. They took many different PTE solutions and combined them into a tree to process them more efficiently. But for larger numbers there are fewer promising PTE solutions so their advantage over the naive approach (checking a single solution at a time) fades.
For a single PTE solution the search can be optimised for the corresponding $C$ and allows to check smoothness only for those integers that are divisible by $C$. In this work we investigate such optimisations and show a significant speed-up compared to the naive approach - both heuristically and empirically. Along the way we compute the number of roots of a given polynomial modulo prime powers and give an upper bound for the number of roots modulo a composite number.
## 2025/884
* Title: $k$-out-of-$n$ Proofs and Application to Privacy-Preserving Cryptocurrencies
* Authors: Min Zhang, Yu Chen, Xiyuan Fu
* [Permalink](https://eprint.iacr.org/2025/884)
* [Download](https://eprint.iacr.org/2025/884.pdf)
### Abstract
Cryptocurrencies enable transactions among mutually distrustful users. While UTXO-based cryptocurrencies offer mature solutions achieving strong privacy and supporting multi-receiver transfers, account-based cryptocurrencies currently lack practical solutions that simultaneously guarantee these properties.
To close this gap, we propose a generic framework for account-based cryptocurrencies that attains strong privacy and supports multi-receiver transfers, and then give a practical instantiation called \textit{Anonymous PGC}. Our system also outperforms in efficiency: for a 64-sized anonymity set and 8 receivers, Anonymous PGC achieves 2.4$\times$ faster transaction generation, 5.7$\times$ faster verification, and 2.2$\times$ reduction in transaction size compared to state-of-the-art Anonymous Zether (IEEE S\&P 2021), which offers only weak privacy and no multi-receiver support.
At the core of Anonymous PGC are two novel zero-knowledge proofs of partial knowledge. First, we generalize the Groth-Kohlweiss (GK) $1$-out-of-$n$ proof (EUROCRYPT 2015) to the $k$-out-of-$n$ case, resolving an open problem regarding its generalization. Particularly, the obtained proof lends itself to seamlessly solder with range proofs, yielding an efficient $k$-out-of-$n$ range proof that demonstrates $k$ witnesses among $n$ instances lie in specific ranges. Second, we extend the Attema-Cramer-Fehr (ACF) $k$-out-of-$n$ proof (CRYPTO 2021) to support distinct group homomorphisms, boosting its expressiveness while slashing both prover and verifier complexities from quadratic to linear. We believe these proofs are of independent interest in broader privacy-preserving applications.
## 2025/1602
* Title: Attacks on PRISM-id via Torsion over Small Extension Fields
* Authors: Kohei Nakagawa, Hiroshi Onuki
* [Permalink](https://eprint.iacr.org/2025/1602)
* [Download](https://eprint.iacr.org/2025/1602.pdf)
### Abstract
PRISM is an isogeny-based cryptographic framework that relies on the hardness of computing a large prime-degree isogeny from a supersingular elliptic curve with an unknown endomorphism ring. It includes both an identification scheme PRISM-id and a signature scheme PRISM-sig. In this work, we present two attacks on PRISM-id. First, we analyze the probability that a randomly sampled prime $q$ in PRISM-id results in a $q$-torsion subgroup defined over a small extension field, and we show that this probability is higher than claimed in the original proposal. Exploiting this observation, we construct classical forgery attacks on PRISM-id. The first attack addresses the scenario in which the attacker cannot reject a challenge. It succeeds with probability $\tilde{\Theta}(2^{-(\lambda + \log\lambda)(1-\varepsilon)})$ and runs in expected time $\tilde{O}(\max\{2^{3\lambda\varepsilon}, 2^{\lambda(\varepsilon + 1/2)}\})$ for any positive real number $\varepsilon < 1/3$. Setting $\varepsilon = 1/4$ yields success probability $\tilde{\Theta}(2^{-3(\lambda + \log\lambda)/4})$ and expected time complexity $\tilde{O}(2^{3\lambda/4})$. The second forgery attack covers the scenario in which the attacker is allowed to reject challenges. It always succeeds and runs in expected time $\tilde{O}(2^{6\lambda/7})$. Finally, we describe an attack against the underlying hardness assumption of PRISM-id that runs in expected time $\tilde{O}(2^{\lambda/2})$. Note that our results do not affect the security of PRISM-sig.
## 2025/2108
* Title: The Grain Family of Stream Ciphers: an Abstraction, Strengthening of Components and New Concrete Instantiations
* Authors: Palash Sarkar
* [Permalink](https://eprint.iacr.org/2025/2108)
* [Download](https://eprint.iacr.org/2025/2108.pdf)
### Abstract
The first contribution of the paper is to put forward an abstract definition of the Grain family of stream ciphers which formalises the different components that are required to specify a particular member of the family. Our second contribution is to provide new and strengthened definitions of the components. These include definining new classes of nonlinear Boolean functions, improved definition of the state update function during initialisation, choice of the tap positions, and the possibility of the linear feedback shift register being smaller than the nonlinear feedback shift register. The third contribution of the paper is to put forward seven concrete proposals of stream ciphers by suitably instantiating the abstract family, one at the 80-bit security level, and two each at the 128-bit, 192-bit, and the 256-bit security levels. At the 80-bit security level, compared to the well known Grain~v1, the new proposal uses Boolean functions with improved cryptographic properties \textit{and} an overall lower gate count. At the 128-bit level, compared to ISO/IEC standard Grain-128a, the new proposals use Boolean functions with improved cryptographic properties; one of the proposals require a few extra gates, while the other has an overall lower gate count. At the 192-bit, and the 256-bit security levels, there are no proposals in the literature with smaller gate counts.
## 2025/2109
* Title: Secure Lookup Tables: Faster, Leaner, and More General
* Authors: Chongrong Li, Pengfei Zhu, Yun Li, Zhanpeng Guo, Jingyu Li, Yuncong Hu, Zhicong Huang, Cheng Hong
* [Permalink](https://eprint.iacr.org/2025/2109)
* [Download](https://eprint.iacr.org/2025/2109.pdf)
### Abstract
Secure lookup table (LUT) protocols allow retrieving values from a table at secret indices, and have become a promising approach for the secure evaluation of non-linear functions. Most existing LUT protocols target the two-party setting, where the best protocols achieve a communication cost of $O(N)$ for a table of size $N$. MAESTRO (Morita et al., USENIX Security 2025) represents the state-of-the-art LUT protocol for AES in the three-party honest-majority setting, with a communication cost of $O(N^{1/2})$; malicious security is achieved with distributed zero-knowledge proofs. However, it only supports single-input tables over characteristic-2 fields $\mathbb{F}_{2^k}$ and lacks support for multi-input tables over rings $\mathbb{Z}_{2^k}$, which are more widely used in modern computation. Moreover, the $O(N^{1/2})$ cost remains expensive for large-scale applications; their efficient distributed zero-knowledge proofs are specialized for AES and cannot be easily applied to $\mathbb{Z}_{2^k}$.
In this work, we present MARLUT, a new generalized and optimized LUT construction supporting multi-input tables over both rings $\mathbb{Z}_{2^k}$ and fields $\mathbb{F}_{2^k}$ with malicious security. We achieve this by (1) extending the semi-honest LUT protocol from MAESTRO, utilizing high-dimensional tensors to reduce its communication cost to $O(N^{1/3})$, and (2) designing a new distributed zero-knowledge proof for inner-product relations over $\mathbb{Z}_{2^k}$. Our distributed zero-knowledge proof is more efficient than the state-of-the-art work (Li et al., CCS 2024) and may be of independent interest. Experiments show that on a table of size $2^{16}$, our semi-honest LUT protocol reduces the offline computational and communication cost by a factor of $5.95$ and $3.23$, respectively. Our distributed zero-knowledge proofs show up to $7.07\times$ and $4.97\times$ speedups over the state-of-the-art protocol on ring $\mathbb{Z}_{2^8}$ and $\mathbb{Z}_{2^{16}}$, respectively.
## 2025/2110
* Title: A note on mutual correlated agreement for Reed-Solomon codes
* Authors: Ulrich Hab||ck
* [Permalink](https://eprint.iacr.org/2025/2110)
* [Download](https://eprint.iacr.org/2025/2110.pdf)
### Abstract
We outline how to generalize the Guruswami-Sudan list decoder anal-
ysis from BenrCoSasson, Carmon, Ishai, Kopparty and Saraf [BCI+20] in
order to obtain a rCLglobalrCY proximity gap, called mutual correlated agree- ment in Arnon, Chiesa, Fenzi and Yogev [WHIR 2024], or strong correlated agreement in Zeilberger [Khatam 24].
## 2025/2111
* Title: SoK: Secure Computation over Secret Shares
* Authors: Tamir Tassa, Arthur Zamarin
* [Permalink](https://eprint.iacr.org/2025/2111)
* [Download](https://eprint.iacr.org/2025/2111.pdf)
### Abstract
Secure multiparty computation (MPC) enables mutually distrustful parties to jointly compute functions over private data without revealing their inputs. A central paradigm in MPC is the secret-sharing-based model, where secret sharing underpins the efficient realization of arithmetic, comparison, numerical, and Boolean operations on shares of private inputs. In this paper, we systematize protocols for these operations, with particular attention to two foundational contributions \cite{ChidaGHIKLN18,NO07} that devised secure multiplication and comparison. Our survey provides a unified, self-contained exposition that highlights the composability, performance trade-offs, and implementation choices of these protocols. We further demonstrate how they support practical privacy-preserving systems, including recommender systems, distributed optimization platforms, and e-voting infrastructures. By clarifying the protocol landscape and connecting it to deployed and emerging applications, we identify concrete avenues for improving efficiency, scalability, and integration into real-world MPC frameworks. Our goal is to bridge theory and practice, equipping both researchers and practitioners with a deeper understanding of secret-sharing-based MPC as a foundation for privacy technologies.
## 2025/2112
* Title: Sharing the Mask: TFHE bootstrapping on Packed Messages
* Authors: Bergerat Loris, Bonte Charlotte, Benjamin R. Curtis, Jean-Baptiste Orfila, Pascal Paillier, Samuel Tap
* [Permalink](https://eprint.iacr.org/2025/2112)
* [Download](https://eprint.iacr.org/2025/2112.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) schemes typically experience significant data expansion during encryption, leading to increased computational costs and memory demands during homomorphic evaluations compared to their plaintext counterparts. This work builds upon prior methods aimed at reducing ciphertext expansion by leveraging matrix secrets under the Matrix-LWE assumption. In particular, we consider a ciphertext format referred to in this work as common mask (CM) ciphertexts, which comprises a shared mask and multiple message bodies. Each body encrypts a distinct message while reusing the common random mask. We demonstrate that all known FHEW/TFHE style ciphertext variants and operations can be naturally extended to this CM format. Our benchmarks highlight the potential for amortizing operations using the CM structure, significantly reducing overhead. For instance, in the boolean setting, we have up to a 51% improvement when packing 8 messages. Beyond ciphertext compression and amortized evaluations, the CM format also enables the generalization of several core-TFHE operations. Specifically, we support applying distinct lookup tables on different encrypted messages within a single CM ciphertext and private linear operations on messages encrypted within the same CM ciphertext.
## 2025/2113
* Title: Single-Server Private Outsourcing of zk-SNARKs
* Authors: Kasra Abbaszadeh, Hossein Hafezi, Jonathan Katz, Sarah Meiklejohn
* [Permalink](https://eprint.iacr.org/2025/2113)
* [Download](https://eprint.iacr.org/2025/2113.pdf)
### 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 serverrCOs 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\times$ and reduce the proving latency by up to $9\times$.
## 2025/2114
* Title: Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
* Authors: Hanlin Ren, Yichuan Wang, Yan Zhong
* [Permalink](https://eprint.iacr.org/2025/2114)
* [Download](https://eprint.iacr.org/2025/2114.pdf)
### Abstract
Given a circuit $G: \{0, 1\}^n \to \{0, 1\}^m$ with $m > n$, the *range avoidance* problem ($\text{Avoid}$) asks to output a string $y\in \{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 \to \{0, 1\}^m$ where $m > n$ but for every $y\in \{0, 1\}^m$, it is infeasible to prove the statement "$y\not\in\mathrm{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).
$\bullet$ We show that the existence of demi-bits generators implies $\text{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 $\text{Avoid}$ even when the instances are constant-degree polynomials over $\mathbb{F}_2$.
$\bullet$ We show that the dual weak pigeonhole principle is unprovable in Cook's theory $\mathsf{PV}_1$ under the existence of demi-bits generators secure against $\mathbf{AM}/_{O(1)}$, thereby separating Je+O|ibek's theory $\mathsf{APC}_1$ from $\mathsf{PV}_1$. Previously, Ilango, Li, and Williams (STOC '23) obtained the same separation under different (and arguably stronger) cryptographic assumptions.
$\bullet$ 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 $\text{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.
## 2025/2115
* Title: Weighted Batched Threshold Encryption with Applications to Mempool Privacy
* Authors: Amit Agarwal, Kushal Babel, Sourav Das, Babak Poorebrahim Gilkalaye, Arup Mondal, Benny Pinkas, Peter Rindal, Aayush Yadav
* [Permalink](https://eprint.iacr.org/2025/2115)
* [Download](https://eprint.iacr.org/2025/2115.pdf)
### 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 rCLBEAT-MEVrCY 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 ree 6|u 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 ree 50|u for 100 validators with total stake weight 5000 distributed as per the latest Solana stake distribution.
## 2025/2116
* Title: Oblivious Batch Updates for Bloom-Filter-based Outsourced Cryptographic Protocols
* Authors: Marten van Dijk, Dandan Yuan
* [Permalink](https://eprint.iacr.org/2025/2116)
* [Download](https://eprint.iacr.org/2025/2116.pdf)
### 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 filterrCOs maximum capacity rather than the actual batch size.
To address these limitations, we introduce a new cryptographic primitive, $\textit{Oblivious Bloom Filter Insertion}$ ($\textsf{OBFI}$), and propose novel constructions. At the core of our design is a novel building block, $\textit{Oblivious Bucket Distribution}$ ($\textsf{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 $\textsf{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 $\textsf{OBFI}$ constructions achieve adaptive data-obliviousness and ensure that batch update costs scale primarily with the batch size. Depending on the variant, the senderrCOs storage requirement ranges from $O(\lambda)$, where $\lambda$ is the security parameter, down to $O(1)$. Finally, we demonstrate the practicality of $\textsf{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.
## 2025/2117
* Title: Revisiting Simulation Extractability in the Updatable Setting
* Authors: Hamidreza Khoshakhlagh
* [Permalink](https://eprint.iacr.org/2025/2117)
* [Download](https://eprint.iacr.org/2025/2117.pdf)
### 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 adversaryrCOs 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.
## 2025/2118
* Title: Revisiting Rational Broadcast Protocols
* Authors: Shunya Otomo, Kenji Yasunaga
* [Permalink](https://eprint.iacr.org/2025/2118)
* [Download](https://eprint.iacr.org/2025/2118.pdf)
### Abstract
A recent study by Yamashita and Yasunaga (GameSec 2023) presented a constant-round deterministic broadcast protocol secure against \emph{detection-averse} 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 \emph{local detectability} 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.
## 2025/2119
* Title: Twinkle: A family of Low-latency Schemes for Authenticated Encryption and Pointer Authentication
* Authors: Jianhua Wang, Tao Huang, Shuang Wu, Zilong Liu
* [Permalink](https://eprint.iacr.org/2025/2119)
* [Download](https://eprint.iacr.org/2025/2119.pdf)
### 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 $\mathtt{Twinkle}$ with an output up to 1152 bits. Leveraging only one block of $\texttt{Twinkle}$, we developed $\texttt{Twinkle-AE}$, a specialized authenticated encryption scheme with six variants covering different cache line sizes and security requirements. We also propose $\texttt{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 $\texttt{Twinkle-AE}$ achieves an encryption and authentication latency of 3.83 $ns$ for a cache line. In comparison, $\texttt{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 $\texttt{Twinkle-PA}$, the latency is 2.04 $ns$, while $\texttt{QARMA-64-}\sigma_0$ has a latency of 5.57 $ns$.
## 2025/2120
* Title: Language-Agnostic Detection of Computation-Constraint Inconsistencies in ZKP Programs via Value Inference
* Authors: Arman Kolozyan, Bram Vandenbogaerde, Janwillem Swalens, Lode Hoste, Stefanos Chaliasos, Coen De Roover
* [Permalink](https://eprint.iacr.org/2025/2120)
* [Download](https://eprint.iacr.org/2025/2120.pdf)
### 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$\times$ 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.
## 2025/2121
* Title: Generic and Algebraic Computation Models: When AGM Proofs Transfer to the GGM
* Authors: Joseph Jaeger, Deep Inder Mohan
* [Permalink](https://eprint.iacr.org/2025/2121)
* [Download](https://eprint.iacr.org/2025/2121.pdf)
### 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.
## 2025/2122
* Title: Adaptive Security for Constrained PRFs
* Authors: Kaishuo Cheng, Joseph Jaeger
* [Permalink](https://eprint.iacr.org/2025/2122)
* [Download](https://eprint.iacr.org/2025/2122.pdf)
### 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.
## 2025/2123
* Title: Dictators? Friends? Forgers. Breaking and Fixing Unforgeability Definitions for Anamorphic Signature Schemes
* Authors: Joseph Jaeger, Roy Stracovsky
* [Permalink](https://eprint.iacr.org/2025/2123)
* [Download](https://eprint.iacr.org/2025/2123.pdf)
### 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.
## 2025/2124
* Title: SALSAA rCo Sumcheck-Aided Lattice-based Succinct Arguments and Applications
* Authors: Shuto Kuriyama, Russell W. F. Lai, Micha+e Osadnik, Lorenzo Tucci
* [Permalink](https://eprint.iacr.org/2025/2124)
* [Download](https://eprint.iacr.org/2025/2124.pdf)
### 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|f, 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$\times$ 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^{28}$ $\mathbb{Z}_q$ elements;
(ii) a polynomial commitment scheme with matching performance; and
(iii) the first lattice-based folding scheme natively operating on $\ell_2$-norm-bounded witnesses, achieving highly efficient verification in $2.28$ ms and producing a proof of just $73$ KB for a witness of $2^{28}$ $\mathbf{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.
## 2025/2125
* Title: Are ideal functionalities really ideal?
* Authors: Myrto Arapinis, V|-ronique Cortier, Hubert de Groote, Charlie Jacomme, Steve Kremer
* [Permalink](https://eprint.iacr.org/2025/2125)
* [Download](https://eprint.iacr.org/2025/2125.pdf)
### 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.
## 2025/2126
* Title: DPaaS: Improving Decentralization by Removing Relays in Ethereum PBS
* Authors: Chenyang Liu, Ittai Abraham, Matthew Lentz, Kartik Nayak
* [Permalink](https://eprint.iacr.org/2025/2126)
* [Download](https://eprint.iacr.org/2025/2126.pdf)
### 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 EthereumrCOs 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.
## 2025/2127
* Title: Censorship-Resistant Sealed-Bid Auctions on Blockchains
* Authors: Orestis Alpos, Lioba Heimbach, Kartik Nayak, Sarisht Wadhwa
* [Permalink](https://eprint.iacr.org/2025/2127)
* [Download](https://eprint.iacr.org/2025/2127.pdf)
### 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.
## 2025/2129
* Title: Binding Security of Explicitly-Rejecting KEMs via Plaintext Confirmation and Robust PKEs
* Authors: Juliane Kr|nmer, Yannick M|+nz, Patrick Struck, Maximiliane Weish|nupl
* [Permalink](https://eprint.iacr.org/2025/2129)
* [Download](https://eprint.iacr.org/2025/2129.pdf)
### 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 transformrCothough 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.
## 2025/2130
* Title: Weightwise (almost) perfectly balanced functions: $t$-concatenation and the general Maiorana-McFarland class
* Authors: Leyla I+f-#k, Ren|- Rodr|!guez-Aldama, Ajla +aehovi-c
* [Permalink](https://eprint.iacr.org/2025/2130)
* [Download](https://eprint.iacr.org/2025/2130.pdf)
### 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.
## 2025/2131
* Title: Persistent BitTorrent Trackers
* Authors: Francois Xavier Wicht, Zhengwei Tong, Shunfan Zhou, Hang Yin, Aviv Yaish
* [Permalink](https://eprint.iacr.org/2025/2131)
* [Download](https://eprint.iacr.org/2025/2131.pdf)
### 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\times$.
## 2025/2132
* Title: Bandwidth Efficient Partial Authorized PSI
* Authors: Tjitske Ollie Koster, Francesca Falzon, Evangelia Anna Markatou
* [Permalink](https://eprint.iacr.org/2025/2132)
* [Download](https://eprint.iacr.org/2025/2132.pdf)
### 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^{20}$, we require around $21\times$ less bandwidth and are about $6\times$ 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.
## 2025/2133
* Title: Byzantine Broadcast with Unknown Participants
* Authors: Wonseok Choi, Ran Cohen, Juan Garay, Nikos Skoumios, Vassilis Zikas * [Permalink](https://eprint.iacr.org/2025/2133)
* [Download](https://eprint.iacr.org/2025/2133.pdf)
### 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.
## 2025/2134
* Title: Non-Interactive Threshold Mercurial Signatures with Applications to Threshold DAC
* Authors: Scott Griffy, Nicholas Jankovic, Anna Lysyanskaya, Arup Mondal
* [Permalink](https://eprint.iacr.org/2025/2134)
* [Download](https://eprint.iacr.org/2025/2134.pdf)
### Abstract
In a mercurial signature, a signer signs a representative $m$ of an equivalence class of messages on behalf of a representative $\mathsf{pk}$ of an equivalence class of public keys, receiving the signature $\sigma$. One can then transform $\sigma$ into a signature $\sigma'$ on an equivalent (to $m$) message $m'$ under an equivalent (to $\mathsf{pk}$) public key $\mathsf{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 chainrCoand thus knows its corresponding secret keyrCowill 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.
## 2025/2135
* Title: Robust Elections and More: Fast MPC in the Preprocessing Model
* Authors: Charanjit S. Jutla, Nathan Manohar, Arnab Roy
* [Permalink](https://eprint.iacr.org/2025/2135)
* [Download](https://eprint.iacr.org/2025/2135.pdf)
### 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.
## 2025/2136
* Title: The Latency Cost Of Censorship Resistance
* Authors: Ittai Abraham, Yuval Efron, Ling Ren
* [Permalink](https://eprint.iacr.org/2025/2136)
* [Download](https://eprint.iacr.org/2025/2136.pdf)
### 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.
## 2025/2137
* Title: Linear Secret-shared Shuffle with Malicious Security
* Authors: Samuel Dittmer, Rohit Nema, Rafail Ostrovsky
* [Permalink](https://eprint.iacr.org/2025/2137)
* [Download](https://eprint.iacr.org/2025/2137.pdf)
### 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.
--- Synchronet 3.21a-Linux NewsLink 1.2