## In this issue

1. [2023/883] Prouff & Rivain’s Formal Security Proof of Masking, ...
2. [2024/456] Tight ZK CPU: Batched ZK Branching with Cost ...
3. [2024/457] Studying Lattice-Based Zero-Knowlege Proofs: A ...
4. [2024/458] Classical and Quantum Generic Attacks on 6-round ...
5. [2024/459] Isogeny problems with level structure
6. [2024/460] Encrypted Image Classification with Low Memory ...
7. [2024/461] Atlas-X Equity Financing: Unlocking New Methods to ...
8. [2024/462] Perfect Zero-Knowledge PCPs for #P
9. [2024/463] Security Guidelines for Implementing Homomorphic ...
10. [2024/464] ON THE IMPLEMENTATION OF A LATTICE-BASED DAA FOR ...
11. [2024/465] Shorter VOLEitH Signature from Multivariate Quadratic
12. [2024/466] Arctic: Lightweight and Stateless Threshold Schnorr ...
13. [2024/467] Partially Non-Interactive Two-Round Lattice-Based ...
14. [2024/468] Zero-Dimensional Gröbner Bases for Rescue-XLIX
15. [2024/469] Malicious Security for Sparse Private Histograms
16. [2024/470] Fast Secure Computations on Shared Polynomials and ...
17. [2024/471] Knot-based Key Exchange protocol
18. [2024/472] Sailfish: Towards Improving Latency of DAG-based BFT
19. [2024/473] Extremely Simple Fail-Stop ECDSA Signatures
20. [2024/474] Accumulation without Homomorphism
21. [2024/475] CheckOut: User-Controlled Anonymization for ...
22. [2024/476] OPSA: Efficient and Verifiable One-Pass Secure ...
23. [2024/477] Large Language Models for Blockchain Security: A ...
24. [2024/478] The Security of SHA2 under the Differential Fault ...
25. [2024/479] Making Hash-based MVBA Great Again
26. [2024/480] Folding-based zkLLM
27. [2024/481] Watermarkable and Zero-Knowledge Verifiable Delay ...

## 2023/883

* Title: Prouff & Rivain’s Formal Security Proof of Masking, Revisited: Tight Bounds in the Noisy Leakage Model
* Authors: Loïc Masure, François-Xavier Standaert
* [Permalink](https://eprint.iacr.org/2023/883)
* [Download](https://eprint.iacr.org/2023/883.pdf)

### Abstract

Masking is a counter-measure that can be incorporated to
software and hardware implementations of block ciphers to provably se-
cure them against side-channel attacks. The security of masking can be
proven in different types of threat models. In this paper, we are interested
in directly proving the security in the most realistic threat model, the
so-called noisy leakage adversary, that captures well how real-world side-
channel adversaries operate. Direct proofs in this leakage model have
been established by Prouff & Rivain at Eurocrypt 2013, Dziembowski
et al. at Eurocrypt 2015, and Prest et al. at Crypto 2019. Both proofs
are complementary to each other, in the sense that the weaknesses of one
proof are fixed in at least one of the others, and conversely. These weak-
nesses concerned in particular the strong requirements on the noise level
and the security parameter to get meaningful security bounds, and some
requirements on the type of adversary covered by the proof — i.e., cho-
sen or random plaintexts. This suggested that the drawbacks of each
security bound could actually be proof artifacts. In this paper, we solve
these issues, by revisiting Prouff & Rivain’s approach.

## 2024/456

* Title: Tight ZK CPU: Batched ZK Branching with Cost Proportional to Evaluated Instruction
* Authors: Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, Muthuramakrishnan Venkitasubramaniam
* [Permalink](https://eprint.iacr.org/2024/456)
* [Download](https://eprint.iacr.org/2024/456.pdf)

### Abstract

We explore Zero-Knowledge proofs (ZKP) of statements expressed as programs written in high-level languages, e.g., C or assembly. At the core of executing such programs in ZK is the repeated evaluation of a CPU step, achieved by branching over the CPU’s instruction set. This approach is general and covers traversal-execution of a program’s control flow graph (CFG): here CPU instructions are straight-line program fragments (of various sizes) associated with the CFG nodes. This highlights the usefulness of ZK CPUs with a large number of instructions of varying sizes.

We formalize and design an efficient tight ZK CPU, where the cost (both computation and communication, for each party) of each step depends only on the instruction taken. This qualitatively improves over state-of-the-art, where cost scales with the size of the largest CPU instruction (largest CFG node).

Our technique is formalized in the standard commit-and-prove paradigm, so our results are compatible with a variety of (interactive and non-interactive) general-purpose ZK.

We implemented an interactive tight arithmetic (over $\mathbb{F}_{2^{61}-1}$) ZK CPU based on Vector Oblivious Linear Evaluation (VOLE) and compared it to the state-of-the-art non-tight VOLE-based ZK CPU Batchman (Yang et al. CCS’23). In our experiments, under the same hardware configuration, we achieve comparable performance when instructions are of the same size and a $5$-$18×$ improvement when instructions are of varied size. Our VOLE-based ZK CPU can execute $100$K (resp. $450$K) multiplication gates per second in a WAN-like (resp. LAN-like) setting. It requires ≤ $102$ Bytes per multiplication gate. Our basic building block, ZK Unbalanced Read-Only Memory (ZK UROM), may be of an independent interest.

## 2024/457

* Title: Studying Lattice-Based Zero-Knowlege Proofs: A Tutorial and an Implementation of Lantern
* Authors: Lena Heimberger, Florian Lugstein, Christian Rechberger
* [Permalink](https://eprint.iacr.org/2024/457)
* [Download](https://eprint.iacr.org/2024/457.pdf)

### Abstract

Lattice-based cryptography has emerged as a promising new candidate to build cryptographic primitives. It offers resilience against quantum attacks, enables fully homomorphic encryption, and relies on robust theoretical foundations.. Zero-knowledge proofs (ZKPs) are an essential primitive for various privacy-preserving applications. For example, anonymous credentials, group signatures, and verifiable oblivious pseudorandom functions all require ZKPs. Currently, the majority of ZKP systems are based on elliptic curves, which are susceptible to attacks from quantum computers. This project presents the first implementation of Lantern, a state-of-the-art lattice-based ZKP system that can create compact proofs, which are a few dozen kilobytes large, for basic statements. We thoroughly explain the theory behind the scheme and give a full implementation in a Jupyter Notebook using SageMath to make Lantern more accessible to researchers. Our interactive implementation allows users to fully understand the scheme and its building blocks, providing a valuable resource to understand both ZKPs and lattice cryptography. Albeit not optimized for performance, this implementation allows us to construct a Module-LWE secret proof in 35s on a consumer laptop. Through our contributions, we aim to advance the understanding and practical utilization of lattice-based ZKP systems, particularly emphasizing accessibility for the broader research community.

## 2024/458

* Title: Classical and Quantum Generic Attacks on 6-round Feistel Schemes
* Authors: Maya Chartouny, Benoit Cogliati, Jacques Patarin
* [Permalink](https://eprint.iacr.org/2024/458)
* [Download](https://eprint.iacr.org/2024/458.pdf)

### Abstract

In this paper, we describe new quantum generic attacks on 6 rounds balanced Feistel networks with internal functions or internal permutations. In order to obtain our new quantum attacks, we revisit a result of Childs and Eisenberg that extends Ambainis' collision finding algorithm to the subset finding problem. In more details, we continue their work by carefully analyzing the time complexity of their algorithm. We also use four points structures attacks instead of two points structures attacks that leads to a complexity of $\mathcal{O}(2^{8n/5})$ instead of $\mathcal{O}(2^{2n})$. Moreover, we have also found a classical (i.e. non quantum) improved attack on $6$ rounds with internal permutations. The complexity here will be in $\mathcal{O}(2^{2n})$ instead of $\mathcal{O}(2^{3n})$ previously known.

## 2024/459

* Title: Isogeny problems with level structure
* Authors: Luca De Feo, Tako Boris Fouotsa, Lorenz Panny
* [Permalink](https://eprint.iacr.org/2024/459)
* [Download](https://eprint.iacr.org/2024/459.pdf)

### Abstract

Given two elliptic curves and the degree of an isogeny between them, finding the isogeny is believed to be a difficult problem---upon which rests the security of nearly any isogeny-based scheme. If, however, to the data above we add information about the behavior of the isogeny on a large enough subgroup, the problem can become easy, as recent cryptanalyses on SIDH have shown.
Between the restriction of the isogeny to a full $N$-torsion subgroup and no ''torsion information'' at all lies a spectrum of interesting intermediate problems, raising the question of how easy or hard each of them is. Here we explore modular isogeny problems where the torsion information is masked by the action of a group of $2\times 2$ matrices. We give reductions between these problems, classify them by their difficulty, and link them to security assumptions found in the literature.

## 2024/460

* Title: Encrypted Image Classification with Low Memory Footprint using Fully Homomorphic Encryption
* Authors: Lorenzo Rovida, Alberto Leporati
* [Permalink](https://eprint.iacr.org/2024/460)
* [Download](https://eprint.iacr.org/2024/460.pdf)

### Abstract

Classifying images has become a straightforward and accessible task, thanks to the advent of Deep Neural Networks. Nevertheless, not much attention is given to the privacy concerns associated with sensitive data contained in images.. In this study, we propose a solution to this issue by exploring an intersection between Machine Learning and cryptography.
In particular, Fully Homomorphic Encryption (FHE) emerges as a promising solution, as it enables computations to be performed on encrypted data. We, therefore, propose a Residual Network implementation based on FHE which allows the classification of encrypted images, ensuring that only the user can see the result.
We suggest a circuit which reduces the memory requirements by more than 85% compared to the most recent works, while maintaining a high level of accuracy and a short computational time. We implement the circuit using the well-known CKKS scheme, which enables approximate encrypted computations.
We evaluate the results from three perspectives: memory requirements, computational time and calculations precision. We demonstrate that it is possible to evaluate an encrypted ResNet20 in less than five minutes on a laptop using approximately 15GB of memory, achieving an accuracy of 91.67% on the CIFAR-10 dataset, which is almost equivalent to the accuracy of the plain model (92.60%).