## In this issue

1. [2024/1574] Scalable Two-Round $n$-out-of-$n$ and Multi- ...
2. [2024/2087] Post-Quantum Privacy for Traceable Receipt-Free ...
3. [2024/2088] An Embedded Domain-Specific Language for Using One- ...
4. [2024/2089] Computing the Hermite Normal Form: A Survey
5. [2024/2090] Breaking the Shadow: Key Recovery Attack on Full- ...
6. [2024/2091] Encrypted Multi-map that Hides Query, Access, and ...
7. [2024/2092] PQConnect: Automated Post-Quantum End-to-End Tunnels
8. [2024/2093] Exploring Large Integer Multiplication for ...
9. [2024/2094] Secure Vault scheme in the Cloud Operating Model
10. [2024/2095] A Note on the Minimality of One-Way Functions in ...
11. [2024/2096] Efficient Multi-party Private Set Union Resistant ...
12. [2024/2097] NMFT: A Copyrighted Data Trading Protocol based on ...
13. [2024/2098] Asymptotically Optimal Adaptive Asynchronous Common ...
14. [2024/2099] MicroNova: Folding-based arguments with efficient ...
15. [2024/2100] Compact Key Storage in the Standard Model
16. [2025/1] Attribute Based Encryption for Turing Machines from ...
17. [2025/2] Voting with coercion resistance and everlasting ...
18. [2025/3] Post-Quantum DNSSEC with Faster TCP Fallbacks
19. [2025/4] Smaug: Modular Augmentation of LLVM for MPC
20. [2025/5] What is "legal" and "illegal?": Social Norms, ...
21. [2025/6] Nearly Quadratic Asynchronous Distributed Key ...
22. [2025/7] Non Linearizable Entropic Operator
23. [2025/8] A Survey to Zero-Knowledge Interactive Verifiable ...
24. [2025/9] Efficient CPA Attack on Hardware Implementation of ...
25. [2025/10] A Combinatorial Approach to IoT Data Security
26. [2025/11] DL-SCADS: Deep Learning-Based Post-Silicon Side- ...
27. [2025/12] Leuvenshtein: Efficient FHE-based Edit Distance ...
28. [2025/13] Wave Hello to Privacy: Efficient Mixed-Mode MPC ...
29. [2025/14] SPY-PMU: Side-Channel Profiling of Your Performance ...
30. [2025/15] A New Method for Solving Discrete Logarithm Based ...
31. [2025/16] Dynamically Available Common Subset
32. [2025/17] New Quantum Cryptanalysis of Binary Elliptic Curves ...
33. [2025/18] On the Independence Assumption in Quasi-Cyclic ...

## 2024/1574

* Title: Scalable Two-Round $n$-out-of-$n$ and Multi-Signatures from Lattices in the Quantum Random Oracle Model
* Authors: Qiqi Lai, Feng-Hao Liu, Yang Lu, Haiyang Xue, Yong Yu
* [Permalink](https://eprint.iacr.org/2024/1574)
* [Download](https://eprint.iacr.org/2024/1574.pdf)

### Abstract

In this paper, we construct the first asymptotically efficient two-round $n$-out-of-$n$ and multi-signature schemes from lattices in the quantum random oracle model (QROM), using the Fiat-Shamir with Aborts (FSwA) paradigm. Our protocols can be viewed as the QROM~variants of the two-round protocols by Damgård et al. (JoC 2022). A notable feature of our protocol, compared to other counterparts in the classical random oracle model, is that each party performs an independent abort and still outputs a signature in exactly two rounds, making our schemes significantly more scalable.

From a technical perspective, the simulation of QROM~and the efficient reduction from breaking underlying assumption to forging signatures are the essential challenges to achieving efficient QROM security for the previously related works.
In order to conquer the former one we adopt the quantum-accessible pseudorandom function (QPRF) to simulate QROM. Particularly, we show
that there exist a QPRF~which can be programmed and inverted, even against a quantum adversary.
For the latter challenge, we tweak and apply the online extractability by Unruh (Eurocrypt 2015).

## 2024/2087

* Title: Post-Quantum Privacy for Traceable Receipt-Free Encryption
* Authors: Paola de Perthuis, Thomas Peters
* [Permalink](https://eprint.iacr.org/2024/2087)
* [Download](https://eprint.iacr.org/2024/2087.pdf)

### Abstract

Traceable Receipt-free Encryption (TREnc) has recently been introduced as a verifiable public-key encryption primitive endowed with a unique security model. In a nutshell, TREnc allows randomizing ciphertexts in transit in order to remove any subliminal information up to a public trace that ensures the non-malleability of the underlying plaintext. A remarkable property of TREnc is the indistinguishability of the randomization of chosen ciphertexts against traceable chosen-ciphertext attacks (TCCA). The main application lies in voting systems by allowing voters to encrypt their votes, tracing whether a published ballot takes their choices into account, and preventing them from proving how they
voted. While being a very promising primitive, the few existing TREnc mechanisms solely rely on discrete-logarithm related assumptions making them vulnerable to the well-known record-now/decrypt-later attack in the wait of quantum computers.
We address this limitation by building the first TREnc whose privacy withstands the advent of quantum adversaries in the future. To design our construction, we first generalize the original TREnc primitive that is too restrictive to be easily compatible with built-in lattice-based semantically-secure encryption. Our more flexible model keeps all the ingredients generically implying receipt-free voting. Our instantiation relies on Ring Learning With Errors (RLWE) with pairing-based statistical zero-knowledge simulation sound proofs from Groth-Sahai, and further enjoys a public-coin common reference string removing the need of a trusted setup.

## 2024/2088

* Title: An Embedded Domain-Specific Language for Using One-Hot Vectors and Binary Matrices in Secure Computation Protocols
* Authors: Andrei Lapets
* [Permalink](https://eprint.iacr.org/2024/2088)
* [Download](https://eprint.iacr.org/2024/2088.pdf)

### Abstract

The use of secure computation protocols within production software systems and applications is complicated by the fact that such protocols sometimes rely upon -- or are most compatible with -- unusual or restricted models of computation. We employ the features of a contemporary and widely used programming language to create an embedded domain-specific language for working with user-defined functions as binary matrices that operate on one-hot vectors. At least when working with small finite domains, this allows programmers to overcome the restrictions of more simple secure computation protocols that support only linear operations (such as addition and scalar multiplication) on private inputs. Notably, programmers are able to define their own input and output domains, to use all available host language features and libraries to define functions that operate on these domains, and to translate inputs, outputs, and functions between their usual host language representations and their one-hot vector or binary matrix forms. Furthermore, these features compose in a straightforward way with simple secure computation libraries available for the host language.

## 2024/2089

* Title: Computing the Hermite Normal Form: A Survey
* Authors: Leon Damer
* [Permalink](https://eprint.iacr.org/2024/2089)
* [Download](https://eprint.iacr.org/2024/2089.pdf)

### Abstract

The Hermite Normal Form (HNF) of a matrix is an analogue of the echolon form over the integers. Any integer matrix can be transformed into its unique HNF.
A common obstacle in computing the HNF is the extensive blow up of intermediate values. As first approach to this problem, we discuss the $Modulo Determinant Algorithm$. It keeps the entries bounded by $d$, the determinant of the lattice, and has a time complexity of $\mathcal{O}(n^3\log^2 d)$, where $n$ is the dimension of the matrix. Although this algorithm is very useful if the determinant is small, in the general case, the entries still become extremely large.
Secondly, we study the $Linear Space Algorithm$. It has a time complexity of $\mathcal{O}(n^5\mathrm{polylog}(M, n))$, where $M$ denotes the largest absolute value of the input matrix. This is as fast as the best previously known algorithms, but in contrast, it assures space complexity linear in the input size, i.e. $\mathcal{O}(n^2\log M)$.
As last algorithm to compute the HNF we analyze the $Heuristic Algorithm$, which is based on the first two algorithms. It achieves a much faster runtime in practice, yielding a heuristic runtime of $\mathcal{O}(n^4\mathrm{polylog}(M, n))$, while keeping the linear space complexity.
Besides some performance speed ups, the $Linear Space Algorithm$ and $Heuristic Algorithm$ are precisely the algorithms implemented by SageMath.

## 2024/2090

* Title: Breaking the Shadow: Key Recovery Attack on Full-Round Shadow Block Ciphers with Minimal Data
* Authors: Anda Che, Shahram Rasoolzadeh
* [Permalink](https://eprint.iacr.org/2024/2090)
* [Download](https://eprint.iacr.org/2024/2090.pdf)

### Abstract

Shadow is a family of lightweight block ciphers introduced by Guo, Li, and Liu in 2021, with Shadow-32 having a 32-bit block size and a 64-bit key, and Shadow-64 having a 64-bit block size and a 128-bit key. Both variants use a generalized Feistel network with four branches, incorporating the AND-Rotation-XOR operation similar to the Simon family for their bridging function. This paper reveals that the security claims of the Shadow family are not as strong as suggested. We present a key recovery attack that can retrieve the sequence of round keys used for encryption with only two known plaintext/ciphertext pairs, requiring time and memory complexity of $2^{43.23}$ encryptions and $2^{21.62}$ blocks of memory for Shadow-32, and complexity of $2^{81.32}$ encryptions and $2^{40.66}$ blocks of memory for Shadow-64. Notably, this attack is independent of the number of rounds and the bridging function employed. Furthermore, we critically evaluate one of the recent cryptanalysis on Shadow ciphers and identify significant flaws in the proposed key recovery attacks. In particular, we demonstrate that the distinguisher used in impossible differential attacks by Liu et al. is ineffective for key recovery, despite their higher claimed complexities compared to ours.

## 2024/2091

* Title: Encrypted Multi-map that Hides Query, Access, and Volume Patterns
* Authors: Alexandra Boldyreva, Tianxin Tang
* [Permalink](https://eprint.iacr.org/2024/2091)
* [Download](https://eprint.iacr.org/2024/2091.pdf)

### Abstract

We present an encrypted multi-map, a fundamental data structure underlying
searchable encryption/structured encryption. Our protocol supports updates and
is designed for applications demanding very strong data security. Not only it
hides the information about queries and data, but also the query, access, and
volume patterns. Our protocol utilizes a position-based ORAM and an encrypted
dictionary. We provide two instantiations of the protocol, along with their
operation-type-revealing variants, all using PathORAM but with different
encrypted dictionary instantiations (AVL tree or BSkiplist). Their efficiency
has been evaluated through both asymptotic and concrete complexity analysis,
outperforming prior work while achieving the same level of strong security. We
have implemented our instantiations and evaluated their performance on two
real-world email databases (Enron and Lucene). We also discuss the strengths and
limitations of our construction, including its resizability, and highlight that
optimized solutions, even with heavy network utilization, may become practical
as network speed improves.

## 2024/2092

* Title: PQConnect: Automated Post-Quantum End-to-End Tunnels
* Authors: Daniel J. Bernstein, Tanja Lange, Jonathan Levin, Bo-Yin Yang
* [Permalink](https://eprint.iacr.org/2024/2092)
* [Download](https://eprint.iacr.org/2024/2092.pdf)

### Abstract

This paper introduces PQConnect, a post-quantum end-to-end tunneling protocol that automatically protects all packets between clients that have installed PQConnect and servers that have installed and configured PQConnect.

Like VPNs, PQConnect does not require any changes to higher-level protocols and application software. PQConnect adds cryptographic protection to unencrypted applications, works in concert with existing pre-quantum applications to add post-quantum protection, and adds a second application-independent layer of defense to any applications that have begun to incorporate application-specific post-quantum protection.

Unlike VPNs, PQConnect automatically creates end-to-end tunnels to any number of servers using automatic peer discovery, with no need for the client administrator to configure per-server information. Each server carries out a client-independent configuration step to publish an announcement that the server's name accepts PQConnect connections. Any PQConnect client connecting to that name efficiently finds this announcement, automatically establishes a post-quantum point-to-point IP tunnel to the server, and routes traffic for that name through that tunnel.

The foundation of security in PQConnect is the server's long-term public key used to encrypt and authenticate all PQConnect packets. PQConnect makes a conservative choice of post-quantum KEM for this public key. PQConnect also uses a smaller post-quantum KEM for forward secrecy, and elliptic curves to ensure pre-quantum security even in case of security failures in KEM design or KEM software. Security of the handshake component of PQConnect has been symbolically proven using
Tamarin.

## 2024/2093

* Title: Exploring Large Integer Multiplication for Cryptography Targeting In-Memory Computing
* Authors: Florian Krieger, Florian Hirner, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2024/2093)
* [Download](https://eprint.iacr.org/2024/2093.pdf)

### Abstract

Emerging cryptographic systems such as Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKP) are computation- and data-intensive. FHE and ZKP implementations in software and hardware largely rely on the von Neumann architecture, where a significant amount of energy is lost on data movements. A promising computing paradigm is computing in memory (CIM), which enables computations to occur directly within memory, thereby reducing data movements and energy consumption. However, efficiently performing large integer multiplications - critical in FHE and ZKP - is an open question, as existing CIM methods are limited to small operand sizes. In this work, we address this question by exploring advanced algorithmic approaches for large integer multiplication,
identifying the Karatsuba algorithm as the most effective for
CIM applications. Thereafter, we design the first Karatsuba multiplier for resistive CIM crossbars. Our multiplier uses a three-stage pipeline to enhance throughput and, additionally, balances memory endurance with efficient array sizes. Compared to existing CIM multiplication methods, when scaled up to the bit widths required in ZKP and FHE, our design achieves up to 916x in throughput and 281x in area-time product improvements.

## 2024/2094

* Title: Secure Vault scheme in the Cloud Operating Model
* Authors: Rishiraj Bhattacharyya, Avradip Mandal, Meghna Sengupta
* [Permalink](https://eprint.iacr.org/2024/2094)
* [Download](https://eprint.iacr.org/2024/2094.pdf)

### Abstract

The rising demand for data privacy in cloud-based environments has led to the development of advanced mechanisms for securely managing sensitive information. A prominent solution in this domain is the "Data Privacy Vault," a concept that is being provided commercially by companies such as Hashicorp, Basis Theory, Skyflow Inc., VGS, Evervault, Protegrity, Anonomatic, and BoxyHQ. However, no existing work has rigorously defined the security notions required for a Data Privacy Vault or proven them within a formal framework which is the focus of this paper.

Among its other uses, data privacy vaults are increasingly being used as storage for LLM training data which necessitates a scheme that enables users to securely store sensitive information in the cloud while allowing controlled access for performing analytics on specific non-sensitive attributes without exposing sensitive data. Conventional solutions involve users generating encryption keys to safeguard their data, but these solutions are not deterministic and are therefore unsuited for the LLM setting. To address this, we propose a novel framework that is deterministic as well as semantically secure. Our scheme operates in the Cloud Operating model where the server is trusted but stateless, and the storage is outsourced.

We provide a formal definition and a concrete instantiation of this data privacy vault scheme. We introduce a novel tokenization algorithm that serves as the core mechanism for protecting sensitive data within the vault. Our approach not only generates secure, unpredictable tokens for sensitive data but also securely stores sensitive data while enabling controlled data retrieval based on predefined access levels. Our work fills a significant gap in the existing literature by providing a formalized framework for the data privacy vault, complete with security proofs and a practical construction - not only enhancing the understanding of vault schemes but also offering a viable solution for secure data management in the era of cloud computing.

## 2024/2095

* Title: A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography
* Authors: Sam Buxbaum, Mohammad Mahmoody
* [Permalink](https://eprint.iacr.org/2024/2095)
* [Download](https://eprint.iacr.org/2024/2095.pdf)

### Abstract

In classical cryptography, one-way functions (OWFs) play a central role as the minimal primitive that (almost) all primitives imply. The situation is more complicated in quantum cryptography, in which honest parties and adversaries can use quantum computation and communication, and it is known that analogues of OWFs in the quantum setting might not be minimal.

In this work we ask whether OWFs are minimal for the intermediate setting of post-quantum cryptography, in which the protocols are classical while they shall resist quantum adversaries. We show that for a wide range of natural settings, if a primitive Q implies OWFs, then so does its (uniformly or non-uniformly secure) post-quantum analogue. In particular, we show that if a primitive Q implies any other primitive P that has a 2-message security game (e.g., OWFs) through a black-box classical security reduction R, then one can always (efficiently) turn any polynomial-size quantum adversary breaking P into a polynomial-size quantum adversary breaking Q. Note that this result holds even if the implementation of P using that of Q is arbitrarily non-black-box.

We also prove extensions of this result for when the reduction R anticipates its oracle adversary to be deterministic, whenever either of the following conditions hold: (1) the adversary needs to win the security game of Q only with non-negligible probability (e.g., Q is collision-resistant hashing) or (2) that either of P and Q have "falsifiable" security games (this is the case when P is OWFs). Our work leaves open answering our main question when Q implies OWFs through a non-black-box security reduction, or when P uses a more complicated security game than a two-message one.

## 2024/2096

* Title: Efficient Multi-party Private Set Union Resistant to Maximum Collusion Attacks
* Authors: Qiang Liu, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2024/2096)
* [Download](https://eprint.iacr.org/2024/2096.pdf)

### Abstract

Multi-party Private Set Union (MPSU) enables multiple participants to jointly compute the union of their private sets without leaking any additional information beyond the resulting union. Liu et al. (ASIACRYPT 2023) presented the first MPSU protocol that scales to large data sets, designating one participant as the "leader" responsible for obtaining the final union. However, this approach assumes that the leader does not collude with any other participant, which can be impractical due to the inherent lack of mutual trust among participants, thereby limiting its applicability.
On the other hand, the state-of-the-art protocol that allows all participants to learn the computed union was proposed by Seo et al. (PKC 2012). While their construction achieves $O(1)$ round complexity, it remains secure only if fewer than half of the participants collude, leaving open the problem of designing stronger collusion tolerance and multi-party output.
In this work, we address these limitations by first proposing $\Pi_\text{MPSU}^{\text{one-leader}}$ that designates one participant as leader to obtain the union result. Building upon this construction, we extend this design to $\Pi_\text{MPSU}^{\text{leaderless}}$, which enables every participant to receive the union result simultaneously. Both protocols operate under the semi-honest model, tolerate maximal collusion among participants, and efficiently handle large-scale set computation. We implement these schemes and conducted a comprehensive comparison against state-of-the-art solutions. The result shows that, for input sizes of $2^{12}$ at a comparable security level, $\Pi_\text{MPSU}^{\text{one-leader}}$ achieves a $663$ times speedup in online runtime compared to the state-of-the-art. Furthermore, it also remains $22$ times faster than half-collusion-tolerant protocol.

## 2024/2097

* Title: NMFT: A Copyrighted Data Trading Protocol based on NFT and AI-powered Merkle Feature Tree
* Authors: Dongming Zhang, Lei Xie, Yu Tao
* [Permalink](https://eprint.iacr.org/2024/2097)
* [Download](https://eprint.iacr.org/2024/2097.pdf)

### Abstract

With the rapid growth of blockchain-based Non-Fungible Tokens (NFTs), data trading has evolved to incorporate NFTs for ownership verification. However, the NFT ecosystem faces significant challenges in copyright protection, particularly when malicious buyers slightly modify the purchased data and re-mint it as a new NFT, infringing upon the original owner's rights. In this paper, we propose a copyright-preserving data trading protocol to address this challenge.

First, we introduce the Merkle Feature Tree (MFT), an enhanced version of the traditional Merkle Tree that incorporates an AI-powered feature layer above the data layer. Second, we design a copyright challenge phase during the trading process, which recognizes the data owner with highly similar feature vectors and earlier on-chain timestamp as the legitimate owner. Furthermore, to achieve efficient and low-gas feature vector similarity computation on blockchain, we employ Locality-Sensitive Hashing (LSH) to compress high-dimensional floating-point feature vectors into single uint256 integers.

Experiments with multiple image and text feature extraction models demonstrate that LSH effectively preserves the similarity between highly similar feature vectors before and after compression, thus supporting similarity-based copyright challenges. Experimental results on the Ethereum Sepolia testnet demonstrate NMFT's scalability with sublinear growth in gas consumption while maintaining stable latency.

## 2024/2098

* Title: Asymptotically Optimal Adaptive Asynchronous Common Coin and DKG with Silent Setup
* Authors: Hanwen Feng, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/2098)
* [Download](https://eprint.iacr.org/2024/2098.pdf)

### Abstract

This paper presents the first optimal-resilient, adaptively secure asynchronous common coin protocol with $O(\lambda n^2)$ communication complexity and $O(1)$ rounds, requiring only a public silent setup. Our protocol immediately implies a sequence of quadratic-communication, constant-round asynchronous Byzantine agreement protocols and asynchronous distributed key generation with a silent setup. Along the way, we formulate a new primitive called asynchronous subset alignment and introduce a simple framework to reason about specific composition security suitable for asynchronous common coin, which may be of independent interest.

## 2024/2099

* Title: MicroNova: Folding-based arguments with efficient (on-chain) verification
* Authors: Jiaxing Zhao, Srinath Setty, Weidong Cui
* [Permalink](https://eprint.iacr.org/2024/2099)
* [Download](https://eprint.iacr.org/2024/2099.pdf)

### Abstract

We describe the design and implementation of MicroNova, a folding-based recursive argument for producing proofs of incremental computations of the form $y = F^{(\ell)}(x)$, where $F$ is a possibly non-deterministic computation (encoded using a constraint system such as R1CS), $x$ is the initial input, $y$ is the output, and $\ell > 0$. The proof of an $\ell$-step computation is produced step-by-step such that the proof size nor the time to verify it depends on $\ell$. The proof at the final iteration is then compressed, to achieve further succinctness in terms of proof size and verification time. Compared to prior folding-based arguments, a distinguishing aspect of MicroNova is the concrete efficiency of the verifier—even in a resource-constrained environment such as Ethereum’s blockchain. In particular, the compressed proof consists of $O(\log{N})$ group elements and it can be verified with $O(\log{N})$ group scalar multiplications and two pairing operations, where $N$ is the number of constraints for a single invocation of $F$. MicroNova requires a universal trusted setup and can employ any existing setup material created for the popular KZG univariate polynomial commitment scheme. Finally, we implement and experimentally evaluate MicroNova. We find that MicroNova’s proofs can be efficiently verified on the Ethereum blockchain with $\approx$2.2M gas. Furthermore, MicroNova’s prover incurs minimal overheads atop its baseline Nova’s prover.

## 2024/2100

* Title: Compact Key Storage in the Standard Model
* Authors: Yevgeniy Dodis, Daniel Jost
* [Permalink](https://eprint.iacr.org/2024/2100)
* [Download](https://eprint.iacr.org/2024/2100.pdf)

### Abstract

In recent work [Crypto'24], Dodis, Jost, and Marcedone introduced Compact Key Storage (CKS) as a modern approach to backup for end-to-end (E2E) secure applications. As most E2E-secure applications rely on a sequence of secrets $(s_1,...,s_n)$ from which, together with the ciphertexts sent over the network, all content can be restored, Dodis et al. introduced CKS as a primitive for backing up $(s_1,...,s_n)$. The authors provided definitions as well as two practically efficient schemes (with different functionality-efficiency trade-offs). Both, their security definitions and schemes relied however on the random oracle model (ROM).

In this paper, we first show that this reliance is inherent. More concretely, we argue that in the standard model, one cannot have a general CKS instantiation that is applicable to all "CKS-compatible games", as defined by Dodis et al., and realized by their ROM construction. Therefore, one must restrict the notion of CKS-compatible games to allow for standard model CKS instantiations.

We then introduce an alternative standard-model CKS definition that makes concessions in terms of functionality (thereby circumventing the impossibility). More precisely, we specify CKS which does not recover the original secret $s_i$ but a derived key $k_i$, and then observe that this still suffices for many real-world applications. We instantiate this new notion based on minimal assumptions. For passive security, we provide an instantiation based on one-way functions only. For stronger notions, we additionally need collision-resistant hash functions and dual-PRFs, which we argue to be minimal.

Finally, we provide a modularization of the CKS protocols of Dodis et al. In particular, we present a unified protocol (and proof) for standard-model equivalents for both protocols introduced in the original work.

## 2025/1

* Title: Attribute Based Encryption for Turing Machines from Lattices
* Authors: Shweta Agrawal, Simran Kumari, Shota Yamada
* [Permalink](https://eprint.iacr.org/2025/001)
* [Download](https://eprint.iacr.org/2025/001.pdf)

### Abstract

We provide the first attribute based encryption (ABE) scheme for Turing machines supporting unbounded collusions from lattice assumptions. In more detail, the encryptor encodes an attribute $\mathbf{x}$ together with a bound $t$ on the machine running time and a message $m$ into the ciphertext, the key generator embeds a Turing machine $M$ into the secret key and decryption returns $m$ if and only if $M(\mathbf{x})=1$. Crucially, the input $\mathbf{x}$ and machine $M$ can be of unbounded size, the time bound $t$ can be chosen dynamically for each input and decryption runs in input specific time.

Previously the best known ABE for uniform computation supported only non-deterministic log space Turing machines (${\sf NL})$ from pairings (Lin and Luo, Eurocrypt 2020). In the post-quantum regime, the state of the art supports non-deterministic finite automata from LWE in the $\textit{ symmetric}$ key setting (Agrawal, Maitra and Yamada, Crypto 2019).

In more detail, our results are:

1. We construct the first ABE for ${\sf NL}$ from the LWE, evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) and Tensor LWE (Wee, Eurocrypt 2022) assumptions. This yields the first (conjectured) post-quantum ABE for ${\sf NL}$.
2. Relying on LWE, evasive LWE and a new assumption called $\textit{circular tensor}$ LWE, we construct ABE for all Turing machines. At a high level, the circular tensor LWE assumption incorporates circularity into the tensor LWE (Wee, Eurocrypt 2022) assumption.

Towards our ABE for Turing machines, we obtain the first CP-ABE for circuits of unbounded depth and size from the same assumptions -- this may be of independent interest.

## 2025/2

* Title: Voting with coercion resistance and everlasting privacy using linkable ring signatures
* Authors: Panagiotis Grontas, Aris Pagourtzis, Marianna Spyrakou
* [Permalink](https://eprint.iacr.org/2025/002)
* [Download](https://eprint.iacr.org/2025/002.pdf)

### Abstract

We propose an e-voting protocol based on a novel linkable ring signature scheme with unconditional anonymity. In our system, all voters register create private credentials and register their public counterparts. To vote, they create a ring (anonymity set) consisting of public credentials together with a proof of knowledge of their secret credential via our signature. Its unconditional anonymity prevents an attacker, no matter how powerful, from deducing the identity of the voter, thus attaining everlasting privacy. Additionally, our protocol provides coercion resistance in the JCJ framework; when an adversary tries to coerce a voter, the attack can be evaded by creating a signature with a fake but indistinguishable credential. During a moment of privacy, they will cast their real vote. Our scheme also provides verifiability and ballot secrecy.

## 2025/3

* Title: Post-Quantum DNSSEC with Faster TCP Fallbacks
* Authors: Aditya Singh Rawat, Mahabir Prasad Jhanwar
* [Permalink](https://eprint.iacr.org/2025/003)
* [Download](https://eprint.iacr.org/2025/003.pdf)

### Abstract

In classical DNSSEC, a drop-in replacement with quantum-safe cryptography would increase DNS query resolution times by $\textit{at least}$ a factor of $2\times$. Since a DNS response containing large post-quantum signatures is likely to get marked truncated ($\texttt{TC}$) by a nameserver (resulting in a wasted UDP round-trip), the client (here, the resolver) would have to retry its query over TCP, further incurring a $\textit{minimum}$ of two round-trips due to the three-way TCP handshake.

We present $\mathsf{TurboDNS}$: a backward-compatible protocol that eliminates $\textit{two}$ round-trips from the preceding flow by 1) sending TCP handshake data in the initial DNS/UDP flight itself, and 2) immediately streaming the DNS response over TCP after authenticating the client with a cryptographic cookie. Our experiments show that DNSSEC over $\mathsf{TurboDNS}$, with either Falcon-512 or Dilithium-2 as the zone signing algorithm, is practically as fast as the currently deployed ECDSA P-256 and RSA-2048 setups in resolving $\texttt{QTYPE}$ $\texttt{A}$ DNS queries.

## 2025/4

* Title: Smaug: Modular Augmentation of LLVM for MPC
* Authors: Radhika Garg, Xiao Wang
* [Permalink](https://eprint.iacr.org/2025/004)
* [Download](https://eprint.iacr.org/2025/004.pdf)

### Abstract

Secure multi-party computation (MPC) is a crucial tool for privacy-preserving computation, but it is getting increasingly complicated due to recent advancements and optimizations. Programming tools for MPC allow programmers to develop MPC applications without mastering all cryptography. However, most existing MPC programming tools fail to attract real users due to the lack of documentation, maintenance, and the ability to compose with legacy codebases. In this work, we build Smaug, a modular extension of LLVM. Smaug seamlessly brings all LLVM support to MPC programmers, including error messaging, documentation, code optimization, and frontend support to compile from various languages to LLVM intermediate representation (IR). Smaug can efficiently convert non-oblivious LLVM IR to their oblivious counterparts while applying popular optimizations as LLVM code transformations. With benchmarks written in C++ and Rust and backends for Yao and GMW protocols, we observe that Smaug performs as well as (and sometimes much better than) prior tools using domain-specific languages with similar backends. Finally, we use Smaug to compile open-source projects that
implement Minesweeper and Blackjack, producing usable two-party games with ease.

## 2025/5

* Title: What is "legal" and "illegal?": Social Norms, Current Practices and Perceived Risks among the Cryptocurrency Users in Bangladesh
* Authors: Tanusree Sharma, Atm Mizanur Rahman, Silvia Sandhi, Yang Wang, Rifat Shahriyar, S M Taiabul Haque
* [Permalink](https://eprint.iacr.org/2025/005)
* [Download](https://eprint.iacr.org/2025/005.pdf)

### Abstract

Cryptocurrency practices worldwide are seen as innovative, yet they navigate a fragmented regulatory environment. Many local authorities aim to balance promoting innovation, safeguarding consumers, and managing potential threats. In particular, it is unclear how people deal with cryptocurrencies in the regions where trading or mining is prohibited. This insight is crucial in conveying the risk reduction strategies. To address this, we conducted semi-structured interviews with 28 cryptocurrency traders and miners from Bangladesh, where the local authority is hostile towards cryptocurrencies. Our research revealed that the participants use unique strategies to mitigate risks around cryptocurrencies. Our findings indicate a prevalent uncertainty at both personal and organizational levels concerning the interpretation of laws, a situation worsened by the actions of the major financial service providers who indirectly facilitate cryptocurrency transactions. We further connect our findings to the broader issues in HCI regarding folk models, informal market and legality, and education and awareness.

## 2025/6

* Title: Nearly Quadratic Asynchronous Distributed Key Generation
* Authors: Ittai Abraham, Renas Bacho, Julian Loss, Gilad Stern
* [Permalink](https://eprint.iacr.org/2025/006)
* [Download](https://eprint.iacr.org/2025/006.pdf)

### Abstract

We prove that for any $1\le k\le \log n$, given a VRF setup and assuming secure erasures, there exists a protocol for Asynchronous Distributed Key Generation (ADKG) that is resilient to a strongly adaptive adversary that can corrupt up to $f<n/3$ parties. With all but negligible probability, all nonfaulty parties terminate in an expected $O(k)$ rounds and send a total expected $\tilde{O}(n^{2+1/k})$ messages.

## 2025/7

* Title: Non Linearizable Entropic Operator
* Authors: Daniel Nager
* [Permalink](https://eprint.iacr.org/2025/007)
* [Download](https://eprint.iacr.org/2025/007.pdf)

### Abstract

In [Pan21] a linearization attack is proposed in order to break the cryp-
tosystem proposed in [Gli21]. We want to propose here a non-linearizable
operator that disables this attack as this operator doesn't give raise to a
quasigrup and doesn't obey the latin square property.

## 2025/8

* Title: A Survey to Zero-Knowledge Interactive Verifiable Computing: Utilizing Randomness in Low-Degree Polynomials
* Authors: Angold Wang
* [Permalink](https://eprint.iacr.org/2025/008)
* [Download](https://eprint.iacr.org/2025/008.pdf)

### Abstract

This survey provides a comprehensive examination of zero-knowledge interactive verifiable computing, emphasizing the utilization of randomnes in low-degree polynomials. We begin by tracing the evolution of general-purpose verifiable computing, starting with the foundational concepts of complexity theory developed in the 1980s, including classes such as P, NP and NP-completeness. Through an exploration of the Cook-Levin Theorem and the transformation between NP problems like HAMPATH and SAT, we demonstrate the reducibility of NP problems to a unified framework, laying the groundwork for subsequent advancements.

Recognizing the limitations of NP-based proof systems in effectively verifying certain problems, we then delve into interactive proof systems (IPS) as a probabilistic extension of NP. IPS enhance verification efficiency by incorporating randomness and interaction, while accepting a small chance of error for that speed. We address the practical challenges of traditional IPS, where the assumption of a prover with unlimited computational power is unrealistic, and introduce the concept of secret knowledge. This approach allows a prover with bounded computational resources to convincingly demonstrate possession of secret knowledge to the verifier, thereby enabling high-probability verification by the verifier. We quantify this knowledge by assessing the verifier's ability to distinguish between a simulator and genuine prover, referencing seminal works such as Goldwasser et al.'s "The knowledge Complexity of Theorem Proving Procedures"

The survey further explores essential mathematical theories and cryptographic protocols, including the Schwartz-Zippel lemma and Reed-Solomon error correction, which underpin the power of low-degree polynomials in error detection and interactive proof systems. We provide a detailed, step-by-step introduction to tyhe sum-check protocol, proving its soundness and runtime characteristics.

Despite the sum-check protocol's theoretical applicability to all NP problems via SAT reduction, we highlight the sum-check protocol's limitation in requiring superpolynomial time for general-purpose computations of a honest prover. To address these limitations, we introduce the GKR protocol, a sophisticate general-purpose interactive proof system developed in the 2010s. We demonstrate how the sum-check protocol integrates into the GKR framework to achieve efficient, sound verification of computations in polynomial time. This survey not only reviews the historical and theoretical advancement in verifiable computing in the past 30 years but also offers an accessible introduction for newcomers by providing a solid foundation to understand the significant advancements in verifiable computing over the past decade, including developments such as ZK-SNARKs.

## 2025/9

* Title: Efficient CPA Attack on Hardware Implementation of ML-DSA in Post-Quantum Root of Trust
* Authors: Merve Karabulut, Reza Azarderakhsh
* [Permalink](https://eprint.iacr.org/2025/009)
* [Download](https://eprint.iacr.org/2025/009.pdf)

### Abstract

Side-channel attacks (SCA) pose a significant threat to cryptographic implementations, including those designed to withstand the computational power of quantum computers.
This paper introduces the first side-channel attack on an industry-grade post-quantum cryptography implementation, Adam's Bridge.
Specifically, we present a Correlation Power Analysis (CPA) attack targeting the hardware implementation of ML-DSA within Caliptra, an open-source Silicon Root of Trust framework developed through a multi-party collaboration involving Google, AMD, and Microsoft.

Our attack focuses on the modular reduction process that follows the Number Theoretic Transform-based polynomial pointwise multiplication.
By exploiting side-channel leakage from a distinctive reduction algorithm unique to Adam's Bridge and leveraging the zeroization mechanism used to securely erase sensitive information by clearing internal registers, we significantly enhance the attack's efficacy.
Our findings reveal that an adversary can extract Caliptra's ML-DSA secret keys using only 10,000 power traces.
With access to these keys, an attacker could forge signatures for certificate generation, thereby compromising the integrity of the root of trust.
This work highlights the vulnerabilities of industry-standard root-of-trust systems to side-channel attacks. It underscores the urgent need for robust countermeasures to secure commercially deployed systems against such threats.

## 2025/10

* Title: A Combinatorial Approach to IoT Data Security
* Authors: Anandarup Roy, Bimal Kumar Roy, Kouichi Sakurai, Suprita Talnikar
* [Permalink](https://eprint.iacr.org/2025/010)
* [Download](https://eprint.iacr.org/2025/010.pdf)

### Abstract

This article explores the potential of Secret Sharing-Based Internet of Things (SBIoT) as a promising cryptographic element across diverse applications, including secure data storage in commercial cloud systems (Datachest), smart home environments (encompassing sensors, cameras, smart locks, and smart assistants), and e-health applications (protecting patient data and medical records). Beyond these applications, the paper makes two key contributions: the introduction of a novel cheater identification algorithm designed to verify the correct submission of shares during secret reconstruction, and empirical validation through experimental studies to support the theoretical advancements. This multifaceted approach not only demonstrates the versatility of SBIoT but also proposes innovative mechanisms to enhance security and integrity, contributing to the development of a more robust cryptographic framework.
This article expands upon the work presented in the poster "A Combinatorial Approach to IoT Data Security" at IWSEC 2023, Yokohama, Japan.

## 2025/11

* Title: DL-SCADS: Deep Learning-Based Post-Silicon Side-Channel Analysis Using Decomposed Signal
* Authors: Dipayan Saha, Farimah Farahmandi
* [Permalink](https://eprint.iacr.org/2025/011)
* [Download](https://eprint.iacr.org/2025/011.pdf)

### Abstract

Side-channel analysis (SCA) does not aim at the algorithm's weaknesses but rather its implementations. The rise of machine learning (ML) and deep learning (DL) is giving adversaries advanced capabilities to perform stealthy attacks.. In this paper, we propose DL-SCADS, a DL-based approach along with signal decomposition techniques to leverage the power of secret key extraction from post-silicon EM/power side-channel traces. We integrate previously proven effective ideas of model ensembling and automated hyperparameter tuning with signal decomposition to develop an efficient and robust side-channel attack. Extensive experiments are performed on Advanced Encryption Standard (AES) and Post-Quantum Cryptography (PQC) to demonstrate the efficacy of our approach. The evaluation of the performance of the side-channel attack employing various decomposition techniques and comparison with the proposed approach in a range of datasets are also tabulated.

## 2025/12

* Title: Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell
* Authors: Wouter Legiest, Jan-Pieter D'Anvers, Bojan Spasic, Nam-Luc Tran, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/012)
* [Download](https://eprint.iacr.org/2025/012.pdf)

### Abstract

This paper presents a novel approach to calculating the Levenshtein (edit) distance within the framework of Fully Homomorphic Encryption (FHE), specifically targeting third-generation schemes like TFHE. Edit distance computations are essential in applications across finance and genomics, such as DNA sequence alignment. We introduce an optimised algorithm that significantly reduces the cost of edit distance calculations called Leuvenshtein. This algorithm specifically reduces the number of programmable bootstraps (PBS) needed per cell of the calculation, lowering it from approximately 28 operations—required by the conventional Wagner-Fisher algorithm—to just 1. Additionally, we propose an efficient method for performing equality checks on characters, reducing ASCII character comparisons to only 2 PBS operations. Finally, we explore the potential for further performance improvements by utilizing preprocessing when one of the input strings is unencrypted. Our Leuvenshtein achieves up to $205\times$ faster performance compared to the best available TFHE implementation and up to $39\times$ faster than an optimised implementation of the Wagner-Fisher algorithm. Moreover, when offline preprocessing is possible due to the presence of one unencrypted input on the server side, an additional $3\times$ speedup can be achieved.

## 2025/13

* Title: Wave Hello to Privacy: Efficient Mixed-Mode MPC using Wavelet Transforms
* Authors: José Reis, Mehmet Ugurbil, Sameer Wagh, Ryan Henry, Miguel de Vega
* [Permalink](https://eprint.iacr.org/2025/013)
* [Download](https://eprint.iacr.org/2025/013.pdf)

### Abstract

This paper introduces new protocols for secure multiparty computation (MPC) leveraging Discrete Wavelet Transforms (DWTs) for computing nonlinear functions over large domains. By employing DWTs, the protocols significantly reduce the overhead typically associated with Lookup Table-style (LUT) evaluations in MPC. We state and prove foundational results for DWT-compressed LUTs in MPC, present protocols for 9 of the most common activation functions used in ML, and experimentally evaluate the performance of our protocols for large domain sizes in the LAN and WAN settings. Our protocols are extremely fast -- for instance, when considering 64-bit inputs, computing 1000 parallel instances of the sigmoid function, with an error less than $2^{-24}$ takes only a few hundred milliseconds incurs just 29\,KiB of online communication (40 bytes per evaluation).

## 2025/14

* Title: SPY-PMU: Side-Channel Profiling of Your Performance Monitoring Unit to Leak Remote User Activity
* Authors: Md Kawser Bepary, Arunabho Basu, Sajeed Mohammad, Rakibul Hassan, Farimah Farahmandi, Mark Tehranipoor
* [Permalink](https://eprint.iacr.org/2025/014)
* [Download](https://eprint.iacr.org/2025/014.pdf)

### Abstract

The Performance Monitoring Unit (PMU), a standard feature in all modern computing systems, presents significant security risks by leaking sensitive user activities through microarchitectural event data. This work demonstrates the feasibility of remote side-channel attacks leveraging PMU data, revealing vulnerabilities that compromise user privacy and enable covert surveillance without physical access to the target machine. By analyzing the PMU feature space, we create distinct micro-architectural fingerprints for benchmark applications, which are then utilized in machine learning (ML) models to detect the corresponding benchmarks. This approach allows us to build a pre-trained model for benchmark detection using the unique micro-architectural fingerprints derived from PMU data. Subsequently, when an attacker remotely accesses the victim’s PMU data, the pre-trained model enables the identification of applications used by the victim with high accuracy. In our proof-of-concept demonstration, the pre-trained model successfully identifies applications used by a victim when the attacker remotely accesses PMU data, showcasing the potential for malicious exploitation of PMU data. We analyze stress-ng benchmarks and build our classifiers using logistic regression, decision tree, k-nearest neighbors, and random forest ML models. Our proposed models achieve an average prediction accuracy of 98%, underscoring the potential risks associated with remote side-channel analysis using PMU data and emphasizing the need for more robust safeguards. This work underscores the urgent need for robust countermeasures to protect against such vulnerabilities and provides a foundation for future research in micro-architectural security.

## 2025/15

* Title: A New Method for Solving Discrete Logarithm Based on Index Calculus
* Authors: Jianjun HU
* [Permalink](https://eprint.iacr.org/2025/015)
* [Download](https://eprint.iacr.org/2025/015.pdf)

### Abstract

Index Calculus (IC) algorithm is the most effective probabilistic algorithm for solving discrete logarithms over finite fields of prime numbers, and it has been widely applied to cryptosystems based on elliptic curves. Since the IC algorithm was proposed in 1920, the research on it has never stopped, especially discretization of prime numbers on the finite fields, both the algorithm itself and its application have been greatly developed. Of course, there has been some research on elliptic curves,but with little success. For the IC algorithm, scholars pay more attention to how to improve the probability of solving and reduce the time complexity of calculation. It is the first time for the IICA to study the optimization problem of the IC by using the method of integer. However, the IICA only studies the case of integer up, and fails to consider the case of integer down. It is found that the integer direction of the IICA can be integer up or integer down, but the concept of modular multiplication needs to be used when integer down. After optimizing the IICA, the probability of successful solution of discrete logarithm is increased by nearly 2 times, and the number of transformations is also reduced to a certain extent, thus reducing the time complexity of solution. The re-optimized the IC algorithm greatly improves the probability of successful the IC solution. This research result poses a serious challenge to cryptosystems based on finite fields of prime numbers.

## 2025/16

* Title: Dynamically Available Common Subset
* Authors: Yuval Efron, Ertem Nusret Tas
* [Permalink](https://eprint.iacr.org/2025/016)
* [Download](https://eprint.iacr.org/2025/016.pdf)

### Abstract

Internet-scale consensus protocols used by blockchains are designed to remain operational in the presence of unexpected temporary crash faults (the so-called sleepy model of consensus) -- a critical feature for the latency-sensitive financial applications running on these systems.
However, their leader-based architecture, where a single block proposer is responsible for creating the block at each height, makes them vulnerable to short-term censorship attacks, in which the proposers profit at the application layer by excluding certain transactions.
In this work, we introduce an atomic broadcast protocol, secure in the sleepy model, that ensures the inclusion of all transactions within a constant expected time, provided that at least one participating node is non-censoring at all times.
Unlike traditional approaches, our protocol avoids designating a single proposer per block height, instead leveraging a so-called dynamically available common subset (DACS) protocol -- the first of its kind in the sleepy model. Additionally, our construction guarantees deterministic synchronization -- once an honest node confirms a block, all other honest nodes do so within a constant time, thus addressing a shortcoming of many low-latency sleepy protocols.

## 2025/17

* Title: New Quantum Cryptanalysis of Binary Elliptic Curves (Extended Version)
* Authors: Kyungbae Jang, Vikas Srivastava, Anubhab Baksi, Santanu Sarkar, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2025/017)
* [Download](https://eprint.iacr.org/2025/017.pdf)

### Abstract

This paper improves upon the quantum circuits required for the Shor's attack on binary elliptic curves. We present two types of quantum point addition, taking both qubit count and circuit depth into consideration.

In summary, we propose an in-place point addition that improves upon the work of Banegas et al. from CHES'21, reducing the qubit count – depth product by more than $73\%$ – $81\%$ depending on the variant. Furthermore, we develop an out-of-place point addition by using additional qubits. This method achieves the lowest circuit depth and offers an improvement of over $92\%$ in the qubit count – quantum depth product (for a single step).

To the best of our knowledge, our work improves from all previous works (including the CHES'21 paper by Banegas et al., the IEEE Access'22 paper by Putranto et al., and the CT-RSA'23 paper by Taguchi and Takayasu) in terms of circuit depth and qubit count – depth product.

Equipped with the implementations, we discuss the post-quantum security of binary elliptic curve cryptography. Under the MAXDEPTH metric (proposed by the US government's NIST), the quantum circuit with the highest depth in our work is $2^{24}$, which is significantly lower than the MAXDEPTH limit of $2^{40}$. For the gate count – full depth product, a metric for estimating quantum attack cost (used by NIST), the highest value in our work is $2^{60}$, considerably below the post-quantum security level 1 threshold (of the order of $2^{156}$).

## 2025/18

* Title: On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography
* Authors: Maxime Bombar, Nicolas Resch, Emiel Wiedijk
* [Permalink](https://eprint.iacr.org/2025/018)
* [Download](https://eprint.iacr.org/2025/018.pdf)

### Abstract

Cryptography based on the presumed hardness of decoding codes -- i.e., code-based cryptography -- has recently seen increased interest due to its plausible security against quantum attackers. Notably, of the four proposals for the NIST post-quantum standardization process that were advanced to their fourth round for further review, two were code-based. The most efficient proposals -- including HQC and BIKE, the NIST submissions alluded to above -- in fact rely on the presumed hardness of decoding structured codes. Of particular relevance to our work, HQC is based on quasi-cyclic codes, which are codes generated by matrices consisting of two cyclic blocks.

In particular, the security analysis of HQC requires a precise understanding of the Decryption Failure Rate (DFR), whose analysis relies on the following heuristic: given random "sparse" vectors $e_1,e_2$ (say, each coordinate is i..i.d. Bernoulli) multiplied by fixed "sparse" quasi-cyclic matrices $A_1,A_2$, the weight of resulting vector $e_1A_1+e_2A_2$ is very concentrated around its expectation. In the documentation, the authors model the distribution of $e_1A_1+e_2A_2$ as a vector with independent coordinates (and correct marginal distribution). However, we uncover cases where this modeling fails. While this does not invalidate the (empirically verified) heuristic that the weight of $e_1A_1+e_2A_2$ is concentrated, it does suggest that the behavior of the noise is a bit more subtle than previously predicted. Lastly, we also discuss implications of our result for potential worst-case to average-case reductions for quasi-cyclic codes.