## In this issue

1. [2023/1381] Sometimes You Can’t Distribute Random-Oracle-Based ...
2. [2023/1542] Don’t Forget Pairing-Friendly Curves with Odd Prime ...
3. [2024/347] The Algebraic Freelunch: Efficient Gröbner Basis ...
4. [2024/358] Stateless Deterministic Multi-Party EdDSA ...
5. [2024/747] Scaling Lattice Sieves across Multiple Machines
6. [2024/757] Formal Definition and Verification for Combined ...
7. [2024/767] Bootstrapping Bits with CKKS
8. [2024/825] KHAN Encryption Algorithm: Leveraging Full Reptend ...
9. [2024/826] Securing Lightning Channels against Rational Miners
10. [2024/827] Multivariate Multi-Polynomial Commitment and its ...
11. [2024/828] Post-quantum XML and SAML Single Sign-On
12. [2024/829] Multi-Server Doubly Efficient PIR
13. [2024/830] How (not) to Build Quantum PKE in Minicrypt
14. [2024/831] Tight Characterizations for Preprocessing against ...
15. [2024/832] Hamming Weight Proofs of Proximity with One-Sided Error
16. [2024/833] INDIANA - Verifying (Random) Probing Security ...
17. [2024/834] Fine-Grained Non-Interactive Key Exchange, Revisited
18. [2024/835] Provable security against decryption failure ...
19. [2024/836] The Round Complexity of Proofs in the Bounded ...
20. [2024/837] Fully Secure MPC and zk-FLIOP Over Rings: New ...
21. [2024/838] Verifiable Secret Sharing from Symmetric Key ...
22. [2024/839] Almost optimal succinct arguments for Boolean ...
23. [2024/840] Batching-Efficient RAM using Updatable Lookup Arguments
24. [2024/841] Two generalizations of almost perfect nonlinearity
25. [2024/842] Computation Efficient Structure Aware PSI From ...
26. [2024/843] Formally verifying Kyber Episode V: Machine-checked ...
27. [2024/844] Finding Dense Submodules with Algebraic Lattice ...
28. [2024/845] PathGES: An Efficient and Secure Graph Encryption ...
29. [2024/846] Distributed Asynchronous Remote Key Generation
30. [2024/847] More Efficient Approximate $k$-wise Independent ...
31. [2024/848] How (Not) to Simulate PLONK
32. [2024/849] Fast, Lagre Scale Dimensionality Reduction Schemes ...
33. [2024/850] Constant-Round Arguments for Batch-Verification and ...
34. [2024/851] On the parallelization of square-root Vélu's formulas
35. [2024/852] Breaking Indistinguishability with Transfer ...
36. [2024/853] Practical q-IND-CPA-D-Secure Approximate ...
37. [2024/854] Simulation-Extractable KZG Polynomial Commitments ...
38. [2024/855] Securing the Future of GenAI: Policy and Technology
39. [2024/856] Indistinguishability Obfuscation from Bilinear Maps ...
40. [2024/857] Speeding up Preimage and Key-Recovery Attacks with ...
41. [2024/858] Ascon-Keccak AEAD Algorithm

## 2023/1381

* Title: Sometimes You Can’t Distribute Random-Oracle-Based Proofs
* Authors: Jack Doerner, Yashvanth Kondi, Leah Namisa Rosenbloom
* [Permalink](https://eprint.iacr.org/2023/1381)
* [Download](https://eprint.iacr.org/2023/1381.pdf)

### Abstract

We investigate the conditions under which straight-line extractable NIZKs in the random oracle model (i.e. without a CRS) permit multiparty realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any MPC protocol to compute such a NIZK cannot make black-box use of the random oracle or a hash function instantiating it if security against all-but-one corruptions is desired, unless the number of queries made by the verifier to the oracle grows linearly with the number of parties. This presents a fundamental barrier to constructing efficient protocols to securely distribute the computation of NIZKs (and signatures) based on MPC-in-the-head, PCPs/IOPs, and sigma protocols compiled with transformations due to Fischlin, Pass, or Unruh.

When the adversary is restricted to corrupt only a constant fraction of parties, we give a positive result by means of a tailored construction, which demonstrates that our impossibility does not extend to weaker corruption models in general.

## 2023/1542

* Title: Don’t Forget Pairing-Friendly Curves with Odd Prime Embedding Degrees
* Authors: Yu Dai, Fangguo Zhang, Chang-an Zhao
* [Permalink](https://eprint.iacr.org/2023/1542)
* [Download](https://eprint.iacr.org/2023/1542.pdf)

### Abstract

Pairing-friendly curves with odd prime embedding degrees
at the 128-bit security level, such as BW13-310 and BW19-286, sparked
interest in the field of public-key cryptography as small sizes of the prime
fields. However, compared to mainstream pairing-friendly curves at the
same security level, i.e., BN446 and BLS12-446, the performance of pairing computations on BW13-310 and BW19-286 is usually considered
ineffcient. In this paper we investigate high performance software implementations of pairing computation on BW13-310 and corresponding
building blocks used in pairing-based protocols, including hashing, group
exponentiations and membership testings. Firstly, we propose effcient
explicit formulas for pairing computation on this curve. Moreover, we
also exploit the state-of-art techniques to implement hashing in G1 and
G2, group exponentiations and membership testings. In particular, for
exponentiations in G2 and GT , we present new optimizations to speed
up computational effciency. Our implementation results on a 64-bit processor show that the gap in the performance of pairing computation between BW13-310 and BN446 (resp. BLS12-446) is only up to 4.9% (resp.
26%). More importantly, compared to BN446 and BLS12-446, BW13-
310 is about 109.1% − 227.3%, 100% − 192.6%, 24.5% − 108.5% and
68.2% − 145.5% faster in terms of hashing to G1, exponentiations in G1
and GT , and membership testing for GT , respectively. These results reveal that BW13-310 would be an interesting candidate in pairing-based
cryptographic protocols.

## 2024/347

* Title: The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives
* Authors: Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, Håvard Raddum
* [Permalink](https://eprint.iacr.org/2024/347)
* [Download](https://eprint.iacr.org/2024/347.pdf)

### Abstract

In this paper, we present a new type of algebraic attack that applies to many recent arithmetization-oriented families of permutations, such as those used in Griffin, Anemoi, ArionHash, and XHash8, whose security relies on the hardness of the constrained-input constrained-output (CICO) problem. We introduce the FreeLunch approach: the monomial ordering is chosen so that the natural polynomial system encoding the CICO problem already is a Gröbner basis. In addition, we present a new dedicated resolution algorithm for FreeLunch systems of complexity lower than applicable state-of-the-art FGLM algorithms.
We show that the FreeLunch approach challenges the security of fullround instances of Anemoi, Arion and Griffin. We confirm these theoretical results with experimental results on those three permutations. In particular, using the FreeLunch attack combined with a new technique to bypass 3 rounds of Griffin, we recover a CICO solution for 7 out of 10 rounds of Griffin in less than four hours on one core of AMD EPYC 7352 (2.3GHz).

## 2024/358

* Title: Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication
* Authors: Qi Feng, Kang Yang, Kaiyi Zhang, Xiao Wang, Yu Yu, Xiang Xie, Debiao He
* [Permalink](https://eprint.iacr.org/2024/358)
* [Download](https://eprint.iacr.org/2024/358.pdf)

### Abstract

EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature scheme based on Edwards curves, benefitting from stateless and deterministic derivation of nonces (i.e., it does not require a reliable source of randomness or state continuity). Recently, NIST called for multi-party threshold EdDSA signatures in one mode of verifying such nonce derivation via zero-knowledge (ZK) proofs. However, it is challenging to translate the stateless and deterministic benefits of EdDSA to the multi-party threshold setting, as no fresh randomness is available for signing the same message. In this paper, we present a new stateless and deterministic multi-party EdDSA protocol in the full-threshold setting, tolerating all-but-one malicious corruptions. Compared to the state-of-the-art multi-party EdDSA protocol by Garillot et al. (Crypto'21), we improve the communication cost by a factor of 56x and have the same three rounds, at the cost of increasing the computational cost by about 2.25x. We adopt information-theoretic message authenticated codes (IT-MACs) in the multi-verifier setting to authenticate values, and convert them from a Boolean domain to an arithmetic domain by refining multi-verifier extended doubly-authenticated bits (\edabits). We adopt pseudorandom correlation function (\PCF) to generate IT-MACs statelessly and deterministically. Together, we design a multi-verifier zero-knowledge (MVZK) protocol to derive nonces statelessly and deterministically.

## 2024/747

* Title: Scaling Lattice Sieves across Multiple Machines
* Authors: Martin R. Albrecht, Joe Rowell
* [Permalink](https://eprint.iacr.org/2024/747)
* [Download](https://eprint.iacr.org/2024/747.pdf)

### Abstract

Lattice sieves are algorithms for finding short vectors in lattices. We present an implementation of two such sieves – known as “BGJ1” and “BDGL” in the literature – that scales across multiple servers (with varying success). This class of algorithms requires exponential memory which had put into question their ability to scale across sieving nodes. We discuss our architecture and optimisations and report experimental evidence of the efficiency of our approach.