From Newsgroup: sci.crypt

## In this issue
1. [2025/379] A Complete Security Proof of SQIsign
2. [2025/1365] Towards Efficient Privacy-Preserving Machine ...
3. [2025/1366] NOPE: Strengthening domain authentication with ...
4. [2025/1367] Encrypted Matrix Multiplication Using 3-Dimensional ...
5. [2025/1368] Post-Quantum Readiness in EdDSA Chains
6. [2025/1369] Cube-Attack-Like Cryptanalysis of Keccak-Based ...
7. [2025/1370] Randomized Distributed Function Computation (RDFC): ...
8. [2025/1371] Securing Credential Sequence Verification
9. [2025/1372] Gluon W: A Cryptocurrency Stabilization Protocol
10. [2025/1373] A Zero-Knowledge Proof for the Syndrome Decoding ...
11. [2025/1374] An Attack to Universally Composable Commitments ...
12. [2025/1375] On the (strong) linkability of Linkable Ring Signatures
13. [2025/1376] On Hull Attacks on the Module Lattice Isomorphism ...
14. [2025/1377] More Practical Non-interactive Encrypted ...
15. [2025/1378] Tight Lower Bound on Witness Update Frequency in ...
16. [2025/1379] Enhancing Scale and Shift Invariance in Deep ...
17. [2025/1380] Quantum Composable and Contextual Security ...
18. [2025/1381] Blockchain-Based Decentralized Domain Name System
19. [2025/1382] Using Learning with Rounding to Instantiate Post- ...
20. [2025/1383] An Efficient Circuit Synthesis Framework for TFHE ...
21. [2025/1384] Silent Threshold Encryption with One-Shot Adaptive ...
22. [2025/1385] Hypersphere Secure Sketch Revisited: Probabilistic ...
23. [2025/1386] How to Tolerate Typos in Strong Asymmetric PAKE
24. [2025/1387] Fast Final Exponentiation on BW and BLS Curves with ...
25. [2025/1388] Collaborative zkSNARKs with Sublinear Prover Time ...
26. [2025/1389] Verification Cost Asymmetry in Cognitive Warfare: A ...
27. [2025/1390] Optimizing Backend Verification in zk-Rollup ...
28. [2025/1391] Inverse Discrete Logarithm - Post-Quantum take on a ...
29. [2025/1392] FLEX rCo Capital-Efficient Optimistic Bridges with ...
30. [2025/1393] Polynomial Lattices for the BIKE Cryptosystem
31. [2025/1394] Peeking Into the Future: MPC Resilient to Super- ...
32. [2025/1395] A Security Comment on ``A Security-Enhanced ...
33. [2025/1396] A Generalized Wiener-type Attack Against a Family ...
34. [2025/1397] Starfighters rCo on the general applicability of X-Wing
35. [2025/1398] General Review of Hash-Based Signatures
36. [2025/1399] Tempo: ML-KEM to PAKE Compiler Resilient to Timing ...
37. [2025/1400] RGB I.0: Scalable consensus for client-side ...
38. [2025/1401] Automated Tool for Meet-in-the-Middle Attacks with ...
39. [2025/1402] Can we Speed up Information Set Decoding by Using ...
40. [2025/1403] Faster Bootstrapping for CKKS with Less Modulus ...
41. [2025/1404] Optimistic Message Dissemination
42. [2025/1405] Two-Tier Black-box Blockchains and Application to ...
43. [2025/1406] Scalable Secure Multiparty Computation with Perfect ...
44. [2025/1407] A Flexible Hardware Design Tool for Fast Fourier ...
45. [2025/1408] $\mathsf{qedb}$: Expressive and Modular Verifiable ...
46. [2025/1409] Oblivious (Un)Learning of Extremely Randomized Trees
47. [2025/1410] Nakamoto Consensus from Multiple Resources
48. [2025/1411] BACON: An Improved Vector Commitment Construction ...
49. [2025/1412] AVPEU: Anonymous Verifiable Presentations with ...
## 2025/379
* Title: A Complete Security Proof of SQIsign
* Authors: Marius A. Aardal, Andrea Basso, Luca De Feo, Sikhar Patranabis, Benjamin Wesolowski
* [Permalink](https://eprint.iacr.org/2025/379)
* [Download](https://eprint.iacr.org/2025/379.pdf)
### Abstract
SQIsign is the leading digital signature from isogenies. Despite the many improvements that have appeared in the literature, all its recents variants lack a complete security proof. In this work, we provide the first full security proof of SQIsign, as submitted to the second round of NIST's on-ramp track for digital signatures.
To do so, we introduce a new framework, which we call Fiat-Shamir with hints, that captures all those protocols where the simulator needs additional information to simulate a transcript. Using this framework, we show that SQIsign is EUF-CMA secure in the ROM, assuming the hardness of the One Endomorphism problem with hints, or the hardness of the Full Endomorphism Ring problem with hints together with a hint indistinguishability assumption; all assumptions, unlike previous ones in the literature, are non-interactive. Along the way, we prove several intermediate results that may be of independent interest.
## 2025/1365
* Title: Towards Efficient Privacy-Preserving Machine Learning: A Systematic Review from Protocol, Model, and System Perspectives
* Authors: Wenxuan Zeng, Tianshi Xu, Yi Chen, Yifan Zhou, Mingzhe Zhang, Jin Tan, Cheng Hong, Meng Li
* [Permalink](https://eprint.iacr.org/2025/1365)
* [Download](https://eprint.iacr.org/2025/1365.pdf)
### Abstract
Privacy-preserving machine learning (PPML) based on cryptographic protocols has emerged as a promising paradigm to protect user data privacy in cloud-based machine learning services. While it achieves formal privacy protection, PPML often incurs significant efficiency and scalability costs due to orders of magnitude overhead compared to the plaintext counterpart. Therefore, there has been a considerable focus on mitigating the efficiency gap for PPML. In this survey, we provide a comprehensive and systematic review of recent PPML studies with a focus on cross-level optimizations. Specifically, we categorize existing papers into protocol level, model level, and system level, and review progress at each level. We also provide qualitative and quantitative comparisons of existing works with technical insights, based on which we discuss future research directions and highlight the necessity of integrating optimizations across protocol, model, and system levels. We hope this survey can provide an overarching understanding of existing approaches and potentially inspire future breakthroughs in the PPML field. As the field is evolving fast, we also provide a public GitHub repository to continuously track the developments, which is available at https://github.com/PKU-SEC-Lab/Awesome-PPML-Papers.
## 2025/1366
* Title: NOPE: Strengthening domain authentication with succinct proofs
* Authors: Zachary DeStefano, Jeff J. Ma, Joseph Bonneau, Michael Walfish
* [Permalink](https://eprint.iacr.org/2025/1366)
* [Download](https://eprint.iacr.org/2025/1366.pdf)
### Abstract
Server authentication assures users that they are communicating with a server that genuinely represents a claimed domain. Today, server authentication relies on certification authorities (CAs), third parties who sign statements binding public keys to domains. CAs remain a weak spot in Internet security, as any faulty CA can issue a certificate for any domain. This paper describes the design, implementation, and experimental evaluation of NOPE, a new mechanism for server authentication that uses succinct proofs (for example, zero-knowledge proofs) to prove that a DNSSEC chain exists that links a public key to a specified domain.
The use of DNSSEC dramatically reduces reliance on CAs, and the small size of the proofs enables compatibility with legacy infrastructure, including TLS servers, certificate formats, and certificate transparency. NOPE proofs add minimal performance overhead to clients, increasing the size of a typical certificate chain by about 10% and requiring just over 1 ms to verify. NOPErCOs core technical contributions (which generalize beyond NOPE) include efficient techniques for representing parsing and cryptographic operations within succinct proofs, which reduce proof generation time and memory requirements by nearly an order of magnitude.
## 2025/1367
* Title: Encrypted Matrix Multiplication Using 3-Dimensional Rotations
* Authors: Hannah Mahon, Shane Kosieradzki
* [Permalink](https://eprint.iacr.org/2025/1367)
* [Download](https://eprint.iacr.org/2025/1367.pdf)
### Abstract
Fully homomorphic encryption (FHE) enables computations over encrypted data without the need for decryption. Recently there has been an increased interest in developing FHE based algorithms to facilitate encrypted matrix multiplication (EMM) due to rising data security concerns surrounding cyber-physical systems, sensor processing, blockchain, and machine learning. Presently, FHE operations have a high computational overhead, resulting in an increased need for low operational complexity algorithms to compensate. We present a novel matrix encoding and EMM algorithm for power-of-2 cyclotomic based rings, utilizing three-dimensional rotations which offer improvements over the one-dimensional rotations used in previous work. We encode each $d \times d$ matrix as a single, batch-encoded, ciphertext, with minimum ciphertext size $d^3$. The proposed algorithm improves the number of plaintext-ciphertext multiplications from $O(d)$ to $O(1)$ and the number of rotations from $O(d)$ to $O(\log_2{d})$. In addition, our work supports rectangular matrix multiplication and matrix packing without incurring additional operations per execution. Benchmarks were obtained with a Microsoft SEAL implementation and compared against leading EMM algorithm, with our work performing $4$ times faster for $16 \times 16$ matrices on consumer hardware. Our algorithm is compatible with existing encrypted machine learning frameworks and can be a drop-in replacement for existing matrix multiplication algorithms for increased speed. The favorable time complexity is well suited for time sensitive encrypted algorithms such as computer vision, controls, and patient health monitoring.
## 2025/1368
* Title: Post-Quantum Readiness in EdDSA Chains
* Authors: Foteini Baldimtsi, Konstantinos Chalkias, Arnab Roy
* [Permalink](https://eprint.iacr.org/2025/1368)
* [Download](https://eprint.iacr.org/2025/1368.pdf)
### Abstract
The impending threat posed by large-scale quantum computers necessitates a reevaluation of signature schemes deployed in blockchain protocols. In particular, blockchains relying on ECDSA, such as Bitcoin and Ethereum, exhibit inherent vulnerabilities due to on-chain public key exposure and the lack of post-quantum security guarantees. Although several post-quantum transition proposals have been introduced, including hybrid constructions and zero-knowledge-based key migration protocols, these approaches often fail to protect inactive "sleeping" accounts, are cumbersome, or require address changes, violating core immutability and full backward compatibility assumptions.
In this work, we observe that blockchains employing EdDSA with RFC 8032-compliant key derivation (e.g., Sui, Solana, Near, Stellar, Aptos, Cosmos) possess an underexplored structural advantage. Specifically, EdDSArCOs hash-based deterministic secret key generation enables post-quantum zero-knowledge proofs of elliptic curve private key ownership, which can help switching to a quantum-safe algorithm proactively without requiring transfer of assets to new addresses.
We demonstrate how Post-Quantum NIZKs can be constructed to prove knowledge of the "seed" used in EdDSA key derivation, enabling post-quantum-secure transaction authorization without altering addresses or disclosing elliptic curve data. By post-quantum readiness, we mean that with a single user action all future signatures can be made post-quantum secure, even if past transactions used classical elliptic curve cryptography. This allows even users who have previously exposed their public key to seamlessly enter the post-quantum era without transferring assets or changing their account address.
As part of this analysis, we also show that BIP32-based ECDSA wallets are not post-quantum ready without breaking changes, as they rely on direct scalar exposure in derivation, making backward-compatible upgrades infeasible. In contrast, SLIP-0010 hash-chain based EdDSA private key derivation provides a foundation for seamless, backwards-compatible migration to quantum-safe wallets, supporting secure upgrades even for dormant or legacy accounts.
This mechanism affords a quantum-resilient path and is the first of its kind that preserves full backward compatibility, supports account abstraction, and critically secures dormant accounts, whether from users or custodians, that would otherwise be compromised under quantum adversaries.
## 2025/1369
* Title: Cube-Attack-Like Cryptanalysis of Keccak-Based Constructions Exploiting State Differences (Full Version)
* Authors: MOHAMMAD VAZIRI, Vesselin Velichkov
* [Permalink](https://eprint.iacr.org/2025/1369)
* [Download](https://eprint.iacr.org/2025/1369.pdf)
### Abstract
This paper presents an enhancement to cube-attack-like cryptanalysis by minimizing output-bit dependency on related key bits, thereby improving attack complexity. We construct two distinct initial states differing exclusively in predetermined bit positions. Through independent cube summation and state difference analysis, we observed reduced related key bits dependency for specific output bits. We validate our approach by targeting four Keccak keyed variants Ketje Minor, Ketje Major, Keccak-MAC-512 and Keccak-MAC-384, developing a dedicated tool to recover all output-bit superpolies. Using our computational resources, we successfully attacked 4-round of Ketje Minor and 5-round of other variants, confirming both the method's validity and practical applicability. While the best known attacks on these structures reach 7-round, our results improve upon the 5-round.
We construct our initial state configurations based on the automated method proposed by Bi et al. in Design, Codes and Cryptography (2019), and compare our results with theirs. For the 4-round Ketje Minor, we reduce the time complexity from \(2^{20}\) to \(2^{16.8}\); for the 5-round Ketje Major, from \(2^{24.3}\) to \(2^{23.9}\); for 5 round Keccak-MAC-512, from \(2^{34}\) to \(2^{31.3}\); and for 5 round Keccak-MAC-384, from \(2^{27.6}\) to \(2^{25.5}\).
## 2025/1370
* Title: Randomized Distributed Function Computation (RDFC): Ultra-Efficient Semantic Communication Applications to Privacy
* Authors: Onur Gunlu
* [Permalink](https://eprint.iacr.org/2025/1370)
* [Download](https://eprint.iacr.org/2025/1370.pdf)
### Abstract
We establish the randomized distributed function computation (RDFC) framework, in which a sender transmits just enough information for a receiver to generate a randomized function of the input data. Describing RDFC as a form of semantic communication, which can be essentially seen as a generalized remoterCasourcerCacoding problem, we show that security and privacy constraints naturally fit this model, as they generally require a randomization step. Using strong coordination metrics, we ensure (local differential) privacy for every input sequence and prove that such guarantees can be met even when no common randomness is shared between the transmitter and receiver.
This work provides lower bounds on Wyner's common information (WCI), which is the communication cost when common randomness is absent, and proposes numerical techniques to evaluate the other corner point of the RDFC rate region for continuousrCaalphabet random variables with unlimited shared randomness. Experiments illustrate that a sufficient amount of common randomness can reduce the semantic communication rate by up to two orders of magnitude compared to the WCI point, while RDFC without any shared randomness still outperforms lossless transmission by a large margin. A finite blocklength analysis further confirms that the privacy parameter gap between the asymptotic and non-asymptotic RDFC methods closes exponentially fast with input length. Our results position RDFC as an energy-efficient semantic communication strategy for privacyrCaaware distributed computation systems.
## 2025/1371
* Title: Securing Credential Sequence Verification
* Authors: Mamunur Rashid Akand, Reihaneh Safavi-Naini
* [Permalink](https://eprint.iacr.org/2025/1371)
* [Download](https://eprint.iacr.org/2025/1371.pdf)
### Abstract
Credentials are used to verify a userrCOs identity and attributes
and form the basis of securing user access to the system resources. Users obtain credentials and store them on their (mobile) devices, and present
them when needed. Anonymous credentials protect the userrCOs identity,
and ensure unlinkability of multiple showing of the credential. In this
paper, we consider a setting where a user is issued multiple credentials
in sequence (e.g., for completing courses), and credential subsequences
must be presented in order of issuance. We focus on the anonymous credential system where information such as the time of issuing is hidden
for anonymity, or settings where there is no global clock and issuing
time information is not recorded. We propose a novel order-preserving Proof-of-Credential-Subsequence (PoCS) system called KROM that allows
a user that is potentially untrusted, to present a subsequence of
their locally stored credentials to a verifier, while the relative chronological
order of issuance is preserved. We formalize the security and privacy
of KROM and present two constructions: a basic one that is based on
Merkle trees and one with batched verification that significantly improves
the efficiency of the system. We use KROM to construct an anonymous order-preserving proof-of-location-subsequence system and prove its security. The system enables users to selectively present a subsequence of
their visited locations to a verifier or an auditor. The main challenge that
is addressed is to ensure that the location information that must be in plaintext, does not breach privacy when used in sequence.
## 2025/1372
* Title: Gluon W: A Cryptocurrency Stabilization Protocol
* Authors: Bruno Woltzenlogel Paleo, Luca D'Angelo, Mohammad Shaheer, Giselle Reis
* [Permalink](https://eprint.iacr.org/2025/1372)
* [Download](https://eprint.iacr.org/2025/1372.pdf)
### Abstract
This paper introduces Gluon W, a novel stablecoin protocol inspired by nuclear physics and named after the particle responsible for the stability of matter in the universe. The key idea in Gluon W is to split (as in nuclear fission) an existing volatile asset into its stable and unstable components. These components can be merged back (as in nuclear fusion) into the original asset or transmuted into each other (as in nuclear beta decays). Various stability theorems are proven and their proofs are formally verified using the interactive proof assistant Rocq.
## 2025/1373
* Title: A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric
* Authors: Mladen Kova-ievi-c, Tatjana Grbi-c, Darko -iapko, Nemanja Nedi-c, Sr-aan Vukmirovi-c
* [Permalink](https://eprint.iacr.org/2025/1373)
* [Download](https://eprint.iacr.org/2025/1373.pdf)
### Abstract
The syndrome decoding problem is one of the NP-complete problems lying at the foundation of code-based cryptography. The variant thereof where the distance between vectors is measured with respect to the Lee metric, rather than the more commonly used Hamming metric, has been analyzed recently in several works due to its potential relevance for building more efficient code-based cryptosystems. The purpose of this article is to present a zero-knowledge proof of knowledge for this variant of the problem.
## 2025/1374
* Title: An Attack to Universally Composable Commitments from Malicious Physically Uncloneable Functions and how to Avoid it
* Authors: Louren|oo Abecasis, Paulo Mateus, Chrysoula Vlachou
* [Permalink](https://eprint.iacr.org/2025/1374)
* [Download](https://eprint.iacr.org/2025/1374.pdf)
### Abstract
In this work, we explore the possibility of unconditionally secure universally composable (UC) commitments, a very relevant cryptographic primitive in the context of secure multi-party computation. To this end, we assume the existence of Physically Uncloneable Functions (PUFs), a hardware security assumption
that has been proven useful for securely achieving diverse tasks. In prior work [ASIACRYPT 2013, LNCS, vol. 8270, pp. 100rCo119] it was shown that a protocol for unconditional UC-secure commitments can be constructed even when the PUFs are malicious. Here, we report an attack to this protocol, as well as a few more issues that we identified in its construction. To address them, first we revise some of the previous PUF properties, and introduce new properties and tools that allow us to rigorously develop and present the security proofs. Second, we propose two different ways for making the commitment scheme secure against the attack we found. The first involves considering a new model where the creator of a PUF is notified whenever the PUF is queried
and the second involves restricting adversaries to only being able to create stateless malicious PUFs. Finally, we analyze the efficiency of our schemes and show that our constructions are advantageous in this respect compared to the original proposal.
## 2025/1375
* Title: On the (strong) linkability of Linkable Ring Signatures
* Authors: Danai Balla, Pyrros Chaidos
* [Permalink](https://eprint.iacr.org/2025/1375)
* [Download](https://eprint.iacr.org/2025/1375.pdf)
### Abstract
We demonstrate that the LLRing linkable ring signature scheme of Hui and Chau (ESORICS 2024) has a unlinkability vulnerability, meaning an adversary can create more unlinkable signatures than the number of secret keys they own, contradicting its security guarantees.
We also find that a similar attack applies to the Threshold Ring Referral scheme of Ta, Hui, and Chau (Security and Privacy 2025). We show how to restore linkability by constructing modifications to the Bulletproofs and Dory protocols.
## 2025/1376
* Title: On Hull Attacks on the Module Lattice Isomorphism Problem
* Authors: Franciele C. Silva, Maja Lie, Cong Ling
* [Permalink](https://eprint.iacr.org/2025/1376)
* [Download](https://eprint.iacr.org/2025/1376.pdf)
### Abstract
The Lattice Isomorphism Problem (LIP) is a relatively recent cryptographic assumption whose precise hardness remains not fully understood. Certain weak instances have been identified through hull attacks on $p$-ary lattices constructed via Construction A using linear codes with trivial hulls. In this work, we generalize the notion of the hull by introducing ideal-based hulls for Hermitian lattices. We propose a new hull attack targeting lattices derived from Generalized Construction A over number fields, under specific structural conditions. Furthermore, we show that modular lattices offer intrinsic resistance to hull attacks: the hull introduces only a limited variation in the lattice gap, bounded by a factor depending on the root discriminant of the number field. In particular, for modular $\mathbb{Z}$-lattices, the hull gap coincides exactly with the original lattice gap. As a concrete example, we show that the family of Barnes-Wall lattices, which are alternatively unimodular and 2-modular over $\mathbb{Z}$, are resistant to hull attacks.
## 2025/1377
* Title: More Practical Non-interactive Encrypted Conjunctive Search with Leakage and Storage Suppression
* Authors: Huu Ngoc Duc Nguyen, Shujie Cui, Shangqi Lai, Tsz Hon Yuen, Joseph K. Liu
* [Permalink](https://eprint.iacr.org/2025/1377)
* [Download](https://eprint.iacr.org/2025/1377.pdf)
### Abstract
Searchable symmetric encryption allows clients to outsource their databases to a semi-trusted cloud server while enabling private searches. The Oblivious Cross-Tag (OXT) protocol is a fundamental approach to conjunctive keyword search, ensuring that search performance scales with the least frequent keyword while introducing keyword pair result pattern (KPRP) and intersection result pattern (IP) leakages. However, recent studies show that the KPRP leakage in OXT can be exploited, allowing the cloud server to infer information about the client database. Several works have aimed to mitigate this issue, with Doris being the first non-interactive OXT-based scheme to hide KPRP and IP leakages. However, this comes at the cost of increased storage overhead. In this work, we propose a Doris-based conjunctive SSE scheme with improved storage efficiency. We replace the XOR filter in Doris with our XEBFF filter, which formalizes XOR filters and Binary Fuse Filters. Additionally, we introduce a frequency estimation approach using Count-Min Sketch to efficiently determine the least frequent keyword, which all previous OXT-based schemes overlook. Our scheme reduces storage overhead by 8% compared to Doris while maintaining search performance. With our s-term selection protocol, we ensure that search operations typically scale with the least frequent keyword.
## 2025/1378
* Title: Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators
* Authors: Wei Qi
* [Permalink](https://eprint.iacr.org/2025/1378)
* [Download](https://eprint.iacr.org/2025/1378.pdf)
### Abstract
We study additive positive accumulators, which maintain a short digest of a growing set such that each value in the set can prove membership via a generated witness. Due to compactness of the digest, previously added values may require updated witnesses as the set grows.
In this paper, we establish a trade-off between the bit-length of the accumulator value and the number of witness updates, using techniques generalized from [MQR22]. Specifically, we show that if the accumulator value has bit-length poly(log n), where n is the number of accumulated values, then some values must incur +-(log n/ log log n) witness updates, which matches the upper bound in [MQ23]. This improves upon the recent -e(1) lower bound of [BCCK25]. Our techniques and results also apply to Registration-based Encryption[GHMR18].
## 2025/1379
* Title: Enhancing Scale and Shift Invariance in Deep Learning-based Side-channel Attacks through Equivariant Convolutional Neural Networks
* Authors: David Perez, Sengim Karayalcin, Stjepan Picek, Servio Paguada
* [Permalink](https://eprint.iacr.org/2025/1379)
* [Download](https://eprint.iacr.org/2025/1379.pdf)
### Abstract
Deep learning-based side-channel analysis (DLSCA) has demonstrated remarkable performance over the past few years. Even with limited preprocessing and feature engineering, DLSCA is capable of breaking protected targets, sometimes requiring only a single attack trace. In the DLSCA context, the commonly investigated countermeasures are Boolean masking and desynchronization. While the exact mechanisms of how DLSCA breaks masking are less understood, the core idea behind handling desynchronization is simple. Convolutional neural networks (CNNs) are shift invariant, allowing them to overcome desynchronization. However, considering the importance and practicality of desynchronization countermeasures, we know remarkably little about the limits of CNNs or how to enhance their capabilities when dealing with desynchronization.
In this work, we begin with the theoretical foundations of shift and temporal scale equivariance. Afterward, we build a neural network model allowing such equivariance and test it against several commonly considered targets. Our results demonstrate that equivariant CNNs are robust, easy to design, and achieve excellent attack performance. More precisely, we showcase how such a simple model can even outperform recent transformer-based neural networks. Finally, we demonstrate the practical relevance of scale equivariance by showing how an equivariant CNN can learn leakage from a device operating at one clock frequency and generalize to a device with a different clock frequency, a result not previously demonstrated in DLSCA.
## 2025/1380
* Title: Quantum Composable and Contextual Security Infrastructure (Q2CSI) : A Modular Architecture for Legally Explainable Cryptographic Signatures
* Authors: Thierry Emmanuel MINKA MI NGUIDJOI, MANI ONANA Flavien Serge, DJOTIO NDI|e Thomas, BOUETOU BOUETOU Thomas
* [Permalink](https://eprint.iacr.org/2025/1380)
* [Download](https://eprint.iacr.org/2025/1380.pdf)
### Abstract
The fundamental incompatibility between confidentiality, reliability, and le gal opposability, formalized as the CRO trilemma, imposes an entropic bound +o_CRO on cryptographic security in contextual adversarial settings. This pa per introduces Q2CSI (Quantum Composable Contextual Security Infras tructure), a layered framework resolving this trilemma through dialectical separation. Q2CSI decomposes security guarantees into three isolated yet composable layers: Iron (reliability: temporal/logging integrity), Gold (con f identiality: semantic entropy preservation), and Clay (opposability: insti tutional interpretability). By embedding entropic constraints into an ex tended Universal Composability (UC) model, Q2CSI achieves +o_CRO < 0.4, surpassing monolithic designs, while maintaining post-quantum resilience. The architecture is abstractly instantiated with minimal primitives (IND CCA2 encryption, EUF-CMA signatures) and validated via a symbolic UC framework. Proofs demonstrate strict dialectical isolation, bounded contex tual leakage, and compatibility with quantum adversaries. Q2CSI establishes a foundation for legally verifiable post-quantum protocols, with applications in zero-knowledge attestations and regulatory-compliant signatures.
## 2025/1381
* Title: Blockchain-Based Decentralized Domain Name System
* Authors: Guang Yang, Peter Trinh, Alma Nkemla, Amuru Serikyaku, Edward Tatchim, Osman Sharaf
* [Permalink](https://eprint.iacr.org/2025/1381)
* [Download](https://eprint.iacr.org/2025/1381.pdf)
### Abstract
The current Domain Name System (DNS) infrastructure faces critical vulnerabilities including poisoning attacks, censorship mechanisms, and centralized points of failure that compromise internet freedom and security. Recent incidents such as DNS poisoning attacks on ISP customers highlight the urgent need for resilient alternatives. This paper presents a novel blockchain-based Decentralized Domain Name System (DDNS). We designed a specialized Proof-of-Work blockchain to maximize support for DNS-related protocols and achieve node decentralization. The system integrates our blockchain with IPFS for distributed storage, implements cryptographic primitives for end-to-end trust signatures, and achieves Never Trust, Always Verify zero-trust verification. Our implementation achieves 15-second domain record propagation times, supports 20 standard DNS record types, and provides perpetual free .ddns domains. The system has been deployed across distributed infrastructure in San Jose, Los Angeles, and Orange County, demonstrating practical scalability and resistance to traditional DNS manipulation techniques. Performance evaluation shows the system can handle up to Max Theor. TPS 1,111.1 tx/s (minimal transactions) and Max Theor. TPS 266.7 tx/s (regular transactions) for domain operations while maintaining sub-second query resolution through intelligent caching mechanisms.
## 2025/1382
* Title: Using Learning with Rounding to Instantiate Post-Quantum Cryptographic Algorithms
* Authors: Andrea Basso, Joppe W. Bos, Jan-Pieter D'Anvers, Angshuman Karmakar, Jose Maria Bermudo Mera, Joost Renes, Sujoy Sinha Roy, Frederik Vercauteren, Peng Wang, Yuewu Wang, Shicong Zhang, Chenxin Zhong
* [Permalink](https://eprint.iacr.org/2025/1382)
* [Download](https://eprint.iacr.org/2025/1382.pdf)
### Abstract
The Learning with Rounding (LWR) problem, introduced as a deterministic variant of Learning with Errors (LWE), has become a promising foundation for post-quantum cryptography. This Systematization of Knowledge (SoK) paper presents a comprehensive survey of the theoretical foundations, algorithmic developments, and practical implementations of LWR-based cryptographic schemes. We introduce LWR within the broader landscape of lattice-based cryptography and post-quantum security, highlighting its advantages such as reduced randomness, improved efficiency, and enhanced side-channel resistance. We explore the evolution of security reductions from LWR to LWE, including recent advances that support practical parameter regimes and address challenges in both bounded and unbounded sample settings. This paper systematically reviews existing LWR-based schemes --- including Saber, Lizard, Florete, Espada, Sable, and SMAUG --- analyzing their design choices, parameter sets, and performance trade-offs. Furthermore, we examine the impact of LWR on side-channel resistance, failure probabilities, and masking efficiency, demonstrating its suitability for secure and efficient implementations. By consolidating the research spanning theory and practice, this SoK aims to guide future cryptographic design and standardization efforts leveraging LWR.
## 2025/1383
* Title: An Efficient Circuit Synthesis Framework for TFHE via Convex Sub-graph Optimization
* Authors: Animesh Singh, Ayantika Chatterjee, Anupam Chattopadhyay, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/1383)
* [Download](https://eprint.iacr.org/2025/1383.pdf)
### Abstract
Optimizing Boolean circuits presents a considerable challenge, especially when aiming to construct circuits amenable to Fully Homomorphic Encryption (FHE) schemes. FHE enables arbitrary computations on encrypted data but incorporates a computationally intensive operation called bootstrapping, necessary for reducing noise in ciphertexts to facilitate computations on circuits of arbitrary depth. This operation can consume a substantial amount of time, depending on the size of the circuits. To address this issue, we propose a technique for efficiently synthesizing circuits specific to FHE by utilizing multi-input homogeneous and composite Boolean gates. Following this we develop an automated framework for designing efficient circuits compatible with FHE schemes. In this work, we use Torus-FHE (TFHE) (JoC 2019), a widely used FHE scheme for Boolean circuits due to its fast bootstrapping operation per bit. Existing techniques typically employ either multi-input homogeneous gates or, multi-bit Look-Up tables during circuit synthesis, which often limits their ability to produce highly optimized circuits for FHE. Our approach addresses this limitation by proposing viable multi-input composite gates alongwith the homogeneous gates during circuit synthesis. Additionally, we propose an efficient and lightweight circuit synthesis approach based on graph optimization. Our approach identifies convex sub-graphs in a Directed Acyclic Graph (DAG) representing the input circuit and replaces them with a more compact structure. This results in a reduction of the number of nodes in the DAG and so as the number of Boolean gates in the input circuit. Our proposed framework provides the most efficient Boolean circuits for TFHE till date, achieving up to a 20% improvement in homomorphic evaluation time compared to the state-of-the-art general compiler optimization techniques for TFHE, and it also demonstrates a 4-6|u improvement over prior work on FHEW-like schemes.
## 2025/1384
* Title: Silent Threshold Encryption with One-Shot Adaptive Security
* Authors: Mathias Hall-Andersen, Mark Simkin, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2025/1384)
* [Download](https://eprint.iacr.org/2025/1384.pdf)
### Abstract
Threshold encryption enables a sender to encrypt a message towards $n$ recipients, such that any sufficiently large subset can decrypt the message, whereas any subset of too small size cannot. Silent threshold encryption additionally requires that all recipients can generate their public keys independently of each other, without engaging in an interactive distributed key generation protocol.
In this work, we present a simple blueprint for constructing such silent threshold encryption schemes, which remain secure as long as the number of corruptions is at most $t \leq (1/2 - \epsilon) \cdot n$, where $\epsilon > 0$ is an arbitrary constant. Our construction allows for ciphertexts and recipient public keys, whose sizes are independent of $n$. We evaluate the concrete efficiency of our construction and show that it is highly efficient. As an exemplary data point, when $t < n/3$, encrypting $1$ MB results in a ciphertext of size $1.067$ MB.
On the technical side, we introduce a new model of corruptions, which we call one-shot adaptive corruptions, which conceptually lie between static and fully adaptive corruptions. We believe that the notion itself and our associated proof techniques may be of independent interest.
In comparison to prior works, we have smaller recipient public keys, do not require strong assumptions, such as indistinguishability obfuscation, or idealizing models, such as the generic group model, we allow for instantiating our blueprint to obtain plausible post-quantum security, and we prove security under a stronger security notion.
## 2025/1385
* Title: Hypersphere Secure Sketch Revisited: Probabilistic Linear Regression Attack on IronMask in Multiple Usage
* Authors: Pengxu Zhu, Lei Wang
* [Permalink](https://eprint.iacr.org/2025/1385)
* [Download](https://eprint.iacr.org/2025/1385.pdf)
### Abstract
Protection of biometric templates is a critical and urgent area of focus. \textbf{IronMask} demonstrates superior recognition performance while protecting facial templates against existing known attacks. In high-level, IronMask can be conceptualized as a fuzzy commitment scheme building on the hypersphere directly. We devise an attack on IronMask targeting on the security notion of renewability. Our attack, termed as \textbf{Probabilistic Linear Regression Attack}, utilizes the linearity of underlying used error correcting code. This attack is the first algorithm to successfully recover the original template when getting multiple protected templates in acceptable time and requirement of storage. We implement experiments on \textbf{IronMask} applied to protect \textbf{ArcFace} that well verify the validity of our attacks. Furthermore, we carry out experiments in noisy environments and confirm that our attacks are still applicable. Finally, we discuss two strategies to mitigate this type of attacks.
## 2025/1386
* Title: How to Tolerate Typos in Strong Asymmetric PAKE
* Authors: Ian McQuoid, Mike Rosulek, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2025/1386)
* [Download](https://eprint.iacr.org/2025/1386.pdf)
### Abstract
Strong asymmetric password-authenticated key exchange (saPAKE) is the gold standard for password-based authentication. When authenticating using saPAKE, the client holds a cleartext password, and the server holds only a "digest" of the password. The two parties obtain a shared session key if and only if the client password matches the password encoded in the digest.

In this work we initiate the study of strong asymmetric fuzzy PAKE (safPAKE), which allows the client and server to obtain a shared session key if the client's password is "close enough" to the password encoded in the digest, according to some policy. safPAKE can be used to tolerate incidental password typos in the PAKE setting, which is becoming a standard industry practice outside the PAKE setting. Our safPAKE functionality supports any "typo policy", and our protocol is practical when there are a small number of permissible mistypings of a password.
## 2025/1387
* Title: Fast Final Exponentiation on BW and BLS Curves with Even Embedding Degrees at 128 bits security
* Authors: Senegue Gomez Nyamsi, Emmanuel Fouotsa, Calvin Tcheka
* [Permalink](https://eprint.iacr.org/2025/1387)
* [Download](https://eprint.iacr.org/2025/1387.pdf)
### Abstract
The final exponentiation is a crucial step in pairing computations, ensuring cor-
rectness and uniqueness of results in pairing-based cryptographic protocols. In this work, we propose an efficient method for computing the hard part of the final
exponentiation on BW10-511, BW14-351 and BLS12 curves at 128 bits security level. Our approach reduces the computation cost by optimizing the exponenti- ation sequence and minimizing the number of required multiplications through
an improved addition chain strategy. The computation cost of our method for
the final exponentiation on these curves is about 25.6%, 33.2% and 10% faster than the previously fastest result on BW10-511, BW14-351 and BLS12 curves respectively. The correctness of our formulas has been verified by a Magma code.
## 2025/1388
* Title: Collaborative zkSNARKs with Sublinear Prover Time and Constant Proof Size
* Authors: Zhiyong Fang, Sanjam Garg, Bhaskar Roberts, Wenxuan Wu, Yupeng Zhang * [Permalink](https://eprint.iacr.org/2025/1388)
* [Download](https://eprint.iacr.org/2025/1388.pdf)
### Abstract
Collaborative zkSNARKs, proposed by Ozdemir and Boneh in 2022, allow a prover to delegate the generation of zkSNARK proofs to multiple servers, without compromising the confidentiality of the secret witness. They enable the use of zkSNARK techniques on computational limited devices in critical applications such as blockchains. However, the running time of each server is at least as slow as computing the proof on a single server. Garg et al. attempted to improve the efficiency in their scheme named zkSaaS using packed secret sharing, but the scheme still requires a powerful central server with linear computation, communication and memory usage.
In this paper, we propose a new collaborative zkSNARK scheme with $O(\frac{C}{n}\log\frac{C}{n})$ prover time and $O(1)$ proof size with $n$ servers for a circuit of size $C$. An adversary compromising less than $\frac{n}{4}$ servers cannot learn any information about the witness. The core of our technique lies in a new zkSNARK scheme for the Plonkish constraint system that is friendly to packed secret sharing. We utilize bivariate polynomials to avoid a large Fast Fourier Transform on the entire witness, which was the major bottleneck in prior work. We also construct permutation constraints based on logarithmic derivatives and univariate sumcheck to avoid the computation of prefix products. Finally, we build a bivariate polynomial commitment scheme that can be computed directly on packed secret shares.
Experimental results show that for a circuit of size $2^{20}$, with 128 servers, our scheme can accelerate the proof generation by 36.2$\times$ compared to running the zkSNARK on a single server. The prover time of our system is 25.9$\times$ faster than the prior work of zkSaaS. The proof size of our scheme is only 960 Bytes.
## 2025/1389
* Title: Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework
* Authors: Joshua Luberisse
* [Permalink](https://eprint.iacr.org/2025/1389)
* [Download](https://eprint.iacr.org/2025/1389.pdf)
### Abstract
Human verification under adversarial information flow operates as a cost-bounded decision procedure constrained by working memory limits and cognitive biases. We introduce the Verification Cost Asymmetry (VCA) coefficient, formalizing it as the ratio of expected verification work between populations under identical claim distributions. Drawing on probabilistically checkable proofs (PCP) and parameterized complexity theory, we construct dissemination protocols that reduce verification for trusted audiences to constant human effort while imposing superlinear costs on adversarial populations lacking cryptographic infrastructure. We prove theoretical guarantees for this asymmetry, validate the framework through controlled user studies measuring verification effort with and without spot-checkable provenance, and demonstrate practical encoding of real-world information campaigns. The results establish complexity-theoretic foundations for engineering democratic advantage in cognitive warfare, with immediate applications to content authentication, platform governance, and information operations doctrine. We are concerned not with verifying ground truth, but with verifying provenancerCothe integrity of the chain of custody from source to receiver. Our protocols allow a user to efficiently check that a bundle of information is authentic and has not been tampered with, even though the underlying claims may still be right or wrong in substance.
## 2025/1390
* Title: Optimizing Backend Verification in zk-Rollup Architectures
* Authors: Mehdi Beriane, Muhammed Ali Bingol
* [Permalink](https://eprint.iacr.org/2025/1390)
* [Download](https://eprint.iacr.org/2025/1390.pdf)
### Abstract
Zero-knowledge rollups represent a critical scaling solution for Ethereum, yet their practical deployment faces significant challenges in on-chain verification costs. This paper presents a comprehensive implementation of the Tokamak zkEVM verifier, specifically optimized for the BLS12-381 elliptic curve operations introduced by EIP-2537. We detail the complete verification architecture, from EVM compatible data formatting for pairing checks, multi-scalar multiplication (MSM), and elliptic curve
addition, to the non-interactive protocol design between prover and verifier. Our key contribution lies in novel optimization techniques that substantially reduce on-chain verification costs. Through strategic polynomial aggregation and scalar factorization, we minimize G1 exponentiations from 40 to 31, achieving gas savings of 108,000 units per verification. Additionally, we introduce a dynamic barycentric interpolation method that replaces computationally intensive FFT operations,
resulting in 92-95% gas reduction for sparse polynomial evaluations. We further present proof aggregation strategies that minimize precompile calls while maintaining the 128-bit security guarantees of BLS12-381.
Our implementation demonstrates that careful protocol design and mathematical optimizations can make zk-rollup verification economically viable on Ethereum. The techniques presented are compatible with the upcoming Pectra upgrade and provide a blueprint for efficient on-chain verification of complex zero-knowledge proofs. Experimental results show total gas costs reduced from 857,200 to 748,450 units for complete proof verification, making our approach practical for high-throughput rollup deployments.
## 2025/1391
* Title: Inverse Discrete Logarithm - Post-Quantum take on a classical problem. * Authors: Mikhail Suslov
* [Permalink](https://eprint.iacr.org/2025/1391)
* [Download](https://eprint.iacr.org/2025/1391.pdf)
### Abstract
We introduce the \(Inverse\ Discrete\ Logarithm\ Problem\) (iDLP) framework, which inverts traditional discrete logarithm assumptions by making the exponent public but deliberately non-invertible modulo the group order, while hiding the base. This creates a many-to-one algebraic mapping that is computationally irreversible under both classical and quantum attack models.
Within this framework, we define three post-quantum cryptographic primitives: Inverse Discrete DiffierCoHellman (IDDH), Inverse Discrete Key Encapsulation (IDKE), and Inverse Discrete Data Encapsulation (IDDE). Using a 512-bit modulus (prime or semiprime), a random generator \( g \), and a public exponent \( y \) with \(\gcd(y, \varphi(m)) = 2\), the masking function
\[
\mathsf{Mask}_{g,y}(x) := g^{x y} \bmod m
\]
induces a two-to-one mapping that renders discrete logarithm inversion infeasible.
Our security analysis shows that known quantum algorithms yield only multiple candidates, requiring exhaustive search among equivalence classes, which remains intractable at 512-bit parameters. We demonstrate efficient prototype implementations with sub-millisecond key operations and AES-GCM-level data throughput. Full source code and parameters are publicly available at \url{https://github.com/AdamaSoftware/InverseDiscrete/}.
## 2025/1392
* Title: FLEX rCo Capital-Efficient Optimistic Bridges with On-Demand Security Bonds for Bitcoin
* Authors: Sergio Demian Lerner, Ariel Futoransky
* [Permalink](https://eprint.iacr.org/2025/1392)
* [Download](https://eprint.iacr.org/2025/1392.pdf)
### Abstract
This paper presents FLEX (Fraud proofs with Lightweight Escrows for eXits), a garbled circuit-based protocol designed to facilitate two-party disputes on Bitcoin without requiring permanent security bonds. FLEX enables conditional security deposits that are only activated in the event of a dispute, reducing the financial overhead for both parties. The main goal of FLEX is to improve the capital efficiency of BitVM-based bridges in a permissioned challenge setting but can also be used to improve the security of any other fraud proof-based protocol such as payment channels. The paper also introduces enhancements that allow faster reimbursements in scenarios where one party's node is unavailable, while preserving security and minimizing race conditions.
## 2025/1393
* Title: Polynomial Lattices for the BIKE Cryptosystem
* Authors: Michael Schaller
* [Permalink](https://eprint.iacr.org/2025/1393)
* [Download](https://eprint.iacr.org/2025/1393.pdf)
### Abstract
In this paper we introduce a rank $2$ lattice over a polynomial ring arising from the public key of the BIKE cryptosystem.
The secret key is a sparse vector in this lattice.
We study properties of this lattice and generalize the recovery of weak keys from "Weak keys for the quasi-cyclic MDPC public key encryption scheme".
In particular, we show that they implicitly solved a shortest vector problem in the lattice we constructed.
Rather than finding only a shortest vector, we obtain a reduced basis of the lattice which makes it possible to check for more weak keys.
## 2025/1394
* Title: Peeking Into the Future: MPC Resilient to Super-Rushing Adversaries
* Authors: Gilad Asharov, Anirudh Chandramouli, Ran Cohen, Yuval Ishai
* [Permalink](https://eprint.iacr.org/2025/1394)
* [Download](https://eprint.iacr.org/2025/1394.pdf)
### Abstract
An important requirement in synchronous protocols is that, even when a party receives all its messages for a given round ahead of time, it must wait until the round officially concludes before sending its messages for the next round. In practice, however, implementations often overlook this waiting requirement. This leads to a mismatch between the security analysis and real-world deployments, giving adversaries a new, unaccounted-for capability: the ability to ``peek into the future.'' Specifically, an adversary can force certain honest parties to advance to round $r+1$, observe their round $r+1$ messages, and then use this information to determine its remaining round $r$ messages. We refer to adversaries with this capability as ``super-rushing" adversaries.
We initiate a study of secure computation in the presence of super-rushing adversaries. We focus on understanding the conditions under which existing synchronous protocols remain secure in the presence of super-rushing adversaries. We show that not all protocols remain secure in this model, highlighting a critical gap between theoretical security guarantees and practical implementations. Even worse, we show that security against super-rushing adversaries is not necessarily maintained under sequential composition.
Despite those limitations, we present a general positive result: secret-sharing based protocols in the perfect setting, such as BGW, or those that are based on multiplication triplets, remain secure against super-rushing adversaries. This general theorem effectively enhances the security of such protocols ``for free.'' It shows that these protocols do not require parties to wait for the end of a round, enabling potential optimizations and faster executions without compromising security. Moreover, it shows that there is no need to spend efforts to achieve perfect synchronization when establishing the communication networks for such protocols.
## 2025/1395
* Title: A Security Comment on ``A Security-Enhanced Authentication and Key Agreement Protocol in Smart Grid''
* Authors: Dariush Abbasinezhad-Mood
* [Permalink](https://eprint.iacr.org/2025/1395)
* [Download](https://eprint.iacr.org/2025/1395.pdf)
### Abstract
In smart grid (SG), key agreement protocols (KAPs) are used as one of the most prevalent means to establish secure data transmission channels between smart meters (SMs) and service providers (SPs). Quite recently, Wu et al. have indicated the vulnerability of Hu et al.'s KAP to key compromise impersonation (KCI) attack and proposed a security-enhanced one for secure communications of SMs and SPs in SG. Not to undermine the noteworthy contributions of their work, this comment demonstrates that their own KAP, i.e., Wu et al.'s scheme is still vulnerable to KCI attack. Accordingly, we suggest a simple modification to fix the KCI attack issue. Our attack procedure gives some delicate hints to scholars to protect their schemes against the KCI attack in future researches.
## 2025/1396
* Title: A Generalized Wiener-type Attack Against a Family RSA-like Cryptosystem
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2025/1396)
* [Download](https://eprint.iacr.org/2025/1396.pdf)
### Abstract
Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA scheme, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 2^i$, where $i > 2$ is an integer. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.
## 2025/1397
* Title: Starfighters rCo on the general applicability of X-Wing
* Authors: Deirdre Connolly, Kathrin H||velmanns, Andreas H|+lsing, Stavros Kousidis, Matthias Meijers
* [Permalink](https://eprint.iacr.org/2025/1397)
* [Download](https://eprint.iacr.org/2025/1397.pdf)
### Abstract
This work presents an exhaustive analysis of QSF, the KEM combiner used by X-Wing (Communications in Cryptology 1(1), 2024). While the X-Wing paper focuses on the applicability of QSF for combining ML-KEM-768 with X25519, we discuss its applicability for combining other post-quantum KEM with other instantiations of ECDH.
To this end, we establish simple conditions that allow one to check whether a KEM is compatible with QSF by proving ciphertext secondrCapreimage resistance C2PRI for several variants of the FujisakirCoOkamoto (FO) transform. Applying these results to post-quantum KEMs that are either standardized or under consideration for standardization, we show that QSF can also be used with all of these, including ML-KEM-1024, (e)FrodoKEM, HQC, Classic McEliece, and sntrup.
We also present QSI, a variation of QSF and show that any two KEM can be combined by hashing their concatenated keys. The result is a hybrid KEM which is IND-CCA-secure as long as one of the KEM is IND-CCA- and the other C2PRI-secure.
Finally, we also analyze QSF and QSI regarding their preservation of the recently introduced family of binding properties for KEM.
## 2025/1398
* Title: General Review of Hash-Based Signatures
* Authors: Halil -#brahim Kaplan
* [Permalink](https://eprint.iacr.org/2025/1398)
* [Download](https://eprint.iacr.org/2025/1398.pdf)
### Abstract
The advent of quantum computing threatens the security
assumptions underpinning classical public-key cryptographic algorithms
such as RSA and ECC. As a response, the cryptographic community has
focused on developing quantum-resistant alternatives, with hash-based
signature schemes emerging as a compelling option due to their reliance
on well-understood hash functions rather than number-theoretic hard-
ness assumptions. This paper presents a comprehensive review of hash-
based signature schemes, including Lamport, WOTS, XMSS, XMSSMT ,
and SPHINCS+, examining their structural design, key generation, sign-
ing, and verification processes. Emphasis is placed on their classification
as stateful and stateless schemes, as well as their practical integration us- ing Merkle trees and address structures. Furthermore, the paper analyzes several notable cryptanalytic attacks-such as intermediate value guess-
ing, AntonovrCOs attack, multi-target attacks, and fault injection strate- gies-that pose risks to these constructions. By discussing both their
strengths and vulnerabilities, this work highlights the viability of hash- based signatures as secure and efficient candidates for post-quantum digital signatures.
## 2025/1399
* Title: Tempo: ML-KEM to PAKE Compiler Resilient to Timing Attacks
* Authors: Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki
* [Permalink](https://eprint.iacr.org/2025/1399)
* [Download](https://eprint.iacr.org/2025/1399.pdf)
### Abstract
Recent KEM-to-PAKE compilers follow the Encrypted Key Exchange (EKE) paradigm (or a variant thereof), where the KEM public key is password-encrypted. While constant-time implementations of KEMs typically avoid secret-dependent branches and memory accesses, this requirement does not usually extend to operations involving the expansion of the public key because public keys are generally assumed to be public. A notable example is $\mathsf{ML\textrm{-}KEM}$, which expands a short seed $\rho$ into a large matrix $\mathsf{A}$ of polynomial coefficients using rejection sampling---a process that is variable-time but usually does not depend on any secret. However, in PAKE protocols that password-encrypt the compressed public key, this introduces the risk of timing honest parties and mounting an offline dictionary attack against the measurement. This is particularly concerning given the well-known real-world impact of such attacks on PAKE protocols.
In this paper we show two approaches which yield $\mathsf{ML\textrm{-}KEM}$-based PAKEs that resist timing attacks. First, we explore constant-time alternatives to $\mathsf{ML\textrm{-}KEM}$ rejection sampling: one that refactors the original $\mathsf{SampleNTT}$ algorithm into constant-time style code, whilst preserving its functionality, and two that modify the matrix expansion procedure to abandon rejection sampling and rely instead on large-integer modular arithmetic. All the proposed constant-time algorithms are slower than the current rejection sampling implementations, but they are still reasonably fast in absolute terms. Our conclusion is that adopting constant-time methods will imply both performance penalties and difficulties in using off-the-shelf $\mathsf{ML\textrm{-}KEM}$ implementations. Alternatively, we present the first $\mathsf{ML\textrm{-}KEM}$-to-PAKE compiler that mitigates this issue by design: our proposal transmits the seed $\rho$ in the clear, decoupling password-dependent runtime variations from the matrix expansion step. This means that vanilla implementations of $\mathsf{ML\textrm{-}KEM}$ can be used as a black-box. Our new protocol $\mathsf{Tempo}$ builds on the ideas from $\mathsf{CHIC}$, which considered splitting the KEM public key, adopts the two-round Feistel approach for password encryption of the non-expandable part of the public key, and leverages the proof techniques from $\mathsf{NoIC}$ to show that, despite the malleability permitted by the two-round Feistel, it is sufficient for password extraction and protocol simulation in the UC framework.
## 2025/1400
* Title: RGB I.0: Scalable consensus for client-side validated smart contracts * Authors: Maxim Orlovsky
* [Permalink](https://eprint.iacr.org/2025/1400)
* [Download](https://eprint.iacr.org/2025/1400.pdf)
### Abstract
The paper defines a novel type of consensus for a distributed smart contract system, named RGB, which is based on the concept of client-side validation, separating the contract state and operations from the blockchain. With this approach, contracts are sharded (each contract is a standalone shard), kept, and validated only by contract participants, providing native scalability and privacy mechanisms, exceeding all existing blockchain-based smart contract systems while not compromising on security or decentralization. The system is designed to operate on top of compatible layers 1, such as an UTXO-based blockchain (e.g., Bitcoin) without relying on it for transaction ordering or state replication. Instead, RGB keeps the state client-side, operating as partially replicated state machines (PRiSM). It employs a novel SONIC (State machine with Ownership Notation Involving Capabilities) architecture, which provides capability-based access control to the contract state, individually owned and operated by a well-defined contract parties via novel single-use seal mechanism. RGB does state validation using zk-AluVM virtual machine, designed to support zk-STARK provers. It has a single security assumption of the collision-resistance hash function and, thus, is quantum-secure. The proposed RGB consensus is distinct from traditional blockchain-based smart contract systems; it is scalable, provably-secure, and formally verifiable.
## 2025/1401
* Title: Automated Tool for Meet-in-the-Middle Attacks with Very Low Data and Memory Complexity (Full Version)
* Authors: MOHAMMAD VAZIRI
* [Permalink](https://eprint.iacr.org/2025/1401)
* [Download](https://eprint.iacr.org/2025/1401.pdf)
### Abstract
In this paper, we present a simple meet-in-the-middle attack that requires low data and memory resources. To evaluate the complexity of the attack, we also propose an automated tool that calculates the time, data, and memory complexities based on the suggested matching points. Our method operates at the bit level and employs a known-plaintext attack, with no constraints on the attacker's choice of data. We apply our tool on various lightweight block ciphers, including CRAFT, Midori, WARP, PRESENT, and ARADI. For CRAFT, our tool successfully identified an attack targeting 15 rounds using 3 known plaintexts. In the case of Midori64 and Midori128, the tool proposed attacks on 5 rounds with 16 known plaintexts and 7 rounds with 3 known plaintexts, respectively. For WARP, the tool discovered an attack on 18 rounds utilizing 7 known plaintexts. Additionally, for PRESENT80, the tool identified an attack on 6 rounds with 18 known plaintexts, and for ARADI, an attack on 5 rounds with 28 known plaintexts was determined.
## 2025/1402
* Title: Can we Speed up Information Set Decoding by Using Extension Field Structure?
* Authors: Freja Elbro, Violetta Weger
* [Permalink](https://eprint.iacr.org/2025/1402)
* [Download](https://eprint.iacr.org/2025/1402.pdf)
### Abstract
The Syndrome Decoding Problem (SDP) underpins the security of most code-based cryptographic schemes, and Information Set Decoding (ISD) algorithms are the fastest known solvers for most parameter sets. While ISD is well developed in the binary setting, the landscape for non-binary ISD is less mature. Most $q$-ary methods are straightforward generalizations of their binary counterparts, with the recent projective Stern algorithm being the only exception. However, no existing algorithm is designed to leverage the specific algebraic properties of extension fields. This research gap -- highlighted by the first-round NIST PQC proposal SDitH -- motivates our central question: is decoding over an extension field fundamentally easier than over a prime field of similar size?
This work explores whether the algebraic structure of extension fields can accelerate ISD. We analyze several techniques for translating the SDP to the base field, including the expansion map, subfield subcodes, and the trace map. We also develop new BJMM variants that restrict base list vectors to rCLsmallrCY field elements, aiming to counter the performance loss of advanced ISD when $q$ is large.
Contrary to our initial intuition, our results provide no evidence of an asymptotic speedup, suggesting that decoding over extension fields is not easier than over prime fields. Additionally, we make two contributions of independent interest: we show that a three-level BJMM algorithm gives a slight improvement over the two-level version for small fields, and we extend MeurerrCOs proof to show that the complexity of advanced ISD algorithms converges to PrangerCOs, even when parameters grow simultaneously.
## 2025/1403
* Title: Faster Bootstrapping for CKKS with Less Modulus Consumption
* Authors: Lianglin Yan, Pengfei Zeng, Peizhe Song, Mingsheng Wang
* [Permalink](https://eprint.iacr.org/2025/1403)
* [Download](https://eprint.iacr.org/2025/1403.pdf)
### Abstract
CKKS bootstrapping requires a significant computational overhead and modulus consumption. In this work, we improve the homomorphic linear transformation algorithm with lower time complexity and less modulus consumption.
We first propose a novel rescaling operation, called level-conserving rescaling, that acts on CoeffsToSlots for saving moduli. Secondly, we reconstruct the rotation keys and merge the plaintext-ciphertext multiplication and rescaling operations into the key-switching procedure, which reduces the time complexity of matrix-vector multiplication for matrices with $\le$64 non-zero diagonals, albeit with increased space overhead. By combining the two methods in CoeffsToSlots in a non-trivial manner, we not only further accelerate the homomorphic linear transformations and save one level of moduli, but also reduce the total size of rotation keys.
Experiments demonstrate the practicability of our techniques. Compared to the state of the art (Bossuat et al., EurocryptrCO21), our approaches: (1) increase the remaining homomorphic capacity, allowing fewer bootstrapping operations in large-depth circuit evaluation; (2) accelerate the CoeffsToSlots by a factor of 1.17$\sim$1.23 and reduce its rotation key size by 11.8$\%\sim$15.0$\%$. Furthermore, for better efficiency, we can speed up the fastest state-of-the-art bootstrapping scheme by 1.28 times at the cost of moderate additional space. The bootstrapping precision and failure probability remain identical to previous method.
## 2025/1404
* Title: Optimistic Message Dissemination
* Authors: Chen-Da Liu-Zhang, Christian Matt, S|+ren Eller Thomsen
* [Permalink](https://eprint.iacr.org/2025/1404)
* [Download](https://eprint.iacr.org/2025/1404.pdf)
### Abstract
Message dissemination is a fundamental building block in distributed systems and guarantees that any message sent eventually reaches all parties. State of the art provably secure protocols for disseminating messages have a per-party communication complexity that is linear in the inverse of the fraction of parties that are guaranteed to be honest in the worst case. Unfortunately, this per-party communication complexity arises even in cases where the actual fraction of parties that behave honestly is close to 1. In this paper, we propose an optimistic message dissemination protocol that adopts to the actual conditions in which it is deployed, with optimal worst-case per-party communication complexity. Our protocol cuts the complexity of prior provably secure protocols for 49% worst-case corruption almost in half under optimistic conditions and allows practitioners to combine efficient heuristics with secure fallback mechanisms.
## 2025/1405
* Title: Two-Tier Black-box Blockchains and Application to Instant Layer-1 Payments
* Authors: Michele Ciampi, Yun Lu, Rafail Ostrovsky, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2025/1405)
* [Download](https://eprint.iacr.org/2025/1405.pdf)
### Abstract
Common blockchain protocols are monolithic, i.e., their security relies on a single assumption, e.g., honest majority of hashing power (Bitcoin) or stake (Cardano, Algorand, Ethereum). In contrast, so-called optimistic approaches (Thunderella, Meshcash) rely on a combination of assumptions to achieve faster transaction liveness.
We revisit, redesign, and augment the optimistic paradigm to a tiered approach. Our design assumes a primary (Tier 1) and a secondary (Tier 2, also referred to as fallback) blockchain, and achieves full security also in a tiered fashion: If the assumption underpinning the primary chain holds, then we guarantee safety, liveness and censorship resistance, irrespectively of the status of the fallback chain. And even if the primary assumption fails, all security properties are still satisfied (albeit with
a temporary slow down) provided the fallback assumption holds. To our knowledge, no existing optimistic or tiered approach preserves both safety and liveness when any one of its underlying blockchain (assumptions) fails. The above is achieved by a new detection-and-recovery mechanism that links the two blockchains, so that any violation of safety, liveness, or censorship resistance on the (faster) primary blockchain is temporaryrCoit is swiftly detected and recovered on the secondary chainrCoand thus cannot result in a persistent fork or halt of the blockchain ledger.
We instantiate the above paradigm using a primary chain based on proof of reputation (PoR) and a fallback chain based on proof of stake (PoS). Our construction uses the PoR and PoS blockchains in a mostly black-box mannerrCowhere rather than assuming a concrete construction we distill abstract properties on the two blockchains that are sufficient for applying our tiered methodology. In fact, choosing reputation as the resource of the primary chain opens the door to an incentive mechanismrCowhich we devise and analyzerCothat tokenizes reputation in order to deter cheating and boost participation (on both the primary/PoR and the fallback/PoS blockchain). As we demonstrate, such tokenization in combination with interpreting reputation as a built-in system-wide credit score, allows for embedding in our two-tiered methodology a novel mechanism which provides collateral-free, multi-use payment-channel-like functionality where payments can be instantly confirmed.
## 2025/1406
* Title: Scalable Secure Multiparty Computation with Perfect Security from Preprocessing
* Authors: Yifan Song, Xiaxi Ye
* [Permalink](https://eprint.iacr.org/2025/1406)
* [Download](https://eprint.iacr.org/2025/1406.pdf)
### Abstract
In this work, we study the communication complexity of MPC achieving perfect security with optimal resilience ($t<n/3$). We ask the question: ``Is it possible to build a perfectly secure MPC for arithmetic circuits of size $|C|$ with optimal resilience with communication of $o(|C|\cdot n)$ field elements?''
On the positive side, we construct a perfectly secure MPC protocol for SIMD circuits with a communication complexity of $O(|C|)$ elements assuming preprocessing data of size $O(|C|)$, where the preprocessing data consists of packed Beaver triples over bivariate polynomials. Furthermore, we show that packed Beaver triples over bivariate polynomials can be prepared at an amortized cost of $O(1)$ elements plus $O(1)$ three-party Beaver triples per secret.
On the negative side, we establish a communication lower bound proving that preparing packed Beaver triples over bivariate polynomials requires at least $\Omega(n)$ elements of communication per secret. This lower bound is derived by first proving a communication lower bound for verifying the correctness of packed Beaver triples with perfect security with abort, and then efficiently reducing the task of verifying packed Beaver triples to preparing packed Beaver triples over bivariate polynomials. To match this bound, we give a concrete construction for packed Beaver triples over bivariate polynomials with $O(n)$ elements per secret, demonstrating the tightness of our lower bound.
Our proof technique also extends to show that for the task of computing the inner-product of two length-$|C|$ vectors, any MPC protocol that achieves perfect security with abort requires either $\Omega(|C|\cdot n)$ elements of communication or $\Omega(|C|)$ elements of preprocessing data.
## 2025/1407
* Title: A Flexible Hardware Design Tool for Fast Fourier and Number-Theoretic Transformation Architectures
* Authors: Florian Krieger, Florian Hirner, Ahmet Can Mert, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2025/1407)
* [Download](https://eprint.iacr.org/2025/1407.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) and Post-Quantum Cryptography (PQC) involve polynomial multiplications, which are a common performance bottleneck. To resolve this bottleneck, polynomial multiplications are often accelerated in hardware using the Number-Theoretic Transformation (NTT) or the Fast Fourier Transformation (FFT). In particular, NTT operates over modular rings while FFT operates over complex numbers. NTT and FFT are widely deployed in applications with diverse parameter sets, leading to long design times for hardware accelerators. Existing hardware generation tools have limited functionality since they do not support generic on-the-fly twiddle factor generation or different memory-related optimizations. This paper improves the hardware design process and presents a generic and flexible tool to generate FFT and NTT architectures. In contrast to prior work, we combine on-the-fly twiddle factor generation and stall-free memory accesses. Moreover, we enhance hardware design flexibility through memory-optimized or routing-optimized design strategies. While our memory-optimized strategy minimizes twiddle factors in ROM, our routing-optimized strategy allows significantly higher clock frequencies on FPGAs. These optimization strategies allow effective customization of NTT/FFT architectures, spanning from low-end PQC to high-end FHE accelerators. Compared to existing works, we reach up to 15.9x lower latency and up to 7.4x improved ATP for FFT applications such as the Falcon signature scheme. Considering other NTT tools, we decrease latency by up to 1.8x and 2x for PQC and FHE parameter sets, respectively.
## 2025/1408
* Title: $\mathsf{qedb}$: Expressive and Modular Verifiable Databases (without SNARKs)
* Authors: Vincenzo Botta, Simone Bottoni, Matteo Campanelli, Emanuele Ragnoli, Alberto Trombetta
* [Permalink](https://eprint.iacr.org/2025/1408)
* [Download](https://eprint.iacr.org/2025/1408.pdf)
### Abstract
Verifiable Databases (VDBs) enable clients delegating storage to a provider without having to trust it: given a claimed response to a query, they can check its correctness by holding a short digest to the database and a small related certificate (a proof). The foundational role of databases and the increasing trend of storage delegation make this an important primitive.
Existing VDB approaches face fundamental tradeoffs (on which we improve in this work). A line of work on VDB designs has leveraged general purpose proof systems (SNARKs). The resulting constructions are expressiverCothey support a large class of queriesrCobut require cumbersome intermediate representations, often rely on heuristic assumptions and are overall very complex. Other prior approaches adopted cleverly combined specialized authenticated data structures (e.g., set accumulators). These designs tend to be simple, elegant and rely on well founded cryptographic assumptions; however they have limited expressivity and some undesirable efficiency features (e.g., scaling quadratically in the number of columns).
We present $\mathsf{qedb}$, a novel construction for verifiable databases that addresses these limitations. $\mathsf{qedb}$ supports more expressive queries than previous approaches based on specialized data structures. At the same time it preserves their simplicity and improves on several of their limitations: it removes the quadratic dependency on the number of columns present in state-of-the-art constructions; its proof sizes are completely independent of the database size (without requiring any circuit representation).
One of our primary contributions is a foundational framework that cleanly separates VDB logic from cryptographic instantiations. At its essence, it resembles other common information theoretic frameworks, such as Polynomial Interactive Oracle Proofs (PIOPs). At the same time it diverges from existing approaches by being slightly specialized for the database setting. We demonstrate how to instantiate our framework using modern pairing-based linear-map vector commitments and set accumulators. More in general, we show that our building blocks can be derived from extractable homomorphic polynomial commitments. Being modular, our approach permits alternative instantiations, such as with lattice-based polynomial commitments enabling post-quantum security.
We implemented $\mathsf{qedb}$ in Rust and experimentally showed that it efficiently scales to datasets with millions of rows while maintaining competitive proving and verification times. This evidence indicates that our approach provides a foundation for practical, secure, and expressive verifiable database systems.
## 2025/1409
* Title: Oblivious (Un)Learning of Extremely Randomized Trees
* Authors: Sofiane Azogagh, Zelma Aubin Birba, S|-bastien Gambs, Marc-Olivier Killijian
* [Permalink](https://eprint.iacr.org/2025/1409)
* [Download](https://eprint.iacr.org/2025/1409.pdf)
### Abstract
While the use of homomorphic encryption (HE) for encrypted inference has received considerable attention, its application for the training of machine learning (ML) models remains comparatively underexplored, primarily due to the high computational overhead traditionally associated with fully homomorphic encryption (FHE).
In this work, we address this challenge by leveraging the inherent connection between inference and training in the context of Extremely Randomized Trees (ERT), thereby enabling efficient training directly over encrypted data.
More precisely, we instantiate this approach by the training of ERT within the TFHE framework.
Our implementation demonstrates that it is possible to train ERTs on encrypted datasets with a runtime significantly lower than current state-of-the-art methods for training Random Forests in the encrypted domain while achieving comparable predictive accuracy.
This result highlights a promising direction for practical privacy-preserving machine learning using FHE.
Our second main contribution consists in leveraging the properties of ERTs to create the first ML model that enables private unlearning. This approach makes the unlearning process indistinguishable from training, thus allowing clients to conceal the true nature of the operations being conducted on the model.
## 2025/1410
* Title: Nakamoto Consensus from Multiple Resources
* Authors: Mirza Ahad Baig, Christoph Ullrich G|+nther, Krzysztof Pietrzak
* [Permalink](https://eprint.iacr.org/2025/1410)
* [Download](https://eprint.iacr.org/2025/1410.pdf)
### Abstract
The blocks in the Bitcoin blockchain record the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF).
In this paper, we ask what weight functions +o(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.
We completely classify such functions in an idealized rCLcontinuousrCY model: +o(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the timed resources V and W, i.e., +#+o(S,V,W)=+o(S,+# V, +# W). This includes the Bitcoin rule +o(S,V,W)=W and the Chia rule +o(S,V,W) = S -+ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia).
Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W_1 and a memory-hard PoW W_2. Previous work suggested to use W_1+W_2 as weight. Our results show that using e.g., reU(W_1)-+reU(W_2) or min{W_1,W_2} are also secure, and we argue that in practice these are much better choices.
## 2025/1411
* Title: BACON: An Improved Vector Commitment Construction with Applications to Signatures
* Authors: Yalan Wang, Bryan Kumara, Harsh Kasyap, Liqun Chen, Sumanta Sarkar, Christopher J.P. Newton, Carsten Maple, Ugur Ilker Atmaca
* [Permalink](https://eprint.iacr.org/2025/1411)
* [Download](https://eprint.iacr.org/2025/1411.pdf)
### Abstract
All-but-one Vector Commitments (AVCs) allow a committed vector to be verified by randomly opening all but one of the committed values. Typically, AVCs are instantiated using Goldwasser-Goldreich-Micali (GGM) trees. Generating these trees comprises a significant computational cost for AVCs due to a large number of hash function calls. Recently, correlated GGM
(cGGM) trees were proposed to halve the number of hash calls and Batched AVCs (BAVCs) using one large GGM tree were integrated to FAEST to form the FAEST version 2 signature scheme, which improves efficiency and reduces the signature size. However, further optimizations on BAVC schemes remain possible.
Inspired by the large-GGM based BAVC and the cGGM tree, this paper proposes BACON, a BAVC with aborts scheme by leveraging a large cGGM tree. BACON executes multiple instances of AVC in a single batch and enables an abort mechanism to probabilistically reduce the commitment size. We prove that BACON is secure under the ideal cipher model and the random oracle model. We also discuss the possible application of the proposed BACON, i.e., FAEST version 2. Furthermore, because the number of hash calls in a large cGGM tree is halved compared with that used in a large GGM tree, theoretically, our BACON is more efficient than the state-of-the-art BAVC scheme.
## 2025/1412
* Title: AVPEU: Anonymous Verifiable Presentations with Extended Usability
* Authors: Yalan Wang, Liqun Chen, Yangguang Tian, Long Meng, Christopher J.P. Newton
* [Permalink](https://eprint.iacr.org/2025/1412)
* [Download](https://eprint.iacr.org/2025/1412.pdf)
### Abstract
The World Wide Web Consortium (W3C) has established standards for decentralized identities (DIDs) and verifiable credentials (VCs). A DID serves as a unique identifier for an entity, while a VC validates specific attributes associated with the DID holder. To prove ownership of credentials, users generate verifiable presentations (VPs). To enhance privacy, the W3C standards advocate for randomizable signatures in VC creation and zero-knowledge proofs for VP generation. However, these standards face a significant limitation: they cannot effectively verify cross-domain credentials while maintaining anonymity. In this paper, we present Anonymous Verifiable Presentations with Extended Usability (AVPEU), a novel framework that addresses this limitation through the introduction of a notary system. At the technical core of AVPEU lies our proposed randomizable message-hiding signature scheme. We provide both a generic construction of AVPEU and specific implementations based on Boneh-Boyen-Shacham (BBS), Camenisch-Lysyanskaya (CL), and Pointcheval-Sanders (PS) signature. Our experimental results demonstrate the feasibility of these schemes.
--- Synchronet 3.21a-Linux NewsLink 1.2