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



## 2024/888

* Title: zkCross: A Novel Architecture for Cross-Chain Privacy-Preserving Auditing
* Authors: Yihao Guo, Minghui Xu, Xiuzhen Cheng, Dongxiao Yu, Wangjie Qiu, Gang Qu, Weibing Wang, Mingming Song
* [Permalink](https://eprint.iacr.org/2024/888)
* [Download](https://eprint.iacr.org/2024/888.pdf)

### Abstract

One of the key areas of focus in blockchain research is how to realize privacy-preserving auditing without sacrificing the system’s security and trustworthiness. However, simultaneously achieving auditing and privacy protection, two seemingly
contradictory objectives, is challenging because an auditing system would require transparency and accountability which might create privacy and security vulnerabilities. This becomes worse in cross-chain scenarios, where the information silos from
multiple chains further complicate the problem. In this paper, we identify three important challenges in cross-chain privacy-preserving auditing, namely Cross-chain Linkability Exposure (CLE), Incompatibility of Privacy and Auditing (IPA), and Full
Auditing Inefficiency (FAI). To overcome these challenges, we propose $\mathsf{zkCross}$, which is a novel two-layer cross-chain architecture equipped with three cross-chain protocols to achieve privacy-preserving cross-chain auditing. Among these three
protocols, two are privacy-preserving cross-chain protocols for transfer and exchange, respectively; the third one is an efficient cross-chain auditing protocol. These protocols are built on solid cross-chain schemes to guarantee privacy protection and
audit efficiency. We implement $\mathsf{zkCross}$ on both local and cloud servers and perform comprehensive tests to validate that $\mathsf{zkCross}$ is well-suited for processing large-scale privacy-preserving auditing tasks. We evaluate the performance
of the proposed protocols in terms of run time, latency, throughput, gas consumption, audit time, and proof size to demonstrate their practicality.



## 2024/889

* Title: Analyzing and Benchmarking ZK-Rollups
* Authors: Stefanos Chaliasos, Itamar Reif, Adrià Torralba-Agell, Jens Ernstberger, Assimakis Kattis, Benjamin Livshits
* [Permalink](https://eprint.iacr.org/2024/889)
* [Download](https://eprint.iacr.org/2024/889.pdf)

### Abstract

As blockchain technology continues to transform the realm of digital transactions, scalability has emerged as a critical issue. This challenge has spurred the creation of innovative solutions, particularly Layer 2 scalability techniques like rollups.
Among these, ZK-Rollups are notable for employing Zero-Knowledge Proofs to facilitate prompt on-chain transaction verification, thereby improving scalability and efficiency without sacrificing security. Nevertheless, the intrinsic complexity of ZK-
Rollups has hindered an exhaustive evaluation of their efficiency, economic impact, and performance.

This paper offers a theoretical and empirical examination aimed at comprehending and evaluating ZK-Rollups, with particular attention to ZK-EVMs. We conduct a qualitative analysis to break down the costs linked to ZK-Rollups and scrutinize the design
choices of well-known implementations. Confronting the inherent difficulties in benchmarking such intricate systems, we introduce a systematic methodology for their assessment, applying our method to two prominent ZK-Rollups: Polygon zkEVM and zkSync Era.
Our research provides initial findings that illuminate trade-offs and areas for enhancement in ZK-Rollup implementations, delivering valuable insights for future research, development, and deployment of these systems.



## 2024/890

* Title: Ring Signatures for Deniable AKEM: Gandalf's Fellowship
* Authors: Phillip Gajland, Jonas Janneck, Eike Kiltz
* [Permalink](https://eprint.iacr.org/2024/890)
* [Download](https://eprint.iacr.org/2024/890.pdf)

### Abstract

Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency,
particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings.

In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards small rings. Our post-quantum scheme achieves a 50% reduction in signature sizes compared to the linear ring signature scheme Raptor (ACNS 2019). For rings of
size two, our signatures are approximately a quarter the size of DualRing (CRYPTO 2021), another linear scheme, and remain more compact for rings up to size seven. Compared to the sublinear scheme Smile (CRYPTO 2021), our signatures are more compact for
rings of up to 26. In particular, for rings of size two, our ring signatures are only 1236 bytes.

Additionally, we explore the use of ring signatures to obtain deniability in authenticated key exchange mechanisms (AKEMs), the primitive behind the recent HPKE standard used in MLS and TLS. We take a fine-grained approach at formalising sender
deniability within AKEM and seek to define the strongest possible notions. Our contributions extend to a black-box construction of a deniable AKEM from a KEM and a ring signature scheme for rings of size two. Our approach attains the highest level of
confidentiality and authenticity, while simultaneously preserving the strongest forms of deniability in two orthogonal settings. Finally, we present parameter sets for our schemes, and show that our deniable AKEM, when instantiated with our ring
signature scheme, yields ciphertexts of 2004 bytes.



## 2024/891

* Title: Glitch-Stopping Circuits: Hardware Secure Masking without Registers
* Authors: Zhenda Zhang, Svetla Nikova, Ventzislav Nikov
* [Permalink](https://eprint.iacr.org/2024/891)
* [Download](https://eprint.iacr.org/2024/891.pdf)

### Abstract

Masking is one of the most popular countermeasures to protect implementations against power and electromagnetic side channel attacks, because it offers provable security. Masking has been shown secure against d-threshold probing adversaries by Ishai et
al. at CRYPTO'03, but this adversary's model doesn't consider any physical hardware defaults and thus such masking schemes were shown to be still vulnerable when implemented as hardware circuits. To addressed these limitations glitch-extended probing
adversaries and correspondingly glitch-immune masking schemes have been introduced. This paper introduces glitch-stopping circuits which, when instantiated with registers, coincide with circuits protected via glitch-immune masking. Then we show that one
can instantiate glitch-stopping circuits without registers by using clocked logic gates or latches. This is illustrated for both ASIC and FPGA, offering a promising alternative to conventional register-based masked implementations. Compared to the
traditional register-based approach, these register-free solutions can reduce the latency to a single cycle and achieve a lower area cost. We prove and experimentally confirm that the proposed solution is as secure as the register-based one. In summary,
this paper proposes a novel method to address the latency of register-based hardware masking without jeopardising their security. This method not only reduces the latency down to one clock, but also improves the areas costs of the implementations.



## 2024/892

* Title: Flock: A Framework for Deploying On-Demand Distributed Trust
* Authors: Darya Kaviani, Sijun Tan, Pravein Govindan Kannan, Raluca Ada Popa
* [Permalink](https://eprint.iacr.org/2024/892)
* [Download](https://eprint.iacr.org/2024/892.pdf)

### Abstract

Recent years have exhibited an increase in applications that distribute trust across $n$ servers to protect user data from a central point of attack. However, these deployments remain limited due to a core obstacle: establishing $n$ distinct trust
domains. An application provider, a single trust domain, cannot directly deploy multiple trust domains. As a result, application providers forge business relationships to enlist third-parties as trust domains, which is a manual, lengthy, and expensive
process, inaccessible to many application developers.

We introduce the on-demand distributed-trust architecture that enables an application provider to deploy distributed trust automatically and immediately without controlling the other trust domains. The insight lies in reversing the deployment method such
that each user's client drives deployment instead of the application provider. While at a first glance, this approach appears infeasible due to cost, performance, and resource abuse concerns, our system Flock resolves these challenges. We implement and
evaluate Flock on 3 major cloud providers and 8 distributed-trust applications. On average, Flock achieves 1.05x the latency and 0.68-2.27x the cloud cost of a traditional distributed-trust deployment, without reliance on third-party relationships.



## 2024/893

* Title: How to Construct Quantum FHE, Generically
* Authors: Aparna Gupte, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/893)
* [Download](https://eprint.iacr.org/2024/893.pdf)

### Abstract

We construct a (compact) quantum fully homomorphic encryption (QFHE) scheme starting from any (compact) classical fully homomorphic encryption scheme with decryption in $\mathsf{NC}^{1}$, together with a dual-mode trapdoor function family. Compared to
previous constructions (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) which made non-black-box use of similar underlying primitives, our construction provides a pathway to instantiations from different assumptions. Our construction uses the techniques of
Dulek, Schaffner and Speelman (CRYPTO 2016) and shows how to make the client in their QFHE scheme classical using dual-mode trapdoor functions. As an additional contribution, we show a new instantiation of dual-mode trapdoor functions from group actions.



## 2024/894

* Title: Quantum Algorithms for Fast Correlation Attacks on LFSR-Based Stream Ciphers
* Authors: Akinori Hosoyamada
* [Permalink](https://eprint.iacr.org/2024/894)
* [Download](https://eprint.iacr.org/2024/894.pdf)

### Abstract

This paper presents quantum algorithms for fast correlation attacks, one of the most powerful techniques for cryptanalysis on LFSR-based stream ciphers in the classical setting.
Typical fast correlation attacks recover a value related to the initial state of the underlying LFSR by solving a decoding problem on a binary linear code with the Fast Walsh-Hadamard Transform (FWHT).
Applying the FWHT on a function in the classical setting is mathematically equivalent to applying the Hadamard transform on the corresponding state in quantum computation.
While the classical FWHT on a function with $\ell$-bit inputs requires $O(\ell 2^\ell)$ operations, the Hadamard transform on $\ell$-qubit states requires only a parallel application of $O(\ell)$ basic gates.
This difference leads to the exponential speed-up by some quantum algorithms, including Simon's period finding algorithm.

Given these facts, the question naturally arises of whether a quantum speedup can also be achieved for fast correlations by replacing the classical FWHT with the quantum Hadamard transform.
We show quantum algorithms achieving speed-up in such a way, introducing a new attack model in the Q2 setting.
The new model endows adversaries with a quite strong power, but we demonstrate its feasibility by showing that certain members of the ChaCha and Salsa20 families will likely be secure in the new model.
Our attack exploits the link between LFSRs' state update and multiplication in a fine field to apply Shor's algorithm for the discrete logarithm problem.
We apply our attacks on SNOW 2.0, SNOW 3G, and Sosemanuk, observing a large speed-up from classical attacks.



## 2024/895

* Title: Fully-Succinct Multi-Key Homomorphic Signatures from Standard Assumptions
* Authors: Gaspard Anthoine, David Balbás, Dario Fiore
* [Permalink](https://eprint.iacr.org/2024/895)
* [Download](https://eprint.iacr.org/2024/895.pdf)

### Abstract

Multi-Key Homomorphic Signatures (MKHS) allow one to evaluate a function on data signed by distinct users while producing a succinct and publicly-verifiable certificate of the correctness of the result. All the constructions of MKHS in the state of the
art achieve a weak level of succinctness where signatures are succinct in the total number of inputs but grow linearly with the number of users involved in the computation. The only exception is a SNARK-based construction which relies on a strong notion
of knowledge soundness in the presence of signing oracles that not only requires non-falsifiable assumptions but also encounters some impossibility results.

In this work, we present the first construction of MKHS that are fully succinct (also with respect to the number of users) while achieving adaptive security under standard falsifiable assumptions. Our result is achieved through a novel combination of
batch arguments for NP (BARGs) and functional commitments (FCs), and yields diverse MKHS instantiations for circuits of unbounded depth based on either pairing or lattice assumptions. Additionally, our schemes support efficient verification with pre-
processing, and they can easily be extended to achieve multi-hop evaluation and context-hiding.



## 2024/896

* Title: Dynamic-FROST: Schnorr Threshold Signatures with a Flexible Committee * Authors: Annalisa Cimatti, Francesco De Sclavis, Giuseppe Galano, Sara Giammusso, Michela Iezzi, Antonio Muci, Matteo Nardelli, Marco Pedicini
* [Permalink](https://eprint.iacr.org/2024/896)
* [Download](https://eprint.iacr.org/2024/896.pdf)

### Abstract

Threshold signatures enable any subgroup of predefined cardinality $t$ out of a committee of $n$ participants to generate a valid, aggregated signature.
Although several $(t,n)$-threshold signature schemes exist, most of them assume that the threshold $t$ and the set of participants do not change over time.
Practical applications of threshold signatures might benefit from the possibility of updating the threshold or the committee of participants. Examples of such applications are consensus algorithms and blockchain wallets.
In this paper, we present Dynamic-FROST (D-FROST, for short) that combines FROST, a Schnorr threshold signature scheme, with CHURP, a dynamic proactive secret sharing scheme. The resulting protocol is the first Schnorr threshold signature scheme that
accommodates changes in both the committee and the threshold value without relying on a trusted third party.
Besides detailing the protocol, we present a proof of its security: as the original signing scheme, D-FROST preserves the property of Existential Unforgeability under Chosen-Message Attack.



## 2024/897

* Title: Laconic Function Evaluation and ABE for RAMs from (Ring-)LWE
* Authors: Fangqi Dong, Zihan Hao, Ethan Mook, Hoeteck Wee, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2024/897)
* [Download](https://eprint.iacr.org/2024/897.pdf)

### Abstract

Laconic function evaluation (LFE) allows us to compress a circuit $f$ into a short digest. Anybody can use this digest as a public-key to efficiently encrypt some input $x$. Decrypting the resulting ciphertext reveals the output $f(x)$, while hiding
everything else about $x$. In this work we consider LFE for Random-Access Machines (RAM-LFE) where, instead of a circuit $f$, we have a RAM program $f_{\mathsf{DB}}$ that potentially contains some large hard-coded data $\mathsf{DB}$. The decryption run-
time to recover $f_{\mathsf{DB}}(x)$ from the ciphertext should be roughly the same as a plain evaluation of $f_{\mathsf{DB}}(x)$ in the RAM model, which can be sublinear in the size of $\mathsf{DB}$. Prior works constructed LFE for circuits under LWE,
and RAM-LFE under indisitinguishability obfuscation (iO) and Ring-LWE. In this work, we construct RAM-LFE with essentially optimal encryption and decryption run-times from just Ring-LWE and a standard circular security assumption, without iO.

RAM-LFE directly yields 1-key succinct functional encryption and reusable garbling for RAMs with similar parameters.

If we only want an attribute-based LFE for RAMs (RAM-AB-LFE), then we can replace Ring-LWE with plain LWE in the above. Orthogonally, if we only want leveled schemes, where the encryption/decryption efficiency can scale with the depth of the RAM
computation, then we can remove the need for a circular-security. Lastly, we also get a leveled many-key attribute-based encryption for RAMs (RAM-ABE), from LWE.



## 2024/898

* Title: Edit Distance Robust Watermarks for Language Models
* Authors: Noah Golowich, Ankur Moitra
* [Permalink](https://eprint.iacr.org/2024/898)
* [Download](https://eprint.iacr.org/2024/898.pdf)

### Abstract

Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ,
Gunn & Zamir (2024) which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's actual output distribution; and (b) robustness to channels which introduce a constant fraction of adversarial
insertions, substitutions, and deletions to the watermarked text. Earlier schemes could only handle stochastic substitutions and deletions, and thus we are aiming for a more natural and appealing robustness guarantee that holds with respect to edit
distance.

Our main result is a watermarking scheme which achieves both undetectability and robustness to edits when the alphabet size for the language model is allowed to grow as a polynomial in the security parameter. To derive such a scheme, we follow an
approach introduced by Christ & Gunn (2024), which proceeds via first constructing pseudorandom codes satisfying undetectability and robustness properties analogous to those above; our key idea is to handle adversarial insertions and deletions by
interpreting the symbols as indices into the codeword, which we call indexing pseudorandom codes. Additionally, our codes rely on weaker computational assumptions than used in previous work. Then we show that there is a generic transformation from such
codes over large alphabets to watermarking schemes for arbitrary language models.



## 2024/899

* Title: Monotone-Policy Aggregate Signatures
* Authors: Maya Farber Brodsky, Arka Rai Choudhuri, Abhishek Jain, Omer Paneth * [Permalink](https://eprint.iacr.org/2024/899)
* [Download](https://eprint.iacr.org/2024/899.pdf)

### Abstract

The notion of aggregate signatures allows for combining signatures from different parties into a short certificate that attests that *all* parties signed a message. In this work, we lift this notion to capture different, more expressive signing policies.
For example, we can certify that a message was signed by a (weighted) threshold of signers.

We present the first constructions of aggregate signatures for monotone policies based on standard polynomial-time cryptographic assumptions. The aggregate signatures in our schemes are succinct, i.e., their size is *independent* of the number of signers.
Moreover, verification is also succinct if all parties sign the same message (or if the messages have a succinct representation). All prior work requires either interaction between the parties or non-standard assumptions (that imply SNARKs for NP).

Our signature schemes are based on non-interactive batch arguments (BARGs) for monotone policies [Brakerski-Brodsky-Kalai-Lombardi-Paneth, Crypto'23]. In contrast to previous constructions, our BARGs satisfy a new notion of *adaptive* security which is
instrumental to our application. Our new BARGs for monotone policies can be constructed from standard BARGs and other standard assumptions.



## 2024/900

* Title: Breaktooth: Breaking Bluetooth Sessions Abusing Power-Saving Mode
* Authors: Keiichiro Kimura, Hiroki Kuzuno, Yoshiaki Shiraishi, Masakatu Morii * [Permalink](https://eprint.iacr.org/2024/900)
* [Download](https://eprint.iacr.org/2024/900.pdf)

### Abstract

With the increasing demand for Bluetooth devices, various Bluetooth devices support a power-saving mode to reduce power consumption. One of the features of the power-saving mode is that the Bluetooth sessions among devices are temporarily disconnected or
close to being disconnected. Prior works have analyzed that the power-saving mode is vulnerable to denial of sleep (DoSL) attacks that interfere with the transition to the power-saving mode of Bluetooth devices, thereby increasing its power consumption.
However, to the best of our knowledge, no prior work has analyzed vulnerabilities or attacks on the state after transitioning to the power-saving mode.


[continued in next message]

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