## 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.
To address this issue, we present an attack that abuses two novel vulnerabilities in sleep mode, which is one of the Bluetooth power-saving modes, to break Bluetooth sessions. We name the attack Breaktooth. The attack is the first to abuse the vulnerabilities as an entry point to hijack Bluetooth sessions between victims. The attack also allows overwriting the link key between the victims using the hijacked session, enabling arbitrary command injection on the victims. Furthermore, while many prior attacks assume that attackers can forcibly disconnect the Bluetooth session using methods such as jamming to launch their attacks, our attack does not require such assumptions, making it more realistic.
In this paper, we present the root causes of the Breaktooth attack and their impact. We also provide the technical details of how attackers can secretly detect the sleep mode of their victims. The attackers can easily recognize the state of the victim's Bluetooth session remotely using a standard Linux command. Additionally, we develop a low-cost toolkit to perform our attack and confirm the effectiveness of our attack. Then, we evaluate the attack on 13 types of commodity Bluetooth keyboards and mice that support the sleep mode and show that the attack poses a serious threat to Bluetooth devices supporting the sleep mode. To fix our attack, we present defenses and its proof-of-concept. We responsibly disclosed our findings to the Bluetooth SIG.
## 2024/901
* Title: Practical Committing Attacks against Rocca-S
* Authors: Ryunosuke Takeuchi, Yosuke Todo, Tetsu Iwata
* [Permalink](
https://eprint.iacr.org/2024/901)
* [Download](
https://eprint.iacr.org/2024/901.pdf)
### Abstract
This note shows practical committing attacks against Rocca-S, an authenticated encryption with associated data scheme designed for 6G applications. Previously, the best complexity of the attack was $2^{64}$ by Derbez et al. in ToSC 2024(1)/FSE 2024. We show that the committing attack against Rocca by Takeuchi et al. in ToSC 2024(2)/FSE 2025 can be applied to Rocca-S, where Rocca is an earlier version of Rocca-S. We show a concrete test vector of our attack. We also point out a committing attack that exploits equivalent keys.
## 2024/902
* Title: Access Structure Hiding Verifiable Tensor Designs
* Authors: Anandarup Roy, Bimal Kumar Roy, Kouichi Sakurai, Suprita Talnikar
* [Permalink](
https://eprint.iacr.org/2024/902)
* [Download](
https://eprint.iacr.org/2024/902.pdf)
### Abstract
The field of verifiable secret sharing schemes was introduced by Verheul et al. and has evolved over time, including well-known examples by Feldman and Pedersen. Stinson made advancements in combinatorial design-based secret sharing schemes in 2004. Desmedt et al. introduced the concept of frameproofness in 2021, while recent research by Sehrawat et al. in 2021 focuses on LWE-based access structure hiding verifiable secret sharing with malicious-majority settings. Furthermore, Roy et al. combined the concepts of reparable threshold schemes by Stinson et al. and frameproofness by Desmedt et al. in 2023, to develop extendable tensor designs built from balanced incomplete block designs, and also presented a frameproof version of their design.
This paper explores ramp-type verifiable secret sharing schemes, and the application of hidden access structures in such cryptographic protocols. Inspired by Sehrawat et al.'s access structure hiding scheme, we develop an $\epsilon$-almost access structure hiding scheme, which is verifiable as well as frameproof. We detail how the concept $\epsilon$-almost hiding is important for incorporating ramp schemes, thus making a fundamental generalisation of this concept.
## 2024/903
* Title: Nopenena Untraceable Payments: Defeating Graph Analysis with Small Decoy Sets
* Authors: Jayamine Alupotha, Mathieu Gestin, Christian Cachin
* [Permalink](
https://eprint.iacr.org/2024/903)
* [Download](
https://eprint.iacr.org/2024/903.pdf)
### Abstract
Decentralized payments have evolved from using pseudonymous identifiers to much more elaborate mechanisms to ensure privacy. They can shield the amounts in payments and achieve untraceability, e.g., decoy-based untraceable payments use decoys to obfuscate the actual asset sender or asset receiver. There are two types of decoy-based payments: full decoy set payments that use all other available users as decoys, e.g., Zerocoin, Zerocash, and ZCash, and user-defined decoy set payments where the users select small decoy sets from available users, e.g., Monero, Zether, and QuisQuis.
Existing decoy-based payments face at least two of the following problems: (1) degrading untraceability due to the possibility of payment-graph analysis in user-defined decoy payments, (2) trusted setup, (3) availability issues due to expiring transactions in full decoy sets and epochs, and (4) an ever-growing set of unspent outputs since transactions keep generating outputs without saying which ones are spent. QuisQuis is the first one to solve all these problems; however, QuisQuis requires large cryptographic proofs for validity.
We introduce Nopenena (means ``cannot see''): account-based, confidential, and user-defined decoy set payment protocol, that has short proofs and also avoids these four issues. Additionally, Nopenena can be integrated with zero-knowledge contracts like Zether's $\Sigma-$Bullets and Confidential Integer Processing (CIP) to build decentralized applications. Nopenena payments are about 80% smaller than QuisQuis payments due to Nopenena's novel cryptographic protocol. Therefore, decentralized systems benefit from Nopenena's untraceability and efficiency.
## 2024/904
* Title: On round elimination for special-sound multi-round identification and the generality of the hypercube for MPCitH
* Authors: Andreas Hülsing, David Joseph, Christian Majenz, Anand Kumar Narayanan
* [Permalink](
https://eprint.iacr.org/2024/904)
* [Download](
https://eprint.iacr.org/2024/904.pdf)
### Abstract
A popular way to build post-quantum signature schemes is by first constructing an identification scheme (IDS) and applying the Fiat-Shamir transform to it.. In this work we tackle two open questions related to the general applicability of techniques around this approach that together allow for efficient post-quantum signatures with optimal security bounds in the QROM.
First we consider a recent work by Aguilar-Melchor, Hülsing, Joseph, Majenz, Ronen, and Yue (Asiacrypt'23) that showed that an optimal bound for three-round commit & open IDS by Don, Fehr, Majenz, and Schaffner (Crypto'22) can be applied to the five-round Syndrome-Decoding in the Head (SDitH) IDS. For this, they first applied a transform that replaced the first three rounds by one. They left it as an open problem if the same approach applies to other schemes beyond SDitH. We answer this question in the affirmative, generalizing their round-elimination technique and giving a generic security proof for it. Our result applies to any IDS with $2n+1$ rounds for $n>1$. However, a scheme has to be suitable for the resulting bound to not be trivial. We find that IDS are suitable when they have a certain form of special-soundness which many commit & open IDS have.
Second, we consider the hypercube technique by Aguilar-Melchor, Gama, Howe, Hülsing, Joseph, and Yue (Eurocrypt'23). An optimization that was proposed in the context of SDitH and is now used by several of the contenders in the NIST signature on-ramp. It was conjectured that the technique applies generically for the MPC-in-the-Head (MPCitH) technique that is used in the design of many post-quantum IDS if they use an additive secret sharing scheme but this was never proven. In this work we show that the technique generalizes to MPCitH IDS that use an additively homomorphic MPC protocol, and we prove that security is preserved.
We demonstrate the application of our results to the identification scheme of RYDE, a contender in the recent NIST signature on-ramp. While RYDE was already specified with the hypercube technique applied, this gives the first QROM proof for RYDE with an optimally tight bound.
## 2024/905
* Title: On the Semidirect Discrete Logarithm Problem in Finite Groups
* Authors: Christopher Battarbee, Giacomo Borin, Ryann Cartor, Nadia Heninger, David Jao, Laura Maddison, Edoardo Persichetti, Angela Robinson, Daniel Smith-Tone, Rainer Steinwandt
* [Permalink](
https://eprint.iacr.org/2024/905)
* [Download](
https://eprint.iacr.org/2024/905.pdf)
### Abstract
We present an efficient quantum algorithm for solving the semidirect discrete logarithm problem (SDLP) in any finite group. The believed hardness of the semidirect discrete logarithm problem underlies more than a decade of works constructing candidate post-quantum cryptographic algorithms from nonabelian groups. We use a series of reduction results to show that it suffices to consider SDLP in finite simple groups. We then apply the celebrated Classification of Finite Simple Groups to consider each family. The infinite families of finite simple groups admit, in a fairly general setting, linear algebraic attacks providing a reduction to the classical discrete logarithm problem. For the sporadic simple groups, we show that their inherent properties render them unsuitable for cryptographically hard SDLP instances, which we illustrate via a Baby-Step Giant-Step style attack against SDLP in the Monster Group.
Our quantum SDLP algorithm is fully constructive for all but three remaining cases that appear to be gaps in the literature on constructive recognition of groups; for these cases SDLP is no harder than finding a linear representation. We conclude that SDLP is not a suitable post-quantum hardness assumption for any choice of finite group.
## 2024/906
* Title: Are Your Keys Protected? Time will Tell
* Authors: Yoav Ben-Dov, Liron David, Moni Naor, Elad Tzalik
* [Permalink](
https://eprint.iacr.org/2024/906)
* [Download](
https://eprint.iacr.org/2024/906.pdf)
### Abstract
Side channel attacks, and in particular timing attacks, are a fundamental obstacle to obtaining secure implementation of algorithms and cryptographic protocols, and have been widely researched for decades.
While cryptographic definitions for the security of cryptographic systems have been well established for decades, none of these accepted definitions take into account the running time information leaked from executing the system.
In this work, we give the foundation of new cryptographic definitions for cryptographic systems that take into account information about their leaked running time, focusing mainly on keyed functions such as signature and encryption schemes. Specifically,
(1) We define several cryptographic properties to express the claim that the timing information does not help an adversary to extract sensitive information, e.g. the key or the queries made. We highlight the definition of key-obliviousness, which means that an adversary cannot tell whether it received the timing of the queries with the actual key or the timing of the same queries with a random key.
(2) We present a construction of key-oblivious pseudorandom permutations on a small or medium-sized domain. This construction is not ``fixed-time,'' and at the same time is secure against any number of queries even in case the adversary knows the running time exactly. Our construction, which we call Janus Sometimes Recurse, is a variant of the ``Sometimes Recurse'' shuffle by Morris and Rogaway.
(3) We suggest a new security notion for keyed functions, called noticeable security, and prove that cryptographic schemes that have noticeable security remain secure even when the exact timings are leaked, provided the implementation is key-oblivious. We show that our notion applies to cryptographic signatures, private key encryption and PRPs.
## 2024/907
* Title: Reducing the Number of Qubits in Quantum Information Set Decoding
* Authors: Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher
* [Permalink](
https://eprint.iacr.org/2024/907)
* [Download](
https://eprint.iacr.org/2024/907.pdf)
### Abstract
This paper presents an optimization of the memory cost of the quantum Information Set Decoding (ISD) algorithm proposed by Bernstein (PQCrypto 2010), obtained by combining Prange's ISD with Grover's quantum search.
When the code has constant rate and length $n$, this algorithm essentially performs a quantum search which, at each iterate, solves a linear system of dimension $\mathcal{O}(n)$. The typical code lengths used in post-quantum public-key cryptosystems range from $10^3$ to $10^5$. Gaussian elimination, which was used in previous works, needs $\mathcal{O}(n^2)$ space to represent the matrix, resulting in millions or billions of (logical) qubits for these schemes.
In this paper, we propose instead to use the algorithm for sparse matrix inversion of Wiedemann (IEEE Trans. inf. theory 1986). The interest of Wiedemann's method is that one relies only on the implementation of a matrix-vector product, where the matrix can be represented in an implicit way. This is the case here.
We propose two main trade-offs, which we have fully implemented, tested on small instances, and benchmarked for larger instances. The first one is a quantum circuit using $\mathcal{O}(n)$ qubits, $\mathcal{O}(n^3)$ Toffoli gates like Gaussian elimination, and depth $\mathcal{O}(n^2 \log n)$. The second one is a quantum circuit using $\mathcal{O}(n \log^2 n)$ qubits, $\mathcal{O}(n^3)$ gates in total but only $\mathcal{O}( n^2 \log^2 n)$ Toffoli gates, which relies on a different representation of the search space.
As an example, for the smallest Classic McEliece parameters we estimate that the Quantum Prange's algorithm can run with 18098 qubits, while previous works would have required at least half a million qubits.
## 2024/908
* Title: Preliminary Analysis of Ascon-Xof and Ascon-Hash
* Authors: Christoph Dobraunig, Maria Eichlseder, Florian Mendel, Martin Schläffer
* [Permalink](
https://eprint.iacr.org/2024/908)
* [Download](
https://eprint.iacr.org/2024/908.pdf)
### Abstract
In this note, we present additional preliminary analysis dedicated to Ascon-Xof and Ascon-Hash [DEMS19].
## 2024/909
* Title: Approximate CRT-Based Gadget Decomposition and Application to TFHE Blind Rotation
* Authors: Olivier Bernard, Marc Joye
* [Permalink](
https://eprint.iacr.org/2024/909)
* [Download](
https://eprint.iacr.org/2024/909.pdf)
### Abstract
One of the main issues to deal with for fully homomorphic encryption is the noise growth when operating on ciphertexts. To some extent, this can be controlled thanks to a so-called gadget decomposition. A gadget decomposition typically relies on radix- or CRT-based representations to split elements as vectors of smaller chunks whose inner products with the corresponding gadget vector rebuilds (an approximation of) the original elements. Radix-based gadget decompositions present the advantage of also supporting the approximate setting: for most homomorphic operations, this has a minor impact on the noise propagation but leads to substantial savings in bandwidth, memory requirements and computational costs. A typical use-case is the blind rotation as used for example in the bootstrapping of the TFHE scheme. On the other hand, CRT-based representations are convenient when machine words are too small for directly accommodating the arithmetic on large operands. This arises in two typical cases: (i) in the hardware case with multipliers of restricted size, e.g., 17 bits; (ii) in the software case for ciphertext moduli above, e.g., 128 bits.
This paper presents new CRT-based gadget decompositions for the approximate setting, which combines the advantages of non-exact decompositions with those of CRT-based decompositions. Significantly, it enables certain hardware or software realizations otherwise hardly supported like the two aforementioned cases. In particular, we show that our new gadget decompositions provide implementations of the (programmable) bootstrapping in TFHE relying solely on native arithmetic and offering extra degrees of parallelism.
## 2024/910
* Title: A Tight Security Proof for $\mathrm{SPHINCS^{+}}$, Formally Verified
* Authors: Manuel Barbosa, François Dupressoir, Andreas Hülsing, Matthias Meijers, Pierre-Yves Strub
* [Permalink](
https://eprint.iacr.org/2024/910)
* [Download](
https://eprint.iacr.org/2024/910.pdf)
### Abstract
$\mathrm{SPHINCS^{+}}$ is a post-quantum signature scheme that, at the time of writing, is being standardized as $\mathrm{SLH\text{-}DSA}$. It is the most conservative option for post-quantum signatures, but the original tight proofs of security were flawed—as reported by Kudinov, Kiktenko and Fedorov in 2020. In this work, we formally prove a tight security bound for $\mathrm{SPHINCS^{+}}$ using the EasyCrypt proof assistant, establishing greater confidence in the general security of the scheme and that of the parameter sets considered for standardization. To this end, we reconstruct the tight security proof presented by Hülsing and Kudinov (in 2022) in a modular way. A small but important part of this effort involves a complex argument relating four different games at once, of a form not yet formalized in EasyCrypt (to the best of our knowledge). We describe our approach to overcoming this major challenge, and develop a general formal verification technique aimed at this type of reasoning.
Enhancing the set of reusable EasyCrypt artifacts previously produced in the formal verification of stateful hash-based cryptographic constructions, we (1) improve and extend the existing libraries for hash functions and (2) develop new libraries for fundamental concepts related to hash-based cryptographic constructions, including Merkle trees. These enhancements, along with the formal verification technique we develop, further ease future formal verification endeavors in EasyCrypt, especially those concerning hash-based cryptographic constructions.
## 2024/911
* Title: Generalized Indifferentiable Sponge and its Application to Polygon Miden VM
* Authors: Tomer Ashur, Amit Singh Bhati
* [Permalink](
https://eprint.iacr.org/2024/911)
* [Download](
https://eprint.iacr.org/2024/911.pdf)
### Abstract
Cryptographic hash functions are said to be the work-horses of modern cryptography. One of the strongest approaches to assess a cryptographic hash function's security is indifferentiability. Informally, indifferentiability measures to what degree the function resembles a random oracle when instantiated with an ideal underlying primitive. However, proving the indifferentiability security of hash functions has been challenging due to complex simulator designs and proof arguments. The Sponge construction is one of the prevalent hashing method used in various systems. The Sponge has been shown to be indifferentiable from a random oracle when initialized with a random permutation.
In this work, we first introduce $\mathsf{GSponge}$, a generalized form of the Sponge construction offering enhanced flexibility in input chaining, field sizes, and padding types. $\mathsf{GSponge}$ not only captures all existing sponge variants but also unveils new, efficient ones. The generic structure of $\mathsf{GSponge}$ facilitates the discovery of two micro-optimizations for already deployed sponges. Firstly, it allows a new padding rule based on zero-padding and domain-separated inputs, saving one full permutation call in certain cases without increasing the generation time of zero-knowledge proofs. Secondly, it allows to absorb up to $\mathsf{c}/2$ more elements (that can save another permutation call for certain message lengths) without compromising the indifferentiability security. These optimizations enhance hashing time for practical use cases such as Merkle-tree hashing and short message processing.
We then propose a new efficient instantiation of $\mathsf{GSponge}$ called $\mathsf{Sponge2}$ capturing these micro-optimizations and provide a formal indifferentiability proof to establish both $\mathsf{Sponge2}$ and $\mathsf{GSponge}$'s security. This proof, simpler than the original for Sponges, offers clarity and ease of understanding for real-world practitioners. Additionally, it is demonstrated that $\mathsf{GSponge}$ can be safely instantiated with permutations defined over large prime fields, a result not previously formally proven.
## 2024/912
* Title: Quantum Evolving Secret Sharing for General Access Structures
* Authors: Efrat Cohen, Anat Paskin-Cherniavsky
* [Permalink](
https://eprint.iacr.org/2024/912)
* [Download](
https://eprint.iacr.org/2024/912.pdf)
### Abstract
In the useful and well studied model of secret-sharing schemes, there are $n$ parties and a dealer, which holds a secret. The dealer applies some randomized algorithm to the secret, resulting in $n$ strings, called shares; it gives the $i$'th share to the $i$'th party. There are two requirements. (1) correctness: some predefined subsets of the parties can jointly reconstruct the secret from their shares, and (2) security: any other set gets no information on the secret. The collection of predefined qualified sets is called an access structure (AS).
This model assumes that the number of parties is known when preparing the shares and giving the shares to the parties; furthermore, the sharing algorithm and the share size are determined by the number of parties, e.g. in the best-known
secret-sharing scheme for an arbitrary $n$-party access structure the share size is $1.5^{n}$ by Appelbaum and Nir.
The assumption that the number of parties is known in advance is problematic in many scenarios. Of course, one can take some upper bound on the number of parties. On one hand, if this bound is big, then the share size will be large even if only few parties actually participate in the scheme. On the other hand, if this bound is small, then there is a risk that too many parties will arrive and no further shares can be produced; this will require an expensive re-sharing of the secret and updating all shares (which can be impossible if some parties are temporally off-line). Thus, we need to consider models with an unbounded number of parties.
To address these concrens, Komargodski, Naor, and Yogev defined \emph{evolving secret-sharing schemes} with an unbounded number of parties. In a nutshell, evolving AS's are defined as a monotone
collection of finite qualified sets, such that at any time $t$ a set $A\subseteq [t]$ is either qualified or not, depending only on $A$ itself, and not on $t$ (a `global' monotonicity notion).
Quantum secret sharing (QSS) in the standard $n$-party setting, where the secret is an arbitrary quantum state (say, qbit), rather than classical data. In face of recent advancements in quantum computing, this is a natural notion to consider, and has been studied before.
In this work, we explore the natural notion of quantum evolving secret sharing (QESS). While this notion has been studied by Samadder 20', we make several new contributions.
(1) The notion of QESS was only implicit in the above work. We formalize this notion (as well as AS's for which it is applicable), and in particular argue that the variant implied by the above work did not require `global monotonicity' of the AS, which was the standard in the evolving secret sharing literature, and appears to be useful for QESS as well.
(2) Discuss the applicability and limitations of the notion in the quantum setting that follow from the no-cloning theorem, and make its usability more limited. Yet, we argue that fundamental advantages of the evovling setting, such as keeping parties' shares independent of the total number of parties that arrive can be mantainted in the quantum setting.
(3) We characterize the AS's ammenable to construction of QSSS - so called `no cloning' evolving AS's, and point out that this class is not severly restricted relatively to the class of all evolving AS's. On the positive side, our construction combines the compiler of [Smith 00'] with ideas of hybrid secret sharing of [Goyal et. al 23'], to obtain a construction with share size comparable to the best classical linear share complexity of the scheme.
## 2024/913
* Title: SoK: Model Reverse Engineering Threats for Neural Network Hardware
* Authors: Seetal Potluri, Farinaz Koushanfar
* [Permalink](
https://eprint.iacr.org/2024/913)
* [Download](
https://eprint.iacr.org/2024/913.pdf)
### Abstract
There has been significant progress over the past seven years in model reverse engineering (RE) for neural network (NN) hardware. Although there has been systematization of knowledge (SoK) in an overall sense, however, the treatment from the hardware perspective has been far from adequate. To bridge this gap, this paper systematically categorizes the types of NN hardware used prevalently by the industry/academia, and also the model RE attacks/defenses published in each category. Further, we sub-categorize existing NN model RE attacks based on different criteria including the degree of hardware parallelism, threat vectors like side channels, fault-injection, scan-chain attacks, system-level attacks, type of asset under attack, the type of NN, exact versus approximate recovery, etc.
We make important technical observations and identify key open research directions. Subsequently, we discuss the state-of-the-art defenses against NN model RE, identify certain categorization criteria, and compare the existing works based on these criteria. We note significant qualitative gaps for defenses, and suggest recommendations for important open research directions for protection of NN models. Finally, we discuss limitations of existing work in terms of the types of models where security evaluation or defenses were proposed, and suggest open problems in terms of protecting practically expensive model IPs.
## 2024/914
* Title: Compact Key Storage: A Modern Approach to Key Backup and Delegation
* Authors: Yevgeniy Dodis, Daniel Jost, Antonio Marcedone
* [Permalink](
https://eprint.iacr.org/2024/914)
* [Download](
https://eprint.iacr.org/2024/914.pdf)
### Abstract
End-to-End (E2E) encrypted messaging, which prevents even the service provider from learning communication contents, is gaining popularity. Since users care about maintaining access to their data even if their devices are lost or broken or just replaced, these systems are often paired with cloud backup solutions: Typically, the user will encrypt their messages with a fixed key, and upload the ciphertexts to the server. Unfortunately, this naive solution has many drawbacks. First, it often undermines the fancy security guarantees of the core application, such as forward secrecy (FS) and post-compromise security (PCS), in case the single backup key is compromised. Second, they are wasteful for backing up conversations in large groups, where many users are interested in backing up the same sequence of messages.
Instead, we formalize a new primitive called Compact Key Storage (CKS) as the "right" solution to this problem. Such CKS scheme allows a mutable set of parties to delegate to a server storage of an increasing set of keys, while each client maintains only a small state. Clients update their state as they learn new keys (maintaining PCS), or whenever they want to forget keys (achieving FS), often without the need to interact with the server. Moreover, access to the keys (or some subset of them) can be efficiently delegated to new group members, who all efficiently share the same server's storage.
We carefully define syntax, correctness, privacy, and integrity of CKS schemes, and build two efficient schemes provably satisfying these notions. Our line scheme covers the most basic "all-or-nothing" flavor of CKS, where one wishes to compactly store and delegate the entire history of past secrets. Thus, new users enjoy the efficiency and compactness properties of the CKS only after being granted access to the entire history of keys. In contrast, our interval scheme is only slightly less efficient but allows for finer-grained access, delegation, and deletion of past keys.
## 2024/915
* Title: REACTIVE: Rethinking Effective Approaches Concerning Trustees in Verifiable Elections
* Authors: Josh Benaloh, Michael Naehrig, Olivier Pereira
* [Permalink](
https://eprint.iacr.org/2024/915)
* [Download](
https://eprint.iacr.org/2024/915.pdf)
### Abstract
For more than forty years, two principal questions have been asked when designing verifiable election systems: how will the integrity of the results be demonstrated and how will the privacy of votes be preserved? Many approaches have been taken towards answering the first question such as use of MixNets and homomorphic tallying. But in the academic literature, the second question has always been answered in the same way: decryption capabilities are divided amongst multiple independent “trustees” so that a collusion is required to compromise privacy.
In practice, however, this approach can be fairly challenging to deploy. Human trustees rarely have a clear understanding of their responsibilities, and they typically all use identical software for their tasks. Rather than exercising independent judgment to maintain privacy, trustees are often reduced to automata who just push the buttons they are told to when they are told to, doing little towards protecting voter privacy. This paper looks at several aspects of the trustee experience. It begins by discussing various cryptographic protocols that have been used for key generation in elections, explores their impact on the role of trustees, and notes that even the theory of proper use of trustees is more challenging than it might seem. This is illustrated by showing that one of the only references defining a full threshold distributed key generation (DKG) for elections defines an insecure protocol. Belenios claims to rely on that reference for its DKG and security proof. Fortunately, it does not inherit the same vulnerability. We offer a security proof for the Belenios DKG.
The paper then discusses various practical contexts, in terms of humans, software, and hardware, and their impact on the practical deployment of a trustee-based privacy model.