[digest] 2024 Week 12

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



## 2024/461

* Title: Atlas-X Equity Financing: Unlocking New Methods to Securely Obfuscate Axe Inventory Data Based on Differential Privacy
* Authors: Antigoni Polychroniadou, Gabriele Cipriani, Richard Hua, Tucker Balch
* [Permalink](https://eprint.iacr.org/2024/461)
* [Download](https://eprint.iacr.org/2024/461.pdf)

### Abstract

Banks publish daily a list of available securities/assets (axe list) to selected clients to help them effectively locate Long (buy) or Short (sell) trades at reduced financing rates. This reduces costs for the bank, as the list aggregates the bank's internal firm inventory per asset for all clients of long as well as short trades. However, this is somewhat problematic: (1) the bank's inventory is revealed; (2) trades of clients who contribute to the aggregated list, particularly those deemed large, are revealed to other clients. Clients conducting sizable trades with the bank and possessing a portion of the aggregated asset exceeding $50\%$ are considered to be concentrated clients. This could potentially reveal a trading concentrated client's activity to their competitors, thus providing an unfair advantage over the market.


Atlas-X Axe Obfuscation, powered by new differential private methods, enables a bank to obfuscate its published axe list on a daily basis while under continual observation, thus maintaining an acceptable inventory Profit and Loss (P\&L) cost pertaining to the noisy obfuscated axe list while reducing the clients' trading activity leakage. Our main differential private innovation is a differential private aggregator for streams (time series data) of both positive and negative integers under continual observation.

For the last two years, Atlas-X system has been live in production across three major regions—USA, Europe, and Asia—at J.P. Morgan, a major financial institution, facilitating significant profitability. To our knowledge, it is the first differential privacy solution to be deployed in the financial sector. We also report benchmarks of our algorithm based on (anonymous) real and synthetic data to showcase the quality of our obfuscation and its success in production.



## 2024/462

* Title: Perfect Zero-Knowledge PCPs for #P
* Authors: Tom Gur, Jack O'Connor, Nicholas Spooner
* [Permalink](https://eprint.iacr.org/2024/462)
* [Download](https://eprint.iacr.org/2024/462.pdf)

### Abstract

We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP. Furthermore, unlike previous constructions of (statistical) zero-knowledge PCPs, our construction simultaneously achieves non-adaptivity and zero knowledge against arbitrary (adaptive) polynomial-time malicious verifiers.

    Our construction consists of a novel masked sumcheck PCP, which uses the combinatorial nullstellensatz to obtain antisymmetric structure within the hypercube and randomness outside of it.  To prove zero knowledge, we introduce the notion of locally simulatable encodings: randomised encodings in which every local view of the encoding can be efficiently sampled given a local view of the message. We show that the code arising from the sumcheck protocol (the Reed--Muller code augmented with subcube sums) admits a locally simulatable encoding. This reduces the algebraic problem of simulating our masked sumcheck to a combinatorial property of antisymmetric functions.



## 2024/463

* Title: Security Guidelines for Implementing Homomorphic Encryption
* Authors: Jean-Philippe Bossuat, Rosario Cammarota, Jung Hee Cheon, Ilaria Chillotti, Benjamin R. Curtis, Wei Dai, Huijing Gong, Erin Hales, Duhyeong Kim, Bryan Kumara, Changmin Lee, Xianhui Lu, Carsten Maple, Alberto Pedrouzo-Ulloa, Rachel Player, Luis Antonio Ruiz Lopez, Yongsoo Song, Donggeon Yhee, Bahattin Yildiz
* [Permalink](https://eprint.iacr.org/2024/463)
* [Download](https://eprint.iacr.org/2024/463.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a cryptographic primitive that allows performing arbitrary operations on encrypted data. Since the conception of the idea in [RAD78], it was considered a holy grail of cryptography. After the first construction in 2009 [Gen09], it has evolved to become a practical primitive with strong security guarantees. Most modern constructions are based on well-known lattice problems such as Learning with Errors (LWE). Besides its academic appeal, in recent years FHE has also attracted significant attention from industry, thanks to its applicability to a considerable number of real-world use-cases. An upcoming standardization effort by ISO/IEC aims to support the wider adoption of these techniques. However, one of the main challenges that standards bodies, developers, and end users usually encounter is establishing parameters. This is particularly hard in the case of FHE because the parameters are not only related to the security level of the system, but also to the type of operations that the system is able to handle. In this paper, we provide examples of parameter sets for LWE targeting particular security levels that can be used in the context of FHE constructions. We also give examples of complete FHE parameter sets, including the parameters relevant for correctness and performance, alongside those relevant for security. As an additional contribution, we survey the parameter selection support offered in open-source FHE libraries.



## 2024/464

* Title: ON THE IMPLEMENTATION OF A LATTICE-BASED DAA FOR VANET SYSTEM
* Authors: Doryan Lesaignoux, Mikael Carmona
* [Permalink](https://eprint.iacr.org/2024/464)
* [Download](https://eprint.iacr.org/2024/464.pdf)

### Abstract

Direct Anonymous Attestation (DAA) is a cryptographic protocol that enables users with a Trusted Platform Module (TPM) to authenticate without revealing their identity. Thus, DAA emerged as a good privacy-enhancing solution. Current standards have security based on factorization and discrete logarithm problem making them vulnerable to quantum computer attacks. Recently, a number of lattice-based DAA has been propose in the literature to start transition to quantum-resistant cryptography. In addition to these, DAA has been adapted to Vehicle Ad-hoc NETwork system (VANETs) to offer secure vehicule-to-vehicule/infrastructure communication (V2V and V2I).  In this paper, we provide an implementation of the most advanced post-quantum DAA for VANETs. We explore the cryptographic foundations, construction methodologies, and the performance of this scheme, offering insights into their suitability for various real-world use cases.



## 2024/465

* Title: Shorter VOLEitH Signature from Multivariate Quadratic
* Authors: Dung Bui
* [Permalink](https://eprint.iacr.org/2024/465)
* [Download](https://eprint.iacr.org/2024/465.pdf)

### Abstract

VOLE-in-the-head paradigm recently introduced by Baum et al. (Crypto 2023) allows transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on vector oblivious linear evaluation (VOLE) and leads to resulting ZK protocols that have linear proof size and are simpler, smaller, and faster than related approaches based on MPC-in-the-head.
We propose a new candidate post-quantum signature scheme from the Multivariate Quadratic(MQ) problem based on a new protocol for the VOLE-in-the-head paradigm, which significantly reduces the signature size compared to previous works. We achieve a signature size of 2.5KB for a 128-bit security level. Compared to the state-of-the-art MQ-based signature schemes, our signature scheme achieves a factor from 3 to 4 improvement in terms of the signature size while keeping the computational efficiency competitive



## 2024/466

* Title: Arctic: Lightweight and Stateless Threshold Schnorr Signatures
* Authors: Chelsea Komlo, Ian Goldberg
* [Permalink](https://eprint.iacr.org/2024/466)
* [Download](https://eprint.iacr.org/2024/466.pdf)

### Abstract

Threshold Schnorr signatures are seeing increased adoption in practice, and offer practical defenses against single points of failure. However, one challenge with existing randomized threshold Schnorr signature schemes is that signers must carefully maintain secret state across signing rounds, while also ensuring that state is deleted after a signing session is completed. Failure to do so will result in a fatal key-recovery attack by re-use of nonces.

While deterministic threshold Schnorr signatures that mitigate this issue exist in the literature, all prior schemes incur high complexity and performance overhead in comparison to their randomized equivalents. In this work, we seek the best of both worlds; a deterministic and stateless threshold Schnorr signature scheme that is also simple and efficient.

Towards this goal, we present Arctic, a lightweight two-round threshold Schnorr signature that is deterministic, and therefore does not require participants to maintain state between signing rounds. As a building block, we formalize the notion of a Verifiable Pseudorandom Secret Sharing (VPSS) scheme, and define Shine, an efficient VPSS construction. Shine is secure when the total number of participants is at least 2t − 1 and the adversary is assumed to corrupt at most t − 1; i.e., in the honest majority model.

We prove that Arctic is secure under the discrete logarithm assumption in the random oracle model, similarly assuming at minimum 2t − 1 number of signers and a corruption threshold of at most t − 1. For moderately sized groups (i.e., when n ≤ 20), Arctic is more than an order of magnitude more efficient than prior deterministic threshold Schnorr signatures in the literature. For small groups where n ≤ 10, Arctic is three orders of magnitude more efficient.



## 2024/467

* Title: Partially Non-Interactive Two-Round Lattice-Based Threshold Signatures
* Authors: Rutchathon Chairattana-Apirom, Stefano Tessaro, Chenzhi Zhu
* [Permalink](https://eprint.iacr.org/2024/467)
* [Download](https://eprint.iacr.org/2024/467.pdf)

### Abstract

This paper gives the first lattice-based two-round threshold signature based on lattice assumptions for which the first message is independent of the message being signed without relying on fully-homomorphic encryption. Our construction supports arbitrary thresholds and is scalable to support a large number of signers, say n = 1024.

Our construction provides a careful instantiation of a generic threshold signature construction by Tessaro and Zhu (EUROCRYPT ’23) based on specific linear hash functions, which in turns can be seen as a generalization of the FROST scheme by Komlo and Goldberg (SAC ’20). Our reduction techniques are new in the context of lattice-based cryptography. Also, our scheme does not use any heavy tools, such as NIZKs or homomorphic trapdoor commitments.



## 2024/468

* Title: Zero-Dimensional Gröbner Bases for Rescue-XLIX
* Authors: Matthias Johann Steiner
* [Permalink](https://eprint.iacr.org/2024/468)
* [Download](https://eprint.iacr.org/2024/468.pdf)

### Abstract

Rescue-XLIX is an Arithmetization-Oriented Substitution-Permutation Network over prime fields $\mathbb{F}_p$ which in one full round first applies a SPN based on $x \mapsto x^d$ followed by a SPN based on the inverse power map $x \mapsto x^\frac{1}{d}$. In a recent work, zero-dimensional Gröbner bases for SPN and Poseidon sponge functions have been constructed by utilizing weight orders. Following this approach we construct zero-dimensional Gröbner bases for Rescue-XLIX ciphers and sponge functions.



## 2024/469

* Title: Malicious Security for Sparse Private Histograms
* Authors: Lennart Braun, Adrià Gascón, Mariana Raykova, Phillipp Schoppmann, Karn Seth
* [Permalink](https://eprint.iacr.org/2024/469)
* [Download](https://eprint.iacr.org/2024/469.pdf)

### Abstract

We present a construction for secure computation of differentially private sparse histograms that aggregates the inputs from a large number of clients. Each client contributes a value to the aggregate at a specific index. We focus on the case where the set of possible indices is superpolynomially large. Hence, the resulting histogram will be sparse, i.e., most entries will have the value zero.

Our construction relies on two non-colluding servers and provides security against malicious adversaries that may control one of the servers and any numbers of clients. It achieves communication and computation complexities linear in the input size, and achieves the optimal error $O\big(\frac{\log(1/\delta)}{\epsilon}\big)$, independent of the size of the domain of indices. We compute the communication cost of our protocol, showing its scalability. For a billion clients, the communication cost for each server is under 26 KiB per client.

Our paper solves an open problem of the work of Bell et al. (CCS'22) which presented a solution for the semi-honest setting while incurring sublinear overhead in its efficiency. We formalize a proof approach for proving malicious security in settings where the output and possible additional information revealed during the execution need to provide differential privacy.



## 2024/470

* Title: Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
* Authors: Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, Damien Vergnaud
* [Permalink](https://eprint.iacr.org/2024/470)
* [Download](https://eprint.iacr.org/2024/470.pdf)

### Abstract

Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or shared using a threshold linear secret-sharing scheme. Our protocols terminate after a constant number of rounds and minimize the number of secure multiplications. In their seminal article at PKC 2006, Mohassel and Franklin proposed constant-rounds protocols for the main operations on (shared) polynomials. In this work, we improve the fan-in multiplication of nonzero polynomials, the multi-point polynomial evaluation and the polynomial interpolation (on secret points) to reach a quasi-linear complexity (instead of quadratic in Mohassel and Franklin's work) in the degree of shared input/output polynomials. Computing with shared polynomials is a core component of designing multi-party protocols for privacy-preserving operations on private sets, like private disjointness test or private set intersection. Using our new protocols, we are able to improve the complexity of such protocols and to design the first variant which always returns a correct result.



## 2024/471

* Title: Knot-based Key Exchange protocol
* Authors: Silvia Sconza, Arno Wildi
* [Permalink](https://eprint.iacr.org/2024/471)
* [Download](https://eprint.iacr.org/2024/471.pdf)

### Abstract

We propose a new key exchange protocol based on the Generalised Diffie-Hellman Key Exchange. In the latter, instead of using a group-action, we consider a semigroup action. In our proposal, the semigroup is the set of oriented knots in $\mathbb{S}^3$ with the operation of connected sum. As a semigroup action, we choose the action of the semigroup on itself through the connected sum. For the protocol to work, we need to use knot invariants, which allow us to create the shared secret key starting from the same knot represented in two different ways. In particular, we use finite type invariants. The security of the protocol is guaranteed by the hardness of decomposing knots in the semigroup.



## 2024/472

* Title: Sailfish: Towards Improving Latency of DAG-based BFT
* Authors: Nibesh Shrestha, Aniket Kate, Kartik Nayak
* [Permalink](https://eprint.iacr.org/2024/472)
* [Download](https://eprint.iacr.org/2024/472.pdf)

### Abstract

Existing DAG-based BFT protocols exhibit long latency to commit decisions. The primary reason for such a long latency is having a leader every 2 or more “rounds”. Even under honest leaders, these protocols require two or more reliable broadcast (RBC) instances to commit the proposal submitted by the leader (leader vertex), and additional RBCs to commit other proposals (non-leader vertices). In this work, we present Sailfish, the first DAG-based BFT that supports a leader vertex in each round. Under honest leaders, Sailfish maintains a commit latency of one RBC round plus $1\delta$ to commit the leader vertex (where $\delta$ is the actual transmission latency of a message) and only an additional RBC round to commit non-leader vertices.



## 2024/473

* Title: Extremely Simple Fail-Stop ECDSA Signatures
* Authors: Mario Yaksetig
* [Permalink](https://eprint.iacr.org/2024/473)
* [Download](https://eprint.iacr.org/2024/473.pdf)

### Abstract

Fail-stop signatures are digital signatures that allow a signer to prove that a specific forged signature is indeed a forgery. After such a proof is published, the system can be stopped.

We introduce a new simple ECDSA fail-stop signature scheme. Our proposal is based on the minimal assumption that an adversary with a quantum computer is not able to break the (second) preimage resistance of a cryptographically-secure hash function. Our scheme is as efficient as traditional ECDSA, does not limit the number of signatures that a signer can produce, and relies on minimal security assumptions. Using our construction, the signer has minimal computational overhead in the signature producing phase and produces a signature indistinguishable from a 'regular' ECDSA signature.



## 2024/474

* Title: Accumulation without Homomorphism
* Authors: Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, William Wang
* [Permalink](https://eprint.iacr.org/2024/474)
* [Download](https://eprint.iacr.org/2024/474.pdf)

### Abstract

Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions.
It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions.

In this paper, we answer this question affirmatively by constructing an accumulation scheme from *non-homomorphic* vector commitments which can be realized from solely symmetric-key assumptions (e.g. Merkle trees).
We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors.

Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps.
We show that such *bounded-depth* accumulation still suffices to construct proof-carrying data (a generalization of IVC).
We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.



## 2024/475

* Title: CheckOut: User-Controlled Anonymization for Customer Loyalty Programs
* Authors: Matthew Gregoire, Rachel Thomas, Saba Eskandarian
* [Permalink](https://eprint.iacr.org/2024/475)
* [Download](https://eprint.iacr.org/2024/475.pdf)

### Abstract

To resist the regimes of ubiquitous surveillance imposed upon us in every facet of modern life, we need technological tools that subvert surveillance systems. Unfortunately, while cryptographic tools frequently demonstrate how we can construct systems that safeguard user privacy, there is limited motivation for corporate entities engaged in surveillance to adopt these tools, as they often clash with profit incentives. This paper demonstrates how, in one particular aspect of everyday life -- customer loyalty programs -- users can subvert surveillance and attain anonymity, without necessitating any cooperation or modification in the behavior of their surveillors.

We present the CheckOut system, which allows users to coordinate large anonymity sets of shoppers to hide the identity and purchasing habits of each particular user in the crowd. CheckOut scales up and systematizes past efforts to subvert loyalty surveillance, which have been primarily ad-hoc and manual affairs where customers physically swap loyalty cards to mask their real identities. CheckOut allows increased scale while ensuring that the necessary computing infrastructure does not itself become a new centralized point of privacy failure.

Of particular importance to our scheme is a protocol for loyalty programs that offer reward points, where we demonstrate how CheckOut can assist users in paying each other back for loyalty points accrued while using each others' loyalty accounts. We present two different mechanisms to facilitate redistributing rewards points, offering trade-offs in functionality, performance, and security.



## 2024/476

* Title: OPSA: Efficient and Verifiable One-Pass Secure Aggregation with TEE for Federated Learning
* Authors: Zhangshuang Guan, Yulin Zhao, Zhiguo Wan, Jinsong Han
* [Permalink](https://eprint.iacr.org/2024/476)
* [Download](https://eprint.iacr.org/2024/476.pdf)

### Abstract

In federated learning, secure aggregation (SA) protocols like Flamingo (S\&P'23) and LERNA (ASIACRYPT'23) have achieved efficient multi-round SA in the malicious model. However, each round of their aggregation requires at least three client-server round-trip communications and lacks support for aggregation result verification. Verifiable SA schemes, such as VerSA (TDSC'21) and Eltaras et al.(TIFS'23), provide verifiable aggregation results under the security assumption that the server does not collude with any user. Nonetheless, these schemes incur high communication costs and lack support for efficient multi-round aggregation. Executing SA entirely within Trusted Execution Environment (TEE), as desined in SEAR (TDSC'22), guarantees both privacy and verifiable aggregation. However, the limited physical memory within TEE poses a significant computational bottleneck, particularly when aggregating large models or handling numerous clients.

In this work, we introduce OPSA, a multi-round one-pass secure aggregation framework based on TEE to achieve efficient communication, streamlined computation and verifiable aggregation all at once. OPSA employs a new strategy of revealing shared keys in TEE and instantiates two types of masking schemes. Furthermore, a result verification module is designed to be compatible with any type of SA protocol instantiated under the OPSA framework with weaker security assumptions. Compared with the state-of-the-art schemes, OPSA achieves a 2$\sim$10$\times$ speedup in multi-round aggregation while also supporting result verification simultaneously. OPSA is more friendly to scenarios with high network latency and large-scale model aggregation.



## 2024/477

* Title: Large Language Models for Blockchain Security: A Systematic Literature Review
* Authors: Zheyuan He, Zihao Li, Sen Yang
* [Permalink](https://eprint.iacr.org/2024/477)
* [Download](https://eprint.iacr.org/2024/477.pdf)

### Abstract

Large Language Models (LLMs) have emerged as powerful tools in various domains involving blockchain security (BS).  Several recent studies are exploring LLMs applied to BS. However, there remains a gap in our understanding regarding the full scope of applications, impacts, and potential constraints of LLMs on blockchain security. To fill this gap, we conduct a literature review on LLM4BS.

As the first review of LLM's application on blockchain security, our study aims to comprehensively analyze existing research and elucidate how LLMs contribute to enhancing the security of blockchain systems. Through a thorough examination of scholarly works, we delve into the integration of LLMs into various aspects of blockchain security.  We explore the mechanisms through which LLMs can bolster blockchain security, including their applications in smart contract auditing, identity verification, anomaly detection, vulnerable repair, and so on. Furthermore, we critically assess the challenges and limitations associated with leveraging LLMs for blockchain security, considering factors such as scalability, privacy concerns, and adversarial attacks. Our review sheds light on the opportunities and potential risks inherent in this convergence, providing valuable insights for researchers, practitioners, and policymakers alike.



## 2024/478

* Title: The Security of SHA2 under the Differential Fault Characteristic of Boolean Functions
* Authors: Weiqiong Cao, Hua Chen, Hongsong Shi, Haoyuan Li, Jian Wang, Jingyi Feng
* [Permalink](https://eprint.iacr.org/2024/478)
* [Download](https://eprint.iacr.org/2024/478.pdf)

### Abstract

SHA2 has been widely adopted across various traditional public-key cryptosystems, post-quantum cryptography, personal identification, and network communication protocols, etc. Hence, ensuring the robust security of SHA2 is of critical importance. There have been several differential fault attacks based on random word faults targeting SHA1 and SHACAL-2. However, extending such random word-based fault attacks to SHA2 proves significantly more difficult due to the heightened complexity of the boolean functions in SHA2.

In this paper, assuming random word faults, we find some distinctive differential properties within the boolean functions in SHA2. Leveraging these findings, we propose a new differential fault attack methodology that can be effectively utilized to recover the final message block and its corresponding initial vector in SHA2, forge HMAC-SHA2 messages, extract the key of SHACAL-2, and extend our analysis to similar algorithm like SM3. We validate the effectiveness of these attacks through rigorous simulations and theoretical deductions, revealing that they indeed pose substantial threats to the security of SHA2.. In our simulation-based experiments, our approach necessitates guessing $T$ bits within a register, with $T$ being no more than $5$ at most, and having a approximate $95\%$ (for SHA512) probability of guessing just $1$ bit. Moreover, upon implementing a consecutive series of 15 fault injections, the success probability for recovering one register (excluding the guessed bits) approaches $100\%$. Ultimately, approximately 928 faulty outputs based on random word faults are required to carry out the attack successfully.



## 2024/479

* Title: Making Hash-based MVBA Great Again
* Authors: Hanwen Feng, Zhenliang Lu, Tiancheng Mai, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/479)
* [Download](https://eprint.iacr.org/2024/479.pdf)

### Abstract

Multi-valued Validated Asynchronous Byzantine Agreement ($\mathsf{MVBA}$) is one essential primitive for many distributed protocols, such as asynchronous Byzantine fault-tolerant scenarios like atomic broadcast ($\mathsf{ABC}$), asynchronous distributed key generation, and many others.
Recent efforts (Lu et al, PODC' 20) have pushed the communication complexity of  $\mathsf{MVBA}$ to optimal $O(\ell n + \lambda n^2)$, which, however, heavily rely on ``heavyweight'' cryptographic tools, such as non-interactive threshold signatures. The computational cost of algebraic operations, the susceptibility to quantum attacks, and the necessity of a trusted setup associated with threshold signatures present significant remaining challenges. There is a growing interest in information-theoretic or hash-based constructions (historically called signature-free constructions). Unfortunately, the state-of-the-art hash-based $\mathsf{MVBA}$ (Duan et al., CCS'23) incurs a large $O(\ell n^2 + \lambda n^3)$-bits communication, which in turn makes the hash-based $\mathsf{MVBA}$inferior performance-wise comparing with the ``classical'' ones.. Indeed, this was clearly demonstrated in our experimental evaluations.

To make hash-based $\mathsf{MVBA}$ actually realize its full potential, in this paper, we introduce an $\mathsf{MVBA}$ with adaptive security,  and $\widetilde{O}(\ell n + \lambda n^2)$ communication, exclusively leveraging conventional hash functions. Our new $\mathsf{MVBA}$ achieves nearly optimal communication, devoid of heavy operations, surpassing both threshold signature-based schemes and the hash-based scheme in many practical settings, as demonstrated in our experiments. For example, in scenarios with a network size of $n = 201$ and an input size of $1.75$ MB, our $\mathsf{MVBA}$ exhibits a latency that is 81\% lower than that of the existing hash-based $\mathsf{MVBA}$ and 47\% lower than the threshold signature-based $\mathsf{MVBA}$. Our new construction also achieves optimal parameters in other metrics such as $O(1)$ rounds and $O(n^2)$ message complexity, except with a sub-optimal resilience, tolerating up to $20\%$ Byzantine corruptions (instead of $33\%$). Given its practical performance advantages, our new hash-based $\mathsf{MVBA}$ naturally leads to better asynchronous distributed protocols, by simply plugging it into existing frameworks.



## 2024/480

* Title: Folding-based zkLLM
* Authors: Wilbert W
* [Permalink](https://eprint.iacr.org/2024/480)
* [Download](https://eprint.iacr.org/2024/480.pdf)

### Abstract

This paper introduces a new approach to construct zero-knowledge large language models (zkLLM) based on the Folding technique. We first review the concept of Incrementally Verifiable Computation (IVC) and compare the IVC constructions based on SNARK and Folding. Then we discuss the necessity of Non-uniform IVC (NIVC) and present several Folding schemes that support more expressive circuits, such as SuperNova, Sangria, Origami, HyperNova, and Protostar. Based on these techniques, we propose a zkLLM design that uses a RAM machine architecture with a set of opcodes. We define corresponding constraint circuits for each opcode and describe the workflows of the prover and verifier. Finally, we provide examples of opcodes to demonstrate the circuit construction methods. Our zkLLM design achieves high efficiency and expressiveness, showing great potential for practical applications.



## 2024/481

* Title: Watermarkable and Zero-Knowledge Verifiable Delay Functions from any Proof of Exponentiation
* Authors: Charlotte Hoffmann, Krzysztof Pietrzak
* [Permalink](https://eprint.iacr.org/2024/481)
* [Download](https://eprint.iacr.org/2024/481.pdf)

### Abstract

A verifiable delay function $\texttt{VDF}(x,T)\rightarrow (y,\pi)$ maps an input $x$ and time parameter $T$ to an output $y$ together with an efficiently verifiable proof
$\pi$ certifying that $y$ was correctly computed. The function runs in $T$ sequential steps, and it should not be possible to compute $y$ much faster than that.  The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., $y=x^{2^T}$. There are two constructions for the proof of exponentiation (PoE) certifying that $y=x^{2^T}$, with Wesolowski (Eurocrypt'19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS'19).

A recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt'22) are short-lived proofs and signatures, which are proofs and signatures which are only sound for some time $t$, but after that can be forged by anyone. For this they rely on "watermarkable VDFs", where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on "zero-knowledge VDFs", where instead of the output $y$, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski's PoE, for the watermarkable VDFs there's currently no security proof.

In this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al.. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al's construction in several dimensions (faster forging times, weaker assumptions).

A key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for $y=x^{2^T}$, but instead give a (watermarked or zk) proof for the more basic statement that $x',y'$ satisfy $x'=x^r,y'=y^r$ for some $r$, together with a normal PoE for $y'=(x')^{2^T}$.