## In this issue

1. [2024/750] Speeding Up Multi-Scalar Multiplications for ...
2. [2024/1587] Fully Homomorphic Encryption for Cyclotomic Prime ...
3. [2024/1974] Efficient and Practical Multi-party Private Set ...
4. [2024/1975] Quadratic Modelings of Syndrome Decoding
5. [2024/1976] HI-CKKS: Is High-Throughput Neglected? Reimagining ...
6. [2024/1977] Bounded CCA Secure Proxy Re-encryption Based on Kyber
7. [2024/1978] µLAM: A LLM-Powered Assistant for Real-Time Micro- ...
8. [2024/1979] On the Security of LWE-based KEMs under Various ...
9. [2024/1980] Sonikku: Gotta Speed, Keed! A Family of Fast and ...
10. [2024/1981] Shutter Network: Private Transactions from ...
11. [2024/1982] New Results in Quantum Analysis of LED: Featuring ...
12. [2024/1983] UTRA: Universe Token Reusability Attack and ...
13. [2024/1984] Low Communication Threshold Fully Homomorphic ...
14. [2024/1985] Endomorphisms for Faster Cryptography on Elliptic ...
15. [2024/1986] Improved Quantum Analysis of ARIA
16. [2024/1987] Side-Channel Attack on ARADI
17. [2024/1988] Garbled Circuits with 1 Bit per Gate
18. [2024/1989] Revisiting OKVS-based OPRF and PSI: Cryptanalysis ...
19. [2024/1990] How To Scale Multi-Party Computation
20. [2024/1991] CHLOE: Loop Transformation over Fully Homomorphic ...
21. [2024/1992] Improved Quantum Linear Attacks and Application to CAST
22. [2024/1993] BOIL: Proof-Carrying Data from Accumulation of ...
23. [2024/1994] Token-Based Key Exchange - Non-Interactive Key ...
24. [2024/1995] BitVM: Quasi-Turing Complete Computation on Bitcoin
25. [2024/1996] A Framework for Generating S-Box Circuits with ...
26. [2024/1997] On format preserving encryption with nonce
27. [2024/1998] Impossible Differential Automation: Model ...
28. [2024/1999] Multivariate Encryptions with LL’ perturbations - ...
29. [2024/2000] Evasive LWE Assumptions: Definitions, Classes, and ...
30. [2024/2001] Xiezhi: Toward Succinct Proofs of Solvency
31. [2024/2002] Improving Differential-Neural Distinguisher For ...
32. [2024/2003] Exploring the Optimal Differential Characteristics ...
33. [2024/2004] Regev's attack on hyperelliptic cryptosystems
34. [2024/2005] Post-Quantum Secure Channel Protocols for eSIMs
35. [2024/2006] Data Decryption and Analysis of Note-Taking ...
36. [2024/2007] A Combinatorial Attack on Ternary Sparse Learning ...
37. [2024/2008] PrivCirNet: Efficient Private Inference via Block ...
38. [2024/2009] The Mis/Dis-information Problem is Hard to Solve
39. [2024/2010] Anonymous credentials from ECDSA
40. [2024/2011] Honest-Majority Threshold ECDSA with Batch ...
41. [2024/2012] GraSS: Graph-based Similarity Search on Encrypted Query
42. [2024/2013] Crescent: Stronger Privacy for Existing Credentials
43. [2024/2014] On the Traceability of Group Signatures: ...
44. [2024/2015] Universal SNARGs for NP from Proofs of Correctness
45. [2024/2016] The Existence of Quantum One-Way Functions
46. [2024/2017] Byzantine Consensus in Wireless Networks
47. [2024/2018] On the BUFF Security of ECDSA with Key Recovery
48. [2024/2019] Key-Insulated and Privacy-Preserving Signature ...
49. [2024/2020] Ring Ring! Who's There? A Privacy Preserving Mobile ...
50. [2024/2021] PrivQuant: Communication-Efficient Private ...
51. [2024/2022] The Revisited Hidden Weight Bit Function
52. [2024/2023] An Abstract Multi-Forking Lemma
53. [2024/2024] Hash-Prune-Invert: Improved Differentially Private ...
54. [2024/2025] Mira: Efficient Folding for Pairing-based Arguments
55. [2024/2026] Orbweaver: Succinct Linear Functional Commitments ...
56. [2024/2027] Impact Tracing: Identifying the Culprit of ...
57. [2024/2028] Qubit Optimized Quantum Implementation of SLIM
58. [2024/2029] NLAT: the NonLinear Distribution Table of Vectorial ...
59. [2024/2030] Security Analysis of ASCON Cipher under Persistent ...

## 2024/750

* Title: Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs
* Authors: Xinxin Fan, Veronika Kuchta, Francesco Sica, Lei Xu
* [Permalink](https://eprint.iacr.org/2024/750)
* [Download](https://eprint.iacr.org/2024/750.pdf)

### Abstract

Multi-scalar multiplication (MSM) is one of the core components of many zero-knowledge proof systems, and a primary performance bottleneck for proof generation in these schemes. One major strategy to accelerate MSM is utilizing precomputation. Several algorithms (e.g., Pippenger and BGMW) and their variants have been proposed in this direction. In this paper, we revisit the recent precomputation-based MSM calculation method proposed by Luo, Fu and Gong at CHES 2023 and generalize their approach. In particular, we presented a general construction of optimal buckets. This improvement leads to significant performance improvements, which are verified by both theoretical analysis and experiments.

## 2024/1587

* Title: Fully Homomorphic Encryption for Cyclotomic Prime Moduli
* Authors: Robin Geelen, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2024/1587)
* [Download](https://eprint.iacr.org/2024/1587.pdf)

### Abstract

This paper presents a Generalized BFV (GBFV) fully homomorphic encryption scheme that encrypts plaintext spaces of the form $\mathbb{Z}[x]/(\Phi_m(x), t(x))$ with $\Phi_m(x)$ the $m$-th cyclotomic polynomial and $t(x)$ an arbitrary polynomial. GBFV encompasses both BFV where $t(x) = p$ is a constant, and the CLPX scheme (CT-RSA 2018) where $m = 2^k$ and $t(x) = x-b$ is a linear polynomial. The latter can encrypt a single huge integer modulo $\Phi_m(b)$, has much lower noise growth than BFV (linear in $m$ instead of exponential), but cannot be bootstrapped.

We show that by a clever choice of $m$ and higher degree polynomial $t(x)$, our scheme combines the SIMD capabilities of BFV with the low noise growth of CLPX, whilst still being efficiently bootstrappable. Moreover, we present parameter families that natively accommodate packed plaintext spaces defined by a large cyclotomic prime, such as the Fermat prime $\Phi_2(2^{16}) = 2^{16} + 1$ and the Goldilocks prime $\Phi_6(2^{32}) = 2^{64} - 2^{32} + 1$. These primes are often used in homomorphic encryption applications and zero-knowledge proof systems.

Due to the lower noise growth, e.g. for the Goldilocks prime, GBFV can evaluate circuits whose multiplicative depth is more than $5$ times larger than native BFV. As a result, we can evaluate either larger circuits or work with much smaller ring dimensions. In particular, we can natively bootstrap GBFV at 128-bit security for a large prime, already at ring dimension $2^{14}$, which was impossible before. We implemented the GBFV scheme on top of the SEAL library and achieve a latency of only $2$ seconds to bootstrap a ciphertext encrypting up to $8192$ elements modulo $2^{16}+1$.

## 2024/1974

* Title: Efficient and Practical Multi-party Private Set Intersection Cardinality Protocol
* Authors: Shengzhe Meng, Xiaodong Wang, Zijie Lu, Bei Liang
* [Permalink](https://eprint.iacr.org/2024/1974)
* [Download](https://eprint.iacr.org/2024/1974.pdf)

### Abstract

We present an efficient and simple multi-party private set intersection cardinality (PSI-CA) protocol that allows several parties to learn the intersection size of their private sets without revealing any other information. Our protocol is highly efficient because it only utilizes the Oblivious Key-Value Store and zero-sharing techniques, without incorporating components such as OPPRF (Oblivious Programmable Pseudorandom Function) which is the main building block of multi-party PSI-CA protocol by Gao et al. (PoPETs 2024). Our protocol exhibits better communication and computational overhead than the state-of-the-art.

To compute the intersection between 16 parties with a set size of $2^{20}$ each, our PSI-CA protocol only takes 5.84 seconds and 326.6 MiB of total communication, which yields a reduction in communication by a factor of up to 2.4× compared to the state-of-the-art multi-party PSI-CA protocol of Gao et al. (PoPETs 2024).
We prove that our protocol is secure in the presence of a semi-honest adversary who may passively corrupt any $(t-2)$-out-of-$t$ parties once two specific participants are non-colluding.

## 2024/1975

* Title: Quadratic Modelings of Syndrome Decoding
* Authors: Alessio Caminata, Ryann Cartor, Alessio Meneghetti, Rocco Mora, Alex Pellegrini
* [Permalink](https://eprint.iacr.org/2024/1975)
* [Download](https://eprint.iacr.org/2024/1975.pdf)

### Abstract

This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over $\mathbb{F}_2$, we improve on a previous work and study the degree of regularity of the modeling of the exact weight SDP. Additionally, we introduce a novel technique that transforms SDP instances over $\mathbb{F}_q$ into systems of polynomial equations and thoroughly investigate the dimension of their varieties. Experimental results are provided to evaluate the complexity of solving SDP instances using our models through Gröbner bases techniques.

## 2024/1976

* Title: HI-CKKS: Is High-Throughput Neglected? Reimagining CKKS Efficiency with Parallelism
* Authors: Fuyuan Chen, Jiankuo Dong, Xiaoyu Hu, Zhenjiang Dong, Wangchen Dai, Jingqiang Lin, Fu Xiao
* [Permalink](https://eprint.iacr.org/2024/1976)
* [Download](https://eprint.iacr.org/2024/1976.pdf)

### Abstract

The proliferation of data outsourcing and cloud services has heightened privacy vulnerabilities. CKKS, among the most prominent homomorphic encryption schemes, allows computations on encrypted data, serving as a critical privacy safeguard. However, performance remains a central bottleneck, hindering widespread adoption. Existing optimization efforts often prioritize latency reduction over throughput performance. This paper presents HI-CKKS, a throughput-oriented High-performance Implementation of CKKS homomorphic encryption, addressing these challenges. Our HI-CKKS introduces a batch-supporting asynchronous execution scheme, effectively mitigating frequent data interactions and high waiting delays between hosts and servers in service-oriented scenarios. We analyze the fundamental (I)NTT primitive, which is critical in CKKS, and develop a hierarchical, hybrid high-throughput implementation. This includes efficient arithmetic module instruction set implementations, unified kernel fusion, and hybrid memory optimization strategies that significantly improve memory access efficiency and the performance of (I)NTT operations. Additionally, we propose a multi-dimensional parallel homomorphic multiplication scheme aimed at maximizing throughput and enhancing the performance of (I)NTT and homomorphic multiplication. In conclusion, our implementation is deployed on the RTX 4090, where we conduct a thorough throughput performance evaluation of HI-CKKS, enabling us to pinpoint the most effective parallel parameter settings. Compared to the CPU implementation, our system achieves throughput increases of $175.08\times$, $191.27\times$, and $679.57\times$ for NTT, INTT, and HMult, respectively. And our throughput performance still demonstrates a significant improvement, ranging from $1.54\times$ to $693.17\times$ compared to the latest GPU-based works.