## 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!).