## In this issue

1. [2024/1210] More Optimizations to Sum-Check Proving
2. [2024/1211] A Generic Framework for Side-Channel Attacks ...
3. [2024/1212] Efficient Layered Circuit for Verification of SHA3 ...
4. [2024/1213] Bounded-Collusion Streaming Functional Encryption ...
5. [2024/1214] Less Effort, More Success: Efficient Genetic ...
6. [2024/1215] Falsifiability, Composability, and Comparability of ...
7. [2024/1216] Delegatable Anonymous Credentials From Mercurial ...
8. [2024/1217] A Compact and Parallel Swap-Based Shuffler based on ...
9. [2024/1218] A Note on the use of the Double Boomerang ...
10. [2024/1219] Foldable, Recursive Proofs of Isogeny Computation ...
11. [2024/1220] Mova: Nova folding without committing to error terms
12. [2024/1221] Depth Optimized Quantum Circuits for HIGHT and LEA
13. [2024/1222] Quantum Implementation and Analysis of ARIA
14. [2024/1223] A short-list of pairing-friendly curves resistant ...
15. [2024/1224] Generic Construction of Secure Sketches from Groups
16. [2024/1225] SIGNITC: Supersingular Isogeny Graph Non- ...
17. [2024/1226] A Spectral Analysis of Noise: A Comprehensive, ...
18. [2024/1227] ZIPNet: Low-bandwidth anonymous broadcast from ...
19. [2024/1228] Automated Software Vulnerability Static Code ...
20. [2024/1229] Benchmarking Attacks on Learning with Errors
21. [2024/1230] Impossible Boomerang Attacks Revisited: ...
22. [2024/1231] A Constructive View of Homomorphic Encryption and ...
23. [2024/1232] Efficient and Privacy-Preserving Collective Remote ...
24. [2024/1233] Binding Security of Implicitly-Rejecting KEMs and ...
25. [2024/1234] EagleSignV3 : A new secure variant of EagleSign ...
26. [2024/1235] Blue fish, red fish, live fish, dead fish
27. [2024/1236] Optimizing Big Integer Multiplication on Bitcoin: ...
28. [2024/1237] Efficient Variants of TNT with BBB Security

## 2024/1210

* Title: More Optimizations to Sum-Check Proving
* Authors: Quang Dao, Justin Thaler
* [Permalink](https://eprint.iacr.org/2024/1210)
* [Download](https://eprint.iacr.org/2024/1210.pdf)

### Abstract

Many fast SNARKs apply the sum-check protocol to an $n$-variate polynomial of the form $g(x) = \text{eq}(w,x) \cdot p(x)$, where $p$ is a product of multilinear polynomials, $w \in \mathbb{F}^n$ is a random vector, and $\text{eq}$ is the multilinear extension of the equality function.

In this setting, we describe an optimization to the sum-check prover that substantially reduces the cost coming from the $\text{eq}(w, x)$ factor. Our work further improves on a prior optimization by Gruen (ePrint 2023), and in the small-field case, can be combined with additional optimizations by Bagad, Domb, and Thaler (ePrint 2024), and Dao and Thaler (ePrint 2024).

Over large prime-order fields, our optimization eliminates roughly $2^{n + 1}$ field multiplications compared to a standard linear-time implementation of the prover, and roughly $2^{n-1}$ field multiplications when considered on top of Gruen's optimization. These savings are about a 25% (respectively 10%) end-to-end prover speedup in common use cases, and potentially even larger when working over binary tower fields.

## 2024/1211

* Title: A Generic Framework for Side-Channel Attacks against LWE-based Cryptosystems
* Authors: Julius Hermelink, Silvan Streit, Erik Mårtensson, Richard Petri
* [Permalink](https://eprint.iacr.org/2024/1211)
* [Download](https://eprint.iacr.org/2024/1211.pdf)

### Abstract

Lattice-based cryptography is in the process of being standardized. Several proposals to deal with side-channel information using lattice reduction exist. However, it has been shown that algorithms based on Bayesian updating are often more favorable in practice.

In this work, we define distribution hints; a type of hint that allows modelling probabilistic information. These hints generalize most previously defined hints and the information obtained in several attacks.

We define two solvers for our hints; one is based on belief propagation and the other one uses a greedy approach. We prove that the latter is a computationally less expensive approximation of the former and that previous algorithms used for specific attacks may be seen as special cases of our solvers. Thereby, we provide a systematization of previously obtained information and used algorithms in real-world side-channel attacks.

In contrast to lattice-based approaches, our framework is not limited to value leakage. For example, it can deal with noisy Hamming weight leakage or partially incorrect information. Moreover, it improves upon the recovery of the secret key from approximate hints in the form they arise in real-world attacks.

Our framework has several practical applications: We exemplarily show that a recent attack can be improved; we reduce the number of traces and corresponding ciphertexts and increase the noise resistance. Further, we explain how distribution hints could be applied in the context of previous attacks and outline a potential new attack.

## 2024/1212

* Title: Efficient Layered Circuit for Verification of SHA3 Merkle Tree
* Authors: Changchang Ding, Zheming Fu
* [Permalink](https://eprint.iacr.org/2024/1212)
* [Download](https://eprint.iacr.org/2024/1212.pdf)

### Abstract

We present an efficient layered circuit design for SHA3-256 Merkle tree verification, suitable for a GKR proof system, that achieves logarithmic verification and proof size. We demonstrate how to compute the predicate functions for our circuit in $O(\log n)$ time to ensure logarithmic verification and provide GKR benchmarks for our circuit.

## 2024/1213

* Title: Bounded-Collusion Streaming Functional Encryption from Minimal Assumptions
* Authors: Kaartik Bhushan, Alexis Korb, Amit Sahai
* [Permalink](https://eprint.iacr.org/2024/1213)
* [Download](https://eprint.iacr.org/2024/1213.pdf)

### Abstract

Streaming functional encryption (sFE), recently introduced by Guan, Korb, and Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored for iterative computation on dynamic data streams. Unlike in regular FE, in an sFE scheme, users can encrypt and compute on the data as soon as it becomes available and in time proportional to just the size of the newly arrived data.

As sFE implies regular FE, all known constructions of sFE and FE for $\mathsf{P/Poly}$ require strong cryptographic assumptions which are powerful enough to build indistinguishability obfuscation. In contrast, bounded-collusion FE, in which the adversary is restricted to making at most $Q$ function queries for some polynomial $Q$ determined at setup, can be built from the minimal assumptions of public-key encryption (for public-key FE) [Sahai and Seyalioglu, CCS 2010; Gorbunov, Vaikuntanathan, and Wee, CRYPTO 2012] and secret-key encryption (for secret-key FE)[Ananth, Vaikuntanathan, TCC 2019].

In this paper, we introduce and build bounded-collusion streaming FE for any polynomial bound $Q$ from the same minimal assumptions of public-key encryption (for public-key sFE) and secret-key encryption (for secret-key sFE). Similarly to the original sFE paper of Guan, Korb, and Sahai, our scheme satisfies semi-adaptive-function-selective security which is similar to standard adaptive indistinguishability-based security except that we require all functions to be queried before any of the challenge messages.

Along the way, our work also replaces a key ingredient (called $\mathsf{One}\text{-}\mathsf{sFE}$) from the original work of Guan, Korb, and Sahai with a much simpler construction based on garbled circuits.

## 2024/1214

* Title: Less Effort, More Success: Efficient Genetic Algorithm-Based Framework for Side-channel Collision Attacks
* Authors: Jiawei Zhang, Jiangshan Long, Changhai Ou, Kexin Qiao, Fan Zhang, Shi Yan
* [Permalink](https://eprint.iacr.org/2024/1214)
* [Download](https://eprint.iacr.org/2024/1214.pdf)

### Abstract

By introducing collision information, the existing side-channel Correlation-Enhanced Collision Attacks (CECAs) performed collision-chain detection, and reduced a given candidate space to a significantly smaller collision-chain space, leading to more efficient key recovery. However, they are still limited by low collision detection speed and low success rate of key recovery. To address these issues, we first give a Collision Detection framework with Genetic Algorithm (CDGA), which exploits Genetic Algorithm to detect the collision chains and has a strong capability of global searching. Secondly, we theoretically analyze the performance of CECA, and bound the searching depth of its output candidate
vectors with a confidence level using a rigorous hypothesis test, which is suitable both for Gaussian and non-Gaussian leakages. This facilitates the
initialization of the population.
Thirdly, we design an innovative goal-directed mutation method to randomly select new gene values for replacement, thus improving efficiency and adaptability of the CDGA. Finally, to optimize the evolutionary of CDGA,
we introduce roulette selection strategy to employ a probability assignment based on individual fitness values to guarantee the preferential selection of superior genes. A single-point crossover strategy is also used to introduce novel gene segments into the chromosomes, thus enhancing the genetic diversity of the population. Experiments verify the superiority of our CDGA.

## 2024/1215

* Title: Falsifiability, Composability, and Comparability of Game-based Security Models for Key Exchange Protocols
* Authors: Chris Brzuska, Cas Cremers, Håkon Jacobsen, Douglas Stebila, Bogdan Warinschi
* [Permalink](https://eprint.iacr.org/2024/1215)
* [Download](https://eprint.iacr.org/2024/1215.pdf)