[digest] 2024 Week 42

## 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.
-- When replacing OT-based MtA in DKLs24 [Doerner et al., S$\&$P 2024] with our Paillier-based batch MtA, we improve the bandwidth efficiency by $7.8\times$ at the cost of $5.7\times$ slower computation.



## 2024/1678

* Title: Commutative Cryptanalysis as a Generalization of Differential Cryptanalysis
* Authors: Jules Baudrin, Christof Beierle, Patrick Felke, Gregor Leander, Patrick Neumann, Léo Perrin, Lukas Stennes
* [Permalink](https://eprint.iacr.org/2024/1678)
* [Download](https://eprint.iacr.org/2024/1678.pdf)

### Abstract

Recently, Baudrin et al. analyzed a special case of Wagner's commutative diagram cryptanalysis, referred to as commutative cryptanalysis. For a family  $(E_k)_k$ of permutations on a finite vector space $G$, commutative cryptanalysis exploits the existence of affine permutations $A,B \colon G \rightarrow G$, $I \notin \{A,B\}$ such that $E_k \circ A (x) = B \circ E_k(x)$ holds with high probability, taken over inputs $x$, for a significantly large set of weak keys $k$. Several attacks against symmetric cryptographic primitives can be formulated within the framework of commutative cryptanalysis, most importantly differential attacks, as well as rotational and rotational-differential attacks. Besides, the notion of $c$-differentials on S-boxes can be analyzed as a special case within this framework.
We discuss the relations between a general notion of commutative cryptanalysis, with $A$ and $B$ being arbitrary functions over a finite Abelian group, and differential cryptanalysis, both from the view of conducting an attack on a symmetric cryptographic primitive, as well as from the view of a theoretical study of cryptographic S-boxes.



## 2024/1679

* Title: Information Set Decoding for Ring-Linear Code
* Authors: Giulia Cavicchioni, Alessio Meneghetti, Giovanni Tognolini
* [Permalink](https://eprint.iacr.org/2024/1679)
* [Download](https://eprint.iacr.org/2024/1679.pdf)

### Abstract

Information set decoding (ISD) algorithms currently offer the most powerful tool to solve the two archetypal problems of coding theory, namely the Codeword Finding Problem and the Syndrome Decoding Problem. Traditionally, ISD have primarily been studied for linear codes over finite fields, equipped with the  Hamming metric.
    However, recently, other possibilities have also been explored. These algorithms have been adapted to different ambient spaces and metrics, such as  the rank metric or the Lee metric over $\mathbb Z_m$.
    In this paper, we show that it is possible to leverage the ring structure to construct more efficient decoding algorithms than those obtained by simply adapting ISD. In particular, we describe a framework that can be applied to any additive metric including Hamming and Lee, and that can be adapted to the case of the rank metric, providing algorithms to solve the two aforementioned problems, along with their average computational costs.



## 2024/1680

* Title: Sunfish: Reading Ledgers with Sparse Nodes
* Authors: Giulia Scaffino, Karl Wüst, Deepak Maram, Alberto Sonnino, Lefteris Kokoris-Kogias
* [Permalink](https://eprint.iacr.org/2024/1680)
* [Download](https://eprint.iacr.org/2024/1680.pdf)

### Abstract

The increased throughput offered by modern blockchains, such as Sui, Aptos, and Solana, enables processing thousands of transactions per second, but it also introduces higher costs for decentralized application (dApp) developers who need to track and verify changes in the state of their application. This is true because dApp developers run full nodes, which download and re-execute every transaction to track the global state of the chain. However, this becomes prohibitively expensive for high-throughput chains due to high bandwidth, computational, and storage requirements. A common alternative is to use light nodes. However, light nodes only verify the inclusion of a set of transactions and have no guarantees that the set is complete, i.e., that includes all relevant transactions. Under a dishonest majority, light nodes can also be tricked into accepting invalid transactions.

To bridge the gap between full and light nodes, we propose and formalize a new type of blockchain node: the sparse node. A sparse node tracks only a subset of the blockchain’s state: it verifies that the received set of transactions touching the substate is complete, and re-executes those transactions to assess their validity. A sparse node retains important security properties even under adversarial majorities, and requires an amount of resources proportional to the number of transactions in the substate and to the size of the substate itself.

We further present Sunfish, an instantiation of a sparse node protocol. Our analysis and evaluation show that Sunfish reduces the bandwidth consumption of real blockchain applications by several orders of magnitude when compared to a full node.



## 2024/1681

* Title: Another L makes it better? Lagrange meets LLL and may improve BKZ pre-processing
* Authors: Sebastien Balny, Claire Delaplace, Gilles Dequen
* [Permalink](https://eprint.iacr.org/2024/1681)
* [Download](https://eprint.iacr.org/2024/1681.pdf)

### Abstract

We present a new variant of the LLL lattice reduction algorithm, inspired by Lagrange notion of pair-wise reduction, called L4. Similar to LLL, our algorithm is polynomial in the dimension of the input lattice, as well as in $\log M$, where $M$ is an upper-bound on the norm of the longest vector of the input basis.
We experimentally compared the norm of the first basis vector obtained with LLL and L4 up to dimension 200. On average we obtain vectors that are up to $16\%$ shorter. We also used our algorithm as a pre-processing step for the BKZ lattice reduction algorithm with blocksize 24. In practice, up to dimension 140, this allows us to reduce the norm of the shortest basis vector on average by $3\%$, while the runtime does not
significantly increases. In $10\%$ of our tests, the whole process was even faster.



## 2024/1682

* Title: Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience
* Authors: Jovan Komatovic, Joachim Neu, Tim Roughgarden
* [Permalink](https://eprint.iacr.org/2024/1682)
* [Download](https://eprint.iacr.org/2024/1682.pdf)

### Abstract

Multi-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, enables $n$ processes to agree on a valid $\ell$-bit value, despite $t$ faulty processes behaving arbitrarily. Among hash-based protocols for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol
has optimal $O(1)$ time complexity and near-optimal $O(n \ell + n^2 \kappa \log n)$ bit complexity, but tolerates only $t < n/5$ faults. We present REDUCER, an MVBA protocol that matches HMVBA's time and bit complexity and improves resilience to $t < n/4$. Like HMVBA, REDUCER relies solely on collision-resistant hash functions. Toward optimal one-third resilience, we also propose REDUCER++, an MVBA protocol
with further improved $t < (1/3 - \epsilon)n$ resilience, for any fixed $\epsilon > 0$, assuming hash functions modeled as random oracles. Time and bit complexity of REDUCER++ remain constant and quasi-quadratic, respectively, with constants depending on $\epsilon$.



## 2024/1683

* Title: Unclonable Functional Encryption
* Authors: Arthur Mehta, Anne Müller
* [Permalink](https://eprint.iacr.org/2024/1683)
* [Download](https://eprint.iacr.org/2024/1683.pdf)

### Abstract

In a functional encryption (FE) scheme, a user that holds a ciphertext and a function-key can learn the result of applying the function to the plaintext message. Security requires that the user does not learn anything beyond the function evaluation. On the other hand, unclonable encryption (UE) is a uniquely quantum primitive, which ensures that an adversary cannot duplicate a ciphertext to decrypt the same message multiple times. In this work we introduce unclonable quantum functional
encryption (UFE), which both extends the notion of FE to the quantum setting and also possesses the unclonable security of UE.
We give a construction for UFE that supports arbitrary quantum messages and polynomialy-sized circuits, and achieves unclonable-indistinguishable security for dependently sampled function keys. In particular, our UFE guarantees that two parties cannot simultaneously recover the correct function outputs using two independently sampled function keys. Our construction combines quantum garbled circuits [BY22], and quantum-key unclonable encryption [AKY24], and leverages techniques from the plaintext expansion arguments in [Hir+23]. As an application we give the first construction for public-key UE with variable decryption keys.
Lastly, we establish a connection between quantum indistinguishability obfuscation (qiO) and quantum functional encryption (QFE); Showing that any multi-input indistinguishability-secure quantum functional encryption scheme unconditionally implies the existence of qiO.



## 2024/1684

* Title: Blind zkSNARKs for Private Proof Delegation and Verifiable Computation over Encrypted Data
* Authors: Mariana Gama, Emad Heydari Beni, Jiayi Kang, Jannik Spiessens, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2024/1684)
* [Download](https://eprint.iacr.org/2024/1684.pdf)

### Abstract

In this paper, we show for the first time it is practical to privately delegate proof generation of zkSNARKs proving up to $2^{20}$ R1CS constraints to a single server. We achieve this by homomorphically computing zkSNARK proof generation, an approach we call blind zkSNARKs. We formalize the concept of blind proofs, analyze their cryptographic properties and show that the resulting blind zkSNARKs remain sound when compiled using BCS compilation. Garg et al. gave a similar framework at CRYPTO 2024,  but no practical instantiation for proving non-trivial computations was known. By delegating proof generation,  we are able to reduce client computation time from 10 minutes to mere seconds, while server computation time remains limited to 20 minutes. We also propose a practical construction for vCOED supporting constraint sizes four orders of magnitude larger than the current state-of-the-art verifiable FHE-based approaches. These results are achieved by optimizing Fractal for the GBFV homomorphic encryption scheme, e.g. by designing specialized homomorphic circuits with two dimensional NTTs. Furthermore, we make the proofs publicly-verifiable by appending a zero-knowledge Proof of Decryption (PoD). We propose a new construction for PoDs, optimized for low proof generation time, exploiting modulus and ring switching in GBFV; these techniques might be of independent interest. Finally, we implement the latter protocol in C and report on execution time and proof sizes.



## 2024/1685

* Title: GAPP: Generic Aggregation of Polynomial Protocols
* Authors: Chaya Ganesh, Sikhar Patranabis, Shubh Prakash, Nitin Singh
* [Permalink](https://eprint.iacr.org/2024/1685)
* [Download](https://eprint.iacr.org/2024/1685.pdf)

### Abstract

We propose a generic framework called GAPP for aggregation of polynomial protocols. This allows proving $n$ instances of a polynomial protocol using a single aggregate proof that has $O(\log n)$ size, and can be verified using $O(\log^2 n)$ operations. The satisfiability of several univariate polynomial identities over a domain is reduced to the satisfiability of a single bivariate polynomial identity over a related domain, where the bivariate polynomials interpolate a batch of univariate polynomials over the domain.  We construct an information-theoretic protocol for proving the satisfiability of the bivariate polynomial identity, which is then compiled using any bivariate polynomial commitment scheme (PCS) to yield an argument of knowledge for the aggregation relation. GAPP can be applied to several popular SNARKs over bilinear groups that are modeled as polynomial protocols in a black-box way.

We present a new bivariate polynomial commitment scheme, bPCLB, with succinct verification that yields an efficient instantiation of GAPP. In addition, the prover only performs sublinear cryptographic operations in the evaluation proof. Towards constructing bPCLB, we show a new folding technique that we call Lagrangian folding. The bivariate PCS bPCLB and the Lagrangian folding scheme are of independent interest. We implement bPCLB and experimentally validate the practical efficiency of our GAPP instantiation. For the popular PLONK proof system, we achieve $25$-$30\%$ faster proof generation than the naive baseline of generating $n$ separate PLONK proofs. Compared to all existing aggregation schemes that incur additional prover overheads on top of the baseline, we achieve significantly more efficient proving, while retaining succinct verification.

We demonstrate the versatility of our GAPP framework by outlining applications of practical interest: tuple lookups that significantly outperform existing lookup arguments in terms of prover overheads; and proofs for non-uniform computation with a la carte prover cost.



## 2024/1686

* Title: Circular Insecure Encryption: from Long Cycles to Short Cycles
* Authors: Zehou Wu
* [Permalink](https://eprint.iacr.org/2024/1686)
* [Download](https://eprint.iacr.org/2024/1686.pdf)

### Abstract

We prove that the existence of a CPA-secure encryption scheme that is insecure in the presence of key cycles of length $n$ implies the existence of such a scheme for key cycles of any length less than $n$. Equivalently, if every encryption scheme in a class is $n$-circular secure and this class is closed under our construction, then every encryption scheme in this class is $n'$-circular secure for $n' > n$.



## 2024/1687

* Title: Revocable Encryption, Programs, and More: The Case of Multi-Copy Security
* Authors: Prabhanjan Ananth, Saachi Mutreja, Alexander Poremba
* [Permalink](https://eprint.iacr.org/2024/1687)
* [Download](https://eprint.iacr.org/2024/1687.pdf)

### Abstract

Fundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led to the emerging field of revocable cryptography. Roughly speaking, in a revocable cryptographic primitive, a cryptographic object (such as a ciphertext or program) is represented as a quantum state in such a way that surrendering it effectively translates into losing the capability to use this cryptographic object. All of the revocable cryptographic systems studied so far have a major drawback: the recipient only receives one copy of the quantum state. Worse yet, the schemes become completely insecure if the recipient receives many identical copies of the same quantum state---a property that is clearly much more desirable in practice.

While multi-copy security has been extensively studied for a number of other quantum cryptographic primitives, it has so far received only little treatment in context of unclonable primitives. Our work, for the first time, shows the feasibility of revocable primitives, such as revocable encryption and revocable programs, which satisfy multi-copy security in oracle models. This suggest that the stronger notion of multi-copy security is within reach in unclonable cryptography more generally, and therefore could lead to a new research
direction in the field.



## 2024/1688

* Title: Revisiting Products of the Form $X$ Times a Linearized Polynomial $L(X)$
* Authors: Christof Beierle
* [Permalink](https://eprint.iacr.org/2024/1688)
* [Download](https://eprint.iacr.org/2024/1688.pdf)

### Abstract

For a $q$-polynomial $L$ over a finite field $\mathbb{F}_{q^n}$, we characterize the differential spectrum of the function $f_L\colon \mathbb{F}_{q^n} \rightarrow \mathbb{F}_{q^n}, x \mapsto x \cdot L(x)$ and show that, for $n \leq 5$, it is completely determined by the image of the rational function $r_L \colon \mathbb{F}_{q^n}^* \rightarrow \mathbb{F}_{q^n}, x \mapsto L(x)/x$. This result follows from the classification of the pairs $(L,M)$ of $q$-polynomials in $\mathbb{F}_{q^n}[X]$, $n \leq 5$, for which $r_L$ and $r_M$ have the same image, obtained in [B. Csajbok, G. Marino, and O. Polverino. A Carlitz type result for linearized
polynomials. Ars Math. Contemp., 16(2):585–608, 2019]. For the  case of $n>5$, we pose an open question on the dimensions of the kernels of $x \mapsto L(x) - ax$ for $a \in \mathbb{F}_{q^n}$.

We further present a link between functions $f_L$ of differential uniformity bounded above by $q$ and scattered $q$-polynomials and show that, for odd values of $q$, we can construct CCZ-inequivalent functions $f_M$ with bounded differential uniformity from a given function $f_L$ fulfilling certain properties.



## 2024/1689

* Title: Homomorphic Encryption with Authority
* Authors: Joohee Lee, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2024/1689)
* [Download](https://eprint.iacr.org/2024/1689.pdf)

### Abstract

Fully homomorphic encryption enables computations over encrypted data, which allows privacy-preserving services to be held between a server and a client. However, real-world applications demand practical considerations, especially concerning public safety and legal investigations. Existing FHE schemes focus solely on privacy, neglecting the societal risks posed by criminal activities utilizing privacy-preserving services. This paper introduces Homomorphic Encryption with Authority (HEwA), a novel framework that balances data privacy with public safety by incorporating an "authority" party. The proposed HEwA system operates in two phases: a normal phase, where client data privacy is protected, and an investigative phase, where the authority referring to a legally authorized entity such as government agencies exerts the right to recover suspicious client’s data. We formalize the security model for HEwA, ensuring that client privacy is protected during the normal phase while enabling authorities to recover encrypted data in the investigative phase. As a concrete example, we design an efficient HEwA system solely based on the CKKS homomorphic encryption scheme, which supports approximate computations over real-number data, making it highly suitable for fruitful applications in AI such as secure genomic analysis. We further provide rigorous security proofs. This new approach addresses the tension between privacy and public safety in cloud services, paving the way for responsible use of homomorphic encryption in practice.



## 2024/1690

* Title: A Note on Security Definitions for Secret Sharing with Certified Deletion
* Authors: Dominique Bazin, Ryo Nishimaki
* [Permalink](https://eprint.iacr.org/2024/1690)
* [Download](https://eprint.iacr.org/2024/1690.pdf)

### Abstract

Bartusek and Raizes (CRYPTO 2024) proposed two security definitions for secret sharing, no-signaling certified deletion and adaptive certified deletion. We prove that adaptive certified deletion does not imply no-signaling certified deletion.



## 2024/1691

* Title: A Framework for Group Action-Based Multi-Signatures and Applications to LESS, MEDS, and ALTEQ
* Authors: Giuseppe D'Alconzo, Andrea Flamini, Alessio Meneghetti, Edoardo Signorini
* [Permalink](https://eprint.iacr.org/2024/1691)
* [Download](https://eprint.iacr.org/2024/1691.pdf)

### Abstract

A multi-signature scheme allows a list of signers to sign a common message. They are widely used in scenarios where the same message must be signed and transmitted by $N$ users, and, instead of concatenating $N$ individual signatures, employing a multi-signature can reduce the data to be sent.
In recent years there have been numerous practical proposals in the discrete logarithm setting, such as MuSig2 (CRYPTO'21) for the Schnorr signature. Recently, these attempts have been extended to post-quantum assumptions, with lattice-based proposals such as MuSig-L (CRYPTO'22).
Given the growth of group action-based signatures, a natural question is whether a multi-signature can be built on the same models. In this work, we present the first construction of such a primitive relying on group action assumptions. We obtain a 3-round scheme achieving concurrent security in the ROM.
Moreover, we instantiate it using the three candidates to the additional post-quantum NIST's call, namely LESS, MEDS and ALTEQ, obtaining a good compression rate for different parameters sets.



## 2024/1692

* Title: On the practicality of quantum sieving algorithms for the shortest vector problem
* Authors: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia
* [Permalink](https://eprint.iacr.org/2024/1692)
* [Download](https://eprint.iacr.org/2024/1692.pdf)

### Abstract

One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of lattice problems like the shortest vector problem (SVP), which asks to find the shortest non-zero vector in an integer lattice. Asymptotic quantum speedups for solving SVP are known and rely on Grover's search. However, to assess the security of lattice-based cryptography against these Grover-like quantum speedups, it is necessary to carry out a precise resource estimation beyond asymptotic scalings. In this work, we perform a careful analysis on the resources required to implement several sieving algorithms aided by Grover's search for dimensions of cryptographic interests. For such, we take into account fixed-point quantum arithmetic operations, non-asymptotic Grover's search, the cost of using quantum random access memory (QRAM), different physical architectures, and quantum error correction. We find that even under very optimistic assumptions like circuit-level noise of $10^{-5}$, code cycles of 100 ns, reaction time of 1 $\mu$s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require $\approx 10^{13}$ physical qubits and $\approx 10^{31}$ years to solve SVP on a lattice of dimension 400, which is roughly the dimension for minimally secure post-quantum cryptographic standards currently being proposed by NIST. We estimate that a 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time to solve the same problem. We conclude that there is currently little to no quantum speedup in the dimensions of cryptographic interest and the possibility of realising a considerable quantum speedup using quantum sieving algorithms would require significant breakthroughs in theoretical protocols and hardware development.



## 2024/1693

* Title: A notion on S-boxes for a partial resistance to some integral attacks
* Authors: Claude Carlet
* [Permalink](https://eprint.iacr.org/2024/1693)
* [Download](https://eprint.iacr.org/2024/1693.pdf)

### Abstract

In two recent papers, we introduced and studied the notion of $k$th-order sum-freedom of a vectorial function $F:\mathbb F_2^n\to \mathbb F_2^m$. This notion generalizes that of almost perfect nonlinearity (which corresponds to $k=2$) and has some relation with the resistance to integral attacks of those block ciphers using $F$ as a substitution box (S-box), by preventing the propagation of the division property of $k$-dimensional affine spaces. In the present paper, we show that this notion, which is rarely satisfied by vectorial functions, can be weakened while retaining the property that the S-boxes do not propagate the division property of $k$-dimensional affine spaces. This leads us to the property that we name $k$th-order $t$-degree-sum-freedom, whose strength decreases when $t$ increases, and which coincides with $k$th-order sum-freedom when $t=1$. The condition for $k$th-order $t$-degree-sum-freedom is that, for every $k$-dimensional affine space $A$, there exists a non-negative integer $j$ of 2-weight at most $t$ such that $\sum_{x\in A}(F(x))^j\neq 0$. We show, for a general $k$th-order $t$-degree-sum-free function $F$, that $t$ can always be taken smaller than or equal to $\min(k,m)$ under some reasonable condition on $F$, and that it is larger than or equal to $\frac k{\deg(F)}$, where $\deg(F)$ is the algebraic degree of $F$. We study examples for $k=2$ (case in which $t=1$ corresponds to APNness) showing that finding $j$ of 2-weight 2 can be challenging, and we begin the study of power functions, and in particular, of the multiplicative inverse function (used as S-box in the AES), for which we extend to $k$th-order $t$-degree-sum-freedom the result that it is $k$th-order sum-free if and only if it is $(n-k)$th-order sum-free. We begin the study of the cases of $k\in \{2,3,n-3,n-2,n-1,n\}$.



## 2024/1694

* Title: Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation
* Authors: Vlad-Florin Drăgoi, Brice Colombier, Nicolas Vallet, Pierre-Louis Cayrel, Vincent Grosso
* [Permalink](https://eprint.iacr.org/2024/1694)
* [Download](https://eprint.iacr.org/2024/1694.pdf)

### Abstract

Classic McEliece is one of the three code-based candidates in the fourth round of the NIST post-quantum cryptography standardization process in the Key Encapsulation Mechanism category. As such, its decapsulation algorithm is used to recover the session key associated with a ciphertext using the private key.. In this article, we propose a new side-channel attack on the syndrome computation in the decapsulation algorithm that recovers the private key, which consists of the private Goppa polynomial $g$ and the permuted support $\mathcal{L}$. The attack relies on both practical aspects and theoretical contributions, namely that the side-channel distinguisher can accurately discriminate elements of the permuted support $\mathcal{L}$, while relying only on a standard noisy Hamming weight leakage assumption and that there exists a cubic-time algorithm that uses this information to recover the private Goppa polynomial $g$. Compared with previous work targeting the Classic McEliece private key, this drastically improves both on the assumptions made in the attacker model and on the overall efficiency of the key-recovery algorithm. We have carried out the attack in practice on a microcontroller target running the reference implementation of Classic McEliece, and make the full attack source code available.



## 2024/1695

* Title: Discrete Gaussians Modulo Sub-Lattices: New Leftover Hash Lemmas for Discrete Gaussians
* Authors: Haoxiang Jin, Feng-Hao Liu, Zhedong Wang, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/1695)
* [Download](https://eprint.iacr.org/2024/1695.pdf)

### Abstract

The Leftover Hash Lemma (LHL) is a powerful tool for extracting randomness from an entropic distribution, with numerous applications in cryptography. LHLs for discrete Gaussians have been explored in both integer settings by Gentry et al. (GPV, STOC'08) and algebraic ring settings by Lyubashevsky et al. (LPR, Eurocrypt'13). However, the existing LHLs for discrete Gaussians have two main limitations: they require the Gaussian parameter to be larger than certain smoothing parameters, and they cannot handle cases where fixed and arbitrary information is leaked.

In this work, we present new LHLs for discrete Gaussians in both integer and ring settings. Our results show that the Gaussian parameter can be improved by a factor of  $\omega(\sqrt{\log\lambda})$ and $O(\sqrt{N})$ compared to the regularity lemmas of GPV and LPR, respectively, under similar parameter choices such as the dimension and ring. Furthermore, our new LHLs can be applied to leaked discrete Gaussians, and the result can be used to establish asymptotic hardness of the extended MLWE assumptions, addressing an open question in recent works by Lyubashevsky et al. (LNP, Crypto'22). Our central techniques involve new fine-grained analyses of the min-entropy in discrete Gaussians modulo sublattices and should be of interest.



## 2024/1696

* Title: Revisiting the Robustness of (R/M)LWR under Polynomial Moduli with Applications to Lattice-Based Compact SO-CCA Security
* Authors: Haoxiang Jin, Feng-Hao Liu, Zhedong Wang, Yang Yu, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/1696)
* [Download](https://eprint.iacr.org/2024/1696.pdf)

### Abstract

This work conducts a comprehensive investigation on determining the entropic hardness of (R/M)LWR under polynomial modulus. Particularly, we establish the hardness of (M)LWR for general entropic secret distributions from (Module) LWE assumptions based on a new conceptually simple framework called rounding lossiness. By combining this hardness result and a trapdoor inversion algorithm with asymptotically the most compact parameters, we obtain a compact lossy trapdoor function (LTF) with improved efficiency. Extending our LTF with other techniques, we can derive a compact all-but-many LTF and PKE scheme against selective opening and chosen ciphertext attacks, solely based on (Module) LWE assumptions within a polynomial modulus. Additionally, we show a search-to-decision reduction for RLWR with Gaussian secrets from a new R\'enyi Divergence-based analysis.



## 2024/1697

* Title: On pairing-friendly 2-cycles and SNARK-friendly 2-chains of elliptic curves containing a curve from a prime-order family
* Authors: Tomáš Novotný
* [Permalink](https://eprint.iacr.org/2024/1697)
* [Download](https://eprint.iacr.org/2024/1697.pdf)

### Abstract

Cryptographic protocols such as zkSNARKs use 2-cycles of elliptic curves for efficiency, often relying on pairing computations. However, 2-cycles of pairing-friendly curves are hard to find, and the only known cases consist of an MNT4 and an MNT6 curve. In this work, we prove that a 2-cycle containing an MNT3 curve cannot be pairing-friendly. For other curve families, we have a similar result for cryptographically attractive field sizes. Thus we cannot hope to find new pairing-friendly 2-cycles using the current methods.

Furthermore, we show that there are no SNARK-friendly 2-chains of elliptic curves from combinations of MNT, Freeman and BN curves of reasonable size, except for the (MNT4, MNT6) chains.



## 2024/1698

* Title: Computational Analysis of Plausibly Post-Quantum-Secure Recursive Arguments of Knowledge
* Authors: Dustin Ray
* [Permalink](https://eprint.iacr.org/2024/1698)
* [Download](https://eprint.iacr.org/2024/1698.pdf)

### Abstract

With the recent standardization of post-quantum cryptographic algorithms, research efforts have largely remained centered on public key exchange and encryption schemes. Argument systems, which allow a party to efficiently argue the correctness of a computation, have received comparatively little attention regarding their quantum-resilient design. These computational integrity frameworks often rely on cryptographic assumptions, such as pairings or group operations, which are vulnerable to quantum attacks. In this work, we present a fully implemented post-quantum secure argument system that compresses unbounded computation into a constant-sized space. We present a fully implemented prover which can argue the truth of any size computation, and verifier which can verify correctness in constant time. This work shows an extension of utility for computational integrity statements into the quantum domain. We provide real-world performance metrics demonstrating that post-quantum secure argument systems not only exist but can outperform classical systems in both efficiency and scalability, making such systems an attractive choice for practical deployment.



## 2024/1699

* Title: HADES: Range-Filtered Private Aggregation on Public Data
* Authors: Xiaoyuan Liu, Ni Trieu, Trinabh Gupta, Ishtiyaque Ahmad, Dawn Song
* [Permalink](https://eprint.iacr.org/2024/1699)
* [Download](https://eprint.iacr.org/2024/1699.pdf)

### Abstract

In aggregation queries, predicate parameters often reveal user intent. Protecting these parameters is critical for user privacy, regardless of whether the database is public or private. While most existing works focus on private data settings, we address a public data setting where the server has access to the database. Current solutions for this setting either require additional setups (e.g., noncolluding servers, hardware enclaves) or are inefficient for practical workloads. Furthermore, they often do not support range predicates or boolean combinations commonly seen in real-world use cases.

To address these limitations, we built HADES, a fully homomorphic encryption (FHE) based private aggregation system for public data that supports point, range predicates, and boolean combinations. Our one-round HADES protocol efficiently generates predicate indicators by leveraging the plaintext form of public data records. It introduces a novel elementwise-mapping operation and an optimized reduction algorithm, achieving latency efficiency within a limited noise budget. Our highly scalable, multi-threaded implementation improves performance over previous one-round FHE solutions by 204x to 6574x on end-to-end TPC-H queries, reducing aggregation time on 1M records from 15 hours to 38 seconds



## 2024/1700

* Title: Does quantum lattice sieving require quantum RAM?
* Authors: Beomgeun Cho, Minki Hhan, Taehyun Kim, Jeonghoon Lee, Yixin Shen
* [Permalink](https://eprint.iacr.org/2024/1700)
* [Download](https://eprint.iacr.org/2024/1700.pdf)

### Abstract

In this paper, we study the requirement for quantum random access memory (QRAM) in quantum lattice sieving, a fundamental algorithm for lattice-based cryptanalysis.

First, we obtain a lower bound on the cost of quantum lattice sieving with a bounded size QRAM. We do so in a new query model encompassing a wide range of lattice sieving algorithms similar to those in the classical sieving lower bound by Kirshanova and Laarhoven [CRYPTO 21]. This implies that, under reasonable assumptions, quantum speedups in lattice sieving require the use of QRAM.. In particular, no quantum speedup is possible without QRAM.

Second, we investigate the trade-off between the size of QRAM and the quantum speedup. We obtain a new interpolation between classical and quantum lattice sieving. Moreover, we show that further improvements require a novel way to use the QRAM by proving the optimality of some subroutines. An important caveat is that this trade-off requires a strong assumption on the efficient replacement of QRAM data, indicating that even speedups with a small QRAM are already challenging.

Finally, we provide a circuit for quantum lattice sieving without using QRAM. Our circuit has a better depth complexity than the best classical algorithms but requires an exponential amount of qubits. To the best of our knowledge, this is the first quantum speedup for lattice sieving without QRAM in the standard quantum circuit model. We explain why this circuit does not contradict our lower bound, which considers the query complexity.



## 2024/1701

* Title: Secure Computation with Parallel Calls to 2-ary Functions
* Authors: Varun Narayanan, Shubham Vivek Pawar, Akshayaram Srinivasan
* [Permalink](https://eprint.iacr.org/2024/1701)
* [Download](https://eprint.iacr.org/2024/1701.pdf)

### Abstract

Reductions are the workhorses of cryptography. They allow constructions of complex cryptographic primitives from simple building blocks. A prominent example is the non-interactive reduction from securely computing a ``complex" function $f$ to securely computing a ``simple" function $g$ via randomized encodings.

    Prior work equated simplicity with functions of small degree. In this work, we consider a different notion of simplicity where we require $g$ to only take inputs from a small number of parties. In other words, we want the arity of $g$ to be as small as possible.

    In more detail, we consider the problem of reducing secure computation of arbitrary functions to secure computation of functions with arity two (two is the minimal arity required to compute non-trivial functions). Specifically, we want to compute a function $f$ via a protocol that makes parallel calls to 2-ary functions. We want this protocol to be secure against malicious adversaries that could corrupt an arbitrary number of parties. We obtain the following results:
   
- Negative Result: We show that there exists a degree-2 polynomial $p$ such that no protocol that makes parallel calls to 2-ary functions can compute $p$ with statistical security with abort.
           
- Positive Results: We give two ways to bypass the above impossibility result.
            
  1. Weakening the Security Notion. We show that every degree-2 polynomial can be computed with statistical privacy with knowledge of outputs (PwKO) by making parallel calls to 2-ary functions. Privacy with knowledge of outputs is weaker than security with abort.
                       
  2. Computational Security. We prove that for every function $f$, there exists a protocol for computing $f$ that makes parallel calls to 2-ary functions and achieves security with abort against computationally-bounded adversaries. The security of this protocol relies on the existence of semi-honest secure oblivious transfer.
             
- Applications: We give connections between this problem and the task of reducing the encoding complexity of Multiparty Randomized Encodings (MPRE) (Applebaum, Brakerski, and Tsabary, TCC 2018). Specifically, we show that under standard computational assumptions, there exists an MPRE where the encoder can be implemented by an $\mathrm{NC}^0$ circuit with constant fan-out.
 
- Extensions: We explore this problem in the honest majority setting and give similar results assuming one-way functions. We also show that if the parties have access to 3-ary functions then we can construct a computationally secure protocol in the dishonest majority setting assuming one-way functions.



## 2024/1702

* Title: Secure and efficient transciphering for FHE-based MPC
* Authors: Diego F. Aranha, Antonio Guimarães, Clément Hoffmann, Pierrick Méaux
* [Permalink](https://eprint.iacr.org/2024/1702)
* [Download](https://eprint.iacr.org/2024/1702.pdf)

### Abstract

Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an es-
tablished technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a fundamental component in the practical construction of HE-based multi-party computation (MPC) protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by multiple (possibly malicious) parties, which may require additional security assumptions that have been so far overlooked in the HHE literature. In this paper, we formalize this issue as a security against related-key attacks (RKA) problem and provide efficient solutions for it. We start by presenting an efficient method for homomorphically evaluating Mixed-Filter-Permutator (MFP) ciphers in leveled mode, enabling speedups of up to thousands of times compared to previous literature. For the multi-party scenario, we focus specifically on the Margrethe cipher (Hoffmann et al., INDOCRYPT 2023). We show that, contrary to other commonly used HHE ciphers (e.g. FLIP), Margrethe is out-of-the-box secure for any protocols that allow malicious parties to learn up to two related key streams, enabling security for the vast majority of static MPC protocols. For other cases, we quantify the loss of security based on the number of related key streams (which often depends on the number of malicious parties and specific protocol). Performance-wise, our implementation of Margrethe takes just 3.9 ms to transcipher 4 bit messages, being significantly faster than the state of the art in terms of latency.



## 2024/1703

* Title: Free-XOR Gate Bootstrapping
* Authors: Chunling Chen, Xianhui Lu, Ruida Wang, Zhihao Li, Xuan Shen, Benqiang Wei
* [Permalink](https://eprint.iacr.org/2024/1703)
* [Download](https://eprint.iacr.org/2024/1703.pdf)

### Abstract

The FHEW-like gate bootstrapping framework operates in a 2-bit plaintext space, where logic gates such as NAND, XOR, and AND are implemented by adding two ciphertexts and extracting the most significant bit. However, each gate operation requires bootstrapping with a primary cost of one blind rotation, which is expensive, when processing circuit operations for applications. We propose a novel Free-XOR gate bootstrapping framework based on a single-bit plaintext space, in which the XOR operation is realized by simply adding two ciphertexts, resulting in an almost free computational cost. To form a minimal complete set for logical operations, we  design an algorithm for the AND gate within this framework. The AND gate cost of our Free-XOR gate bootstrapping involves two blind rotations. However, by utilizing a single-bit plaintext space to enhance noise tolerance and swapping some operations of the bootstrapping process, we can adopt a more compact parameter setting, which in turn accelerates the speed of blind rotation. We propose an instantiation of the NTRU-based AND gate operation, which requires two blind rotations. Despite the additional rotation, the overall computational cost is marginally lower than the state-of-the-art gate bootstrapping scheme LLW+ [TCHES24], which utilizes only a single blind rotation. In addition, our approach achieves a significant reduction in key size, reducing it to 3.3 times the size of LLW+ [TCHES24].



## 2024/1704

* Title: From One-Time to Two-Round Reusable Multi-Signatures without Nested Forking
* Authors: Lior Rotem, Gil Segev, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/1704)
* [Download](https://eprint.iacr.org/2024/1704.pdf)

### Abstract

Multi-signature schemes are gaining significant interest due to their blockchain applications. Of particular interest are two-round schemes in the plain public-key model that offer key aggregation, and whose security is based on the hardness of the DLOG problem. Unfortunately, despite substantial recent progress, the security proofs of the proposed schemes provide rather insufficient concrete guarantees (especially for 256-bit groups). This frustrating situation has so far been approached either by relying on the security of seemingly stronger assumptions or by considering restricted classes of attackers (e.g.., algebraic attackers, which are assumed to provide an algebraic justification of each group element that they produce).

We present a complementing approach by constructing multi-signature schemes that satisfy two relaxed notions of security, whose applicability nevertheless ranges from serving as drop-in replacements to enabling expressive smart contract validation procedures. Our first notion, one-time unforgeability, extends the analogous single-signer notion by considering attackers that obtain a single signature for some message and set of signers of their choice. We construct a non-interactive one-time scheme based on any ring-homomorphic one-way function, admitting efficient instantiations based on the DLOG and RSA assumptions. Aggregated verification keys and signatures consist of two group elements and a single group element, respectively, and our security proof consists of a single application of the forking lemma (thus avoiding the substantial security loss exhibited by the proposed two-round schemes). Additionally, we demonstrate that our scheme naturally extends to a $t$-time scheme, where aggregated verification keys consist of $t+1$ group elements, while aggregated signatures still consist of a single group element.

Our second notion, single-set unforgeability, considers attackers that obtain any polynomial number of signatures but are restricted to a single set of signers of their choice. We transform any non-interactive one-time scheme into a two-round single-set scheme via a novel forking-free construction that extends the seminal Naor-Yung tree-based approach to the multi-signer setting. Aggregated verification keys are essentially identical to those of the underlying one-time scheme, and the length of aggregated signatures is determined by that of the underlying scheme while scaling linearly with the length of messages (noting that long messages can always be hashed using a collision-resistant function). Instantiated with our one-time scheme, we obtain aggregated verification keys and signatures whose lengths are completely independent of the number of signers.



## 2024/1705

* Title: Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience
* Authors: Yuan Su, Yuan Lu, Jiliang Li, Yuyi Wang, Chengyi Dong, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/1705)
* [Download](https://eprint.iacr.org/2024/1705.pdf)

### Abstract

Fully asynchronous multi-party computation (AMPC) has superior robustness in realizing privacy and guaranteed output delivery (G.O.D.) against asynchronous adversaries that can arbitrarily delay communications. However, none of these protocols are truly practical, as they either have sub-optimal resilience, incur cumbersome communication cost, or suffer from an online phase with extra cryptographic overhead. The only attempting implementation---HoneyBadgerMPC (hbMPC)---merely ensures G.O.D. in some implausible optimistic cases due to a non-robust offline pre-processing phase.

We propose Dumbo-MPC a concretely efficient  AMPC-as-a-service design with all phases G.O.D. and optimal resilience against  $t<n/3$ malicious parties (where $n$ is the total number of parties). Same to hbMPC, Dumbo-MPC has a robust (almost) information-theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. While for achieving all phases G.O.D., we design a novel dual-mode offline protocol that can robustly pre-process multiplication triples in asynchrony. The offline phase features $O(n)$ per-triple communication in the optimistic case, followed by a fully asynchronous fallback to a pessimistic path to securely restore G.O..D. in the bad case. To efficiently implement the pessimistic path, we devise a concretely efficient zk-proof for product relationship of secret shares over compact KZG polynomial commitments, which enables us to reduce the degree of two secret shares' product from $2t$ to  $t$ and could be of independent interest.

We also implement and extensively evaluate Dumbo-MPC (particularly its offline phase) in varying network settings with up to 31 AWS servers. To our knowledge, we provide the first implementation of AMPC with all-phase G.O.D. A recent asynchronous triple generation protocol from Groth and Shoup (GS23) is also implemented and experimentally compared. When $n = 31$, Dumbo-MPC generates 94 triples/sec (almost twice of GS23) in the pessimistic case and 349 triples/sec (6X of GS23) in the good case, such that 31 parties require only 2-8 min to prepare a private Vickrey auction of 100 bidders or 10-36 min for a mixing network of $2^{10}$ inputs.



## 2024/1706

* Title: State of the art of HFE variants Is it possible to repair HFE with appropriate perturbations?
* Authors: Benoit COGLIATI, Gilles Macariot-Rat, Jacques Patarin, Pierre Varjabedian
* [Permalink](https://eprint.iacr.org/2024/1706)
* [Download](https://eprint.iacr.org/2024/1706.pdf)

### Abstract

HFE (that stands for Hidden Field Equations) belongs to
multivariate cryptography and was designed by Jacques Patarin in 1996
as a public key trapdoor suitable for encryption or signature. This original basic version is unfortunately known to have a super-polynomial
attack, but as imagined since the beginning, it comes with various variants, one can describe as combinations of “modifiers”.
In this work, we first present the state of the art of these HFE modifiers,
along with their effect on the complexity of the main cryptanalysis techniques against HFE-based schemes. This allows us, in a second time, to
identify a combination of two modifiers that has not yet been explored
and may still be secure with efficient parameters. Based on our analysis,
we propose a new signature scheme that offers extremely short signature
sizes, with reasonable public key sizes and performance. In particular, we
rely on the classical Feistel-Patarin technique to reduce signature sizes
below two times the security parameter.



## 2024/1707

* Title: CountCrypt: Quantum Cryptography between QCMA and PP
* Authors: Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/1707)
* [Download](https://eprint.iacr.org/2024/1707.pdf)

### Abstract

We construct a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QCMA}$ but quantum-computation-classical-communication (QCCC) key exchange, QCCC commitments, and two-round quantum key distribution exist. We also construct an oracle relative to which $\mathbf{BQP}=\mathbf{QMA}$, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QMA}$ but pseudorandom state generators (a quantum variant of pseudorandom generators) exist.
    We also show that QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of "quantum samplable" one-wayness and are an intermediate primitive between pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if $\mathbf{BQP}=\mathbf{PP}$.
    Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if $\mathbf{BQP} = \mathbf{QCMA}$, but are broken if $\mathbf{BQP} = \mathbf{PP}$. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class "CountCrypt".



## 2024/1708

* Title: Subliminal Encrypted Multi-Maps and Black-Box Leakage Absorption
* Authors: Amine Bahi, Seny Kamara, Tarik Moataz, Guevara Noubir
* [Permalink](https://eprint.iacr.org/2024/1708)
* [Download](https://eprint.iacr.org/2024/1708.pdf)

### Abstract

We propose a dynamic, low-latency encrypted multi-map (EMM) that operates in two
modes: low-leakage mode, which reveals minimal information such as data
size, expected response length, and query arrival rate; and subliminal
mode, which reveals only the data size while hiding metadata including query
and update times, the number of operations executed, and even whether an
operation was executed at all---albeit at the cost of full correctness. We
achieve this by exploiting a tradeoff between leakage and latency, a previously
underexplored resource in EMM design.  In low-leakage mode, our construction
improves upon existing work both asymptotically and empirically: it achieves
optimal server-side storage, as well as communication and computational
complexity that is independent of the maximum response length. In subliminal
mode, it is the first construction to hide metadata.

To analyze the latency and client-side storage of our construction, we utilize queuing theory and introduce a new queuing model, which may be of independent interest. To examine its metadata-hiding properties, we extend standard security definitions to account for metadata and prove a surprising result: if a scheme is subliminal in that it hides the execution of its operations, then it absorbs the leakage of any scheme that makes black-box use of it without sending additional messages. In other words, if a scheme is subliminal, then any scheme that makes black-box use of it will also be subliminal.

We implement and evaluate our construction, demonstrating that our empirical results align with our theoretical analysis and that the scheme achieves a median query latency below $10$ milliseconds, making it practical for some applications.



## 2024/1709

* Title: Do Not Disturb a Sleeping Falcon: Floating-Point Error Sensitivity of the Falcon Sampler and Its Consequences
* Authors: Xiuhan Lin, Mehdi Tibouchi, Yang Yu, Shiduo Zhang
* [Permalink](https://eprint.iacr.org/2024/1709)
* [Download](https://eprint.iacr.org/2024/1709.pdf)

### Abstract

Falcon is one of the three postquantum signature schemes already selected by NIST for standardization. It is the most compact among them, and offers excellent efficiency and security. However, it is based on a complex algorithm for lattice discrete Gaussian sampling which presents a number of implementation challenges. In particular, it relies on (possibly emulated) floating-point arithmetic, which is often regarded as a cause for concern, and has been leveraged in, e.g., side-channel analysis. The extent to which Falcon's use of floating point arithmetic can cause security issues has yet to be thoroughly explored in the literature.

In this paper, we contribute to filling this gap by identifying a way in which Falcon's lattice discrete Gaussian sampler, due to specific design choices, is singularly sensitive to floating-point errors. In the presence of small floating-point discrepancies (which can occur in various ways, including the use of the two almost but not quite equivalent signing procedures ``dynamic'' and ``tree'' exposed by the Falcon  API), we find that, when called twice on the same input, the Falcon sampler has a small but significant chance (on the order of once in a few thousand calls) of outputting two different lattice points with a very structured difference, that immediately reveals the secret key. This is in contrast to other lattice Gaussian sampling algorithms like Peikert's sampler and Prest's hybrid sampler, that are stable with respect to small floating-point errors.

Correctly generated Falcon signatures include a salt that should in principle prevent the sampler to ever be called on the same input twice. In that sense, our observation has little impact on the security of Falcon signatures per se (beyond echoing warnings about the dangers of repeated randomness). On the other hand, it is critical for derandomized variants of Falcon, which have been proposed for use in numerous settings.  One can mention in particular identity-based encryption, SNARK-friendly signatures, and sublinear signature aggregation. For all these settings, small floating point discrepancies have a chance of resulting in full private key exposure, even when using the slower, integer-based emulated floating-point arithmetic of Falcon's
reference implementation.



## 2024/1710

* Title: $\widetilde{\mbox{O}}$ptimal Adaptively Secure Hash-based Asynchronous Common Subset
* Authors: Hanwen Feng, Zhenliang Lu, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/1710)
* [Download](https://eprint.iacr.org/2024/1710.pdf)

### Abstract

Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in the same setting. In contrast, ACS has optimal constructions with quadratic communication complexity based on bilinear map assumptions.

In this paper, we bridge this gap by introducing a nearly optimal ACS, which solely relies on the blackbox use of collision-resistant hash functions. It exhibits $\widetilde{\mathcal{O}}(n^2)$ communication complexity, expected constant round complexity, and security against adaptive adversaries who can corrupt up to $n/3$ nodes and perform ``after-fact-removal'' attacks.

At the core of our new ACS is the first nearly optimal hash-based Multi-valued Validated Byzantine Agreement (MVBA).
To reduce cubic communication while avoiding heavy cryptographic tools, we introduce a new design paradigm, with several new components. We define and analyze our MVBA and components within the UC-framework, facilitating their modular use in broader applications, particularly in AMPC.



## 2024/1711

* Title: Good things come to those who wait: Dishonest-Majority Coin-Flipping Requires Delay Functions
* Authors: Joseph Bonneau, Benedikt Bünz, Miranda Christ, Yuval Efron
* [Permalink](https://eprint.iacr.org/2024/1711)
* [Download](https://eprint.iacr.org/2024/1711.pdf)

### Abstract

We reconsider Cleve's famous 1986 impossibility result on coin-flipping without an honest majority. Recently proposed constructions have circumvented this limit by using cryptographic delay functions. We show that this is necessary: a (weak) notion of delay functions is in fact implied by the existence of a protocol circumventing Cleve's impossibility. However, such delay functions are weaker than those used in existing constructions. We complete our result by showing an equivalence, that these weaker delay functions are also sufficient to construct not just fair dishonest-majority coin-flipping protocols, but also the stronger notion of a distributed randomness beacon. We also show that this is possible in a weaker communication model than previously considered, without the assumption of reliable broadcast or a public bulletin board.



## 2024/1712

* Title: Low-Communication Updatable PSI from Asymmetric PSI and PSU
* Authors: Guowei Ling, Peng Tang, Weidong Qiu
* [Permalink](https://eprint.iacr.org/2024/1712)
* [Download](https://eprint.iacr.org/2024/1712.pdf)

### Abstract

Private Set Intersection (PSI) allows two mutually untrusted parties to compute the intersection of their private sets without revealing additional information. In general, PSI operates in a static setting, where the computation is performed only once on the input sets of both parties. Badrinarayanan et al. (\textit{PoPETs} 2022) initiated the study of Updatable PSI (UPSI), which extends this capability to dynamically updating sets, enabling both parties to securely compute the intersection as their sets are modified while incurring significantly less overhead than re-executing a conventional PSI. However, existing UPSI protocols either do not support arbitrary deletion of elements or incur high computational and communication overhead. In this work, we combine asymmetric PSI with Private Set Union (PSU) to present a novel UPSI protocol. Our UPSI protocol supports arbitrary additions and deletions of elements, offering a flexible approach to update sets. Furthermore, our protocol enjoys extremely low communication overhead, scaling linearly with the size of the update set while remaining independent of the total set size. We implement our protocol and compare it against state-of-the-art conventional PSI and UPSI protocols. Experimental results demonstrate that our UPSI protocol incurs $587$ to $755$ times less communication overhead than the recently proposed UPSI protocol (\textit{AsiaCrypt} 2024) that supports arbitrary additions and deletions. Moreover,  our UPSI protocol has a significant advantage in low-bandwidth environments due to the exceptionally low communication overhead. Specifically, with an input size of $2^{22}$ and the size of the addition/deletion set being $2^{10}$, the existing UPSI protocol requires approximately $1650.45$, $1789.5$, and $3458.1$ seconds at bandwidths of $200$ Mbps, $50$ Mbps, and $5$ Mbps, respectively, whereas our UPSI protocol only requires around $13.01$, $13.75$, and $22.53$ seconds under the same conditions. Our open-source implementation is available at: \href{https://github.com/ShallMate/upsi}{https://github.com/ShallMate/upsi}.



## 2024/1713

* Title: Universally Composable Non-Interactive Zero-Knowledge from Sigma Protocols via a New Straight-line Compiler
* Authors: Megan Chen, Pousali Dey, Chaya Ganesh, Pratyay Mukherjee, Pratik Sarkar, Swagata Sasmal
* [Permalink](https://eprint.iacr.org/2024/1713)
* [Download](https://eprint.iacr.org/2024/1713.pdf)

### Abstract

Non-interactive zero-knowledge proofs (NIZK) are essential building blocks in threshold cryptosystems like multiparty signatures, distributed key generation, and verifiable secret sharing, allowing parties to prove correct behavior without revealing secrets. Furthermore, universally composable (UC) NIZKs enable seamless composition in the larger cryptosystems.  A popular way to construct NIZKs is to compile interactive protocols using the Fiat-Shamir transform. Unfortunately, Fiat-Shamir transformed NIZK requires rewinding the adversary and is not $\textit{straight-line extractable}$, making it at odds with UC. Using Fischlin's transform gives straight-line extractability, but at the expense of many repetitions of the underlying protocol leading to poor concrete efficiency and difficulty in setting parameters.

In this work, we propose a simple new transform that compiles a Sigma protocol for an algebraic relation into a UC-NIZK protocol $\textit{without any overheads of repetition}$.

    - Given a Sigma protocol for proving m algebraic statements over n witnesses, we construct a compiler to transform it into a $\textit{straight-line extractable}$ protocol using an additively homomorphic encryption scheme AHE. Our prover executes the Sigma protocol's prover once and computes 2n encryptions. The verification process involves running the Sigma protocol verifier once and then computing n encryptions, which are homomorphically verified against the prover generated encryptions.

    - We apply the Fiat-Shamir transform to the above straight-line extractable Sigma protocol to obtain a UC-NIZK. We instantiate AHE using class group-based encryption where the public key of the encryption scheme is obliviously sampled using a suitable hash function. This yields a UC-NIZK protocol in the random oracle model.



## 2024/1714

* Title: Theoretical Approaches to Solving the Shortest Vector Problem in NP-Hard Lattice-Based Cryptography with Post-SUSY Theories of Quantum Gravity in Polynomial Time
* Authors: Trevor Nestor
* [Permalink](https://eprint.iacr.org/2024/1714)
* [Download](https://eprint.iacr.org/2024/1714.pdf)

### Abstract

The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, noncommutative geometry, spectral theory, and post-SUSY particle physics to address SVP. By mapping high-dimensional lattice points to spin foam networks and by means of Hamiltonian engineering, it is theoretically possible to devise new algorithms that leverage the interactions topologically protected Majorana fermion particles have with the gravitational field through the spectral action principle to loop through these spinfoam networks where SVP vectors could then be encoded onto the spectrum of the corresponding Dirac operators within the system. We establish a novel approach that leverages post-SUSY physics and theories of quantum gravity to achieve algorithmic speedups beyond those expected by conventional quantum computers. This interdisciplinary methodology not only proposes potential polynomial-time algorithms for SVP but also bridges gaps between theoretical physics and cryptographic applications, providing further insights into the Riemann Hypothesis (RH) and the Hilbert-Polya Conjecture.



## 2024/1715

* Title: OT-PCA: New Key-Recovery Plaintext-Checking Oracle Based Side-Channel Attacks on HQC with Offline Templates
* Authors: Haiyue Dong, Qian Guo
* [Permalink](https://eprint.iacr.org/2024/1715)
* [Download](https://eprint.iacr.org/2024/1715.pdf)

### Abstract

In this paper, we introduce OT-PCA, a novel approach for conducting Plaintext-Checking (PC) oracle based side-channel attacks, specifically designed for Hamming Quasi-Cyclic (HQC). By calling the publicly accessible HQC decoder, we build offline templates that enable efficient extraction of soft information for hundreds of secret positions with just a single PC oracle call. Our method addresses critical challenges in optimizing key-related information extraction, including maximizing decryption output entropy and ensuring error pattern independence, through the use of genetic-style algorithms.

Extensive simulations demonstrate that our new attack method significantly reduces the required number of oracle calls, achieving a 2.4-fold decrease for hqc-128 and even greater reductions for hqc-192 and hqc-256 compared to current state-of-the-art methods. Notably, the attack shows strong resilience against inaccuracy in the PC oracle—when the oracle accuracy decreases to 95%, the reduction factor in oracle call requirements increases to 7.6 for hqc-128.

Lastly, a real-world evaluation conducted using power analysis on a platform with an ARM Cortex-M4 microcontroller validates the practical applicability and effectiveness of our approach.



## 2024/1716

* Title: Rate-1 Statistical Non-Interactive Zero-Knowledge
* Authors: Pedro Branco, Nico Döttling, Akshayaram Srinivasan
* [Permalink](https://eprint.iacr.org/2024/1716)
* [Download](https://eprint.iacr.org/2024/1716.pdf)

### Abstract

We give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge.  For the $\mathsf{circuitSAT}$ language, our construction achieves a proof length of $|w| + |w|^\epsilon \cdot \mathsf{poly}(\lambda)$ where $w$ denotes the witness, $\lambda$ is the security parameter, $\epsilon$ is a small constant less than 1, and $\mathsf{poly}(\cdot)$ is a fixed polynomial that is independent of the instance or the witness size. The soundness of our construction follows from either the LWE assumption, or the $O(1)$-$\mathsf{LIN}$ assumption on prime-order groups with efficiently computable bilinear maps, or the sub-exponential DDH assumption. Previously, Gentry et al. (Journal of Cryptology, 2015) achieved NIZKs with statistical soundness and computational zero-knowledge with the aforementioned proof length by relying on the Learning with Errors (LWE) assumption.



## 2024/1717

* Title: Practical Asynchronous MPC from Lightweight Cryptography
* Authors: Atsuki Momose
* [Permalink](https://eprint.iacr.org/2024/1717)
* [Download](https://eprint.iacr.org/2024/1717.pdf)

### Abstract

We present an asynchronous secure multi-party computation (MPC) protocol that is practically efficient. Our protocol can evaluate any arithmetic circuit with linear communication in the number of parties per multiplication gate, while relying solely on computationally lightweight cryptography such as hash function and symmetric encryption. Our protocol is optimally resilient and tolerates $t$ malicious parties among $n = 3t+1$ parties.

At the technical level, we manage to apply the \emph{player-elimination} paradigm to asynchronous MPC. This framework enables the detection and eviction of cheating parties by repeatedly attempting to generate Beaver triples. Once all malicious parties are eliminated, honest parties can proceed with efficient Beaver triple generation.
While this approach is standard in synchronous MPC, it presents several technical challenges when adopted in an asynchronous network, which we address in this work.