[digest] 2025 Week 14

## In this issue

1. [2025/198] Engorgio: An Arbitrary-Precision Unbounded-Size ...
2. [2025/326] On the Adaptive Security of Free-XOR-based Garbling ...
3. [2025/383] Pencil: A Domain-Extended PRF with Full $n$-bit ...
4. [2025/569] Solving Data Availability Limitations in Client- ...
5. [2025/570] Partial Key Overwrite Attacks in Microcontrollers: ...
6. [2025/571] Universally Composable Relaxed Asymmetric Password- ...
7. [2025/572] Zinnia: An Expressive and Efficient Tensor-Oriented ...
8. [2025/573] Forking Lemma in EasyCrypt
9. [2025/574] Buffalo: A Practical Secure Aggregation Protocol ...
10. [2025/575] Wagner's Algorithm Provably Runs in Subexponential ...
11. [2025/576] Pre-Constructed Publicly Verifiable Secret Sharing ...
12. [2025/577] Making GCM Great Again: Toward Full Security and ...
13. [2025/578] Efficient Garbled Pseudorandom Functions and Lookup ...
14. [2025/579] REGKYC: Supporting Privacy and Compliance ...
15. [2025/580] Efficient Revocable Identity-Based Encryption from ...
16. [2025/581] Reusable Dynamic Multi-Party Homomorphic Encryption
17. [2025/582] Release the Power of Rejected Signatures: An ...
18. [2025/583] Counter Galois Onion (CGO) for Tor: Fast Non- ...
19. [2025/584] The Singularity Random Number Generator: Bridging ...
20. [2025/585] Adaptively-Secure Big-Key Identity-Based Encryption
21. [2025/586] Heuristic Algorithm for Solving Restricted SVP and ...
22. [2025/587] Lifeboats on the Titanic Cryptography
23. [2025/588] A Place for Everyone vs Everyone in its Place: ...
24. [2025/589] Defeating AutoLock: From Simulation to Real-World ...
25. [2025/590] $\mathsf{emGraph}$: Efficient Multiparty Secure ...
26. [2025/591] ColliderVM: Stateful Computation on Bitcoin
27. [2025/592] DSM: Decentralized State Machine - The Missing ...
28. [2025/593] Oblivious Immutable Memory
29. [2025/594] Efficient SNARKs for Boolean Circuits via Sumcheck ...
30. [2025/595] Partial Key Exposure Attacks on UOV and Its Variants
31. [2025/596] Highway to Hull: An Algorithm for Solving the ...
32. [2025/597] SoK: Self-Generated Nudes over Private Chats: How ...
33. [2025/598] Nominal State-Separating Proofs
34. [2025/599] Insecurity of One Decentralized Attribute-based ...
35. [2025/600] Improved Round-by-round Soundness IOPs via Reed- ...
36. [2025/601] PHOENIX: Crypto-Agile Hardware Sharing for ML-KEM ...
37. [2025/602] Lattice-Based Sanitizable Signature Schemes: ...
38. [2025/603] Mobile Byzantine Agreement in a Trusted World
39. [2025/604] On the success rate of simple side-channel attacks ...

## 2025/198

* Title: Engorgio: An Arbitrary-Precision Unbounded-Size Hybrid Encrypted Database via Quantized Fully Homomorphic Encryption
* Authors: Song Bian, Haowen Pan, Jiaqi Hu, Zhou Zhang, Yunhao Fu, Jiafeng Hua, Yi Chen, Bo Zhang, Yier Jin, Jin Dong, Zhenyu Guan
* [Permalink](https://eprint.iacr.org/2025/198)
* [Download](https://eprint.iacr.org/2025/198.pdf)

### Abstract

This work proposes an encrypted hybrid database framework that combines vectorized data search and relational data query over quantized fully homomorphic encryption (FHE). We observe that, due to the lack of efficient encrypted data ordering capabilities, most existing encrypted database (EDB) frameworks do not support hybrid queries involving both vectorized and relational data. To further enrich query expressiveness while retaining evaluation efficiency, we propose Engorgio, a hybrid EDB framework based on quantized data ordering techniques over FHE.  Specifically, we design a new quantized data encoding scheme along with a set of novel comparison and permutation algorithms to accurately generate and apply orders between large-precision data items. Furthermore, we optimize specific query types, including full table scan, batched query, and Top-k query to enhance the practical performance of the proposed framework. In the experiment, we show that, compared to the state-of-the-art EDB frameworks, Engorgio is up to 28x--854x faster in homomorphic comparison, 65x--687x faster in homomorphic sorting and 15x--1,640x faster over a variety of end-to-end relational, vectorized, and hybrid SQL benchmarks. Using Engorgio, the amortized runtime for executing a relational and hybrid query on a 48-core processor is under 3 and 75 seconds, respectively, over a 10K-row hybrid database.



## 2025/326

* Title: On the Adaptive Security of Free-XOR-based Garbling Schemes in the Plain Model
* Authors: Anasuya Acharya, Karen Azari, Chethan Kamath
* [Permalink](https://eprint.iacr.org/2025/326)
* [Download](https://eprint.iacr.org/2025/326.pdf)

### Abstract

A Garbling Scheme is a fundamental cryptographic primitive, with numerous theoretical and practical applications.  Since its inception by Yao (FOCS'82, '86), optimizing the communication and computation complexities of securely garbling circuits has been an area of active research. One such optimization, and perhaps the most fundamental, is the `Free-XOR' technique (Kolesnikov and Schneider, ICALP'08) which allows XOR gates in a function garbling to not require representation, and therefore communication.

Since then, several works have designed and analysed the security of schemes that adopt the Free-XOR optimisation. In particular: (1) Applebaum (JoC'16) proved that this can be securely instantiated assuming symmetric-key encryption satisfying a notion called RK-KDM security; and (2) Zahur, Rosulek and Evans (Eurocrypt'15) proposed the so-called `Half Gates' scheme, and proved that it can be instantiated assuming hash functions satisfying a notion called CCR security. Although both schemes have been proven selectively secure, prior work leaves it open to analyze whether they satisfy a stronger security notion -- adaptive security -- in the plain model.

In this work, we formally show that the selective security of these two schemes cannot be lifted to adaptive security under the same assumptions. To establish these barriers, we adopt techniques from the work of Kamath et al (Crypto'21), who proved similar negative results for Yao's garbling. We use that as a starting point and introduce new techniques tailored towards addressing Free-XOR-based schemes.



## 2025/383

* Title: Pencil: A Domain-Extended PRF with Full $n$-bit Security for Strengthening GCM and More
* Authors: Ritam Bhaumik, Jean Paul Degabriele
* [Permalink](https://eprint.iacr.org/2025/383)
* [Download](https://eprint.iacr.org/2025/383.pdf)

### Abstract

We consider the problem of constructing efficient pseudorandom functions with Beyond-Birthday-Bound (BBB) security from blockciphers. More specifically, we are interested in variable-output-length pseudorandom functions (PRF) whose domain is twice that of the underlying blockcipher. We present two such constructions, $\textsf{Pencil}$ and $\sharp\textsf{Pencil}$, which provide weak PRF and full PRF security, respectively, where both achieve full $n$-bit security. While several recent works have focused on constructing BBB PRFs from blockciphers, much less attention has been given to weak PRF constructions which can potentially be constructed more efficiently and still serve as a useful primitive. Another understudied problem in this domain, is that of extending the domain of a BBB PRF, which turns out to be rather challenging. Besides being of theoretical interest in itself, this is also a very practical problem. Often, the input to the BBB PRF is a nonce, but random nonces are much easier to handle in practice as they do not require maintaining state---which can be very cumbersome in distributed systems and encrypted cloud storage. Accordingly, in order to maintain a BBB security bound, one requires random nonces of size between $1.5n$ and $2n$ bits long and corresponding BBB (weak) PRF constructions that admit matching input sizes. NIST has recently announced a pre-draft call for comments to standardise AEAD schemes that can encrypt larger amounts of data and admit larger nonces. The call lists two approaches. The first is to define an analogue of GCM using a 256-bit blockcipher, and the second is based on a recent proposal by Gueron, to extend GCM with a key derivation function (KDF) called DNDK to increase its security. In essence, DNDK is a BBB-secure expanding weak pseudorandom function with a domain size of 192 bits that is realised from AES. Our work makes relevant contributions to this domain in two important ways. Firstly, an immediate consequence of our work is that one can construct a GCM analogue with BBB security from $\sharp\textsf{Pencil}$, without resorting to a 256-bit blockcipher. Our second contribution is that $\sharp\textsf{Pencil}$ can be used as a KDF in combination with GCM in an analogous manner to DNDK-GCM. However, $\sharp\textsf{Pencil}$ being a full PRF as opposed to DNDK which is only a weak PRF, allows one to prove the KDF-GCM composition secure as an AEAD scheme. Finally, when contrasting $\textsf{Pencil}$ and DNDK as weak PRFs with comparable parameters, our construction requires only half the blockcipher calls.



## 2025/569

* Title: Solving Data Availability Limitations in Client-Side Validation with UTxO Binding
* Authors: Yunwen Liu, Bo Wang, Ren Zhang
* [Permalink](https://eprint.iacr.org/2025/569)
* [Download](https://eprint.iacr.org/2025/569.pdf)

### Abstract

Issuing tokens on Bitcoin remains a highly sought-after goal, driven by its market dominance and robust security. However, Bitcoin's limited on-chain storage and functionality pose significant challenges. Among the various approaches to token issuance on Bitcoin, client-side validation (CSV) has emerged as a prominent solution. CSV delegates data storage and functionalities beyond Bitcoin’s native capabilities to off-chain clients, while leveraging the blockchain to validate tokens and prevent double-spending. Nevertheless, these protocols require participants to maintain token ownership and transactional data, rendering them vulnerable to data loss and malicious data withholding. In this paper, we propose UTxO binding, a novel framework that achieves both robust data availability and enhanced functionality compared to existing CSV designs. This approach securely binds a Bitcoin UTxO, which prevents double-spending, to a UTxO on an auxiliary blockchain, providing data storage and programmability. We formally prove its security and implement our design using Nervos CKB as the auxiliary blockchain.



## 2025/570

* Title: Partial Key Overwrite Attacks in Microcontrollers: a Survey
* Authors: pcy Sluys, Lennert Wouters, Benedikt Gierlichs, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/570)
* [Download](https://eprint.iacr.org/2025/570.pdf)

### Abstract

Embedded devices can be exposed to a wide range of attacks. Some classes of attacks can be mitigated using security features or dedicated countermeasures. Examples include Trusted Execution Environments, and masking countermeasures against physical side-channel attacks. However, a system that incorporates such secure components is not automatically a secure system. Partial Key Overwrite attacks are one class of attacks that specifically target the interface between different components of the security system. These attacks may allow an adversary to extract otherwise protected cryptographic keys through careful manipulation of memory-mapped registers. So far this powerful class of attacks has received little attention in the academic literature. In this work, we provide an overview of known Partial Key Overwrite vulnerabilities and how they were used in real-world attacks. Additionally, we evaluated 31 common microcontrollers and embedded microprocessors from eleven distinct vendors and detail our findings. Based on a first high-level evaluation we selected 15 SoCs and performed an in-depth evaluation. This evaluation revealed that at least eight of these SoCs are vulnerable to partial key overwrite attacks.



## 2025/571

* Title: Universally Composable Relaxed Asymmetric Password-Authenticated Key Exchange
* Authors: Shuya Hanai, Keisuke Tanaka, Masayuki Tezuka, Yusuke Yoshida
* [Permalink](https://eprint.iacr.org/2025/571)
* [Download](https://eprint.iacr.org/2025/571.pdf)

### Abstract

Password-Authenticated Key Exchange (PAKE) establishes a secure channel between two parties who share a password. Asymmetric PAKE is a variant of PAKE, where one party stores a hash of the password to preserve security under the situation that the party is compromised. The security of PAKE and asymmetric PAKE is often analyzed in the framework of universal composability (UC).
Abdalla et al. (CRYPTO '20) relaxed the UC security of PAKE and showed that the relaxed security still guarantees reasonable properties. This relaxation makes it possible to prove the security in the UC framework for several PAKE protocols.
In this paper, we propose a relaxed functionality of asymmetric PAKE by following the approach of Abdalla et al. We prove that the SPAKE2+ protocol UC-realizes this functionality. We also define a more relaxed functionality and prove that a variant of the AuCPace protocol UC-realizes it.



## 2025/572

* Title: Zinnia: An Expressive and Efficient Tensor-Oriented Zero-Knowledge Programming Framework
* Authors: Zhantong Xue, Pingchuan Ma, Zhaoyu Wang, Shuai Wang
* [Permalink](https://eprint.iacr.org/2025/572)
* [Download](https://eprint.iacr.org/2025/572.pdf)

### Abstract

Zero-knowledge proofs (ZKPs) are cryptographic protocols that enable a prover to convince a verifier of a statement's truth without revealing any details beyond its validity. Typically, the statement is encoded as an arithmetic circuit, and allows the prover to demonstrate that the circuit evaluates to true without revealing its inputs. Despite their potential to enhance privacy and security, ZKPs are difficult to write and optimize, limiting their adoption in machine learning and data science. To address these challenges, we introduce Zinnia, a zero-knowledge programming framework with high utility, expressiveness and efficiency for tensor-oriented computation. Zinnia provides a high-level programming language that enables developers to easily write ZKP programs, and it employs a novel symbolic execution-inspired approach to extracting semantics from these programs to generate arithmetic circuits. Zinnia supports tensor-oriented computations and provides a rich set of programming constructs, optimizations, and a powerful static type system for expressing and optimizing complex logic. We evaluate Zinnia across 25 real-world programming tasks and a user study, comparing it to existing solutions, including DSLs and zkVMs (Halo2, SP1, and RISC0). Our results demonstrate that Zinnia outperforms these baselines in utility, expressiveness, and efficiency, with a statistically significant reduction in development time, $2-3\times$ shorter code length, 19.3% smaller circuit size, and up to $245\times$ faster proving time compared to zkVMs, paving the way for practical ZKP applications in various domains.



## 2025/573

* Title: Forking Lemma in EasyCrypt
* Authors: Denis Firsov, Jakub Janků
* [Permalink](https://eprint.iacr.org/2025/573)
* [Download](https://eprint.iacr.org/2025/573.pdf)

### Abstract

Formal methods are becoming an important tool for ensuring correctness and security of cryptographic constructions. However, the support for certain advanced proof techniques, namely rewinding, is scarce among existing verification frameworks, which hinders their application to complex schemes such as multi-party signatures and zero-knowledge proofs.

We expand the support for rewinding in EasyCrypt by implementing a version of the general forking lemma by Bellare and Neven. We demonstrate its usability by proving EUF-CMA security of Schnorr signatures.



## 2025/574

* Title: Buffalo: A Practical Secure Aggregation Protocol for Asynchronous Federated Learning
* Authors: Riccardo Taiello, Clémentine Gritti, Melek Önen, Marco Lorenzi
* [Permalink](https://eprint.iacr.org/2025/574)
* [Download](https://eprint.iacr.org/2025/574.pdf)

### Abstract

Federated Learning (FL) has become a crucial framework for collaboratively training Machine Learning (ML) models while ensuring data privacy. Traditional synchronous FL approaches, however, suffer from delays caused by slower clients (called stragglers), which hinder the overall training process.

Specifically, in a synchronous setting, model aggregation happens once all the intended clients have submitted their local updates to the server. To address these inefficiencies, Buffered Asynchronous FL (BAsyncFL) was introduced, allowing clients to update the global model as soon as they complete local training. In such a setting, the new global model is obtained once the buffer is full, thus removing synchronization bottlenecks. Despite these advantages, existing Secure Aggregation (SA) techniques—designed to protect client updates from inference attacks—rely on synchronized rounds, making them unsuitable for asynchronous settings.

In this paper, we present Buffalo, the first practical SA protocol tailored for BAsyncFL. Buffalo leverages lattice-based encryption to handle scalability challenges in large ML models and introduces a new role, the assistant, to support the server in securely aggregating client updates. To protect against an actively corrupted server, we enable clients to verify that their local updates have been correctly integrated into the global model. Our comprehensive evaluation—incorporating theoretical analysis and real-world experiments on benchmark datasets—demonstrates that Buffalo is an efficient and scalable privacy-preserving solution in BAsyncFL environments.



## 2025/575

* Title: Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
* Authors: Léo Ducas, Lynn Engelberts, Johanna Loyer
* [Permalink](https://eprint.iacr.org/2025/575)
* [Download](https://eprint.iacr.org/2025/575.pdf)

### Abstract

At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus $q=\mathrm{poly}(n)$ and narrow error distribution, when given enough LWE samples. Taking a modular view, one may regard BKW as a combination of Wagner's algorithm (CRYPTO 2002), run over the corresponding dual problem, and the Aharonov-Regev distinguisher (JACM 2005). Hence the subexponential Wagner step alone should be of interest for solving this dual problem - namely, the Short Integer Solution problem (SIS) - but this appears to be undocumented so far.

We re-interpret this Wagner step as walking backward through a chain of projected lattices, zigzagging through some auxiliary superlattices. We further randomize the bucketing step using Gaussian randomized rounding to exploit the powerful discrete Gaussian machinery. This approach avoids sample amplification and turns Wagner's algorithm into an approximate discrete Gaussian sampler for $q$-ary lattices.
   
For an SIS lattice with $n$ equations modulo $q$, this algorithm runs in subexponential time $\exp(O(n/\log \log n))$ to reach a Gaussian width parameter $s = q/\mathrm{polylog}(n)$ only requiring $m = n + \omega(n/\log \log n)$ many SIS variables. This directly provides a provable algorithm for solving the Short Integer Solution problem in the infinity norm ($\mathrm{SIS}^\infty$) for norm bounds $\beta = q/\mathrm{polylog}(n)$. This variant of SIS underlies the security of the NIST post-quantum cryptography standard Dilithium.. Despite its subexponential complexity, Wagner's algorithm does not appear to threaten Dilithium's concrete security.



## 2025/576

* Title: Pre-Constructed Publicly Verifiable Secret Sharing and Applications
* Authors: Karim Baghery, Noah Knapen, Georgio Nicolas, Mahdi Rahimi
* [Permalink](https://eprint.iacr.org/2025/576)
* [Download](https://eprint.iacr.org/2025/576.pdf)

### Abstract

Conventional Publicly Verifiable Secret Sharing (PVSS) protocols allow a dealer to share a secret among $n$ parties without interaction, ensuring that any $t + 1$ parties (where $t+1 \le n$) can recover the secret, while anyone can publicly verify the validity of both the individual shares and the reconstructed secret. PVSS schemes are shown to be a key tool in a wide range of practical applications. In this paper, we introduce Pre-constructed PVSS (PPVSS), an extension of standard PVSS schemes, highlighting its enhanced utility and efficiency in various protocols. Unlike standard PVSS, PPVSS requires the dealer to publish a commitment or encryption of the main secret and incorporates a novel secret reconstruction method. We show that these refinements make PPVSS more practical and versatile than conventional PVSS schemes.
To build a PPVSS scheme, we first point out that the well-known PVSS scheme by Schoenmakers (CRYPTO'99) and its pairing-based variant presented by Heidarvand and Villar (SAC'08) can be seen as special cases of PPVSS, where the dealer also publishes a commitment to the main secret. However, these protocols are not practical for many applications due to efficiency limitations and are less flexible compared to a standard PPVSS scheme. To address this, we propose a general strategy for transforming a Shamir-based PVSS scheme into a PPVSS scheme. Using this strategy, we construct two practical PPVSS schemes in both the Random Oracle (RO) and plain models, grounded in state-of-the-art PVSS designs. Leveraging the new RO-based PPVSS scheme, we revisit some applications and present more efficient variants. Notably, we propose a new universally verifiable e-voting protocol that improves on the alternative scheme by Schoenmakers (CRYPTO'99), reducing the verification complexity with $m$ voters from $O(n^2m)$ to $O(nm)$ exponentiations--a previously unattainable goal with standard PVSS schemes. Our implementation results demonstrate that both our proposed PPVSS schemes and the new universally verifiable e-voting protocol significantly outperform existing alternatives in terms of efficiency.



## 2025/577

* Title: Making GCM Great Again: Toward Full Security and Longer Nonces
* Authors: Woohyuk Chung, Seongha Hwang, Seongkwang Kim, Byeonghak Lee, Jooyoung Lee
* [Permalink](https://eprint.iacr.org/2025/577)
* [Download](https://eprint.iacr.org/2025/577.pdf)

### Abstract

The GCM authenticated encryption (AE) scheme is one of the most widely used AE schemes in the world, while it suffers from risk of nonce misuse, short message length per encryption and an insufficient level of security. The goal of this paper is to design new AE schemes achieving stronger provable security in the standard model and accepting longer nonces (or providing nonce misuse resistance), with the design rationale behind GCM.

As a result, we propose two enhanced variants of GCM and GCM-SIV, dubbed eGCM and eGCM-SIV, respectively. eGCM and eGCM-SIV are built on top of a new CENC-type encryption mode, dubbed eCTR: using 2n-bit counters, eCTR enjoys beyond-birthday-bound security without significant loss of efficiency. eCTR is combined with an almost uniform and almost universal hash function, yielding a variable input-length variable output-length pseudorandom function, dubbed HteC.. GCM and GCM-SIV are constructed using eCTR and HteC as building blocks.

eGCM and eGCM-SIV accept nonces of arbitrary length, and provide almost the full security (namely, n-bit security when they are based on an n-bit block cipher) for a constant maximum input length, under the assumption that the underlying block cipher is a pseudorandom permutation (PRP). Their efficiency is also comparable to GCM in terms of the rate and the overall speed.



## 2025/578

* Title: Efficient Garbled Pseudorandom Functions and Lookup Tables from Minimal Assumption
* Authors: Wei-Kai Lin, Zhenghao Lu, Hong-Sheng Zhou
* [Permalink](https://eprint.iacr.org/2025/578)
* [Download](https://eprint.iacr.org/2025/578.pdf)

### Abstract

Yao's garbled circuits have received huge attention in both theory and practice. While garbled circuits can be constructed using minimal assumption (i.e., the existence of pseudorandom functions or one-way functions), the state-of-the-art constructions (e.g., Rosulek-Roy, Crypto 2021) are based on stronger assumptions. In particular, the ``Free-XOR'' technique (Kolesnikov-Schneider, ICALP 2008) is essential in these state-of-the-art constructions, and their security can only be proven in the random oracle model, or rely on the ``circular-correlation robust hash'' assumption. 

In this paper, we aim to develop new techniques to construct efficient garbling schemes using minimal assumptions. Instead of generically replacing the Free-XOR technique, we focus on garbling schemes for specific functionalities. We successfully eliminated the need for Free-XOR in several state-of-the-art schemes, including the one-hot garbling (Heath and Kolesnikov, CCS 2021) and the garbled pseudorandom functions, and the garbled lookup tables (Heath, Kolesnikov and Ng, Eurocrypt 2024). Our schemes are based on minimal assumptions, i.e., standard pseudorandom functions (PRFs)---we resolved the need for circular security. The performance of our scheme is almost as efficient as the best results except for a small constant factor. Namely, for any lookup table $\{0,1\}^n \to \{0,1\}^m$, our scheme takes $n + (5n+9)m\lambda + 2^n \cdot m$ bits of communication, where $\lambda$ is the security parameter of PRF.



## 2025/579

* Title: REGKYC: Supporting Privacy and Compliance Enforcement for KYC in Blockchains
* Authors: Xihan Xiong, Michael Huth, William Knottenbelt
* [Permalink](https://eprint.iacr.org/2025/579)
* [Download](https://eprint.iacr.org/2025/579.pdf)

### Abstract

Know Your Customer (KYC) is a core component of the Anti-Money Laundering (AML) framework, designed to prevent illicit activities within financial systems.. However, enforcing KYC and AML on blockchains remains challenging due to difficulties in establishing accountability and preserving user privacy. This study proposes REGKYC, a privacy-preserving Attribute-Based Access Control (ABAC) framework that balances user privacy with externally mandated KYC and AML requirements. REGKYC leverages a structured ABAC model to support the flexible verification of KYC attributes and the enforcement of compliance policies, providing benefits to multiple stakeholders. First, it enables legitimate users to meet compliance requirements while preserving the privacy of their on-chain activities. Second, it empowers Crypto-asset Service Providers (CASPs) to tailor compliance policies to operational needs, ensuring adaptability to evolving regulations. Finally, it enhances regulatory accountability by enabling authorized deanonymization of malicious actors. We hope this work inspires future research to harmonize user privacy and regulatory compliance in blockchain systems.



## 2025/580

* Title: Efficient Revocable Identity-Based Encryption from Middle-Product LWE
* Authors: Takumi Nishimura, Atsushi Takayasu
* [Permalink](https://eprint.iacr.org/2025/580)
* [Download](https://eprint.iacr.org/2025/580.pdf)

### Abstract

The Middle-Product Learning with Errors (MPLWE) assumption is a variant of the Learning with Errors (LWE) assumption. The MPLWE assumption reduces the key size of corresponding LWE-based schemes by setting keys as sets of polynomials. Moreover, MPLWE has more robust security than other LWE variants such as Ring-LWE
and Module-LWE. Lombardi et al. proposed an identity-based encryption (IBE) scheme (LVV-IBE) based on the MPLWE assumption in the random oracle model (ROM) by following Gentry et al.'s IBE scheme (GPV-IBE) based on LWE. Due to the benefit of MPLWE, LVV-IBE has a shorter master public key and a secret key than GPV-IBE without changing the size of a ciphertext. However, Lombardi et al..'s proof is not tight in the ROM, while Katsumata et al. proved that GPV-IBE achieves tight adaptive anonymity in the quantum ROM (QROM). Revocable IBE (RIBE) is a variant of IBE supporting a key revocation mechanism to remove malicious users from the system. Takayasu proposed the most efficient RIBE scheme (Takayasu-RIBE) based on LWE achieving tight adaptive anonymity in the QROM.. Although a concrete RIBE scheme based on MPLWE has not been proposed, we can construct a scheme (LVV-based RIBE) by applying Ma and Lin's generic transformation to LVV-IBE. Due to the benefit of MPLWE, LVV-based RIBE has an asymptotically shorter master public key and a shorter secret key than Takayasu-RIBE although the former has a larger ciphertext than the latter. Moreover, the security proof is not tight and anonymous in the ROM due to security proofs of Ma-Lin and Lombardi et al. In this paper, we propose a concrete RIBE scheme based on MPLWE. Compared with the above RIBE schemes, the proposed RIBE scheme is the most asymptotically efficient since the sizes of a master public key and a secret key (resp. ciphertext) of the proposed scheme are the same as those of LVV-based RIBE scheme (resp. Takayasu-RIBE). Moreover, we prove the tight adaptive anonymity of the proposed RIBE scheme in the QROM. For this purpose, we also prove the tight adaptive anonymity of LVV-IBE in the QROM.



## 2025/581

* Title: Reusable Dynamic Multi-Party Homomorphic Encryption
* Authors: Jung Hee Cheon, Hyeongmin Choe, Seunghong Kim, Yongdong Yeo
* [Permalink](https://eprint.iacr.org/2025/581)
* [Download](https://eprint.iacr.org/2025/581.pdf)

### Abstract

Homomorphic Encryption (HE) is a promising primitive for evaluating arbitrary circuits while keeping the user's privacy. We investigate how to use HE in the multi-party setting where data is encrypted with several distinct keys. One may use the Multi-Key Homomorphic Encryption (MKHE) in this setting, but it has space/computation overhead of $\mathcal O(n)$ for the number of users $n$, which makes it impractical when $n$ grows large. On the contrary, Multi-Party Homomorphic Encryption (MPHE) is the other Homomorphic Encryption primitive in the multi-party setting, where the space/computation overhead is $\mathcal O(1)$; however, is limited in terms of ciphertext reusability and dynamicity, that ciphertexts are encrypted just for a group of parties and cannot be reused for other purposes, and that additional parties cannot join the computation dynamically.

Contrary to MKHE, where the secret key owners engage only in the decryption phase, we consider a more relaxed situation where the secret key owners can communicate before the computation. In that case, we can reduce the size of a ciphertext and the evaluation complexity from $\mathcal O(n)$ to $\mathcal O(1)$ as in a single-key HE setting. We call this primitive as {\em Reusable Dynamic Multi-Party Homomorphic Encryption}, which is more suitable in real-world scenarios.

We show that 1) the procedures before the computation can be done in a very few rounds of communications, 2) the evaluation/space complexities are independent of the number of users, and 3) the functionalities are as efficient as MKHE, with asymptotic analysis and with implementation.



## 2025/582

* Title: Release the Power of Rejected Signatures: An Efficient Side-Channel Attack on Dilithium
* Authors: Zheng Liu, An Wang, Congming Wei, Yaoling Ding, Jingqi Zhang, Annyu Liu, Liehuang Zhu
* [Permalink](https://eprint.iacr.org/2025/582)
* [Download](https://eprint.iacr.org/2025/582.pdf)

### Abstract

The Module-Lattice-Based Digital Signature Standard (ML-DSA), formerly known as CRYSTALS-Dilithium, is a lattice-based post-quantum cryptographic scheme. In August 2024, the National Institute of Standards and Technology (NIST) officially standardized ML-DSA under FIPS 204. Dilithium generates one valid signature and multiple rejected signatures during the signing process. Most Side-Channel Attacks targeting Dilithium have focused solely on the valid signature, while neglecting the hints contained in rejected signatures. In this paper, we propose a method for recovering the private key by simultaneously leveraging side-channel leakages from both valid signatures and rejected signatures. This approach minimizes the number of signing attempts required for full key recovery. We construct a factor graph incorporating all relevant side-channel leakages and apply the Belief Propagation (BP) algorithm for private key recovery.

We conducted a proof-of-concept experiment on a Cortex M4 core chip, where the results demonstrate that utilizing rejected signatures reduces the required number of traces by at least $42\%$ for full key recovery. A minimum of a single trace can recover the private key with a success rate of $30\%$. Our findings highlight that protecting rejected signatures is crucial, as their leakage provides valuable side-channel information. We strongly recommend implementing countermeasures for rejected signatures during the signing process to mitigate potential threats.



## 2025/583

* Title: Counter Galois Onion (CGO) for Tor: Fast Non-Malleable Onion Encryption
* Authors: Jean Paul Degabriele, Alessandro Melloni, Jean-Pierre Münch, Martijn Stam
* [Permalink](https://eprint.iacr.org/2025/583)
* [Download](https://eprint.iacr.org/2025/583.pdf)

### Abstract

In 2012, the Tor project expressed the need to upgrade Tor's onion encryption scheme to protect against tagging attacks and thereby strengthen its end-to-end integrity protection. Tor proposal 261, where each encryption layer is processed by a strongly secure, yet relatively expensive tweakable wide-block cipher, is the only concrete candidate replacement to be backed by formal, yet partial, security proofs (Degabriele and Stam, EUROCRYPT 2018, and Rogaway and Zhang, PoPETS 2018).

We propose an alternative onion encryption scheme, called Counter Galois Onion (CGO), that follows a minimalistic, modular design and includes several improvements over proposal 261. CGO's underlying primitive is an updatable tweakable split-domain cipher accompanied with a new security notion, that augments the recently introduced rugged pseudorandom permutation (Degabriele and Karadžić, CRYPTO 2022). Thus, we relax the security compared to a tweakable wide-block cipher, allowing for more efficient designs. We suggest a concrete instantiation for the updatable tweakable split-domain cipher and report on our experiments comparing the performance of CGO with Tor's existing onion encryption scheme.



## 2025/584

* Title: The Singularity Random Number Generator: Bridging Determinism and Unpredictability to Redefine Randomness, Secure Systems, and Adaptive Intelligence
* Authors: S. P. Prahlad
* [Permalink](https://eprint.iacr.org/2025/584)
* [Download](https://eprint.iacr.org/2025/584.pdf)

### Abstract

Abstract
The Singularity Random Number Generator (SRNG) represents a groundbreaking advancement in the generation of random numbers by integrating two key properties - computational irreducibility and seed independence - into a deterministic algorithm. Unlike conventional pseudorandom number generators (PRNGs) whose randomness is intrinsically linked to seed quality or chaotic sensitivity, SRNG transforms even low-entropy seeds into complex, unpredictable outputs. SRNG demonstrates high-quality randomness can emerge independently of seed entropy or size. This paper explores how SRNG not only challenges classical paradigms of predictability in deterministic systems but also offers transformative applications in cryptography, artificial intelligence (AI), and interdisciplinary research. Furthermore, by drawing parallels with cognitive variability research - such as insights from the Forbes article “Why A ‘Productively Distracted’ Brain Is A Superpower” - we discuss how the emergent unpredictability of SRNG may contribute to enhanced adaptive learning and decision-making processes in AI systems. Ultimately, SRNG is presented as a model that bridges the realms of science and mystery, inviting a new understanding of randomness and the limits of scientific inquiry, thereby expanding the frontiers of interdisciplinary research.



## 2025/585

* Title: Adaptively-Secure Big-Key Identity-Based Encryption
* Authors: Jeffrey Champion, Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2025/585)
* [Download](https://eprint.iacr.org/2025/585.pdf)

### Abstract

Key-exfiltration attacks on cryptographic keys are a significant threat to computer security. One proposed defense against such attacks is big-key cryptography which seeks to make cryptographic secrets so large that it is infeasible for an adversary to exfiltrate the key (without being detected). However, this also introduces an inconvenience to the user who must now store the large key on all of their different devices. The work of Döttling, Garg, Sekar and Wang (TCC 2022) introduces an elegant solution to this problem in the form of big-key identity-based encryption (IBE). Here, there is a large master secret key, but very short identity keys. The user can now store the large master secret key as her long-term key, and can provision each of her devices with short ephemeral identity keys (say, corresponding to the current date). In this way, the long-term secret key is protected by conventional big-key cryptography, while the user only needs to distribute short ephemeral keys to their different devices. Döttling et al. introduce and construct big-key IBE from standard pairing-based assumptions. However, their scheme only satisfies selective security where the adversary has to declare its challenge set of identities at the beginning of the security game. The more natural notion of security is adaptive security where the user can adaptively choose which identities it wants to challenge after seeing the public parameters (and part of the master secret key).

In this work, we give the first adaptively-secure construction of big-key IBE from standard cryptographic assumptions. Our first construction relies on indistinguishability obfuscation (and one-way functions), while our second construction relies on witness encryption for NP together with standard pairing-based assumptions (i.e., the SXDH assumption). To prove adaptive security, we show how to implement the classic dual-system methodology with indistinguishability obfuscation as well as witness encryption.



## 2025/586

* Title: Heuristic Algorithm for Solving Restricted SVP and its Applications
* Authors: Geng Wang, Wenwen Xia, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/586)
* [Download](https://eprint.iacr.org/2025/586.pdf)

### Abstract

In lattice-based cryptography, many attacks are performed by finding a short enough vector on a specific lattice. However, it is possible that length is not the only restriction on the vector to be found. A typical example is SVP with infinity norm: since most SVP solving algorithms only aim to find short vector under Euclidean norm, the infinity norm is in fact another restriction on the vector. In the literature, such problems are usually solved by performing exhaustive search on a list of short vectors generated from lattice sieving. However, the sieving list might either be too large or too small to pass the additional restriction, which makes the solving algorithm inefficient in some cases.

Our contribution in this work is as follows: (1) We formally define a new lattice hard problem called restricted SVP, and show that it can be used to generalize many lattice hard problems, including SVP with non-Euclidean norm and Kannan's embedding on approximate CVP. (2) We extend the dimension for free technique and the enumerate-then-slice technique into approximate SVP where the goal is to output a list of short vectors with a certain size. (3) We give the heuristic algorithm for solving restricted SVP, and design a hardness estimator for this algorithm, which can be used to estimate the concrete hardness of signature forgery in Dilithium and other lattice-based signatures. Using this estimator, we present a concrete security analysis for Dilithium against signature forgery under the gate-count model for the first time. Our estimation matches well with the security estimation from core-SVP model in the document of Dilithium, and we also combine our estimator with the rescaling technique to generate a tighter estimation.



## 2025/587

* Title: Lifeboats on the Titanic Cryptography
* Authors: Gideon Samid
* [Permalink](https://eprint.iacr.org/2025/587)
* [Download](https://eprint.iacr.org/2025/587.pdf)

### Abstract

The Titanic was the ship that "could not sink," fortunately its designers installed lifeboats (not enough) despite having no logical grounding for this waste of space and material. It was out of respect for unforeseen surprises. NIST-Post Quantum Ciphers represent the best and the brightest in world crypto intelligence. They are certified as good for their purpose. And likely so, alas, not surely so. If we could find a crypto equivalent for the Titanic Lifeboats, should not we load them up for our journey? Indeed, pattern-devoid cryptography is the crypto equivalent of the lifeboats that mitigated the Titanic disaster. Pattern-Devoid cryptography (PDC) may be deemed inelegant, inconvenient, and bloated, but it will hold up against quantum computers more powerful than expected, and more importantly, it will hold up against adversarial mathematical talent greater than expected. Which is why we should put up with its negatives, and install it just in case the Titanic story repeats itself in cyberspace. This article elaborates on this proposition.



## 2025/588

* Title: A Place for Everyone vs Everyone in its Place: Measuring and Attacking the Ethereum Global Network
* Authors: Chenyu Li, Ren Zhang, Xiaorui Gong
* [Permalink](https://eprint.iacr.org/2025/588)
* [Download](https://eprint.iacr.org/2025/588.pdf)

### Abstract

The Ethereum Global Network (EGN) is the peer-to-peer (P2P) network underlying Ethereum and thousands of subsequent blockchain services. Deviating from traditional single-service P2P networks, EGN's multi-service architecture has gained widespread acceptance for supposedly improving node discovery efficiency and security. This paper challenges this belief by critically examining EGN's design and its purported benefits. Our analysis reveals significant shortcomings in EGN's node discovery process. EGN nodes struggle to connect with peers offering the desired service: over three-quarters of connection attempts reach nodes of other services. In an extreme case, one node spent an average of $45\,908$ connection attempts to find each neighbor. Moreover, this blended architecture compromises EGN's security. The network demonstrates high susceptibility to DHT pollution and partition attacks. Even with only $300$ malicious nodes in EGN, an attacker can isolate thousands of nodes, significantly hindering recovery. In contrast, such a small number of malicious nodes has minimal impact on every single-service P2P network. We propose solutions to improve EGN's node discovery efficiency and strengthen its resilience against attacks.



## 2025/589

* Title: Defeating AutoLock: From Simulation to Real-World Cache-Timing Exploits against TrustZone
* Authors: Quentin Forcioli, Sumanta Chaudhuri, Jean-Luc Danger
* [Permalink](https://eprint.iacr.org/2025/589)
* [Download](https://eprint.iacr.org/2025/589.pdf)

### Abstract

In this article, we present for the first time a cross-core Prime+Probe attack on ARM
TrustZone, which bypasses the AutoLock mechanism. We introduce our simulation-
driven methodology based on gem5 for vulnerability analysis. We demonstrate its
utility in reverse engineering a SoC platform in order to study its microarchitectural
behavior (caches, etc.), inside a simulator, in spite of hardware protection. We present
a novel vulnerability analysis technique, which takes into account the cache set
occupancy for targeted victim executable. This proves to be essential in identifying
information leakage in presence of AutoLock. The above tool also identifies the cache
lines leaking a maximum amount of information. A cross-core Prime+Probe attack is
then mounted on these max-leakage cache lines both in simulation for fine-tuning,
and in real hardware. We validate our analysis and attack method on OP-TEE, an
open-source trusted execution environment running on RockPi4 a board based on
RK3399 SoC. More specifically we target the RSA subroutine in the MbedTLS library
used inside OP-TEE. Despite the presence of AutoLock, multiplier obfuscation, and
assuming a cross-core attack, we are able to retrieve 30% of the key bits, which can
later be used in Branch-and-Prune methods to recover the full key.



## 2025/590

* Title: $\mathsf{emGraph}$: Efficient Multiparty Secure Graph Computation
* Authors: Siddharth Kapoor, Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
* [Permalink](https://eprint.iacr.org/2025/590)
* [Download](https://eprint.iacr.org/2025/590.pdf)

### Abstract

Secure graph computation enables computing on graphs while hiding the graph topology as well as the associated node/edge data. This facilitates collaborative analysis among multiple data owners, who may only hold a private partial view of the global graph. Several works address this problem using the technique of secure multiparty computation (MPC) in the presence of 2 or 3 parties. However, when moving to the multiparty setting, as required for collaborative analysis among multiple data owners, these solutions are no longer scalable.. This remains true with respect to the state-of-the-art framework of $\mathsf{Graphiti}$ (Koti et al., CCS 2024) as well. Specifically, $\mathsf{Graphiti}$ incurs a round complexity linear in the number of parties or data owners. This is due to its reliance on secure shuffle protocol, constituting a bottleneck in the multiparty setting. Additionally, $\mathsf{Graphiti}$ has a prohibitively expensive initialisation phase due to its reliance on secure sort, with a round complexity dependent on both the graph size and the number of parties.

We propose $\mathsf{emGraph}$, a generic framework for secure graph computation in the multiparty setting that eliminates the need of shuffle and instead, relies on a weaker primitive known as $\mathsf{Permute+Share}$. Further $\mathsf{emGraph}$ is designed to have a lightweight initialisation, that eliminates the need for sorting, making its round complexity independent of the graph size and number of parties. Unlike any of the prior works, achieving a round complexity independent of the number of parties is what makes $\mathsf{emGraph}$ scalable.

Finally, we implement and benchmark the performance of $\mathsf{emGraph}$ for the application of PageRank computation and showcase its efficiency and scalability improvements over $\mathsf{Graphiti}$. Concretely, we witness improvements of up to $80\times$ in runtime in comparison to state-of-the-art framework $\mathsf{Graphiti}$. Further, we observe that $\mathsf{emGraph}$ takes under a minute to perform 10 iterations of PageRank computation on a graph of size $10^6$ that is distributed among $25$ parties/data owners, making it highly practical for secure graph computation in the multiparty setting.



## 2025/591

* Title: ColliderVM: Stateful Computation on Bitcoin
* Authors: Victor I. Kolobov, Avihu M. Levy, Moni Naor
* [Permalink](https://eprint.iacr.org/2025/591)
* [Download](https://eprint.iacr.org/2025/591.pdf)

### Abstract

Bitcoin script cannot easily access and store state information onchain without an upgrade such as BIP-347 (OP_CAT); this makes performing general (stateful) computation on Bitcoin impossible to do directly. Despite this limitation, several approaches have been proposed to bypass it, with BitVM being by far the most production-ready of them. BitVM enables fraud-proof-based computation on Bitcoin, relying on a $1$-out-of-$n$ honesty assumption.

This left the question of whether it is possible to achieve computation under the same honesty assumption without requiring onlookers to ensure validity through fraud proofs.  In this note, we answer this question affirmatively by introducing ColliderVM, a new approach for performing computation on Bitcoin today. Crucially, this approach eliminates some capital inefficiency concerns stemming from reliance on fraud proofs.

For our construction, a key point is to replace the Lamport or Winternitz signature-based storage component in contemporary protocols with a hash collision-based commitment. With it, we estimate that the Bitcoin script length for STARK proof verification is drastically shorter than that for other pairing-based proof systems used today in applications.



## 2025/592

* Title: DSM: Decentralized State Machine - The Missing Trust Layer of the Internet
* Authors: Brandon Ramsay
* [Permalink](https://eprint.iacr.org/2025/592)
* [Download](https://eprint.iacr.org/2025/592.pdf)

### Abstract

The modern internet relies heavily on centralized trust systems controlled by corporations, governments, and intermediaries to manage authentication, identity, and value transfer. These models introduce fundamental vulnerabilities, including censorship, fraud, and systemic insecurity. The Decentralized State Machine (DSM) addresses these issues by introducing a mathematically enforced trust layer that eliminates the need for consensus mechanisms, third-party validators, and centralized infrastructure. DSM enables quantum-resistant, deterministic state transitions for digital identity and value exchange—offering immediate finality, offline capability, and tamper-proof forward-only state progression.

DSM replaces traditional blockchain execution models with deterministic, pre-committed state transitions, enabling secure, multi-path workflows without requiring Turing-completeness or global consensus. The protocol architecture is based on a straight hash chain with sparse indexing and Sparse Merkle Trees (SMTs), ensuring efficient verification, scalability, and privacy. A bilateral isolation model supports asynchronous, offline operation with built-in consistency guarantees. DSM introduces a sustainable, gas-free economic model based on cryptographic subscription commitments.

This paper outlines the architecture, cryptographic foundations, and security guarantees of DSM, and demonstrates how it achieves verifiable, trustless interaction between peers—both online and offline. By decoupling security from consensus and enabling self-validating state transitions, DSM offers a practical and scalable alternative to conventional internet trust models.



## 2025/593

* Title: Oblivious Immutable Memory
* Authors: Ananya Appan, David Heath
* [Permalink](https://eprint.iacr.org/2025/593)
* [Download](https://eprint.iacr.org/2025/593.pdf)

### Abstract

An oblivious RAM (ORAM) compiler is a cryptographic tool that transforms a program $P$ running in time $n$ into an equivalent program $\tilde P$, with the property that the sequence of memory addresses read from/written to by $\tilde P$ reveal nothing about $\tilde P$'s data (Goldreich and Ostrovsky, JACM'96). An efficient ORAM compiler $C$ should achieve some combination of the following:

- Low bandwidth blow-up: $\tilde P$ should read/write a similar amount of data as does P.
- Low latency: $\tilde P$ should incur a similar number of roundtrips to the memory as does P.
- Low space complexity: $\tilde P$ should run in as few words of local memory as possible.

It is well known that for a generic compiler (i.e. one that works for any RAM program $P$), certain combinations of efficiencies are impossible. Any generic ORAM compiler must incur $\Omega(\log n)$ bandwidth blow-up, and any ORAM compiler with no latency blow-up must incur either $\Omega(\sqrt n)$ bandwidth blow-up and/or local space. Moreover, while a $O(\log n)$ bandwidth blow-up compiler is known, it requires the assumption that one-way functions exist and incurs enormous constant factors.

To circumvent the above problems and improve efficiency of particular ORAM programs, we develop a compiler for a specific class of programs. Let $P$ be a program that interacts with an immutable memory. Namely, $P$ may write values to memory, then read them back, but it cannot change values that were already written. Using only information-theoretic techniques, we compile any such $P$ into an oblivious form $\tilde P$ with a combination of efficiencies that no generic ORAM compiler can achieve:

- $\tilde P$ incurs $\Theta(\log n)$ amortized bandwidth blow-up.
- $\tilde P$ incurs $O(1)$ amortized latency blow-up.
- $\tilde P$ runs in $O(\lambda)$ words of local space ($\tilde P$ incurs an error with probability $2^{-\Omega(\lambda)}$).

We show that this, for instance, implies that any pure functional program can be compiled with the same asymptotics.

Our work builds on and is compatible with prior work  (Appan et al., CCS'24) that showed similar results for pointer machine programs that manipulate objects with constant in-degree (i.e., the program may only maintain a constant number of pointers to any one memory cell; our immutable memory approach does not have this limitation). By combining techniques, we can consider programs that interact with a mixed memory that allows each memory cell to be updated until it is frozen, after which it becomes immutable, allowing further reads to be compiled with the above asymptotics, even when in-degree is high. Many useful algorithms/data structures can be naturally implemented as mixed memory programs, including suffix trees (powerful data structures used in computational biology) and deterministic finite automata (DFAs).



## 2025/594

* Title: Efficient SNARKs for Boolean Circuits via Sumcheck over Tower Fields
* Authors: Tianyi Liu, Yupeng Zhang
* [Permalink](https://eprint.iacr.org/2025/594)
* [Download](https://eprint.iacr.org/2025/594.pdf)

### Abstract

In this paper, we present efficient SNARKs for Boolean circuits, achieving significant improvements in the prover efficiency. The core of our technique is a novel tower sumcheck protocol and a tower zero-check protocol tailored for tower fields, which enable this efficiency boost. When instantiated with Wiedemann's binary tower fields with the base field of $GF(2)$ and the top-level field $GF(2^{2^\ell})$, assuming the quadratic complexity of multiplications \(O(2^{2\ell})\) in the top-level field with $2^\ell$ bits, the prover time of our sumcheck protocol is \(O(2^{1.5\ell}N)\). It is faster than the standard sumcheck protocol over the large field with the complexity of \(O(2^{2\ell}N)\). To achieve a reasonable security level, $2^\ell$ is usually set to $128$.

Leveraging this advancement, we improve the efficiency of IOP protocols over the binary or small characteristic fields for Plonkish, CCS, and GKR-based constraint systems. Moreover, to further improve the prover efficiency of the SNARKs, we introduce a basis-switching mechanism that efficiently transforms polynomial evaluations on the base-field polynomial to evaluations on the tower-field polynomial. With the basis-switching, we are able to compile the binary-field IOPs to SNARKs using large-field polynomial commitment schemes (PCS) that batch the witness over the base field. The size of the large-field PCS is only $\frac{1}{2^\ell}$ of the size of the witness over the base field. Combining the IOP and the PCS, the overall prover time of our SNARKs for Boolean circuits significantly faster than the naive approach of encoding Boolean values in a large field.



## 2025/595

* Title: Partial Key Exposure Attacks on UOV and Its Variants
* Authors: Yuki Seto, Hiroki Furue, Atsushi Takayasu
* [Permalink](https://eprint.iacr.org/2025/595)
* [Download](https://eprint.iacr.org/2025/595.pdf)

### Abstract

In CRYPTO 2022, Esser et al. proposed a partial key exposure attack on several post-quantum cryptographic schemes including Rainbow which is a variant of UOV. The task of the attack is to recover a full secret key from its partial information such as a secret key with symmetric/asymmetric bit errors. One of the techniques Esser et al. developed is a partial enumeration that combines the standard algorithms to solve the MQ problem with enumeration.

Although an efficient attack on Rainbow was proposed, UOV and its variants have still been paid much attention since UOV and its three variants, i.e., MAYO, QR-UOV and SNOVA, were selected as the Round 2 candidates of the additional call for digital signature schemes proposal by NIST.

In this paper, we analyze partial key exposure attacks on UOV, MAYO, and QR-UOV. Although our proposed attacks use the partial enumeration, we refine their enumeration strategy. We employ two enumeration strategies and analyze the complexity of the proposed attacks. Then, we find a structural difference between UOV and its variants to resist partial enumeration. Specifically, the partial enumeration is effective if the number of vinegar variables is smaller than the number of equations and the order of a finite field is small.

As a result, the proposed attack is the most effective on MAYO. While our attacks on UOV and QR-UOV are effective only when the symmetric error probabilities are 0.11 and 0.05, respectively, that on MAYO is effective even when the probability is close to 0.5.



## 2025/596

* Title: Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem
* Authors: Alain Couvreur, Christophe Levrat
* [Permalink](https://eprint.iacr.org/2025/596)
* [Download](https://eprint.iacr.org/2025/596.pdf)

### Abstract

The matrix code equivalence problem consists, given two matrix spaces $\mathcal{C},\mathcal{D}\subset \mathbb{F}_q^{m\times n}$ of dimension $k$, in finding invertible matrices $P\in\textrm{GL}_m(\mathbb{F}_q)$ and $Q\in\textrm{GL}_n(\mathbb{F}_q)$ such that $\mathcal{D} =P\mathcal{C} Q^{-1}$. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Naranayan et. al. recently published an algorithm solving this problem in the case $k = n =m$ in $\widetilde{\mathcal{O}}(q^{\frac k 2})$ operations. We present a different algorithm which solves the problem in the general case. Our approach consists in reducing the problem to the matrix code conjugacy problem, i.e. the case $P=Q$. For the latter problem, similarly to the permutation code equivalence problem in Hamming metric, a natural invariant based on the \emph{Hull} of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For $k=m=n$, our algorithm achieves the same complexity as in the aforementioned reference. However, it extends to a much broader range of parameters.



## 2025/597

* Title: SoK: Self-Generated Nudes over Private Chats: How Can Technology Contribute to a Safer Sexting?
* Authors: Joel Samper, Bernardo Ferreira
* [Permalink](https://eprint.iacr.org/2025/597)
* [Download](https://eprint.iacr.org/2025/597.pdf)

### Abstract

More and more people take advantage of mobile apps to strike up relationships and casual contacts. This sometimes results in the sharing of self-generated nudes. While this opens a way for sexual exploration, it also raises concerns. In this paper, we review existing technology-assisted permissive proposals/features that provide security or privacy benefits when sharing nudes online.. To do so, we performed a systematic literature review combing through 10,026 search results and cross-references, and we identified real-world solutions by surveying OS features and 52 dating, messaging and social network apps. We systematized knowledge by defining a sexting threat model, deriving a taxonomy of the proposals/features, discussing some of their shortcomings, organizing privacy-related concepts, and providing take-aways with some directions for future research and development. Our study found a very diverse ecosystem of academic proposals and app features, showing that safer sexting goes far beyond nude detection. None of the techniques represents the ultimate solution for all threats, but each contributes to safer sexting in a different way.



## 2025/598

* Title: Nominal State-Separating Proofs
* Authors: Markus Krabbe Larsen, Carsten Schürmann
* [Permalink](https://eprint.iacr.org/2025/598)
* [Download](https://eprint.iacr.org/2025/598.pdf)

### Abstract

State-separting proofs are a powerful tool to structure cryptographic arguments, so that they are amenable for mechanization, as has been shown through implementations, such as SSProve. However, the treatment of separation for heaps has never been satisfactorily addressed. In this work, we present the first comprehensive treatment of nominal state separation in state-separating proofs using nominal sets. We provide a Coq library, called Nominal-SSProve, that builds on nominal state separation supporting mechanized proofs that appear more concise and arguably more elegant.



## 2025/599

* Title: Insecurity of One Decentralized Attribute-based Signature Scheme for Social Co-governance
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2025/599)
* [Download](https://eprint.iacr.org/2025/599.pdf)

### Abstract

We show that the attribute-based signature scheme [Information Sciences, 654(2024), 119839] is insecure,  because an adversary can generate valid signatures for any message even though he cannot access the signer's secret key.  The four components of signature $\{\delta_1, \delta_2, \delta_3, \delta_4\}$ are not tightly bound to the target message $M$ and the signer's public key. The dependency between the signer's public key and secret key is not properly used to construct any intractable problem. The inherent flaw results in that the  adversary can find an efficient signing algorithm functionally equivalent to the valid signing algorithm.



## 2025/600

* Title: Improved Round-by-round Soundness IOPs via  Reed-Muller Codes
* Authors: Dor Minzer, Kai Zhe Zheng
* [Permalink](https://eprint.iacr.org/2025/600)
* [Download](https://eprint.iacr.org/2025/600.pdf)

### Abstract

We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves  the best known query complexity in some range of security parameters. Specifically, for degree $d$ and security parameter $\lambda\leq \frac{\log^2 d}{\log\log d}$  , our IOPP has $2^{-\lambda}$ round-by-round soundness, $O(\lambda)$ queries, $O(\log\log d)$ rounds and $O(d)$ length. This improves upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, that have larger query and round complexity standing at $O(\lambda \log d)$ and  $O(\log d+\lambda\log\log d)$ respectively. We use our IOPP to give an IOP for the NP-complete language Rank-1-Constraint-Satisfaction with the same parameters.

    Our construction is based on the line versus point test in the low-soundness regime. Compared to the axis parallel test (which is used in all prior works), the general affine lines test has improved soundness, which is the main source of our improved soundness. 
   
    Using this test involves several complications, most significantly that projection to affine lines does not preserve individual degrees, and we show how to overcome these difficulties. En route, we extend some existing machinery to more general settings. Specifically, we give proximity generators for Reed-Muller codes, show a more systematic way of handling "side conditions" in IOP constructions, and generalize the compiling procedure of [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] to general codes.



## 2025/601

* Title: PHOENIX: Crypto-Agile Hardware Sharing for ML-KEM and HQC
* Authors: Antonio Ras, Antoine Loiseau, Mikaël Carmona, Simon Pontié, Guénaël Renault, Benjamin Smith, Emanuele Valea
* [Permalink](https://eprint.iacr.org/2025/601)
* [Download](https://eprint.iacr.org/2025/601.pdf)

### Abstract

The transition to quantum-safe public-key cryptography has begun: for key agreement, NIST has standardized ML-KEM and selected HQC for future standardization. The relative immaturity of these schemes encourages crypto-agile implementations, to facilitate easy transitions between them. Intelligent crypto-agility requires efficient sharing strategies to compute operations from different cryptosystems using the same resources. This is particularly challenging for cryptosystems with distinct mathematical foundations, like lattice-based ML-KEM and code-based HQC.
We introduce PHOENIX, the first crypto-agile hardware coprocessor for lattice- and code-based cryptosystems--specifically, ML-KEM and HQC, at all three NIST security levels--with an effective agile sharing strategy.
PHOENIX accelerates polynomial multiplication, which is the main operation in both cryptosystems, and the current bottleneck of HQC. To maximise sharing, we replace HQC's Karatsuba-based polynomial multiplication with the Frobenius Additive FFT (FAFFT), which is similar on an abstract level to ML-KEM's Number Theoretic Transform (NTT).
We show that the FAFFT already brings substantial performance improvements in software. In hardware, our sharing strategy for the FAFFT and NTT is based on a new SuperButterfly unit that seamlessly switches between these two FFT variants over completely different rings. This is, to our knowledge, the first FAFFT hardware accelerator of any kind. We have integrated PHOENIX in a real System-on-Chip FPGA scenario, where our performance measurements show that efficient crypto-agility for lattice- and code-based KEMs can be achieved with low overhead.



## 2025/602

* Title: Lattice-Based Sanitizable Signature Schemes: Chameleon Hash Functions and More
* Authors: Sebastian Clermont, Samed Düzlü, Christian Janson, Laurens Porzenheim, Patrick Struck
* [Permalink](https://eprint.iacr.org/2025/602)
* [Download](https://eprint.iacr.org/2025/602.pdf)

### Abstract

Sanitizable Signature Schemes (SSS) enable a designated party, the sanitizer, to modify predefined parts of a signed message without invalidating the signature, making them useful for applications like pseudonymization and redaction. Since their introduction by Ateniese et al. (ESORICS'05), several classical SSS constructions have been proposed, but none have been instantiated from quantum-resistant assumptions. In this work, we develop the first quantum-secure sanitizable signature schemes based on lattice assumptions. Our primary focus is on SSS constructions that rely on chameleon hash functions (CHFs), a key component for enabling the controlled modification of messages. While lattice-based CHFs exist, they do not meet the required security guarantees for SSS, becoming insecure under adversarial access to an adapt oracle. To address this, we construct a novel lattice-based CHF that achieves collision resistance even in such settings, called full collision resistance. However, our CHF lacks the uniqueness property, a limitation we show to be inherent in lattice-based CHFs. As a result, our SSS constructions initially fall short of achieving the critical security property of accountability. To overcome this, we apply a transformation based on verifiable ring signatures (VRS), for which we present the first lattice-based instantiation. Additionally, we provide a comprehensive analysis of existing classical SSS constructions, explore their potential for post-quantum instantiations, and present new attacks on previously assumed secure SSS schemes. Our work closes the gap in constructing quantum-secure SSS and lays the groundwork for further research into advanced cryptographic primitives based on lattice assumptions.



## 2025/603

* Title: Mobile Byzantine Agreement in a Trusted World
* Authors: Bo Pan, Maria Potop Butucaru
* [Permalink](https://eprint.iacr.org/2025/603)
* [Download](https://eprint.iacr.org/2025/603.pdf)

### Abstract

In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host.
We focus on three representative models: \emph{Garay's}, \emph{Bonnet's} and \emph{Buhrman's} models.
In \emph{Garay's model} when a process has been left by the Byzantine, it is in the \emph{cured} state and it is aware of its condition and thus can remain silent for a round to prevent the dissemination of wrong information.
In \emph{Bonnet's model} a cured process may send messages (based on a state corrupted by the malicious agent), however it will behave correctly in the way it sends those messages: i.e., send messages according to the algorithm.
In \emph{Buhrman's model} Byzantine agents move together with the message. 
It has been shown that in order to solve Byzantine Agreement in the \emph{Garay's model} at least $4t+1$ processors are needed, for \emph{Bonnet's model} at least $5t+1$ processors are needed, while for \emph{Buhrman's model} at least $3t+1$ processors are needed.
In this paper we target to increase the tolerance to mobile Byzantines by integrating a trusted counter abstraction to the above models. This abstraction prevents nodes to equivocate. In the new models we prove that at least $3t+1$, respectively $4t+1$, and $2t+1$ processors are needed  to tolerate $t$ mobile Byzantine agents. Furthermore,  we propose novel Mobile Byzantine Agreement algorithms that  match these new lower bounds for \emph{Garay's}, \emph{Bonnet's} and \emph{Buhrman's} models.



## 2025/604

* Title: On the success rate of simple side-channel attacks against masking with unlimited attack traces
* Authors: Aymeric Hiltenbrand, Julien Eynard, Romain Poussier
* [Permalink](https://eprint.iacr.org/2025/604)
* [Download](https://eprint.iacr.org/2025/604.pdf)

### Abstract

Side-channel attacks following a classical differential power
analysis (DPA) style are well understood, along with the effect the mask-
ing countermeasure has on them. However, simple attacks (SPA) where
the target variable does not vary thanks to a known value, such as the
plaintext, are less studied. In this paper, we investigate how the masking
countermeasure affects the success rate of simple attacks. To this end, we
provide theoretical, simulated, and practical experiments. Interestingly,
we will see that masking can allow us to asymptotically recover more
information on the secret than in the case of an unprotected implemen-
tation, depending on the masking type. We will see that this is true for
masking encodings that add non-linearity with respect to the leakages,
such as arithmetic masking, while it is not for Boolean masking. We be-
lieve this context provides interesting results, as the average information
of arithmetic encoding is proven less informative than the Boolean one.