## In this issue

1. [2024/547] Efficient Permutation Correlations and Batched ...
2. [2024/866] Ripple: Accelerating Programmable Bootstraps for ...
3. [2024/870] Computationally Secure Aggregation and Private ...
4. [2024/874] Fake It till You Make It: Enhancing Security of ...
5. [2024/1654] Compressed $\Sigma$-protocol Theory from Sum-check
6. [2024/1666] Concretely Efficient Asynchronous MPC from ...
7. [2024/1667] Overlapped Bootstrapping for FHEW/TFHE and Its ...
8. [2024/1669] The Role of Message-Bound Signatures for the Beyond ...
9. [2024/1670] Statistical Layered MPC
10. [2024/1671] Multi-party Setup Ceremony for Generating Tokamak ...
11. [2024/1672] New Strategies for Bootstrapping Large-Error ...
12. [2024/1673] Proteus: A Fully Homomorphic Authenticated ...
13. [2024/1674] Provable Security Analysis of Butterfly Key ...
14. [2024/1675] Testing Robustness of Homomorphically Encrypted ...
15. [2024/1676] The Sting Framework: Proving the Existence of ...
16. [2024/1677] Batch Range Proof: How to Make Threshold ECDSA More ...
17. [2024/1678] Commutative Cryptanalysis as a Generalization of ...
18. [2024/1679] Information Set Decoding for Ring-Linear Code
19. [2024/1680] Sunfish: Reading Ledgers with Sparse Nodes
20. [2024/1681] Another L makes it better? Lagrange meets LLL and ...
21. [2024/1682] Toward Optimal-Complexity Hash-Based Asynchronous ...
22. [2024/1683] Unclonable Functional Encryption
23. [2024/1684] Blind zkSNARKs for Private Proof Delegation and ...
24. [2024/1685] GAPP: Generic Aggregation of Polynomial Protocols
25. [2024/1686] Circular Insecure Encryption: from Long Cycles to ...
26. [2024/1687] Revocable Encryption, Programs, and More: The Case ...
27. [2024/1688] Revisiting Products of the Form $X$ Times a ...
28. [2024/1689] Homomorphic Encryption with Authority
29. [2024/1690] A Note on Security Definitions for Secret Sharing ...
30. [2024/1691] A Framework for Group Action-Based Multi-Signatures ...
31. [2024/1692] On the practicality of quantum sieving algorithms ...
32. [2024/1693] A notion on S-boxes for a partial resistance to ...
33. [2024/1694] Full Key-Recovery Cubic-Time Template Attack on ...
34. [2024/1695] Discrete Gaussians Modulo Sub-Lattices: New ...
35. [2024/1696] Revisiting the Robustness of (R/M)LWR under ...
36. [2024/1697] On pairing-friendly 2-cycles and SNARK-friendly ...
37. [2024/1698] Computational Analysis of Plausibly Post-Quantum- ...
38. [2024/1699] HADES: Range-Filtered Private Aggregation on Public ...
39. [2024/1700] Does quantum lattice sieving require quantum RAM?
40. [2024/1701] Secure Computation with Parallel Calls to 2-ary ...
41. [2024/1702] Secure and efficient transciphering for FHE-based MPC
42. [2024/1703] Free-XOR Gate Bootstrapping
43. [2024/1704] From One-Time to Two-Round Reusable Multi- ...
44. [2024/1705] Dumbo-MPC: Efficient Fully Asynchronous MPC with ...
45. [2024/1706] State of the art of HFE variants Is it possible to ...
46. [2024/1707] CountCrypt: Quantum Cryptography between QCMA and PP
47. [2024/1708] Subliminal Encrypted Multi-Maps and Black-Box ...
48. [2024/1709] Do Not Disturb a Sleeping Falcon: Floating-Point ...
49. [2024/1710] $\widetilde{\mbox{O}}$ptimal Adaptively Secure ...
50. [2024/1711] Good things come to those who wait: Dishonest- ...
51. [2024/1712] Low-Communication Updatable PSI from Asymmetric PSI ...
52. [2024/1713] Universally Composable Non-Interactive Zero- ...
53. [2024/1714] Theoretical Approaches to Solving the Shortest ...
54. [2024/1715] OT-PCA: New Key-Recovery Plaintext-Checking Oracle ...
55. [2024/1716] Rate-1 Statistical Non-Interactive Zero-Knowledge
56. [2024/1717] Practical Asynchronous MPC from Lightweight ...

## 2024/547

* Title: Efficient Permutation Correlations and Batched Random Access for Two-Party Computation
* Authors: Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal, Harshal Shah * [Permalink](https://eprint.iacr.org/2024/547)
* [Download](https://eprint.iacr.org/2024/547.pdf)

### Abstract

In this work we formalize the notion of a two-party permutation correlation $(A, B), (C, \pi)$ s.t. $\pi(A)=B+C$ for a random permutation $\pi$ of $n$ elements and vectors $A,B,C\in \mathbb{F}^n$. This correlation can be viewed as an abstraction and
generalization of the Chase et al. (Asiacrypt 2020) share translation protocol. We give a systematization of knowledge for how such a permutation correlation can be derandomized to allow the parties to perform a wide range of oblivious permutations of
secret-shared data. This systematization immediately enables the translation of various popular honest-majority protocols to be efficiently instantiated in the two-party setting, e.g. collaborative filtering, sorting, database joins, graph algorithms,
and many more.

We give two novel protocols for efficiently generating a random permutation correlation. The first uses MPC-friendly PRFs to generate a correlation of $n$ elements, each of size $\ell=\log|\mathbb{F}|$ bits, with $O(n\ell)$ bit-OTs, time, communication,
and only three rounds. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for $n=2^{20},\ell=128$ requires just 7 seconds & $\sim2\ell n$ bits of communication, a
respective 40 & $1.1\times$ improvement on the LWE solution of Juvekar at al. (CCS 2018). The second protocol is based on pseudo-random correlation generators and achieves an overhead that is sublinear in the string length $\ell$, i.e. the communication
and number of OTs is $O(n\log \ell)$. The overhead of the latter protocol has larger hidden constants, and therefore is more efficient only when long strings are permuted, e.g. in graph algorithms.

Finally, we present a suite of highly efficient protocols based on permutations for performing various batched random access operations. These include the ability to extract a hidden subset of a secret-shared list. More generally, we give ORAM-like
protocols for obliviously reading and writing from a list in a batched manner. We argue that this suite of batched random access protocols should be a first class primitive in the MPC practitioner's toolbox.



## 2024/866

* Title: Ripple: Accelerating Programmable Bootstraps for FHE with Wavelet Approximations
* Authors: Charles Gouert, Mehmet Ugurbil, Dimitris Mouris, Miguel de Vega, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/866)
* [Download](https://eprint.iacr.org/2024/866.pdf)

### Abstract

Homomorphic encryption can address key privacy challenges in cloud-based outsourcing by enabling potentially untrusted servers to perform meaningful computation directly on encrypted data. While most homomorphic encryption schemes offer addition and
multiplication over ciphertexts natively, any non-linear functions must be implemented as costly polynomial approximations due to this restricted computational model. Nevertheless, the CGGI cryptosystem is capable of performing arbitrary univariate
functions over ciphertexts in the form of lookup tables through the use of programmable bootstrapping. While promising, this procedure can quickly become costly when high degrees of precision are required. To address this challenge, we propose Ripple: a
framework that introduces different approximation methodologies based on discrete wavelet transforms (DWT) to decrease the number of entries in homomorphic lookup tables while maintaining high accuracy. Our empirical evaluations demonstrate significant
error reduction compared to plain quantization methods across multiple non-linear functions. Notably, Ripple improves runtime performance for several realistic benchmarks, such as logistic regression and cross-correlation, among others.



## 2024/870

* Title: Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model
* Authors: Adrià Gascón, Yuval Ishai, Mahimna Kelkar, Baiyu Li, Yiping Ma, Mariana Raykova
* [Permalink](https://eprint.iacr.org/2024/870)
* [Download](https://eprint.iacr.org/2024/870.pdf)

### Abstract

The shuffle model has recently emerged as a popular setting for differential privacy, where clients can communicate with a central server using anonymous channels or an intermediate message shuffler. This model was also explored in the context of
cryptographic tasks such as secure aggregation and private information retrieval (PIR). However, this study was almost entirely restricted to the stringent notion of information-theoretic security.

In this work, we study computationally secure aggregation protocols and PIR in the shuffle model. Our starting point is the insight that the previous technique of shuffling additive shares can be improved in the computational setting. We show that this
indeed holds under the standard learning parity with noise (LPN) assumption, but even better efficiency follows from plausible conjectures about the multi-disjoint syndrome decoding (MDSD) problem that we introduce and study in this work.

We leverage the above towards improving the efficiency of secure aggregation and PIR in the shuffle model. For secure aggregation of long vectors, our protocols require $9\times$-$25\times$ less communication than the previous information-theoretic
solutions. Our PIR protocols enjoy the simplicity and concrete efficiency benefits of multi-server PIR while only requiring a single server to store the database. Under the MDSD assumption, they improve over recent single-server PIR constructions by up
to two orders of magnitude.



## 2024/874

* Title: Fake It till You Make It: Enhancing Security of Bluetooth Secure Connections via Deferrable Authentication
* Authors: Marc Fischlin, Olga Sanina
* [Permalink](https://eprint.iacr.org/2024/874)
* [Download](https://eprint.iacr.org/2024/874.pdf)

### Abstract

The Bluetooth protocol for wireless connection between devices comes with several security measures to protect confidentiality and integrity of data. At the heart of these security protocols lies the Secure Simple Pairing, wherewith the devices can
negotiate a shared key before communicating sensitive data. Despite the good intentions, the Bluetooth security protocol has repeatedly been shown to be vulnerable, especially with regard to active attacks on the Secure Simple Pairing.

We propose here a mechanism to limit active attacks on the Secure Connections protocol (the more secure version of the Secure Simple Pairing protocol), without infringing on the current Bluetooth protocol stack specification. The idea is to run an
authentication protocol, like a classical challenge-response step for certified keys, within the existing infrastructure, even at a later, more convenient point in time. We prove that not only does this authentication step ensure freshness of future
encryption keys, but an interesting feature is that it—a posteriori—also guarantees security of previously derived encryption keys. We next argue that this approach indeed prevents a large set of known attacks on the Bluetooth protocol.



## 2024/1654

* Title: Compressed $\Sigma$-protocol Theory from Sum-check
* Authors: Shang Gao, Chen Qian, Tianyu Zheng, Yu Guo, Bin Xiao
* [Permalink](https://eprint.iacr.org/2024/1654)
* [Download](https://eprint.iacr.org/2024/1654.pdf)

### Abstract

The compressed $\Sigma$-protocol theory [AC20, ACF21] presents a standard framework for constructing efficient $\Sigma$-protocols. This approach primarily consists of two phases: amortization to fold multiple instances satisfying a homomorphic relation
into one, and Bulletproofs compression [BBB+18] to reduce the communication overhead to a logarithmic scale when verifying the folded instance. For high-degree polynomial (non-homomorphic) relations, a circuit-based linearization technique is employed to
convert each instance into a linear relation, resulting in a protocol with at least linear complexity.

In this paper, we provide a direct method to extend the compressed $\Sigma$-protocol theory to polynomial relations. One major objective is to avoid the linear cost of linearization. To achieve this, we employ a sum-check during the amortization phase to
ensure a logarithmic communication cost. To the best of our knowledge, this is the first work to achieve a logarithmic amortization for polynomial relations. Nevertheless, without linearization, the amortized relation may not be linear, which hinders us
from using Bulletproofs compression. To overcome this problem, we employ another sum-check during the compression phase to effectively manage high-degree relations. This allows us to extend the compressed $\Sigma$-protocol framework to polynomial
relations. Furthermore, we introduce several variants of our techniques and adapt them for arithmetic circuit relations. We conclude by showcasing the practicality of our compressed $\Sigma$-protocol theory through applications such as binary proofs,
range proofs, and partial knowledge proofs. Our basic protocols are initially based on the Discrete Logarithm (DL) assumption. We have also extended them to incorporate the Strong-RSA assumption and the Generalized Discrete Logarithm Representation (GDLR)
assumption. Our work expands the scope of compressed $\Sigma$-protocol theory and provides a robust foundation for real-world cryptographic applications.



## 2024/1666

* Title: Concretely Efficient Asynchronous MPC from Lightweight Cryptography
* Authors: Akhil Bandarupalli, Xiaoyu Ji, Aniket Kate, Chen-Da Liu-Zhang, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/1666)
* [Download](https://eprint.iacr.org/2024/1666.pdf)

### Abstract

We consider the setting of asynchronous multi-party computation (AMPC) with optimal resilience $n=3t+1$ and linear communication complexity, and employ only ``lightweight'' cryptographic primitives, such as random oracle hash.

In this model, we introduce two concretely efficient AMPC protocols for a circuit with $|C|$ multiplication gates: a protocol achieving fairness with $\mathcal{O}(|C|\cdot n + n^3)$ field elements of communication, and a protocol achieving guaranteed
output delivery with $\mathcal{O}(|C|\cdot n + n^5)$ field elements.
These protocols significantly improve upon the best prior AMPC protocol in this regime communicating $\mathcal{O}(|C|\cdot n + n^{14})$ elements. To achieve this, we introduce novel variants of asynchronous complete secret sharing (ACSS) protocols with
linear communication in the number of sharings, providing different abort properties.



## 2024/1667

* Title: Overlapped Bootstrapping for FHEW/TFHE and Its Application to SHA3
* Authors: Deokhwa Hong, Youngjin Choi, Yongwoo Lee, Young-Sik Kim
* [Permalink](https://eprint.iacr.org/2024/1667)
* [Download](https://eprint.iacr.org/2024/1667.pdf)

### Abstract

Homomorphic Encryption (HE) enables operations on encrypted data without requiring decryption, thus allowing for secure handling of confidential data within smart contracts. Among the known HE schemes, FHEW and TFHE are particularly notable for use in
smart contracts due to their lightweight nature and support for arbitrary logical gates. In contrast, other HE schemes often require several gigabytes of keys and are limited to supporting only addition and multiplication. As a result, there has been
significant work implementing smart contract functionalities over HE, broadening the potential applications of blockchain technology. However, a significant drawback of the FHEW/TFHE schemes is the need for bootstrapping after the execution of each
binary gate. While bootstrapping reduces noise in the ciphertext, it also becomes a performance bottleneck due to its computational complexity.

In this work, we propose an efficient new bootstrapping method for FHEW/TFHE that takes advantage of the flexible scaling factors of encrypted data. The proposed method is particularly beneficial in circuits with consecutive XOR gates. Moreover, we
implement Keccak using FHEW/TFHE, as it is one of the most important functions in smart contracts. Our experimental results demonstrate that the proposed method reduces the runtime of Keccak over HE by 42%. Additionally, the proposed method does not
require additional keys or parameter sets from the key-generating party and can be adopted by the computing party without need for any extra information.



## 2024/1669

* Title: The Role of Message-Bound Signatures for the Beyond UnForgeability Features and Weak Keys
* Authors: Samed Düzlü, Patrick Struck
* [Permalink](https://eprint.iacr.org/2024/1669)
* [Download](https://eprint.iacr.org/2024/1669.pdf)

### Abstract

In the present work, we establish a new relationship among the Beyond UnForgeability Features (BUFF) introduced by Cremers et al. (SP’21). There, the BUFF notions have been shown to be independent of one another. On the other hand, the analysis by
Aulbach et al. (PQCrypto’24) reveals that one of the BUFF notions—message-bound signatures (MBS)—is achieved by most schemes. To achieve BUFF security, there is the generic BUFF transform that achieves all the beyond unforgeability features. The
BUFF transform works by signing a hash of the public key and the message (rather than just the message), and appending this hash value to the signature. The need for appending the hash comes from the intuitive notion of weak keys that verify all message-
signature pairs. We explain that MBS security effectively rules out the possibility of weak keys. This opens the possibility for a more efficient transform to achieve BUFF. We show that this transform, first introduced by Pornin and Stern (ACNS’05),
indeed suffices to achieve BUFF security, if the original signature schemes satisfies MBS. Only in the malicious setting of exclusive ownership, we present an attack on UOV, even after applying the PS-3 transform.



## 2024/1670

* Title: Statistical Layered MPC
* Authors: Giovanni Deligios, Anders Konring, Chen-Da Liu-Zhang, Varun Narayanan
* [Permalink](https://eprint.iacr.org/2024/1670)
* [Download](https://eprint.iacr.org/2024/1670.pdf)

### Abstract

The seminal work of Rabin and Ben-Or (STOC'89) showed that the problem of secure $n$-party computation can be solved for $t<n/2$ corruptions with guaranteed output delivery and statistical security. This holds in the traditional static model where the
set of parties is fixed throughout the entire protocol execution.

The need to better capture the dynamics of large scale and long-lived computations, where compromised parties may recover and the set of parties can change over time, has sparked renewed interest in the proactive security model by Ostrovsky and Yung (
PODC'91). This abstraction, where the adversary may periodically uncorrupt and corrupt a new set of parties, is taken even a step further in the more recent YOSO and Fluid MPC models (CRYPTO'21) which allow, in addition, disjoint sets of parties
participating in each round. Previous solutions with guaranteed output delivery and statistical security only tolerate $t<n/3$ corruptions, or assume a random corruption pattern plus non-standard communication models.
Matching the Rabin and Ben-Or bound in these settings remains an open problem.

In this work, we settle this question considering the unifying Layered MPC abstraction recently introduced by David et al. (CRYPTO'23). In this model, the interaction pattern is defined by a layered acyclic graph, where each party sends secret messages
and broadcast messages only to parties in the very next layer. We complete the feasibility landscape of layered MPC, by extending the Rabin and Ben-Or result to this setting. Our results imply maximally-proactive MPC with statistical security in the
honest-majority setting.



## 2024/1671

* Title: Multi-party Setup Ceremony for Generating Tokamak zk-SNARK Parameters * Authors: Muhammed Ali Bingol
* [Permalink](https://eprint.iacr.org/2024/1671)
* [Download](https://eprint.iacr.org/2024/1671.pdf)

### Abstract

This document provides a specification guide for the Multi-party Computation (MPC) setup ceremony for the Tokamak zk-SNARK scheme. It begins by revisiting the MMORPG protocol proposed in BGM17 for Groth16 setup generation, which leverages a random beacon
to ensure public randomness. Additionally, it explores the alternative design approach presented in the ``Snarky Ceremonies" paper KMSV21, which removes the need for a random beacon. The document includes a detailed pseudocode and workflow for each stage
of parameter generation in the Tokamak zk-SNARK protocol.

Tokamak zk-SNARK employs a universal setup through sub-circuits, which allows for CRS reuse across multiple circuits. This approach reduces the need for repeated trusted setups and emphasizes efficiency in verifier preprocessing. The document also
introduces pseudocodes for various types of parameter generation during the MPC setup. This includes the generation of parameters like Powers of $\tau$, circuit-specific parameters, and different types of mappings across both the random beacon and non-
random beacon based approaches. These pseudocodes ensure clarity in the protocol's step-by-step process, from the computation of shared parameters to verifying correctness.

Finally, the document presents a sketch security analysis of both protocols, relying on the Algebraic Group Model (AGM) and the Random Oracle Model (ROM) to prove knowledge soundness and security of the generated CRS. The analysis considers potential
attacks and demonstrates that, even without a random beacon, the setup remains secure under the assumptions of these models.



## 2024/1672

* Title: New Strategies for Bootstrapping Large-Error Ciphertext in Large-Precision FHEW/TFHE Cryptosystem
* Authors: Hongbo Li, Dengfa Liu, Guangsheng Ma
* [Permalink](https://eprint.iacr.org/2024/1672)
* [Download](https://eprint.iacr.org/2024/1672.pdf)

### Abstract

Bootstrapping is the core task in fully homomorphic encryption. It is designed to self-clean encrypted data to support unlimited level of homomorphic computing. FHEW/TFHE cryptosystem provides the fastest bootstrapping machinery in addition to the unique
homomorphic evaluation functionality. In 2021, the problem of large-precision bootstrapping was investigated in the literature, with fast algorithms proposed and implemented. A common strategy to all the algorithms is to decompose the plaintext
homomorphically into blocks from the tail up, at the same bootstrap the blocks sequentially.
This paper proposes two new strategies to improve the efficiency of large-precision plaintext bootstrapping. Both strategies are based on a new design of continuous nega-cyclic function with varying resolution, for making accurate computation with
blockwise approximate computing. To minimize the approximation error in each block, optimizations are proposed based on rigorous error estimation, and are illustrated by error bounds in power-of-two binomial representation.
The first strategy is to make homomorphic approximate decomposition of the input plaintext from the head on. Compared with the tail-up approach, the head-on approach reduces the number of blocks at most by half asympotitically, at the same time reducing
the final refreshed error by at most $1-1/\sqrt{2}\approx 29.3\%$.
The second strategy extends the head-on approach from large-precision plaintext bootstrapping to large error reduction. It can be used directly to the input ciphertext for the purpose of plaintext bootstrapping; it can also be used after plaintext
bootstrapping to further reduce the refreshed error.
Two algorithms based on the above two strategies are proposed, together with some variants combining the tail-up approach. The tail-up approach is completely re-developed for optimal blocksize control based on careful error analysis, and a corresponding
algorithm is proposed. All the algorithms are implemented on PALISADE, and experiments based on real data show that the by the new strategies, the speed of large-precision plaintext bootstrapping can be improved to as many as 7 times.



## 2024/1673

* Title: Proteus: A Fully Homomorphic Authenticated Transciphering Protocol
* Authors: Lars Wolfgang Folkerts, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1673)
* [Download](https://eprint.iacr.org/2024/1673.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a powerful technology that allows a cloud server to perform computations directly on ciphertexts. To overcome the overhead of sending and storing large FHE ciphertexts, the concept of FHE transciphering was
introduced, allowing symmetric key encrypted ciphertexts to be transformed into FHE ciphertexts by deploying symmetric key decryption homomorphically. However, existing FHE transciphering schemes remain unauthenticated and malleable, allowing attackers
to manipulate data and remain undetected. This work introduces Proteus, a new methodology for authenticated transciphering, which enables oblivious access control, preventing users from downloading unauthenticated or malicious data. Our protocol
implementation adopts ASCON, NIST's new standard for lightweight cryptography, to enable homomorphic hashing and authenticated transciphering. Our ASCON transcipher is paired with the TFHE encryption scheme, which is well suited to perform encrypted
rotation and bitwise operations. We evaluate our approach with a variety of real-life privacy-preserving applications, including URL phishing detection, private content moderation of hate speech, and biometric authentication.



## 2024/1674

* Title: Provable Security Analysis of Butterfly Key Mechanism Protocol in IEEE 1609.2.1 Standard
* Authors: Alexandra Boldyreva, Virendra Kumar, Jiahao Sun
* [Permalink](https://eprint.iacr.org/2024/1674)
* [Download](https://eprint.iacr.org/2024/1674.pdf)

### Abstract

The paper provides the first provable security analysis of the Butterfly Key Mechanism (BKM) protocol from IEEE 1609.2.1 standard. The BKM protocol specifies a novel approach for efficiently requesting multiple certificates for use in vehicle-to-
everything (V2X) communication. We define the main security goals of BKM, such as vehicle privacy and communication authenticity. We prove that the BKM protocol, with small modifications, meets those security goals. We also propose a way to
significantly improve the protocol's efficiency without sacrificing security.



## 2024/1675

* Title: Testing Robustness of Homomorphically Encrypted Split Model LLMs
* Authors: Lars Wolfgang Folkerts, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1675)
* [Download](https://eprint.iacr.org/2024/1675.pdf)

### Abstract

Large language models (LLMs) have recently transformed many industries, enhancing content generation, customer service agents, data analysis and even software generation. These applications are often hosted on remote servers to protect the neural-network
model IP; however, this raises concerns about the privacy of input queries. Fully Homomorphic Encryption (FHE), an encryption technique that allows for computations on private data, has been proposed as a solution to the challenge. Nevertheless, due to
the increased size of LLMs and the computational overheads of FHE, today's practical FHE LLMs are implemented using a split model approach. Here, a user sends their FHE encrypted data to the server to run an encrypted attention head layer; then the
server returns the result of the layer for the user to run the rest of the model locally. By employing this method, the server maintains part of their model IP, and the user still gets to perform private LLM inference. In this work, we evaluate the
neural-network model IP protections of single layer split model LLMs, and demonstrate a novel attack vector that makes it easy for a user to extract the neural network model IP from the server, bypassing the claimed protections for encrypted computation.
In our analysis, we demonstrate the feasibility of this attack, and discuss potential mitigations.



## 2024/1676

* Title: The Sting Framework: Proving the Existence of Superclass Adversaries
* Authors: Mahimna Kelkar, Yunqi Li, Nerla Jean-Louis, Carolina Ortega Pérez, Kushal Babel, Andrew Miller, Ari Juels
* [Permalink](https://eprint.iacr.org/2024/1676)
* [Download](https://eprint.iacr.org/2024/1676.pdf)

### Abstract

We introduce superclass accountability, a new notion of accountability for security protocols. Classical notions of accountability typically aim to identify specific adversarial players whose violation of adversarial assumptions has caused a security
failure. Superclass accountability describes a different goal: to prove the existence of adversaries capable of violating security assumptions.

We develop a protocol design approach for realizing superclass accountability called the sting framework (SF). Unlike classical accountability, SF can be used for a broad range of applications without making protocol modifications and even when security
failures aren’t attributable to particular players.

SF generates proofs of existence for superclass adversaries that are publicly verifiable, making SF a promising springboard for reporting by whistleblowers, high-trust bug-bounty programs, and so forth.

We describe how to use SF to prove the existence of adversaries capable of breaching the confidentiality of practical applications that include Tor, block-building infrastructure in web3, ad auctions, and private contact discovery---as well as the
integrity of fair-transaction-ordering systems. We report on two end-to-end SF systems we have constructed---for Tor and block-building---and on experiments with those systems.



## 2024/1677

* Title: Batch Range Proof: How to Make Threshold ECDSA More Efficient
* Authors: Guofeng Tang, Shuai Han, Li Lin, Changzheng Wei, Ying Yan
* [Permalink](https://eprint.iacr.org/2024/1677)
* [Download](https://eprint.iacr.org/2024/1677.pdf)

### Abstract

With the demand of cryptocurrencies, threshold ECDSA recently regained popularity. So far, several methods have been proposed to construct threshold ECDSA, including the usage of OT and homomorphic encryptions (HE). Due to the mismatch between the
plaintext space and the signature space, HE-based threshold ECDSA always requires zero-knowledge range proofs, such as Paillier and Joye-Libert (JL) encryptions. However, the overhead of range proofs constitutes a major portion of the total cost.

In this paper, we propose efficient batch range proofs to improve the efficiency of threshold ECDSA. At the heart of our efficiency improvement is a new technical tool called Multi-Dimension Forking Lemma, as a generalization of the well-known general
forking lemma [Bellare and Neven, CCS 2006]. Based on our new tool, we construct efficient batch range proofs for Paillier and JL encryptions, and use them to give batch multiplication-to-addition (MtA) protocols, which are crucial to most threshold
ECDSA. Our constructions improve the prior Paillier-based MtA by a factor of 2 and the prior JL-based MtA by a factor of 3, in both computation and bandwidth in an amortized way. Our batch MtA can be used to improve the efficiency of most Paillier and JL
based threshold ECDSA. As three typical examples, our benchmarking results show:
-- We improve the Paillier-based CGGMP20 [Canetti et al., CCS 2020] in bandwidth by a factor of 2.1 to 2.4, and in computation by a factor of 1.5 to 1.7.
-- By implementing threshold ECDSA with the batch JL MtA of XAL+23 [Xue et al., CCS 2023] and our batch JL MtA, respectively, our batch construction improves theirs in bandwidth by a factor of 2.0 to 2.29, and in computation by a factor of 1.88 to 2.09.

[continued in next message]

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