## In this issue

1. [2024/353] FuLeakage: Breaking FuLeeca by Learning Attacks
2. [2024/374] Universal Composable Password Authenticated Key ...
3. [2024/379] SyRA: Sybil-Resilient Anonymous Signatures with ...
4. [2024/770] Sublinear-Round Broadcast without Trusted Setup
5. [2024/887] Secret Key Recovery in a Global-Scale End-to-End ...
6. [2024/888] zkCross: A Novel Architecture for Cross-Chain ...
7. [2024/889] Analyzing and Benchmarking ZK-Rollups
8. [2024/890] Ring Signatures for Deniable AKEM: Gandalf's Fellowship
9. [2024/891] Glitch-Stopping Circuits: Hardware Secure Masking ...
10. [2024/892] Flock: A Framework for Deploying On-Demand ...
11. [2024/893] How to Construct Quantum FHE, Generically
12. [2024/894] Quantum Algorithms for Fast Correlation Attacks on ...
13. [2024/895] Fully-Succinct Multi-Key Homomorphic Signatures ...
14. [2024/896] Dynamic-FROST: Schnorr Threshold Signatures with a ...
15. [2024/897] Laconic Function Evaluation and ABE for RAMs from ...
16. [2024/898] Edit Distance Robust Watermarks for Language Models
17. [2024/899] Monotone-Policy Aggregate Signatures
18. [2024/900] Breaktooth: Breaking Bluetooth Sessions Abusing ...
19. [2024/901] Practical Committing Attacks against Rocca-S
20. [2024/902] Access Structure Hiding Verifiable Tensor Designs
21. [2024/903] Nopenena Untraceable Payments: Defeating Graph ...
22. [2024/904] On round elimination for special-sound multi-round ...
23. [2024/905] On the Semidirect Discrete Logarithm Problem in ...
24. [2024/906] Are Your Keys Protected? Time will Tell
25. [2024/907] Reducing the Number of Qubits in Quantum ...
26. [2024/908] Preliminary Analysis of Ascon-Xof and Ascon-Hash
27. [2024/909] Approximate CRT-Based Gadget Decomposition and ...
28. [2024/910] A Tight Security Proof for $\mathrm{SPHINCS^{+}}$, ...
29. [2024/911] Generalized Indifferentiable Sponge and its ...
30. [2024/912] Quantum Evolving Secret Sharing for General Access ...
31. [2024/913] SoK: Model Reverse Engineering Threats for Neural ...
32. [2024/914] Compact Key Storage: A Modern Approach to Key ...
33. [2024/915] REACTIVE: Rethinking Effective Approaches ...

## 2024/353

* Title: FuLeakage: Breaking FuLeeca by Learning Attacks
* Authors: Felicitas Hörmann, Wessel van Woerden
* [Permalink](https://eprint.iacr.org/2024/353)
* [Download](https://eprint.iacr.org/2024/353.pdf)

### Abstract

FuLeeca is a signature scheme submitted to the recent NIST call for additional signatures. It is an efficient hash-and-sign scheme based on quasi-cyclic codes in the Lee metric and resembles the lattice-based signature Falcon. FuLeeca proposes a so-called concentration step within the signing procedure to avoid leakage of secret-key information from the signatures. However, FuLeeca is still vulnerable to learning attacks, which were first observed for lattice-based schemes. We present three full key-recovery attacks by exploiting the proximity of the code-based FuLeeca scheme to lattice-based primitives.
More precisely, we use a few signatures to extract an $n/2$-dimensional circulant sublattice from the given length-$n$ code, that still contains the exceptionally short secret-key vector. This significantly reduces the classical attack cost and, in addition, leads to a full key recovery in quantum-polynomial time. Furthermore, we exploit a bias in the concentration procedure to classically recover the full key for any security level with at most 175,000 signatures in less than an hour.

## 2024/374

* Title: Universal Composable Password Authenticated Key Exchange for the Post-Quantum World
* Authors: You Lyu, Shengli Liu, Shuai Han
* [Permalink](https://eprint.iacr.org/2024/374)
* [Download](https://eprint.iacr.org/2024/374.pdf)

### Abstract

In this paper, we construct the first password authenticated key exchange (PAKE) scheme from isogenies with Universal Composable (UC) security in the random oracle model (ROM). We also construct the first two PAKE schemes with UC security in the quantum random oracle model (QROM), one is based on the learning with error (LWE) assumption, and the other is based on the group-action decisional Diffie- Hellman (GA-DDH) assumption in the isogeny setting.
To obtain our UC-secure PAKE scheme in ROM, we propose a generic construction of PAKE from basic lossy public key encryption (LPKE) and CCA-secure PKE. We also introduce a new variant of LPKE, named extractable LPKE (eLPKE). By replacing the basic LPKE with eLPKE, our generic construction of PAKE achieves UC security in QROM. The LPKE and eLPKE have instantiations not only from LWE but also from GA-DDH, which admit four specific PAKE schemes with UC security in ROM or QROM, based on LWE or GA-DDH.

## 2024/379

* Title: SyRA: Sybil-Resilient Anonymous Signatures with Applications to Decentralized Identity
* Authors: Elizabeth Crites, Aggelos Kiayias, Markulf Kohlweiss, Amirreza Sarencheh
* [Permalink](https://eprint.iacr.org/2024/379)
* [Download](https://eprint.iacr.org/2024/379.pdf)

### Abstract

We introduce a new cryptographic primitive, called Sybil-Resilient Anonymous (SyRA) signatures, which enable users to generate, on demand, unlinkable pseudonyms tied to any given context, and issue signatures on behalf of these pseudonyms. Concretely, given a personhood relation, an issuer (who may be a distributed entity) enables users to prove their personhood and extract an associated long-term key, which can then be used to issue signatures for any given context and message. Sybil-resilient anonymous signatures achieve two key security properties: 1) Sybil resilience, which ensures that every user is entitled to at most one pseudonym per context, and 2) anonymity, which requires that no information about the user is leaked through their various pseudonyms or the signatures they issue on their pseudonyms’ behalf.
We conceptualize SyRA signatures as an ideal functionality in the Universal Composition (UC) setting and realize the functionality via an efficient, pairing-based construction that utilizes two levels of verifiable random functions (VRFs), which may be of independent interest. One of the key features of this approach is the statelessness of the issuer: we achieve the core properties of Sybil resilience and anonymity without requiring the issuer to retain any information about past user interactions. SyRA signatures have various applications in multiparty systems, such as e-voting (e.g., for decentralized governance), privacy-preserving regulatory compliance (e.g., AML/CFT checks), and cryptocurrency airdrops, making them an attractive option for deployment in decentralized identity (DID) systems. Furthermore, we demonstrate the practicality of SyRA signatures for use in such systems by providing a performance evaluation of our construction.

## 2024/770

* Title: Sublinear-Round Broadcast without Trusted Setup
* Authors: Andreea B. Alexandru, Julian Loss, Charalampos Papamanthou, Giorgos Tsimos, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2024/770)
* [Download](https://eprint.iacr.org/2024/770.pdf)

### Abstract

Byzantine broadcast is one of the fundamental problems in distributed computing. Many of its practical applications, from multiparty computation to consensus mechanisms for blockchains, require increasingly weaker trust assumptions, as well as scalability for an ever-growing number of users $n$. This rules out existing solutions which run in a linear number of rounds in $n$ or rely on trusted setup requirements. In this paper, we propose the first sublinear-round and trustless Byzantine broadcast protocol for the dishonest majority setting. Unlike previous sublinear-round protocols, our protocol assumes neither the existence of a trusted dealer who honestly issues keys and correlated random strings to the parties nor random oracles. Instead, we present a solution whose setup is limited to an unstructured uniform reference string and a plain public key infrastructure (a.k.a. bulletin-board PKI).
Our broadcast protocol builds on top of a moderated gradecast protocol which parties can use to reach weak agreement on shared random strings. Using these strings, we can then run in an unbiased fashion a committee-based Byzantine protocol, similar to that of Chan et al. (PKC 2020), which terminates in a sublinear number of rounds. To this end, we propose a novel construction for committee election, which does not rely either on random oracles or on a trusted setup, and uses NIZKs and time-lock puzzles. Our protocol is resilient against an adaptive adversary who corrupts any constant fraction of parties.

## 2024/887

* Title: Secret Key Recovery in a Global-Scale End-to-End Encryption System
* Authors: Graeme Connell, Vivian Fang, Rolfe Schmidt, Emma Dauterman, Raluca Ada Popa
* [Permalink](https://eprint.iacr.org/2024/887)
* [Download](https://eprint.iacr.org/2024/887.pdf)

### Abstract

End-to-end encrypted messaging applications ensure that an attacker cannot read a user's message history without their decryption keys. While end-to-end encryption provides strong privacy, it creates a usability problem: if a user loses their devices and cannot access their decryption keys, they can no longer access their message history. To solve this usability problem, users should be able to back up their decryption keys with the messaging provider. For privacy, the provider should not have access to users' decryption keys. To solve this problem, we present Secure Value Recovery 3 (SVR3), a secret key recovery system that distributes trust across different types of hardware enclaves run by different cloud providers in order to protect users' decryption keys.. SVR3 is the first deployed secret key recovery system to split trust across heterogeneous enclaves managed by different cloud providers: this design ensures that a single type of enclave does not become a central point of attack. SVR3 protects decryption keys via rollback protection and fault tolerance techniques tailored to the enclaves' security guarantees. SVR3 costs $0.0025/user/year and takes 365ms for a user to recover their key, which is a rare operation. A part of SVR3 has been rolled out to millions of real users in a deployment with capacity for over 500 million users, demonstrating the ability to operate at scale.