## In this issue

1. [2023/872] Conjunctive Searchable Symmetric Encryption from ...
2. [2024/765] Information-Theoretic Multi-Server PIR with Global ...
3. [2024/957] VRaaS: Verifiable Randomness as a Service on ...
4. [2024/962] Secure Account Recovery for a Privacy-Preserving ...
5. [2024/963] Shared OT and Its Applications to Unconditional ...
6. [2024/964] Malicious Security for PIR (almost) for Free
7. [2024/965] Efficient and Secure Post-Quantum Certificateless ...
8. [2024/966] Diffuse Some Noise: Diffusion Models for ...
9. [2024/967] Consolidated Linear Masking (CLM): Generalized ...
10. [2024/968] Fast SNARK-based Non-Interactive Distributed ...
11. [2024/969] Analysis, modify and apply in IIOT form light- ...
12. [2024/970] Cryptography at the Crossroads: Ethical ...
13. [2024/971] A Note on (2, 2)-isogenies via Theta Coordinates
14. [2024/972] Efficient Secure Communication Over Dynamic ...
15. [2024/973] ICICLE v2: Polynomial API for Coding ZK Provers to ...
16. [2024/974] Towards Optimal Parallel Broadcast under a ...
17. [2024/975] ZLR: a fast online authenticated encryption scheme ...
18. [2024/976] PIR with Client-Side Preprocessing: Information- ...
19. [2024/977] Improved Boomerang Attacks on 6-Round AES
20. [2024/978] Distributed PIR: Scaling Private Messaging via the ...
21. [2024/979] Volatile and Persistent Memory for zkSNARKs via ...
22. [2024/980] FaultyGarble: Fault Attack on Secure Multiparty ...
23. [2024/981] Hadamard Product Arguments and Their Applications
24. [2024/982] SoK: Programmable Privacy in Distributed Systems
25. [2024/983] SoCureLLM: An LLM-driven Approach for Large-Scale ...
26. [2024/984] Side-Channel and Fault Resistant ASCON ...
27. [2024/985] DualRing-PRF: Post-Quantum (Linkable) Ring ...
28. [2024/986] FABESA: Fast (and Anonymous) Attribute-Based ...
29. [2024/987] CoGNN: Towards Secure and Efficient Collaborative ...
30. [2024/988] Privacy-Preserving Dijkstra
31. [2024/989] A Formal Treatment of End-to-End Encrypted Cloud ...
32. [2024/990] Perfectly-secure Network-agnostic MPC with Optimal ...
33. [2024/991] Leveled Homomorphic Encryption Schemes for ...
34. [2024/992] The Complexity of the Crossbred Algorithm
35. [2024/993] Limits on the Power of Prime-Order Groups: ...
36. [2024/994] On Knowledge-Soundness of Plonk in ROM from ...
37. [2024/995] Cross-chain bridges via backwards-compatible SNARKs
38. [2024/996] Great-LaKeys: An Improved Threshold-PRF and a Novel ...
39. [2024/997] Dishonest Majority Multi-Verifier Zero-Knowledge ...
40. [2024/998] Measuring Conditional Anonymity - A Global Study
41. [2024/999] ProxCode: Efficient Biometric Proximity Searchable ...
42. [2024/1000] File-Injection Attacks on Searchable Encryption, ...
43. [2024/1001] Guidance for Efficient Selection of Secure ...
44. [2024/1002] Elementary Formulas for Greatest Common Divisors ...
45. [2024/1003] zkVoting : Zero-knowledge proof based coercion- ...
46. [2024/1004] Relaxed Vector Commitment for Shorter Signatures
47. [2024/1005] Differential Fault Attack on HE-Friendly Stream ...
48. [2024/1006] Delegated-Query Oblivious Transfer and its ...
49. [2024/1007] On the vector subspaces of $\mathbb{F}_{2^n}$ over ...
50. [2024/1008] A Deep Study of The Impossible Boomerang ...
51. [2024/1009] Improved Reductions from Noisy to Bounded and ...
52. [2024/1010] FSSiBNN: FSS-based Secure Binarized Neural Network ...
53. [2024/1011] Secure Vickrey Auctions with Rational Parties

## 2023/872

* Title: Conjunctive Searchable Symmetric Encryption from Hard Lattices
* Authors: Debadrita Talapatra, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2023/872)
* [Download](https://eprint.iacr.org/2023/872.pdf)

### Abstract

Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-
broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key crypto-primitives either do not support conjunctive
searches, or are practically inefficient. In particular, there exists no quantum-safe yet practically efficient conjunctive SSE scheme from lattice-based hardness assumptions.
We solve this open question by proposing Oblivious Post-Quantum Secure Cross Tags (OQXT) – the first lattice-based practically efficient and highly scalable conjunctive SSE scheme. The technical centerpiece of OQXT is a novel oblivious cross-tag
generation protocol with provable security guarantees derived from lattice-based hardness assumptions. We prove the post-quantum simulation security of OQXT with respect to a rigorously defined and thoroughly analyzed leakage profile. We then present a
prototype implementation of OQXT and experimentally validate its practical efficiency and scalability over extremely large real-world databases. Our experiments show that OQXT has competitive end-to-end search latency when compared with the best (quantum-
broken) conjunctive SSE schemes.



## 2024/765

* Title: Information-Theoretic Multi-Server PIR with Global Preprocessing
* Authors: Ashrujit Ghoshal, Baitian Li, Yaohua Ma, Chenxin Dai, Elaine Shi
* [Permalink](https://eprint.iacr.org/2024/765)
* [Download](https://eprint.iacr.org/2024/765.pdf)

### Abstract

We propose a new unified framework to construct multi-server, information-theoretic Private Information Retrieval (PIR) schemes that leverage global preprocesing to achieve sublinear computation per query.
Despite a couple earlier attempts, our understanding of PIR schemes in the global preprocessing model remains limited, and so far, we only know a few sparse points in the broad design space.
Our framework not only unifies earlier results in this space, but leads to several new results. First, we can improve the server space of the state-of-the-art scheme by a polynomial factor. Second, we can broaden the parameter space of known results,
allowing a smooth tradeoff between bandwidth and computation. Third, while earlier schemes achieve better per-server bandwidth and computation as we add more servers, the server space actually grows w.r.t. the number of servers. We offer a new scalable
family of schemes where the per-server bandwidth, computation, and space all decrease as we add more servers. This scalable family of schemes also implies the so-called ``doubly efficient'' PIR scheme with any super-constant number of servers, achieving $
n^{1+o(1)}$ server space and preprocessing cost, and $n^{o(1)}$ bandwidth and computation per query.



## 2024/957

* Title: VRaaS: Verifiable Randomness as a Service on Blockchains
* Authors: Jacob Gorman, Lucjan Hanzlik, Aniket Kate, Easwar Vivek Mangipudi, Pratyay Mukherjee, Pratik Sarkar, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2024/957)
* [Download](https://eprint.iacr.org/2024/957.pdf)

### Abstract

Web3 applications, such as on-chain games, NFT minting, and leader elections necessitate access to unbiased, unpredictable, and publicly verifiable randomness. Despite its broad use cases and huge demand, there is a notable absence of comprehensive
treatments of on-chain verifiable randomness services. To bridge this, we offer an extensive formal analysis of on-chain verifiable randomness services.

We present the $first$ formalization of on-chain verifiable randomness in the blockchain setting by introducing the notion of Verifiable Randomness as a Service (VRaaS). We formally define VRaaS using an ideal functionality $\mathcal{F}_{\sf VRaaS}$
in the Universal Composability model. Our definition not only captures the core features of randomness services, such as unbiasability, unpredictability, and public verifiability, but also accounts for many other crucial nuances pertaining to different
entities involved, such as smart contracts.

Within our framework we study a generic design of Verifiable Random Function~(VRF)-based randomness service -- where the randomness requester provides an input on which the randomness is evaluated as VRF output. We show that it does satisfy our
formal VRaaS definition. Furthermore, we show that the generic protocol captures many real-world randomness services like Chainlink VRF and Supra dVRF.

We investigate whether our definition is minimalistic in terms of the desired security properties - towards that, we show that a couple of insecure constructions fall short of realizing our definition. Using our definition we also discover practical
vulnerabilities in other designs such as Algorand beacon, Pyth VRF and Band VRF that offer on-chain verifiable randomness.



## 2024/962

* Title: Secure Account Recovery for a Privacy-Preserving Web Service
* Authors: Ryan Little, Lucy Qin, Mayank Varia
* [Permalink](https://eprint.iacr.org/2024/962)
* [Download](https://eprint.iacr.org/2024/962.pdf)

### Abstract

If a web service is so secure that it does not even know—and does not want to know—the identity and contact info of its users, can it still offer account recovery if a user forgets their password? This paper is the culmination of the authors' work to
design a cryptographic protocol for account recovery for use by a prominent secure matching system: a web-based service that allows survivors of sexual misconduct to become aware of other survivors harmed by the same perpetrator. In such a system, the
list of account-holders must be safeguarded, even against the service provider itself.

In this work, we design an account recovery system that, on the surface, appears to follow the typical workflow: the user types in their email address, receives an email containing a one-time link, and answers some security questions. Behind the scenes,
the defining feature of our recovery system is that the service provider can perform email-based account validation without knowing, or being able to learn, a list of users' email addresses. Our construction uses standardized cryptography for most
components, and it has been deployed in production at the secure matching system.

As a building block toward our main construction, we design a new cryptographic primitive that may be of independent interest: an oblivious pseudorandom function that can either have a fully-private input or a partially-public input, and that reaches the
same output either way. This primitive allows us to perform online rate limiting for account recovery attempts, without imposing a bound on the creation of new accounts. We provide an open-source implementation of this primitive and provide evaluation
results showing that the end-to-end interaction time takes 8.4-60.4 ms in fully-private input mode and 3.1-41.2 ms in partially-public input mode.



## 2024/963

* Title: Shared OT and Its Applications to Unconditional Secure Integer Equality, Comparison and Bit-Decomposition
* Authors: Lucas Piske, Jeroen van de Graaf, Anderson C. A. Nascimento, Ni Trieu
* [Permalink](https://eprint.iacr.org/2024/963)
* [Download](https://eprint.iacr.org/2024/963.pdf)

### Abstract

We present unconditionally perfectly secure protocols in the
semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo $M$ and allowing additive secret-sharing of all inputs and outputs. These
extensions can be implemented
by simple local computations without incurring additional OT invocations. We believe our Shared OT may be of independent interest.


Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds.



## 2024/964

* Title: Malicious Security for PIR (almost) for Free
* Authors: Brett Falk, Pratyush Mishra, Matan Shtepel
* [Permalink](https://eprint.iacr.org/2024/964)
* [Download](https://eprint.iacr.org/2024/964.pdf)

### Abstract

Private Information Retrieval (PIR) enables a client to retrieve a database element from a semi-honest server while hiding the element being queried from the server. Maliciously-secure PIR (mPIR) [Colombo et al., USENIX Security '23] strengthens the
guarantees of plain (i.e., semi-honest) PIR by ensuring that even a misbehaving server (a) cannot compromise client privacy via selective-failure attacks, and (b) must answer every query *consistently* (i.e., with respect to the same database). These
additional security properties are crucial for many real-world applications.

In this work we present a generic compiler that transforms any PIR scheme into an mPIR scheme in a black-box manner, minimal overhead, and without requiring additional cryptographic assumptions. Since mPIR trivially implies PIR, our compiler establishes
the equivalence of mPIR and PIR. By instantiating our compiler with existing PIR schemes, we immediately obtain mPIR schemes with $O(N^\epsilon)$ communication cost. In fact, by applying our compiler to a recent doubly-efficient PIR [Lin et al., STOC '23]
, we are able to construct a *doubly-efficient* mPIR scheme that requires only $\text{polylog}(N)$ communication and server and client computation. In comparison, all prior work incur a $\Omega(\sqrt{N})$ cost in these metrics.

Our compiler makes use of smooth locally-decodable codes (LDCs) that have a robust decoding procedure. We term these codes "subcode"-LDCs, because they are LDCs where the query responses are from an error-correcting code. This property is shared by Reed--
Muller codes (whose query responses are Reed--Solomon codewords) and more generally lifted codes.

Applying our compiler requires us to consider decoding in the face of *non-signaling adversaries*, for reasons analogous to the need for non-signaling PCPs in the succinct-argument literature. We show how to construct such decoders for Reed--Muller codes,
and more generally for smooth locally-decodable codes that have a robust decoding procedure.



## 2024/965

* Title: Efficient and Secure Post-Quantum Certificateless Signcryption for Internet of Medical Things
* Authors: Shiyuan Xu, Xue Chen, Yu Guo, Siu-Ming Yiu, Shang Gao, Bin Xiao
* [Permalink](https://eprint.iacr.org/2024/965)
* [Download](https://eprint.iacr.org/2024/965.pdf)

### Abstract

Internet of Medical Things (IoMT) has gained significant research focus in both academic and medical institutions. Nevertheless, the sensitive data involved in IoMT raises concerns regarding user validation and data privacy. To address these concerns,
certificateless signcryption (CLSC) has emerged as a promising solution, offering authenticity, confidentiality, and unforgeability. Unfortunately, most existing CLSC schemes are impractical for IoMT due to their heavy computational and storage
requirements. Additionally, these schemes are vulnerable to quantum computing attacks. Therefore, research focusing on designing an efficient post-quantum CLSC scheme is still far-reaching.
In this work, we propose PQ-CLSC, a novel post-quantum CLSC scheme that ensures quantum safety for IoMT. Our proposed design facilitates secure transmission of medical data between physicians and patients, effectively validating user legitimacy and
minimizing the risk of private information leakage. To achieve this, we leverage lattice sampling algorithms and hash functions to generate the particial secret key and then employ the sign-then-encrypt method to obtain the ciphertext.
We also formally and prove the security of our design, including indistinguishability against chosen-ciphertext attacks (IND-CCA2) and existential unforgeability against chosen-message attacks (EU-CMA) security. Finally, through comprehensive performance
evaluation, our signcryption overhead is only 30%-55% compared to prior arts, while our computation overhead is just around 45% of other existing schemes. The evaluation results demonstrate that our solution is practical and efficient.



## 2024/966

* Title: Diffuse Some Noise: Diffusion Models for Measurement Noise Removal in Side-channel Analysis
* Authors: Sengim Karayalcin, Guilherme Perin, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2024/966)
* [Download](https://eprint.iacr.org/2024/966.pdf)

### Abstract

Resilience against side-channel attacks is an important consideration for cryptographic implementations deployed in devices with physical access to the device. However, noise in side-channel measurements has a significant impact on the complexity of
these attacks, especially when an implementation is protected with masking. Therefore, it is important to assess the ability of an attacker to deal with noise. While some previous works have considered approaches to remove (some) noise from measurements,
these approaches generally require considerable expertise to be effectively employed or necessitate the ability of the attacker to capture a 'clean' set of traces without the noise.
In this paper, we introduce a method for utilizing diffusion models to remove measurement noise from side-channel traces in a fully non-profiled setting. Denoising traces using our method considerably lowers the complexity of mounting attacks in both
profiled and non-profiled settings. For instance, for a collision attack against the ASCADv2 dataset, we reduced the number of traces required to retrieve the key by 40%, and we showed similar improvements for ESHARD using a state-of-the-art MORE attack.
Furthermore, we provide analyses into the scenarios where our method is useful and generate insights into how the diffusion networks denoise traces.



## 2024/967

* Title: Consolidated Linear Masking (CLM): Generalized Randomized Isomorphic Representations, Powerful Degrees of Freedom and Low(er)-cost
* Authors: Itamar Levi, Osnat Keren
* [Permalink](https://eprint.iacr.org/2024/967)
* [Download](https://eprint.iacr.org/2024/967.pdf)

### Abstract

Masking is a widely adopted countermeasure against side-channel analysis (SCA) that protects cryptographic implementations from information leakage. However, current masking schemes often incur significant overhead in terms of electronic cost. RAMBAM, a
recently proposed masking technique that fits elegantly with the AES algorithm, offers ultra-low latency/area by utilizing redundant representations of finite field elements. This paper presents a comprehensive generalization of RAMBAM and various other
masking schemes within a unified framework and a mathematical representation known as Consolidated Linear Masking (CLM), where masking schemes are formalized by their encoding. We establish a theoretical foundation for CLM linking randomized isomorphic (
code) representations and the entropy provided by the redundancy to a revised notion of masking order. Our analysis reveals that RAMBAM is a specific instance of CLM as well as other masking constructions, thus paving the way for significant enhancements.
For example, a $1^{st}$-order secure design can be achieved almost without increasing the size of the representation of the variables. This property scales up to any order and is versatile. We demonstrate how CLM enables: (1) randomized selection of the
isomorphic field for improved security; (2) flexible choice of the randomization polynomial; (3) embedded mask-refreshing via the randomized isomorphic representation that reduces randomness requirements significantly as well as improves performance; (4)
a wider range of isomorphic randomized mappings that significantly increases the available randomization space compared to RAMBAM; (5) considerable improvement in securing fault-injection attacks and inherent security against probing adversaries, i.e.,
more required probes. In addition, our framework addresses ways to improve the brute-force parameter choices in the original RAMBAM. By offering a unifying theoretical perspective for masking and practical enhancements, this work advances the design of
efficient and secure masking countermeasures against SCA threats.



## 2024/968

* Title: Fast SNARK-based Non-Interactive Distributed Verifiable Random Function with Ethereum Compatibility
* Authors: Jia Liu, Mark Manulis
* [Permalink](https://eprint.iacr.org/2024/968)
* [Download](https://eprint.iacr.org/2024/968.pdf)

### Abstract

Distributed randomness beacons (DRBs) are fundamental for various decentralised applications, such as consensus protocols, decentralised gaming and lotteries, and collective governance protocols. These applications are heavily used on modern blockchain
platforms.

This paper presents the so far most efficient direct construction and implementation of a non-interactive distributed verifiable random function (NI-DVRF) that is fully compatible with Ethereum. Our NI-DVRF scheme adopts pairings and combines techniques
from secret sharing, SNARKs, and BLS signatures. The security properties of the resulting NI-DVRF scheme are formally modelled and proven in the random oracle model under standard pairing-based assumptions.

To justify the efficiency and cost claims and more generally its adoption potential in practice, the proposed NI-DVRF scheme was implemented in Rust and Solidity. Our implementation is highly optimised and is currently being investigated for deployment
on the multichain layer-2 scaling solution provided by Boba Network to power its DRB service zkRand. Our experimental analysis, therefore, also evaluates performance and scalability properties of the proposed NI-DVRF and its implementation.



## 2024/969

* Title: Analysis, modify and apply in IIOT form light-weight PSI in CM20
* Authors: Zhuang Shan, Leyou Zhang, Qing Wu, Qiqi Lai
* [Permalink](https://eprint.iacr.org/2024/969)
* [Download](https://eprint.iacr.org/2024/969.pdf)

### Abstract

Multi-party computation (\textsf{MPC}) is a major research interest in modern cryptography, and Privacy Set Intersection (\textsf{PSI}) is an important research topic within \textsf{MPC}. Its main function is to allow two parties to compute the
intersection of their private sets without revealing any other information. Therefore, \textsf{PSI} can be applied to various real-world scenarios, such as the Industrial Internet of Things (\textsf{IIOT}). Chase and Miao presented a paper on ``Light-
weight PSI'' at CRYPTO 2020, highlighting its convenient structure and optimal communication cost. However, the drawback is that this protocol is deterministically encrypted and it was discovered through simulation that it is not resistant to
probabilistic attacks. Building upon the ideas from CM20, this paper introduces the concept of a {\em perturbed pseudorandom generator}, constructs and proves its security, and replaces one of the hash functions (originally there were two) from CM20. In
order to demonstrate the security of the \textsf{PSI} protocol proposed in this paper, a dedicated definition of Chosen Plaintext Attack (\textsf{CPA}) security model for this \textsf{PSI} protocol is provided. The paper then proceeds to prove that the \
textsf{PSI} protocol satisfies this defined security model. Efficiency analysis shows that the \textsf{PSI} in this paper is comparable to CM20's \textsf{PSI}, whether on PC, pad, or phone.



## 2024/970

* Title: Cryptography at the Crossroads: Ethical Responsibility, the Cypherpunk Movement and Institutions
* Authors: Eric Blair
* [Permalink](https://eprint.iacr.org/2024/970)
* [Download](https://eprint.iacr.org/2024/970.pdf)

### Abstract

This paper explores the intersection of cryptographic work with ethical responsibility and political activism, inspired by the Cypherpunk Manifesto and Phillip Rogaway's analysis of the moral character of cryptography. The discussion encompasses the
historical context of cryptographic development, the philosophical underpinnings of the cypherpunk ideology, and contemporary challenges posed by mass surveillance and privacy concerns. By examining these facets, the paper calls for a renewed commitment
to developing cryptographic solutions that prioritize human rights and societal good.



## 2024/971

* Title: A Note on (2, 2)-isogenies via Theta Coordinates
* Authors: Jianming Lin, Saiyu Wang, Chang-An Zhao
* [Permalink](https://eprint.iacr.org/2024/971)
* [Download](https://eprint.iacr.org/2024/971.pdf)

### Abstract

In this paper, we revisit the algorithm for computing chains of $(2, 2)$-isogenies between products of elliptic curves via theta coordinates proposed by Dartois et al. For each fundamental block of this algorithm, we provide a explicit inversion-free
version. Besides, we exploit a novel technique of $x$-only ladder to speed up the computation of gluing isogeny. Finally, we present a mixed optimal strategy, which combines the inversion-elimination tool with the original methods together to execute a
chain of $(2, 2)$-isogenies.

We make a cost analysis and present a concrete comparison between ours and the previously known methods for inversion elimination. Furthermore, we implement the mixed optimal strategy for benchmark. The results show that when computing $(2, 2)$-
isogeny chains with lengths of 126, 208 and 632, compared to Dartois, Maino, Pope and Robert's original implementation, utilizing our techniques can reduce $30.8\%$, $20.3\%$ and $9.9\%$ multiplications over the base field $\mathbb{F}_p$,
respectively. Even for the updated version which employs their inversion-free methods, our techniques still possess a slight advantage.



## 2024/972

* Title: Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity
* Authors: Ivan Damgård, Divya Ravi, Lawrence Roy, Daniel Tschudi, Sophia Yakoubov
* [Permalink](https://eprint.iacr.org/2024/972)
* [Download](https://eprint.iacr.org/2024/972.pdf)

### Abstract

We study the problem of implementing unconditionally secure reliable and private communication (and hence secure computation) in dynamic incomplete networks.
Our model assumes that the network is always $k$-connected, for some $k$, but the concrete connection graph is adversarially chosen in each round of interaction.
We show that, with $n$ players and $t$ malicious corruptions, perfectly secure communication is possible if and only if $k > 2t$. This disproves a conjecture from earlier work, that $k> 3t$ is necessary. Our new protocols are much more efficient than
previous work; in particular, we improve the round and communication complexity by an exponential factor (in $n$) in both the semi-honest and the malicious corruption setting, leading to protocols with polynomial complexity.



## 2024/973

* Title: ICICLE v2: Polynomial API for Coding ZK Provers to Run on Specialized Hardware
* Authors: Karthik Inbasekar, Yuval Shekel, Michael Asa
* [Permalink](https://eprint.iacr.org/2024/973)
* [Download](https://eprint.iacr.org/2024/973.pdf)

### Abstract

Polynomials play a central role in cryptography. In the context of Zero Knowledge Proofs (ZKPs), protocols can be exclusively expressed using polynomials, making them a powerful abstraction tool, as demonstrated in most ZK research papers. Our first
contribution is a high-level framework that enables practitioners to implement ZKPs in a more natural way, based solely on polynomial primitives.

ZK provers are considered computationally intensive algorithms with a high degree of parallelization. These algorithms benefit significantly from hardware acceleration, and deployed ZK systems typically include specialized hardware to optimize the
performance of the prover code. Our second contribution is leveraging our polynomial API to abstract away low-level hardware primitives and automate their memory management. This device-agnostic design allows ZK engineers to prototype and build solutions
while taking advantage of the performance gains offered by specialized hardware, such as GPUs and FPGAs, without needing to understand the hardware implementation details.

Finally, our polynomial API is integrated into version 2 of the ICICLE library and is running in production. This paper also serves as a comprehensive documentation for the ICICLE v2 polynomial API.



## 2024/974

* Title: Towards Optimal Parallel Broadcast under a Dishonest Majority
* Authors: Daniel Collins, Sisi Duan, Julian Loss, Charalampos Papamanthou, Giorgos Tsimos, Haochen Wang
* [Permalink](https://eprint.iacr.org/2024/974)
* [Download](https://eprint.iacr.org/2024/974.pdf)

### Abstract

The parallel broadcast (PBC) problem generalises the classic Byzantine broadcast problem to the setting where all $n$ nodes broadcast a message and deliver $O(n)$ messages. PBC arises naturally in many settings including multi-party computation. Recently,
Tsimos, Loss, and Papamanthou (CRYPTO 2022) showed PBC protocols with improved communication, against an adaptive adversary who can corrupt all but a constant fraction $\epsilon$ of nodes (i.e., $f < (1 - \epsilon)n$). However, their study is limited to
single-bit messages, and their protocols have large polynomial overhead in the security parameter $\kappa$: their TrustedPBC protocol achieves $\tilde{O}(n^2 \kappa^4)$ communication and $O(\kappa\log n)$ rounds. Since these factors of $\kappa$ are in
practice often close (or at least polynomially related) to $n$, they add a significant overhead. In this work, we propose three parallel broadcast protocols for $L$-bit messages, for any size $L$, that significantly improve the communication efficiency
of the state-of-the-art.

We first propose a new extension protocol that uses a $\kappa$-bit PBC as a black box and achieves i) communication complexity of $O(L n^2 + \mathcal{P}(\kappa))$, where $\mathcal{P}(\kappa)$ is the communication complexity of the $\kappa$-bit PBC, and
ii) round complexity same as the $\kappa$-bit PBC. By comparison, the state-of-the-art extension protocol for regular broadcast (Nayak et al., DISC 2020) incurs $O(n)$ additional rounds of communication. Next, we propose a protocol that is secure against
a static adversary, for $\kappa$-bit messages with $O(n^2 \kappa^{1+K} + n\kappa^3 + \kappa^4)$ communication and $O(\kappa)$ round complexity, where $K$ is an arbitrarily small constant such that $0<K<1$. Finally, we propose an adaptively-secure
protocol for $\kappa$-bit messages with $\tilde{O}(n^2\kappa^2 + n\kappa^3)$ communication overhead and $O(\kappa \log{n})$ round complexity by modifying and improving the next-best protocol TrustedPBC in several key ways. Notably, our latter two
protocols are $\tilde{O}(\kappa^{2 - K})$ and $O(\kappa^2)$ times more communication-efficient, respectively, than the state-of-the-art protocols while achieving the same round complexity.



## 2024/975

* Title: ZLR: a fast online authenticated encryption scheme achieving full security
* Authors: Wonseok Choi, Seongha Hwang, Byeonghak Lee, Jooyoung Lee
* [Permalink](https://eprint.iacr.org/2024/975)
* [Download](https://eprint.iacr.org/2024/975.pdf)

### Abstract


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)