From Newsgroup: sci.crypt

## In this issue
1. [2025/1494] Quantum Circuit Synthesis for AES with Low DW-cost
2. [2025/1797] An efficient quantum algorithm for computing ...
3. [2025/1980] Traceable Secret Sharing Revisited
4. [2025/2138] Synergeia: Super-Linear Consistency and Adaptive ...
5. [2025/2139] Scalable Private World Computer via Root iO: ...
6. [2025/2140] Nostalgia Cipher: Can Filtered LFSRs Be Secure ...
7. [2025/2141] New Memory Optimizations of Wagner's Algorithms via ...
8. [2025/2142] Differential cryptanalysis of An optimized novel ...
9. [2025/2143] New Post-Quantum IBE leveraging maturity, ...
10. [2025/2144] On Equivalence of the Butterfly Structure
11. [2025/2145] Derivative-Free Richelot Isogenies via ...
12. [2025/2146] Zero-Knowledge Protocols with PVC Security: ...
13. [2025/2147] Updatable Private Set Intersection and Beyond: ...
14. [2025/2148] Introducing the ALF family: AES-NI-based length- ...
15. [2025/2149] Weak Tweak-Key Analysis Of Blink Via Superbox
16. [2025/2150] Low-Latency Fully Homomorphic Arithmetic Using ...
17. [2025/2151] Hardness of Problems with Hints in Code-Based ...
18. [2025/2152] Sum-check protocol for approximate computations
19. [2025/2153] Semigroup-homomorphic Signature
20. [2025/2154] Optimal Threshold Traitor Tracing
21. [2025/2155] A New Approach to Arguments of Quantum Knowledge
22. [2025/2156] Multi-Verifier Keyed-Verification Anonymous Credentials
23. [2025/2157] Taming the Stack: Proof-Preserving Blockwise ...
24. [2025/2158] Efficient Batched IBE from Lattices
25. [2025/2159] One Fell Swoop: A Single-Trace Key-Recovery Attack ...
26. [2025/2160] Pairing-Based SNARGs with Two Group Elements
27. [2025/2161] Attacks and Remedies for Randomness in AI: ...
28. [2025/2162] You Only Decapsulate Once: Ciphertext-Independent ...
29. [2025/2163] Correction-Based Fault Attack Against Randomized MAYO
30. [2025/2164] Hardness and Algorithms for Batch LPN under ...
31. [2025/2165] Extending and Accelerating Inner Product Masking ...
32. [2025/2166] How to Prove Post-Quantum Security for Succinct ...
33. [2025/2167] 1-Adaptive Weak Pseudorandom Functions
34. [2025/2168] Hybrid Subsupport Guessing: A New Hybrid Technique ...
35. [2025/2169] Multivariate exponential equations with unknown ...
36. [2025/2170] Lattice-Based Linkable Ring Signatures for ...
37. [2025/2171] Efficient GHASH and POLYVAL Implementation Using ...
38. [2025/2172] Crypto Wars in Secure Messaging: Covert Channels in ...
## 2025/1494
* Title: Quantum Circuit Synthesis for AES with Low DW-cost
* Authors: Haoyu Liao, Qingbin Luo
* [Permalink](https://eprint.iacr.org/2025/1494)
* [Download](https://eprint.iacr.org/2025/1494.pdf)
### Abstract
Symmetric cryptography is confronting threats posed by quantum computing, including Grover's search algorithm and Simon's algorithm. In the fault-tolerant quantum computation, the limited qubit count, connectivity constraints, and error rates of quantum hardware impose stringent requirements on the implementation of cryptographic quantum circuits. Constructing low-resource quantum circuit models forms the foundation for evaluating algorithmic resistance to quantum threats. At CRYPTO 2019, Jaques et al. justified the adoption of depth-times-width cost (DW-cost) as a metric for quantum circuits by incorporating advancements in quantum computation and error correction. In this work, we address the fundamental limitations in in-place implementations of AES quantum circuits by proposing a set of in-place synthesis methods centered on DW-cost optimization. First, we prove that within the composite field arithmetic framework, intermediate circuit states can be utilized to uncompute S-box input states, and introduce a novel design pathway and circuit structure for in-place S-box quantum circuits. Second, we establish the necessary conditions for maximizing parallelization of Toffoli gates under minimal-width constraints in binary field multiplication. Through co-design and optimization of multiple nonlinear components, we construct a compact in-place S-box with a DW-cost of merely 276. Finally, building on this, we achieve quantum circuit implementations for AES-128, AES-192, and AES-256 via co-optimization of key expansion and round functions, reducing their DW-cost values to 65,280, 87,552, and 112,896 respectively. These results indicate a reduction of at least 46%, 45%, and 45% compared to existing state-of-the-art solutions. This study establishes new technical benchmarks for low-resource fault-tolerant implementations of symmetric cryptography in the post-quantum era. (This is a revised version containing Clifford+T resource estimates for both AES-128 Grover oracle and encryption oracle. Key revisions are highlighted in red.)
## 2025/1797
* Title: An efficient quantum algorithm for computing $S$-units and its applications
* Authors: Jean-Fran|oois Biasse, Fang Song
* [Permalink](https://eprint.iacr.org/2025/1797)
* [Download](https://eprint.iacr.org/2025/1797.pdf)
### Abstract
In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, $S$-class groups, relative class group and unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.
## 2025/1980
* Title: Traceable Secret Sharing Revisited
* Authors: Vipul Goyal, Abhishek Jain, Aditi Partap
* [Permalink](https://eprint.iacr.org/2025/1980)
* [Download](https://eprint.iacr.org/2025/1980.pdf)
### Abstract
In a secret sharing scheme for a monotone access structure $\mathcal{A}$, one can share a secret among a set of parties such that all subsets of parties authorized by $\mathcal{A}$ can reconstruct the secret while all other subsets learn nothing. However, what if an unauthorized subset of parties collude and offer their shares for sale? Specifically, suppose that the parties pool their shares to create a reconstruction box that reveals the secret upon receiving enough additional shares as input. To deter this behavior, Goyal et al. (CRYPTO'21) introduced the notion of traceable secret sharing (TSS), where it is possible to provably trace reconstruction boxes containing leaked secret shares back to their respective parties. Goyal et al. and subsequent work presented definitions and constructions of TSS for the threshold access structure.
In this work, we revisit the notion of TSS.
- We identify shortcomings in previous formulations of TSS and present new, strengthened definitions that are not achieved by known constructions. We show that it is easy to build reconstruction boxes for which the tracing guarantees of all previous works fail.
- We extend the study of TSS beyond threshold to general access structures. Our new definitions are, in fact, necessary for this setting as natural adaptations of existing definitions become vacuous for general access structures.
- We present new constructions of TSS that satisfy our definitions for all access structures captured by monotone circuits. One of our constructions relies solely on one-way functions while the other additionally relies on indistinguishability obfuscation.
## 2025/2138
* Title: Synergeia: Super-Linear Consistency and Adaptive Stability in a Hybrid PoW/PoS Consensus
* Authors: Aaron M. Schutza
* [Permalink](https://eprint.iacr.org/2025/2138)
* [Download](https://eprint.iacr.org/2025/2138.pdf)
### Abstract
We present the Synergeia (+u-a+++|-U+|+>+#) protocol, a novel, permissionless blockchain protocol that synergistically integrates Proof-of-Work (PoW) and a dynamically regulated Proof-of-Stake (PoS) mechanism. Traditional Nakamoto protocols exhibit consistency violations decaying as $\epsilon \approx exp(-\Omega(k))$ leading to long finality times. Our primary contribution is leveraging a Local Dynamic Difficulty (LDD) scheme to reshape the block inter-arrival time distribution towards a Rayleigh distribution. We prove this yields a full consistency bound of $\epsilon(k) \le exp(-C_{1}k^{2}) + exp(-C_{2}k)$. While this provides a quadratic asymptotic advantage, we demonstrate that for practical security parameters, the bound is dominated by the linear term. Our LDD mechanism achieves a superior constant factor ($C_{2}$) in this linear exponent, requiring only $k=26$ blocks against a 40% adversary for enterprise-grade security ($\epsilon \le 10^{-9}$). Furthermore, we introduce the Decentralized Consensus Service ($\mathcal{F}_{DCS}$) providing BFT-robust consensus on network time, stake, delay, and load via on-chain beacons. This enables a fully autonomous LDD system that dynamically adapts its Slot Gap ($\psi$) and target block time ($\mu_{target}$) to measured network conditions, ensuring the security assumption $\psi > \Delta$ holds robustly. The protocol utilizes an Accumulated Synergistic Work (ASW) metric incorporating Proof-of-Burn for PoS block commitment. As a result of this constant-factor improvement, Synergeia achieves probabilistic finality in approximately 6.5 minutes under typical Bitcoin-like network conditions ($\mathbb{E}[\Delta] \approx 8s$). Additionally, we introduce Burst Finality, an optional mechanism triggered by high transaction fees (secured by Proof-of-Burn) that provides execution-driven confirmation for instant finality. Synergeia establishes a new paradigm for adaptive consensus, offering a significant constant-factor improvement for probabilistic finality alongside optional near-instant settlement.
## 2025/2139
* Title: Scalable Private World Computer via Root iO: Application-Agnostic iO and Our Roadmap for Making It Practical
* Authors: Sora Suegami, Enrico Bottazzi
* [Permalink](https://eprint.iacr.org/2025/2139)
* [Download](https://eprint.iacr.org/2025/2139.pdf)
### Abstract
Ethereum has established itself as a world computer, enabling general-purpose, decentralized, and verifiable computation via smart contracts on a globally replicated state. However, because all computations and state are public by default, it is fundamentally unsuitable for confidential smart contracts that jointly process private data from multiple users. This motivates the notion of a private world computer: an ideal future form of Ethereum that preserves its integrity and availability guarantees while supporting such confidential smart contracts. Prior constructions based on implementable cryptographic primitives such as fully homomorphic encryption (FHE) inevitably rely on committees that hold secret shares and perform computations using those shares, a capability that is not provided by today's Ethereum validators. We cannot simply modify the Ethereum protocol so as to shift the committeerCOs role onto the Ethereum validators, because the computational and communication costs borne by the committee grow with the demand for confidential smart contracts, forcing higher hardware requirements for participation, undermining decentralization, and increasing the risk of malicious collusion. Hence, there remains a fundamental trade-off between committee decentralization and scalability for confidential smart contracts.
In this position paper, we make two contributions toward a scalable private world computer. First, we show how indistinguishability/ideal obfuscation (iO), combined with FHE and succinct non-interactive arguments of knowledge (SNARK), yields a private world computer that, after a one-time obfuscation process, introduces no additional ongoing trust assumptions beyond EthereumrCOs validators, incurring no additional overhead for validators to process confidential smart contracts compared to public smart contracts. In this design, a single application-agnostic obfuscated circuit, called root iO, suffices to realize arbitrary confidential smart contracts. The outputs of root iO can be verified on-chain at a cost comparable to signature verification, and the obfuscation process can be distributed among multiple parties while remaining secure as long as at least one party is honest. As the second contribution, we outline our roadmap toward a practical implementation of root iO. Assuming that the underlying assumptions of our lattice-based iO construction remain secure, the remaining missing pieces are technically concrete: namely, practical implementations of verifiable FHE and of homomorphic evaluation of a pseudorandom function (PRF) and SNARK verification over key-homomorphic encodings, which together would allow us to implement root iO without incurring prohibitive overhead.
## 2025/2140
* Title: Nostalgia Cipher: Can Filtered LFSRs Be Secure Again? An Application to Hybrid Homomorphic Encryption with Sub-50 ms Latency
* Authors: Nabil Chacal, Antonio Guimar|ues, Ange Martinelli, Pierrick M|-aux, Romain Poussier
* [Permalink](https://eprint.iacr.org/2025/2140)
* [Download](https://eprint.iacr.org/2025/2140.pdf)
### Abstract
Linear Feedback Shift Registers (LFSRs) combined with non linear filtering functions have long been a fundamental design for stream ciphers, offering a well-understood structure that remains easy to analyze. However, the introduction of algebraic attacks in 2003 shifted the focus toward more complex designs, as filtered LFSRs required larger registers to maintain security. While this was seen as a drawback at the time, it is no longer a limiting factor, and emerging cryptographic applications benefit from specialized designsrCochallenges that filtered LFSRs can effectively address.
In this work, we propose a new filtered LFSR design, called Nostalgia, tailored for Hybrid Homomorphic Encryption (HHE). We use a weightwise quadratic function as filtering function, leveraging its efficiency in the HHE setting while ensuring security against classical attacks. We also discuss the parameter selection of our design and demonstrate its efficiency in this setting by providing a proof-of-concept implementation. In terms of latency, our HHE solution outperforms current state-of-the-art for TFHE-based HHE (Baudrin et. al. Crypto 2025) by a factor of 6.1 times.
By revisiting filtered LFSRs in light of modern security requirements, we aim to renew interest in their potential applications and stimulate further cryptanalysis efforts.
## 2025/2141
* Title: New Memory Optimizations of Wagner's Algorithms via List Item Reduction
* Authors: Lili Tang, Rui Ding, Yao Sun, Xiaorui Gong
* [Permalink](https://eprint.iacr.org/2025/2141)
* [Download](https://eprint.iacr.org/2025/2141.pdf)
### Abstract
The Generalized Birthday Problem ($\textsf{GBP}$) serves as a cornerstone for a broad spectrum of cryptanalytic research. The classical solution, WagnerrCOs $k$-tree algorithm (CRYPTOrCO02), is characterized by inherently high memory complexity. Subsequently, Biryukov and Khovratovich (NDSSrCO16) introduced $\textsf{Equihash}$, a memory-hard proof-of-work scheme constructed upon a single-list variant of WagnerrCOs algorithm. Due to its robust resistance to ASIC mining, $\textsf{Equihash}$ has emerged as one of the most widely adopted proof-of-work schemes in blockchain. However, memory optimization for Wagner-style algorithms remains a persistent challenge in cryptographic research. Conventional approaches primarily focus on reducing list size to lower memory consumption, yet this strategy typically incurs a prohibitive time penalty. For instance, halving the peak memory usage of the $\textsf{Equihash}(200, 9)$ mining algorithm increases its theoretical time complexity by a factor of $2^{24.6}$.
In this work, we investigate a novel optimization vector: List Item Reduction (LIR), which facilitates practical and fine-grained memory-time trade-offs. We systematize existing LIR techniques and propose novel optimization methods integrated into a new hybrid framework. While our approach does not improve asymptotic memory complexity, it achieves a near-linear trade-off in practice, offering substantial benefits for the concrete design of efficient Wagner-style algorithms. Specifically, our techniques reduce peak memory usage by nearly 50% (from $2nN$ to $nN$ bits) across all $\textsf{Equihash}$ parameters, with only an approximate twofold time penalty. Furthermore, we present concrete implementations, including the first realization of an in-place $\textsf{merge}$. Building on these results, we propose an ASIC-friendly framework leveraging an external-memory caching mechanism.
## 2025/2142
* Title: Differential cryptanalysis of An optimized novel lightweight block cipher for image encryption
* Authors: Khaled Hosseini, Sadegh Sadeghi
* [Permalink](https://eprint.iacr.org/2025/2142)
* [Download](https://eprint.iacr.org/2025/2142.pdf)
### Abstract
This paper presents a security analysis of the ARX-based lightweight block cipher proposed by Mohanapriya and Nithish (Sci Rep 15, 36060 (2025)) for image encryption in IoT environments. The cipher employs a 64-bit key and a 64-bit block size, relying on Addition, Rotation, and XOR (ARX) operations. Our analysis demonstrates that the full-round version of this cipher is vulnerable to differential cryptanalysis. In fact, the cipher can be distinguished from a random permutation using $2^{41}$ chosen plaintexts. Consequently, the designers' security claims are not fully supported.
## 2025/2143
* Title: New Post-Quantum IBE leveraging maturity, efficiency and security of standard schemes
* Authors: Julien CAM
* [Permalink](https://eprint.iacr.org/2025/2143)
* [Download](https://eprint.iacr.org/2025/2143.pdf)
### Abstract
Many Identity-Based Encryption (IBE) schemes rely on the hardness of the Discrete Logarithm Problem, making them vulnerable to quantum attacks like Shor's algorithm. In recent years, lattice-based cryptography has emerged as a source of Post-Quantum cryptosystems, for example with Kyber, Dilithium and Falcon chosen by NIST to be standardized as ML-KEM, ML-DSA and FN-DSA. In the meantime, some IBEs have also been proposed over lattices. However, they can still be considered as interesting theoretical constructions, the community's attention having been more on the NIST competition than on optimizing IBEs, assessing their security, and protecting them against physical attacks.
So, in this paper, we build a new IBE scheme from the highly studied ML-KEM, ML-DSA and ModFalcon. More precisely, we leverage the Module-NTRU trapdoor from ModFalcon to enable extraction of secret keys, we use the encryption and decryption algorithms from ML-KEM, and the modular arithmetic and Number-Theoretic Transform from ML-DSA. Therefore, being able to reuse some of their code, our scheme is easy to implement, and can benefit from existing and future and side-channel protections. In this paper, we also prove the IND-sID-CPA-security of our scheme under the Ring-LWE and Module-NTRU assumptions, and we precisely describe the choice of appropriate parameters. As a work that can be of independent interest, we also provide an efficient estimator for the decryption failure probability of a LWE-based scheme, which allows us to concretely check the negligible failure probability of our scheme, at a standard security level.
## 2025/2144
* Title: On Equivalence of the Butterfly Structure
* Authors: Chin Hei Chan
* [Permalink](https://eprint.iacr.org/2025/2144)
* [Download](https://eprint.iacr.org/2025/2144.pdf)
### Abstract
The butterfly structures were introduced by Perrin et al. as a generalization of the Dillon's APN permutation operated in 6 bits. It was proved by several authors independently that such butterflies are differentially 4-uniform and have best known nonlinearity among functions over $\mathbb{F}_{2^{2k}}$. In [LLHQ21, LHXZ22] authors provided sufficient coefficient conditions such that the closed butterfly is a permutation and they further prove that such functions have boomerang uniformity 4 and are linear equivalent to Gold functions. In this paper, we adopt techniques from [DZ23] and [GK] to classify closed butterfly structures satisfying more general conditions in terms of EA-equivalence and CCZ-equivalence.
## 2025/2145
* Title: Derivative-Free Richelot Isogenies via Subresultants: Algebraic Equivalence and Certified Guarded Computation
* Authors: Hung T. Dang
* [Permalink](https://eprint.iacr.org/2025/2145)
* [Download](https://eprint.iacr.org/2025/2145.pdf)
### Abstract
We present a derivative-free Richelot (2,2)-isogeny formulation using first subresultants and a canonical quadratic lift. Over odd characteristic, we prove its algebraic equivalence in Fp[x] to the classical Wronskian under natural normalization. Leveraging this, we introduce the Guarded Subresultant Route (GSR): a deterministic evaluator with constant-size algebraic guards, a lightweight post-check, and at most one affine retry. It returns a certified triple (U, V, W) or rejects non-admissible inputs, eliminating differentiation while enforcing admissibility and auditable control flow. Prototypes show the core is 1.46rCo1.70 times faster than the classical Wronskian across varied primes, with GSR adding about 5rCo10 microseconds of constant overhead. The backend-agnostic design suits batched and hierarchical genus-2 isogeny pipelines for reproducible computation.
## 2025/2146
* Title: Zero-Knowledge Protocols with PVC Security: Striking the Balance between Security and Efficiency
* Authors: Yi Liu, Yipeng Song, Anjia Yang, Junzuo Lai
* [Permalink](https://eprint.iacr.org/2025/2146)
* [Download](https://eprint.iacr.org/2025/2146.pdf)
### Abstract
Zero-knowledge protocols allow a prover to prove possession of a witness for an NP-statement without revealing any information about the witness itself. This kind of protocol has found extensive applications in various fields, including secure computation and blockchain. However, in certain scenarios (e.g. when the statements are complicated), existing zero-knowledge protocols may not be well-suited due to their limited applicability or high computational overhead.
We address these limitations by incorporating the notion of publicly verifiable covert (PVC) security into zero-knowledge protocols. PVC security, recently emerging from secure computation, effectively balances security and efficiency in practical scenarios. With PVC security, while a malicious party may attempt to cheat, such cheating will be detected and become publicly verifiable with a significant probability (called deterrence factor, e.g. ${>}90\%$). This notion is well-suited for practical scenarios involving reputation-conscious parties (e.g. companies) and offers substantial efficiency improvements.
In this paper, we present the first definition of zero-knowledge protocols with PVC security. We then propose a generic transformation to convert Sigma protocols with $1$-bit challenge, a kind of protocol widely used for zero-knowledge, into efficient zero-knowledge protocols with PVC security. By applying our transformation, we can substantially improve the efficiency of existing protocols for reputation-sensitive parties. For instance, applying the transformation to achieve a deterrence factor of $93.75\%$ incurs a cost of only around $20\%$ compared to the original protocol. Therefore, our results contribute to significant advancements in practical zero-knowledge protocols.
## 2025/2147
* Title: Updatable Private Set Intersection and Beyond: Efficient Constructions via Circuit Private Set Intersection
* Authors: Ferran Alborch, Tom Chauvier, Antonio Faonio, Alexandre Fontaine, Ferhat Karako|o, Alptekin K|+p|o|+, Camille Malek, Melek |unen
* [Permalink](https://eprint.iacr.org/2025/2147)
* [Download](https://eprint.iacr.org/2025/2147.pdf)
### Abstract
Private Set Intersection (PSI) has been widely studied, deployed, and demonstrated through various real-life use cases such as mobile private contact discovery, privacy-preserving contact tracing, etc. Nevertheless, the majority of existing solutions typically assume that the underlying datasets are static and require a fresh execution of PSI at each time the datasets are updated over time. In this work, similar to a recent solution by Badrinaryanan et. al' (ASIACRYPT 2024), we investigate the problem of designing efficient and secure updatable PSIs in the honest-but-curious model by adopting the approach of executing a small number of PSIs over smaller sets instead of one PSI over the entire, updated sets. We first identify that existing constructions suffer from two privacy leakages and further propose to mitigate them thanks to the use of circuit PSIs, which are variants of PSI protocols that instead of outputting the resulting intersection, output the secret shares of the intersection and nothing more, combined with secure shuffling when needed. We construct a generic framework for PSI over updated sets which can use any circuit-PSI. Additionally, we show that this framework can easily be extended to a protocol that outputs the cardinality of the intersection instead of the intersection, itself. Finally, we provide an in-depth discussion on the feasibility of circuit PSI over updated sets, with the main challenges to overcome and solutions for some particular cases. Our solutions are implemented in Rust and their performance is compared with the state of the art, achieving an improvement of $11\times$ to $40\times$ in updatable PSI and $14\times$ to $107\times$ in updatable cardinality PSI in computation time. The proposed framework is also demonstrated through a real-life use case, namely, a spam detection filter.
## 2025/2148
* Title: Introducing the ALF family: AES-NI-based length- and format-preserving encryption
* Authors: Dachao Wang, Alexander Maximov, Thomas Johansson
* [Permalink](https://eprint.iacr.org/2025/2148)
* [Download](https://eprint.iacr.org/2025/2148.pdf)
### Abstract
This paper introduces the ALF cipher family, designed for format-preserving encryption. The key strategy is to leverage AES-NI instructions to achieve a high software performance while also providing 128-bit security. As the input size may vary a lot between different cases, we present a family of ciphers, where different instances cover different domain sizes. While the included designs differ, the common theme is their use of AES-NI instructions in the designs.
A central part of the paper is the design of an AES-related bit-oriented block cipher with varying block size in the interval 16-127 bits. The design is byte-oriented, but allows appending 0-7 bits to a byte-oriented input. We introduce an approach for efficient implementation using AES-NI, even though the block size is not 128 bits. The block cipher family is turned into a format-preserving encryption by a new cycle-sliding transformation, improving slightly on traditional cycle-walking. Performance evaluation shows improvements in speed of several orders of magnitude compared to the standardised algorithm FF1 and the previous FF3.
## 2025/2149
* Title: Weak Tweak-Key Analysis Of Blink Via Superbox
* Authors: Shiyao Chen, Jian Guo, Tianyu Zhang
* [Permalink](https://eprint.iacr.org/2025/2149)
* [Download](https://eprint.iacr.org/2025/2149.pdf)
### Abstract
This work presents the first third-party cryptanalysis of Blink, a recent tweakable block cipher built on the Three-Hash Framework (THF) with an $\alpha$-reflection structure and a long-key design. We build our analysis on the idea of Superbox, in view of its natural support of local clustering and easy integration with automatic search tools. Thus, we first develop a deliberately lightweight theoretical model that captures the value correlations inside the Superbox of Blink when the value spaces are affine, the weak-key conditions, fixed-key probabilities and the local clustering behaviors. Our theory is only intended as a concrete, easy-to-follow specialization of existing generic frameworks adapted precisely to the structure of Blink. We then build a simple pattern-based automatic search model for weak tweak-key differentials. As a result, for Blink-64 with 448-bit key, we obtain a 10-round distinguisher for up to $2^{442}$ weak keys with probability $2^{-50.42}$; For Blink-128 with 1024-bit key, we obtain a 10-round distinguisher for up to $2^{1010}$ weak keys with probability $2^{-68.83}$, which can be extended to a 12-round multiple differential distinguisher with probability $2^{-96.83}$. The all-zero tweak is a convenient choice to maximize the weak key space. Based on the weak tweak-key distinguisher, we further mount a 13-round key recovery attack on Blink-64, recovering the full 448-bit master key with time complexity $2^{112.15}$ and $2^{56}$ chosen plaintexts. All these distinguishers and key recovery attacks work within the designers' claimed data and time bounds, and our analysis remains consistent with the security of the full-round design of Blink, while offering additional insight into the edge-case behaviors arising from the tweak-key interaction in Blink, and could be potentially informative for future refinements of tweakable block cipher constructions.
## 2025/2150
* Title: Low-Latency Fully Homomorphic Arithmetic Using Parallel Prefix Group Circuit with Primitive Gate Bootstrapping
* Authors: Dohyuk Kim, Sin Kim, Seunghwan Lee, Dong-Joon Shin
* [Permalink](https://eprint.iacr.org/2025/2150)
* [Download](https://eprint.iacr.org/2025/2150.pdf)
### Abstract
Fully Homomorphic Encryption over the Torus (TFHE) is a fully homomorphic encryption scheme that efficiently supports Boolean logic gates by performing gate operations and refreshing ciphertext noise with single gate bootstrapping. However, its operation is limited to simple two-input gates such as AND, OR, XOR and NAND, requiring deep circuits and multiple bootstrapping steps to support more complex arithmetic. In this paper, we propose Primitive Gate Bootstrapping, a new algebraic framework that significantly expands the class of Boolean functions evaluable with a single bootstrapping. By formalizing bootstrappable functions as compositions of linear maps and negacyclic functions, called the Blind-Rotational Function Family (BRFF), we define a subclass, the Primitive Gate Family (PGF). This family includes multi-input hybrid gates such as l-input XOR, 3-input Majority, and AND-XOR, which can all be realized with a single bootstrapping. Building on PGF, we further design a general circuit framework called the Parallel Prefix Group Circuit (PPGC) for efficiently implementing arithmetic and logical operations. PPGC enable n-bit addition, subtraction, comparison, equality, select, minimum/maximum, absolute, and negation with logarithmic depth O(log n) and significantly reduced latency compared to TFHE. In particular, our optimized implementations of addition and subtraction achieve a 1.92|u speedup over TFHE, while the size of the blind rotation key was reduced by approximately 40%. In addition to the two-input addition, we also introduce an efficient technique for multi-input addition, which is particularly useful in applications such as encrypted matrix multiplication. Therefore, it is clear that the PGF-based constructions offer a practically scalable and efficient foundation for depth-sensitive homomorphic computations
## 2025/2151
* Title: Hardness of Problems with Hints in Code-Based Cryptography and Applications to Traitor Tracing
* Authors: Thomas Debris-Alazard, Victor Dyseryn, Duong Hieu Phan
* [Permalink](https://eprint.iacr.org/2025/2151)
* [Download](https://eprint.iacr.org/2025/2151.pdf)
### Abstract
Code-based cryptography has reached maturity for standard primitives such as encryption and digital signatures. However, when it comes to advanced encryption functionalities, particularly in multi-user settings involving collusions among users holding different secret keys, there is still no foundational framework for code-based schemes.
In this work, we address this gap by introducing a multi-receiver encryption scheme with tracing capability based on coding assumptions. This primitive often serves as a foundation for more advanced constructions such as attribute-based or functional encryption.
To achieve this goal, we propose a kernel sampling technique that enables the sampling of secret keys under a common public key, thereby realizing multi-receiver encryption. The resulting construction is as efficient as the underlying public-key encryption scheme, namely Alekhnovich's scheme from FOCS'03. We also introduce new hardness assumptions on problems with hints. These assumptions extend classical code-based problems to handle collusion among dishonest users in the multi-user setting.
In particular, we define the $\ell$-Decoding Problem ($\ell$-DP), the code-based analogue of the $k$-LWE problem in lattices, and provide a reduction from the standard Decoding Problem (DP) to $\ell$-DP. We further introduce structural variants relying on Moderate Density Parity Check (MDPC) codes that we call $\ell$-MDPC-DP.
Based on $\ell$-MDPC-DP, we design the first code-based traitor-tracing encryption scheme. Interestingly, the security of our scheme relies on $\ell$-MDPC-DP and a slight variation called $(\ell,\ell')$-OM-MDPC-DP, the latter of which we prove to be as hard as $\ell$-DP via a polynomial reduction, therefore reducing the security of our scheme to only $\ell$-MDPC-DP. Although no formal reduction from $\ell$-DP to $\ell$-MDPC-DP is given, the definition of $\ell$-MDPC-DP is a natural variant of $\ell$-DP adapted to the multi-user code-based setting. Furthermore, we also provide evidence of $\ell$-MDPC-DP hardness by presenting detailed cryptanalytic arguments.
## 2025/2152
* Title: Sum-check protocol for approximate computations
* Authors: Dor Bitan, Zachary DeStefano, Shafi Goldwasser, Yuval Ishai, Yael Tauman Kalai, Justin Thaler
* [Permalink](https://eprint.iacr.org/2025/2152)
* [Download](https://eprint.iacr.org/2025/2152.pdf)
### Abstract
Motivated by the mismatch between floating-point arithmetic, which is intrinsically approximate, and verifiable computing protocols for exact computations, we develop a generalization of the classical sum-check protocol. Our generalization proves claims of the form $\sum_{x \in \{0,1\}^v} g(x) \approx H$, where $g$ is a low-degree $v$-variate polynomial over an integral domain $\mathbb{U}$. The verifier performs its check in each round of the protocol using a tunable error parameter $\delta$. If $\Delta$ is the error in the prover's initial claim, then the soundness error of our protocols degrades gracefully with $\delta/\Delta$. In other words, if the initial error $\Delta$ is large relative to $\delta$, then the soundness error is small, meaning the verifier is very likely to reject.
Unlike the classical sum-check protocol, which is fundamentally algebraic, our generalization exploits the metric structure of low-degree polynomials. The protocol can be instantiated over various domains, but is most natural over the complex numbers, where the analysis draws on the behavior of polynomials over the unit circle. We also analyze the protocol under the Fiat-Shamir transform, revealing a new intermediate security phenomenon that appears intrinsic to approximation.
Prior work on verifiable computing for numerical tasks typically verifies that a prover exactly executed a computation that only approximates the desired function. In contrast, our protocols treat approximation as a first-class citizen: the verifier's checks are relaxed to accept prover messages that are only approximately consistent with the claimed result.
This establishes the first black-box feasibility result for approximate arithmetic proof systems: the protocol compiler is independent of how arithmetic operations are implemented, requiring only that they satisfy error bounds. This opens a path to verifying approximate computations while sidestepping much of the prover overhead imposed by existing techniques that require encoding real-valued data into finite field arithmetic.
## 2025/2153
* Title: Semigroup-homomorphic Signature
* Authors: Heng Guo, Kun Tian, Fengxia Liu, Zhiyong Zheng
* [Permalink](https://eprint.iacr.org/2025/2153)
* [Download](https://eprint.iacr.org/2025/2153.pdf)
### Abstract
In 2002, Johnson et al. posed an open problem at the Cryptographers' Track of the RSA Conference: how to construct a secure homomorphic signature on a semigroup, rather than on a group. In this paper, we introduce, for the first time, a semigroup-homomorphic signature scheme. Under certain conditions, we prove that the security of this scheme is based on the hardness of the Short Integer Solution (SIS) problem and is tightly secure. Furthermore, we extend it to a linearly semigroup-homomorphic signature scheme over lattices, and this scheme can also ensure privacy.
## 2025/2154
* Title: Optimal Threshold Traitor Tracing
* Authors: Sourav Das, Pratish Datta, Aditi Partap, Swagata Sasmal, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2025/2154)
* [Download](https://eprint.iacr.org/2025/2154.pdf)
### Abstract
Threshold encryption distributes decryption capability across $n$ parties such that any $t$ of them can jointly decrypt a ciphertext, while smaller coalitions learn nothing. However, once $t$ or more parties collude, traditional threshold schemes provide no accountability: a coalition of $t$ or more parties can pool its keys into a pirate decoder that enables unrestricted decryption, all without any risk of being exposed. To address this, Boneh, Partap, and Rotem [CRYPTO '24] introduced threshold traitor tracing (TTT), which equips threshold encryption with traceability. Yet, all known TTT schemes either suffer from parameter sizes growing with at least $n^{1/3}$, or rely on indistinguishability obfuscation to achieve optimal parameters.
In this paper, we present the first TTT schemes with optimal parameters, where public keys, secret keys, and ciphertexts are all bounded by ${\sf poly}(\lambda,\log n)$, built solely from standard cryptographic tools and assumptions. Our first construction relies on the decisional Bilinear DiffierCoHellman (DBDH) assumption in prime order bilinear groups. Our second construction, based on the Learning with Errors (LWE) assumption, is plausibly post-quantum secure, and supports ramp-thresholds where decryption requires a larger coalition than those tolerated by security. Both of our constructions provide traceability against coalitions of arbitrary sizes.
To achieve these results, we introduce a new primitive, Attribute-Based Threshold Encryption (ABTE), which generalizes both threshold and attribute-based encryption. We then combine ABTE with Mixed Functional Encryption through a new compiler to obtain our TTT schemes. We believe ABTE is a powerful primitive that may have independent applications beyond optimal TTT.
## 2025/2155
* Title: A New Approach to Arguments of Quantum Knowledge
* Authors: James Bartusek, Ruta Jawale, Justin Raizes, Kabir Tomer
* [Permalink](https://eprint.iacr.org/2025/2155)
* [Download](https://eprint.iacr.org/2025/2155.pdf)
### Abstract
We construct a publicly-verifiable non-interactive zero-knowledge argument system for QMA with the following properties of interest.
1. Transparent setup. Our protocol only requires a uniformly random string (URS) setup. The only prior publicly-verifiable NIZK for QMA (Bartusek and Malavolta, ITCS 2022) requires an entire obfuscated program as the common reference string.
2. Extractability. Valid QMA witnesses can be extracted directly from our accepting proofs. That is, we obtain a publicly-verifiable non-interactive argument of quantum knowledge, previously only known in a privately-verifiable setting (Coladangelo, Vidick, and Zhang, CRYPTO 2020).
Our construction introduces a novel ZX QMA verifier with "strong completeness" and builds upon the coset state authentication scheme from (Bartusek, Brakerski, and Vaikuntanathan, STOC 2024) within the context of QMA verification. Along the way, we establish new properties of the authentication scheme.
The security of our construction rests on the heuristic use of a post-quantum indistinguishability obfuscator. Rather than rely on the full-fledged classical oracle model (i.e. ideal obfuscation), we isolate a particular game-based property of the obfuscator that suffices for our proof, which we dub the evasive composability heuristic.
As an additional contribution, we study a general method for replacing heuristic use of obfuscation with heuristic use of hash functions in the post-quantum setting. In particular, we establish security of the ideal obfuscation scheme of Jain, Lin, Luo, and Wichs (CRYPTO 2023) in the quantum pseudorandom oracle model (QPrO), which can be heuristically instantiated with a hash function. This gives us NIZK arguments of quantum knowledge for QMA in the QPrO, and additionally allows us to translate several quantum-cryptographic results that were only known in the classical oracle model to results in the QPrO.
## 2025/2156
* Title: Multi-Verifier Keyed-Verification Anonymous Credentials
* Authors: Jan Bobolz, Emad Heydari Beni, Anja Lehmann, Omid Mirzamohammadi, Cavit |uzbay, Mahdi Sedaghat
* [Permalink](https://eprint.iacr.org/2025/2156)
* [Download](https://eprint.iacr.org/2025/2156.pdf)
### Abstract
Keyed-Verification anonymous credentials (KVAC) enable privacy-preserving authentication and can be seen as the symmetric primitive of conventional anonymous credentials: issuance and verification of credentials requires a shared secret key. The core advantage of KVACs is that they can be realized without pairings, which still appears to be a significant bottleneck when it comes to real-world adoption. KVACs provide all the benefits from anonymous credentials, in particular multi-show unlinkability, but only work in the setting where the issuer and verifier are the same entity, limiting the applications they can be used in. In this work we extend the idea of keyed-verification credential to a setting where again multiple verifiers are supported, each sharing an individual secret key with the issuer. We formally introduce this as multi-verifier keyed-verification anonymous credentials (mKVACs). While users must now get verifier-specific credentials, each credential still provides multi-show unlinkability. In terms of security, mKVAC naturally strengthens the single-verifier variant, as it guarantees that corruption of any verifier does not impact unforgeability guarantees for other verifiers. The main challenge therein is to not trade this added flexibility for privacy, and hide the verifier's identity in the credential issuance. We provide formal definitions of all desired security and privacy features and propose a provably secure and pairing-free construction. Along the way, we develop a new KVAC-like primitive that authenticates group elements and offers statistical privacy, solving the open problem of combining multi-verifier support and pairing-freeness. Finally, we demonstrate practicality of our protocol via implementation benchmarks.
## 2025/2157
* Title: Taming the Stack: Proof-Preserving Blockwise FrodoKEM on RISC-V Devices with Hardware Acceleration
* Authors: Frank Hartmann
* [Permalink](https://eprint.iacr.org/2025/2157)
* [Download](https://eprint.iacr.org/2025/2157.pdf)
### Abstract
FrodoKEM provides conservative post-quantum security through unstructured lattices, yet its deployment on embedded systems is historically constrained by high memory requirements. While state-of-the-art implementations mitigate this by generating the public matrix on-the-fly, they remain bottlenecked by the sequential generation of secret matrices, which enforces a rigid trade-off between stack usage and recomputation overhead. To address this, we propose a blockwise secret generation mechanism that enables efficient random access to arbitrary matrix tiles. We formally prove that this modification is indistinguishable from the standard specification in the Random Oracle Model, thereby preserving IND-CCA2 security. By evaluating this approach on a 32-bit RISC-V core with custom cryptographic extensions, we demonstrate tiled encapsulation and key generation strategies that maintain constant transient stack usage ($\approx$2--3 kB) across all parameter sets. This design effectively decouples memory footprint from algorithmic complexity, enabling flexible buffering strategies that optimize performance according to the available heap memory of the target platform.
## 2025/2158
* Title: Efficient Batched IBE from Lattices
* Authors: Saisi Xiong, Yijian Zhang, Jie Chen
* [Permalink](https://eprint.iacr.org/2025/2158)
* [Download](https://eprint.iacr.org/2025/2158.pdf)
### Abstract
In this work, we present the first construction of batched IBE scheme from lattices. The security is proven in the standard model under the succinct LWE assumption. Prior batched IBE schemes are only known from pairing-based assumptions. Moreover, our lattice-based batched IBE scheme is shown to be highly efficient, as the master public key, decryption key, and ciphertext are independent of the batch size $B$. In contrast, existing pairing-based schemes cannot provide the post-quantum security guarantee, and their master public keys have to scale with $B$.
Technically, we mainly rely on an insightful observation: batched IBE can be obtained solely from Inner-Product Encryption (IPE). To satisfy the efficiency requirements of batched IBE, we require an IPE scheme that owns two important features: decomposable key generation and compact components. Finally, we show how to construct such an IPE scheme from the well-known BGG+14 IPE scheme via careful modification.
## 2025/2159
* Title: One Fell Swoop: A Single-Trace Key-Recovery Attack on the Falcon Signing Algorithm
* Authors: Kang Li, Shouran Ma, Haochen Dou, Qian Guo
* [Permalink](https://eprint.iacr.org/2025/2159)
* [Download](https://eprint.iacr.org/2025/2159.pdf)
### Abstract
Falcon, a lattice-based signature scheme selected for NIST post-quantum standardization, is notable for its compact signature size alongside a complex signing procedure involving extensive floating-point arithmetic.
Prior side-channel attacks on Falcon, while demonstrating vulnerabilities, have consistently required a large number of power traces for successful key recovery; this critical efficiency gap means previously reported attacks are often impractical in real-world scenarios where trace collection is limited.
This paper presents a new single-trace attack on the Falcon. We identify and exploit novel leakage points within the floating-point conversion and Fast Fourier Transform (FFT) routines during the secret key expansion, which allow us to progressively partition the possible values of the secret key coefficients. By identifying a sufficient number of these coefficients, we establish a system of linear equations that can be solved to recover the entire secret key.
Our attack is particularly critical for the \texttt{sign\_dyn} design---the memory-efficient implementation adopted in important cryptographic libraries and reference implementations---as it executes key expansion during every signature operation. We emphasize that this is the \textbf{first single-trace attack on the Falcon signing procedure itself}, providing a more compelling threat scenario than previous work.
We validate our attack on an ARM Cortex-M4 microcontroller, demonstrating a 100\% key recovery success rate with just a single power trace for both Falcon-512 and Falcon-1024 in both signing designsrCo\texttt{sign\_tree} and \texttt{sign\_dyn}, compiled at the \texttt{-O0} level. While the \texttt{-O3} optimization level mitigates some leakages, our multi-trace attack remains effective in the practically used \texttt{sign\_dyn} design, recovering 80 out of 100 Falcon-512 keys with only 5 traces. Our findings expose a critical implementation vulnerability in Falcon, highlighting the urgent necessity of integrating countermeasures to protect Falcon in real-world applications.
## 2025/2160
* Title: Pairing-Based SNARGs with Two Group Elements
* Authors: Gal Arnon, Jesko Dujmovic, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2025/2160)
* [Download](https://eprint.iacr.org/2025/2160.pdf)
### Abstract
SNARGs are cryptographic primitives that allow a prover to demonstrate membership in an NP language while sending a proof that is much smaller than the witness. In this work, we focus on the succinctness of publicly-verifiable group-based SNARGs, analyzed in a model that combines both a generic bilinear group $(\mathbb{G}_{1} \times \mathbb{G}_{2} \to \mathbb{G}_{T})$ and a random oracle (the GGM + ROM).
We construct the first publicly-verifiable SNARG in the GGM + ROM where the proof consists of exactly $2$ elements of $\mathbb{G}_{1}$ and no additional bits, achieving the smallest proof size among all known publicly verifiable group-based SNARGs. Our security analysis is tight, ensuring that the construction incurs no hidden security losses. Concretely, when instantiated with the BLS12-381 curve for 128-bit security, our scheme yields a proof size of $768$ bits, nearly a $2\times$ improvement over the best known pairing-based SNARG. While our scheme is not yet concretely efficient, it demonstrates the feasibility of ultra-short proofs and opens the door to future practical instantiations.
Complementing this construction, we establish a new lower bound for group-based SNARGs. We prove that under mild and natural restrictions on the verifier (which are satisfied by all known schemes) no SNARG exists in the Maurer GGM + ROM with a proof that consists of a single group element (assuming one-way functions). This substantially strengthens the lower bound of Groth, which was more restrictive and did not extend to settings with a random oracle.
## 2025/2161
* Title: Attacks and Remedies for Randomness in AI: Cryptanalysis of PHILOX and THREEFRY
* Authors: Jens Alich, Thomas Eisenbarth, Hossein Hadipour, Gregor Leander, Felix M|nchtle, Yevhen Perehuda, Shahram Rasoolzadeh, Jonas Sander, Cihangir Tezcan
* [Permalink](https://eprint.iacr.org/2025/2161)
* [Download](https://eprint.iacr.org/2025/2161.pdf)
### Abstract
In this work, we address the critical yet understudied question of the security of the most widely deployed pseudorandom number generators (PRNGs) in AI applications. We show that these generators are vulnerable to practical and low-cost attacks. With this in mind, we conduct an extensive survey of randomness usage in current applications to understand the efficiency requirements imposed in practice. Finally, we present a cryptographically secure and well-understood alternative, which has a negligible effect on the overall AI/ML workloads. More generally, we recommend the use of cryptographically strong PRNGs in all contexts where randomness is required, as past experience has repeatedly shown that security requirements may arise unexpectedly even in applications that appear uncritical at first.
## 2025/2162
* Title: You Only Decapsulate Once: Ciphertext-Independent Single-Trace Passive Side-Channel Attacks on HQC
* Authors: Zhenzhi Lai, Ruiyi Zhang, Zhiyuan Zhang, Julius Hermelink, Michael Schwarz, Van-Thuan Pham, Udaya Parampalli
* [Permalink](https://eprint.iacr.org/2025/2162)
* [Download](https://eprint.iacr.org/2025/2162.pdf)
### Abstract
Hamming Quasi-Cyclic (HQC) has recently been selected by NIST, after the Round 4 submission, as a postquantum key encapsulation mechanism (KEM) standard and will soon be widely deployed. Therefore, it is important to ensure its implementation is constant-time, i.e., resistant to side-channel attacks. Existing timing attacks on HQC exploit non-constant-time source code and the decryption that is vulnerable to chosen-ciphertext attacks. These active attacks require constructing thousands of invalid ciphertexts, and thus, they can be easily detected. The latest HQC implementation has mitigated all these attacks by making its source code constant-time.
In this work, we provide a new perspective on reviewing the implementation of HQC and exploiting timing leakages. For the first time, we show that an attacker can recover the secret key of HQC without targeting the CCA-insecure decryption and internal states of message decryption. Specifically, an attacker can exploit the timing leakages that occur when processing sparse vectors, which are ciphertext-independent, to recover the secret key by measuring the leakages only once. We find two such timing leakages in the latest stable HQC implementation, supposedly constant-time, and practically extract the leakages even when the process is protected by AMD Secure Encryption Virtualization. We also show that a power side-channel can extract similar leakages on embedded devices.
Our findings apply to all code-based KEMs that are submitted to the NIST Round 4 PQC submission. We show that an attacker can also perform similar passive attacks to recover the session key of BIKE and Classic McEliece. To help write constant-time code, we propose and test a workflow that uses CT-grind when developing the code. We find that CT-grind can effectively find all timing leakages in various implementations of HQC. Therefore, we suggest that cryptographic developers constantly use constant-time analysis tools when developing code.
## 2025/2163
* Title: Correction-Based Fault Attack Against Randomized MAYO
* Authors: Mohamed Abdelmonem, Lejla Batina, Durba Chatterjee, H|Nvard Raddum
* [Permalink](https://eprint.iacr.org/2025/2163)
* [Download](https://eprint.iacr.org/2025/2163.pdf)
### Abstract
This paper introduces a novel and practical fault injection attack targeting the randomized version of the MAYO post-quantum signature scheme. While prior attacks on MAYO either relied on deterministic signing modes or specific memory assumptions, our attack succeeds without such constraints. By exploiting the inherent structural properties of MAYO signatures, we combine targeted fault injections with signature correction techniques to extract partial information about the secret oil space. By systematically accumulating such partial information across multiple fault-induced signatures and utilizing linear dependencies among oil vectors, we present an efficient method for achieving full secret key recovery. The attack requires only one fault injection per oil coefficient, repeated a small (i.e., 8, 17, 10, or 12 for the different MAYO versions, respectively) number of times. We demonstrate the targeted fault injection attack on a MAYO implementation on an ARM Cortex-M3 processor via clock glitching, establishing the feasibility of the attack in practice. Our approach is validated through simulations, and a detailed computational cost analysis is provided. Additionally, we demonstrate the ineffectiveness of some previously proposed countermeasures against our attack, thereby highlighting the urgent need for developing more robust protection mechanisms for multivariate post-quantum signature schemes, such as MAYO.
## 2025/2164
* Title: Hardness and Algorithms for Batch LPN under Dependent Noise
* Authors: Xin Li, Songtao Mao, Zhaienhe Zhou
* [Permalink](https://eprint.iacr.org/2025/2164)
* [Download](https://eprint.iacr.org/2025/2164.pdf)
### Abstract
We study the Batch Learning Parity with Noise (LPN) variant, where the oracle returns $k$ samples in a batch, and draws the noise vector from a joint noise distribution $\mathcal{D}$ on $\mathbb{F}_2^k$ (instead of i.i.d.). This model captures a broad range of correlated or structured noise patterns studied in cryptography and learning theory, and was formally defined in recent work by Golowich, Moitra, and Rohatgi (FOCS 2024). Consequently, understanding which distributions preserve the hardness of LPN has become an important question.
On the hardness side, we design several reductions from standard LPN to Batch LPN. Our reductions provide a more comprehensive characterization of hard distributions. Specifically, we show that a Batch LPN instance is as hard as standard LPN with noise rate $\eta:=\frac{1}{2}-\varepsilon$ provided that its noise distribution $\mathcal{D}$ satisfies one of the following:
1. The noise distribution $\mathcal{D}$ satisfies a mild Fourier-analytic condition (specifically, $\sum_{s\neq 0}|\widehat{P}_{\mathcal{D}}(s)|\le 2\varepsilon$).
2. The noise distribution $\mathcal{D}$ is $\Omega(\eta \cdot k 2^{-k})$-dense (i.e., every error pattern occurs with probability at least $\Omega(\eta \cdot k 2^{-k})$) for $\eta < 1/k$.
3. The noise distribution $\mathcal{D}$ is a $\delta$-Santha-Vazirani source. Our reduction improves the allowable bias $\delta$ from $O(2^{-k}\varepsilon)$ (in Golowich et al.) to $O(2^{-k/2}\varepsilon)$.
On the algorithmic side, we design an algorithm for solving Batch LPN whenever the noise distribution assigns sufficiently small probability to at least one point, which gives an algorithm--hardness separation for Batch LPN. Our algorithm can be seen as an extension of Arora and Ge's (ICALP 2011) linearization attack.
Our reduction is based on random affine transformations, developed and analyzed through the lens of Fourier analysis, providing a general framework for studying various LPN variants.
## 2025/2165
* Title: Extending and Accelerating Inner Product Masking with Fault Detection via Instruction Set Extension
* Authors: Songqiao Cui, Geng Luo, Junhan Bao, Josep Balasch, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/2165)
* [Download](https://eprint.iacr.org/2025/2165.pdf)
### Abstract
Inner product masking is a well-studied masking countermeasure against side-channel attacks. IPM-FD further extends the IPM scheme with fault detection capabilities. However, implementing IPM-FD in software especially on embedded devices results in high computational overhead. Therefore, in this work we perform a detailed analysis of all building blocks for IPM-FD scheme and propose a Masked Processing Unit to accelerate all operations, for example multiplication and IPM-FD specific Homogenization. We can then offload these computational extensive operations with dedicated hardware support. With only $4.05\%$ and $4.01\%$ increase in Look-Up Tables and Flip-Flops (Random Number Generator excluded), respectively, compared with baseline CV32E40p RISC-V core, we can achieve up to $16.55\times$ speed-up factor with optimal configuration. We then practically evaluate the side-channel security via uni- and bivariate Test Vector Leakage Assessment which exhibits no leakage. Finally, we use two different methods to simulate the injected fault and confirm the fault detection capability of up to $k-1$ faults, with $k$ being the replication factor.
## 2025/2166
* Title: How to Prove Post-Quantum Security for Succinct Non-Interactive Reductions
* Authors: Alessandro Chiesa, Zijing Di, Zihan Hu, Yuxi Zheng
* [Permalink](https://eprint.iacr.org/2025/2166)
* [Download](https://eprint.iacr.org/2025/2166.pdf)
### Abstract
Hash-based succinct non-interactive arguments (SNARGs) are widely used in practice, owing to their ease of deployment, notable efficiency, and post-quantum properties. They are constructed via the BCS transformation, which combines an interactive oracle proof (IOP) and a hash-based vector commitment. This success has motivated the study of hash-based succinct non-interactive reductions (SNRDXs), used for recursively ensuring the correctness of distributed computations, by extending the BCS transformation to work with an interactive oracle reduction (IOR) rather than an IOP.
We prove that hash-based SNRDXs constructed from IORs are secure in the quantum random oracle model (QROM), provided the IOR satisfies a natural post-quantum analogue of state-restoration security; moreover, we show that (classical) round-by-round security implies post-quantum state-restoration security. Our results thus achieve a post-quantum analogue of the classical security of SNRDXs in the ROM, and generalize a prior result about SNARGs in the QROM to cover recent SNRDXs constructions.
Moreover, for SNRDXs we propose and achieve an adaptively-secure straightline quantum extraction property in the QROM, while prior work obtains non-adaptive security for SNARGs in the QROM. Along the way, we develop a modular framework for proving the security of the (extended) BCS transformation based on a new quantum extraction property for vector commitments (which we prove is achieved by Merkle commitments), mirroring classical security analyses and departing from prior "monolithic" post-quantum analyses. This demands a new commutator bound that shows the almost-commutativity between quantum extraction and quantum oracle queries, by bounding a natural classical extraction property.
## 2025/2167
* Title: 1-Adaptive Weak Pseudorandom Functions
* Authors: Davide Li Calsi, Dominique Schr||der, Julian Thomas
* [Permalink](https://eprint.iacr.org/2025/2167)
* [Download](https://eprint.iacr.org/2025/2167.pdf)
### Abstract
A message authentication code (MAC) ensures authenticity and integrity in symmetric-key settings. The CarterrCoWegmanrCoShoup (CWS) paradigm establishes that MACs for arbitrary-length messages can be built in a black-box way using a single call to a pseudorandom function (PRF) on a random input. More than a decade ago, Dodis, Kiltz, Pietrzak, and Wichs left open whether weak pseudorandom functions (wPRFs) would suffice in this construction.
This work establishes tight upper and lower bounds that precisely characterize the minimal computational assumptions needed for the security of the CWS paradigm.
On the negative side, we prove that weak PRFs are insufficient to instantiate the CWS paradigm. On the positive side, we introduce a new primitive, the 1-adaptive weak pseudorandom function (1-awPRF), which guarantees pseudorandomness for polynomially many non-adaptive queries followed by one adaptive query. We show that 1-awPRFs are sufficient to secure CWS in a black-box manner.
Finally, we construct 1-adaptive weak pseudorandom functions in a black-box way from standard cryptographic assumptions, using a new randomized design paradigm that treats randomization as a fundamental structural element. Instantiating our generic construction under the Decisional Diffie Hellman and Learning with Errors assumptions yields concrete and efficient realizations. These lead to more efficient MAC schemes and illustrate how weak and abstract building blocks can be transformed into stronger and practically useful cryptographic constructions.
## 2025/2168
* Title: Hybrid Subsupport Guessing: A New Hybrid Technique for the Rank Decoding Problem
* Authors: Hugo Beeloo-Sauerbier Couv|-e, Antonia Wachter-Zeh, Violetta Weger
* [Permalink](https://eprint.iacr.org/2025/2168)
* [Download](https://eprint.iacr.org/2025/2168.pdf)
### Abstract
The Rank Decoding Problem (R-DP) has gained a lot of attention due to the competitive KEM proposals ROLLO and RQC, as well as the more recent signature scheme RYDE, the latter being a second-round candidate in the ongoing NIST post-quantum standardization process. While previous attacks on the R-DP are based on combinatorial methods, the seminal work of [Bardet et al., 2020] has shown the potential of attacks that use algebraic modelings, breaking the proposed parameters of ROLLO and RQC. These algebraic attacks model the R-DP as a large system of equations. For most parameter ranges, this system is underdetermined; hence, the algebraic attack first needs to perform several guessing steps to obtain a reduced instance for which the system of equations is overdetermined. These steps, in essence, guess a supersupport of the unknown error support, making this attack a hybrid approach between combinatorial and algebraic solvers.
In this paper, we present a novel type of guessing step based on searching a subsupport of the error support. While supersupport guessing only reduces the length and dimension of the code, subsupport guessing instead reduces the length and the rank weight of the sought-after error vector. This introduces an additional method for instance reduction compatible with supersupport guessing. Both types of guessing step can be performed sequentially in hybrid attacks, and their numbers can be optimized to outperform current hybrid attacks. We provide experimentally supported comparisons of the attack complexities with and without the novel guessing technique. We measure the impact of our new hybrid attack on the RYDE parameters; for the NIST security category 5 parameters, we decrease the hybrid MaxMinors attack complexity from 301 bits to 272 bits, outperforming all other known rank decoders and tightening the margin above the 256 threshold.
For the other security levels, we decrease the complexities to be on par with the best performing combinatorial decoders.
## 2025/2169
* Title: Multivariate exponential equations with unknown coefficients
* Authors: Trey Li
* [Permalink](https://eprint.iacr.org/2025/2169)
* [Download](https://eprint.iacr.org/2025/2169.pdf)
### Abstract
We introduce a novel class of equations defined over Euclidean domains. These abstract equations establish a unified framework for deriving new, concrete computational problems useful for cryptography. We prove that solving a single such equation is NP-hard. For systems of these equations, we further prove NP-hardness, average-case hardness, random self-reducibility, search-to-decision reducibility, and trapdoorizability. Based on the hardness of solving these systems, we construct various cryptographic primitives. Our results are proved in an abstract, domain-agnostic manner and hold for a wide range of Euclidean domains. This generality allows the framework to accommodate rich mathematical structures, providing both theoretical depth and flexibility for diverse cryptographic applications.
## 2025/2170
* Title: Lattice-Based Linkable Ring Signatures for Anonymous and Accountable Whistleblowing
* Authors: Vishal Pareek, Aditi Kar Gangopadhyay, Sugata Gangopadhyay
* [Permalink](https://eprint.iacr.org/2025/2170)
* [Download](https://eprint.iacr.org/2025/2170.pdf)
### Abstract
Ring signatures allow an individual to sign a message on behalf of a group in such a way that the verifier can only confirm that someone in the group signed it, but cannot identify the actual signer. This strong anonymity, while desirable, may also be exploited for repeated or harmful activities. Linkable ring signatures mitigate this issue by enabling the system to recognise whether two signatures originate from the same signer, while still keeping the signer anonymous. Such constructions are essential in domains like e-voting, e-cash, privacy-preserving blockchain systems, and whistleblowing, where detecting repeated actionsrCosuch as double-spending or double-votingrCois necessary to maintain system reliability.
In this paper, we present a lattice-based linkable ring signature scheme designed to withstand quantum-era adversaries. The framework relies on exact and efficient zero-knowledge proofs, and employs a weak pseudorandom function (wPRF) to enable linkability. To demonstrate both ring membership and the generation of a unique tag, we integrate a Merkle tree accumulator, which also streamlines the verification steps. The scheme is instantiated using concrete parameter choices, allowing us to precisely evaluate how the signature size scales with different ring sizes. An important feature of our design is that it eliminates the need for trapdoor techniques, yet still produces a signature of roughly 0.22 MB when the ring contains 2^10 users. We further outline practical application scenarios, such as anonymous but accountable whistleblowing, to highlight the usefulness of the proposed construction.
## 2025/2171
* Title: Efficient GHASH and POLYVAL Implementation Using Polynomial Multiplication: Optimized 64-bit Decomposition with Bit-Reversal Elimination
* Authors: Mamone Tarsha Kurdi, Niels M||ller
* [Permalink](https://eprint.iacr.org/2025/2171)
* [Download](https://eprint.iacr.org/2025/2171.pdf)
### Abstract
We present an optimized implementation of the GHASH and POLYVAL authentication algorithms used in AES-GCM and AES-GCM-SIV that eliminates the computational overhead of bit-reversal operations. Our approach computes these universal hash functions directly in bit-reversed representation, matching the native format used by carry-less multiplication instructions available on modern processors. The algorithm exploits 64-bit polynomial primitives and parallel execution on superscalar architectures. We achieve performance of 0.34 cycles/byte on POWER9 (35% faster than OpenSSL) and 0.33 cycles/byte on Intel Comet Lake (11% faster than OpenSSL), representing a 32-fold improvement over table-based software implementations. Combined with hardware accelerated AES, the complete AES-GCM mode achieves 1.12 cycles/byte throughput. For platforms with hardware carry-less multiplication (x86 PCLMULQDQ, ARM PMULL, PowerPC vpmsumd), the R/F algorithm achieves re+1.7|u speedup over Karatsuba. For portable software implementations without hardware acceleration, we demonstrate that Karatsuba remains 1.4-1.6|u faster due to reduced multiplication count.
## 2025/2172
* Title: Crypto Wars in Secure Messaging: Covert Channels in Signal Despite Leaked Keys
* Authors: Mohammadamin Rakeei, Rosario Giustolisi, Andy Rupp, Chuanwei Lin, Gabriele Lenzini
* [Permalink](https://eprint.iacr.org/2025/2172)
* [Download](https://eprint.iacr.org/2025/2172.pdf)
### Abstract
End-to-end encryption (E2EE) is the foundation of modern secure messaging, with the Signal protocol as the de facto standard in applications such as Signal, WhatsApp, Facebook Messenger and Google Messages. At the same time, the deployment of E2EE has led to growing pressure from authorities to decrypt user traffic under lawful enforcement. This raises a critical question: if an adversary can routinely decrypt Signal messages (for example via a mandated access or a leaked key), can users still communicate securely and covertly?
We address this question through the lens of anamorphic encryption, which enables hidden communication within seemingly legitimate ciphertexts, even against an adversary who can decrypt them. We design two constructions that embed covert channels into the existing Signal Double Ratchet protocol. Concretely, we show how to embed covert messages (i) into Diffie-Hellman keys used in the asymmetric ratchet, or (ii) into authentication tags produced in the symmetric ratchet. Our techniques are compatible with existing Signal-style deployments and require no changes by the service provider.
We formalize security in threat models that capture adversaries with decryption capabilities granted through lawful-access mechanisms, and prove that the resulting protocol transcripts are indistinguishable from those of standard Signal. We implement our constructions in the official Signal library and Android client, and show that they incur low overhead and are practical in real-world settings. Our results show that covert communication channels can persist even when conventional E2EE guarantees are compromised.
--- Synchronet 3.21a-Linux NewsLink 1.2