[digest] 2024 Week 6

[IACR ePrint Archive]

## In this issue

1. [2023/807] Ready to SQI? Safety First! Towards a constant-time ...
2. [2024/163] On Tweakable Correlation Robust Hashing against Key ...
3. [2024/164] Faster BGV Bootstrapping for Power-of-Two ...
4. [2024/165] Adaptively-Sound Succinct Arguments for NP from ...
5. [2024/166] A Practical MinRank Attack Against VOX
6. [2024/167] Creating from Noise: Trace Generations Using ...
7. [2024/168] Breaking the Cubic Barrier: Distributed Key and ...
8. [2024/169] Machine Learning based Blind Side-Channel Attacks ...
9. [2024/170] Train Wisely: Multifidelity Bayesian Optimization ...
10. [2024/171] Approximate Methods for the Computation of Step ...
11. [2024/172] Relaxed Functional Bootstrapping: A New Perspective ...
12. [2024/173] Constant-Size zk-SNARKs in ROM from Falsifiable ...
13. [2024/174] QPP and HPPK: Unifying Non-Commutativity for ...
14. [2024/175] Lossy Cryptography from Code-Based Assumptions
15. [2024/176] The impact of data-heavy, post-quantum TLS 1.3 on ...
16. [2024/177] Registered Functional Encryption for Quadratic ...
17. [2024/178] Fast Public-Key Silent OT and More from Constrained ...
18. [2024/179] Traitor Tracing without Trusted Authority from ...
19. [2024/180] Exploiting RPMB authentication in a closed source ...
20. [2024/181] Functional Bootstrapping for FV-style Cryptosystems
21. [2024/182] FileDES: A Secure, Scalable and Succinct ...
22. [2024/183] On Security Proofs of Existing Equivalence Class ...
23. [2024/184] Threshold Raccoon: Practical Threshold Signatures ...
24. [2024/185] Vortex: A List Polynomial Commitment and its ...
25. [2024/186] RAD-FS - Inherent and Embedded SCA-Security in ...
26. [2024/187] On the bijectivity of the map $\chi$
27. [2024/188] HomeRun: High-efficiency Oblivious Message ...
28. [2024/189] ZeroAuction: Zero-Deposit Sealed-bid Auction via ...
29. [2024/190] Constructing Committing and Leakage-Resilient ...
30. [2024/191] A Simpler and More Efficient Reduction of DLog to ...
31. [2024/192] Direct FSS Constructions for Branching Programs and ...
32. [2024/193] MQ Does Not Reduce to TUOV
33. [2024/194] Helium: Scalable MPC among Lightweight Participants ...
34. [2024/195] PQC-AMX: Accelerating Saber and FrodoKEM on the ...
35. [2024/196] Subfield attack: leveraging composite-degree ...
36. [2024/197] Alba: The Dawn of Scalable Bridges for Blockchains
37. [2024/198] Distributed Randomness using Weighted VRFs
38. [2024/199] Formal Security Proofs via Doeblin Coefficients: ...
39. [2024/200] A Better Proof-of-Work Fork Choice Rule
40. [2024/201] Breaking the decisional Diffie-Hellman problem in ...
41. [2024/202] Fully Homomorphic Encryption beyond IND-CCA1 ...
42. [2024/203] Application-Aware Approximate Homomorphic ...
43. [2024/204] PerfOMR: Oblivious Message Retrieval with Reduced ...
44. [2024/205] A Generalized Distributed RSA Key Generation
45. [2024/206] Kronos: A Robust Sharding Blockchain Consensus with ...
46. [2024/207] NIZKs with Maliciously Chosen CRS: Subversion ...
47. [2024/208] Asymmetric Cryptography from Number Theoretic ...
48. [2024/209] General Adversary Structures in Byzantine Agreement ...
49. [2024/210] Rollerblade: Replicated Distributed Protocol ...

## 2023/807

* Title: Ready to SQI? Safety First! Towards a constant-time implementation of isogeny-based signature, SQIsign
* Authors: David Jacquemin, Anisha Mukherjee, Péter Kutas, Sujoy SINHA ROY
* [Permalink](https://eprint.iacr.org/2023/807)
* [Download](https://eprint.iacr.org/2023/807.pdf)

### Abstract

NIST has already published the first round of submissions for additional post-quantum signature schemes and the only isogeny-based candidate is SQIsign. It boasts the
most compact key and signature sizes among all post-quantum signature schemes.
However, its current implementation does not address side-channel resistance. This
work is the first to identify a potential side-channel vulnerability in SQIsign. At
certain steps within the signing procedure, it relies on Cornacchia’s algorithm to
represent an integer as a sum of squares of two integers. This algorithm in turn uses
a ‘half-GCD’ (half-greatest common divisor) sub-routine based on Euclid’s division
algorithm which has often been exploited for side-channel attacks. We show that if
the inputs of Cornacchia’s algorithm leak, then one can retrieve the signing key in
polynomial time. Also, since there is no constant-time implementation for SQIsign,
we propose two timing attack-resistant versions of Cornacchia’s algorithm. The
first version uses a constant-time ‘half-GCD’ algorithm that runs a fixed number
of times for a given upper bound based on the bit-size of the inputs. The second
version is based on the two-dimensional lattice reduction algorithm. We show that
randomizing the starting basis with an unimodular matrix would make the execution
time independent of the input.



## 2024/163

* Title: On Tweakable Correlation Robust Hashing against Key Leakages
* Authors: Chun Guo, Xiao Wang, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/163)
* [Download](https://eprint.iacr.org/2024/163.pdf)

### Abstract

We continue the study of blockcipher-based (tweakable) correlation robust hash functions, which are central building blocks of circuit garbling and oblivious-transfer extension schemes. As results, we first enhance the multi-user tweakable correlation robust notion of Guo et al. (CRYPTO 2020) with a {\it key leaking oracle} that tells the adversary whether a certain user key satisfies the adversarially-chosen predicate. We then investigate the state-of-the-art hash construction of Guo et al. with respect to our new security definition, providing security proof as well as matching attacks. As an application, we exhibit an OT extension protocol with non-trivial multi-user security.



## 2024/164

* Title: Faster BGV Bootstrapping for Power-of-Two Cyclotomics through Homomorphic NTT
* Authors: Shihe Ma, Tairong Huang, Anyu Wang, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2024/164)
* [Download](https://eprint.iacr.org/2024/164.pdf)

### Abstract

Power-of-two cyclotomics is a popular choice when instantiating the BGV scheme because of its efficiency and compliance with the FHE standard. However, in power-of-two cyclotomics, the linear transformations in BGV bootstrapping cannot be decomposed into sub-transformations for acceleration with existing techniques. Thus, they can be highly time-consuming when the number of slots is large, degrading the advantage brought by the SIMD property of the plaintext space. By exploiting the algebraic structure of power-of-two cyclotomics, this paper derives explicit decomposition of the linear transformations in BGV bootstrapping into NTT-like sub-transformations, which are highly efficient to compute homomorphically. Moreover, multiple optimizations are made to evaluate homomorphic linear transformations, including modified BSGS algorithms, trade-offs between level and time, and specific simplifications for thin and general bootstrapping. We implement our method on HElib. With the number of slots ranging from 4096 to 32768, we obtain a 7.35x$\sim$143x improvement in the running time of linear transformations and a 4.79x$\sim$66.4x improvement in bootstrapping throughput, compared to previous works or the naive approach.



## 2024/165

* Title: Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
* Authors: Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/165)
* [Download](https://eprint.iacr.org/2024/165.pdf)

### Abstract

A succinct non-interactive argument (SNARG) for $\mathsf{NP}$ allows a prover to convince a verifier that an $\mathsf{NP}$ statement $x$ is true with a proof of size $o(|x| + |w|)$, where $w$ is the associated $\mathsf{NP}$ witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for $\mathsf{NP}$ in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions, and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for $\mathsf{NP}$ from falsifiable assumptions. All previous SNARGs for $\mathsf{NP}$ in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).



## 2024/166

* Title: A Practical MinRank Attack Against VOX
* Authors: Hao Guo, Jintai Ding
* [Permalink](https://eprint.iacr.org/2024/166)
* [Download](https://eprint.iacr.org/2024/166.pdf)

### Abstract

VOX is a UOV-like signature scheme submitted to Round 1 additional signatures of NIST PQC standardization process. In 2023 Furue and Ikematsu proposed a rectangular MinRank attack on VOX, resulting in the submitters changing their parameters to counter this attack. In this paper we propose a new type of MinRank attack called padded MinRank attack. We show that the attack is highly efficient in its running time, taking less than one minute to break eight of nine parameters and about eight hours for the remaining one. Therefore the parameters of VOX should be reexamined to ensure its safety.



## 2024/167

* Title: Creating from Noise: Trace Generations Using Diffusion Model for Side-Channel Attack
* Authors: Trevor Yap, Dirmanto Jap
* [Permalink](https://eprint.iacr.org/2024/167)
* [Download](https://eprint.iacr.org/2024/167.pdf)

### Abstract

In side-channel analysis (SCA), the success of an attack is largely dependent on the dataset sizes and the number of instances in each class. The generation of synthetic traces can help to improve attacks like profiling attacks.
However, manually creating synthetic traces from actual traces is arduous. Therefore, automating this process of creating artificial traces is much needed.
Recently, diffusion models have gained much recognition after beating another generative model known as Generative Adversarial Networks (GANs) in creating realistic images. We explore the usage of diffusion models in the domain of SCA. We proposed frameworks for a known mask setting and unknown mask setting in which the diffusion models could be applied. Under a known mask setting, we show that the traces generated under the proposed framework preserved the original leakage. Next, we demonstrated that the artificially created profiling data in the unknown mask setting can reduce the required attack traces for a profiling attack. This suggests that the artificially created profiling data from the trained diffusion model contains useful leakages to be exploited.



## 2024/168

* Title: Breaking the Cubic Barrier: Distributed Key and Randomness Generation through Deterministic Sharding
* Authors: Hanwen Feng, Zhenliang Lu, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/168)
* [Download](https://eprint.iacr.org/2024/168.pdf)

### Abstract

There are long line of researches on the fundamental distributed key generation (DKG) protocols. Unfortunately, all of them suffer from a large cubic total communication, due to the fact that $O(n)$ participants need to {\em broadcast} to all $n$ participants.

We introduce the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring $\widetilde{\mathcal{O}}(n^{2.5}\lambda)$ total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element. This property makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. Additionally, both DKG protocols straightforwardly imply an improved (single-shot) common coin protocol.

At the core of our techniques, we develop a simple-yet-effective methodology via deterministic sharding that arbitrarily groups nodes into shards;
and a new primitive called consortium-dealer secret sharing, to enable a shard of nodes to securely contribute a secret to the whole population only at the cost of one-dealer. We also formalize simulation-based security for publicly verifiable secret sharing (PVSS), making it possible for a modular analysis for DKG. Those might be of independent interest.



## 2024/169

* Title: Machine Learning based Blind Side-Channel Attacks on PQC-based KEMs - A Case Study of Kyber KEM
* Authors: Prasanna Ravi, Dirmanto Jap, Shivam Bhasin, Anupam Chattopadhyay
* [Permalink](https://eprint.iacr.org/2024/169)
* [Download](https://eprint.iacr.org/2024/169.pdf)

### Abstract

Kyber KEM, the NIST selected PQC standard for Public Key Encryption and Key Encapsulation Mechanisms (KEMs) has been subjected to a variety of side-channel attacks, through the course of the NIST PQC standardization process. However, all these attacks targeting the decapsulation procedure of Kyber KEM either require knowledge of the ciphertexts or require to control the value of ciphertexts for key recovery. However, there are no known attacks in a blind setting, where the attacker does not have access to the ciphertexts. While blind side-channel attacks are known for symmetric key cryptographic schemes, we are not aware of such attacks for Kyber KEM. In this paper, we fill this gap by proposing the first blind side-channel attack on Kyber KEM. We target leakage of the pointwise multiplication operation in the decryption procedure to carry out practical blind side-channel attacks resulting in full key recovery. We perform practical validation of our attack using power side-channel from the reference implementation of Kyber KEM taken from the pqm4 library, implemented on the ARM Cortex-M4 microcontroller. Our experiments clearly indicate the feasibility of our proposed attack in recovering the full key in only a few hundred to few thousand traces, in the presence of a suitably accurate Hamming Weight (HW) classifier.



## 2024/170

* Title: Train Wisely: Multifidelity Bayesian Optimization Hyperparameter Tuning in Side-Channel Analysis
* Authors: Trevor Yap Hong Eng, Shivam Bhasin, Léo Weissbart
* [Permalink](https://eprint.iacr.org/2024/170)
* [Download](https://eprint.iacr.org/2024/170.pdf)

### Abstract

Side-Channel Analysis (SCA) is critical in evaluating the security of cryptographic implementations. The search for hyperparameters poses a significant challenge, especially when resources are limited. In this work, we explore the efficacy of a multifidelity optimization technique known as BOHB in SCA. In addition, we proposed a new objective function called $ge_{+ntge}$, which could be incorporated into any Bayesian Optimization used in SCA. We show the capabilities of both BOHB and $ge_{+ntge}$ on four different public datasets. Specifically, BOHB could obtain the least number of traces in CTF2018 when trained in the Hamming weight and identity leakage model. Notably, this marks the first reported successful recovery of the key for the identity leakage model in CTF2018.



## 2024/171

* Title: Approximate Methods for the Computation of Step Functions in Homomorphic Encryption
* Authors: Tairong Huang, Shihe Ma, Anyu Wang, XiaoYun Wang
* [Permalink](https://eprint.iacr.org/2024/171)
* [Download](https://eprint.iacr.org/2024/171.pdf)

### Abstract

The computation of step functions over encrypted data is an essential issue in homomorphic encryption due to its fundamental application in privacy-preserving computing. However, an effective method for homomorphically computing general step functions remains elusive in cryptography. This paper proposes two polynomial approximation methods for general step functions to tackle this problem. The first method leverages the fact that any step function can be expressed as a linear combination of shifted sign functions. This connection enables the homomorphic evaluation of any step function using known polynomial approximations of the sign function. The second method boosts computational efficiency by employing a composite polynomial approximation strategy. We present a systematic approach to construct a composite polynomial $f_k \circ f_{k-1} \circ \cdots \circ f_1$ that increasingly approximates the step function as $k$ increases. This method utilizes an adaptive linear programming approach that we developed to optimize the approximation effect of $f_i$ while maintaining the degree and coefficients bounded. We demonstrate the effectiveness of these two methods by applying them to typical step functions such as the round function and encrypted data bucketing, implemented in the HEAAN homomorphic encryption library. Experimental results validate that our methods can effectively address the homomorphic computation of step functions.



## 2024/172

* Title: Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping
* Authors: Zeyu Liu, Yunhao Wang
* [Permalink](https://eprint.iacr.org/2024/172)
* [Download](https://eprint.iacr.org/2024/172.pdf)

### Abstract

BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes, supporting evaluations over a finite field. To evaluate a circuit with arbitrary depth, bootstrapping is needed. However, despite the recent progress, bootstrapping of BGV/BFV still remains relatively impractical, compared to other FHE schemes.

In this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself.

Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1-2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function.

Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for batched binary gate bootstrapping and a plaintext-space-dependent speed-up for batched functional bootstrapping with plaintext space smaller than $\mathbb{Z}_{512}$.



## 2024/173

* Title: Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions
* Authors: Helger Lipmaa, Roberto Parisella, Janno Siim
* [Permalink](https://eprint.iacr.org/2024/173)
* [Download](https://eprint.iacr.org/2024/173.pdf)

### Abstract

We prove that the seminal KZG polynomial commitment scheme (PCS) is black-box extractable under a simple falsifiable assumption ARSDH. To create an interactive argument, we construct a compiler that combines a black-box extractable non-interactive PCS and a polynomial IOP (PIOP). The compiler incurs a minor cost per every committed polynomial. Applying the Fiat-Shamir transformation, we obtain slightly less efficient variants of well-known PIOP-based zk-SNARKs, such as Plonk, that are knowledge-sound in the ROM under the ARSDH assumption. Importantly, there is no need for idealized group models or knowledge assumptions. This results in the first known zk-SNARKs in the ROM from falsifiable assumptions with both an efficient prover and constant-size argument.



## 2024/174

* Title: QPP and HPPK: Unifying Non-Commutativity for Quantum-Secure Cryptography with Galois Permutation Group
* Authors: Randy Kuang
* [Permalink](https://eprint.iacr.org/2024/174)
* [Download](https://eprint.iacr.org/2024/174.pdf)

### Abstract

In response to the evolving landscape of quantum computing and the heightened vulnerabilities in classical cryptographic systems, our paper introduces a comprehensive cryptographic framework. Building upon the pioneering work of Kuang et al., we present a unification of two innovative primitives: the Quantum Permutation Pad (QPP) for symmetric key encryption and the Homomorphic Polynomial Public Key (HPPK) for Key Encapsulation Mechanism (KEM) and Digital Signatures (DS). By harnessing matrix representations of the Galois Permutation Group and inheriting its bijective and non-commutative properties, QPP achieves quantum-secure symmetric key encryption, seamlessly extending Shannon’s perfect secrecy to both classical and quantum-native systems. Simultaneously, HPPK, free of NP-hard problems, relies on the security of symmetric encryption for the plain public key. This is accomplished by concealing the mathematical structure through arithmetic representations or modular multiplicative operators (arithmetic QPP) of the Galois Permutation Group over hidden rings, utilizing their partial homomorphic properties. This ensures secure computation on encrypted data during secret encapsulations, thereby enhancing the security of the plain public key. The integration of KEM and DS within HPPK cryptography results in compact key, cipher, and signature sizes, showcasing exceptional performance. This paper organically unifies QPP and HPPK under the Galois Permutation Group, marking a significant advance in laying the groundwork for quantum-resistant cryptographic protocols. Our contribution propels the development of secure communication systems in the era of quantum computing.



## 2024/175

* Title: Lossy Cryptography from Code-Based Assumptions
* Authors: Quang Dao, Aayush Jain
* [Permalink](https://eprint.iacr.org/2024/175)
* [Download](https://eprint.iacr.org/2024/175.pdf)

### Abstract

Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class $\mathcal{SZK}$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $\mathcal{BPP}^{\mathcal{SZK}}$. This poses a barrier for building advanced primitives from code-based assumptions, as the only known such assumption is Learning Parity with Noise (LPN) with an extremely low noise rate $\frac{\log^2 n}{n}$, which is broken in quasi-polynomial time.

In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class $\mathcal{BPP}^{\mathcal{SZK}}$ and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece's cryptosystem and random $k\mbox{-}$XOR in average-case complexity. Roughly, the assumption states that
\[(\mathbf{T}\, \mathbf{M}, \mathbf{s} \,\mathbf{T}\, \mathbf{M} + \mathbf{e}) \quad \text{is indistinguishable from}\quad (\mathbf{T} \,\mathbf{M}, \mathbf{u}),\] for a random (dense) matrix $\mathbf{T}$, random sparse matrix $\mathbf{M}$, and sparse noise vector $\mathbf{e}$ drawn from the Bernoulli distribution with inverse polynomial noise probability.

We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate $\frac{\log^2 n}{n}$ that is only quasi-polynomially secure.



## 2024/176

* Title: The impact of data-heavy, post-quantum TLS 1.3 on the Time-To-Last-Byte of real-world connections
* Authors: Panos Kampanakis, Will Childs-Klein
* [Permalink](https://eprint.iacr.org/2024/176)
* [Download](https://eprint.iacr.org/2024/176.pdf)

### Abstract

It has been shown that post-quantum key exchange and authentication with ML-KEM and ML-DSA, NIST’s postquantum algorithm picks, will have an impact on TLS 1.3 performance used in the Web or other applications. Studies so far have focused on the overhead of quantum-resistant algorithms on TLS time-to-first-byte (handshake time). Although these works have been important in quantifying the slowdown in connection establishment, they do not capture the full picture regarding real-world TLS 1.3 connections which carry sizable amounts of data. Intuitively, the introduction of an extra 10KB of ML-KEM and ML-DSA exchanges in the connection negotiation will inflate the connection establishment time proportionally more than it will increase the total connection time of a Web connection carrying 200KB of data. In this work, we quantify the impact of ML-KEM and ML-DSA on typical TLS 1.3 connections which transfer a few hundreds of KB from the server to the client. We study the slowdown in the time-to-last-byte of postquantum connections under normal network conditions and in more unstable environments with high packet delay variability and loss probabilities. We show that the impact of ML-KEM and ML-DSA on the TLS 1.3 time-to-last-byte under stable network conditions is lower than the impact on the time-to-first-byte and diminishes as the transferred data increases. The time-to-last-byte increase stays below 5% for high-bandwidth, stable networks. It goes from 32% increase of the time-to-first-byte to under 15% increase of the time-to-last-byte when transferring 50KiB of data or more under low-bandwidth, stable network conditions. Even when congestion control affects connection establishment, the additional slowdown drops below 10% as the connection data increases to 200KiB. We also show that connections under lossy or volatile network conditions could see higher impact from post-quantum handshakes, but these connections’ time-to-lastbyte increase still drops as the transferred data increases. Finally, we show that such connections are already significantly slow and volatile regardless of the TLS handshake.



## 2024/177

* Title: Registered Functional Encryption for Quadratic Functions from MDDH
* Authors: Qiaohan Chu, Li Lin, Chen Qian, Jie Chen
* [Permalink](https://eprint.iacr.org/2024/177)
* [Download](https://eprint.iacr.org/2024/177.pdf)

### Abstract

We present a Registered Functional Encryption (RFE) scheme for inner product and a RFE scheme for quadratic functions based on pairings and relying on the Matrix Decision Diffie-Hellman (MDDH) assumption and bilateral MDDH assumption. Previously, RFE is only known to be constructed from indistinguishability obfuscation (iO) in Francati-Friolo-Maitra-Malavolta-Rahimi-Venturi [Asiacrypt '23].



## 2024/178

* Title: Fast Public-Key Silent OT and More from Constrained Naor-Reingold
* Authors: Dung Bui, Geoffroy Couteau, Pierre Meyer, Alain Passelègue, Mahshid Riahinia
* [Permalink](https://eprint.iacr.org/2024/178)
* [Download](https://eprint.iacr.org/2024/178.pdf)

### Abstract

Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols.
In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient public-key PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other party's public key.
In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-Passelègue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15k-40k OT/s, which is of a similar order of magnitude to the state-of-the-art interactive PCFs and about 4 orders of magnitude faster than state-of-the-art public-key PCFs.
As a side result, we also show that public-key PCFs can serve as a building block to construct reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZK) for NP. Combined with our instantiations, this yields simple and efficient reusable DV-NIZKs for NP in pairing-free groups.



## 2024/179

* Title: Traitor Tracing without Trusted Authority from Registered Functional Encryption
* Authors: Pedro Branco, Russell W. F. Lai, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2024/179)
* [Download](https://eprint.iacr.org/2024/179.pdf)

### Abstract

Traitor-tracing systems allow identifying the users who contributed to building a rogue decoder in a broadcast environment. In a traditional traitor-tracing system, a key authority is responsible for generating the global public parameters and issuing secret keys to users. All security is lost if the \emph{key authority itself} is corrupt. This raises the question: Can we construct a traitor-tracing scheme, without a trusted authority?

In this work, we propose a new model for traitor-tracing systems where, instead of having a key authority, users could generate and register their own public keys. The public parameters are computed by aggregating all user public keys. Crucially, the aggregation process is \emph{public}, thus eliminating the need of any trusted authority. We present two new traitor-tracing systems in this model based on bilinear pairings. Our first scheme is proven adaptively secure in the generic group model. This scheme features a transparent setup, ciphertexts consisting of $6\sqrt{L}+4$ group elements, and a public tracing algorithm. Our second scheme supports a bounded collusion of traitors and is proven selectively secure in the standard model. Our main technical ingredients are new registered functional encryption (RFE) schemes for quadratic and linear functions which, prior to this work, were known only from indistinguishability obfuscation.

To substantiate the practicality of our approach, we evaluate the performance a proof of concept implementation. For a group of $L = 1024$ users, encryption and decryption take roughly 50ms and 4ms, respectively, whereas a ciphertext is of size 6.7KB.



## 2024/180

* Title: Exploiting RPMB authentication in a closed source TEE implementation
* Authors: Aya Fukami, Richard Buurke, Zeno Geradts
* [Permalink](https://eprint.iacr.org/2024/180)
* [Download](https://eprint.iacr.org/2024/180.pdf)

### Abstract

Embedded Multimedia Cards (eMMCs) provide a protected memory area called the Replay Protected Memory Block (RPMB). eMMCs are commonly used as storage media in modern smartphones. In order to protect these devices from unauthorized access, important data is stored in the RPMB area in an authenticated manner. Modification of the RPMB data requires a pre-shared authentication key. An unauthorized user cannot change the stored data. On modern devices, this pre-shared key is generated and used exclusively within a Trusted Execution Environment (TEE) preventing attackers from access. In this paper, we investigate how the authentication key for RPMB is programmed on the eMMC. We found that this key can be extracted directly from the target memory chip. Once obtained, the authentication key can be used to manipulate stored data. In addition, poor implementation of certain security features, aimed at preventing replay attacks using RPMB on the host system can be broken by an attacker. We show how the authentication key can be extracted and how it can be used to break the anti-rollback protection to enable data restoration even after a data wipe operation has been completed. Our findings show that non-secure RPMB implementations can enable forensic investigators to break security features implemented on modern smartphones.



## 2024/181

* Title: Functional Bootstrapping for FV-style Cryptosystems
* Authors: Dongwon Lee, Seonhong Min, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/181)
* [Download](https://eprint.iacr.org/2024/181.pdf)

### Abstract

Fully Homomorphic encryption (FHE) enables the computation of an arbitrary function over encrypted data without decrypting them. In particular, bootstrapping is a core building block of FHE which reduces the noise of a ciphertext thereby recovering the computational capability.

This paper introduces a new bootstrapping framework for the Fan-Vercuteren (FV) scheme, called the functional bootstrapping, providing more generic and advanced functionality than the ordinary bootstrapping method. More specifically, the functional bootstrapping allows us to evaluate an arbitrary function while removing the error of an input ciphertext. Therefore, we achieve better depth consumption and computational complexity as the evaluation of a circuit can be integrated as part of the functional bootstrapping procedure. In particular, our approach extends the functionality of FV since it is even applicable to functions between different plaintext spaces.

At the heart of our functional bootstrapping framework is a novel homomorphic Look-Up Table (LUT) evaluation method where we represent any LUT using only the operations supported by the FV scheme. Finally, we provide a proof-of-concept implementation and present benchmarks. In concrete examples, such as delta and sign functions, our functional bootstrapping takes about 46.5s or 171.4s for 9-bit or 13-bit plaintext modulus, respectively.



## 2024/182

* Title: FileDES: A Secure, Scalable and Succinct Decentralized Encrypted Storage Network
* Authors: Minghui Xu, Jiahao Zhang, Hechuan Guo, Xiuzhen Cheng, Dongxiao Yu, Qin Hu, Yijun Li, Yipu Wu
* [Permalink](https://eprint.iacr.org/2024/182)
* [Download](https://eprint.iacr.org/2024/182.pdf)

### Abstract

Decentralized Storage Network (DSN) is an emerging technology that challenges traditional cloud-based storage systems by consolidating storage capacities from independent providers and coordinating to provide decentralized storage and retrieval services. However, current DSNs face several challenges associated with data privacy and efficiency of the proof systems. To address these issues, we propose FileDES (Decentralized Encrypted Storage), which incorporates three essential elements: privacy preservation, scalable storage proof, and batch verification. FileDES provides encrypted data storage while maintaining data availability, with a scalable Proof of Encrypted Storage (PoES) algorithm that is resilient to Sybil and Generation attacks. Additionally, we introduce a rollup-based batch verification approach to simultaneously verify multiple files using publicly verifiable succinct proofs. We conducted a comparative evaluation on FileDES, Filecoin, Storj and Sia under various conditions, including a WAN composed of up to 120 geographically dispersed nodes. Our protocol outperforms the others in terms of proof generation/verification efficiency, storage costs, and scalability.



## 2024/183

* Title: On Security Proofs of Existing Equivalence Class Signature Schemes
* Authors: Balthazar Bauer, Georg Fuchsbauer
* [Permalink](https://eprint.iacr.org/2024/183)
* [Download](https://eprint.iacr.org/2024/183.pdf)

### Abstract

Equivalence class signatures (EQS), introduced by Hanser and Slamanig (AC'14), sign vectors of elements from a bilinear group. Signatures can be ``adapted'', meaning that anyone can transform a signature on a vector to a (random) signature on any multiple of that vector. (Signatures thus authenticate equivalence classes.) A transformed signature/message pair is then indistinguishable from a random signature on a random message. EQS have been used to efficiently instantiate (delegatable) anonymous credentials, (round-optimal) blind signatures, ring and group signatures and anonymous tokens.

The original EQS construction (J.Crypto'19) is only proven in the generic group model, while the first construction from standard assumptions (PKC'18) only yields security guarantees insufficient for most applications. Two works (AC'19, PKC'22) propose applicable schemes which assume the existence of a common reference string for the anonymity notion. Their unforgeability is argued via a security proof from standard (or non-interactive) assumptions.

In this work we show that their security proof is flawed and explain the subtle issue.



## 2024/184

* Title: Threshold Raccoon: Practical Threshold Signatures from Standard Lattice Assumptions
* Authors: Rafael del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, Markku-Juhani Saarinen
* [Permalink](https://eprint.iacr.org/2024/184)
* [Download](https://eprint.iacr.org/2024/184.pdf)

### Abstract

Threshold signatures improve both availability and security of digital signatures by splitting the signing key into $N$ shares handed out to different parties. Later on, any subset of at least $T$ parties can cooperate to produce a signature on a given message. While threshold signatures have been extensively studied in the pre-quantum setting, they remain sparse from quantum-resilient assumptions.

We present the first efficient lattice-based threshold signatures with signature size 13 KiB and communication cost 40 KiB per user, supporting a threshold size as large as 1024 signers. We provide an accompanying high performance implementation. The security of the scheme is based on the same assumptions as Dilithium, a signature recently selected by NIST for standardisation which, as far as we know, cannot easily be made threshold efficiently.

All operations used during signing are due to symmetric primitives and simple lattice operations; in particular our scheme does not need heavy tools such as threshold fully homomorphic encryption or homomorphic trapdoor commitments as in prior constructions. The key technical idea is to use one-time additive masks to mitigate the leakage of the partial signing keys through partial signatures.



## 2024/185

* Title: Vortex: A List Polynomial Commitment and its Application to Arguments of Knowledge
* Authors: Alexandre Belling, Azam Soleimanian, Bogdan Ursu
* [Permalink](https://eprint.iacr.org/2024/185)
* [Download](https://eprint.iacr.org/2024/185.pdf)

### Abstract

A list polynomial commitment scheme (LPC) is a polynomial commitment scheme with a relaxed binding property. Namely, in an LPC setting, a commitment to a function $f(X)$ can be opened to a list of low-degree polynomials close to $f(X)$ (w.r.t. the relative Hamming distance and over a domain $D$). The scheme also allows opening one of the polynomials of the list at an arbitrary point $x$ and convincing a verifier that one of the polynomials in the list evaluates to the purported value.

Vortex is a list polynomial commitment, obtained through a modification of Ligero (CCS 2017), inspired by the schemes of Brakedown (Crypto 2023), batch-FRI (FOCS 2020), and RedShift (CCS 2022). Concerning one application of Vortex, for a witness of size $N$, the messages between the prover and the verifier are of size $O(N^{1/2})$. Vortex is a core component of the SNARK used by the prover of Linea (Consensys). This paper provides a complete security analysis for Vortex. We use a general compiler to build an Argument of Knowledge (AoK) by combining our list polynomial commitment and a polynomial-IOP (PIOP).

The approach is similar to combining a PIOP with a polynomial commitment scheme and has a soundness loss only linear in the list size. This overcomes a previous limitation in the standard compiler from a generic PIOP and a list polynomial commitment scheme to an interactive argument of knowledge, which suffers from a soundness loss of $\mathcal{O}(|L|^r)$ (where $|L|$ is the list size and $r$ is the number of interactions between the prover and the verifier in the PIOP).



## 2024/186

* Title: RAD-FS - Inherent and Embedded SCA-Security in Ultra-Low Power IoTs
* Authors: Daniel Dobkin, Nimrod Cever, Itamar Levi
* [Permalink](https://eprint.iacr.org/2024/186)
* [Download](https://eprint.iacr.org/2024/186.pdf)

### Abstract

High-performance and energy-efficient encryption engines have become crucial components in modern System-On-Chip (SoC) architectures across multiple platforms, including servers, desktops, mobile devices, and IoT edge devices. Alas, the secure operation of cryptographic engines faces a significant obstacle caused by information leakage through various side-channels. Adversaries can exploit statistical analysis techniques on measured (e.g.,) power and timing signatures generated during (e.g.,) encryption process to extract secret material. Countermeasures against such side-channel attacks often impose substantial power, area, and performance overheads. Consequently, designing side-channel secure encryption engines becomes a critical challenge when ensuring high-performance and energy-efficient operations. In this paper we will suggest a novel technique for low cost, high impact, easily scalable protection based on Adaptive Dynamic Voltage and Frequency Scaling (A-DVFS) capabilities in ultra-low-power (ULP) sub-threshold chips. We review the improvement of using integrated voltage regulators and DVFS, normally used for efficient power management, towards increasing side-channel resistance of encryption engines; Pushing known prior-art in the topic to ULP-regime. The hardware measurements were performed on PLS15 test-chip fabricated in ULP 40nm process going down from nominal voltage to 580 mV power-supply. Various results and detailed analysis is presented to demonstrate the impact of power management circuits on side-channel security, performance-impact and comparison to prior-art. Importantly, we highlight security sensitivities DVFS embeds in terms of software side-channels such as timing, and their mitigation with our proposed technique, successfully masking the time signature introduced by DVFS.



## 2024/187

* Title: On the bijectivity of the map $\chi$
* Authors: Anna-Maurin Graner, Björn Kriepke, Lucas Krompholz, Gohar M. Kyureghyan
* [Permalink](https://eprint.iacr.org/2024/187)
* [Download](https://eprint.iacr.org/2024/187.pdf)

### Abstract

We prove that for $n>1$ the map $\chi:\mathbb{F}_q^n \to \mathbb{F}_q^n$, defined by $y=\chi(x)$ with $y_i = x_i + x_{i+2}\cdot(1+x_{i+1})$ for $1\leq i \leq n$, is bijective if and only if
$q=2$ and $n$ is odd, as it was conjectured by Schoone and Daemen in 2023.



## 2024/188

* Title: HomeRun: High-efficiency Oblivious Message Retrieval, Unrestricted
* Authors: Yanxue Jia, Varun Madathil, Aniket Kate
* [Permalink](https://eprint.iacr.org/2024/188)
* [Download](https://eprint.iacr.org/2024/188.pdf)

### Abstract

In the realm of privacy-preserving blockchain applications such as Zcash, oblivious message retrieval (OMR) enables recipients to privately access messages directed to them on blockchain nodes (or bulletin board servers). OMR prevents servers from linking a message and its corresponding recipient's address, thereby safeguarding recipient privacy. Several OMR schemes have emerged recently to meet the demands of these privacy-centric blockchains; however, we observe that existing solutions exhibit shortcomings in various critical aspects and may only achieve certain objectives inefficiently, sometimes relying on trusted hardware, thereby impacting their practical utility. This work introduces a novel OMR protocol, HomeRun, that leverages two semi-honest, non-colluding servers to excel in both performance and security attributes as compared to the current state-of-the-art.

HomeRun stands out by providing unlinkability across multiple requests for the same recipient's address. Moreover, it does not impose a limit on the number of pertinent messages that can be received by a recipient, which thwarts ``message balance exhaustion'' attacks and enhances system usability. HomeRun also empowers servers to regularly delete the retrieved messages and the associated auxiliary data, which mitigates the constantly increasing computation costs and storage costs incurred by servers. Remarkably, none of the existing solutions offer all of these features collectively. Finally, thanks to its judicious use of highly efficient cryptographic building blocks, HomeRun is highly performant: Specifically, the total runtime of servers in HomeRun is $3830 \times$ less than that in the work by Liu et al. (CRYPTO '22) based on fully-homomorphic encryption, and at least $1459 \times$ less than that in the design by Madathil et al. (USENIX Security '22) based on two semi-honest and non-colluding servers, using a single thread in a WAN setting.



## 2024/189

* Title: ZeroAuction: Zero-Deposit Sealed-bid Auction via Delayed Execution
* Authors: Haoqian Zhang, Michelle Yeo, Vero Estrada-Galinanes, Bryan Ford
* [Permalink](https://eprint.iacr.org/2024/189)
* [Download](https://eprint.iacr.org/2024/189.pdf)

### Abstract

Auctions, a long-standing method of trading goods and services, are a promising use case for decentralized finance. However, due to the inherent transparency property of blockchains, current sealed-bid auction implementations on smart contracts requires a bidder to send at least two transactions to the underlying blockchain: a bidder must first commit their bid in the first transaction during the bidding period and reveal their bid in the second transaction once the revealing period starts. In addition, the smart contract often requires a deposit to incentivize bidders to reveal their bids, rendering unnecessary financial burdens and risks to bidders. We address these drawbacks by enforcing delayed execution in the blockchain execution layer to all transactions. In short, the blockchain only accepts encrypted transactions, and when the blockchain has finalized an encrypted transaction, the consensus group decrypts and executes it. This architecture enables ZeroAuction, a sealed-bid auction smart contract with zero deposit requirement. ZeroAuction relies on the blockchain enhanced with delayed execution to hide and bind the bids within the encrypted transactions and, after a delay period, reveals them automatically by decrypting and executing the transactions. Because a bidder only needs to interact with the blockchain once instead of two times to participate in the auction, ZeroAuction significantly reduces the latency overhead along with eliminating the deposit requirement.



## 2024/190

* Title: Constructing Committing and Leakage-Resilient Authenticated Encryption
* Authors: Patrick Struck, Maximiliane Weishäupl
* [Permalink](https://eprint.iacr.org/2024/190)
* [Download](https://eprint.iacr.org/2024/190.pdf)

### Abstract

The main goal of this work is to construct authenticated encryption (AE) that is both committing and leakage-resilient. As a first approach for this we consider generic composition as a well-known method for constructing AE schemes. While the leakage resilience of generic composition schemes has already been analyzed by Barwell et al. (AC'17), for committing security this is not the case. We fill this gap by providing a separate analysis of the generic composition paradigms with respect to committing security, giving both positive and negative results: By means of a concrete attack, we show that Encrypt-then-MAC is not committing. Furthermore, we prove that Encrypt-and-MAC is committing, given that the underlying schemes satisfy security notions we introduce for this purpose. We later prove these new notions achievable by providing schemes that satisfy them. MAC-then-Encrypt turns out to be more difficult due to the fact that the tag is not outputted alongside the ciphertext as it is done for the other two composition methods. Nevertheless, we give a detailed heuristic analysis of MAC-then-Encrypt with respect to committing security, leaving a definite result as an open task for future work. Our results, in combination with the fact that only Encrypt-then-MAC yields leakage-resilient AE schemes, show that one cannot obtain AE schemes that are both committing and leakage-resilient via generic composition. As a second approach for constructing committing and leakage-resilient AE, we develop a generic transformation that turns an arbitrary AE scheme into one that fulfills both properties. The transformation relies on a keyed function that is both binding, i.e., it is hard to find key-input pairs that result in the same output, and leakage-resilient pseudorandom.



## 2024/191

* Title: A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group Actions
* Authors: Steven Galbraith, Yi-Fu Lai, Hart Montgomery
* [Permalink](https://eprint.iacr.org/2024/191)
* [Download](https://eprint.iacr.org/2024/191.pdf)

### Abstract

Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLog) problems for abelian group actions.
Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLog to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed how to convert an unreliable CDH oracle into one that is correct with overwhelming probability. However, while a theoretical breakthrough, their reduction is quite inefficient: if the CDH oracle is correct with probability $\epsilon$ then their algorithm to amplify the success requires on the order of $1/\epsilon^{21}$ calls to the CDH oracle.

We revisit this line of work and give a much simpler and tighter algorithm. Our method only takes on the order of $1/\epsilon^{4}$ CDH oracle calls and is conceptually simpler than the Montgomery-Zhandry reduction. Our algorithm is also fully black-box, whereas the Montgomery-Zhandry algorithm is slightly non-black-box. Our main tool is a thresholding technique that replaces the comparison of distributions in Montgomery-Zhandry with testing equality of thresholded sets.



## 2024/192

* Title: Direct FSS Constructions for Branching Programs and More from PRGs with Encoded-Output Homomorphism
* Authors: Elette Boyle, Lisa Kohl, Zhe Li, Peter Scholl
* [Permalink](https://eprint.iacr.org/2024/192)
* [Download](https://eprint.iacr.org/2024/192.pdf)

### Abstract

Function secret sharing (FSS) for a class $\cal{F}$ allows to split a secret function $f \in \cal{F}$ into (succinct) secret shares $f_0,f_1$, such that for all $x\in \{0,1\}^n$ it holds $f_0(x)-f_1(x)=f(x)$. FSS has numerous applications, including private database queries, nearest neighbour search, private heavy hitters and secure computation in the preprocessing model, where the supported class $\cal{F}$ translates to richness in the application. Unfortunately, concretely efficient FSS constructions are only known for very limited function classes.

In this work we introduce the notion of pseudorandom generators with encoded-output homomorphism (EOH-PRGs), and give direct FSS constructions for bit-fixing predicates, branching programs and more based on this primitive. Further, we give constructions of FSS for deterministic finite automatas (DFAs) from a KDM secure variant of EOH-PRGs.

- New abstractions. Following the work of Alamati et al.(EUROCRYPT '19), who classify minicrypt primitives with algebraic structure and their applications, we capture the essence of our FSS constructions in the notion of EOH-PRG, paving the road towards future efficiency improvements via new instantiations of this primitive. The abstraction of EOH-PRG and its instantiations may be of independent interest, as it is an approximate substitution of an ideal homomorphic PRG.
- Better efficiency. We show that EOH-PRGs can be instantiated from LWE and a small-exponent variant of the DCR assumption. A theoretical analysis of our instantiations suggest efficiency improvements over the state of the art both in terms of key size and evaluation time: We show that our FSS instantiations lead to smaller key sizes, improving over previous constructions by a factor of $3.5$ and more. While for bit-fixing predicates our FSS constructions show comparable or mildly improved run time (depending on the instantiation), we achieve considerable improvements for branching programs by avoiding the expensive generic transformation via universal circuits, shaving off a factor of $w$ and more in the number of abstract operations, where $w$ corresponds to an upper bound on the width of the underlying class of branching programs.
- New constructions. We show that our instantiations of EOH-PRGs additionally support a form of KDM-security, without requiring an additional circular-security assumption. Based on this, we give the first FSS construction for DFAs which supports the evaluation of inputs of a-priori unbounded length without relying on FHE.
- Applications. We outline applications of our FSS constructions including pattern matching with wild cards, image matching, nearest neighbor search and regular expression matching.



## 2024/193

* Title: MQ Does Not Reduce to TUOV
* Authors: Laura Maddison
* [Permalink](https://eprint.iacr.org/2024/193)
* [Download](https://eprint.iacr.org/2024/193.pdf)

### Abstract

The submission of the Triangular Unbalanced Oil and Vinegar (TUOV) digital signature scheme to the NIST competition in 2023 claims that if the Multivariate Quadratic (MQ) problem (with suitable parameters) is hard, then the TUOV problem must also be hard. We show why the proof fails and why the claimed theorem cannot be true in general.



## 2024/194

* Title: Helium: Scalable MPC among Lightweight Participants and under Churn
* Authors: Christian Mouchet, Sylvain Chatel, Apostolos Pyrgelis, Carmela Troncoso
* [Permalink](https://eprint.iacr.org/2024/194)
* [Download](https://eprint.iacr.org/2024/194.pdf)

### Abstract

We introduce Helium, a novel framework that supports scalable secure multiparty computation for lightweight participants and tolerates churn.
Helium relies on multiparty homomorphic encryption (MHE) as its core building block.
While MHE schemes have been well studied in theory, prior works fall short of addressing critical considerations paramount for adoption such as supporting resource-constrained participants and ensuring liveness and security under network churn.
In this work, we systematize the requirements of MHE-based MPC protocols from a practical lens, and we propose a novel execution mechanism, that addresses those considerations.
We implement this execution in Helium, which makes it the first implemented solution that effectively supports sub-linear-cost MPC among lightweight participants and under churn.
This represents a significant leap in applied MPC, as most previously proposed frameworks require the participants to have high bandwidth and to be consistently online.
We show that a Helium network of $30$ parties connected with a $100$Mbits/s link and experiencing a system-wide churn rate of $40$ failures per minute can compute the product of a fixed secret $512\times512$ matrix (e.g., a collectively trained model) with an input secret vector (e.g., a feature vector) $8.3$ times per second.
This is $\sim1500$ times faster than a state-of-the art MPC implementation without churn.



## 2024/195

* Title: PQC-AMX: Accelerating Saber and FrodoKEM on the Apple M1 and M3 SoCs
* Authors: Décio Luiz Gazzoni Filho, Guilherme Brandão, Gora Adj, Arwa Alblooshi, Isaac A. Canales-Martínez, Jorge Chávez-Saab, Julio López
* [Permalink](https://eprint.iacr.org/2024/195)
* [Download](https://eprint.iacr.org/2024/195.pdf)

### Abstract

As CPU performance is unable to keep up with the dramatic growth of the past few decades, CPU architects are looking into domain-specific architectures to accelerate certain tasks. A recent trend is the introduction of matrix-multiplication accelerators to CPUs by manufacturers such as IBM, Intel and ARM, some of which have not launched commercially yet. Apple's systems-on-chip (SoCs) for its mobile phones, tablets and personal computers include a proprietary, undocumented CPU-coupled matrix multiplication coprocessor called AMX. In this paper, we leverage AMX to accelerate the post-quantum lattice-based cryptosystems Saber and FrodoKEM, and benchmark their performance on Apple M1 and M3 SoCs. We propose a variant of the Toeplitz Matrix-Vector Product algorithm for polynomial multiplication, which sets new speed records for Saber using AMX (up to 13% for the main KEM operations, and 151% for matrix-vector multiplication of polynomials). For FrodoKEM, we set new speed records with our AMX implementation (up to 21% for the main KEM operations, and 124% for matrix multiplication, with even greater improvements for $4 \times$-batching). Such speedups are relative to our optimized NEON implementation, also presented here, which improves upon the state-of-the-art implementation for ARMv8 CPUs.



## 2024/196

* Title: Subfield attack: leveraging composite-degree extensions in the Quotient Ring transform
* Authors: Pierre Pébereau
* [Permalink](https://eprint.iacr.org/2024/196)
* [Download](https://eprint.iacr.org/2024/196.pdf)

### Abstract

In this note, we show that some of the parameters of the Quotient-Ring transform proposed for VOX are vulnerable.
More precisely, they were chosen to defeat an attack in the field extension $\mathbb F_{q^l}$ obtained by quotienting $\mathbb F_q[X]$ by an irreducible polynomial of degree $l$.
We observe that we may use a smaller extension $\mathbb F_{q^{l'}}$ for any $l'|l$, in which case the attacks apply again.
We also introduce a simple algebraic attack without the use of the MinRank problem to attack the scheme.
These attacks concern a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb.
We estimate the cost of our attack on these parameter sets and find costs of at most $2^{67}$ gates, and significantly lower in most cases.
In practice, our attack requires $0.3s, 1.35s, 0.56s$ for parameter sets I,III,V for the initial VOX parameters, and $56.7s, 6.11s$ for parameter sets IIIa, Vb proposed after the rectangular MinRank attack.



## 2024/197

* Title: Alba: The Dawn of Scalable Bridges for Blockchains
* Authors: Giulia Scaffino, Lukas Aumayr, Mahsa Bastankhah, Zeta Avarikioti, Matteo Maffei
* [Permalink](https://eprint.iacr.org/2024/197)
* [Download](https://eprint.iacr.org/2024/197.pdf)

### Abstract

Over the past decade, cryptocurrencies have garnered attention from academia and industry alike, fostering a diverse blockchain ecosystem and novel applications. The inception of bridges improved interoperability, enabling asset transfers across different blockchains to capitalize on their unique features. Despite their surge in popularity and the emergence of Decentralized Finance (DeFi), trustless bridge protocols remain inefficient, either relaying too much information (e.g., light-client-based bridges) or demanding expensive computation (e.g., zk-based bridges). These inefficiencies arise because existing bridges securely prove a transaction's on-chain inclusion on another blockchain. Yet this is unnecessary as off-chain solutions, like payment and state channels, permit safe transactions without on-chain publication. However, existing bridges do not support the verification of off-chain payments.

This paper fills this gap by introducing the concept of Pay2Chain bridges that leverage the advantages of off-chain solutions like payment channels to overcome current bridges' limitations. Our proposed Pay2Chain bridge, named Alba, facilitates the efficient, secure, and trustless execution of conditional payments or smart contracts on a target blockchain based on off-chain events. Alba, besides its technical advantages, enriches the source blockchain's ecosystem by facilitating DeFi applications, multi-asset payment channels, and optimistic stateful off-chain computation.

We formalize the security of Alba against Byzantine adversaries in the UC framework and complement it with a game theoretic analysis. We further introduce formal scalability metrics to demonstrate Alba’s efficiency. Our empirical evaluation confirms Alba efficiency in terms of communication complexity and on-chain costs, with its optimistic case incurring only twice the cost of a standard Ethereum transaction of token ownership transfer.



## 2024/198

* Title: Distributed Randomness using Weighted VRFs
* Authors: Sourav Das, Benny Pinkas, Alin Tomescu, Zhuolun Xiang
* [Permalink](https://eprint.iacr.org/2024/198)
* [Download](https://eprint.iacr.org/2024/198.pdf)

### Abstract

Generating and integrating shared randomness into a blockchain can expand applications and strengthen security. We aim to have validators generating blockchain randomness autonomously, and fresh shared randomness is generated for each block. We focus on proof-of-stake blockchains, where each validator has a different amount of stake (aka weight). Such chains introduce a weighted threshold setting where subset authorization relies on the cumulative weight of validators rather than the subset size.

We introduce three cryptographic protocols to enable generating shared randomness in a weighted setting: A publicly verifiable secret sharing scheme (PVSS) which is weighted and aggregatable, a weighted distributed key generation protocol (DKG), and a weighted verifiable unpredictable function (VUF). Importantly, in the VUF protocol, which is the protocol that is run most frequently, the computation and communication costs of participants are independent of their weight. This feature is crucial for scalability.

We implemented our schemes on top of Aptos blockchain, which is a proof-of-stake blockchain deployed in production. Our micro-benchmarks demonstrate that the signing and verification time, as well as the signature size, are independent of the total weight of the parties, whereas the signing time and signature size of the baseline (BLS with virtualization) increase significantly. For instance, our VUF reduces the signature size by factors of 7X and 34X for total weights of 821 and 4053, respectively. We also demonstrate the practicability of our design via an end-to-end evaluation.



## 2024/199

* Title: Formal Security Proofs via Doeblin Coefficients: Optimal Side-channel Factorization from Noisy Leakage to Random Probing
* Authors: Julien Béguinot, Wei Cheng, Sylvain Guilley, Olivier Rioul
* [Permalink](https://eprint.iacr.org/2024/199)
* [Download](https://eprint.iacr.org/2024/199.pdf)

### Abstract

Masking is one of the most popular countermeasures to side-
channel attacks, because it can offer provable security. However, depend-
ing on the adversary’s model, useful security guarantees can be hard
to provide. At first, masking has been shown secure against t-threshold
probing adversaries by Ishai et al. at Crypto’03. It has then been shown
secure in the more generic random probing model by Duc et al. at Euro-
crypt’14. Prouff and Rivain have introduced the noisy leakage model to
capture more realistic leakage at Eurocrypt’13. Reduction from noisy
leakage to random probing has been introduced by Duc et al. at Euro-
crypt’14, and security guarantees were improved for both models by
Prest et al. at Crypto’19, Duc et al. in Eurocrypt’15/J. Cryptol’19,
and Masure and Standaert at Crypto’23. Unfortunately, as it turns out,
we found that previous proofs in either random probing or noisy leakage
models are flawed, and such flaws do not appear easy to fix.
In this work, we show that the Doeblin coefficient allows one to over-
come these flaws. In fact, it yields optimal reductions from noisy leakage
to random probing, thereby providing a correct and usable metric to
properly ground security proofs. This shows the inherent inevitable cost
of a reduction from the noisy leakages to the random probing model. We
show that it can also be used to derive direct formal security proofs using
the subsequence decomposition of Prouff and Rivain.



## 2024/200

* Title: A Better Proof-of-Work Fork Choice Rule
* Authors: Karl Kreder, Shreekara Shastry, Apostolos Tzinas, Sriram Vishwanath, Dionysis Zindros
* [Permalink](https://eprint.iacr.org/2024/200)
* [Download](https://eprint.iacr.org/2024/200.pdf)

### Abstract

We propose a modification to the fork choice rule of proof-of-work blockchains. Instead of choosing the heaviest chain, we choose the chain with the most intrinsic work. The intrinsic work of a block is roughly the number of zeroes at the front of its hash. This modification allows us to safely decrease the confirmations required, yielding a $28.5\%$ improvement in confirmation delay or, dually, safely increase the block production rate, yielding a $16.3\%$ improvement in throughput, as compared to the vanilla Bitcoin proof-of-work fork choice rule. Our modification is at the level of the proof-of-work inequality, and thus can be composed with any other methods to improve latency or throughput that have been proposed in the literature. We report the experimental findings by measuring them on a production-grade implementation of our system, whose testnet is already deployed in the wild. Lastly, we formally prove the security of our new protocol in the Bitcoin Backbone model.



## 2024/201

* Title: Breaking the decisional Diffie-Hellman problem in totally non-maximal imaginary quadratic orders
* Authors: Antonio Sanso
* [Permalink](https://eprint.iacr.org/2024/201)
* [Download](https://eprint.iacr.org/2024/201.pdf)

### Abstract

This paper introduces an algorithm to efficiently break the Decisional Diffie-Hellman (DDH) assumption in totally non-maximal imaginary quadratic orders, specifically when $\Delta_1 = 3$, and $f$ is non-prime with knowledge of a single factor. Inspired by Shanks and Dedekind's work on 3-Sylow groups, we generalize their observations to undermine DDH security.



## 2024/202

* Title: Fully Homomorphic Encryption beyond IND-CCA1 Security: Integrity through Verifiability
* Authors: Mark Manulis, Jérôme Nguyen
* [Permalink](https://eprint.iacr.org/2024/202)
* [Download](https://eprint.iacr.org/2024/202.pdf)

### Abstract

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond CCA1. Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (vCCA). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be "linked" to the original input ciphertexts. We formalize the vCCA notion in two equivalent formulations; the first is in the indistinguishability paradigm, the second follows the non-malleability simulation-based approach, and is a generalization of the targeted malleability introduced by Boneh et al. in 2012.

We strengthen the credibility of our definitions by exploring relations to existing security notions for homomorphic encryption schemes, namely CCA1, RCCA, FuncCPA, CCVA, and HCCA. We prove that vCCA security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, vCCA is strictly stronger than CCA1.

Finally, we provide a general transformation, that takes any CPA-secure FHE scheme and makes it vCCA-secure. Our transformation first turns an FHE scheme into a CCA2-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge (SNARK) to verifiably control the evaluation algorithm. In fact, we obtain four general variation of this transformation. We handle both the asymmetric and the symmetric key FHE schemes, and for each we give two variations differing in whether the ciphertext integrity can be verified publicly or requires the secret key. We use well-known techniques to achieve CCA security in the first step of our transformation. In the asymmetric case, we use the double encryption paradigm, and in the symmetric case, we use Encrypt-then-MAC techniques. Furthermore, our transformation also gives the first CCA-secure FHE scheme based on bootstrapping techniques.



## 2024/203

* Title: Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use
* Authors: Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, Yuriy Polyakov
* [Permalink](https://eprint.iacr.org/2024/203)
* [Download](https://eprint.iacr.org/2024/203.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a powerful tool for performing privacy-preserving analytics over encrypted data. A promising method for FHE over real and complex numbers is approximate homomorphic encryption, instantiated with the Cheon-Kim-Kim-Song (CKKS) scheme. The CKKS scheme enables efficient evaluation for many privacy-preserving machine learning applications. Despite its high efficiency, there is currently a lot of confusion on how to securely instantiate CKKS for a given application, especially after secret-key recovery attacks were proposed by Li and Micciancio (EUROCRYPT'21) for the $IND-CPA^{D}$ setting, i.e., where decryption results are shared with other parties. On the one hand, the generic definition of $IND-CPA^{D}$ is application-agnostic and often requires impractically large parameters. On the other hand, practical CKKS implementations target specific applications and use tighter parameters. A good illustration are the recent secret-key recovery attacks against a CKKS implementation in the OpenFHE library by Guo et al. (USENIX Security'24). We show that these attacks misuse the library by employing different (incompatible) circuits during parameter estimation and run-time computation, yet they do not violate the generic (application-agnostic) $IND-CPA^{D}$ definition.

To address this confusion, we introduce the notion of application-aware homomorphic encryption and devise related security definitions, which correspond more closely to how homomorphic encryption schemes are implemented and used in practice. We then formulate the guidelines for implementing the application-aware homomorphic encryption model to achieve $IND-CPA^{D}$ security for practical applications of CKKS. We also show that our application-aware model can be used for secure, efficient instantiation of exact homomorphic encryption schemes.



## 2024/204

* Title: PerfOMR: Oblivious Message Retrieval with Reduced Communication and Computation
* Authors: Zeyu Liu, Eran Tromer, Yunhao Wang
* [Permalink](https://eprint.iacr.org/2024/204)
* [Download](https://eprint.iacr.org/2024/204.pdf)

### Abstract

Anonymous message delivery, as in privacy-preserving blockchain and private messaging applications, needs to protect recipient metadata: eavesdroppers should not be able to link messages to their recipients. This raises the question: how can untrusted servers assist in delivering the pertinent messages to each recipient, without learning which messages are addressed to whom?

Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource the message detection and retrieval in a privacy-preserving way, using homomorphic encryption. This exhibits significant costs in computation per message scanned (${\sim}109$ms), as well as in the size of the associated messages (${\sim}1$kB overhead) and public keys (${\sim}132$kB).

This work constructs more efficient OMR schemes, by replacing the LWE-based clue encryption of prior works with a Ring-LWE variant, and utilizing the resulting flexibility to improve several components of the scheme. We thus devise, analyze, and benchmark two protocols:

The first protocol focuses on improving the detector runtime, using a new retrieval circuit that can be homomorphically evaluated more efficiently. Concretely, this construction takes only ${\sim}7.3$ms per message scanned, about $15$x faster than the prior work.

The second protocol focuses on reducing the communication costs, by designing a different homomorphic decryption circuit. While the circuit is less homomorphic-encryption-friendly (than our first construction), it allows the parameter of the Ring-LWE encryption to be set such that both the public key and the message size are greatly reduced. Concretely, the public key size is about $235$x smaller than the prior work, and the message size is roughly $1.6$x smaller. The runtime of this second construction is ${\sim}40.0$ms per message, still more than $2.5$x faster than prior works.



## 2024/205

* Title: A Generalized Distributed RSA Key Generation
* Authors: ChihYun Chuang, IHung Hsu, TingFang Lee
* [Permalink](https://eprint.iacr.org/2024/205)
* [Download](https://eprint.iacr.org/2024/205.pdf)

### Abstract

In this paper, we propose a novel bi-primality test to determine whether $N=pq$ is the product of two primes on any RSA modulus in which we relaxed the restriction, $p\equiv q \equiv 3 \mbox{ (mod } 4)$, that was assumed in most of current bi-primality tests. Our bi-primality test is generalized from Lucas primality test to the bi-prime case. Our test always accepts when $p$ and $q$ are both prime, and otherwise accepts with probability at most $1/2$. In addition, we also prove that the Boneh-Franklin's bi-primality test accepts composite with probability at most $1/4$ instead of $1/2$, if we add an additional condition $\gcd(N, p+q-1)=1$. Moreover, we design a multiparty protocol against of static semi-honest adversaries in the hybrid model and provide a security proof. We then implement the proposed protocol and run in a single thread on a laptop which turned out with average 224 seconds execution time, given that $N$ is around $2048$-bit.



## 2024/206

* Title: Kronos: A Robust Sharding Blockchain Consensus with Optimal Communication Overhead
* Authors: Andi Liu, Yizhong Liu, Zhuocheng Pan, Yinuo Li, Jianwei Liu, Yuan Lu
* [Permalink](https://eprint.iacr.org/2024/206)
* [Download](https://eprint.iacr.org/2024/206.pdf)

### Abstract

Sharding enhances blockchain scalability by dividing the network into shards, each managing specific unspent transaction outputs or accounts. As an introduced new transaction type, cross-shard transactions pose a critical challenge to the security and efficiency of sharding blockchains. Current solutions, however, either prioritize security with assumptions and substantial investments, or focus on reducing overhead and overlooking security considerations.

In this paper, we present Kronos, a generic and efficient sharding blockchain consensus ensuring robust security. At the core of Kronos, we introduce a ''buffer'' mechanism for atomic cross-shard transaction processing. Shard members collectively maintain a buffer to manage cross-shard inputs, ensuring that a transaction is committed only if all inputs are available, and no fund is transferred for invalid requests. While ensuring security including atomicity, Kronos processes transactions with optimal intra-shard communication overhead. A valid cross-shard transaction, involving $x$ input shards and $y$ output shards, is processed with a minimal intra-shard communication overhead factor of $x+y$. Additionally, we propose a reduction for transaction invalidity proof generation to simple and fast multicasting, leading to atomic rejection without executing full-fledged Byzantine fault tolerance (BFT) protocol in optimistic scenarios. Moreover, Kronos adopts a newly designed ''batch'' mechanism, reducing inter-shard message complexity for cross-shard transactions from $\mathcal{O}(\lambda)$ to $\mathcal{O}((m \text{log} m/b)\lambda)$ without sacrificing responsiveness (where $m$ denotes number of shards, $b$ denotes the batch size of intra-shard consensus, and $\lambda$ is security parameter).

Kronos operates without dependence on any time or client honesty assumption, serving as a plug-in sharding blockchain consensus supporting applications in diverse network environments including asynchronous ones. We implement Kronos using two prominent BFT protocols: asynchronous Speeding Dumbo (NDSS'22) and partial synchronous HotStuff (PODC'19). Extensive experiments (over up to $1000$ AWS EC2 nodes across 4 AWS regions) demonstrate Kronos achieving a substantial throughput of $68.6$ktx/sec with $1.7$sec latency. Compared with state-of-the-art solutions, Kronos outperforms in all cases, achieving up to a $42 \times$ improvement in throughput and a $50\%$ reduction in latency when cross-shard transactions dominate the workload.



## 2024/207

* Title: NIZKs with Maliciously Chosen CRS: Subversion Advice-ZK and Accountable Soundness
* Authors: Prabhanjan Ananth, Gilad Asharov, Vipul Goyal, Hadar Kaner, Pratik Soni, Brent Waters
* [Permalink](https://eprint.iacr.org/2024/207)
* [Download](https://eprint.iacr.org/2024/207.pdf)

### Abstract

Trusted setup is commonly used for non-interactive proof and argument systems. However, there is no guarantee that the setup parameters in these systems are generated in a trustworthy manner. Building upon previous works, we conduct a systematic study of non-interactive zero-knowledge arguments in the common reference string model where the authority running the trusted setup might be corrupted. We explore both zero-knowledge and soundness properties in this setting. 

- We consider a new notion of NIZK called subversion advice-ZK NIZK that strengthens the notion of zero-knowledge with malicious authority security considered by Ananth, Asharov, Dahari and Goyal (EUROCRYPT'21), and present a construction of a subversion advice-ZK NIZK from the sub-exponential hardness of learning with errors.

- We introduce a new notion that strengthens the traditional definition of soundness, called accountable soundness, and present generic compilers that lift any NIZK for interesting languages in NP to additionally achieve accountable soundness.

- Finally, we combine our results for both subversion advice-ZK and accountable soundness to achieve a subversion advice-ZK NIZK that also satisfies accountable soundness. This results in the first NIZK construction that satisfies meaningful notions of both soundness and zero-knowledge even for maliciously chosen CRS.



## 2024/208

* Title: Asymmetric Cryptography from Number Theoretic Transformations
* Authors: Samuel Lavery
* [Permalink](https://eprint.iacr.org/2024/208)
* [Download](https://eprint.iacr.org/2024/208.pdf)

### Abstract

In this work, we introduce a family of asymmetric cryptographic functions based on dynamic number theoretic transformations with multiple rounds of modular arithmetic to enhance diffusion and difficulty of inversion. This function acts as a basic cryptographic building block for a novel communication-efficient zero-knowledge crypto-system. The system as defined exhibits partial homomorphism and behaves as an additive positive accumulator. By using a novel technique to constructively embed lattice problems in a nested fashion, the dimensionality and overall complexity of the lattice structure is increased.
This linked lattice framework obscures internal structure and mitigates cryptanalysis by applying a novel ’noisy roots’ technique. By relaxing the need for specifically correct nth ω roots in a given field, we apply offset values to create a framework of consisting of a set of uniquely transforming but arithmetically compatible NTTs. We provide specific parameters for conjectured NIST level V security. Communication costs are extremely low at 288-bytes per public key and 144-bytes per cipher-text or digital signature. Example protocols for key agreement, secure data exchange, additive accumulation, and digital signatures are provided.
Peer review is in preliminary stages at time of dissemination. Claims within have not undergone rigorous validation and likely contain inaccuracies, errors, flaws or incomplete analysis. Contents may see significant modification through later iterations.



## 2024/209

* Title: General Adversary Structures in Byzantine Agreement and Multi-Party Computation with Active and Omission Corruption
* Authors: Konstantinos Brazitikos, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2024/209)
* [Download](https://eprint.iacr.org/2024/209.pdf)

### Abstract

Typical results in multi-party computation (in short, MPC) capture faulty parties by assuming a threshold adversary corrupting parties actively and/or fail-corrupting. These corruption types are, however, inadequate for capturing correct parties that might suffer temporary network failures and/or localized faults - these are particularly relevant for MPC over large, global scale networks. Omission faults and general adversary structures have been proposed as more suitable alternatives. However, to date, there is no characterization of the feasibility landscape combining the above ramifications of fault types and patterns.
In this work we provide a tight characterization of feasibility of MPC in the presence of general adversaries - characterized by an adversary structure - that combine omission and active corruption. To this front we first provide a tight characterization of feasibility for Byzantine agreement (BA), a key tool in MPC protocols - this BA result can be of its own separate significance.
Subsequently, we demonstrate that the common techniques employed in the threshold MPC literature to deal with omission corruptions do not work in the general adversary setting, not even for proving bounds that would appear straightforward, e.g, sufficiency of the well known $Q^3$ condition on omission-only general adversaries. Nevertheless we provide a new protocol that implements general adversary MPC under a surprisingly complex, yet tight as we prove, bound.
As a contribution of independent interest, our work puts forth, for the first time, a formal treatment of general-adversary MPC with (active and) omission corruptions in Canetti's universal composition framework.



## 2024/210

* Title: Rollerblade: Replicated Distributed Protocol Emulation on Top of Ledgers
* Authors: Dionysis Zindros, Apostolos Tzinas, David Tse
* [Permalink](https://eprint.iacr.org/2024/210)
* [Download](https://eprint.iacr.org/2024/210.pdf)

### Abstract

We observe that most fixed-party distributed protocols can be rewritten by replacing a party with a ledger (such as a blockchain system) and the authenticated channel communication between parties with cross-chain relayers. This transform is useful because blockchain systems are always online and have battle-tested security assumptions. We provide a definitional framework that captures this analogy. We model the transform formally, and posit and prove a generic metatheorem that allows translating all theorems from the party setting into theorems in the emulated setting, while preserving analogies between party honesty and ledger security. In the heart of our proof lies a reduction-based simulation argument. As an example, our metatheorem can be used to construct a consensus protocol on top of other blockchains, creating a reliable rollup that assumes only the majority of the underlying layer-1s are secure.