[digest] 2024 Week 7

[IACR ePrint Archive]

## In this issue

1. [2024/214] Distributed Fiat-Shamir Transform
2. [2024/218] Lightweight Leakage-Resilient PRNG from TBCs using ...
3. [2024/220] Security Properties of One-Way Key Chains and ...
4. [2024/221] Mastic: Private Weighted Heavy-Hitters and ...
5. [2024/222] Reducing the Number of Qubits in Quantum Factoring
6. [2024/223] Game-Theoretically Fair Distributed Sampling
7. [2024/224] Amplification of Non-Interactive Zero Knowledge, ...
8. [2024/225] Universal Computational Extractors from Lattice ...
9. [2024/226] Attribute-based Keyed (Fully) Homomorphic Encryption
10. [2024/227] Adaptively Sound Zero-Knowledge SNARKs for UP
11. [2024/228] On the Untapped Potential of the Quantum FLT-based ...
12. [2024/229] Strong Batching for Non-Interactive Statistical ...
13. [2024/230] Analysis of Layered ROLLO-I
14. [2024/231] Need for Speed: Leveraging the Power of Functional ...
15. [2024/232] On the Security of Nova Recursive Proof System
16. [2024/233] Cayley hashing with cookies
17. [2024/234] Bare PAKE: Universally Composable Key Exchange from ...
18. [2024/235] Pseudorandom Error-Correcting Codes
19. [2024/236] Public-Key Cryptography through the Lens of Monoid ...
20. [2024/237] Collusion-Resilience in Transaction Fee Mechanism ...
21. [2024/238] A Single Trace Fault Injection Attack on Hedged ...
22. [2024/239] Simulation-Secure Threshold PKE from Standard ...
23. [2024/240] Implementation of Cryptanalytic Programs Using ChatGPT
24. [2024/241] Generalized Adaptor Signature Scheme: From Two- ...
25. [2024/242] Perfectly-Secure MPC with Constant Online ...
26. [2024/243] Towards Achieving Asynchronous MPC with Linear ...
27. [2024/244] Don’t Use It Twice! Solving Relaxed Linear Code ...
28. [2024/245] Linear-Communication Asynchronous Complete Secret ...
29. [2024/246] OCash: Fully Anonymous Payments between Blockchain ...
30. [2024/247] Fault-Resistant Partitioning of Secure CPUs for ...
31. [2024/248] FRIDA: Data Availability Sampling from FRI
32. [2024/249] Robust Additive Randomized Encodings from IO and ...
33. [2024/250] Exploring the Six Worlds of Gröbner Basis ...
34. [2024/251] Communication-Optimal Convex Agreement
35. [2024/252] Short Signatures from Regular Syndrome Decoding, ...
36. [2024/253] 2PC-MPC: Emulating Two Party ECDSA in Large-Scale MPC
37. [2024/254] Adaptive Security in SNARGs via iO and Lossy Functions
38. [2024/255] Revisiting Differential-Linear Attacks via a ...
39. [2024/256] Fiat-Shamir for Bounded-Depth Adversaries
40. [2024/257] LatticeFold: A Lattice-based Folding Scheme and its ...
41. [2024/258] SoK: Decentralized Storage Network
42. [2024/259] Anonymity on Byzantine-Resilient Decentralized ...
43. [2024/260] Kleptographic Attacks against Implicit Rejection
44. [2024/261] Election Eligibility with OpenID: Turning ...
45. [2024/262] Note on the cryptanalysis of Speedy
46. [2024/263] Threshold Encryption with Silent Setup
47. [2024/264] Extractable Witness Encryption for KZG Commitments ...
48. [2024/265] Beyond the circuit: How to Minimize Foreign ...
49. [2024/266] WhisPIR: Stateless Private Information Retrieval ...
50. [2024/267] zkPi: Proving Lean Theorems in Zero-Knowledge
51. [2024/268] A New Approach to Generic Lower Bounds: ...
52. [2024/269] A note on PUF-Based Robust and Anonymous ...
53. [2024/270] YPIR: High-Throughput Single-Server PIR with Silent ...
54. [2024/271] Understanding User-Perceived Security Risks and ...

## 2024/214

* Title: Distributed Fiat-Shamir Transform
* Authors: Michele Battagliola, Andrea Flamini
* [Permalink](https://eprint.iacr.org/2024/214)
* [Download](https://eprint.iacr.org/2024/214.pdf)

### Abstract

The recent surge of distribute technologies caused an increasing interest towards threshold signature protocols, that peaked with the recent NIST First Call for Multi-Party Threshold Schemes.
Since its introduction, the Fiat-Shamir Transform has been the most popular way to design standard digital signature schemes.
In this work, we translate the Fiat-Shamir Transform into a multi-party setting, building a framework that seeks to be an alternative, easier way to design threshold digital signatures. We do that by introducing the concept of threshold identification scheme and threshold sigma protocol, and showing necessary and sufficient conditions to prove the security of the threshold signature schemes derived from them.
Lastly, we show a practical application of our framework providing an alternative security proof for Sparkle, a recent threshold Schnorr signature. In particular, we consider the threshold identification scheme underlying Sparkle and prove the security of the signature derived from it.
We show that using our framework the effort required to prove the security of threshold signatures might be drastically lowered. In fact, instead of reducing explicitly its security to the security of a hard problem, it is enough to prove some properties of the underlying threshold sigma protocol and threshold identification scheme. Then, by applying the results that we prove in this paper it is guaranteed that the derived threshold signature is secure.



## 2024/218

* Title: Lightweight Leakage-Resilient PRNG from TBCs using Superposition
* Authors: Mustafa Khairallah, Srinivasan Yadhunathan, Shivam Bhasin
* [Permalink](https://eprint.iacr.org/2024/218)
* [Download](https://eprint.iacr.org/2024/218.pdf)

### Abstract

In this paper, we propose a leakage-resilient pseudo-random number generator (PRNG) design that leverages the rekeying techniques of the PSV-Enc encryption scheme and the superposition property of the Superposition-Tweak-Key (STK) framework. The random seed of the PRNG is divided into two parts; one part is used as an ephemeral key that changes every two calls to a tweakable block cipher (TBC), and the other part is used as a static long-term key. Using the superposition property, we show that it is possible to eliminate observable leakage by only masking the static key. Thus, our proposal itself can be seen as a superposition of masking and rekeying. We show that our observations can be used to design an unpredictable-with-leakage PRNG as long as the static key is protected, and the ephemeral key cannot be attacked with 2 traces. Our construction enjoys better theoretical security arguments than PSV-Enc; better Time-Data trade-off and leakage assumptions, using the recently popularized unpredictability with leakage. We verify our proposal by performing Test Vector Leakage Assessment (TVLA) on an STK-based TBC (\deoxys) operated with a fixed key and a dynamic random tweak. Our results show that while the protection of the static key is non-trivial, it only requires $\approx 10\%$ overhead for first-order protection in the most conservative setting, unlike traditional masking which may require significant overheads of $300\%$ or more.



## 2024/220

* Title: Security Properties of One-Way Key Chains and Implications for Security Protocols like TLS 1.3
* Authors: John Preuß Mattsson
* [Permalink](https://eprint.iacr.org/2024/220)
* [Download](https://eprint.iacr.org/2024/220.pdf)

### Abstract

One-way key chains or ratchets play a vital role in numerous important security protocols such as TLS 1.3, QUIC, Signal, MLS, EDHOC, and OSCORE. Despite the crucial role they play, very little is known about their security properties. This paper categorizes and examines different key chain constructions, offering a comprehensive overview of their security. Our analysis reveals notable distinctions among the number of collisions occurring within chains, between chains, and between a chain and a random set. Notably, the type of key chain used in protocols such as TLS 1.3 and Signal exhibit a significant number of weak keys, an unexpectedly high rate of key collisions surpassing birthday attack expectations, and a predictable shrinking key space susceptible to novel Time-Memory Trade-Off (TMTO) attacks with complexity $\le N^{1/3}$, which is well within the capabilities of current supercomputers and distributed systems. Consequently, the security level provided by e.g., TLS 1.3 is significantly lower than anticipated based on key sizes. To address these concerns, we analyze the aforementioned protocols and provide numerous concrete recommendations for enhancing their security, as well as guidance for future security protocol design.



## 2024/221

* Title: Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics
* Authors: Dimitris Mouris, Christopher Patton, Hannah Davis, Pratik Sarkar, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/221)
* [Download](https://eprint.iacr.org/2024/221.pdf)

### Abstract

Insight into user experience and behavior is critical to the success of large software systems and web services. Yet gaining such insights, while preserving user privacy, is a significant challenge. Recent advancements in multi-party computation have made it practical to compute verifiable aggregates over secret shared data. One important use case for these protocols is heavy hitters, where the servers compute the most popular inputs held by the users without learning the inputs themselves. The Poplar protocol (IEEE S&P 2021) focuses on this use case, but cannot support other aggregation tasks. Another such protocol, Prio (NSDI 2017), supports a wider variety of statistics but is unsuitable for heavy hitters.

We introduce Mastic, a flexible protocol for private and verifiable general-purpose statistics based on function secret sharing and zero-knowledge proofs on secret shared data. Mastic is the first to solve the more general problem of weighted heavy-hitters, enabling new use cases, not supported by Prio or Poplar. In addition, Mastic allows grouping general-purpose metrics by user attributes, such as their geographic location or browser version, without sacrificing privacy or incurring high-performance costs, which is a major improvement over Prio. We demonstrate Mastic's benefits with two real-world applications, private network error logging and browser telemetry, and compare our protocol with Prio and Poplar on a wide area network. Overall, we report over one order of magnitude performance improvement over Poplar for heavy hitters and $1.5-2\times$ improvement over Prio for attribute-based metrics.



## 2024/222

* Title: Reducing the Number of Qubits in Quantum Factoring
* Authors: Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher
* [Permalink](https://eprint.iacr.org/2024/222)
* [Download](https://eprint.iacr.org/2024/222.pdf)

### Abstract

This paper focuses on the optimization of the number of logical qubits in Shor's quantum factoring algorithm. As in previous works, we target the implementation of the modular exponentiation, which is the most costly component of the algorithm, both in qubits and operations.

In this paper, we show that using only $o(n)$ work qubits, one can obtain the first bit of the modular exponentiation output. We combine this result with May and Schlieper's truncation technique (ToSC 2022) and the Ekerå-Håstad variant of Shor's algorithm (PQCrypto 2017) to obtain a quantum factoring algorithm requiring only $n/2 + o(n)$ qubits in the case of an $n$-bit RSA modulus, while current envisioned implementations require about $2n$ qubits.

Our algorithm uses a Residue Number System and succeeds with a parametrizable probability. Being completely classical, we have implemented and tested it. Among possible trade-offs, we can reach a gate count $\mathcal{O}(n^3)$ for a depth $\mathcal{O}(n^2 \log^3 n)$, which then has to be multiplied by $\mathcal{O}(\log n)$ (the number of measurement results required by Ekerå-Håstad). Preliminary logical resource estimates suggest that this circuit could be engineered to use less than 1700 qubits and $2^{36}$ Toffoli gates, and require 60 independent runs to factor an RSA-2048 instance.



## 2024/223

* Title: Game-Theoretically Fair Distributed Sampling
* Authors: Sri Aravinda Krishnan Thyagarajan, Ke Wu, Pratik Soni
* [Permalink](https://eprint.iacr.org/2024/223)
* [Download](https://eprint.iacr.org/2024/223.pdf)

### Abstract

Cleve's celebrated result (STOC'86) showed that a strongly fair multi-party coin-toss is impossible in the presence of majority-sized coalitions. Recently, however, a fascinating line of work studied a relaxed fairness notion called \emph{game-theoretic fairness}, which guarantees that no coalition should be incentivized to deviate from the prescribed protocol.
A sequence of works has explored the feasibility of game-theoretic fairness for \emph{two-sided} coin-toss, and indeed demonstrated feasibility in the dishonest majority setting under standard cryptographic assumptions. In fact, the recent work of Wu, Asharov, and Shi (EUROCRYPT'22) completely characterized the regime where game-theoretic fairness is feasible. However, this line of work is largely restricted to two-sided coin-toss, and more precisely on a \emph{uniform} coin-toss (i.e., Bernoulli with parameter $1/2$). The only exceptions are the works on game-theoretically fair leader election, which can be viewed as a special case of uniform $n$-sided coin-toss where $n$ is the number of parties.

In this work, we \emph{initiate} the comprehensive study of game-theoretic fairness for multi-party \emph{sampling from general distributions}. In particular, for the case of $m$-sided \emph{uniform} coin-toss we give a nearly complete characterization of the regime in which game-theoretic fairness is feasible. Interestingly, contrary to standard fairness notions in cryptography, the composition of game-theoretically fair two-sided coin-toss protocols does not necessarily yield game-theoretically fair multi-sided coins. To circumvent this, we introduce new techniques compatible with game-theoretic fairness.
In particular, we give the following results:

- We give a protocol from standard cryptographic assumptions that achieves game-theoretic fairness for uniform $m$-sided coin-toss against half- or more-sized adversarial coalitions.

- To complement our protocol, we give a general impossibility result that establishes the optimality of our protocol for a broad range of parameters modulo an additive constant. Even in the worst-case, the gap between our protocol and our impossibility result is only a small constant multiplicative factor.

- We also present a game-theoretically fair protocol for \emph{any} efficiently sampleable $m$-outcome distribution in the dishonest majority setting. For instance, even for the case of $m=2$ (i.e., two-sided coin-toss), our result implies a game-theoretically fair protocol for an \emph{arbitrary} Bernoulli coin. In contrast, the work of Wu, Asharov, and Shi only focussed on a Bernoulli coin with parameter $1/2$.



## 2024/224

* Title: Amplification of Non-Interactive Zero Knowledge, Revisited
* Authors: Nir Bitansky, Nathan Geier
* [Permalink](https://eprint.iacr.org/2024/224)
* [Download](https://eprint.iacr.org/2024/224.pdf)

### Abstract

In an (α,β)-weak non-interactive zero knowledge (NIZK), the soundness error is at most α and the zero-knowledge error is at most β. Goyal, Jain, and Sahai (CRYPTO 2019) show that if α+β<1 for some constants α,β, then (α,β)-weak NIZK can be turned into fully-secure NIZK, assuming sub-exponentially-secure public-key encryption.
We revisit the problem of NIZK amplification:
– We amplify NIZK arguments assuming only polynomially-secure public-key encryption, for any constants α+β<1.
– We amplify NIZK proofs assuming only one-way functions, for any constants α+β<1.
– When the soundness error α is negligible to begin with, we can also amplify NIZK arguments assuming only one-way functions.
Our results are based on the hidden-bits paradigm, and can be viewed as a reduction from NIZK amplification to the better understood problem of pseudorandomness amplification.



## 2024/225

* Title: Universal Computational Extractors from Lattice Assumptions
* Authors: Yilei Chen, Xinyu Mao
* [Permalink](https://eprint.iacr.org/2024/225)
* [Download](https://eprint.iacr.org/2024/225.pdf)

### Abstract

Universal computational extractors (UCEs), introduced by Bellare, Hoang, and Keelveedhi [BHK13], can securely replace random oracles in various applications, including KDM-secure encryption, deterministic encryption, RSA-OAEP, etc. Despite its usefulness, constructing UCE in the standard model is challenging. The only known positive result is given by Brzuska and Mittelbach [BM14], who construct UCE with strongly computationally unpredictable one-query source assuming indistinguishability obfuscation (iO) and the existence of point obfuscators with auxiliary input (AIPO); they also construct UCE with $q$-query sources assuming iO and composable AIPO. On the other hand, Brzuska, Farshim, and Mittelbach [BFM14] show that the most potent version of UCE does not exist, assuming the existence of iO.

In this paper, we construct UCE with strongly computationally unpredictable one-query sources from lattice assumptions based on the GGH15 encodings [GGH15], without using iO. Security is proven under the following assumptions: (1) LWE with subexponential hardness; (2) evasive LWE, which is a new assumption proposed by Wee [Wee22]; (3) the existence of AIPO in NC1. Our UCE directly implies a universal hardcore function that outputs a polynomial number of bits, giving the first lattice-based universal hardcore function without using iO. We also put forth a new primitive called obliviously programmable function as an intermediate abstraction; it makes our analysis more modularized and could be of independent interest



## 2024/226

* Title: Attribute-based Keyed (Fully) Homomorphic Encryption
* Authors: Keita Emura, Shingo Sato, Atsushi Takayasu
* [Permalink](https://eprint.iacr.org/2024/226)
* [Download](https://eprint.iacr.org/2024/226.pdf)

### Abstract

Keyed homomorphic public key encryption (KHPKE) is a variant of homomorphic public key encryption, where only users who have a homomorphic evaluation key can perform a homomorphic evaluation. Then, KHPKE satisfies the CCA2 security against users who do not have a homomorphic evaluation key, while it satisfies the CCA1 security against users who have the key. Thus far, several KHPKE schemes have been proposed under the standard Diffie-Hellman-type assumptions and keyed fully homomorphic encryption (KFHE) schemes have also been proposed from lattices. As a natural extension, there is an identity-based variant of KHPKE; however, the security is based on a $q$-type assumption and there are no attribute-based variants. Moreover, there are no identity-based variants of KFHE schemes due to the complex design of the known KFHE schemes. In this paper, we obtain two results for constructing the attribute-based variants. First, we propose an attribute-based KFHE (ABKFHE) scheme from lattices. We start by designing the first KFHE scheme secure solely under the LWE assumption in the standard model. Since the design is conceptually much simpler than known KFHE schemes, we just replace their building blocks with attribute-based ones and obtain the proposed ABKFHE schemes. Next, we propose an efficient attribute-based KHPKE (ABKHE) scheme from a pair encoding scheme (PES). Due to the benefit of PES, we obtain various ABKHE schemes that contain the first identity-based KHPKE scheme secure under the standard $k$-linear assumption and the first pairing-based ABKHE schemes supporting more expressive predicates.



## 2024/227

* Title: Adaptively Sound Zero-Knowledge SNARKs for UP
* Authors: Surya Mathialagan, Spencer Peters, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/227)
* [Download](https://eprint.iacr.org/2024/227.pdf)

### Abstract

We study succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) for the class $\mathsf{UP}$ in the reusable designated verifier model. $\mathsf{UP}$ is an expressive subclass of $\mathsf{NP}$ consisting of all $\mathsf{NP}$ languages where each instance has at most one witness; a designated verifier SNARG (dvSNARG) is one where verification of the SNARG proof requires a private verification key; and such a dvSNARG is reusable if soundness holds even against a malicious prover with oracle access to the (private) verification algorithm.

Our main results are as follows.

(1) A reusably and adaptively sound zero-knowledge (zk) dvSNARG for $\mathsf{UP}$, from subexponential LWE and evasive LWE (a relatively new but popular variant of LWE). Our SNARGs achieve very short proofs of length $(1 + o(1)) \cdot \lambda$ bits for $2^{-\lambda}$ soundness error.

(2) A generic transformation that lifts any ``Sahai-Waters-like'' (zk) SNARG to an adaptively sound (zk) SNARG, in the designated-verifier setting. In particular, this shows that the Sahai-Waters SNARG for $\mathsf{NP}$ is adaptively sound in the designated verifier setting, assuming subexponential hardness of the underlying assumptions. The resulting SNARG proofs have length $(1 + o(1)) \cdot \lambda$ bits for $2^{-\lambda}$ soundness error. Our result sidesteps the Gentry-Wichs barrier for adaptive soundness by employing an exponential-time security reduction.

(3) A generic transformation, building on the work of Campanelli, Ganesh, that lifts any adaptively sound (zk) SNARG for $\mathsf{UP}$ to an adaptively sound (zk) SNARK for $\mathsf{UP}$, while preserving zero-knowledge. The resulting SNARK achieves the strong notion of black-box extraction. There are barriers to achieving such SNARKs for all of $\mathsf{NP}$ from falsifiable assumptions, so our restriction to $\mathsf{UP}$ is, in a sense, necessary.

Applying (3) to our SNARG for $\mathsf{UP}$ from evasive LWE (1), we obtain a reusably and adaptively sound designated-verifier zero-knowledge SNARK for $\mathsf{UP}$ from subexponential LWE and evasive LWE. Moreover, applying both (2) and (3) to the Sahai-Waters SNARG, we obtain the same result from LWE, subexponentially secure one-way functions, and subexponentially secure indistinguishability obfuscation. Both constructions have succinct proofs of size $\mathsf{poly}(\lambda)$. These are the first SNARK constructions (even in the designated-verifier setting) for a non-trivial subset of $\mathsf{NP}$ from (sub-exponentially) falsifiable assumptions.



## 2024/228

* Title: On the Untapped Potential of the Quantum FLT-based Inversion
* Authors: Ren Taguchi, Atsushi Takayasu
* [Permalink](https://eprint.iacr.org/2024/228)
* [Download](https://eprint.iacr.org/2024/228.pdf)

### Abstract

Thus far, several papers estimated concrete quantum resources of Shor’s algorithm for solving a binary elliptic curve discrete logarithm problem. In particular, the complexity of computing quantum inversions over a binary field F2n is dominant when running the algorithm, where n is a degree of a binary elliptic curve. There are two major methods for quantum inversion, i.e., the quantum GCD-based inversion and the quantum FLT-based inversion. Among them, the latter method is known to require more qubits; however, the latter one is valuable since it requires much fewer Toffoli gates and less depth. When n = 571, Kim-Hong’s quantum GCD-based inversion algorithm (Quantum Information Processing 2023) and Taguchi-Takayasu’s quantum FLT-based inversion algorithm (CT-RSA 2023) require 3, 473 qubits and 8, 566 qubits, respectively. In contrast, for the same n = 571, the latter algorithm requires only 2.3% of Toffoli gates and 84% of depth compared to the former one. In this paper, we modify Taguchi-Takayasu’s quantum FLT-based inversion algorithm to reduce the required qubits. While Taguchi-Takayasu’s FLT-based inversion algorithm takes an addition chain for n−1 as input and computes a sequence whose number is the same as the length of the chain, our proposed algorithm employs an uncomputation step and stores a shorter one. As a result, our proposed algorithm requires only 3, 998 qubits for n = 571, which is only 15% more than Kim-Hong’s GCD-based inversion algorithm. Furthermore, our proposed algorithm preserves the advantage of FLT-based inversion since it requires only 3.7% of Toffoli gates and 77% of depth compared to Kim-Hong’s GCD-based inversion algorithm for n = 571.



## 2024/229

* Title: Strong Batching for Non-Interactive Statistical Zero-Knowledge
* Authors: Changrui Mu, Shafik Nassar, Ron D. Rothblum, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/229)
* [Download](https://eprint.iacr.org/2024/229.pdf)

### Abstract

A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by a factor of $k$. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for $S$ possible?

Recent works by Kaslasi et al. (TCC 2020, Eurocrypt 2021) show that any problem possessing a non-interactive statistical zero-knowledge proof (NISZK) has a non-trivial statistical zero-knowledge batch verification protocol. Their results had two major limitations: (1) to batch verify $k$ inputs of size $n$ each, the communication in their batch protocol is roughly $\textrm{poly}(n,\log{k})+O(k)$, which is better than the naive cost of $k \cdot \textrm{poly}(n)$ but still scales linearly with $k$, and, (2) the batch protocol requires $\Omega(k)$ rounds of interaction.

In this work we remove both of these limitations by showing that any problem in $NISZK$ has a non-interactive statistical zero-knowledge batch verification protocol with communication $\textrm{poly}(n,\log{k})$.



## 2024/230

* Title: Analysis of Layered ROLLO-I
* Authors: Seongtaek Chee, Kyung Chul Jeong, Tanja Lange, Nari Lee, Alex Pellegrini, Hansol Ryu
* [Permalink](https://eprint.iacr.org/2024/230)
* [Download](https://eprint.iacr.org/2024/230.pdf)

### Abstract

We analyse Layered ROLLO-I, a code-based cryptosystem submitted to the Korean post quantum cryptography competition, of which four versions have been proposed. We show that the first two versions do not provide the claimed security against rank decoding attacks and give reductions to small instances of ROLLO-I for which such attacks are even more effective. Finally, we provide two efficient message recovery attacks, affecting every security level of the first three versions of Layered ROLLO-I and security levels 128 and 192 of the fourth version.



## 2024/231

* Title: Need for Speed: Leveraging the Power of Functional Encryption for Resource-Constrained Devices
* Authors: Eugene Frimpong, Alexandros Bakas, Camille Foucault, Antonis Michalas
* [Permalink](https://eprint.iacr.org/2024/231)
* [Download](https://eprint.iacr.org/2024/231.pdf)

### Abstract

Functional Encryption (FE) is a cutting-edge cryptographic technique that enables a user with a specific functional decryption key to determine a certain function of encrypted data without gaining access to the underlying data. Given its potential and the fact that FE is still a relatively new field, we set out to investigate how it could be applied to resource-constrained environments. This work presents what we believe to be the first lightweight FE scheme explicitly designed for resource-constrained devices. We also propose a use case protocol that demonstrates how our scheme can secure an Internet of Things (IoT) architecture where relevant devices collect data and securely deliver them to a storage server, where an analyst can request access to the encrypted data. Finally, we conduct thorough experiments on two commercially available resource-constrained devices to provide compelling evidence of our approach's practicality and efficiency. Although the results of our evaluations show that there is room for improvement in the proposed scheme, this work represents one of the first attempts to apply FE to the IoT setting that can directly impact people's daily lives and the everyday operations of organizations.



## 2024/232

* Title: On the Security of Nova Recursive Proof System
* Authors: Hyeonbum Lee, Jae Hong Seo
* [Permalink](https://eprint.iacr.org/2024/232)
* [Download](https://eprint.iacr.org/2024/232.pdf)

### Abstract

Nova is a new type of recursive proof system that uses folding scheme as its core building block. This brilliant idea of folding relations can significantly reduce recursion overhead. In this paper, we study some issues related to Nova's soundness proof that relies on the soundness of the folding scheme in a recursive manner.

First, its proof strategy, due to its recursive nature, inevitably expands the running time of the recursive extractor polynomially for each additional recursive step. This constrains Nova's soundness model to have only logarithmically bounded recursive steps, and so the soundness proof in this limited model does not guarantee the soundness for linear rounds in the security parameter, e.g., 128 rounds for 128 bit security. On the other hand, there are no known attacks on arbitrary depth recursion of Nova, leaving a gap between theoretical security guarantees and real-world attacks. We aim to bridge this gap in two opposite directions. In a negative direction, we present a recursive proof system that is unforgeable in a log-round model but forgeable if used in linear rounds. This shows that the soundness proof in the log-round model might tell nothing about real-world uses that require linearly long rounds. In a positive direction, we show that when Nova uses a specific group-based folding scheme, its knowledge soundness over polynomial rounds can be proven in the algebraic group model with our refinements. To the best of our knowledge, this is the first result to show Nova's polynomial rounds soundness.

Second, the folding scheme is converted non-interactively via the Fiat-Shamir transformation and then arithmetized into R1CS. Therefore, the soundness of Nova using the non-interactive folding scheme essentially relies on the heuristic random oracle instantiation in the standard model. In our new soundness proof for Nova in the algebraic group model, we replace this heuristics with a cryptographic hash function with special property. We view this hash function as an independent object of interest and expect it to help further understand the soundness of Nova.



## 2024/233

* Title: Cayley hashing with cookies
* Authors: Vladimir Shpilrain, Bianca Sosnovski
* [Permalink](https://eprint.iacr.org/2024/233)
* [Download](https://eprint.iacr.org/2024/233.pdf)

### Abstract

Cayley hash functions are based on a simple idea of using a pair of semigroup elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the semigroup. The main advantage of Cayley hash functions compared to, say, hash functions in the SHA family is that when an already hashed document is amended, one does not have to hash the whole amended document all over again, but rather hash just the amended part and then multiply the result by the hash of the original document. Some authors argued that this may be a security hazard, specifically that this property may facilitate finding a second preimage by splitting a long bit string into shorter pieces. In this paper, we offer a way to get rid of this alleged disadvantage and keep the advantages at the same time. We call this method ``Cayley hashing with cookies" using terminology borrowed from the theory of random walks in a random environment. For the platform semigroup, we use $2\times 2$ matrices over $F_p$.



## 2024/234

* Title: Bare PAKE: Universally Composable Key Exchange from just Passwords
* Authors: Manuel Barbosa, Kai Gellert, Julia Hesse, Stanislaw Jarecki
* [Permalink](https://eprint.iacr.org/2024/234)
* [Download](https://eprint.iacr.org/2024/234.pdf)

### Abstract

In the past three decades, an impressive body of knowledge has been built around secure and private password authentication. In particular, secure password-authenticated key exchange (PAKE) protocols require only minimal overhead over a classical Diffie-Hellman key exchange. PAKEs are also known to fulfill strong composable security guarantees that capture many password-specific concerns such as password correlations or password mistyping, to name only a few. However, to enjoy both round-optimality and strong security, applications of PAKE protocols must provide unique session and participant identifiers. If such identifiers are not readily available, they must be agreed upon at the cost of additional communication flows, a fact which has been met with incomprehension among practitioners, and which hindered the adoption of provably secure password authentication in practice.

In this work, we resolve this issue by proposing a new paradigm for truly password-only yet securely composable PAKE, called bare PAKE. We formally prove that two prominent PAKE protocols, namely CPace and EKE, can be cast as bare PAKEs and hence do not require pre-agreement of anything else than a password. Our bare PAKE modeling further allows us to investigate a novel "reusability" property of PAKEs, i.e., whether $n^2$ pairwise keys can be exchanged from only $n$ messages, just as the Diffie-Hellman non-interactive key exchange can do in a public-key setting. As a side contribution, this add-on property of bare PAKEs leads us to observe that some previous PAKE constructions relied on unnecessarily strong, "reusable" building blocks. By showing that ``non-reusable'' tools suffice for standard PAKE, we open a new path towards round-optimal post-quantum secure password-authenticated key exchange.



## 2024/235

* Title: Pseudorandom Error-Correcting Codes
* Authors: Miranda Christ, Sam Gunn
* [Permalink](https://eprint.iacr.org/2024/235)
* [Download](https://eprint.iacr.org/2024/235.pdf)

### Abstract

We construct pseudorandom error-correcting codes (or simply pseudorandom codes), which are error-correcting codes with the property that any polynomial number of codewords are pseudorandom to any computationally-bounded adversary. Efficient decoding of corrupted codewords is possible with the help of a decoding key.

We build pseudorandom codes that are robust to substitution and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically, pseudorandomness is based on either $2^{O(\sqrt{n})}$-hardness of LPN, or polynomial hardness of LPN and the planted XOR problem at low density.

As our primary application of pseudorandom codes, we present an undetectable watermarking scheme for outputs of language models that is robust to cropping and a constant rate of random substitutions and deletions. The watermark is undetectable in the sense that any number of samples of watermarked text are computationally indistinguishable from text output by the original model. This is the first undetectable watermarking scheme that can tolerate a constant rate of errors.

Our second application is to steganography, where a secret message is hidden in innocent-looking content. We present a constant-rate stateless steganography scheme with robustness to a constant rate of substitutions. Ours is the first stateless steganography scheme with provable steganographic security and any robustness to errors.



## 2024/236

* Title: Public-Key Cryptography through the Lens of Monoid Actions
* Authors: Hart Montgomery, Sikhar Patranabis
* [Permalink](https://eprint.iacr.org/2024/236)
* [Download](https://eprint.iacr.org/2024/236.pdf)

### Abstract

We show that key exchange and two-party computation are exactly equivalent to monoid actions with certain structural and hardness properties. To the best of our knowledge, this is the first "natural" characterization of the mathematical structure inherent to any key exchange or two-party computation protocol, and the first explicit proof of the necessity of mathematical structure for public-key cryptography. We then utilize these characterizations to show a new black-box separation result, while also achieving a simpler and more general version of an existing black-box separation result. Concretely, we obtain the following results:

- Two-Party Key Exchange. We show that that any two-party noninteractive key exchange protocol is equivalent to the existence of an abelian monoid equipped with a natural hardness property, namely (distributional) unpredictability. More generally, we show that any $k$-round (two-party) key exchange protocol is essentially equivalent to the existence of a (distributional) unpredictable monoid with certain commutator-like properties. We then use a generic version of this primitive to show a simpler and more general version of Rudich's (Crypto '91) black-box separation of $k$-round and $(k+1)$-round key exchange.

- Two-Party Computation. We show that any maliciously secure two-party computation protocol is also equivalent to a monoid action with commutator-like properties and certain hardness guarantees. We then use a generic version of this primitive to show a black-box separation between $k$-round semi-honest secure two-party computation and $(k+1)$-round maliciously secure two-party computation. This yields the first black-box separation (to our knowledge) between $k$-round and $(k+1)$-round maliciously secure two-party computation protocols.


We believe that modeling cryptographic primitives as mathematical objects (and our approach of using such modeling for black-box separations) may have many other potential applications and uses in understanding what sort of assumptions and mathematical structure are necessary for certain cryptoprimitives.



## 2024/237

* Title: Collusion-Resilience in Transaction Fee Mechanism Design
* Authors: Hao Chung, Tim Roughgarden, Elaine Shi
* [Permalink](https://eprint.iacr.org/2024/237)
* [Download](https://eprint.iacr.org/2024/237.pdf)

### Abstract

Users bid in a transaction fee mechanism (TFM) to get their transactions included and confirmed by a blockchain protocol. Roughgarden (EC'21) initiated the formal treatment of TFMs and proposed three requirements: user incentive compatibility (UIC), miner incentive compatibility (MIC), and a form of collusion-resilience called OCA-proofness. Ethereum's EIP-1559 mechanism satisfies all three properties simultaneously when there is no contention between transactions, but loses the UIC property when there are too many eligible transactions to fit in a single block. Chung and Shi (SODA'23) considered an alternative notion of collusion-resilience, called c-side-constract-proofness (c-SCP), and showed that, when there is contention between transactions, no TFM can satisfy UIC, MIC, and c-SCP for any c at least 1. OCA-proofness asserts that the users and a miner should not be able to "steal from the protocol" and is intuitively weaker than the c-SCP condition, which stipulates that a coalition of a miner and a subset of users should not be able to profit through strategic deviations (whether at the expense of the protocol or of the users outside the coalition).

Our main result is the first proof that, when there is contention between transactions, no (possibly randomized) direct-revelation TFM satisfies UIC, MIC, and OCA-proofness. This result resolves the main open question in Roughgarden(EC'21). We also suggest several relaxations of the basic model that allow our impossibility result to be circumvented.



## 2024/238

* Title: A Single Trace Fault Injection Attack on Hedged CRYSTALS-Dilithium
* Authors: Sönke Jendral
* [Permalink](https://eprint.iacr.org/2024/238)
* [Download](https://eprint.iacr.org/2024/238.pdf)

### Abstract

CRYSTALS-Dilithium is a post-quantum secure digital signature algorithm currently being standardised by NIST. As a result, devices making use of CRYSTALS-Dilithium will soon become generally available and be deployed in various environments. It is thus important to assess the resistance of CRYSTALS-Dilithum implementations to physical attacks.
In this paper, we present an attack on a CRYSTALS-Dilithium implementation in hedged mode in ARM Cortex-M4 using fault injection. Voltage glitching is performed to skip computation of a seed during the generation of the signature. We identified settings that consistently skip the desired function without crashing the device. After the successful fault injection, the resulting signature allows for the extraction of the secret key vector. Our attack succeeds with probability 0.582 in a single trace.
We also propose countermeasures against the presented attack.



## 2024/239

* Title: Simulation-Secure Threshold PKE from Standard (Ring-)LWE
* Authors: Hiroki Okada, Tsuyoshi Takagi
* [Permalink](https://eprint.iacr.org/2024/239)
* [Download](https://eprint.iacr.org/2024/239.pdf)

### Abstract

Threshold public key encryption (ThPKE) is PKE that can be decrypted by collecting "partial decryptions" from t (≤ N) out of N parties. ThPKE based on the learning with errors problem (LWE) is particularly important because it can be extended to threshold fully homomorphic encryption (ThFHE). ThPKE and ThFHE are fundamental tools for constructing multiparty computation (MPC) protocols: In 2023, NIST initiated a project (NIST IR 8214C) to establish guidelines for implementing threshold cryptosystems. Because MPC often requires simulation-security (SS), ThPKE schemes that satisfy SS (SS-ThPKE) are also important. Recently, Micciancio and Suhl (ePrint 2023/1728) presented an efficient SS-ThPKE scheme based on LWE with a polynomial modulus. However, the scheme requires to use a nonstandard problem called “known-norm LWE” for the security proof because the norm ∥e∥ of the error of the public key is leaked from the partial decryptions. This leads to the following two challenges: 1) The construction based on LWE incurs a security loss of approximately 13 bits for 128-bit security. 2) No construction based on (standard) Ring-LWE has been presented. In this paper, we address both of these challenges: we propose an efficient SS-ThPKE scheme whose security is (directly) reduced from standard (Ring-)LWE with a polynomial modulus. The core technique of our construction is what we call "error sharing". We distribute shares of a small error ζ via secret sharing, and use them to prevent leakage of ∥e∥ from partial decryptions.



## 2024/240

* Title: Implementation of Cryptanalytic Programs Using ChatGPT
* Authors: Nobuyuki Sugio
* [Permalink](https://eprint.iacr.org/2024/240)
* [Download](https://eprint.iacr.org/2024/240.pdf)

### Abstract

Large language models (LLMs), exemplified by the advanced AI tool ChatGPT in 2023, have demonstrated remarkable capabilities in generating sentences, images, and program codes, driven by their development from extensive datasets. With over 100 million users worldwide, ChatGPT stands out as a leader among LLMs. Previous studies have shown its proficiency in generating program source codes for the symmetric-key block ciphers AES, CHAM, and ASCON. This study ventures into the implementation of cryptanalytic program source codes for a lightweight block cipher using ChatGPT, exploring its potential and limitations in the field of cryptography.



## 2024/241

* Title: Generalized Adaptor Signature Scheme: From Two-Party to N-Party Settings
* Authors: Kaisei Kajita, Go Ohtake, Tsuyoshi Takagi
* [Permalink](https://eprint.iacr.org/2024/241)
* [Download](https://eprint.iacr.org/2024/241.pdf)

### Abstract

Adaptor signatures have attracted attention as a tool to ad-dress scalability and interoperability issues in blockchain applications, for example, such as atomic swaps for exchanging di˙erent cryptocur-rencies. Adaptor signatures can be constructed by extending of common digital signature schemes that both authenticate a message and disclose a secret witness to a speci˝c party. In Asiacrypt 2021, Aumayr et al. formulated the two-party adaptor signature as an independent crypto-graphic primitive. In this study, we extend the their adaptor signature scheme formulation to N party adaptor signature scheme, present its generic construction, and de˝ne the security to be satis˝ed. Next, we present a concrete construction based on Schnorr signatures and discuss the security properties.



## 2024/242

* Title: Perfectly-Secure MPC with Constant Online Communication Complexity
* Authors: Yifan Song, Xiaxi Ye
* [Permalink](https://eprint.iacr.org/2024/242)
* [Download](https://eprint.iacr.org/2024/242.pdf)

### Abstract

In this work, we study the communication complexity of perfectly secure MPC protocol with guaranteed output delivery against $t=(n-1)/3$ corruptions. The previously best-known result in this setting is due to Goyal, Liu, and Song (CRYPTO, 2019) which achieves $O(n)$ communication per gate, where $n$ is the number of parties.

On the other hand, in the honest majority setting, a recent trend in designing efficient MPC protocol is to rely on packed Shamir sharings to speed up the online phase. In particular, the work by Escudero et al. (CCS 2022) gives the first semi-honest protocol that achieves a constant communication overhead per gate across all parties in the online phase while maintaining overall $O(n)$ communication per gate. We thus ask the following question: ``Is it possible to construct a perfectly secure MPC protocol with GOD such that the online communication per gate is $O(1)$ while maintaining overall $O(n)$ communication per gate?''

In this work, we give an affirmative answer by providing an MPC protocol with communication complexity $O(|C|+\mathsf{Depth}\cdot n+n^5)$ elements for the online phase, and $O(|C|\cdot n+\mathsf{Depth}\cdot n^2 + n^4)$ elements for the preprocessing phase, where $|C|$ is the circuit size and $\mathsf{Depth}$ is the circuit depth.



## 2024/243

* Title: Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience
* Authors: Vipul Goyal, Chen-Da Liu-Zhang, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/243)
* [Download](https://eprint.iacr.org/2024/243.pdf)

### Abstract

Secure multi-party computation (MPC) allows a set of $n$ parties to jointly compute a function over their private inputs.
The seminal works of Ben-Or, Canetti and Goldreich [STOC '93] and Ben-Or, Kelmer and Rabin [PODC '94] settled the feasibility of MPC over asynchronous networks. Despite the significant line of work devoted to improving the communication complexity, current protocols with information-theoretic security and optimal resilience $t<n/3$ communicate $\Omega(n^4C)$ field elements for a circuit with $C$ multiplication gates. In contrast, synchronous MPC protocols with $\Omega(nC)$ communication have long been known.

In this work we make progress towards closing this gap.
We provide a novel MPC protocol that makes black-box use of an asynchronous complete secret-sharing (ACSS) protocol, where the cost per multiplication reduces to the cost of distributing a constant number of sharings via ACSS, improving a linear factor over the state of the art by Choudhury and Patra [IEEE Trans. Inf. Theory '17].

Instantiating ACSS with the protocol by Choudhury and Patra [J. Crypto '23] we achieve an MPC protocol with $\mathcal{O}(n^3C)$ communication. Moreover, with a recent concurrent work achieving ACSS with linear cost per sharing, we achieve an MPC with $\mathcal{O}(nC)$ communication.



## 2024/244

* Title: Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Problems
* Authors: Alessandro Budroni, Jesús-Javier Chi-Domínguez, Giuseppe D'Alconzo, Antonio J. Di Scala, Mukul Kulkarni
* [Permalink](https://eprint.iacr.org/2024/244)
* [Download](https://eprint.iacr.org/2024/244.pdf)

### Abstract

The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with additional properties, including linkable ring, group, and threshold signatures, has been proposed. These novel constructions introduce relaxed versions of LCE (and MCE), wherein multiple samples share the same secret equivalence. Despite their significance, these variations have often lacked a thorough security analysis, being assumed to be as challenging as their original counterparts. Addressing this gap, our work delves into the sample complexity of LCE and MCE --- precisely, the sufficient number of samples required for efficient recovery of the shared secret equivalence. Our findings reveal, for instance, that one shouldn't use the same secret twice in the LCE setting since this enables a polynomial time (and memory) algorithm to retrieve the secret. Consequently, our results unveil the insecurity of two advanced signatures based on variants of the LCE Problem.



## 2024/245

* Title: Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience
* Authors: Xiaoyu Ji, Junru Li, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/245)
* [Download](https://eprint.iacr.org/2024/245.pdf)

### Abstract

Secure multiparty computation (MPC) allows a set of $n$ parties to jointly compute a function on their private inputs. In this work, we focus on the information-theoretic MPC in the \emph{asynchronous network} setting with optimal resilience ($t<n/3$). The best-known result in this setting is achieved by Choudhury and Patra [J. Cryptol '23], which requires $O(n^4\kappa)$ bits per multiplication gate, where $\kappa$ is the size of a field element.

An asynchronous complete secret sharing (ACSS) protocol allows a dealer to share a batch of Shamir sharings such that all parties eventually receive their shares. ACSS is an important building block in AMPC. The best-known result of ACSS is due to Choudhury and Patra [J. Cryptol '23], which requires $O(n^3\kappa)$ bits per sharing. On the other hand, in the synchronous setting, it is known that distributing Shamir sharings can be achieved with $O(n\kappa)$ bits per sharing. There is a gap of $n^2$ in the communication between the synchronous setting and the asynchronous setting.

Our work closes this gap by presenting the first ACSS protocol that achieves $O(n\kappa)$ bits per sharing. When combined with the compiler from ACSS to AMPC by Choudhury and Patra [IEEE Trans. Inf. Theory '17], we obtain an AMPC with $O(n^2\kappa)$ bits per multiplication gate, improving the previously best-known result by a factor of $n^2$. Moreover, with a concurrent work that improves the compiler by Choudhury and Patra by a factor of $n$, we obtain the first AMPC with $O(n\kappa)$ bits per multiplication gate.



## 2024/246

* Title: OCash: Fully Anonymous Payments between Blockchain Light Clients
* Authors: Adam Blatchley Hansen, Jesper Buus Nielsen, Mark Simkin
* [Permalink](https://eprint.iacr.org/2024/246)
* [Download](https://eprint.iacr.org/2024/246.pdf)

### Abstract

We study blockchain-based provably anonymous payment systems between light clients. Such clients interact with the blockchain through full nodes, who can see what the light clients read and write. The goal of our work is to enable light clients to perform anonymous payments, while maintaining privacy even against the full nodes through which they interact with the blockchain.

We formalize the problem in the universal composability model and present a provably secure solution to it. In comparison to existing works, we are the first ones that simultaneously provide strong anonymity guarantees, provable security, and anonymity with respect to the full nodes. Along the way, we make several contributions that may be of independent interest.

We define and construct efficient compressible randomness beacons, which produce unpredictable values in regular intervals and allow for storing all published values in a short digest. We define and construct anonymous-coin friendly encryption schemes and we show how they can be used within anonymous payment systems. We define and construct strongly oblivious read-once map, which can be seen as a special data structure that needs to satisfy a stronger notion of obliviousness than what is usually considered. We present a new approach, which is compatible with light clients, for mitigating double-spending attacks in anonymous cryptocurrencies.



## 2024/247

* Title: Fault-Resistant Partitioning of Secure CPUs for System Co-Verification against Faults
* Authors: Simon Tollec, Vedad Hadžić, Pascal Nasahl, Mihail Asavoae, Roderick Bloem, Damien Couroussé, Karine Heydemann, Mathieu Jan, Stefan Mangard
* [Permalink](https://eprint.iacr.org/2024/247)
* [Download](https://eprint.iacr.org/2024/247.pdf)

### Abstract

To assess the robustness of CPU-based systems against fault injection attacks, it is necessary to analyze the consequences of the fault propagation resulting from the intricate interaction between the software and the processor. However, current formal methodologies that combine both hardware and software aspects experience scalability issues, primarily due to the use of bounded verification techniques.
This work formalizes the notion of $k$-fault resistant partitioning as an inductive solution to this fault propagation problem when assessing redundancy-based hardware countermeasures to fault injections. Proven security guarantees can then reduce the remaining hardware attack surface to consider in a combined analysis with the software, enabling a full co-verification methodology. As a result, we formally verify the robustness of the hardware lockstep countermeasure of the OpenTitan secure element to single bit-flip injections. Besides that, we demonstrate that previously intractable problems, such as analyzing the robustness of OpenTitan running a secure boot process, can now be solved by a co-verification methodology that leverages a $k$-fault resistant partitioning. We also report a potential exploitation of the register file vulnerability in two other software use cases. Finally, we provide a security fix for the register file, verify its robustness, and integrate it into the OpenTitan project.



## 2024/248

* Title: FRIDA: Data Availability Sampling from FRI
* Authors: Mathias Hall-Andersen, Mark Simkin, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2024/248)
* [Download](https://eprint.iacr.org/2024/248.pdf)

### Abstract

As blockchains like Ethereum continue to grow, clients with limited resources can no longer store the entire chain.
Light nodes that want to use the blockchain, without verifying that it is in a good state overall, can just download the block headers without the corresponding block contents.
As those light nodes may eventually need some of the block contents, they would like to ensure that they are in principle available.

Data availability sampling, introduced by Bassam et al., is a process that allows light nodes to check the availability of data without download it.
In a recent effort, Hall-Andersen, Simkin, and Wagner have introduced formal definitions and analyzed several constructions.
While their work thoroughly lays the formal foundations for data availability sampling, the constructions are either prohibitively expensive, use a trusted setup, or have a download complexity for light clients scales with a square root of the data size.

In this work, we make a significant step forward by proposing an efficient data availability sampling scheme without a trusted setup and only polylogarithmic overhead.
To this end, we find a novel connection with interactive oracle proofs of proximity (IOPPs).
Specifically, we prove that any IOPP meeting an additional consistency criterion can be turned into an erasure code commitment, and then, leveraging a compiler due to Hall-Andersen, Simkin, and Wagner, into a data availability sampling scheme.
This new connection enables data availability to benefit from future results on IOPPs.
We then show that the widely used FRI IOPP satisfies our consistency criterion and demonstrate that the resulting data availability sampling scheme outperforms the state-of-the-art asymptotically and concretely in multiple parameters.



## 2024/249

* Title: Robust Additive Randomized Encodings from IO and Pseudo-Non-linear Codes
* Authors: Nir Bitansky, Sapir Freizeit
* [Permalink](https://eprint.iacr.org/2024/249)
* [Download](https://eprint.iacr.org/2024/249.pdf)

### Abstract

Additive randomized encodings (ARE), introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), reduce the computation of a k-party function $f (x_1, . . . , x_k )$ to locally computing encodings $\hat{x}_i$ of each input xi and then adding them together over some Abelian group into an output encoding $\hat{y} = ∑ \hat{x}_i$, which reveals nothing but the result. In robust ARE (RARE) the sum of any subset of $\hat{x}_i$, reveals only the residual function obtained by restricting the corresponding inputs. The appeal of (R)ARE comes from the simplicity of the online part of the computation involving only addition, which yields for instance non-interactive multi-party computation in the shuffle model where messages from different parties are anonymously shuffled. Halevi, Ishai, Kushilevitz, and Rabin constructed ARE from standard assumptions and RARE in the ideal obfuscation model, leaving open the question of whether RARE can be constructed in the plain model.
We construct RARE in the plain model from indistinguishability obfuscation, which is necessary, and a new primitive that we call pseudo-non-linear codes. We provide two constructions of this primitive assuming either Learning with Errors or Decision Diffie Hellman. A bonus feature of our construction is that it is online succinct. Specifically, encodings $\hat{x}_i$ can be decomposed to offline parts $\hat{z}_i$ that can be sent directly to the evaluator and short online parts $\hat{g}_i$ that are added together.



## 2024/250

* Title: Exploring the Six Worlds of Gröbner Basis Cryptanalysis: Application to Anemoi
* Authors: Katharina Koschatko, Reinhard Lüftenegger, Christian Rechberger
* [Permalink](https://eprint.iacr.org/2024/250)
* [Download](https://eprint.iacr.org/2024/250.pdf)

### Abstract

Gröbner basis cryptanalysis of hash functions and ciphers, and their underlying permutations, has seen renewed interest recently. Anemoi (Crypto'23) is a permutation-based hash function that is arithmetization-friendly, i.e., efficient for a variety of arithmetizations used in zero-knowledge proofs. In this paper, exploring both theoretical bounds as well as experimental validation, we present new complexity estimates for Gröbner basis attacks on the Anemoi permutation over prime fields.
We cast our findings in what we call the six worlds of Gröbner basis cryptanalysis. As an example, keeping the same security arguments of the design, we conclude that at least $23 /45$ instead of $17 / 33$ rounds would need to be used for $128 / 256$-bit security before adding a security margin.



## 2024/251

* Title: Communication-Optimal Convex Agreement
* Authors: Diana Ghinea, Chen-Da Liu-Zhang, Roger Wattenhofer
* [Permalink](https://eprint.iacr.org/2024/251)
* [Download](https://eprint.iacr.org/2024/251.pdf)

### Abstract

Byzantine Agreement (BA) allows a set of $n$ parties to agree on a value even when up to $t$ of the parties involved are corrupted.
While previous works have shown that, for $\ell$-bit inputs, BA can be achieved with the optimal communication complexity $\mathcal{O}(\ell n)$ for sufficiently large $\ell$, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications.

This gave rise to the notion of Convex Agreement (CA), introduced by Vaidya and Garg [PODC'13], which requires the honest parties' outputs to be in the convex hull of the honest inputs. Unfortunately, all existing CA protocols incur a communication complexity of at least $\Omega(\ell n^2)$.
In this work, we introduce the first CA protocol with the optimal communication of $\mathcal{O}(\ell n)$ bits for inputs in $\mathbb{Z}$ of size $\ell = \Omega(\kappa \cdot n^2 \log n)$, where $\kappa$ is the security parameter.



## 2024/252

* Title: Short Signatures from Regular Syndrome Decoding, Revisited
* Authors: Dung Bui, Eliana Carozza, Geoffroy Couteau, Dahmun Goudarzi, Antoine Joux
* [Permalink](https://eprint.iacr.org/2024/252)
* [Download](https://eprint.iacr.org/2024/252.pdf)

### Abstract

We revisit the construction of signature scheme using the MPC-in-the-head paradigm, and focus in particular on constructions from the regular syndrome decoding assumption, a well-known variant of the syndrome decoding assumption. We obtain two main contributions:

– We observe that previous signatures in the MPC-in-the-head paradigm must rely on a salted version of the GGM puncturable pseudorandom function (PPRF) to avoid collision attacks. We design a new efficient PPRF construction provably secure in the multi-instance setting. The security analysis of our PPRF, in the ideal cipher model, is quite involved and forms a core technical contribution of our work. While previous constructions had to rely on a hash function, our construction uses only a fixed-key block cipher and is considerably more efficient as a result. Our improved PPRF can be used to speed up many MPC-in-the-head signatures, and illustrate it on two signatures: the recent SDitH (submitted to the NIST), and a new signature scheme that we introduce.

– We introduce a new signature scheme from the regular syndrome decoding assumption, based on a new protocol for the MPC-in-the-head paradigm, which significantly reduces communication compared to previous works. Our scheme is conceptually simple, though its security analysis requires a delicate and nontrivial combinatorial analysis.



## 2024/253

* Title: 2PC-MPC: Emulating Two Party ECDSA in Large-Scale MPC
* Authors: Offir Friedman, Avichai Marmor, Dolev Mutzari, Omer Sadika, Yehonatan C. Scaly, Yuval Spiizer, Avishay Yanai
* [Permalink](https://eprint.iacr.org/2024/253)
* [Download](https://eprint.iacr.org/2024/253.pdf)

### Abstract

Motivated by the need for a massively decentralized network concurrently servicing many clients, we present novel low-overhead UC-secure, publicly verifiable, threshold ECDSA protocols with identifiable abort.
For the first time, we show how to reduce the message complexity from O(n^2) to O(n) and the computational complexity from O(n) to practically O(1) (per party, where n is the number of parties).
We require only a broadcast channel for communication. Therefore, we natively support use-cases like permissionless bridges and decentralized custody, where P2P channels between every pair of parties are infeasible. Consequently, the message complexity is reduced and the protocol is publicly verifiable.
We enable all communication to be public (over a broadcast channel), by using a threshold additively homomorphic encryption scheme and novel zero-knowledge proofs.
To further reduce the computation and communication overheads, our protocols employ novel batching and amortization techniques, which may be of independent interest.

Our second main contribution is the introduction of the notion of a 2PC-MPC protocol - a two-party ECDSA protocol where the second party is fully emulated by a network of n parties.
This notion assures that both the first party (the client) and (a threshold) of the network are required to participate in signing, while abstracting away the internal structure of the network.
In particular, the communication and computation complexities of the client remain independent of the network properties (e.g. size). This allows ultimate decentralization in distributed custody use-cases, as recent growing interest in the industry demands.

We report that our implementation completes the signing phase in 1.23 and 12.703 seconds, for 256 and 1024 parties, respectively.



## 2024/254

* Title: Adaptive Security in SNARGs via iO and Lossy Functions
* Authors: Brent Waters, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/254)
* [Download](https://eprint.iacr.org/2024/254.pdf)

### Abstract

We construct an adaptively sound SNARGs in the plain model with CRS
relying on the assumptions of (subexponential) indistinguishability obfuscation (iO), subexponential one-way functions and a notion of lossy functions we call length parameterized lossy functions. Length parameterized lossy functions take in separate security and input length parameters and have the property that the function image size in lossy mode depends only on the security parameter. We then show a novel way of constructing such functions from the Learning with Errors (LWE) assumption.

Our work provides an alternative path towards achieving adaptively secure SNARGs from the recent work of Waters and Wu. Their work required the use of (essentially) perfectly re-randomizable one way functions (in addition to obfuscation). Such functions are only currently known to be realizable from assumptions such as discrete log or factoring that are known to not hold in a quantum setting.



## 2024/255

* Title: Revisiting Differential-Linear Attacks via a Boomerang Perspective with Application to AES, Ascon, CLEFIA, SKINNY, PRESENT, KNOT, TWINE, WARP, LBlock, Simeck, and SERPENT
* Authors: Hosein Hadipour, Patrick Derbez, Maria Eichlseder
* [Permalink](https://eprint.iacr.org/2024/255)
* [Download](https://eprint.iacr.org/2024/255.pdf)

### Abstract

In 1994, Langford and Hellman introduced differential-linear (DL) cryptanalysis, with the idea of decomposing the block cipher E into two parts, EU and EL, such that EU exhibits a high-probability differential trail, while EL has a high-correlation linear trail.Combining these trails forms a distinguisher for E, assuming independence between EU and EL. The dependency between the two parts of DL distinguishers remained unaddressed until EUROCRYPT 2019, where Bar-On et al. introduced the DLCT framework, resolving the issue up to one S-box layer. However, extending the DLCT framework to formalize the dependency between the two parts for multiple rounds remained an open problem.

In this paper, we first tackle this problem from the perspective of boomerang analysis. By examining the relationships between DLCT, DDT, and LAT, we introduce a set of new tables facilitating the formulation of dependencies between the two parts of the DL distinguisher across multiple rounds. Then, as the main contribution, we introduce a highly versatile and easy-to-use automatic tool for exploring DL distinguishers, inspired by automatic tools for boomerang distinguishers. This tool considers the dependency between differential and linear trails across multiple rounds. We apply our tool to various symmetric-key primitives, and in all applications, we either present the first DL distinguishers or enhance the best-known ones. We achieve successful results against Ascon, AES, SERPENT, PRESENT, SKINNY, TWINE, CLEFIA, WARP, LBlock, Simeck, and KNOT. Furthermore, we demonstrate that, in some cases, DL distinguishers outperform boomerang distinguishers significantly.



## 2024/256

* Title: Fiat-Shamir for Bounded-Depth Adversaries
* Authors: Liyan Chen, Yilei Chen, Zikuan Huang, Nuozhou Sun, Tianqi Yang, Yiding Zhang
* [Permalink](https://eprint.iacr.org/2024/256)
* [Download](https://eprint.iacr.org/2024/256.pdf)

### Abstract

We study how to construct hash functions that can securely instantiate the Fiat-Shamir transformation against bounded-depth adversaries. The motivation is twofold. First, given the recent fruitful line of research of constructing cryptographic primitives against bounded-depth adversaries under worst-case complexity assumptions, and the rich applications of Fiat-Shamir, instantiating Fiat-Shamir hash functions against bounded-depth adversaries under worst-case complexity assumptions might lead to further applications (such as SNARG for P, showing the cryptographic hardness of PPAD, etc.) against bounded-depth adversaries. Second, we wonder whether it is possible to overcome the impossibility results of constructing Fiat-Shamir for arguments [Goldwasser, Kalai, FOCS ’03] in the setting where the depth of the adversary is bounded, given that the known impossibility results (against p.p.t. adversaries) are contrived.

Our main results give new insights for Fiat-Shamir against bounded-depth adversaries in both the positive and negative directions. On the positive side, for Fiat-Shamir for proofs with certain properties, we show that weak worst-case assumptions are enough for constructing explicit hash functions that give $\mathsf{AC}^0[2]$-soundness. In particular, we construct an $\mathsf{AC}^0[2]$-computable correlation-intractable hash family for constant-degree polynomials against $\mathsf{AC}^0[2]$ adversaries, assuming $\oplus \mathsf{L}/\mathsf{poly} \not\subseteq \widetilde{\mathsf{Sum}}_{n^{-c}} \circ\mathsf{AC}^0[2]$ for some $c > 0$. This is incomparable to all currently-known constructions, which are typically useful for larger classes and against stronger adversaries, but based on arguably stronger assumptions. Our construction is inspired by the Fiat-Shamir hash function by Peikert and Shiehian [CRYPTO ’19] and the fully-homomorphic encryption scheme against bounded-depth adversaries by Wang and Pan [EUROCRYPT ’22].

On the negative side, we show Fiat-Shamir for arguments is still impossible to achieve against bounded-depth adversaries. In particular,
• Assuming the existence of $\mathsf{AC}^0[2]$-computable CRHF against p.p.t. adversaries, for every poly-size hash function, there is a (p.p.t.-sound) interactive argument that is not $\mathsf{AC}^0[2]$-sound after applying Fiat-Shamir with this hash function.
• Assuming the existence of $\mathsf{AC}^0[2]$-computable CRHF against $\mathsf{AC}^0[2]$ adversaries, there is an $\mathsf{AC}^0[2]$-sound interactive argument such that for every hash function computable by $\mathsf{AC}^0[2]$ circuits the argument does not preserve $\mathsf{AC}^0[2]$-soundness when applying Fiat-Shamir with this hash function. This is a low-depth variant of the result of Goldwasser and Kalai.



## 2024/257

* Title: LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems
* Authors: Dan Boneh, Binyi Chen
* [Permalink](https://eprint.iacr.org/2024/257)
* [Download](https://eprint.iacr.org/2024/257.pdf)

### Abstract

Folding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed, such as Nova, Supernova, Hypernova, Protostar, and others. However, all of them rely on an additively homomorphic commitment scheme based on discrete log, and are therefore not post-quantum secure. In this work we present LatticeFold, the first lattice-based folding protocol based on the Module SIS problem. This folding protocol naturally leads to an efficient recursive lattice-based SNARK and an efficient PCD scheme. LatticeFold supports folding low-degree relations, such as R1CS, as well as high-degree relations, such as CCS. The key challenge is to construct a secure folding protocol that works with the Ajtai commitment scheme. The difficulty, is ensuring that extracted witnesses are low norm through many rounds of folding. We present a novel technique using the sumcheck protocol to ensure that extracted witnesses are always low norm no matter how many rounds of folding are used. Our evaluation of the final proof system suggests that it is as performant as Hypernova, while providing post-quantum security.



## 2024/258

* Title: SoK: Decentralized Storage Network
* Authors: Chuanlei Li, Minghui Xu, Jiahao Zhang, Hechuan Guo, Xiuzhen Cheng
* [Permalink](https://eprint.iacr.org/2024/258)
* [Download](https://eprint.iacr.org/2024/258.pdf)

### Abstract

Decentralized Storage Networks (DSNs) represent a paradigm shift in data storage methodology, distributing and housing data across multiple network nodes rather than relying on a centralized server or data center architecture. The fundamental objective of DSNs is to enhance security, reinforce reliability, and mitigate censorship risks by eliminating a single point of failure. Leveraging blockchain technology for functions such as access control, ownership validation, and transaction facilitation, DSN initiatives aim to provide users with a robust and secure alternative to traditional centralized storage solutions. This paper conducts a comprehensive analysis of the developmental trajectory of DSNs, focusing on key components such as Proof of Storage protocols, consensus algorithms, and incentive mechanisms. Additionally, the study explores recent optimization tactics, encountered challenges, and potential avenues for future research, thereby offering insights into the ongoing evolution and advancement within the DSN domain.



## 2024/259

* Title: Anonymity on Byzantine-Resilient Decentralized Computing
* Authors: Kehao Ma, Minghui Xu, Yihao Guo, Lukai Cui, Shiping Ni, Shan Zhang, Weibing Wang, Haiyong Yang, Xiuzhen Cheng
* [Permalink](https://eprint.iacr.org/2024/259)
* [Download](https://eprint.iacr.org/2024/259.pdf)

### Abstract

In recent years, decentralized computing has gained popularity in various domains such as decentralized learning, financial services and the Industrial Internet of Things. As identity privacy becomes increasingly important in the era of big data, safeguarding user identity privacy while ensuring the security of decentralized computing systems has become a critical challenge. To address this issue, we propose ADC (Anonymous Decentralized Computing) to achieve anonymity in decentralized computing. In ADC, the entire network of users can vote to trace and revoke malicious nodes. Furthermore, ADC possesses excellent Sybil-resistance and Byzantine fault tolerance, enhancing the security of the system and increasing user trust in the decentralized computing system. To decentralize the system, we propose a practical blockchain-based decentralized group signature scheme called Group Contract. We construct the entire decentralized system based on Group Contract, which does not require the participation of a trusted authority to guarantee the above functions. Finally, we conduct rigorous privacy and security analysis and performance evaluation to demonstrate the security and practicality of ADC for decentralized computing with only a minor additional time overhead.



## 2024/260

* Title: Kleptographic Attacks against Implicit Rejection
* Authors: Antoine Joux, Julian Loss, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2024/260)
* [Download](https://eprint.iacr.org/2024/260.pdf)

### Abstract

Given its integral role in modern encryption systems such as CRYSTALS-Kyber, the Fujisaki-Okamoto (FO) transform will soon be at the center of our secure communications infrastructure. An enduring debate surrounding the FO transform is whether to use explicit or implicit rejection when decapsulation fails. Presently, implicit rejection, as implemented in CRYSTALS-Kyber, is supported by a strong set of arguments. Therefore, understanding its security implications in different attacker models is essential.

In this work, we study implicit rejection through a novel lens, namely, from the perspective of kleptography. Concretely, we consider an attacker model in which the attacker can subvert the user's code to compromise security while remaining undetectable. In this scenario, we present three attacks that significantly reduce the security level of the FO transform with implicit rejection. Notably, our attacks apply to CRYSTALS-Kyber.



## 2024/261

* Title: Election Eligibility with OpenID: Turning Authentication into Transferable Proof of Eligibility
* Authors: Véronique Cortier, Alexandre Debant, Anselme Goetschmann, Lucca Hirschi
* [Permalink](https://eprint.iacr.org/2024/261)
* [Download](https://eprint.iacr.org/2024/261.pdf)

### Abstract

Eligibility checks are often abstracted away or omitted in voting protocols, leading to situations where the voting server can easily stuff the ballot box. One reason for this is the difficulty of bootstraping the authentication material for voters without relying on trusting the voting server.
In this paper, we propose a new protocol that solves this problem by building on OpenID, a widely deployed authentication protocol. Instead of using it as a standard authentication means, we turn it into a mechanism that delivers transferable proofs of eligibility. Using zk-SNARK proofs, we show that this can be done without revealing any compromising information, in particular, protecting everlasting privacy. Our approach remains efficient and can easily be integrated into existing protocols, as we have done for the Belenios voting protocol. We provide a full-fledged proof of concept along with benchmarks showing our protocol could be realistically used in large-scale elections.



## 2024/262

* Title: Note on the cryptanalysis of Speedy
* Authors: Tim Beyne, Addie Neyt
* [Permalink](https://eprint.iacr.org/2024/262)
* [Download](https://eprint.iacr.org/2024/262.pdf)

### Abstract

At Eurocrypt 2023, a differential attack on the block cipher Speedy-7-192 was presented. This note shows that the main differential characteristic that this attack is based on has probability zero.



## 2024/263

* Title: Threshold Encryption with Silent Setup
* Authors: Sanjam Garg, Dimitris Kolonelos, Guru-Vamsi Policharla, Mingyuan Wang
* [Permalink](https://eprint.iacr.org/2024/263)
* [Download](https://eprint.iacr.org/2024/263.pdf)

### Abstract

We build a concretely efficient threshold encryption scheme where the joint public key of a set of parties is computed as a deterministic function of their locally computed public keys, enabling a silent setup phase. By eliminating interaction from the setup phase, our scheme immediately enjoys several highly desirable features such as asynchronous setup, multiverse support, and dynamic threshold.
Prior to our work, the only known constructions of threshold encryption with silent setup relied on heavy cryptographic machinery such as indistinguishability Obfuscation or witness encryption for all of $\mathsf{NP}$. Our core technical innovation lies in building a special purpose witness encryption scheme for the statement ``at least $t$ parties have signed a given message''. Our construction relies on pairings and is proved secure in the Generic Group Model.
Notably, our construction, restricted to the special case of threshold $t=1$, gives an alternative construction of the (flexible) distributed broadcast encryption from pairings, which has been the central focus of several recent works.
We implement and evaluate our scheme to demonstrate its concrete efficiency. Both encryption and partial decryption are constant time, taking $<7\,$ms and $<1\,$ms, respectively. For a committee of $1024$ parties, the aggregation of partial decryptions takes $<200\,$ms, when all parties provide partial decryptions. The size of each ciphertext is $\approx 8\times$ larger than an ElGamal ciphertext.



## 2024/264

* Title: Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT
* Authors: Nils Fleischhacker, Mathias Hall-Andersen, Mark Simkin
* [Permalink](https://eprint.iacr.org/2024/264)
* [Download](https://eprint.iacr.org/2024/264.pdf)

### Abstract

We present a concretely efficient and simple extractable witness encryption scheme for KZG polynomial commitments.
It allows to encrypt a message towards a triple $(\mathsf{com}, \alpha, \beta)$, where $\mathsf{com}$ is a KZG commitment for some polynomial $f$.
Anyone with an opening for the commitment attesting $f(\alpha) = \beta$ can decrypt, but without knowledge of a valid opening the message is computationally hidden.
Our construction is simple and highly efficient. The ciphertext is only a single group element. Encryption and decryption both require a single pairing evaluation and a constant number of group operations.

Using our witness encryption scheme, we construct a simple and highly efficient laconic OT protocol, which significantly outperforms the state of the art in most important metrics.



## 2024/265

* Title: Beyond the circuit: How to Minimize Foreign Arithmetic in ZKP Circuits
* Authors: Michele Orrù, George Kadianakis, Mary Maller, Greg Zaverucha
* [Permalink](https://eprint.iacr.org/2024/265)
* [Download](https://eprint.iacr.org/2024/265.pdf)

### Abstract

Zero-knowledge circuits are frequently required to prove gadgets that are not optimised for the constraint system in question. A particularly daunting task is to embed foreign arithmetic such as Boolean operations, field arithmetic, or public-key cryptography.

We construct techniques for offloading foreign arithmetic from a zero-knowledge circuit including:
(i) equality of discrete logarithms across different groups;
(ii) scalar multiplication without requiring elliptic curve operations;
(iii) proving knowledge of an AES encryption.

To achieve our goal, we employ techniques inherited from rejection sampling and lookup protocols. We implement and provide concrete benchmarks for our protocols.



## 2024/266

* Title: WhisPIR: Stateless Private Information Retrieval with Low Communication
* Authors: Leo de Castro, Kevin Lewi, Edward Suh
* [Permalink](https://eprint.iacr.org/2024/266)
* [Download](https://eprint.iacr.org/2024/266.pdf)

### Abstract

Recent constructions of private information retrieval (PIR) have seen significant improvements in computational performance. However, these improvements rely on heavy offline preprocessing that is typically difficult in real-world applications. Motivated by the question of PIR with no offline processing, we introduce WhisPIR, a fully stateless PIR protocol with low per-query communication. WhisPIR clients are all ephemeral, meaning that they appear with only the protocol public parameters and disappear as soon as their query is complete, giving no opportunity for additional "offline" communication that is not counted towards the overall query communication. As such, WhisPIR is highly suited for practical applications that must support many clients and frequent database updates.

We demonstrate that WhisPIR requires significantly less communication than all other lattice-based PIR protocols in a stateless setting. WhisPIR is outperformed in computation only by SimplePIR and HintlessPIR when the database entries are large (several kilobytes). WhisPIR achieves this performance by introducing a number of novel optimizations. These include improvements to the index expansion algorithm of SealPIR & OnionPIR that optimizes the algorithm when only one rotation key is available. WhisPIR also makes novel use of the non-compact variant of the BGV homomorphic encryption scheme to further save communication and computation. To demonstrate the practicality of WhisPIR, we apply the protocol to the problem of secure blocklist checking, an important user-safety application in end-to-end encrypted messaging.



## 2024/267

* Title: zkPi: Proving Lean Theorems in Zero-Knowledge
* Authors: Evan Laufer, Alex Ozdemir, Dan Boneh
* [Permalink](https://eprint.iacr.org/2024/267)
* [Download](https://eprint.iacr.org/2024/267.pdf)

### Abstract

Interactive theorem provers (ITPs), such as Lean and Coq, can express
formal proofs for a large category of theorems, from abstract math to
software correctness. Consider Alice who has a Lean proof for some
public statement $T$. Alice wants to convince the world that she has
such a proof, without revealing the actual proof. Perhaps the proof
shows that a secret program is correct or safe, but the proof itself
might leak information about the program's source code. A natural way
for Alice to proceed is to construct a succinct, zero-knowledge,
non-interactive argument of knowledge (zkSNARK) to prove that she has a
Lean proof for the statement $T$.

In this work we build zkPi, the first zkSNARKfor proofs expressed in
Lean, a state of the art interactive theorem prover. With zkPi, a prover
can convince a verifier that a Lean theorem is true, while revealing
little else. The core problem is building an efficient zkSNARKfor
dependent typing. We evaluate zkPion theorems from two core Lean
libraries: stdlib and mathlib. zkPisuccessfuly proves 57.9% of the
theorems in stdlib, and 14.1% of the theorems in mathlib, within 4.5
minutes per theorem. A zkPiproof is sufficiently short that Fermat could
have written one in the margin of his notebook to convince the world, in
zero knowledge, that he proved his famous last theorem.

Interactive theorem provers (ITPs) can express virtually all systems of
formal reasoning. Thus, an implemented zkSNARKfor ITP theorems
generalizes practical zero-knowledge's interface beyond the status quo:
circuit satisfiability and program execution.



## 2024/268

* Title: A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More
* Authors: Minki Hhan
* [Permalink](https://eprint.iacr.org/2024/268)
* [Download](https://eprint.iacr.org/2024/268.pdf)

### Abstract

This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models.
- In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring.
- In the quantum generic group model (QGGM), we study the complexity of variants of the discrete logarithm. We prove the logarithm DL lower bound in the QGGM even for the composite order setting. We also prove an asymptotically tight lower bound for the multiple-instance DL problem. Both results resolve the open problems suggested in a recent work by Hhan, Yamakawa, and Yun.
- In the quantum generic ring model we newly suggested, we give the logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also give a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm.
- Finally, we prove a lower bound for the basic index calculus method for solving the DL problem in a new idealized group model regarding smooth numbers.
The quantum lower bounds in both models allow certain (different) types of classical preprocessing.
All of the proofs are significantly simpler than the previous proofs and are through a single tool, the so-called compression lemma, along with linear algebra tools. Our use of this lemma may be of independent interest.



## 2024/269

* Title: A note on PUF-Based Robust and Anonymous Authentication and Key Establishment Scheme for V2G Networks
* Authors: Milad Seddigh, Seyed Hamid Baghestani
* [Permalink](https://eprint.iacr.org/2024/269)
* [Download](https://eprint.iacr.org/2024/269.pdf)

### Abstract

Vehicle-to-grid (V2G) provides effective charging services, allows bidirectional energy communication between the power grid and electric vehicle (EV), and reduces environmental pollution and energy crises. Recently, Sungjin Yu et al. proposed a PUF-based, robust, and anonymous authentication and key establishment scheme for V2G networks. In this paper, we show that the proposed protocol does not provide user anonymity and is vulnerable to tracing attack. We also found their scheme is vulnerable to ephemeral secret leakage attacks.



## 2024/270

* Title: YPIR: High-Throughput Single-Server PIR with Silent Preprocessing
* Authors: Samir Jordan Menon, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/270)
* [Download](https://eprint.iacr.org/2024/270.pdf)

### Abstract

We introduce YPIR, a single-server private information retrieval (PIR) protocol that achieves high throughput (up to 75% of the memory bandwidth of the machine) without any offline communication. For retrieving a 1-bit (or 1-byte) record from a 32-GB database, YPIR achieves 10.9 GB/s/core server throughput and requires 2.5 MB of total communication. On the same setup, the state-of-the-art SimplePIR protocol achieves a 12.6 GB/s/core server throughput, requires 1.5 MB total communication, but additionally requires downloading a 724 MB hint in an offline phase. YPIR leverages a new lightweight technique to remove the hint from high-throughput single-server PIR schemes with small overhead. We also show how to reduce the server preprocessing time in the SimplePIR family of protocols by a factor of $10$-$15\times$.

By removing the need for offline communication, YPIR significantly reduces the server-side costs for private auditing of Certificate Transparency logs. Compared to the best previous PIR-based approach, YPIR reduces the server-side costs by a factor of $5.6\times$. Note that to reduce communication costs, the previous approach assumed that updates to the Certificate Transparency log servers occurred in weekly batches. Since there is no offline communication in YPIR, our approach allows clients to always audit the most recent Certificate Transparency logs (e.g., updating once a day). Supporting daily updates using the prior scheme would cost $30\times$ more than YPIR (based on current AWS compute costs).



## 2024/271

* Title: Understanding User-Perceived Security Risks and Mitigation Strategies in the Web3 Ecosystem
* Authors: Janice Jianing Si, Sharma Tanusree, Kanye Ye Wang
* [Permalink](https://eprint.iacr.org/2024/271)
* [Download](https://eprint.iacr.org/2024/271.pdf)

### Abstract

The advent of Web3 technologies promises unprecedented levels of user control and autonomy. However, this decentralization shifts the burden of security onto the users, making it crucial to understand their security behaviors and perceptions. To address this, our study introduces a comprehensive framework that identifies four core components of user interaction within the Web3 ecosystem: blockchain infrastructures, Web3-based Decentralized Applications (DApps), online communities, and off-chain cryptocurrency platforms. We delve into the security concerns perceived by users in each of these components and analyze the mitigation strategies they employ, ranging from risk assessment and aversion to diversification and acceptance. We further discuss the landscape of both technical and human-induced security risks in the Web3 ecosystem, identify the unique security differences between Web2 and Web3, and highlight key challenges that render users vulnerable, to provide implications for security design in Web3.