## 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


[continued in next message]

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