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