## 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

Online authenticated encryption has been considered of practical relevance in light-weight environments due to low latency and constant memory usage. In this paper, we propose a new tweakable block cipher-based online authenticated encryption scheme, dubbed ZLR, and its domain separation variant, dubbed DS-ZLR. ZLR and DS-ZLR follow the Encrypt-MixEncrypt paradigm. However, in contrast to existing schemes using the same paradigm such as ELmE and CoLM, ZLR and DS-ZLR enjoy n-bit security by using larger internal states with an efficient ZHash-like hashing algorithm. In this way, 2n-bit blocks are processed with only a single primitive call for hashing and two primitive calls for encryption and decryption, when they are based on an n-bit tweakable block cipher using n-bit (resp. 2n-bit) tweaks for ZLR (resp. DS-ZLR). Furthermore, they support pipelined computation as well as online nonce-misuse resistance. To the best of our knowledge, ZLR and DS-ZLR are the first pipelineable tweakable block cipher-based online authenticated encryption schemes of rate 2/3 that provide n-bit security with online nonce-misuse resistance.

## 2024/976

* Title: PIR with Client-Side Preprocessing: Information-Theoretic Constructions and Lower Bounds
* Authors: Yuval Ishai, Elaine Shi, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2024/976)
* [Download](https://eprint.iacr.org/2024/976.pdf)

### Abstract

It is well-known that classical Private Information Retrieval (PIR) schemes without preprocessing must suffer from linear server computation per query. Moreover, any such single-server PIR with sublinear bandwidth must rely on public-key cryptography. Several recent works showed that these barriers pertaining to classical PIR can be overcome by introducing a preprocessing phase where each client downloads a small hint that helps it make queries subsequently. Notably, the Piano PIR scheme (and subsequent improvements) showed that with such a client-side preprocessing, not only can we have PIR with sublinear computation and bandwidth per query, but somewhat surprisingly, we can also get it using only symmetric-key cryptography (i.e., one-way functions).

In this paper, we take the question of minimizing cryptographic assumptions to an extreme. In particular, we are the first to explore the landscape of information theoretic single-server preprocessing PIR. We make contributions on both the upper- and lower-bounds fronts. First, we show new information-theoretic constructions with various non-trivial performance tradeoffs between server computation, client space and bandwidth. Second, we prove a (nearly) tight lower bound on the tradeoff between the client space and bandwidth in information-theoretic constructions. Finally, we prove that any computational scheme that overcomes the information-theoretic lower bound and satisfies a natural syntactic requirement (which is met by all known constructions) would imply a hard problem in the complexity class SZK. In particular, this shows that Piano achieves (nearly) optimal client space and bandwidth tradeoff subject to making a black-box use of a one-way function. Some of the techniques we use for the above results can be of independent interest.

## 2024/977

* Title: Improved Boomerang Attacks on 6-Round AES
* Authors: Augustin Bariant, Orr Dunkelman, Nathan Keller, Gaëtan Leurent, Victor Mollimard
* [Permalink](https://eprint.iacr.org/2024/977)
* [Download](https://eprint.iacr.org/2024/977.pdf)

### Abstract

The boomerang attack is a cryptanalytic technique which allows combining two short high-probability differentials into a distinguisher for a large number of rounds. Since its introduction by Wagner in 1999, it has been applied to many ciphers. One of the best-studied targets is a 6-round variant of AES, on which the boomerang attack is outperformed only by the dedicated Square attack. Recently, two new variants of the boomerang attack were presented: retracing boomerang (Eurocrypt'20) and truncated boomerang (Eurocrypt'23). These variants seem incompatible: the former achieves lower memory complexity by throwing away most of the data in order to force dependencies, while the latter achieves lower time complexity by using large structures, which inevitably leads to a large memory complexity.

In this paper we show that elements of the two techniques can be combined to get `the best of the two worlds' – the practical memory complexity of the retracing attack and the lower time complexity of the truncated attack. We obtain an attack with data complexity of $2^{57}$ (compared to $2^{59}$ and $2^{55}$ of truncated and retracing boomerang, respectively), memory complexity of $2^{33}$ (compared to $2^{59}$ and $2^{31}$), and time complexity of $2^{61}$ (compared to $2^{61}$ and $2^{80}$). This is the second-best attack on 6-round AES, after the Square attack.

## 2024/978

* Title: Distributed PIR: Scaling Private Messaging via the Users' Machines
* Authors: Elkana Tovey, Jonathan Weiss, Yossi Gilad
* [Permalink](https://eprint.iacr.org/2024/978)
* [Download](https://eprint.iacr.org/2024/978.pdf)

### Abstract

This paper presents a new architecture for metadata-private messaging that
counters scalability challenges by offloading most computations to the clients.
At the core of our design is a distributed private information retrieval (PIR)
protocol, where the responder delegates its work to alleviate PIR's
computational bottleneck and catches misbehaving delegates by efficiently
verifying their results. We introduce DPIR, a messaging system that uses
distributed PIR to let a server storing messages delegate the work to the
system's clients, such that each client contributes proportional processing to
the number of messages it reads. The server removes clients returning invalid
results, which DPIR leverages to integrate an incentive mechanism for honest
client behavior by conditioning messaging through DPIR on correctly processing
PIR requests from other users. The result is a metadata-private messaging system
that asymptotically improves scalability over prior work with the same threat
model. We show through experiments on a prototype implementation that DPIR
concretely improves performance by $3.25\times$ and $4.31\times$ over prior
work and that the performance gap grows
with the user base size.

## 2024/979

* Title: Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs
* Authors: Alex Ozdemir, Evan Laufer, Dan Boneh
* [Permalink](https://eprint.iacr.org/2024/979)
* [Download](https://eprint.iacr.org/2024/979.pdf)

### Abstract

In verifiable outsourcing, an untrusted server runs an expensive computation and produces a succinct proof (called a SNARK) of the results. In many scenarios, the computation accesses a RAM that the server maintains a commitment to (persistent RAM) or that is initially zero (volatile RAM). But, SNARKs for such scenarios are limited by the high overheads associated with existing techniques for RAM checking. We develop new proofs about volatile, persistent, and sparse persistent RAM that reduce SNARK proving times. Our results include both asymptotic and concrete improvements---including a proving time reduction of up to 51.3$\times$ for persistent RAM. Along the way, we apply two tools that may be of independent interest. First, we generalize an existing construction to convert any algebraic interactive proof (AIP) into a SNARK. An AIP is a public-coin, non-succinct, interactive proof with a verifier that is an arithmetic circuit. Second, we apply Bézout's identity for polynomials to construct new AIPs for uniqueness and disjointness. These are useful for showing the independence of accesses to different addresses.

## 2024/980

* Title: FaultyGarble: Fault Attack on Secure Multiparty Neural Network Inference
* Authors: Mohammad Hashemi, Dev Mehta, Kyle Mitard, Shahin Tajik, Fatemeh Ganji
* [Permalink](https://eprint.iacr.org/2024/980)
* [Download](https://eprint.iacr.org/2024/980.pdf)

### Abstract

The success of deep learning across a variety of
applications, including inference on edge devices, has led to
increased concerns about the privacy of users’ data and deep
learning models. Secure multiparty computation allows parties
to remedy this concern, resulting in a growth in the number
of such proposals and improvements in their efficiency. The
majority of secure inference protocols relying on multiparty
computation assume that the client does not deviate from the
protocol and passively attempts to extract information. Yet
clients, driven by different incentives, can act maliciously to
actively deviate from the protocol and disclose the deep learning
model owner’s private information. Interestingly, faults are
well understood in multiparty computation-related literature,
although fault attacks have not been explored. Our paper
introduces the very first fault attack against secure inference
implementations relying on garbled circuits as a prime example
of multiparty computation schemes. In this regard, laser fault
injection coupled with a model-extraction attack is successfully
mounted against existing solutions that have been assumed to
be secure against active attacks. Notably, the number of queries
required for the attack is equal to that of the best model extraction
attack mounted against the secure inference engines
under the semi-honest scenario.

## 2024/981

* Title: Hadamard Product Arguments and Their Applications
* Authors: Kyeongtae Lee, Donghwan Oh, Hankyung Ko, Jihye Kim, Hyunok Oh
* [Permalink](https://eprint.iacr.org/2024/981)
* [Download](https://eprint.iacr.org/2024/981.pdf)

### Abstract

This paper introduces transparent and efficient arguments for Hadamard products between committed vectors from two source groups. For vectors of length $n$, the proofs consist of $\mathcal{O}(\log n)$ target group elements and $\mathcal{O}(1)$ additional elements. The verifier's workload is dominated by $\mathcal{O}(\log n)$ multi-exponentiations in the target group and $\mathcal{O}(1)$ pairings. We prove our security under the standard SXDH assumption. Additionally, we propose an aggregator for Groth16 pairing-based zk-SNARKs and a proof aggregation technique for the general case of the KZG pairing-based polynomial commitment scheme using our Hadamard product arguments. Both applications support logarithmic-sized aggregated proofs without requiring an additional trusted setup, significantly reducing the verifier’s pairing operations to $\mathcal{O}(1)$.

## 2024/982

* Title: SoK: Programmable Privacy in Distributed Systems
* Authors: Daniel Benarroch, Bryan Gillespie, Ying Tong Lai, Andrew Miller
* [Permalink](https://eprint.iacr.org/2024/982)
* [Download](https://eprint.iacr.org/2024/982.pdf)

### Abstract

This Systematization of Knowledge conducts a survey of contemporary distributed blockchain protocols, with the aim of identifying cryptographic and design techniques which practically enable both expressive programmability and user data confidentiality. To facilitate a framing which supports the comparison of concretely very different protocols, we define an epoch-based computational model in the form of a flexible UC-style ideal functionality which divides the operation of privacy-preserving networks into three phases: Independent, Mediated, and Global computation. Our analysis of protocols focuses in particular on features of the Mediated computation phase, which provides the facility to execute non-trivial program logic on private inputs from multiple users. Specifically, we compare implementations in different protocols for private limit order auctions, which we find to be a representative application which is common and relatively simple, but which exhibits adversarial dynamics which demonstrate the capabilities of a non-trivial Mediated computation mechanism. In our analysis, we identify four protocols representative of different high-level approaches used to implement Mediated computations. We compare protocols according to the degree and flexibility of programmability, the privacy properties achieved, and the security assumptions required for correct operation. We conclude by offering recommendations and best practices for future programmable privacy designs.

## 2024/983

* Title: SoCureLLM: An LLM-driven Approach for Large-Scale System-on-Chip Security Verification and Policy Generation
* Authors: Shams Tarek, Dipayan Saha, Sujan Kumar Saha, Mark Tehranipoor, Farimah Farahmandi
* [Permalink](https://eprint.iacr.org/2024/983)
* [Download](https://eprint.iacr.org/2024/983.pdf)

### Abstract

Contemporary methods for hardware security verification struggle with adaptability, scalability, and availability due to the increasing complexity of the modern system-on-chips (SoCs). Large language models (LLMs) have emerged as a viable approach to address these shortcomings in security verification because of their natural language understanding, advanced reasoning, and knowledge transfer capabilities. However, their application to large designs is limited by inherent token limitation and memorization constraints. In this paper, we introduce SoCureLLM, an LLM-based framework that excels in identifying security vulnerabilities within SoC designs and creating a comprehensive security policy database. Our framework is adaptable and adept at processing varied, large-scale designs, overcoming the abovementioned issues of LLM. In evaluations, SoCureLLM detected 76.47% of security bugs across three vulnerable RISC-V SoCs, outperforming the state-of-the-art security verification methods. Furthermore, assessing three additional large-scale RISC-V SoC designs against various threat models led to the formulation of 84 novel security policies, enriching the security policy database. Previously requiring extensive manual effort to craft, these newly generated security policies can be used as guidelines for developing secured SoC designs.

## 2024/984

* Title: Side-Channel and Fault Resistant ASCON Implementation: A Detailed Hardware Evaluation (Extended Version)
* Authors: Aneesh Kandi, Anubhab Baksi, Peizhou Gan, Sylvain Guilley, Tomáš Gerlich, Jakub Breier, Anupam Chattopadhyay, Ritu Ranjan Shrivastwa, Zdeněk Martinásek, Shivam Bhasin
* [Permalink](https://eprint.iacr.org/2024/984)
* [Download](https://eprint.iacr.org/2024/984.pdf)

### Abstract

In this work, we present various hardware implementations for the lightweight cipher ASCON, which was recently selected as the winner of the NIST organized Lightweight Cryptography (LWC) competition. We cover encryption + tag generation and decryption + tag verification for the ASCON hash function and ASCON AEAD. On top of the usual (unprotected) implementation, we present side-channel protection (threshold countermeasure) and triplication/majority-based fault protection. To the best of our knowledge, this is the first protected hardware implementation of ASCON with respect to side-channel and fault inject protection. The side-channel and fault protections work orthogonal to each other (i.e., either one can be turned on/off without affecting the other). We present ASIC and FPGA benchmarks for all our implementations (hash and AEAD) with/without countermeasures for varying input sizes.

## 2024/985

* Title: DualRing-PRF: Post-Quantum (Linkable) Ring Signatures from Legendre and Power Residue PRFs
* Authors: Xinyu Zhang, Ron Steinfeld, Joseph K. Liu, Muhammed F. Esgin, Dongxi Liu, Sushmita Ruj
* [Permalink](https://eprint.iacr.org/2024/985)
* [Download](https://eprint.iacr.org/2024/985.pdf)

### Abstract

Ring signatures are one of the crucial cryptographic primitives used in the design of privacy-preserving systems. Such a signature scheme allows a signer to anonymously sign a message on behalf of a spontaneously formed group. It not only ensures the authenticity of the message but also conceals the true signer within the group. An important extension of ring signatures is linkable ring signatures, which prevent a signer from signing twice without being detected (under some constraints). Linkable ring signatures offer advantages in applications where full anonymity might jeopardise the intended purpose, such as privacy-oriented cryptocurrencies like Monero.

In this work, we introduce post-quantum ring signature (DualRing-PRF) and linkable ring signature (DualRingL-PRF) schemes whose security solely rely on symmetric-key primitives (namely, Legendre PRF and power residue PRF). Our construction of the ring signature departs from previous approaches with similar security assumptions, offering the most competitive signature sizes for small and medium-sized rings. In particular, for a ring size of 16, DualRing-PRF has a communication overhead 1.4 times smaller than the state-of-the-art scheme proposed by Goel et al. (PETS’21). Furthermore, we demonstrate the extension of DualRing-PRF to incorporate linkability and non-slanderability. Compared to the existing one-time traceable ring signature (a variant of linkable ring signature) by Scafuro and Zhang (ESORICS’21), our construction supports many-time signing and achieves significantly smaller signature sizes when ring size exceeds 16. This advantage becomes more pronounced as the ring size increases.

## 2024/986

* Title: FABESA: Fast (and Anonymous) Attribute-Based Encryption under Standard Assumption
* Authors: Long Meng, Liqun Chen, Yangguang Tian, Mark Manulis
* [Permalink](https://eprint.iacr.org/2024/986)
* [Download](https://eprint.iacr.org/2024/986.pdf)

### Abstract

Attribute-Based Encryption (ABE) provides fine-grained access control to encrypted data and finds applications in various domains. The practicality of ABE schemes hinges on the balance between security and efficiency. The state-of-the-art adaptive secure ABE scheme, proven to be adaptively secure under standard assumptions (FAME, CCS'17), is less efficient compared to the fastest one (FABEO, CCS'22) which is only proven secure under the Generic Group Model (GGM). These traditional ABE schemes focus solely on message privacy. To address scenarios where attribute value information is also sensitive, Anonymous ABE (${\rm A}^{\rm 2}$BE) ensures the privacy of both the message and attributes. However, most ${\rm A}^{\rm 2}$BE schemes suffer from intricate designs with low efficiency, and the security of the fastest key-policy ${\rm A}^{\rm 2}$BE (proposed in FEASE, USENIX'24) relies on the GGM.

In this paper, we propose novel fast key-policy and ciphertext-policy ABE schemes that (1) support both AND and OR gates for access policies, (2) have no restriction on the size and type of policies or attributes, (3) achieve adaptive security under the standard DLIN assumption, and (4) only need 4 pairings for decryption. As our ABE constructions automatically provide ciphertext anonymity, we easily transform our ABE schemes to ${\rm A}^{\rm 2}$BE schemes while maintaining the same features and high-level efficiency.

The implementation results show that all our schemes achieve the best efficiency comparing to other schemes with adaptive security proven under standard assumptions. Specifically, our ABE schemes perform better than FAME and are close to FABEO. Our key-policy ${\rm A}^{\rm 2}$BE scheme performs close to the one in FEASE and our ciphertext-policy ${\rm A}^{\rm 2}$BE outperforms the state-of-the-art (Cui et al., ProvSec'16).

## 2024/987

* Title: CoGNN: Towards Secure and Efficient Collaborative Graph Learning
* Authors: Zhenhua Zou, Zhuotao Liu, Jinyong Shan, Qi Li, Ke Xu, Mingwei Xu
* [Permalink](https://eprint.iacr.org/2024/987)
* [Download](https://eprint.iacr.org/2024/987.pdf)

### Abstract

Collaborative graph learning represents a learning paradigm where multiple parties jointly train a graph neural network (GNN) using their own proprietary graph data. To honor the data privacy of all parties, existing solutions for collaborative graph learning are either based on federated learning (FL) or secure machine learning (SML). Although promising in terms of efficiency and scalability due to their distributed training scheme, FL-based approaches fall short in providing provable security guarantees and achieving good model performance. Conversely, SML-based solutions, while offering provable privacy guarantees, are hindered by their high computational and communication overhead, as well as poor scalability as more parties participate.

To address the above problem, we propose CoGNN, a novel framework that simultaneously reaps the benefits of both FL-based and SML-based approaches. At a high level, CoGNN is enabled by (i) a novel message passing mechanism that can obliviously and efficiently express the vertex data propagation/aggregation required in GNN training and inference and (ii) a two-stage Dispatch-Collect execution scheme to securely decompose and distribute the GNN computation workload for concurrent and scalable executions. We further instantiate the CoGNN framework, together with customized optimizations, to train Graph Convolutional Network (GCN) models. Extensive evaluations on three graph datasets demonstrate that compared with the state-of-the-art (SOTA) SML-based approach, CoGNN reduces up to $123$x running time and up to $522$x communication cost per party. Meanwhile, the GCN models trained using CoGNN have nearly identical accuracies as the plaintext global-graph training, yielding up to $11.06\%$ accuracy improvement over the GCN models trained via federated learning.

## 2024/988

* Title: Privacy-Preserving Dijkstra
* Authors: Benjamin Ostrovsky
* [Permalink](https://eprint.iacr.org/2024/988)
* [Download](https://eprint.iacr.org/2024/988.pdf)

### Abstract

Given a graph $G(V,E)$, represented as a secret-sharing of an adjacency list, we show how to obliviously convert it into an alternative, MPC-friendly secret-shared representation, so-called $d$-normalized replicated adjacency list (which we abbreviate to $d$-normalized), where the size of our new data-structure is only 4x larger -- compared to the original (secret-shared adjacency list) representation of $G$. Yet, this new data structure enables us to execute oblivious graph algorithms that simultaneously improve underlying graph algorithms' round, computation, and communication complexity. Our $d$-normalization proceeds in two steps:

First, we show how for any graph $G$, given a secret-shared adjacency list, where vertices are arbitrary alphanumeric strings that fit into a single RAM memory word, we can efficiently and securely rename vertices to integers from $1$ to $V$ that will appear in increasing order in the resulting secret-shared adjacency list. The secure renaming takes $O(\log V)$ rounds and $O((V+E)\log V)$ secure operations. Our algorithm also outputs in a secret-shared form two arrays: a mapping from integers to alphanumeric names and its sorted inverse. Of course, if the adjacency list is already in such an integer format, this step could be skipped.

Second, given a secret-shared adjacency list for any graph $G$, where vertices are integers from $1$ to $V$ and are sorted, there exists a $d$-normalization
algorithm that takes $O(1)$ rounds and $O((V+E))$ secure operations.

We believe that both conversions are of independent interest. We demonstrate the power of our data structures by designing a privacy-preserving Dijkstra's single-source shortest-path algorithm that simultaneously achieves
$O\left((V +E) \cdot \log V \right)$ secure operations and $O(V \cdot \log V \cdot \log \log\log V)$ rounds. Our secure Dijkstra algorithm works for any adjacency list representation as long as all vertex labels and weights can individually fit into RAM memory word.
Our algorithms work for two or a constant number of servers in the honest but curious setting. The limitation of our result (to only a constant number of servers) is due to our reliance on linear work and constant-round secure shuffle.

## 2024/989

* Title: A Formal Treatment of End-to-End Encrypted Cloud Storage
* Authors: Matilda Backendal, Hannah Davis, Felix Günther, Miro Haller, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2024/989)
* [Download](https://eprint.iacr.org/2024/989.pdf)

### Abstract

Users increasingly store their data in the cloud, thereby benefiting from easy access, sharing, and redundancy. To additionally guarantee security of the outsourced data even against a server compromise, some service providers have started to offer end-to-end encrypted (E2EE) cloud storage. With this cryptographic protection, only legitimate owners can read or modify the data. However, recent attacks on the largest E2EE providers have highlighted the lack of solid foundations for this emerging type of service.

In this paper, we address this shortcoming by initiating the formal study of E2EE cloud storage. We give a formal syntax to capture the core functionality of a cloud storage system, capturing the real-world complexity of such a system's constituent interactive protocols. We then define game-based security notions for confidentiality and integrity of a cloud storage system against a fully malicious server. We treat both selective and fully adaptive client compromises. Our notions are informed by recent attacks on E2EE cloud storage providers. In particular we show that our syntax is rich enough to capture the core functionality of MEGA and that recent attacks on it arise as violations of our security notions. Finally, we present an E2EE cloud storage system that provides all core functionalities and that is both efficient and provably secure with respect to our selective security notions. Along the way, we discuss challenges on the path towards bringing the security of cloud storage up to par with other end-to-end primitives, such as secure messaging and TLS.

## 2024/990

* Title: Perfectly-secure Network-agnostic MPC with Optimal Resiliency
* Authors: Shravani Patil, Arpita Patra
* [Permalink](https://eprint.iacr.org/2024/990)
* [Download](https://eprint.iacr.org/2024/990.pdf)

### Abstract

We study network-agnostic secure multiparty computation with perfect security.. Traditionally MPC is studied assuming the underlying network is either synchronous or asynchronous. In a network-agnostic setting, the parties are unaware of whether the underlying network is synchronous or asynchronous.

The feasibility of perfectly-secure MPC in synchronous and asynchronous networks has been settled a long ago. The landmark work of [Ben-Or, Goldwasser, and Wigderson, STOC'88] shows that $n > 3t_s$ is necessary and sufficient for any MPC protocol with $n$-parties over synchronous network tolerating $t_s$ active corruptions. In yet another foundational work, [Ben-Or, Canetti, and Goldreich, STOC'93] show that the bound for asynchronous network is $n > 4t_a$, where $t_a$ denotes the number of active corruptions. However, the same question remains unresolved for network-agnostic setting till date. In this work, we resolve this long-standing question.

We show that perfectly-secure network-agnostic $n$-party MPC tolerating $t_s$ active corruptions when the network is synchronous and $t_a$ active corruptions when the network is asynchronous is possible if and only if $n > 2 \max(t_s,t_a) + \max(2t_a,t_s)$.

When $t_a \geq t_s$, our bound reduces to $n > 4t_a$, whose tightness follows from the known feasibility results for asynchronous MPC. When $t_s > t_a$, our result gives rise to a new bound of $n > 2t_s + \max(2t_a,t_s)$. Notably, the previous network-agnostic MPC in this setting [Appan, Chandramouli, and Choudhury, PODC'22] only shows sufficiency for a loose bound of $n > 3t_s + t_a$. When $t_s > 2t_a$, our result shows tightness of $ n > 3t_s$, whereas the existing work shows sufficiency for $n > 3t_s+t_a$.

## 2024/991

* Title: Leveled Homomorphic Encryption Schemes for Homomorphic Encryption Standard
* Authors: Shuhong Gao, Kyle Yates
* [Permalink](https://eprint.iacr.org/2024/991)
* [Download](https://eprint.iacr.org/2024/991.pdf)

### Abstract

Homomorphic encryption allows for computations on encrypted data without exposing the underlying plaintext, enabling secure and private data processing in various applications such as cloud computing and machine learning. This paper presents a comprehensive mathematical foundation for three prominent homomorphic encryption schemes: Brakerski-Gentry-Vaikuntanathan (BGV), Brakerski-Fan-Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS), all based on the Ring Learning with Errors (RLWE) problem. We align our discussion with the functionalities proposed in the recent homomorphic encryption standard, providing detailed algorithms and correctness proofs for each scheme. Additionally, we propose improvements to the current schemes focusing on noise management and optimization of public key encryption and leveled homomorphic computation. Our modifications ensure that the noise bound remains within a fixed function for all levels of computation, guaranteeing correct decryption and maintaining efficiency comparable to existing methods. The proposed enhancements reduce ciphertext expansion and storage requirements, making these schemes more practical for real-world applications.

## 2024/992

* Title: The Complexity of the Crossbred Algorithm
* Authors: Damien VIDAL, Sorina IONICA, Claire Delaplace
* [Permalink](https://eprint.iacr.org/2024/992)
* [Download](https://eprint.iacr.org/2024/992.pdf)

### Abstract

The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over $\mathbb{F}_2$. Since its publication in 2015, several record breaking implementations have been proposed and demonstrate the power of this hybrid approach. Despite these practical results, the complexity of this algorithm and the choice of optimal parameters for it are difficult open questions. In this paper, we prove a bivariate generating series for potentially admissible parameters of the Crossbred algorithm.

## 2024/993

* Title: Limits on the Power of Prime-Order Groups: Separating Q-Type from Static Assumptions
* Authors: George Lu, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/993)
* [Download](https://eprint.iacr.org/2024/993.pdf)

### Abstract

Subgroup decision techniques on cryptographic groups and pairings have been critical for numerous applications. Originally conceived in the composite-order setting, there is a large body of work showing how to instantiate subgroup decision techniques in the prime-order setting as well. In this work, we demonstrate the first barrier to this research program, by demonstrating an important setting where composite-order techniques cannot be replicated in the prime-order setting.

In particular, we focus on the case of $q$-type assumptions, which are ubiquitous in group- and pairing-based cryptography, but unfortunately are less desirable than the more well-understood static assumptions. Subgroup decision techniques have had great success in removing $q$-type assumptions, even allowing $q$-type assumptions to be generically based on static assumptions on composite-order groups. Our main result shows that the same likely does not hold in the prime order setting. Namely, we show that a large class of $q$-type assumptions, including the security definition of a number of cryptosystems, cannot be proven secure in a black box way from any static assumption.

## 2024/994

* Title: On Knowledge-Soundness of Plonk in ROM from Falsifiable Assumptions
* Authors: Helger Lipmaa, Roberto Parisella, Janno Siim
* [Permalink](https://eprint.iacr.org/2024/994)
* [Download](https://eprint.iacr.org/2024/994.pdf)

### Abstract

Lipmaa, Parisella, and Siim [Eurocrypt, 2024] proved the extractability of the KZG polynomial commitment scheme under the falsifiable assumption ARSDH. They also showed that variants of real-world zk-SNARKs like Plonk can be made knowledge-sound in the random oracle model (ROM) under the ARSDH assumption. However, their approach did not consider various batching optimizations, resulting in their variant of Plonk having approximately 3.5 times longer argument.. Our contributions are: (1) We prove that several batch-opening protocols for KZG, used in modern zk-SNARKs, have computational special-soundness under the ARSDH assumption. (2) We prove that interactive Plonk has computational special-soundness under the ARSDH assumption and a new falsifiable assumption TriRSDH. We also prove that a minor modification of the interactive Plonk has computational special-soundness under only the ARSDH assumption. The Fiat-Shamir transform can be applied to obtain non-interactive versions, which are secure in the ROM under the same assumptions.

## 2024/995

* Title: Cross-chain bridges via backwards-compatible SNARKs
* Authors: Sergio Juárez, Mark Blunden, Joris Koopman, Anish Mohammed, Kapil Shenvi Pause, Steve Thakur
* [Permalink](https://eprint.iacr.org/2024/995)
* [Download](https://eprint.iacr.org/2024/995.pdf)

### Abstract

In recent years, SNARKs have shown great promise as a tool for building trustless bridges to connect the heterogeneous ecosystem of blockchains. Unfortunately, the parameters hardwired for many of the widely used blockchains are incongruous with the conventional SNARKs, which results in unsatisfactory performance. This bottleneck necessitates new proof systems tailored for efficiency in these environments.

The primary focus of this paper is on succinct bridges from Cosmos to Ethereum, which largely boils down to efficient proofs of multiple Ed25519 signatures. However, these techniques can be ported to settings that require succinct proofs of multiple secp256k1 or BLS12-381 signatures.

We describe our succinct validity bridging scheme Overfly, which uses a field-agnostic SNARK to circumvent the huge overhead of non-native field arithmetic arising from Ed25519 scalar multiplications in the circuit. We also explore the schemes deVirgo and zkTree, which exploit the parallelization of proof generation and the subsequent aggregation of proofs.

Our benchmarks indicate that it is crucial to sidestep non-native arithmetic to the extent that it is possible. We also found that two or more proof systems need to be securely amalgamated to optimize a succinct validity bridging scheme.

## 2024/996

* Title: Great-LaKeys: An Improved Threshold-PRF and a Novel Exponent-VRF from LWR
* Authors: Matthias Geihs
* [Permalink](https://eprint.iacr.org/2024/996)
* [Download](https://eprint.iacr.org/2024/996.pdf)

### Abstract

Building on the recently proposed LWR-based threshold-PRF LaKey, we propose two new constructions. First, we propose an optimized threshold-PRF with significantly reduced round and communication complexity. We achieve this by improving the underlying bit truncation protocol, as well as the lower bound on the required number of LWR instances. Second, we show that the same underlying PRF construction lends itself as a basis for a novel and efficient exponent-VRF. We implement prototypes of both of our contributions and demonstrate their practical performance.

## 2024/997

* Title: Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers
* Authors: Daniel Escudero, Antigoni Polychroniadou, Yifan Song, Chenkai Weng
* [Permalink](https://eprint.iacr.org/2024/997)
* [Download](https://eprint.iacr.org/2024/997.pdf)

### Abstract

In this work we study the efficiency of Zero-Knowledge (ZK) arguments of knowledge, particularly exploring Multi-Verifier ZK (MVZK) protocols as a midway point between Non-Interactive ZK and Designated-Verifier ZK, offering versatile applications across various domains. We introduce a new MVZK protocol designed for the preprocessing model, allowing any constant fraction of verifiers to be corrupted, potentially colluding with the prover. Our contributions include the first MVZK over rings. Unlike recent prior works on fields in the dishonest majority case, our protocol demonstrates communication complexity independent of the number of verifiers, contrasting the linear complexity of previous approaches. This key advancement ensures improved scalability and efficiency. We provide an end-to-end implementation of our protocol. The benchmark shows that it achieves a throughput of 1.47 million gates per second for 64 verifiers with $50\%$ corruption, and 0.88 million gates per second with $75\%$ corruption.

## 2024/998

* Title: Measuring Conditional Anonymity - A Global Study
* Authors: Pascal Berrang, Paul Gerhart, Dominique Schröder
* [Permalink](https://eprint.iacr.org/2024/998)
* [Download](https://eprint.iacr.org/2024/998.pdf)

### Abstract

The realm of digital health is experiencing a global surge, with mobile applications extending their reach into various facets of daily life. From tracking daily eating habits and vital functions to monitoring sleep patterns and even the menstrual cycle, these apps have become ubiquitous in their pursuit of comprehensive health insights.
Many of these apps collect sensitive data and promise users to protect their privacy - often through pseudonymization. We analyze the real anonymity that users can expect by this approach and report on our findings. More concretely:

1. We introduce the notion of conditional anonymity sets derived from statistical properties of the population.
2. We measure anonymity sets for two real-world applications and present overarching findings from 39 countries.
3. We develop a graphical tool for people to explore their own anonymity set.

One of our case studies is a popular app for tracking the menstruation cycle. Our findings for this app show that, despite their promise to protect privacy, the collected data can be used to identify users up to groups of 5 people in 97% of all the US counties, allowing the de-anonymization of the individuals. Given that the US Supreme Court recently overturned abortion rights, the possibility
of determining individuals is a calamity.

## 2024/999

* Title: ProxCode: Efficient Biometric Proximity Searchable Encryption from Error Correcting Codes
* Authors: Maryam Rezapour, Benjamin Fuller
* [Permalink](https://eprint.iacr.org/2024/999)
* [Download](https://eprint.iacr.org/2024/999.pdf)

### Abstract

This work builds approximate proximity searchable encryption. Secure biometric databases are the primary application. Prior work (Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC ’98), and oblivious multimaps. The multimap associates LSH outputs as keywords to biometrics as values.

When the desired result set is of size at most one, we show a new preprocessing technique and system called ProxCode that inserts shares of a linear secret sharing into the map instead of the full biometric. Instead of choosing shares independently, shares are correlated so exactly one share is associated with each keyword/LSH output. As a result, one can rely on a map instead of a multimap. Secure maps are easier to construct with low leakage than multimaps.

For many parameters, this approach reduces the required number of LSHs for a fixed accuracy. Our scheme yields the most improvement when combining a high accuracy requirement with a biometric with large underlying noise. Our approach builds on any secure map. We evaluate the scheme accuracy for both iris data and random data.

## 2024/1000

* Title: File-Injection Attacks on Searchable Encryption, Based on Binomial Structures
* Authors: Tjard Langhout, Huanhuan Chen, Kaitai Liang
* [Permalink](https://eprint.iacr.org/2024/1000)
* [Download](https://eprint.iacr.org/2024/1000.pdf)

### Abstract

One distinguishable feature of file-inject attacks on searchable encryption schemes is the 100% query recovery rate, i.e., confirming the corresponding keyword for each query. The main efficiency consideration of file-injection attacks is the number of injected files. In the work of Zhang et al. (USENIX 2016), $|\log_2|K||$ injected files are required, each of which contains $|K|/2$ keywords for the keyword set $K$. Based on the construction of the uniform $(s,n)$-set, Wang et al. need fewer injected files when considering the threshold countermeasure. In this work, we propose a new attack that further reduces the number of injected files where Wang et al. need up to 38% more injections to achieve the same results. The attack is based on an increment $(s,n)$-set, which is also defined in this paper.

## 2024/1001

* Title: Guidance for Efficient Selection of Secure Parameters for Fully Homomorphic Encryption
* Authors: Elena Kirshanova, Chiara Marcolla, Sergi Rovira
* [Permalink](https://eprint.iacr.org/2024/1001)
* [Download](https://eprint.iacr.org/2024/1001.pdf)

### Abstract

The field of Fully Homomorphic Encryption (FHE) has seen many theoretical and computational advances in recent years, bringing the technology closer to practicality than ever before. For this reason, practitioners from neighbouring fields such as machine learning have sought to understand FHE to provide privacy to their work. Unfortunately, selecting secure and efficient parameters in FHE is a daunting task due to the many interdependencies between the parameters involved. In this work, we solve this problem by moving away from the standard parameter selection procedure, introducing formulas which provide secure and optimal parameters for any lattice-based scheme. We build our formulas from a strong theoretical foundation based on cryptanalysis against LWE.

## 2024/1002

* Title: Elementary Formulas for Greatest Common Divisors and Semiprime Factors
* Authors: Joseph M. Shunia
* [Permalink](https://eprint.iacr.org/2024/1002)
* [Download](https://eprint.iacr.org/2024/1002.pdf)

### Abstract

We present new formulas for computing greatest common divisors (GCDs) and extracting the prime factors of semiprimes using only elementary arithmetic operations: addition, subtraction, multiplication, floored division, and exponentiation. Our GCD formula simplifies a result of Mazzanti, and is derived using Kronecker substitution techniques from our previous work. We utilize the GCD formula, along with recent developments on arithmetic terms for square roots and factorials, to derive explicit expressions for the prime factors of a semiprime $n=pq$.

## 2024/1003

* Title: zkVoting : Zero-knowledge proof based coercion-resistant and E2E verifiable e-voting system
* Authors: Seongho Park, Jaekyoung Choi, Jihye Kim, Hyunok Oh
* [Permalink](https://eprint.iacr.org/2024/1003)
* [Download](https://eprint.iacr.org/2024/1003.pdf)

### Abstract

We introduce ${zkVoting}$, a coercion-resistant e-voting system that utilizes a fake keys approach based on a novel nullifiable commitment scheme. This scheme allows voters to receive both real and fake commitment keys from a registrar. Each ballot includes this commitment, but only the tallier can efficiently discern the fake ballots, simplifying the tally process to $\mathcal{O}(n)$ and ensuring coercion resistance. ${zkVoting}$ also preserves voter anonymity by ensuring each ballot conceals the voter's identity. Additionally, by integrating zero-knowledge proofs, ${zkVoting}$ achieves end-to-end (E2E) verifiability. We formally prove its security and demonstrate its practicality for real-world applications, with a ballot casting time of 2.3 seconds and a tally time of 3.9 milliseconds per ballot.

## 2024/1004

* Title: Relaxed Vector Commitment for Shorter Signatures
* Authors: Seongkwang Kim, Byeonghak Lee, Mincheol Son
* [Permalink](https://eprint.iacr.org/2024/1004)
* [Download](https://eprint.iacr.org/2024/1004.pdf)

### Abstract

The MPC-in-the-Head (MPCitH) paradigm has recently gained traction as a foundation for post-quantum signature schemes, offering robust security without the need for trapdoors. Despite its strong security profile, MPCitH-based schemes suffer from high computational overhead and large signature sizes, limiting their practical application.

This work addresses these inefficiencies by enhancing vector commitments within MPCitH-based schemes. We introduce the concept of vector semi-commitment, which relaxes traditional vector commitment requirements without compromising security, thus reducing signature size while maintaining performance. We instantiate vector semi-commitment schemes in both the random oracle model and the ideal cipher model, leveraging recent optimizations such as the Half-tree technique. Additionally, we propose a key injection technique that further minimizes signature size by embedding the secret key into the Half-GGM tree.

We apply these improvements to the BN++ signature scheme and prove it fully secure in the ideal cipher model. Implementing these improvements in the $\mathsf{AIMer}$ v2.0 signature scheme, we achieve up to 18% shorter signatures and up to 112% faster signing and verification speeds, setting new benchmarks for MPCitH-based schemes.

## 2024/1005

* Title: Differential Fault Attack on HE-Friendly Stream Ciphers: Masta, Pasta and Elisabeth
* Authors: Weizhe Wang, Deng Tang
* [Permalink](https://eprint.iacr.org/2024/1005)
* [Download](https://eprint.iacr.org/2024/1005.pdf)

### Abstract

In this paper, we propose the Differential Fault Attack (DFA) on three Homomorphic Encryption (HE) friendly stream ciphers Masta, Pasta, and Elisabeth. Both Masta and Pasta are Rasta-like ciphers with publicly derived and pseudorandom affine layers. The design of Elisabeth is an extension of FLIP and FiLIP, following the group filter permutator paradigm. All these three ciphers operate on elements over $\mathbb{Z}_p$ or $\mathbb{Z}_{2^n}$, rather than $\mathbb{Z}_2$. We can recover the secret keys of all the targeted ciphers through DFA. In particular, for Elisabeth, we present a new method to determine the filtering path, which is vital to make the attack practical. Our attacks on various instances of Masta are practical and require only one block of keystream and a single word-based fault. By injecting three word-based faults, we can theoretically mount DFA on two instances of Pasta, Pasta-3 and Pasta-4. For our DFA on Elisabeth-4, the only instance of the Elisabeth family, a single bit-based fault injection is needed. With 15000 normal and faulty keystream words, the DFA on Elisabeth-4 can be completed within several minutes.

## 2024/1006

* Title: Delegated-Query Oblivious Transfer and its Practical Applications
* Authors: Yvo Desmedt, Aydin Abadi
* [Permalink](https://eprint.iacr.org/2024/1006)
* [Download](https://eprint.iacr.org/2024/1006.pdf)

### Abstract

Databases play a pivotal role in the contemporary World Wide Web and the world of cloud computing. Unfortunately, numerous privacy violations have recently garnered attention in the news. To enhance database privacy, we consider Oblivious Transfer (OT), an elegant cryptographic technology. Our observation reveals that existing research in this domain primarily concentrates on theoretical cryptographic applications, overlooking various practical aspects:

- OTs assume parties have direct access to databases. Our "1-out-of-2 Delegated-Query OT" enables parties to privately query a database, without direct access.

- With the rise of cloud computing, physically separated databases may no longer remain so. Our "1-out-of-2 Delegated-Query Multi-Receiver OT" protects privacy in such evolving scenarios.

- Research often ignores the limitations of thin clients, e.g., Internet of Things devices. To address this, we propose a compiler that transforms any 1-out-of-n OT into a thin client version.

## 2024/1007

* Title: On the vector subspaces of $\mathbb{F}_{2^n}$ over which the multiplicative inverse function sums to zero
* Authors: Claude Carlet
* [Permalink](https://eprint.iacr.org/2024/1007)
* [Download](https://eprint.iacr.org/2024/1007.pdf)

### Abstract

We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields), with respect to a recently introduced generalization of almost perfect nonlinearity (APN), called $k$th-order sum-freedom, that extends a classical characterization of APN functions, and has also some relationship with integral attacks. This generalization corresponds to the fact that a vectorial function $F:\mathbb F_2^n\mapsto \mathbb F_2^m$ sums to a nonzero value over every $k$-dimensional affine subspace of $\mathbb F_2^n$, for some $k\leq n$. The sum of the values of the inverse function $x\in \mathbb F_{2^n}\mapsto x^{2^n-2}\in \mathbb F_{2^n}$ over any affine subspace $A$ of $\mathbb{F}_{2^n}$ not containing 0 (i.e. being not a vector space) is easy to address: there exists a simple expression of such sum which shows that it never vanishes. We study in the present paper the case of a vector subspace (a linear subspace), which is much less simple to handle. We show that the sum depends on a coefficient in subspace polynomials. We derive several expressions of this coefficient. Then we study for which values of $k$ the multiplicative inverse function can sum to nonzero values over all $k$-dimensional vector subspaces. We show that, for every $k$ not co-prime with $n$, it sums to zero over at least one $k$-dimensional $\mathbb{F}_2$-subspace of $\mathbb{F}_{2^n}$. We study the behavior of the inverse function over direct sums of vector spaces and we deduce that the property of the inverse function to be $k$th-order sum-free happens for $k$ if and only if it happens for $n-k$. We derive several results on the sums of values of the inverse function over vector subspaces, addressing in particular the cases of dimension at most 3 (equivalently, of co-dimension at most 3).. We leave other cases open and provide computer investigation results.

## 2024/1008

* Title: A Deep Study of The Impossible Boomerang Distinguishers: New Construction Theory and Automatic Search Methods
* Authors: Xichao Hu, Dengguo Feng, Lin Jiao, Yonglin Hao, Xinxin Gong, Yongqiang Li
* [Permalink](https://eprint.iacr.org/2024/1008)
* [Download](https://eprint.iacr.org/2024/1008.pdf)

### Abstract

The impossible boomerang attack (IBA) is a combination of the impossible differential attack and boomerang attack, which has demonstrated remarkable power in the security evaluation of AES and other block ciphers. However, this method has not received sufficient attention in the field of symmetric cipher analysis. The only existing search method for impossible boomerang distinguishers (IBD), the core of IBAs, is the $\mathcal{UB}\text{-method}$, but it is considered rather rudimentary given current technological advancements and may result in missed opportunities for effective attacks. Therefore, this paper delves into a comprehensive study on the construction theory and automatic search method of IBDs.

Theoretically, we propose 5 IBD constructions aligned with the techniques of arbitrary S-box, boomerang distinguisher, Boomerang Connectivity Table, U/L/EBCT and mixed tables for differential propagation for SPN-network block ciphers, and 2 IBD constructions accompanied by state propagation for block ciphers with any structure. Furthermore, we investigate the relationship among these IBD constructions and demonstrate that the most superior IBD aligns precisely with the original definition. Technically, we develop a general SAT-based automatic search tool for IBDs by introducing optimized search strategies of the composite model method and the mixed model method. This tool not only considers the details of each operation but also takes into account the impact of key schedule in a single-key setting.

As applications, we first acquire 59584 4-round 1 active word truncated IBDs for AES-128, and 192 of those IBDs cannot be detected by the $\mathcal{UB} \text{-method}$. For Midori64, we first demonstrate the non-existence of $7$-round $1$ active word truncated IBDs, and obtain $7296$ $6$-round $1$ active word truncated IBDs, which is complementary to the finding that there are no existing $6$-round $1$ active word truncated IDs. For PRESENT-80, we get the first 6-round IBDs which cannot be detected by the $\mathcal{UB}\text{-method}$. Those results indicate that our method outperforms the $\mathcal{UB}\text{-method}$ and offer an advantage over IDs. We believe that our work can bring new insights to symmetric cipher analysis.

## 2024/1009

* Title: Improved Reductions from Noisy to Bounded and Probing Leakages via Hockey-Stick Divergences
* Authors: Maciej Obremski, João Ribeiro, Lawrence Roy, François-Xavier Standaert, Daniele Venturi
* [Permalink](https://eprint.iacr.org/2024/1009)
* [Download](https://eprint.iacr.org/2024/1009.pdf)

### Abstract

There exists a mismatch between the theory and practice of cryptography in the presence of leakage. On the theoretical front, the bounded leakage model, where the adversary learns bounded-length but noiseless information about secret components, and the random probing model, where the adversary learns some internal values of a leaking implementation with some probability, are convenient abstractions to analyze the security of numerous designs. On the practical front, side-channel attacks produce long transcripts which are inherently noisy but provide information about all internal computations, and this noisiness is usually evaluated with closely related metrics like the mutual information or statistical distance. Ideally, we would like to claim that resilience to bounded leakage or random probing implies resilience to noisy leakage evaluated according to these metrics. However, prior work (Duc, Dziembowski and Faust, Eurocrypt 2014; Brian et al., Eurocrypt 2021) has shown that proving such reductions with useful parameters is challenging.

In this work, we study noisy leakage models stemming from hockey-stick divergences, which generalize statistical distance and are also the basis of differential privacy. First, we show that resilience to bounded leakage and random probing implies resilience to our new noisy leakage model with improved parameters compared to models based on the statistical distance or mutual information. Second, we establish composition theorems for our model, showing that these connections extend to a setting where multiple leakages are obtained from a leaking implementation. We complement our theoretical results with a discussion of practical relevance, highlighting that (i) the reduction to bounded leakage applies to realistic leakage functions with noise levels that are decreased by several orders of magnitude compared to Brian et al., and (ii) the reduction to random probing usefully generalizes the seminal work of Duc, Dziembowski, and Faust, although it remains limited when the field size in which masking operates grows (i.e., hockey-stick divergences can better hide the field size dependency of the noise requirements, but do not annihilate it).

## 2024/1010

* Title: FSSiBNN: FSS-based Secure Binarized Neural Network Inference with Free Bitwidth Conversion
* Authors: Peng Yang, Zoe Lin Jiang, Jiehang Zhuang, Junbin Fang, Siu Ming Yiu, Xuan Wang
* [Permalink](https://eprint.iacr.org/2024/1010)
* [Download](https://eprint.iacr.org/2024/1010.pdf)

### Abstract

Neural network inference as a service refers to the process where a cloud server holding a model provides inference services to a client initiating inference requests. Secure neural network inference built on this service ensures the privacy of both the cloud server's model and the client's data. A binarized neural network (BNN) is a type of neural network with binary weights and activations, expected to accelerate inference. When achieving secure BNN inference using multi-party computation, we must address the issue of non-uniform bitwidths, i.e., secure computation protocols cannot directly operate on values of different bitwidths and require bitwidth conversion. Existing bitwidth conversion schemes have to expand the bitwidths of weights and activations, incurring significant communication latency and computational load.

To address the above issues, we propose a secure BNN inference framework, FSSiBNN, with free bitwidth conversion based on function secret sharing (FSS). Specifically, by leveraging the property of FSS that supports arbitrary input and output bitwidths, we propose a bitwidth conversion embedding scheme. We naturally embed the bitwidth conversion into the FSS-based secure activation and max pooling computation, thereby avoiding the additional computational and communication overhead introduced by the bitwidth conversion. Moreover, we combine and convert multiple BNN layer functions into fewer matrix multiplication and comparison operations, and precompute multiplication tuples and FSS keys in the offline phase to achieve constant-round online inference.

In the experiment, we conduct tests on various datasets and models, and compare our results with state-of-the-art work. Compared to the existing best two-party framework XONN (USENIX Security '19), our work is approximately 7$\times$ faster in inference time and reduces communication overhead by about 577$\times$. Compared with the existing best three-party frameworks, SecureBiNN (ESORICS '22) and FLEXBNN (TIFS '23), our work is approximately 2.5$\times$ faster in inference time and reduces communication overhead by 1.3 to 16.4$\times$.

## 2024/1011

* Title: Secure Vickrey Auctions with Rational Parties
* Authors: Chaya Ganesh, Shreyas Gupta, Bhavana Kanukurthi, Girisha Shankar
* [Permalink](https://eprint.iacr.org/2024/1011)
* [Download](https://eprint.iacr.org/2024/1011.pdf)

### Abstract

In this work, we construct a second price (Vickrey) auction protocol (SPA), which does not require any auctioneers and ensures total privacy in the presence of rational parties participating in auction. In particular, the confidentiality of the highest bid and the identity of the second highest bidder are protected. We model the bidders participating in the second price auction as rational, computationally bounded and privacy-sensitive parties. These are self-interested agents who care about winning the auction more than learning about the private bids of other parties. A rational party does not deviate from the protocol arbitrarily but does so only for its own individual `advantage' -- without any consideration for others. Such an advantage is modeled using suitable utility functions.

We show that for rational and computationally bounded parties participating in our second-price auctions protocol, there exists a privacy-preserving dominant strategy equilibrium in which every party prefers to follow the protocol rather than to deviate.

Our protocol is implemented using open-source cryptographic constructs. Running our SPA protocol on commodity hardware with $15$ bidders, with bids of length $10$ bits, completes in $1.26$sec and has total communication of $0.77$MB whereas, under similar conditions, Atlas (semi-honest) protocol takes $40\%$ more time ($2.11$ sec) and $87\%$ more communication ($6.09$MB).