From Newsgroup: sci.crypt

## In this issue
1. [2025/442] A Unified Framework for Succinct Garbling from ...
2. [2025/620] Need for zkSpeed: Accelerating HyperPlonk for Zero- ...
3. [2025/864] Fheanor: a new, modular FHE library for designing ...
4. [2025/1413] When Can We Incrementally Prove Computations of ...
5. [2025/1414] Data Availability Sampling with Repair
6. [2025/1415] Quantum Implementation of SHA-1
7. [2025/1416] A Note on the Binding Properties of KEM Combiners
8. [2025/1417] A Note on the Post-Quantum Security of the Inverse ...
9. [2025/1418] Note: Shared Key Recovery Attack on Cascader Key ...
10. [2025/1419] BEAST-MEV: Batched Threshold Encryption with Silent ...
11. [2025/1420] Coral: Fast Succinct Non-Interactive Zero-Knowledge ...
12. [2025/1421] Efficient randomized strong $2$-source non- ...
13. [2025/1422] Design ZK-NR: A Post-Quantum Layered Protocol for ...
14. [2025/1423] Collusion-Safe Proxy Re-Encryption
15. [2025/1424] LESS is Even More: Optimizing Digital Signatures ...
16. [2025/1425] Lodia: Towards Optimal Sparse Matrix-Vector ...
17. [2025/1426] (Im)Possibility of Symmetric Encryption against ...
18. [2025/1427] End-to-End Non-Profiled Side-Channel Analysis on ...
19. [2025/1428] Strategic Mining in Proof-of-Stake with Practical ...
20. [2025/1429] Public-Key Encryption and Injective Trapdoor ...
21. [2025/1430] Practical Collision Attacks on Reduced-Round ...
22. [2025/1431] Multi-Partner Project: Securing Future Edge-AI ...
23. [2025/1432] Brauer and certain class of Hansen chain are closed ...
24. [2025/1433] A Fully-Adaptive Threshold Partially-Oblivious PRF
25. [2025/1434] TLShare: Private Authenticated MPC and FHE Inputs ...
26. [2025/1435] Weak Keys in QC-MDPC-based cryptosystems via the ...
27. [2025/1436] VOLE-in-the-Head Signatures Based on the Linear ...
28. [2025/1437] GURKE: Group Unidirectional Ratcheted Key Exchange
29. [2025/1438] Secure Protocols for Best Arm Identification Using ...
30. [2025/1439] A Note on the Post-Quantum Security of Identity- ...
31. [2025/1440] Faster Homomorphic Integer Computer
32. [2025/1441] DIMSEPP: A Decentralized Identity Management System ...
33. [2025/1442] Shuffling is Universal: Statistical Additive ...
## 2025/442
* Title: A Unified Framework for Succinct Garbling from Homomorphic Secret Sharing
* Authors: Yuval Ishai, Hanjun Li, Huijia Lin
* [Permalink](https://eprint.iacr.org/2025/442)
* [Download](https://eprint.iacr.org/2025/442.pdf)
### Abstract
A major challenge in cryptography is the construction of succinct garbling schemes that have asymptotically smaller size than YaorCOs garbled circuit construction. We present a new framework for succinct garbling that replaces the heavy machinery of most previous constructions by lighter-weight homomorphic secret sharing techniques.
Concretely, we achieve 1-bit-per-gate (amortized) garbling size for Boolean circuits under circular variants of standard assumptions in composite-order or prime-order groups, as well as a lattice-based instantiation. We further extend these ideas to layered circuits, improving the per-gate cost below 1 bit, and to arithmetic circuits, eliminating the typical +-(++)-factor overhead for garbling mod-p computations. Our constructions also feature rCLleveledrCY variants that remove circular-security requirements at the cost of adding a depth-dependent term to the garbling size.
Our framework significantly extends a recent technique of Liu, Wang, Yang, and Yu (Eurocrypt 2025) for lattice-based succinct garbling, and opens new avenues toward practical succinct garbling. For moderately large circuits with a few million gates, our garbled circuits can be two orders of magnitude smaller than Yao-style garbling. While our garbling and evaluation algorithms are much slower, they are still practically feasible, unlike previous fully succinct garbling schemes that rely on expensive tools such as iO or a non-black-box combination of FHE and ABE. This trade-off
can make our framework appealing when a garbled circuit is used as a functional ciphertext that is broadcast or stored in multiple locations (e.g., on a blockchain), in which case communication and storage may dominate computational cost.
## 2025/620
* Title: Need for zkSpeed: Accelerating HyperPlonk for Zero-Knowledge Proofs
* Authors: Alhad Daftardar, Jianqiao Mo, Joey Ah-kiow, Benedikt B|+nz, Ramesh Karri, Siddharth Garg, Brandon Reagen
* [Permalink](https://eprint.iacr.org/2025/620)
* [Download](https://eprint.iacr.org/2025/620.pdf)
### Abstract
Zero-Knowledge Proofs (ZKPs) are a rapidly growing technique for privacy-preserving and verifiable computation.
ZKPs enable one party (a prover: $\mathcal{P}$) to prove to another (a verifier: $\mathcal{V}$) that a statement is true or correct without revealing any additional information.
This powerful capability has led to ZKPs being applied and proposed for application in blockchain technologies, verifiable machine learning, and electronic voting.
However, ZKPs have yet to see widespread, ubiquitous adoption due to the exceptionally high computational complexity of the proving process.
Naturally, there has been recent work to accelerate ZKP primitives and protocols using GPUs and ASICs.
However, the protocols considered so far face one of two challenges:
they require a trusted setup for each new application or
generate large proofs with high verification costs, limiting their applicability in scenarios with numerous verifiers or strict verification time constraints.
HyperPlonk is a state-of-the-art ZKP protocol that supports both one-time, universal setup and small proof sizes/verification costs expected by publicly verifiable, consensus-based systems (e.g., blockchain).
While HyperPlonk's setup and verifier properties are highly desirable, the proving phase is costly.
A HyperPlonk prover must compute on large bitwidths (e.g., 255-381b) and polynomials (e.g., of degree 2$^{24}$),
employs computationally (e.g., MSM) and bandwidth (e.g., SumCheck) intensive kernels,
and the complete protocol comprises many steps, each constituting distinct kernels.
We present an accelerator, \emph{zkSpeed}, to address these challenges and effectively accelerate HyperPlonk.
zkSpeed provides hardware support for all major primitives (e.g., SumCheck and Multi-Scalar Multiplications (MSMs)) and judiciously schedules each protocol phase onto the allocated hardware.
We leverage high-level synthesis to thoroughly explore and optimize the hardware design tradeoffs of each unit.
These are then input into a full-chip simulator for large-scale design space exploration to optimize all aspects of the architecture in unison.
Our Pareto analysis demonstrates that with a 366mm$^2$ chip and 2 TB/s of off-chip bandwidth, zkSpeed is able to accelerate the entire proof generation by 801$\times$ (geomean) over a CPU baseline.
## 2025/864
* Title: Fheanor: a new, modular FHE library for designing and optimising schemes
* Authors: Hiroki Okada, Rachel Player, Simon Pohmann
* [Permalink](https://eprint.iacr.org/2025/864)
* [Download](https://eprint.iacr.org/2025/864.pdf)
### Abstract
Implementations of modern FHE schemes are available in various highly-optimized libraries. Many of these libraries are designed to allow developers who may not have deep expertise in FHE to build fast and secure privacy-preserving applications. To support such users, the API of these libraries often hides the internals of the schemes in question from the user. However, this design choice makes it hard for users of these libraries to modify existing schemes, or implement new ones; work that is often valuable when conducting research on FHE schemes.
We present our new Rust library Fheanor, which aims to facilitate such research on FHE schemes. The core target user is an FHE researcher, rather than an application developer. Most importantly, the design of Fheanor is very modular, and mirrors the mathematical structure of the available FHE schemes. By exposing the mathematical structure, but still hiding implementation details, it is easy to modify or extend the functionality of FHE schemes implemented in the library and still preserve high performance. Indeed, Fheanor demonstrates performance that is close to that of HElib or SEAL, with the potential for optimizations in the future.
Fheanor implements several features that have not, or have only rarely, been implemented in previous libraries. These include non-power-of-two cyclotomic rings, single-RNS based ring arithmetic, the CLPX/GBFV scheme, and bootstrapping for BFV and BGV.
In addition, this paper presents new theoretical contributions that are also implemented in Fheanor. The first is an extension of optimal digit extraction circuits, used in BFV/BGV bootstrapping, to the case 2^23. The second is a more efficient algorithm for computing the trace in the non-power-of-two cyclotomic setting.
## 2025/1413
* Title: When Can We Incrementally Prove Computations of Arbitrary Depth?
* Authors: Matteo Campanelli, Dario Fiore, Mahak Pancholi
* [Permalink](https://eprint.iacr.org/2025/1413)
* [Download](https://eprint.iacr.org/2025/1413.pdf)
### Abstract
Incrementally Verifiable Computation (IVC) allows one to prove the correctness of a computation of potentially unbounded length in an incremental way, while a computationally weak client can efficiently check its correctness in time sublinear in the computation's length. IVC is particularly useful in several real-world applications such as scalable blockchains, distributed computation, and verifiable machine learning. Yet, most existing IVC schemes are only provably secure for constant-depth computations. Arguing their security for computations of polynomial depth relies on heuristic assumptions, raising both theoretical and practical concerns.
In this work, we delve into the security foundations of incremental proof systems, addressing two main questions. First, we revisit the security analysis, in the unbounded-depth regime, of the canonical construction of IVC based on the recursive composition of SNARKs. We extend this analysis to include SNARKs that are straightline extractable in the algebraic group model (AGM) and some additional oracle model. As a consequence of our result, we obtain novel instantiations of IVC for unbounded-depth computations based on AGM-based SNARKs, such as Groth16 or Marlin, to name a fewrCoan important class of SNARKs not captured by similar analyses in prior work [Chiesa et al. TCC 2024].
Second, we consider incremental proof systems for arbitrary depth computations in which full-blown extractability is not necessary. We study under what conditions they can be instantiated from the recursive composition of "plain" building blocks (SNARKs, folding, accumulation schemes), that is without requiring special straightline extractability. We introduce incremental functional commitments (incremental FC), a primitive that allows one to commit to a large data $D$ and later prove a function $f(D)$. The key aspect is that both the committing and proving functionalities operate incrementally, processing $D$ in a streaming, piece-by-piece manner. Also, like in standard FCs, their security property is a form of evaluation binding, a notion that is weaker than knowledge-soundness (it states that it is hard to produce two valid proofs for the same commitment and two distinct outputs). Our second main result consists of a construction of incremental FCs based on recursive composition of SNARKs and its security analysis, which shows that arbitrarily deep compositions of primitives with non-straightline extractors do not suffer from inherent security limitations.
## 2025/1414
* Title: Data Availability Sampling with Repair
* Authors: Dan Boneh, Joachim Neu, Valeria Nikolaenko, Aditi Partap
* [Permalink](https://eprint.iacr.org/2025/1414)
* [Download](https://eprint.iacr.org/2025/1414.pdf)
### Abstract
Data availability sampling (DAS) is an important technique to horizontally scale consensus protocols without compromising on the number of adversarial nodes that can be tolerated. DAS is on the technical roadmap of major blockchains such as Ethereum. A major challenge for DAS schemes, that has not been formally studied in the literature, is how incomplete shares can be repaired. The need for repairing data shares motivates key aspects of Ethereum's DAS-based sharding vision called "Danksharding".
In this work, we make two contributions. First, we provide a new definitional framework that formalizes the notion of repair, along with the security guarantees that a DAS scheme must provide. Second, we propose a new DAS scheme designed with efficient repair in mind, based on locally-correctable multiplicity codes. To facilitate using these codes, we introduce a new multivariate polynomial commitment scheme that (i) supports efficient openings of partial derivatives of a committed polynomial, (ii) supports fast batch opening proof generation at many points, and (iii) has an algorithm to recompute (repair) opening proofs at a point from only a few other proofs. The proposed scheme improves upon the state-of-the-art Ethereum Fulu DAS scheme, slated for deployment in late 2025/early 2026, in storage overhead, repair bandwidth and coordination, while only slightly increasing dispersal cost and sampling bandwidth. Our techniques readily carry over to data availability schemes based on verifiable information dispersal (VID).
## 2025/1415
* Title: Quantum Implementation of SHA-1
* Authors: Seyoung Yoon, Gyeongju Song, Kyungbae Jang, Sangmin Cha, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2025/1415)
* [Download](https://eprint.iacr.org/2025/1415.pdf)
### Abstract
As quantum computing technology rapidly advances, threats to existing symmetric-key and public-key cryptosystems are becoming increasingly real. In this study, we implement a SHA-1 quantum circuit that operates efficiently in a quantum computing environment. We optimize the quantum circuit, focusing on minimizing total circuit depth, a key performance indicator of quantum algorithms. The SHA-1 quantum circuit implementation used 985 qubits, resulting in a measured circuit depth of 9,026. Furthermore, by integrating this optimized circuit with the Grover algorithm, we establish the foundation for an efficient quantum attack on the SHA-1 algorithm. This research is significant not only because it presents a resource-efficient SHA-1 quantum implementation but also because it enables accelerated attacks in a quantum computing environment.
## 2025/1416
* Title: A Note on the Binding Properties of KEM Combiners
* Authors: Juliane Kr|nmer, Patrick Struck, Maximiliane Weish|nupl
* [Permalink](https://eprint.iacr.org/2025/1416)
* [Download](https://eprint.iacr.org/2025/1416.pdf)
### Abstract
In this note we analyze the various binding properties of combiners for KEMs. We show that several properties follow easily for the most general combinerrCoassuming a collision-resistant hash functionrCowhile more performance-oriented versions require the respective property from one or both of the underlying KEMs. Other properties are not obtained as directly and require either more properties of one underlying KEM or the respective property from both KEMs.
## 2025/1417
* Title: A Note on the Post-Quantum Security of the Inverse Discrete Logarithm Problem
* Authors: Joshua Limbrey, Andrew Mendelsohn
* [Permalink](https://eprint.iacr.org/2025/1417)
* [Download](https://eprint.iacr.org/2025/1417.pdf)
### Abstract
In Submission 2025/1391 to the IACR Cryptology ePrint Archive, the Inverse Discrete Logarithm Problem (IDLP) is introduced and used to build a key exchange protocol and a KEM. The author claims both classical and post-quantum security for IDLP and therefore for the proposed protocols. It is the purpose of this note to give an efficient quantum algorithm for IDLP, based on the algorithm of Shor. We give an implementation of our algorithm, replacing the use of Shor's algorithm with an oracle.
## 2025/1418
* Title: Note: Shared Key Recovery Attack on Cascader Key Exchange Protocol
* Authors: Nick Aquina, Simon Rommel, Idelfonso Tafur Monroy
* [Permalink](https://eprint.iacr.org/2025/1418)
* [Download](https://eprint.iacr.org/2025/1418.pdf)
### Abstract
Cascader has been introduced as a new key exchange protocol based on iterative multiplicative recurrence. This short note presents a practical shared key recovery attack on the Cascader key exchange protocol. This note also shows that Cascader as a hash function is not collision resistant, presents a new upper bound on the output space of Cascader and shows that a Cascader-based KDF is not secure against an Adaptive Chosen Public Inputs Attack (CPM).
## 2025/1419
* Title: BEAST-MEV: Batched Threshold Encryption with Silent Setup for MEV prevention
* Authors: Jan Bormet, Arka Rai Choudhuri, Sebastian Faust, Sanjam Garg, Hussien Othman, Guru-Vamsi Policharla, Ziyan Qu, Mingyuan Wang
* [Permalink](https://eprint.iacr.org/2025/1419)
* [Download](https://eprint.iacr.org/2025/1419.pdf)
### Abstract
Threshold encrypted mempools protect the privacy of transactions up until the point their inclusion on chain is confirmed. They are a promising approach to protection against front-running attacks on decentralized blockchains.
Recent works have introduced two key properties that an encryption scheme must satisfy in order to scale to large scale decentralized blockchains such as Ethereum:
Silent Setup [Garg-Kolonelos-Policharla-Wang, CRYPTO'24], demands that a threshold encryption scheme does not require any interaction during the setup phase and only relies on the existence of Public Key Infrastructure. Batched Decryption [Choudhuri-Garg-Piet-Policharla, USENIX'24], demands that an entire block containing $B$ encrypted transactions can be decrypted using communication that is independent of (or sublinear in) $B$, without compromising the privacy of transactions that have not yet been confirmed.
While existing constructions achieve either Silent Setup or Batched Decryption independently, a truly decentralized and scalable encrypted mempool requires both properties to be satisfied simultaneously. In this work, we present the first ``Batched Threshold Encryption scheme with Silent Setup'' built using bilinear pairings. We provide formal definitions for the primitive, and prove security in the Generic Group Model. We provide several optimizations and implement our scheme to evaluate its performance. Our experiments demonstrate its efficiency for deployment in blockchain systems.
## 2025/1420
* Title: Coral: Fast Succinct Non-Interactive Zero-Knowledge CFG Proofs
* Authors: Sebastian Angel, Sof|!a Celi, Elizabeth Margolin, Pratyush Mishra, Martin Sander, Jess Woods
* [Permalink](https://eprint.iacr.org/2025/1420)
* [Download](https://eprint.iacr.org/2025/1420.pdf)
### Abstract
We introduce Coral, a system for proving in zero-
knowledge that a committed byte stream corresponds to a
structured object in accordance to a Context Free Grammar.
Once a prover establishes the validity of the parsed object with
Coral, they can selectively prove facts about the objectrCosuch as
fields in Web API responses or in JSON Web TokensrCorCoto third
parties or blockchains. Coral reduces the problem of correct
parsing to a few simple checks over a left-child right-sibling
tree and introduces a novel segmented memory abstraction that
unifies and extends prior constructions for RAM in zkSNARKs.
Our implementation of Coral runs on a standard laptop, and
non-interactively proves the parsing of real Web responses
(JSON) and files (TOML and C) in seconds. The resulting
proofs are small and cheap to verify.
## 2025/1421
* Title: Efficient randomized strong $2$-source non-malleable extractor for any linear min-entropy
* Authors: Divesh Aggarwal, Pranjal Dutta, Saswata Mukherjee, Satyajeet Nagargoje, Maciej Obremski
* [Permalink](https://eprint.iacr.org/2025/1421)
* [Download](https://eprint.iacr.org/2025/1421.pdf)
### Abstract
Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by generating nearly uniform randomness from two independent weak sources. Moreover, cryptographic systems must also be resilient to leakage and tampering attacks, necessitating the development of non-malleable two-source extractors.
In this work, we construct a two-source non-malleable extractor in the Common Reference String (CRS) model, where a random low-degree polynomial is sampled once and made accessible to independent random sources, the distinguisher, and the tamperer. Our extractor requires only linear min-entropy in both sources and doesn't rely on strong computational assumptions, in contrast to prior constructions requiring computational assumptions such as sub-exponential hardness of the Decisional Diffie-Hellman (DDH) problem. Notably, our construction builds upon and relies on the recent breakthrough proof of the polynomial Freiman-Ruzsa conjecture. A connection of the Freiman-Ruzsa conjecture with two-source extractors was considered in prior work [ZBS11],[AGMR24], but their construction did not achieve non-malleability.
Our results advance the state of non-malleable cryptographic primitives, with applications in secure storage, leakage-resilient cryptography, and privacy amplification. By eliminating the need for strong computational hardness assumptions, our techniques provide a more foundational and widely applicable method for randomness extraction.
We also show, that the requirements on CRS for our application are so mild that the CRS can be sampled with $2$ party computation even when one of the parties is malicious (setting in which establishing unbiased coins is impossible).
## 2025/1422
* Title: Design ZK-NR: A Post-Quantum Layered Protocol for Legally Explainable Zero-Knowledge Non-Repudiation Attestation
* Authors: Minka Mi Nguidjoi Thierry Emmanuel, Mani Onana Flavien Serge, Djotio Ndi|- Thomas, Atsa Etoundi Roger
* [Permalink](https://eprint.iacr.org/2025/1422)
* [Download](https://eprint.iacr.org/2025/1422.pdf)
### Abstract
This article presents the architectural design of Zero Knowledge Non-Repudiation (ZK-NR), a layered cryptographic protocol enabling post-quantum secure, legally interpretable, and verifiably non-repudiable attestations. Built upon STARK-based zero-knowledge proofs, hybrid post-quantum signatures, and entropy-accumulating ledger anchoring, ZK-NR satisfies the structural properties of both the Q2CSI framework and the NIZK-E model. The protocol achieves semantic interpretability by structurally separating contextual proofs from bounded explanations, while maintaining cryptographic soundness under the Universal Composability framework. Formal UC proofs are deferred to Article A.2 in this series. This article constitutes the first entry in the ZK-NR series, focused specifically on the protocol's architectural and functional design. Subsequent articles will cover its mathematical foundations, implementation strategies, and operational validation using formal verification environments.
## 2025/1423
* Title: Collusion-Safe Proxy Re-Encryption
* Authors: Haotian Yin, Jie Zhang, Wanxin Li, Yuji Dong, Eng Gee Lim, Dominik Wojtczak
* [Permalink](https://eprint.iacr.org/2025/1423)
* [Download](https://eprint.iacr.org/2025/1423.pdf)
### Abstract
Proxy re-encryption is a cryptographic scheme enabling a delegator (user $i$) to delegate its decryption right to a valid delegatee (user $j$) through a proxy, who cannot extract any information about the message during the procedure. An important security notion is the security against collusion between the proxy and the delegatee. In this case, the adversary has the secret key of the delegatee, $\mathsf{sk}_j$, and the re-encryption key, $\mathsf{rk}_{i\to j}$. The master secret security is first formalised by Ateniese et al. (NDSS'05) to capture the secrecy of $i$'s secret key during collusion. This notion was further formalised by Zhou et al. (ASIACRYPT'23) as the indistinguishability of re-encrypted ciphertext against chosen-message attacks, called collusion safety, which implies the master secret security. In this paper, we find that a PRE scheme is not master secret secure as they claimed, and many other schemes were not master secret secure. Then, we propose a generic construction to achieve collusion safety at the cost of doubling the key size from the IND-CPA secure PRE, enjoying a much better generality and efficiency than the existing technique by secret sharing.
## 2025/1424
* Title: LESS is Even More: Optimizing Digital Signatures from Code Equivalence * Authors: Luke Beckwith, Andre Esser, Edoardo Persichetti, Paolo Santini, Floyd Zweydinger
* [Permalink](https://eprint.iacr.org/2025/1424)
* [Download](https://eprint.iacr.org/2025/1424.pdf)
### Abstract
LESS is a signature scheme based on the code equivalence problem that has advanced to the second round of the NIST PQC standardization process. While promising, the scheme suffers from relatively large signatures and moderate to slow signing and verification times. Chou, Santini, and Persichetti recently introduced a variant of LESS relying on canonical forms to significantly reduce signature sizes. However, the overall performance impact of this approach remained largely unclear. In this work, we provide the first implementation of the new LESS variant and show that, in its original form, it performs poorly due to the overhead of computing canonical forms in a na|>ve way. We then introduce a series of algorithmic and implementation-level optimizations that reduce this overhead to about 10%, showing that the signature size reduction comes at minor cost. In addition, we present further improvements to the signature scheme as a whole, as well as a re-parameterization. The resulting scheme achieves speedups of 2.5|u to 10|u over the Round 1 NIST submission, while maintaining the reduced signature sizes.
## 2025/1425
* Title: Lodia: Towards Optimal Sparse Matrix-Vector Multiplication for Batched Fully Homomorphic Encryption
* Authors: Jiping Yu, Kun Chen, Xiaoyu Fan, Yunyi Chen, Xiaowei Zhu, Wenguang Chen
* [Permalink](https://eprint.iacr.org/2025/1425)
* [Download](https://eprint.iacr.org/2025/1425.pdf)
### Abstract
Encrypted matrix-vector multiplication is a fundamental component of a variety of applications that involve data privacy concerns. Current algorithms utilizing fully homomorphic encryption (FHE) generally use batching to enhance computational efficiency while neglecting the sparsity of the matrices, a characteristic that exists naturally in many practical situations. Alternatively, porting plaintext algorithms that address sparsity may fail to utilize batching and introduce additional privacy concerns.
We propose Lodia, an efficient outsourced SpMV algorithm for batched FHE schemes without sacrificing privacy. It only requires $\Theta((n+m)\log(n+m)/s)$ FHE operations, where $n$ is the number of rows/columns, $m$ is the number of non-zero elements of the matrix, and $s$ is the batch size of the FHE scheme. This is optimal for $m=\Omega(n)$ and $m=O(n^\rho)$ for some $\rho<2$ (i.e., $an \le m \le bn^\rho$ asymptotically), covering most practical cases. To our knowledge, no method has been published with better than $\Theta(n^2/s)$ FHE operations, suitable for any sparse matrix, and without privacy concerns.
Lodia utilizes a novel low-diagonal decomposition, which decomposes a sparse matrix into a series of special matrices named low-diagonal matrices. Based on a conventional method encoding the matrix in diagonal order, each low-diagonal matrix can be efficiently multiplied by a vector. This results in an efficient SpMV method suitable for any sparse matrix. Experiments show that Lodia practically achieves a speedup of up to $96\times$ compared to baselines that ignore matrix sparsity, and up to $3.6\times$ compared to implementations even with fewer security guarantees. This is the first SpMV solution on encrypted data that can process a substantial matrix with over 8 million rows/columns and 125 million non-zero elements.
## 2025/1426
* Title: (Im)Possibility of Symmetric Encryption against Coordinated Algorithm Substitution Attacks and Key Exfiltration
* Authors: Simone Colombo, Damian Viz|ir
* [Permalink](https://eprint.iacr.org/2025/1426)
* [Download](https://eprint.iacr.org/2025/1426.pdf)
### Abstract
A growing body of work addresses the security of cryptographic systems in the presence of mass surveillance, a threat made concrete by SnowdenrCOs revelations and the widespread use of spyware against journalists and activists. In this paper, we investigate the security of symmetric encryption faced with simultaneous algorithm substitution attacks (ASAs) and key exfiltration (KE). The security of symmetric encryption in presence of ASAs or KE alone was established but no result deals with their coordinated deployment. Yet, that is a necessary step to be made if we are to achieve actual security against mass surveillance. We formalize this setting, and prove that no scheme alone stands chance against coordinated ASA and KE, by describing a realistic attack. We then describe a new kind of schemes, which make use of externally supplied randomness. We formalize their security and give a construction which provably resists simultaneous ASAs and KE when paired with a verifiable source of randomness, with security bounds in the concrete security spirit.
## 2025/1427
* Title: End-to-End Non-Profiled Side-Channel Analysis on Long Raw Traces
* Authors: Jintong Yu, Yuxuan Wang, Shipei Qu, Yubo Zhao, Yipeng Shi, Pei Cao, Xiangjun Lu, Chi Zhang, Dawu Gu, Cheng Hong
* [Permalink](https://eprint.iacr.org/2025/1427)
* [Download](https://eprint.iacr.org/2025/1427.pdf)
### Abstract
With the advancement of deep learning techniques, Deep
Learning-based Non-profiled Side-Channel Analysis (DL-NSCA) can automatically learn and combine features, making it a promising method
that can skip the manual and precise selection of Points of Interest (PoIs). Existing DL-NSCA methods assume that the attacker can identify a
short leakage interval (usually less than 5000 points) containing PoIs
from raw traces (more than 100,000 points) and then feed the leakage
interval into the neural network to recover the key. However, in practice,
the attacker often faces a black-box scenario with unknown underlying implementations, making locating the short interval from raw traces
challenging, especially when masking countermeasures exist. To address
this issue, we propose a lightweight end-to-end DL-NSCA model called convWIN-MCR, which consists of a performance-optimizing component,
convWIN, and an accelerator component, MCR. It can efficiently process
raw traces without the need to manually identify the short leakage interval. On the public dataset ASCADv1, while the state-of-the-art model
Multi-Output Regression (MOR) requires 28,000 traces and 24 minutes
to recover the key from the leakage interval with 1,400 feature points, our framework only requires 6,000 traces in 13 minutes to directly analyze
raw traces with 250,000 feature points. To further validate the practical applicability of our framework, we successfully crack a commercial USIM
card by analyzing its raw traces and recovering its 128-bit AES key.
## 2025/1428
* Title: Strategic Mining in Proof-of-Stake with Practical Random Election
* Authors: Zhuo Cai
* [Permalink](https://eprint.iacr.org/2025/1428)
* [Download](https://eprint.iacr.org/2025/1428.pdf)
### Abstract
The security of blockchain systems relies on the honest ma-
jority assumption. However, strategic mining threatens this assumption,
because selfish miners can gain more block rewards than honest miners
by attacks such as withholding blocks. Due to its significant implica-
tion, blockchain mining games have been studied in PoW and PoS under
various settings using different methods. Nonetheless, this paper argues
that the practical limitation of random beacons has not been exploited
in strategic mining in PoS blockchains.
Current PoS blockchains use random beacons to randomly select valida-
tors for each slots. However, the randomness is usually fixed for multiple slots, due to the latency of distributed random beacon protocols. This indicates that validators actually know some information about the elec-
tion result in the future, which contrasts with the Markov process models
in previous analysis. Using this information, this paper presents a close
to optimal mining strategy based on an optimal interval scheduling algo-
rithm for each epoch. For proof-of-stake protocols with no propagation
delay, we show that a validator with arbitrary proportion of stake can
strictly benefit from strategic mining and get significantly higher block rewards than the previous strategies.
## 2025/1429
* Title: Public-Key Encryption and Injective Trapdoor Functions from LWE with Large Noise Rate
* Authors: Liheng Ji, Yilei Chen
* [Permalink](https://eprint.iacr.org/2025/1429)
* [Download](https://eprint.iacr.org/2025/1429.pdf)
### Abstract
The hardness of the learning with errors (LWE) problem increases as its noise rate grows. However, all existing LWE-based public-key encryption schemes require the noise rate to be no greater than $o(1/(\sqrt{n}\log n))$. Breaking through this limitation presents an intriguing challenge.
In this paper, we construct public-key encryption (PKE) schemes based on the sub-exponential hardness of decisional LWE with polynomial modulus and noise rate ranging from $O(1/\sqrt{n})$ to $o(1/\log n)$. More concretely, we demonstrate the existence of CPA-secure PKE schemes as long as one of the following three assumptions holds.
(i) $(n^{\omega(1)},n^{-\omega(1)})-$hardness of decisional LWE with noise rate $O(1/\sqrt{n})$.
(ii) $(2^{\omega(n^{1/c_1})},2^{-\omega(n^{1/c_1})})$-hardness of decisional LWE with noise rate $O(1/\sqrt{n^{1-1/c_1}\log n})$ for some constant $c_1>1$.
(iii) $(2^{\omega(n/\log^{c_2}n)},2^{-\omega(n/\log^{c_2}n)})$-hardness of decisional LWE with noise rate $O(1/\sqrt{\log^{c_2+1} n})$ for some constant $c_2>0$. \end{itemize}
We also construct injective trapdoor function (iTDF) families based on the same hardness assumption as our PKE. To achieve this, we give a generalization of Babai's nearest plane algorithm, which finds a ``common closest lattice point'' for a set of vectors.
In addition, we propose a PKE based on the $(2^{\omega(n^{1/2})},2^{-\omega(n^{1/2})})$-hardness of constant noise learning parity with noise (LPN) problem. Our construction is simpler than the construction of Yu and Zhang [CRYPTO 2016] while achieving the same security.
## 2025/1430
* Title: Practical Collision Attacks on Reduced-Round Xoodyak Hash Mode
* Authors: Huina Li, Le He, Weidong Qiu
* [Permalink](https://eprint.iacr.org/2025/1430)
* [Download](https://eprint.iacr.org/2025/1430.pdf)
### Abstract
\xoodyak is a finalist of the NIST lightweight cryptography competition, offering both keyed and hash modes. After several years of cryptanalysis, the largest number of \xoodyak hash rounds for which actual collisions was still in vacancy.
To the best of our knowledge, one of the most powerful collision attacks on hash functions based on sponge construction is the differential-based attacks using the S-box linearization technique proposed by Qiao \etal (EUROCRYPT 2017).
However, the linearization technique requires a large number of degrees of freedom, making it challenging to apply to \xoodyak with a small outer part. On the other hand, the constraint-input and constraint-output imposed on the differential trail of \xoodoo permutation make the exhaustive search for such high-probability differential trails in collision attacks extremely costly.
In this paper, we present critical observations regarding \xoodoo round function, particularly focusing on its unique $\theta$ and $\chi$ operation. These properties can be leveraged to manually design specific differential trails for the \xoodoo permutation, referred to as \textit{loop} differential trails. To efficiently find practical collisions for up to 3 rounds, we develop a SAT model based on these \textit{loop} trails. Finally, we present the first practical collision on 2 rounds and a practical semi-free-start collision on 3 rounds of \xoodyak hash mode. Besides, we improve Dong \etal's (CRYPTO 2024) collision attack on 3-round \xoodyak-\hash from $2^{125.23}$ to $2^{100.93}$ using several linearization strategies.
Since we focus on the analysis on collisions during the message absorbing phase of the hash modes, our results are applicable to both \xoodyak-\hash and \xoodyak-\xof.
## 2025/1431
* Title: Multi-Partner Project: Securing Future Edge-AI Processors in Practice (CONVOLVE)
* Authors: Sven Argo, Henk Corporaal, Alejandro Garza, Marc Geilen, Manil Dev Gomony, Tim G|+neysu, Adrian Marotzke, Fouwad Mir, Christian Larmann, Jan Richter-Brockmann, Jeffrey Smith, Mottaqiallah Taouil, Said Hamdioui
* [Permalink](https://eprint.iacr.org/2025/1431)
* [Download](https://eprint.iacr.org/2025/1431.pdf)
### Abstract
Artificial Intelligence (AI) has had a profound impact
on our contemporary society, and it is indisputable that it will
continue to play a significant role in the future. To further enhance
AI experience and performance, a transition from large-scale
server applications towards AI-powered edge devices is inevitable.
In fact, current projections indicate that the market for Smart
Edge Processors (SEPs) will grow beyond 70 Billion USD by
2026 [1]. Such a shift comes with major challenges, as these devices
have limited computing and energy resources yet need to be
highly performant. Additionally, security mechanisms need to be
implemented to protect against diverse attack vectors as attackers
now have physical access to the device. Besides cryptographic keys, Intellectual Property (IP), including neural network weights, may
also be potential targets.
The CONVOLVE [2] project (currently in its intermediate
stage) follows a holistic approach to address these challenges and
establish the EU in a leading position in embedded, ultra-low-
power and secure processors for edge computing. It encompasses
novel hardware technologies, end-to-end integrated workflows,
and a security-by-design approach. This paper highlights the
security aspects of future edge-AI processors by illustrating
challenges encountered in CONVOLVE, the solutions we pursue
including some early results, and directions for future research.
## 2025/1432
* Title: Brauer and certain class of Hansen chain are closed addition chains
* Authors: Theophilus Agama
* [Permalink](https://eprint.iacr.org/2025/1432)
* [Download](https://eprint.iacr.org/2025/1432.pdf)
### Abstract
We show that Brauer and a certain class of Hansen chains satisfy the requirements for an addition chain to be closed. This puts these types of addition chain as a subfamily of the so-called closed addition chains.
## 2025/1433
* Title: A Fully-Adaptive Threshold Partially-Oblivious PRF
* Authors: Ruben Baecker, Paul Gerhart, Daniel Rausch, Dominique Schr||der
* [Permalink](https://eprint.iacr.org/2025/1433)
* [Download](https://eprint.iacr.org/2025/1433.pdf)
### Abstract
Oblivious Pseudorandom Functions (OPRFs) are fundamental cryptographic primitives essential for privacy-enhancing technologies such as private set intersection, oblivious keyword search, and password-based authentication protocols. We present the first fully adaptive, partially oblivious threshold pseudorandom function that supports proactive key refresh and provides composable security under the One-More Gap Diffie-Hellman assumption in the random oracle model.
Our construction is secure with respect to a new ideal functionality for OPRFs that addresses three critical shortcomings of previous modelsrCospecifically, key refresh and non-verifiability issues that rendered them unrealizable. In addition, we identify a gap in a prior work's proof of partial obliviousness and develop a novel proof technique to salvage their scheme.
## 2025/1434
* Title: TLShare: Private Authenticated MPC and FHE Inputs Over TLS
* Authors: Manuel B. Santos, Dimitris Mouris, Xiang Xie, Miguel de Vega, Andrei Lapets
* [Permalink](https://eprint.iacr.org/2025/1434)
* [Download](https://eprint.iacr.org/2025/1434.pdf)
### Abstract
Transport Layer Security (TLS) is the backbone of the web, allowing clients to establish secure and private channels with servers. DECO (CCS'20) and follow-up works proposed protocols that enable proving the provenance of a TLS response, i.e., that a payload came from a particular server, without needing server-side modifications. Unfortunately, these works are limited to proving Boolean statements over the payload (e.g., age $\ge$ 18) and cannot combine payloads from multiple clients.
We introduce TLShare, a framework that extracts authenticated data from a TLS connection and imports it into secure multiparty computation (MPC) or fully homomorphic encryption (FHE), without requiring server-side changes or exposing client credentials. Unlike prior work, TLShare allows the payload itself, not just a predicate about it, to serve as private input to secure downstream computation. TLShare supports combining verifiable inputs across multiple clients and servers, enabling new applications such as privacy-preserving financial risk assessment and collaborative analytics. We design three protocols for TLShare: one for MPC using verifiable secret sharing, and two for FHE using interactive and non-interactive zero-knowledge proofs, each ensuring input authenticity, integrity, and end-to-end privacy. We evaluate all three protocols of TLShare over both LAN and WAN settings, comparing their trade-offs and demonstrating their practicality.
## 2025/1435
* Title: Weak Keys in QC-MDPC-based cryptosystems via the Extended Euclidean Algorithm
* Authors: Alessio Meneghetti, Federica Zanetti
* [Permalink](https://eprint.iacr.org/2025/1435)
* [Download](https://eprint.iacr.org/2025/1435.pdf)
### Abstract
In this work we analyze a problem strictly linked with the Rational Reconstruction, which forms the foundation of some post-quantum Quasi-Cyclic Moderate-Density Parity-Check and Quasi-Cyclic Low-Density Parity-Check code-based schemes such as LEDAkem and BIKE.
Given a polynomial in a cyclic ring as input, our aim is to recover two polynomials, with specific properties, whose ratio is the input one.
The starting point of this work is the paper of Bardet, Dragoi, Luque, and Otmani, which describes some approaches, based on the Extended Euclidean Algorithm, that solves this problem in some specific cases.
In comparison to previous work, we define an additional setting in which the problem can be solved. We also provide an alternative approach to estimate the probability of success, by taking into account a requirement that was not considered in the original paper, thus getting a more precise estimation. Finally, we present a key-recovery attack on BIKE, evaluate its computational cost, and compare it with that of the most efficient known attacks. Although this last step is performed specifically on BIKE, the methodology can be extended to other schemes as well.
## 2025/1436
* Title: VOLE-in-the-Head Signatures Based on the Linear Code Equivalence Problem
* Authors: Michele Battagliola, Laura Mattiuz, Alessio Meneghetti
* [Permalink](https://eprint.iacr.org/2025/1436)
* [Download](https://eprint.iacr.org/2025/1436.pdf)
### Abstract
The Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm has proven to be a versatile tool to design zero-knowledge proofs and signatures in post-quantum cryptography.
In this paper, we propose three VOLE-friendly modellings for Proofs of Knowledge (PoK) of a solution of an instance of the Linear Code Equivalence Problem (LEP). For the first two schemes, we propose two new reductions from LEP to the Multivariate Quadratic (MQ) problem, that may be of independent interest for the cryptanalysis of LEP. Instead, the last model is obtained by generalizing a recent work by Bettaieb et al. to the context of monomial matrices instead of permutation matrices.
While our proposed schemes exhibit larger signature sizes compared to LESS, they significantly improve the computational efficiency, reducing the overall complexity from $O(n^3)$ to $O(n^2)$, where $n$ is the code dimension.
## 2025/1437
* Title: GURKE: Group Unidirectional Ratcheted Key Exchange
* Authors: Daniel Collins, Paul R||sler
* [Permalink](https://eprint.iacr.org/2025/1437)
* [Download](https://eprint.iacr.org/2025/1437.pdf)
### Abstract
Continuous Group Key Agreement (CGKA) is a primitive with which members of a group can continuously establish shared keys. With every interaction, these members also update their individual, local secrets such that temporary corruptions of these secrets only affect the security of shared keys established shortly before (Forward Security; FS) and after the corruption (Post-Compromise Security; PCS). Due to these interactive updatesrCopossibly enriched by dynamic group membership changesrCo, CGKA is a very powerful but also very complex primitive.
In this work, we limit the power of CGKA to identify and analyze its core components. More concretely, we consider the case that all members of a group are always either senders or receivers. Thus, the interaction is strictly unidirectional from the former to the latter: a group of senders Alice establishes shared keys with a group of receivers Bob. With every shared key, Alice updates her local state to achieve FS and PCS; when receiving an established key, each Bob also updates their local state to achieve FS. This notion naturally lifts the so called Unidirectional Ratcheted Key Exchange concept (Bellare et al., Crypto 2017; Poettering and R||sler, Crypto 2018) to the group setting and, thereby, captures and generalizes Signal's Sender Key Mechanism, which is the core of WhatsApp and Signal's group chat protocols. We modularize this concept of Group Unidirectional RKE (GURKE) by considering either single or multiple senders, single or multiple receivers, and static or dynamic membership on each of both sides of the group.
To instantiate these new primitives, we develop a building block called Updatable Broadcast KEM (UB-KEM). Using UB-KEM, our GURKE constructions for static groups only use standard Key Encapsulation Mechanisms (KEMs) and induce only a constant communication overhead. Our GURKE constructions for dynamic groups are based on general Non-Interactive Key Exchange (NIKE) and offer a constant communication overhead as long as the set of members is unchanged; only for adding and removing users, a communication overhead logarithmic in the group size is induced. We discuss the benefits of replacing the Sender Key Mechanism in Signal and WhatsApp with our constructions, and demonstrate their practicality with a performance evaluation of our proof of concept UB-KEM implementation.
## 2025/1438
* Title: Secure Protocols for Best Arm Identification Using Secret Sharing Schemes
* Authors: Shanuja Sasi, Asaf Cohen, Onur G|+nl|+
* [Permalink](https://eprint.iacr.org/2025/1438)
* [Download](https://eprint.iacr.org/2025/1438.pdf)
### Abstract
This paper addresses the challenge of best arm identification in stochastic multi-armed bandit (MAB) models under privacy-preserving constraints, such as in dynamic spectrum access networks where secondary users must privately detect underutilized channels. While previous network security research has explored securing MAB algorithms through techniques such as homomorphic encryption or differential privacy, these methods often suffer from high computational overhead or introduce noise that strictly decreases accuracy. In contrast, this work focuses on lightweight solutions that ensure data confidentiality without compromising the accuracy of best arm identification. We introduce two secure protocols that leverage additive secret sharing and threshold secret sharing. The proposed model, employing aggregation nodes and a comparator node, securely distributes computations to prevent any entity from accessing complete reward or ranking data. Furthermore, the protocol ensures resistance to collusion and fault tolerance, while maintaining computational efficiency. These contributions establish a scalable and robust framework for privacy-preserving best arm identification, offering practical and secure solutions that use MAB methods for network security.
## 2025/1439
* Title: A Note on the Post-Quantum Security of Identity-Based Encryption on Isogenous Pairing Groups
* Authors: Malte Andersch, Cezary Pilaszewicz, Marian Margraf
* [Permalink](https://eprint.iacr.org/2025/1439)
* [Download](https://eprint.iacr.org/2025/1439.pdf)
### Abstract
The development of cryptographic schemes which remain secure in the post-quantum era is an urgent challenge, particularly in light of the growing ubiquity of low-power devices and the looming threat of quantum computing. Identity-Based Encryption (IBE) offers a compelling alternative to traditional Public Key Infrastructures by simplifying key management, but most classical IBE schemes rely on number-theoretic assumptions that are vulnerable to quantum attacks. In response, Koshiba and Takashima proposed a novel approach based on Isogenous Pairing Groups (IPGs) [11], claiming partial quantum resistance. In this work, we critically examine their construction and security claims. We show that the proposed scheme, despite its theoretical elegance, reduces to the Elliptic Curve Discrete Logarithm Problem (ECDLP) on supersingular curves, which can be broken in polynomial time by quantum algorithms and in subexponential time classically. Our analysis reveals structural weaknesses inherent to the IPG framework, such as the use of explicit group elements in prime-order groups and exploitable isogeny homomorphisms, which undermine its claimed security guarantees. These findings suggest that IPG-based constructions, in their current form, are unlikely to provide robust post-quantum security.
## 2025/1440
* Title: Faster Homomorphic Integer Computer
* Authors: Jaehyung Kim
* [Permalink](https://eprint.iacr.org/2025/1440)
* [Download](https://eprint.iacr.org/2025/1440.pdf)
### Abstract
We design a fast and efficient fully homomorphic encryption for radix power modulus. We mainly rely on the CKKS modular reduction by Kim and Noh [CiC'25] and the intermediate CKKS encoding from NeuJeans [Ju et al.;CCS'24]. Our construction is a direct improvement of the homomorphic integer computer by Kim [TCHES'25]: The asymptotic latency reduces from $O(k)$ to $O(\log k)$ for a given plaintext modulus $b^k$ for a fixed radix base $b$, while keeping the throughput. Our experiments show that the latency of our $64$ bit multiplication is $\approx 6$ times faster than Kim and slightly faster than TFHE-rs, while being three orders of magnitude better in terms of throughput than TFHE-rs. The performance gap widens for larger precision. Our work also concretely outperforms the work by Boneh and Kim [Crypto'25], by a factor of $4.70$ better latency and $75.3$ times better throughput for $256$ bit multiplication.
## 2025/1441
* Title: DIMSEPP: A Decentralized Identity Management System with Enhanced Privacy Protection
* Authors: Yu Zhang, Zongbin Wang
* [Permalink](https://eprint.iacr.org/2025/1441)
* [Download](https://eprint.iacr.org/2025/1441.pdf)
### Abstract
This paper proposes DIMSEPP, a decentralized identity management system that enhances privacy while preserving blockchain verifiability. The system cryptographically enforces data minimal disclosure principles by storing attribute commitments on-chain and validating them through zero-knowledge proofs, allowing users to demonstrate attribute validity without revealing sensitive values.
The architecture maintains full compatibility with existing DID standards through standard document structures and verification methods. Security analysis demonstrates provable guarantees under standard cryptographic assumptions. Practical evaluation confirms the system's efficiency for resource-constrained environments, supporting deployment in applications where both privacy and verifiability are essential.
## 2025/1442
* Title: Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions
* Authors: Nir Bitansky, Saroja Erabelli, Rachit Garg, Yuval Ishai
* [Permalink](https://eprint.iacr.org/2025/1442)
* [Download](https://eprint.iacr.org/2025/1442.pdf)
### Abstract
The shuffle model is a widely used abstraction for non-interactive anonymous communication. It allows $n$ parties holding private inputs $x_1,\dots,x_n$ to simultaneously send messages to an evaluator, so that the messages are received in a random order. The evaluator can then compute a joint function $f(x_1,\dots,x_n)$, ideally while learning nothing else about the private inputs. The model has become increasingly popular both in cryptography, as an alternative to non-interactive secure computation in trusted setup models, and even more so in differential privacy, as an intermediate between the high-privacy, little-utility local model and the little-privacy, high-utility central curator model.
The main open question in this context is which functions $f$ can be computed in the shuffle model with statistical security. While general feasibility results were obtained
using public-key cryptography, the question of statistical security has remained elusive. The common conjecture has been that even relatively simple functions cannot be computed with statistical security in the shuffle model.
We refute this conjecture, showing that all functions can be computed in the shuffle model with statistical security. In particular, any differentially private mechanism in the central curator model can also be realized in the shuffle model with essentially the same utility, and while the evaluator learns nothing beyond the central model result.
This feasibility result is obtained by constructing a statistically secure additive randomized encoding (ARE) for any function. An ARE randomly maps individual inputs to group elements whose sum only reveals the function output.
Similarly to other types of randomized encoding of functions, our statistical ARE is efficient for functions in $NC^1$ or $NL$. Alternatively, we get computationally secure ARE for all polynomial-time functions using a one-way function. More generally, we can convert any (information-theoretic or computational) ``garbling scheme'' to an ARE with a constant-factor size overhead.
--- Synchronet 3.21a-Linux NewsLink 1.2