[continued from previous message]

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)