[digest] 2024 Week 39

## In this issue

1. [2023/1538] Unclonable Commitments and Proofs
2. [2024/562] Practical Proofs of Parsing for Context-free Grammars
3. [2024/881] PipeSwap: Forcing the Timely Release of a Secret ...
4. [2024/1395] A Formal Analysis of Apple’s iMessage PQ3 Protocol
5. [2024/1479] Honest Majority GOD MPC with $O(\mathsf{depth}(C))$ ...
6. [2024/1480] On Schubert cells of Projective Geometry and ...
7. [2024/1481] Tighter Adaptive IBEs and VRFs: Revisiting Waters' ...
8. [2024/1482] The Power of NAPs: Compressing OR-Proofs via ...
9. [2024/1483] Making Searchable Symmetric Encryption Schemes ...
10. [2024/1484] Quadratic-like balanced functions and permutations
11. [2024/1485] LARMix$\mathbf{++}$: Latency-Aware Routing in Mix ...
12. [2024/1486] Adaptively Secure Attribute-Based Encryption from ...
13. [2024/1487] The transition to post-quantum cryptography, ...
14. [2024/1488] Compact Proofs of Partial Knowledge for Overlapping ...
15. [2024/1489] Adaptive Security, Erasures, and Network ...
16. [2024/1490] Founding Quantum Cryptography on Quantum Advantage, ...
17. [2024/1491] On the Anonymity of One Authentication and Key ...
18. [2024/1492] Multi-Designated Detector Watermarking for Language ...
19. [2024/1493] Rate-1 Zero-Knowledge Proofs from One-Way Functions
20. [2024/1494] Concretely Efficient Private Set Union via Circuit- ...
21. [2024/1495] Lattice-Based Vulnerabilities in Lee Metric Post- ...
22. [2024/1496] No Fish Is Too Big for Flash Boys! Frontrunning on ...
23. [2024/1497] Low-degree Security of the Planted Random Subgraph ...
24. [2024/1498] Practical Implementation of Pairing-Based zkSNARK ...
25. [2024/1499] Multi-Key Fully-Homomorphic Aggregate MAC for ...
26. [2024/1500] Hard Quantum Extrapolations in Quantum Cryptography
27. [2024/1501] Exploring User Perceptions of Security Auditing in ...
28. [2024/1502] TopGear 2.0: Accelerated Authenticated Matrix ...
29. [2024/1503] Scalable Mixnets from Mercurial Signatures on ...
30. [2024/1504] Comments on "Privacy-Enhanced Federated Learning ...
31. [2024/1505] FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE
32. [2024/1506] Bit Security: optimal adversaries, equivalence ...
33. [2024/1507] Unbounded ABE for Circuits from LWE, Revisited
34. [2024/1508] Key Collisions on AES and Its Applications
35. [2024/1509] DUPLEX: Scalable Zero-Knowledge Lookup Arguments ...
36. [2024/1510] Group Factorisation for Smaller Signatures from ...
37. [2024/1511] Some Classes of Cubic Monomial Boolean Functions ...
38. [2024/1512] Improved Soundness Analysis of the FRI Protocol
39. [2024/1513] Depth Optimized Circuits for Lattice Based Voting ...
40. [2024/1514] Black-Box Non-Interactive Zero Knowledge from ...
41. [2024/1515] Optimized Software Implementation of Keccak, Kyber, ...
42. [2024/1516] Practical Mempool Privacy via One-time Setup ...
43. [2024/1517] A Note on the SNOVA Security
44. [2024/1518] Witness Semantic Security
45. [2024/1519] Efficient theta-based algorithms for computing ...
46. [2024/1520] On the rough order assumption in imaginary ...
47. [2024/1521] The SMAesH dataset
48. [2024/1522] Beware of Keccak: Practical Fault Attacks on SHA-3 ...
49. [2024/1523] Functional Adaptor Signatures: Beyond All-or- ...
50. [2024/1524] Lower Bounds on the Overhead of ...
51. [2024/1525] Evaluating Leakage Attacks Against Relational ...
52. [2024/1526] Overpass Channels: Horizontally Scalable, Privacy- ...
53. [2024/1527] How to Recover the Full Plaintext of XCB
54. [2024/1528] Schnorr Signatures are Tightly Secure in the ROM ...

## 2023/1538

* Title: Unclonable Commitments and Proofs
* Authors: Vipul Goyal, Giulio Malavolta, Justin Raizes
* [Permalink](https://eprint.iacr.org/2023/1538)
* [Download](https://eprint.iacr.org/2023/1538.pdf)

### Abstract

Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition.  In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers).
   
In this work, we prevent even the possibility of copying the proof as it is, by relying on quantum information. We call the resulting primitive unclonable proofs, making progress on a question posed by Aaronson. We also consider the related notion of unclonable commitments. We introduce formal definitions of these primitives that model security in various settings of interest. We also provide a near tight characterization of the conditions under which these primitives are possible, including a rough equivalence between unclonable proofs and public-key quantum money.



## 2024/562

* Title: Practical Proofs of Parsing for Context-free Grammars
* Authors: Harjasleen Malvai, Siam Hussain, Gregory Neven, Andrew Miller
* [Permalink](https://eprint.iacr.org/2024/562)
* [Download](https://eprint.iacr.org/2024/562.pdf)

### Abstract

We present a scheme to prove, in zero-knowledge (ZK), the correct parsing of a string in context-free grammar (CFG). This is a crucial step towards applications such as proving statements about web API responses in ZK.

To the best of our knowledge, this is the first ZK scheme to prove the correctness of CFG parsing with complexity linear in the length of the string. Further, our algorithm flexibly accommodates different ZK proof systems. We demonstrate this flexibility with multiple implementations using both non-interactive and interactive proof paradigms.

Given general-purpose ZK programming frameworks, our implementations are not only compact (e.g., around 200 lines of code for the non-interactive version) but also deliver competitive performance. In the non-interactive setting, proving the correct parsing of a $\approx 1$KB string takes 24 seconds, even for grammars with $2^{10}$ production rules. In the interactive setting the same proof takes just 1.6 seconds.



## 2024/881

* Title: PipeSwap: Forcing the Timely Release of a Secret for Atomic Swaps Across All Blockchains
* Authors: Peifang Ni, Anqi Tian, Jing Xu
* [Permalink](https://eprint.iacr.org/2024/881)
* [Download](https://eprint.iacr.org/2024/881.pdf)

### Abstract

Atomic cross-chain swap, which allows users to exchange coins securely, is critical functionality to facilitate inter-currency exchange and trading. Although most classic atomic swap protocols based on Hash Timelock Contracts have been applied and deployed in practice, they are substantially far from universality due to the inherent dependence of rich scripting language supported by the underlying blockchains. The recently proposed Universal Atomic Swaps protocol [IEEE S\&P'22] takes a novel path to scriptless cross-chain swap, and it ingeniously delegates scripting functionality to cryptographic lock mechanisms, particularly the adaptor signature and timed commitment schemes designed to guarantee atomicity. However, in this work, we discover a new form of attack called double-claiming attack, such that the honest user would lose coins with overwhelming probability and atomicity is directly broken. Moreover, this attack is easy to carry out and can be naturally generalized to other cross-chain swap protocols as well as the payment channel networks, highlighting a general difficulty in designing universal atomic swap.

We present pipeSwap, a cross-chain swap protocol that satisfies both security and practical universality. To avoid transactions of the same frozen coins being double-claimed to violate the atomicity property, pipeSwap proposes a novelly designed paradigm of pipelined coins flow by using two-hop swap and two-hop refund techniques. pipeSwap achieves universality by not relying on any specific script language, aside from the basic ability to verify signatures. Furthermore, we analyze why existing ideal functionality falls short in capturing the atomicity property of Universal Atomic Swaps, and define for the first time ideal functionality to guarantee atomicity. In addition to a detailed security analysis in the Universal Composability framework, we develop a proof-of-concept implementation of pipeSwap with Schnorr/ECDSA signatures, and conduct extensive experiments to evaluate the overhead. The experimental results show that pipeSwap can be performed in less than 1.7 seconds and requires less than 7 kb of communication overhead on commodity machines, which demonstrates its high efficiency.



## 2024/1395

* Title: A Formal Analysis of Apple’s iMessage PQ3 Protocol
* Authors: Felix Linker, Ralf Sasse, David Basin
* [Permalink](https://eprint.iacr.org/2024/1395)
* [Download](https://eprint.iacr.org/2024/1395.pdf)

### Abstract

We present the formal verification of Apple’s iMessage PQ3, a highly performant, device-to-device messaging protocol offering strong security guarantees even against an adversary with quantum computing capabilities. PQ3 leverages Apple’s identity services together with a custom, post-quantum secure initialization phase and afterwards it employs a double ratchet construction in the style of Signal, extended to provide post-quantum, post-compromise security.

We present a detailed formal model of PQ3, a precise specification of its fine-grained security properties, and machine-checked security proofs using the TAMARIN prover. Particularly novel is the integration of post-quantum secure key encapsulation into the relevant protocol phases and the detailed security claims along with their complete formal analysis. Our analysis covers both key ratchets, including unbounded loops, which was believed by some to be out of scope of symbolic provers like TAMARIN (it is not!).



## 2024/1479

* Title: Honest Majority GOD MPC with $O(\mathsf{depth}(C))$ Rounds and Low Online Communication
* Authors: Amit Agarwal, Alexander Bienstock, Ivan Damgård, Daniel Escudero
* [Permalink](https://eprint.iacr.org/2024/1479)
* [Download](https://eprint.iacr.org/2024/1479.pdf)

### Abstract

In the context of secure multiparty computation (MPC) protocols with guaranteed output delivery (GOD) for the honest majority setting, the state-of-the-art in terms of communication is the work of (Goyal et al. CRYPTO'20), which communicates O(n|C|) field elements, where |C| is the size of the circuit being computed and n is the number of parties. Their round complexity, as usual in secret-sharing based MPC, is proportional to O(depth(C)), but only in the optimistic case where there is no cheating. Under attack, the number of rounds can increase to \Omega(n^2) before honest parties receive output, which is undesired for shallow circuits with depth(C) << n^2. In contrast, other protocols that only require O(depth(C) rounds even in the worst case exist, but the state-of-the-art from (Choudhury and Patra, Transactions on Information Theory, 2017) still requires \Omega(n^4|C|) communication in the offline phase, and \Omega(n^3|C|) in the online (for both point-to-point and broadcast channels). We see there exists a tension between efficient communication and number of rounds. For reference, the recent work of (Abraham et al., EUROCRYPT'23) shows that for perfect security and t<n/3, protocols with both linear communication and O(depth(C)) rounds exist.

We address this state of affairs by presenting a novel honest majority GOD protocol that maintains O(depth(C)) rounds, even under attack, while improving over the communication of the most efficient protocol in this setting by Choudhury and Patra. More precisely, our protocol has point-to-point (P2P) online communication of O(n|C|), accompanied by O(n|C|) broadcasted (BC) elements, while the offline has O(n^3|C|) P2P communication with O(n^3|C|) BC. This improves over the previous best result, and reduces the tension between communication and round complexity. Our protocol is achieved via a careful use of packed secret-sharing in order to improve the communication of existing verifiable secret-sharing approaches, although at the expense of weakening their robust guarantees: reconstruction of shared values may fail, but only if the adversary gives away the identities of many corrupt parties. We show that this less powerful notion is still useful for MPC, and we use this as a core building block in our construction. Using this weaker VSS, we adapt the recent secure-with-abort Turbopack protocol (Escudero et al. CCS'22) to the GOD setting without significantly sacrificing in efficiency.



## 2024/1480

* Title: On Schubert cells of Projective Geometry  and quadratic public keys of Multivariate Cryptography
* Authors: Vasyl Ustimenko
* [Permalink](https://eprint.iacr.org/2024/1480)
* [Download](https://eprint.iacr.org/2024/1480.pdf)

### Abstract

Jordan-Gauss graphs are bipartite graphs given by special quadratic equations over the commutative ring K with unity with partition sets 
K^n and K^m , n ≥m such that the neighbour of each vertex is defined by the system of linear equation given in its row-echelon form.
 We use families of this graphs for the construction of new quadratic and cubic surjective multivariate maps F of  K^n onto K^m  (or K^n onto  K^n) with the trapdoor accelerators  T , i. e. pieces of information which allows to compute the reimage of the given value of F in poly-nomial time. The technique allows us to use the information on the quadratic map F from K^s  to K^r, s ≥ r with the trapdoor accelerator T for the construction of  other  map G from K^{s+rs} onto K^{r+rs} with trapdoor accelerator. In the case of finite field it can be used for construc-tion of new cryptosystems from known pairs (F, T).
   So we can introduce enveloping trapdoor accelerator for Matsumoto-Imai cryptosystem over finite fields of characteristic 2, for the Oil and Vinegar public keys over F_q  (TUOV in particular), for quadratic multivariate public keys defined over Jordan-Gauss graphs  D(n, K) where K is arbitrary finite commutative ring  with the nontrivial multiplicative group.



## 2024/1481

* Title: Tighter Adaptive IBEs and VRFs: Revisiting Waters' Artificial Abort
* Authors: Goichiro Hanaoka, Shuichi Katsumata, Kei Kimura, Kaoru Takemure, Shota Yamada
* [Permalink](https://eprint.iacr.org/2024/1481)
* [Download](https://eprint.iacr.org/2024/1481.pdf)

### Abstract

One of the most popular techniques to prove adaptive security of  identity-based encryptions (IBE) and verifiable random functions (VRF) is the partitioning technique. Currently, there are only two methods to relate the adversary's advantage and runtime $(\epsilon, {\sf T})$ to those of the reduction's ($\epsilon_{\sf proof}, {\sf T}_{\sf proof}$) using this technique: One originates to Waters (Eurocrypt 2005) who introduced the famous artificial abort step to prove his IBE, achieving $(\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon/Q), {\sf T} + O(Q^2/\epsilon^2))$, where $Q$ is the number of key queries. Bellare and Ristenpart (Eurocrypt 2009) provide an alternative analysis for the same scheme removing the artificial abort step, resulting in $(\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon^2/Q), {\sf T} + O(Q))$. Importantly, the current reductions all loose quadratically in $\epsilon$.

In this paper, we revisit this two decade old problem and analyze proofs based on the partitioning technique through a new lens. For instance, the Waters IBE can now be proven secure with $(\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon^{3/2}/Q), {\sf T} + O(Q))$, breaking the quadratic dependence on $\epsilon$. At the core of our improvement is a finer estimation of the failing probability of the reduction in Waters' original proof relying on artificial abort. We use Bonferroni's inequality, a tunable inequality obtained by cutting off higher order terms from the equality derived by the inclusion-exclusion principle.

Our analysis not only improves the reduction of known constructions but also opens the door for new constructions. While a similar improvement to Waters IBE is possible for the lattice-based IBE by Agrawal, Boneh, and Boyen (Eurocrypt 2010), we can slightly tweak the so-called partitioning function in their construction, achieving $(\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon/Q), {\sf T} + O(Q))$. This is a much better reduction than the previously known $ (O(\epsilon^3/Q^2), {\sf T} + O(Q))$. We also propose the first VRF with proof and verification key sizes sublinear in the security parameter under the standard $d$-LIN assumption, while simultaneously improving the reduction cost compared to all prior constructions.



## 2024/1482

* Title: The Power of NAPs: Compressing OR-Proofs via Collision-Resistant Hashing
* Authors: Katharina Boudgoust, Mark Simkin
* [Permalink](https://eprint.iacr.org/2024/1482)
* [Download](https://eprint.iacr.org/2024/1482.pdf)

### Abstract

Proofs of partial knowledge, first considered by Cramer, Damgård and Schoenmakers (CRYPTO'94) and De Santis et al. (FOCS'94), allow for proving the validity of $k$ out of $n$ different statements without revealing which ones those are. In this work, we present a new approach for transforming certain proofs system into new ones that allows for proving partial knowledge. The communication complexity of the resulting proof system only depends logarithmically on the total number of statements $n$ and its security only relies on the existence of collision-resistant hash functions. As an example, we show that our transformation is applicable to the proof systems of Goldreich, Micali, and Wigderson (FOCS'86) for the graph isomorphism and the graph 3-coloring problem.

Our main technical tool, which we believe to be of independent interest, is a new cryptographic primitive called non-adaptively programmable functions (NAPs). Those functions can be seen as pseudorandom functions which allow for re-programming the output at an input point, which must be fixed during key generation. Even when given the re-programmed key, it remains infeasible to find out where re-programming happened. Finally, as an additional technical tool, we also build explainable samplers for any distribution that can be sampled efficiently via rejection sampling and use them to construct NAPs for various output distributions.



## 2024/1483

* Title: Making Searchable Symmetric Encryption Schemes Smaller and Faster
* Authors: Debrup Chakraborty, Avishek Majumder, Subhabrata Samajder
* [Permalink](https://eprint.iacr.org/2024/1483)
* [Download](https://eprint.iacr.org/2024/1483.pdf)

### Abstract

Searchable Symmetric Encryption (SSE) has emerged as a promising tool for facilitating efficient query processing over encrypted data stored in un-trusted cloud servers. Several techniques have been adopted to enhance the efficiency and security of SSE schemes. The query processing costs, storage costs and communication costs of any SSE are directly related to the size of the encrypted index that is stored in the server. To our knowledge, there is no work directed towards minimizing the index size. In this paper we introduce a novel technique to directly reduce the index size of any SSE. Our proposed technique generically transforms any secure single keyword SSE into an equivalently functional and secure version with reduced storage requirements, resulting in faster search and reduced communication overhead. Our technique involves in arranging the set of document identifiers $\mathsf{db}(w)$ related to a keyword $w$ in leaf nodes of a complete binary tree and eventually obtaining a succinct representation of the set $\mathsf{db}(w)$. This small representation of $\mathsf{db}(w)$ leads to smaller index sizes. We do an extensive theoretical analysis of our scheme and prove its correctness. In addition, our comprehensive experimental analysis validates the effectiveness of our scheme on real and simulated data and shows that it can be deployed in practical situations.



## 2024/1484

* Title: Quadratic-like balanced functions and permutations
* Authors: Claude Carlet, Irene Villa
* [Permalink](https://eprint.iacr.org/2024/1484)
* [Download](https://eprint.iacr.org/2024/1484.pdf)

### Abstract

We study those $(n,n)$-permutations, and more generally those balanced $(n,m)$-functions, whose component functions all admit a derivative equal to constant function 1 (this property itself implies balancedness). We call these functions quadratic-like permutations (resp. quadratic-like balanced functions) since all quadratic balanced functions have this property. We show that all Feistel permutations, all crooked permutations and (more generally) all balanced strongly plateaued functions have this same property and we observe that the notion is affine invariant.  We also study in each of these classes and in the class of quadratic-like APN permutations the "reversed" property that every derivative in a nonzero direction has a component function equal to constant function 1, and we show that this property can be satisfied only if $m\ge n$. We also show that all the quadratic-like power permutations $F(x)=x^d$, $x\in \mathbb F_{2^n}$ must be quadratic, which  generalizes a well-known similar result on power crooked functions. We give several constructions of quadratic-like permutations and balanced functions outside the three classes of quadratic balanced functions, permutations affine equivalent to Feistel permutations and crooked permutations. We characterize the property by the Walsh transform.



## 2024/1485

* Title: LARMix$\mathbf{++}$: Latency-Aware Routing in Mix Networks with Free Routes Topology
* Authors: Mahdi Rahimi
* [Permalink](https://eprint.iacr.org/2024/1485)
* [Download](https://eprint.iacr.org/2024/1485.pdf)

### Abstract

Mix networks (mixnets) enhance anonymity by routing client messages through multiple hops, intentionally delaying or reordering these messages to ensure unlinkability. However, this process increases end-to-end latency, potentially degrading the client experience. To address this issue, LARMix (NDSS, 2024) proposed a low-latency routing methodology specifically designed for stratified mixnet architectures. Our paper extends this concept to Free Routes mixnet designs, where, unlike stratified topologies, there are no restrictions on node connections. We adapt several state-of-the-art low-latency routing strategies from both mix and Tor networks to optimize the Free Routes topology. Despite the benefits, low-latency routing can cause certain mixnodes to receive disproportionate amounts of traffic. To overcome this challenge, we introduce a novel load-balancing algorithm that evenly distributes traffic among nodes without significantly compromising low-latency characteristics. Our analytical and simulation experiments demonstrate a considerable reduction in latency compared to uniform routing methods, with negligible loss in message anonymity, defined as the confusion an adversary experiences when correlating messages exiting the mixnet to an initially targeted input message. Additionally, we provide an analysis of adversarial strategies, revealing a balanced trade-off between low latency and adversary advantages.



## 2024/1486

* Title: Adaptively Secure Attribute-Based Encryption from Witness Encryption
* Authors: Brent Waters, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2024/1486)
* [Download](https://eprint.iacr.org/2024/1486.pdf)

### Abstract

Attribute-based encryption (ABE) enables fine-grained control over which ciphertexts various users can decrypt. A master authority can create secret keys $sk_f$ with different functions (circuits) $f$ for different users. Anybody can encrypt a message under some attribute $x$ so that only recipients with a key $sk_f$ for a function such that $f(x)=1$ will be able to decrypt. There are a number of different approaches toward achieving selectively secure ABE, where the adversary has to decide on the challenge attribute $x$ ahead of time before seeing any keys, including constructions via bilinear maps (for NC1 circuits),  learning with errors, or witness encryption. However, when it comes adaptively secure ABE, the problem seems to be much more challenging and we only know of two potential approaches: via the ``dual systems'' methodology from bilinear maps, or via indistinguishability obfuscation. In this work, we give a new approach that constructs adaptively secure ABE from witness encryption (along with statistically sound NIZKs and one-way functions). While witness encryption is a strong assumption, it appears to be fundamentally weaker than indistinguishability obfuscation. Moreover, we have candidate constructions of witness encryption from some assumptions (e.g., evasive LWE) from which we do not know how to construct indistinguishability obfuscation, giving us adaptive ABE from these assumptions as a corollary of our work.



## 2024/1487

* Title: The transition to post-quantum cryptography, metaphorically
* Authors: Stefan-Lukas Gazdag, Sophia Grundner-Culemann
* [Permalink](https://eprint.iacr.org/2024/1487)
* [Download](https://eprint.iacr.org/2024/1487.pdf)

### Abstract

Are we there yet? Are we there yet? No, kids, the road to quantum-safety is long and sturdy. But let me tell you a story:

Once upon a time, science discovered a great threat to Cryptography World: The scalable quantum computer! Nobody had ever seen one, but everyone understood it would break the mechanisms used to secure Internet communication since times of yore (or the late 20th century, anyway). The greatest minds from all corners of the land were gathered to invent, implement, and test newer, stronger tools. They worked day and night, but alas, when smaller quantum computers already started to emerge, no end to their research was in sight. How could that be?

This paper provides a collection of carefully wrought, more or less creative and more or less consistent metaphors to explain to audiences at all expertise levels the manifold challenges researchers and practitioners face in the ongoing quest for post-quantum migration.



## 2024/1488

* Title: Compact Proofs of Partial Knowledge for Overlapping CNF Formulae
* Authors: Gennaro Avitabile, Vincenzo Botta, Daniele Friolo, Daniele Venturi, Ivan Visconti
* [Permalink](https://eprint.iacr.org/2024/1488)
* [Download](https://eprint.iacr.org/2024/1488.pdf)

### Abstract

At CRYPTO '94, Cramer, Damgaard, and Schoenmakers introduced a general technique for constructing
honest-verifier zero-knowledge proofs of partial knowledge (PPK), where a prover Alice wants to prove to a verifier Bob she knows $\tau$ witnesses for $\tau$ claims out of $k$ claims without revealing the indices of those $\tau$ claims.
Their solution starts from a base honest-verifier zero-knowledge proof of knowledge $\Sigma$ and requires to run in parallel $k$ execution of the base protocol, giving a complexity of $O(k\gamma(\Sigma))$, where $\gamma(\Sigma)$ is the communication complexity of the base protocol.
However, modern practical scenarios require  communication-efficient zero-knowledge proofs tailored to handle partial knowledge in specific application-dependent formats.

In this paper we propose a technique to compose a large class of $\Sigma$-protocols for atomic statements into $\Sigma$-protocols for PPK over formulae in conjunctive normal form (CNF) that overlap, in the sense that there is a common subset of literals among all clauses of the formula.
In such formulae, the statement is expressed as a conjunction of $m$ clauses, each of which consists of a disjunction of $k$ literals (i.e., each literal is an atomic statement) and $\ell$ literals are shared among clauses.
The prover, for a threshold parameter $\tau \le k$, proves knowledge of at least $\tau$ witnesses for $\tau$ distinct literals in each clause.
 
At the core of our protocol, there is a new technique to compose $\Sigma$-protocols for regular CNF relations (i.e., when $ \tau=1$) that exploits the overlap among clauses and
that we then generalize to formulae where $\tau>1$ providing improvements over state-of-the-art constructions.



## 2024/1489

* Title: Adaptive Security, Erasures, and Network Assumptions in Communication-Local MPC
* Authors: Nishanth Chandran, Juan Garay, Ankit Kumar Misra, Rafail Ostrovsky, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2024/1489)
* [Download](https://eprint.iacr.org/2024/1489.pdf)

### Abstract

The problem of reliable/secure all-to-all communication over low-degree networks has been essential for communication-local (CL) n-party MPC (i.e., MPC protocols where every party directly communicates only with a few, typically polylogarithmic in n, parties) and more recently for communication over ad hoc networks, which are used in blockchain protocols. However, a limited number of adaptively secure solutions exist, and they all make relatively strong assumptions on the ability of parties to act in some specific manner before the adversary can corrupt them. Two such assumptions were made in the work of Chandran et al. [ITCS ’15]---parties can (a) multisend messages to several receivers simultaneously; and (b) securely erase the message and the identities of the receivers, before the adversary gets a chance to corrupt the sender (even if a receiver is corrupted). A natural question to ask is: Are these assumptions necessary for adaptively secure CL MPC? In this paper, we characterize the feasibility landscape for all-to-all reliable message transmission (RMT) under these two assumptions, and use this characterization to obtain (asymptotically) tight feasibility results for CL MPC.

– First, we prove a strong impossibility result for a broad class of RMT protocols, termed here store-and-forward protocols, which includes all known communication protocols for CL MPC from standard cryptographic assumptions. Concretely, we show that no such protocol with a certain expansion rate can tolerate a constant fraction of parties being corrupted.

– Next, under the assumption of only a PKI, we show that assuming secure erasures, we can obtain an RMT protocol between all pairs of parties with polylogarithmic locality (even without assuming multisend) for the honest majority setting. We complement this result by showing a negative result for the setting of dishonest majority.

– Finally, and somewhat surprisingly, under stronger assumptions (i.e.., trapdoor permutations with a reverse domain sampler, and compact and malicious circuit-private FHE), we construct a polylogarithmic-locality all-to-one RMT protocol, which is adaptively secure and tolerates any constant fraction of corruptions, without assuming either secure erasures or multisend. This last result uses a novel combination of adaptively secure (e.g., non-committing) encryption and (static) FHE to bypass the impossibility of compact adaptively secure FHE by Katz et al. [PKC’13], which we believe may be of independent interest. Intriguingly, even such assumptions do not allow reducing all-to-all RMT to all-to-one RMT (a reduction which is trivial in the non-CL setting). Still, we can implement what we call sublinear output-set RMT (SOS-RMT for short). We show how SOS-RMT can be used for SOS-MPC under the known bounds for feasibility of MPC in the standard (i.e., non-CL) setting assuming, in addition to SOS-RMT, an anonymous PKI.



## 2024/1490

* Title: Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\#\mathsf{P}$-Hardness
* Authors: Dakshita Khurana, Kabir Tomer
* [Permalink](https://eprint.iacr.org/2024/1490)
* [Download](https://eprint.iacr.org/2024/1490.pdf)

### Abstract

Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial heirarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P}^{\#\mathsf{P}}$ -- such as approximating the permanents of complex gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as \any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P}^{\#\mathsf{P}} \not\subseteq \mathsf{(io)BQP}/\mathsf{qpoly}$.
Our techniques uncover strong connections between the hardness of approximating the probabilities of outcomes of quantum processes, the existence of ``one-way'' state synthesis problems, and the existence of useful cryptographic primitives such as one-way puzzles and quantum bit commitments. Specifically, we prove that the following hardness assumptions are equivalent under $\mathsf{BQP}$ reductions.
1. The hardness of approximating the probabilities of outcomes of certain efficiently sampleable distributions. That is, there exist quantumly efficiently sampleable distributions for which it is hard to approximate the probability assigned to a randomly chosen string in the support of the distribution (upto inverse polynomial multiplicative error).
2. The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24].
3. The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges).  
These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.
Along the way, we also show that distributions that admit efficient quantum samplers but cannot be pseudo-deterministically efficiently sampled imply quantum commitments.



## 2024/1491

* Title: On the Anonymity of One Authentication and Key Agreement Scheme for Peer-to-Peer Cloud
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1491)
* [Download](https://eprint.iacr.org/2024/1491.pdf)

### Abstract

Peer-to-peer communication systems can provide many functions, including anonymized routing of network traffic, massive parallel computing environments, and distributed storage. Anonymity refers to the state of being completely nameless, with no attached identifiers. Pseudonymity involves the use of a fictitious name that can be consistently linked to a particular user, though not necessarily to the real identity. Both  provide a layer of privacy, shielding the user's true identity from public view. But we find their significations are often misunderstood. In this note, we clarify the differences between anonymity and pseudonymity. We also find the Zhong et al.'s key agreement scheme [IEEE TCC, 2022, 10(3), 1592-1603] fails to keep anonymity, not as claimed.



## 2024/1492

* Title: Multi-Designated Detector Watermarking for Language Models
* Authors: Zhengan Huang, Gongxian Zeng, Xin Mu, Yu Wang, Yue Yu
* [Permalink](https://eprint.iacr.org/2024/1492)
* [Download](https://eprint.iacr.org/2024/1492.pdf)

### Abstract

In this paper, we initiate the study of  multi-designated detector watermarking (MDDW) for large language models (LLMs). This technique allows model providers to generate watermarked outputs from LLMs with two key properties: (i) only specific, possibly multiple, designated detectors can identify the watermarks, and (ii) there is no perceptible degradation in the output quality for ordinary users. We formalize the security definitions for MDDW and present a framework for constructing MDDW for any LLM using multi-designated verifier signatures (MDVS). Recognizing the significant economic value of LLM outputs, we introduce claimability  as an optional security feature for MDDW, enabling model providers to assert ownership of LLM outputs within designated-detector settings. To support claimable MDDW, we  propose a generic transformation converting any MDVS to a claimable MDVS. Our implementation of the MDDW scheme highlights its advanced functionalities and flexibility over existing methods, with satisfactory performance metrics.



## 2024/1493

* Title: Rate-1 Zero-Knowledge Proofs from One-Way Functions
* Authors: Noor Athamnah, Eden Florentz – Konopnicki, Ron D. Rothblum
* [Permalink](https://eprint.iacr.org/2024/1493)
* [Download](https://eprint.iacr.org/2024/1493.pdf)

### Abstract

We show that every NP relation that can be verified by a bounded-depth polynomial-sized circuit, or a bounded-space polynomial-time algorithm, has a computational zero-knowledge proof (with statistical soundness) with communication that is only additively larger than the witness length. Our construction relies only on the minimal assumption that one-way functions exist.
   
    In more detail, assuming one-way functions, we show that every NP relation that can be verified in NC has a zero-knowledge proof with communication $|w|+poly(\lambda,\log(|x|))$ and relations that can be verified in SC have a zero-knowledge proof with communication $|w|+|x|^\epsilon \cdot poly(\lambda)$.. Here $\epsilon>0$ is an arbitrarily small constant and \lambda denotes the security parameter. As an immediate corollary, we also get that any NP relation, with a size S verification circuit (using unbounded fan-in XOR, AND and OR gates), has a zero-knowledge proof with communication $S+poly(\lambda,\log(S))$.

    Our result improves on a recent result of Nassar and Rothblum (Crypto, 2022), which achieve length $(1+\epsilon) \cdot |w|+|x|^\epsilon \cdot poly(\lambda)$ for bounded-space computations, and is also considerably simpler. Building on a work of Hazay et al. (TCC 2023), we also give a more complicated version of our result in which the parties only make a black-box use of the one-way function, but in this case we achieve only an inverse polynomial soundness error.



## 2024/1494

* Title: Concretely Efficient Private Set Union via Circuit-based PSI
* Authors: Gowri R Chandran, Thomas Schneider, Maximilian Stillger, Christian Weinert
* [Permalink](https://eprint.iacr.org/2024/1494)
* [Download](https://eprint.iacr.org/2024/1494.pdf)

### Abstract

Private set intersection (PSI) is a type of private set operation (PSO) for which concretely efficient linear-complexity protocols do exist.
However, the situation is currently less satisfactory for other relevant PSO problems such as private set union (PSU):
For PSU, the most promising protocols either rely entirely on computationally expensive public-key operations or suffer from substantial communication overhead.

In this work, we present the first PSU protocol that is mainly based on efficient symmetric-key primitives yet enjoys comparable communication as public-key-based alternatives.
Our core idea is to re-purpose state-of-the-art circuit-based PSI to realize a multi-query reverse private membership test (mq-RPMT), which is instrumental for building PSU.
We carefully analyze a privacy leakage issue resulting from the hashing paradigm commonly utilized in circuit-based PSI and show how to mitigate this via oblivious pseudorandom function (OPRF) and new shuffle sub-protocols.
Our protocol is modularly designed as a sequential execution of different building blocks that can be easily replaced by more efficient variants in the future, which will directly benefit the overall performance.

We implement our resulting PSU protocol, showing a run-time improvement of 10% over the state-of-the-art public-key-based protocol of Chen et al. (PKC'24) for input sets of size $2^{20}$.
Furthermore, we improve communication by $1.6\times$ over the state-of-the-art symmetric-key-based protocol of Zhang et al. (USENIX Sec'23).



## 2024/1495

* Title: Lattice-Based Vulnerabilities in Lee Metric Post-Quantum Cryptosystems
* Authors: Anna-Lena Horlemann, Karan Khathuria, Marc Newman, Amin Sakzad, Carlos Vela Cabello
* [Permalink](https://eprint.iacr.org/2024/1495)
* [Download](https://eprint.iacr.org/2024/1495.pdf)

### Abstract

Post-quantum cryptography has gained attention due to the need for secure cryptographic systems in the face of quantum computing. Code-based and lattice-based cryptography are two promi- nent approaches, both heavily studied within the NIST standardization project. Code-based cryptography—most prominently exemplified by the McEliece cryptosystem—is based on the hardness of decoding random linear error-correcting codes. Despite the McEliece cryptosystem having been unbroken for several decades, it suffers from large key sizes, which has led to exploring variants using metrics than the Hamming metric, such as the Lee metric. This alternative metric may allow for smaller key sizes, but requires further analysis for potential vulnerabilities to lattice- based attack techniques. In this paper, we consider a generic Lee met- ric based McEliece type cryptosystem and evaluate its security against lattice-based attacks.



## 2024/1496

* Title: No Fish Is Too Big for Flash Boys! Frontrunning on DAG-based Blockchains
* Authors: Jianting Zhang, Aniket Kate
* [Permalink](https://eprint.iacr.org/2024/1496)
* [Download](https://eprint.iacr.org/2024/1496.pdf)

### Abstract

Frontrunning is rampant in blockchain ecosystems, yielding attackers profits that have already soared into several million. Most existing frontrunning attacks focus on manipulating transaction order (namely, prioritizing attackers' transactions before victims' transactions) $\textit{within}$ a block. However, for the emerging directed acyclic graph (DAG)-based blockchains, these intra-block frontrunning attacks may not fully reveal the frontrunning vulnerabilities as they introduce block ordering rules to order transactions belonging to distinct blocks.

This work performs the first in-depth analysis of frontrunning attacks toward DAG-based blockchains. We observe that the current block ordering rule is vulnerable to a novel $\textit{inter-block}$ frontrunning attack, which enables the attacker to prioritize ordering its transactions before the victim transactions across blocks. We introduce three attacking strategies: $\textit{(i)}$ Fissure attack, where attackers render the victim transactions ordered later by disconnecting the victim's blocks. $\textit{(ii)}$ Speculative attack, where attackers speculatively construct order-priority blocks. $\textit{(iii)}$ Sluggish attack, where attackers deliberately create low-round blocks assigned a higher ordering priority by the block ordering rule.

We implement our attacks on two open-source DAG-based blockchains, Bullshark and Tusk. We extensively evaluate our attacks in geo-distributed AWS and local environments by running up to $n=100$ nodes. Our experiments show remarkable attack effectiveness. For instance, with the speculative attack, the attackers can achieve a $92.86\%$ attack success rate (ASR) on Bullshark and an $86.27\%$ ASR on Tusk. Using the fissure attack, the attackers can achieve a $94.81\%$ ASR on Bullshark and an $87.31\%$ ASR on Tusk.

We also discuss potential countermeasures for the proposed attack, such as ordering blocks randomly and reordering transactions globally based on transaction fees. However, we find that they either compromise the performance of the system or make the protocol more vulnerable to frontrunning using the existing frontrunning strategies.



## 2024/1497

* Title: Low-degree Security of the Planted Random Subgraph Problem
* Authors: Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik
* [Permalink](https://eprint.iacr.org/2024/1497)
* [Download](https://eprint.iacr.org/2024/1497.pdf)

### Abstract

The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs $(H, G)$, where $G$ is an Erdos-Renyi random graph on $n$ vertices, and $H$ is
a random induced subgraph of $G$ on $k$ vertices.
Assuming the hardness of distinguishing these two distributions (with two leaked vertices), Abram et al. construct communication-efficient, computationally secure (1) 2-party private simultaneous messages (PSM)  and (2) secret sharing for forbidden graph structures.

We prove the low-degree hardness of detecting planted random subgraphs all the way up to $k\leq n^{1 - \Omega(1)}$.  This improves over Abram et al.'s analysis for $k \leq n^{1/2 - \Omega(1)}$.  The hardness extends to $r$-uniform hypergraphs for constant $r$.

Our analysis is tight in the distinguisher's degree, its advantage, and in the number of leaked vertices.  Extending the constructions of Abram et al, we apply the conjecture towards (1) communication-optimal multiparty PSM protocols for random functions and (2) bit secret sharing with share size $(1 + \epsilon)\log n$ for any $\epsilon > 0$ in which arbitrary minimal coalitions of up to $r$ parties can reconstruct and secrecy holds against all unqualified subsets of up to $\ell = o(\epsilon \log n)^{1/(r-1)}$ parties.



## 2024/1498

* Title: Practical Implementation of Pairing-Based zkSNARK in Bitcoin Script
* Authors: Federico Barbacovi, Enrique Larraia, Paul Germouty, Wei Zhang
* [Permalink](https://eprint.iacr.org/2024/1498)
* [Download](https://eprint.iacr.org/2024/1498.pdf)

### Abstract

Groth16 is a pairing-based zero-knowledge proof scheme that has a constant proof size and an efficient verification algorithm. Bitcoin Script is a stack-based low-level programming language that is used to lock and unlock bitcoins. In this paper, we present a practical implementation of the Groth16 verifier in Bitcoin Script deployable on the mainnet of a Bitcoin blockchain called BSV. Our result paves the way for a framework of verifiable computation on Bitcoin: a Groth16 proof is generated for the correctness of an off-chain computation and is verified in Bitcoin Script on-chain. This approach not only offers privacy but also scalability. Moreover, this approach enables smart contract capability on Bitcoin which was previously thought rather limited if not non-existent.



## 2024/1499

* Title: Multi-Key Fully-Homomorphic Aggregate MAC for Arithmetic Circuits
* Authors: Suvasree Biswas, Arkady Yerukhimovich
* [Permalink](https://eprint.iacr.org/2024/1499)
* [Download](https://eprint.iacr.org/2024/1499.pdf)

### Abstract

Homomorphic message authenticators allow a user to perform computation on previously authenticated data producing a tag $\sigma$ that can be used to verify the authenticity of the computation.  We extend this notion to consider a multi-party setting where we wish to produce a tag that allows verifying (possibly different) computations on all party's data at once.  Moreover, the size of this tag should not grow as a function of the number of parties or the complexity of the computations.  We construct the first aggregate homomorphic MAC scheme that achieves such aggregation of homomorphic tags.  Moreover, the final aggregate tag consists of only a single group element. 
Our construction supports aggregation of computations that can be expressed by bounded-depth arithmetic circuits and is secure in the random oracle model based on the hardness of the Computational Co-Diffie-Hellman problem over an asymmetric bilinear map.



## 2024/1500

* Title: Hard Quantum Extrapolations in Quantum Cryptography
* Authors: Luowen Qian, Justin Raizes, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/1500)
* [Download](https://eprint.iacr.org/2024/1500.pdf)

### Abstract

Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrapolation, first considered by Impagliazzo and Levin (1990), is hard if and only if one-way functions exist. Towards better understanding minimal assumptions for quantum cryptography, we study the quantum analogues of the universal extrapolation task. Specifically, we put forth the classical$\rightarrow$quantum extrapolation task, where we ask to extrapolate the rest of a bipartite pure state given the first register measured in the computational basis. We then use it as a key component to establish new connections in quantum cryptography: (a) quantum commitments exist if classical$\rightarrow$quantum extrapolation is hard; and (b) classical$\rightarrow$quantum extrapolation is hard if any of the following cryptographic primitives exists: quantum public-key cryptography (such as quantum money and signatures) with a classical public key or 2-message quantum key distribution protocols.

For future work, we further generalize the extrapolation task and propose a fully quantum analogue. We observe that it is hard if quantum commitments exist, and it is easy for quantum polynomial space.



## 2024/1501

* Title: Exploring User Perceptions of Security Auditing in the Web3 Ecosystem
* Authors: Molly Zhuangtong Huang, Rui Jiang, Tanusree Sharma, Kanye Ye Wang
* [Permalink](https://eprint.iacr.org/2024/1501)
* [Download](https://eprint.iacr.org/2024/1501.pdf)

### Abstract

In the rapidly evolving Web3 ecosystem, transparent auditing has emerged as a critical component for both applications and users. However, there is a significant gap in understanding how users perceive this new form of auditing and its implications for Web3 security. Utilizing a mixed-methods approach that incorporates a case study, user interviews, and social media data analysis, our study leverages a risk perception model to comprehensively explore Web3 users' perceptions regarding information accessibility, the role of auditing, and its influence on user behavior. Based on these extensive findings, we discuss how this open form of auditing is shaping the security of the Web3 ecosystem, identifying current challenges, and providing design implications.



## 2024/1502

* Title: TopGear 2.0: Accelerated Authenticated Matrix Triple Generation with Scalable Prime Fields via Optimized HE Packing
* Authors: HyunHo Cha, Intak Hwang, Seonhong Min, Jinyeong Seo, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/1502)
* [Download](https://eprint.iacr.org/2024/1502.pdf)

### Abstract

The SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries.
Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares, called authenticated triples, are generated.
However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are required.

In this work, we propose a new protocol for the SPDZ offline phase, TopGear 2..0, which improves upon the previous state-of-the-art construction, TopGear (Baum et al., SAC'19), and its variant for matrix triples (Chen et al., Asiacrypt'20).
Our protocol aims to achieve a speedup in matrix triple generation and support for larger prime fields, up to 4096 bits in size.
To achieve this, we employ a variant of the BFV scheme and a homomorphic matrix multiplication algorithm optimized for our purpose.

As a result, our protocol achieves about 3.6x speedup for generating scalar triples in a 1024-bit prime field and about 34x speedup for generating 128x128 matrix triples.
In addition, we reduce the size of evaluation keys from 27.4 GB to 0.22 GB and the communication cost for MAC key generation from 816 MB to 16.6 MB.



## 2024/1503

* Title: Scalable Mixnets from Mercurial Signatures on Randomizable Ciphertexts
* Authors: Masayuki Abe, Masaya Nanri, Miyako Ohkubo, Octavio Perez Kempner, Daniel Slamanig, Mehdi Tibouchi
* [Permalink](https://eprint.iacr.org/2024/1503)
* [Download](https://eprint.iacr.org/2024/1503.pdf)

### Abstract

A mix network, or mixnet, is a cryptographic tool for anonymous routing, taking messages from multiple (identifiable) senders and delivering them in a randomly permuted order. Traditional mixnets employ encryption and proofs of correct shuffle to cut the link between each sender and their input.

Hébant et al. (PKC '20) introduced a novel approach to scalable
mixnets based on linearly homomorphic signatures. Unfortunately, their security model is too weak to support voting applications. Building upon their work, we leverage recent advances in equivalence class signatures, replacing linearly homomorphic signatures to obtain more efficient mixnets with security in a more robust model. More concretely, we introduce the notion of mercurial signatures on randomizable ciphertexts along with an efficient construction, which
we use to build a scalable mixnet protocol suitable for voting. We compare our approach to other (scalable) mixnet approaches, implement our protocols, and provide concrete performance benchmarks. Our findings show our mixnet significantly outperforms existing alternatives in efficiency and scalability. Verifying the mixing process for 50k ciphertexts takes 135 seconds on a commodity laptop (without parallelization) when employing ten mixers.



## 2024/1504

* Title: Comments on "Privacy-Enhanced Federated Learning Against Poisoning Adversaries"
* Authors: Thomas Schneider, Ajith Suresh, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2024/1504)
* [Download](https://eprint.iacr.org/2024/1504.pdf)

### Abstract

In August 2021, Liu et al. (IEEE TIFS'21) proposed a privacy-enhanced framework named PEFL  to efficiently detect poisoning behaviours in Federated Learning (FL) using homomorphic encryption. In this article, we show that PEFL does not preserve privacy. In particular, we illustrate that PEFL reveals the entire gradient vector of all users in clear to one of the participating entities, thereby violating privacy. Furthermore, we clearly show that an immediate fix for this issue is still insufficient to achieve privacy by pointing out multiple flaws in the proposed system.



## 2024/1505

* Title: FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE
* Authors: Jeongeun Park, Barry Van Leeuwen, Oliver Zajonc
* [Permalink](https://eprint.iacr.org/2024/1505)
* [Download](https://eprint.iacr.org/2024/1505.pdf)

### Abstract

Multi-key fully homomorphic encryption (MKFHE), a generalization of
fully homomorphic encryption (FHE), enables a computation over encrypted data
under multiple keys. The first MKFHE schemes were based on the NTRU primitive,
however these early NTRU based FHE schemes were found to be insecure due to the
problem of over-stretched parameters. Recently, in the case of standard (non-multi
key) FHE a secure version, called FINAL, of NTRU has been found. In this work
we extend FINAL to an MKFHE scheme, this allows us to benefit from some of
the performance advantages provided by NTRU based primitives. Thus, our scheme
provides competitive performance against current state-of-the-art multi-key TFHE,
in particular reducing the computational complexity from quadratic to linear in the
number of keys.



## 2024/1506

* Title: Bit Security: optimal adversaries, equivalence results, and a toolbox for computational-statistical security analysis
* Authors: Daniele Micciancio, Mark Schultz-Wu
* [Permalink](https://eprint.iacr.org/2024/1506)
* [Download](https://eprint.iacr.org/2024/1506.pdf)

### Abstract

We investigate the notion of bit-security for decisional cryptographic properties, as originally proposed in (Micciancio & Walter, Eurocrypt 2018), and its main variants and extensions, with the goal clarifying the relation between different definitions, and facilitating their use.
Specific contributions of this paper include:
(1) identifying the optimal adversaries achieving the highest possible  MW advantage, showing that they are deterministic and have a very simple threshold structure;
(2) giving a simple proof that a competing definition proposed by (Watanabe & Yasunaga, Asiacrypt 2021) is actually equivalent to the original MW definition; and
(3) developing tools for the use of the extended notion of computational-statistical bit-security introduced in (Li, Micciancio, Schultz & Sorrell, Crypto 2022), showing that it fully supports common cryptographic proof techniques like hybrid arguments and probability replacement theorems.
On the technical side, our results are obtained by introducing a new notion of "fuzzy" distinguisher (which we prove equivalent to the "aborting" distinguishers of Micciancio and Walter), and a tight connection between the MW advantage and the Le Cam metric, a standard quantity used in statistics.



## 2024/1507

* Title: Unbounded ABE for Circuits from LWE, Revisited
* Authors: Valerio Cini, Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2024/1507)
* [Download](https://eprint.iacr.org/2024/1507.pdf)

### Abstract

We introduce new lattice-based techniques for building ABE for circuits with unbounded attribute length based on the LWE assumption, improving  upon the previous constructions of Brakerski and Vaikuntanathan (CRYPTO 16) and Goyal, Koppula, and Waters (TCC 16).  Our main result is a simple and more efficient unbounded ABE scheme for circuits where only the circuit depth is fixed at set-up; this is the first unbounded ABE scheme for circuits that rely only on black-box access to cryptographic and lattice algorithms. The scheme achieves semi-adaptive security against unbounded collusions under the LWE assumption.. The encryption time and ciphertext size are roughly $3 \times$ larger than the prior bounded ABE of Boneh et al. (EUROCRYPT 2014), substantially improving upon the encryption times in prior works. As a secondary contribution, we present an analogous result for unbounded inner product predicate encryption that satisfies weak attribute-hiding.



## 2024/1508

* Title: Key Collisions on AES and Its Applications
* Authors: Kodai Taiyama, Kosei Sakamoto, Ryoma Ito, Kazuma Taka, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2024/1508)
* [Download](https://eprint.iacr.org/2024/1508.pdf)

### Abstract

In this paper, we explore a new type of key collisions called target-plaintext key collisions of AES, which emerge as an open problem in the key committing security and are directly converted into single-block collision attacks on Davies-Meyer (DM) hashing mode. For this key collision, a ciphertext collision is uniquely observed when a specific plaintext is encrypted under two distinct keys. We introduce an efficient automatic search tool designed to find target-plaintext key collisions. This tool exploits bit-wise behaviors of differential characteristics and dependencies among operations and internal variables of both data processing and key scheduling parts. This allows us to hierarchically perform rebound-type attacks to identify key collisions. As a result, we demonstrate single-block collision attacks on 2/5/6-round AES-128/192/256-DM and semi-free-start collision attacks on 5/7/9-round AES-128/192/256-DM, respectively. To validate our attacks, we provide an example of fixed-target-plaintext key collision/semi-free-start collisions on 9-round AES-256-DM.  Furthermore, by exploiting a specific class of free-start collisions with our tool, we present two-block collision attacks on 3/9-round AES-128/256-DM, respectively.



## 2024/1509

* Title: DUPLEX: Scalable Zero-Knowledge Lookup Arguments over RSA Group
* Authors: Semin Han, Geonho Yoon, Hyunok Oh, Jihye Kim
* [Permalink](https://eprint.iacr.org/2024/1509)
* [Download](https://eprint.iacr.org/2024/1509.pdf)

### Abstract

Lookup arguments enable a prover to convince a verifier that a committed vector of lookup elements $\vec{f} \in \mathbb{F}^m$ is contained within a predefined table $T \in \mathbb{F}^N$. These arguments are particularly beneficial for enhancing the performance of SNARKs in handling non-arithmetic operations, such as batched range checks or bitwise operations. While existing works have achieved efficient and succinct lookup arguments, challenges remain, particularly when dealing with large vectors of lookup elements in privacy-sensitive applications.

In this paper, we introduce $\duplex$, a scalable zero-knowledge lookup argument scheme that offers significant improvements over previous approaches. Notably, we present the first lookup argument designed to operate over the RSA group. Our core technique allows for the transformation of elements into prime numbers to ensure compatibility with the RSA group, all without imposing substantial computational costs on the prover. Given $m$ lookup elements, $\duplex$ achieves an asymptotic proving time of $O(m \log m)$, with constant-sized proofs, constant-time verification, and a public parameter size independent of the table size $N$. Additionally, $\duplex$ ensures the privacy of lookup elements and is robust against dynamic table updates, making it highly suitable for scalable verifiable computation in real-world applications.

We implemented and empirically evaluated $\duplex$, comparing it with the state-of-the-art zero-knowledge lookup argument Caulk [CCS'22]. Our experimental results demonstrate that $\duplex$ significantly outperforms Caulk in proving time for both single and batched lookup arguments, while maintaining practical proof size and verification time.



## 2024/1510

* Title: Group Factorisation for Smaller Signatures from Cryptographic Group Actions
* Authors: Giuseppe D'Alconzo, Alessio Meneghetti, Edoardo Signorini
* [Permalink](https://eprint.iacr.org/2024/1510)
* [Download](https://eprint.iacr.org/2024/1510.pdf)

### Abstract

Cryptographic group actions have gained significant attention in recent years for their application on post-quantum Sigma protocols and digital signatures.. In NIST's recent additional call for post-quantum signatures, three relevant proposals are based on group actions: LESS, MEDS, and ALTEQ. This work explores signature optimisations leveraging a group's factorisation. We show that if the group admits a factorisation as a semidirect product of subgroups, the group action can be restricted on a quotient space under the equivalence relation induced by the factorisation. If the relation is efficiently decidable, we show that it is possible to construct an equivalent Sigma protocol for a relationship that depends only on one of the subgroups. Moreover, if a special class of representative of the quotient space is efficiently computable via a canonical form, the restricted action is effective and does not incur in security loss.
Finally, we apply these techniques to the group actions underlying LESS and MEDS, showing how they will affect the length of signatures and public keys.



## 2024/1511

* Title: Some Classes of Cubic Monomial Boolean Functions with Good  Second-Order Nonlinearity
* Authors: RUCHI TELANG GODE
* [Permalink](https://eprint.iacr.org/2024/1511)
* [Download](https://eprint.iacr.org/2024/1511.pdf)

### Abstract

It is well known that estimating a sharp lower bound on the second-order nonlinearity of a general class of cubic  Booleanfunction  is a difficult task. In this paper for a given integer $n \geq 4$,  some values of $s$ and $t$  are determined for which  cubic monomial Boolean functions of the form $h_{\mu}(x)=Tr( \mu x^{2^s+2^t+1})$ $(n>s>t \geq 1)$  possess good lower bounds on their  second-order nonlinearity. The obtained functions are worth considering for securing symmetric cryptosystems against various quadratic approximation attacks and fast algebraic attacks.



## 2024/1512

* Title: Improved Soundness Analysis of the FRI Protocol
* Authors: Yiwen Gao, Haibin Kan, Yuan Li
* [Permalink](https://eprint.iacr.org/2024/1512)
* [Download](https://eprint.iacr.org/2024/1512.pdf)

### Abstract

We enhance the provable soundness of FRI, an interactive oracle proof of proximity (IOPP) for Reed-Solomon codes introduced by Ben-Sasson et al. in ICALP 2018. More precisely, we prove the soundness error of FRI is less than $\max\left\{O\left(\frac{1}{\eta}\cdot \frac{n}{|\mathbb{F}_q|}\right), (1-\delta)^{t}\right\}$, where $\delta\le 1-\sqrt{\rho}-\eta$ is within the Johnson bound and $\mathbb{F}_q$ is a finite field with characteristic greater than $2$. Previously, the best-known provable soundness error for FRI was $\max\left\{O\left(\frac{\rho^2}{\eta^7}\cdot \frac{n^2}{|\mathbb{F}_q|}\right), (1-\delta)^{t}\right\}$, as established by Ben-Sasson et al. in FOCS 2020.

We prove the number of \emph{bad} folding points in FRI is linear in the length $n$ of codeword when it is $\delta$-far from the Reed-Solomon code. This implies the linear proximity gaps for Reed-Solomon codes and improves the provable soundness of batched FRI. Our results indicate that the FRI protocol can be implemented over a smaller field, thereby enhancing its efficiency. Furthermore, for a fixed finite field $\mathbb{F}_q$, we prove that FRI can achieve improved security.



## 2024/1513

* Title: Depth Optimized Circuits for Lattice Based Voting with Large Candidate Sets
* Authors: Oskar Goldhahn, Kristian Gjøsteen
* [Permalink](https://eprint.iacr.org/2024/1513)
* [Download](https://eprint.iacr.org/2024/1513.pdf)

### Abstract

Homomorphic encryption has long been used to build voting
schemes. Additively homomorphic encryption only allows simple count-
ing functions. Lattice-based fully (or somewhat) homomorphic encryp-
tion allows more general counting functions, but the required parameters
quickly become impractical if used naively. It is safe to leak information
during the counting function evaluation, as long as the information could
be derived from the public result. To exploit this observation, we de-
sign a flexible framework for using somewhat homomorphic encryption
for voting that incorporates random input and allows controlled leakage
of information. We instantiate the framework using novel circuits with
low but significant multiplicative depth exploiting the fact that, in the
context of voting, leakage of certain information during homomorphic
evaluation can be permitted. We also instantiate the framework with a
circuit that uses random input to shuffle without the use of mixnets.



## 2024/1514

* Title: Black-Box Non-Interactive Zero Knowledge from Vector Trapdoor Hash
* Authors: Pedro Branco, Arka Rai Choudhuri, Nico Döttling, Abhishek Jain, Giulio Malavolta, Akshayaram Srinivasan
* [Permalink](https://eprint.iacr.org/2024/1514)
* [Download](https://eprint.iacr.org/2024/1514.pdf)

### Abstract

We present a new approach for constructing non-interactive zero-knowledge (NIZK) proof systems from vector trapdoor hashing (VTDH) -- a generalization of trapdoor hashing [Döttling et al., Crypto'19]. Unlike prior applications of trapdoor hash to NIZKs, we use VTDH to realize the hidden bits model [Feige-Lapidot-Shamir, FOCS'90] leading to black-box constructions of NIZKs. This approach gives us the following new results:
 - A statistically-sound NIZK proof system based on the hardness of decisional Diffie-Hellman (DDH) and learning parity with noise (LPN) over finite fields with inverse polynomial noise rate. This gives the first statistically sound NIZK proof system that is not based on either LWE, or bilinear maps, or factoring.
 - A dual-mode NIZK satisfying statistical zero-knowledge in the common random string mode and statistical soundness in the common reference string mode assuming the hardness of learning with errors (LWE) with polynomial modulus-to-noise ratio. This gives the first black-box construction of such a dual-mode NIZK under LWE. This improves the recent work of Waters (STOC'24) which relied on LWE with super-polynomial modulus-to-noise ratio and required a setup phase with private coins.

The above constructions are black-box and satisfy single-theorem zero-knowledge property. Building on the works of Feige et al.(FOCS'90) and Fishclin and Rohrback (PKC'21), we upgrade these constructions (under the same assumptions) to satisfy multi-theorem zero-knowledge property at the expense of making non-black-box use of cryptography.



## 2024/1515

* Title: Optimized Software Implementation of Keccak, Kyber, and Dilithium on RV{32,64}IM{B}{V}
* Authors: Jipeng Zhang, Yuxing Yan, Junhao Huang, Çetin Kaya Koç
* [Permalink](https://eprint.iacr.org/2024/1515)
* [Download](https://eprint.iacr.org/2024/1515.pdf)

### Abstract

With the standardization of NIST post-quantum cryptographic (PQC) schemes, optimizing these PQC schemes across various platforms presents significant research value. While most existing software implementation efforts have concentrated on ARM platforms, research on PQC implementations utilizing various RISC-V instruction set architectures (ISAs) remains limited.
In light of this gap, this paper proposes comprehensive and efficient optimizations of Keccak, Kyber, and Dilithium on RV{32,64}IM{B}{V}. We thoroughly optimize these implementations for dual-issue CPUs, believing that our work on various RISC-V ISAs will provide valuable insights for future PQC deployments.

Specifically, for Keccak, we revisit a range of optimization techniques, including bit interleaving, lane complementing, in-place processing, and hybrid vector/scalar implementations. We construct an optimal combination of methods aimed at achieving peak performance on dual-issue CPUs for various RISC-V ISAs.
For the NTT implementations of Kyber and Dilithium, we deliver optimized solutions based on Plantard and Montgomery arithmetic for diverse RISC-V ISAs, incorporating extensive dual-issue enhancements. Additionally, we improve the signed Plantard multiplication algorithm proposed by Akoi et al.
Ultimately, our testing demonstrates that our implementations of Keccak and NTT across various ISAs achieve new performance records. More importantly, they significantly enrich the PQC software ecosystem for RISC-V.



## 2024/1516

* Title: Practical Mempool Privacy via One-time Setup Batched Threshold Encryption
* Authors: Arka Rai Choudhuri, Sanjam Garg, Guru-Vamsi Policharla, Mingyuan Wang
* [Permalink](https://eprint.iacr.org/2024/1516)
* [Download](https://eprint.iacr.org/2024/1516.pdf)

### Abstract

An important consideration with the growth of the DeFi ecosystem is the protection of clients who submit transactions to the system. As it currently stands, the public visibility of these transactions in the memory pool (mempool) makes them susceptible to market manipulations such as frontrunning and backrunning. More broadly, for various reasons—ranging from avoiding market manipulation to including time-sensitive information in their transactions—clients may want the contents of their transactions to remain private until they are executed, i.e. they have *pending transaction privacy*. Therefore, *mempool privacy* is becoming an increasingly important feature as DeFi applications continue to spread.

    We construct the first *practical* mempool privacy scheme that uses a *one-time* DKG setup for $n$ decryption servers. Our scheme ensures the strong privacy requirement by not only hiding the transactions until they are decrypted but also guaranteeing privacy for transactions that were not selected in the epoch (*pending transaction privacy*). For each epoch (or block), clients can encrypt their transactions so that, once $B$ (encrypted) transactions are selected for the epoch, they can be decrypted by each decryption server while communicating only $O(1)$ information.

    Our result improves upon the best-known prior works, which either: (i) require an expensive initial setup involving a (special purpose) multiparty computation protocol executed by the $n$ decryption servers, along with an additional *per-epoch* setup; (ii) require each decryption server to communicate $O(B)$ information; or (iii) do not guarantee pending transaction privacy.

    We implement our scheme and find that transactions can be encrypted in approximately 8.5 ms, independent of committee size, and the communication required to decrypt an entire batch of transactions is 48 bytes per party, independent of the number of transactions. If deployed on Ethereum, which processes close to 500 transactions per block, it takes close to 3.2 s for each committee member to compute a partial decryption and 3.0 s to decrypt all transactions for a block in single-threaded mode. Compared to prior work, which had an expensive setup phase per epoch, we incur $<2\times$ overhead in the worst case. On some metrics such as partial decryptions size, we actually fare better.



## 2024/1517

* Title: A Note on the SNOVA Security
* Authors: Lih-Chung Wang, Chun-Yen Chou, Jintai Ding, Yen-Liang Kuan, Jan Adriaan Leegwater, Ming-Siou Li, Bo-Shu Tseng, Po-En Tseng, Chia-Chun Wang
* [Permalink](https://eprint.iacr.org/2024/1517)
* [Download](https://eprint.iacr.org/2024/1517.pdf)

### Abstract

SNOVA is one of the submissions in the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition. SNOVA is a UOV variant that uses the noncommutative-ring technique to educe the size of the public key. SNOVA's public key size and signature size are well-balanced and have good performance. Recently, Beullens proposed a forgery attack against SNOVA, pointing out that the parameters of SNOVA can be attacked. Beullens also argued that with some slight adjustments his attacks can be prevented. In this note, we explain Beullens' forgery attack and show that the attack can be invalid by two different approaches. Finally, we show that these two approaches do not increase the sizes of the public keys or signatures and the current parameters satisfy the security requirement of NIST.



## 2024/1518

* Title: Witness Semantic Security
* Authors: Paul Lou, Nathan Manohar, Amit Sahai
* [Permalink](https://eprint.iacr.org/2024/1518)
* [Download](https://eprint.iacr.org/2024/1518.pdf)

### Abstract

To date, the strongest notions of security achievable for two-round publicly-verifiable cryptographic proofs for $\mathsf{NP}$ are witness indistinguishability (Dwork-Naor 2000, Groth-Ostrovsky-Sahai 2006), witness hiding (Bitansky-Khurana-Paneth 2019, Kuykendall-Zhandry 2020), and super-polynomial simulation (Pass 2003, Khurana-Sahai 2017). On the other hand, zero-knowledge and even weak zero-knowledge (Dwork-Naor-Reingold-Stockmeyer 1999) are impossible in the two-round publicly-verifiable setting (Goldreich-Oren 1994). This leaves an enormous gap in our theoretical understanding of known achievable security and the impossibility results for two-round publicly-verifiable cryptographic proofs  for $\mathsf{NP}$.

    Towards filling this gap, we propose a new and natural notion of security, called witness semantic security, that captures the natural and strong notion that an adversary should not be able to learn any partial information about the prover's witness beyond what it could learn given only the statement $x$. Not only does our notion of witness semantic security subsume both witness indistinguishability and witness hiding, but it also has an easily appreciable interpretation.

    Moreover, we show that assuming the subexponential hardness of LWE, there exists a two-round public-coin publicly-verifiable witness semantic secure argument. To our knowledge, this is the strongest form of security known for this setting.

    As a key application of our work, we show that non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model can additionally maintain witness semantic security even when the CRS is maliciously generated. Our work gives the first construction from (subexponential) standard assumptions that achieves a notion stronger than witness-indistinguishability against a malicious CRS authority.

    In order to achieve our results, we give the first construction of a ZAP from subexponential LWE that is adaptively sound. Additionally, we propose a notion of simulation using non-uniform advice about a malicious CRS, which we also believe will be of independent interest.



## 2024/1519

* Title: Efficient theta-based algorithms  for computing $(\ell, \ell)$-isogenies  on Kummer surfaces for arbitrary odd $\ell$
* Authors: Ryo Yoshizumi, Hiroshi Onuki, Ryo Ohashi, Momonari Kudo, Koji Nuida
* [Permalink](https://eprint.iacr.org/2024/1519)
* [Download](https://eprint.iacr.org/2024/1519.pdf)

### Abstract

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. Recently, many isogeny-based cryptosystems  using  isogenies between Kummer surfaces were proposed. Most of those cryptosystems use $(2,2)$-isogenies. However, to enhance the possibility of cryptosystems, higher degree isogenies, say $(\ell,\ell)$-isogenies for an odd $\ell$, is also crucial. For an odd $\ell$, the Lubicz-Robert gave a  formula to compute $(\ell)^g$-isogenies in general dimension $g$.  In this paper, we propose explicit and efficient algorithms to compute $(\ell,\ell)$-isogenies  between Kummer surfaces, based on the Lubicz-Robert formula.In particular, we propose two algorithms for computing the codomain of the isogeny and two algorithms for evaluating the image of a point under the isogeny. Then, we count the number of arithmetic operations required for each of our proposed algorithms, and determine the most efficient algorithm in terms of the number of arithmetic operations from each of two types of algorithms for each $\ell$. As an application, using the most efficient one, we implemented the SIDH attack on B-SIDH in SageMath.In setting that  originally claimed 128-bit security, our implementation was able to recover that secret key  in about 11 hours.



## 2024/1520

* Title: On the rough order assumption in imaginary quadratic number fields
* Authors: Antonio Sanso
* [Permalink](https://eprint.iacr.org/2024/1520)
* [Download](https://eprint.iacr.org/2024/1520.pdf)

### Abstract

In this paper, we investigate the rough order assumption (\(RO_C\)) introduced by Braun, Damgård, and Orlandi at CRYPTO 23, which posits that class groups of imaginary quadratic fields with no small prime factors in their order are computationally indistinguishable from general class groups. We present a novel attack that challenges the validity of this assumption by leveraging properties of Mordell curves over the rational numbers. Specifically, we demonstrate that if the rank of the Mordell curve \( E_{-16D} \) is at least 2, it contradicts the rough order assumption. Our attack deterministically breaks the \(RO_C\) assumption for discriminants of a special form, assuming the parity conjecture holds and certain conditions are met. Additionally, for both special and generic cases, our results suggest that the presence of nontrivial 3-torsion elements in class groups can undermine the \(RO_C\) assumption. Although our findings are concrete for specific cases, the generic scenario relies on heuristic arguments related to the Birch and Swinnerton-Dyer (BSD) conjecture, a significant and widely believed conjecture in number theory. Attacks against 2-torsion elements in class groups are already well known, but our work introduces a distinct approach targeting 3-torsion elements. These attacks are fundamentally different in nature, and both have relatively straightforward countermeasures, though they do not generalize to higher torsions. While these results do not entirely invalidate the \(RO_C\) assumption, they highlight the need for further exploration of its underlying assumptions, especially in the context of specific torsion structures within class groups.



## 2024/1521

* Title: The SMAesH dataset
* Authors: Gaëtan Cassiers, Charles Momin
* [Permalink](https://eprint.iacr.org/2024/1521)
* [Download](https://eprint.iacr.org/2024/1521.pdf)

### Abstract

Datasets of side-channel leakage measurements are widely used in research to develop and benchmarking side-channel attack and evaluation methodologies. Compared to using custom and/or one-off datasets, widely-used and publicly available datasets improve research reproducibility and comparability. Further, performing high-quality measurements requires specific equipment and skills, while also taking a significant amount of time. Therefore, using publicly available datasets lowers the barriers to entry into side-channel research. This paper introduces the SMAesH dataset. SMAesH is an optimized masked hardware implementation of the AES with a provably secure arbitrary-order masking scheme. The SMAesH dataset contains power traces of the first-order SMAesH on two FPGAs of different generations, along with key, plaintext and masking randomness. A part of the dataset use uniformly random key and plaintext to enable leakage profiling, while another part uses a fixed key (still with uniformly random plaintext) to enable attack validation or leakage assessment in a fixed-versus-random setting. We document the experimental setup used to acquire the dataset. It is built from components that are widely available. We also discuss particular methods employed to maximize the information content in the leakage traces, such as power supply selection, fine-grained trace alignment and resolution optimization.



## 2024/1522

* Title: Beware of Keccak: Practical Fault Attacks on SHA-3 to Compromise Kyber and Dilithium on ARM Cortex-M Devices
* Authors: Yuxuan Wang, Jintong Yu, Shipei Qu, Xiaolin Zhang, Xiaowei Li, Chi Zhang, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/1522)
* [Download](https://eprint.iacr.org/2024/1522.pdf)

### Abstract

Keccak acts as the hash algorithm and eXtendable-Output Function (XOF) specified in the NIST standard drafts for Kyber and Dilithium. The Keccak output is highly correlated with sensitive information. While in RSA and ECDSA, hash-like components are only used to process public information, such as the message. The importance and sensitivity of hash-like components like Keccak are much higher in Kyber and Dilithium than in traditional public-key cryptography. However, few works study Keccak regarding the physical security of Kyber and Dilithium. In this paper, we propose a practical fault attack scheme on Keccak to compromise Kyber and Dilithium on ARM Cortex-M devices. Specifically, by injecting loop-abort faults in the iterative assignments or updates of Keccak, we propose six attacks that can set the Keccak output to a known value. These attacks can be exploited to disrupt the random number expansion or other critical processes in Kyber and Dilithium, thereby recovering sensitive information derived from the Keccak output. In this way, we propose eight attack strategies on Kyber and seven on Dilithium, achieving key recovery, signature forgery, and verification bypass. To validate the practicality of the proposed attack strategies, we perform fault characterization on five real-world devices belonging to four different series (ARM Cortex-M0+, M3, M4, and M33). The success rate is up to 89.5%, demonstrating the feasibility of loop-abort faults. This paper also provides a guide for reliably inducing loop-abort faults on ARM Cortex-M devices using electromagnetic fault injection. We further validate our complete attacks on Kyber and Dilithium based on the official implementations, achieving a success rate of up to 55.1%. The results demonstrate that the excessive use of Keccak in generating and computing secret information leads to severe vulnerabilities. Our work can potentially be migrated to other post-quantum cryptographic algorithms that use Keccak, such as Falcon, BIKE, and HQC.



## 2024/1523

* Title: Functional Adaptor Signatures: Beyond All-or-Nothing Blockchain-based Payments
* Authors: Nikhil Vanjani, Pratik Soni, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2024/1523)
* [Download](https://eprint.iacr.org/2024/1523.pdf)

### Abstract

In scenarios where a seller holds sensitive data $x$, like employee / patient records or ecological data, and a buyer seeks to obtain an evaluation of specific function $f$ on this data, solutions in trustless digital environments like blockchain-based Web3 systems typically fall into two categories: (1) Smart contract-powered solutions and (2) cryptographic solutions leveraging tools such as adaptor signatures. The former approach offers atomic transactions where the buyer learns the function evaluation $f(x)$ (and not $x$ entirely) upon payment. However, this approach is often inefficient, costly, lacks privacy for the seller's data, and is incompatible with systems that do not support smart contracts with required functionalities. In contrast, the adaptor signature-based approach addresses all of the above issues but comes with an "all-or-nothing" guarantee, where the buyer fully extracts $x$ and does not support functional extraction of the sensitive data. In this work, we aim to bridge the gap between these approaches, developing a solution that enables fair functional sales of information while offering improved efficiency, privacy, and compatibility similar to adaptor signatures.

Towards this, we propose functional adaptor signatures (FAS) a novel cryptographic primitive that achieves all the desired properties as listed above. Using FAS, the seller can publish an advertisement committing to $x$. The buyer can pre-sign the payment transaction w.r.t. a function $f$, and send it along with the transaction to the seller.
The seller adapts the pre-signature into a valid (buyer's) signature and posts the payment and the adapted signature on the blockchain to get paid. Finally, using the pre-signature and the posted signature, the buyer efficiently extracts $f(x)$, and completes the sale. We formalize the security properties of FAS, among which is a new notion called witness privacy to capture seller's privacy, which ensures the buyer does not learn anything beyond $f(x)$.
We present multiple variants of witness privacy, namely, witness hiding, witness indistinguishability, and zero-knowledge, to capture varying levels of leakage about $x$ beyond $f(x)$ to a malicious buyer.

We introduce two efficient constructions of FAS supporting linear functions (like statistics/aggregates, kernels in machine learning, etc.), that satisfy the strongest notion of witness privacy. One construction is based on prime-order groups and compatible with Schnorr signatures for payments, and the other is based on lattices and compatible with a variant of Lyubashevsky's signature scheme. A central conceptual contribution of our work lies in revealing a surprising connection between functional encryption, a well-explored concept over the past decade, and adaptor signatures, a relatively new primitive in the cryptographic landscape. On a technical level, we avoid heavy cryptographic machinery and achieve improved efficiency, by making black-box use of building blocks like inner product functional encryption (IPFE) while relying on certain security-enhancing techniques for the IPFE in a non-black-box manner. We implement our FAS construction for Schnorr signatures and show that for reasonably sized seller witnesses, the different operations are quite efficient even for commodity hardware.



## 2024/1524

* Title: Lower Bounds on the Overhead of Indistinguishability Obfuscation
* Authors: Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass
* [Permalink](https://eprint.iacr.org/2024/1524)
* [Download](https://eprint.iacr.org/2024/1524.pdf)

### Abstract

We consider indistinguishability obfuscation (iO) for multi-output circuits $C:\{0,1\}^n\to\{0,1\}^n$ of size s, where s is the number of AND/OR/NOT gates in C. Under the worst-case assumption that NP $\nsubseteq$ BPP, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size $s + o(s/ \log s)$. In other words, to be secure, an efficient iO scheme must incur an $\Omega(s/ \log s)$ additive overhead in the size of the obfuscated circuit. The hardness assumption under which this negative result holds is minimal since an optimal iO scheme with no circuit size overhead exists if NP$\nsubseteq$ BPP.

Expanding on this result, we also rule out iO for single-output database-aided circuits with an arbitrary polynomial overhead in circuit size. This strengthens an impossibility result by Goldwasser and Rothblum [GR07], which considered circuits with access to an exponential-length database that the obfuscator has oracle access to; in contrast, our impossibility result holds even w.r..t. polynomial-size databases and even w.r.t. obfuscators that may run in time polynomial in the size of the database (and thus may read the whole database).

The proof of our main result builds on a connection between obfuscation and meta-complexity put forward by Mazor and Pass [MP24], and on the NP-hardness of circuit minimization for multi-output circuits established by Loff, Ilango, and Oliveira [ILO20], together with other techniques from cryptography and complexity theory.



## 2024/1525

* Title: Evaluating Leakage Attacks Against Relational Encrypted Search
* Authors: Patrick Ehrler, Abdelkarim Kati, Thomas Schneider, Amos Treiber
* [Permalink](https://eprint.iacr.org/2024/1525)
* [Download](https://eprint.iacr.org/2024/1525.pdf)

### Abstract

Encrypted Search Algorithms (ESAs) are a technique to encrypt data while the user can still search over it. ESAs can protect privacy and ensure security of sensitive data stored on a remote storage. Originally, ESAs were used in the context of documents that consist of keywords. The user encrypts the documents, sends them to a remote server and is still able to search for keywords, without exposing information about the plaintext. The idea of ESAs has also been applied to relational databases, where queries (similar to SQL statements) can be privately executed on an encrypted database.But just as traditional schemes for Keyword-ESAs, also Relational-ESAs have the drawback of exposing some information, called leakage. Leakage attacks have been proposed in the literature that use this information together with auxiliary information to learn details about the plaintext. However, these leakage attacks have overwhelmingly been designed for and applied to Keyword-ESAs and not Relational-ESAs.
In this work, we review the suitability of major leakage attacks against ESAs in the relational setting by adapting them accordingly. We perform extensive re-evaluations of the attacks on various relational datasets with different properties.
Our evaluations show that major attacks can work against Relational-ESAs in the known-data setting. However, the attack performance differs between datasets, exploited patterns, and attacks.



## 2024/1526

* Title: Overpass Channels: Horizontally Scalable, Privacy-Enhanced, with Independent Verification, Fluid Liquidity, and Robust Censorship Proof, Payments
* Authors: Brandon "Cryptskii" Ramsay
* [Permalink](https://eprint.iacr.org/2024/1526)
* [Download](https://eprint.iacr.org/2024/1526.pdf)

### Abstract

Overpass Channels presents a groundbreaking approach to blockchain scalability, offering a horizontally scalable, privacy-enhanced payment network with independent verification, fluid liquidity, and robust censorship resistance. This paper introduces a novel architecture that leverages zero-knowledge proofs, specifically zk-SNARKs, to ensure transaction validity and privacy while enabling unprecedented throughput and efficiency.
By eliminating the need for traditional consensus mechanisms and miners, Overpass Channels achieves remarkable cost-effectiveness and energy efficiency. The system's design focuses on unilateral payment channels and off-chain transaction processing, allowing for high-speed, low-latency operations without compromising security or decentralization. This paper provides a comprehensive analysis of the Overpass Channels system, including its cryptographic foundations, scalability metrics, integration, and potential applications across various domains, from global payments to confidential voting systems and secure health record management.



## 2024/1527

* Title: How to Recover the Full Plaintext of XCB
* Authors: Peng Wang, Shuping Mao, Ruozhou Xu, Jiwu Jing, Yuewu Wang
* [Permalink](https://eprint.iacr.org/2024/1527)
* [Download](https://eprint.iacr.org/2024/1527.pdf)

### Abstract

XCB, a tweakable enciphering mode, is part of IEEE Std. 1619.2 for shared storage media. We show that all versions of XCB are not secure through three plaintext recovery attacks. A key observation is that XCB behaves like an LRW1-type tweakable block cipher for single-block messages, which lacks CCA security. The first attack targets one-block XCB, using three queries to recover the plaintext. The second one requires four queries to recover the plaintext that excludes one block. The last one requires seven queries to recover the full plaintext. The first attack applies to any scheme that follows the XCB structure, whereas the latter two attacks work on all versions of XCB, exploiting the separable property of the underlying universal hash function. We also discuss the impact of these vulnerabilities on XCB-based applications, such as disk encryption, nonce-based encryption, deterministic authenticated encryption and robust authenticated encryption, highlighting the risks due to XCB's failure to achieve STPRP security. To address these flaws, we propose the XCB* structure, an improved version of XCB that adds only two XOR operations. We prove that XCB* is STPRP-secure when using AXU hash functions, SPRPs, and a secure IV-based stream cipher.



## 2024/1528

* Title: Schnorr Signatures are Tightly Secure in the ROM under a Non-interactive Assumption
* Authors: Gavin Cho, Georg Fuchsbauer, Adam O'Neill
* [Permalink](https://eprint.iacr.org/2024/1528)
* [Download](https://eprint.iacr.org/2024/1528.pdf)

### Abstract

We show that the Schnorr signature scheme meets existential unforgeability under chosen-message attack (EUF-CMA) in the random oracle model (ROM) if the circular discrete-logarithm (CDL) assumption, a new, non-interactive variant of DL we introduce, holds in the underlying group. Our reduction is completely tight, meaning the constructed adversary against CDL has both essentially the same running time and success probability as the assumed forger. To our knowledge, we are the first to exhibit such a reduction. Previously, Bellare and Dai (INDOCRYPT 2020) showed the scheme is EUF-CMA the ROM if their multi-base DL assumption holds in the underlying group. However, multi-base DL is interactive; moreover, their reduction, while tighter than the initial result of Pointcheval and Stern (EUROCRYPT 1996), still incurs a security loss that is linear in the number of the adversary’s RO queries. We justify CDL by showing it holds in two carefully chosen idealized models, which idealize different aspects of our assumption. Our quantitative bounds in these models are essentially the same as for DL, giving strong evidence that CDL is as hard DL in appropriate elliptic-curve groups groups.