From Newsgroup: sci.crypt

## In this issue
1. [2025/278] New Techniques for Random Probing Security and ...
2. [2025/891] Obfuscation of Unitary Quantum Programs
3. [2025/897] SQIsign2DPush: Faster Signature Scheme Using ...
4. [2025/980] Formal Security and Functional Verification of ...
5. [2025/991] MOAI: Module-Optimizing Architecture for Non- ...
6. [2025/1294] Interstellar: Efficient GKR-based Folding/IVC ...
7. [2025/1301] Evaluating Larger Lookup Tables using CKKS
8. [2025/1601] Meet-in-the-Middle Attacks on Full ChiLow-32
9. [2025/1796] Efficient Fuzzy PSI Based on Prefix Representation
10. [2025/1800] Constructions of Efficiently Implementable Boolean ...
11. [2025/1808] Variables for Free: Fault Injection Attack on MAYO ...
12. [2025/1820] On the Plaintext Awareness of AEAD Schemes
13. [2025/1831] Authenticated Garbling with Tensor Gates
14. [2025/1832] Can Quantum Break ZUC? Only with a Million Qubits ...
15. [2025/1841] Pegasus and PegaRing: Efficient (Ring) Signatures ...
16. [2025/1843] Efficiency Improvements for Signal's Handshake Protocol
17. [2025/1850] Linear*-Time Permutation Check
18. [2025/1851] Locally Recoverable Data Availability Sampling
19. [2025/1852] A Gaussian Leftover Hash Lemma for Modules over ...
20. [2025/1853] Compact, Efficient and CCA-Secure Updatable ...
21. [2025/1854] Credential Revocation Assisted by a Covertly ...
22. [2025/1855] Less is More: On Copy Complexity in Quantum ...
23. [2025/1856] Optimal Good-Case Latency for Sleepy Consensus
24. [2025/1857] On the Quantum Equivalence between S|LWErf- and ISIS
25. [2025/1858] Testing Security Equivalence in the Random Probing ...
26. [2025/1859] qt-Pegasis: Simpler and Faster Effective Class ...
27. [2025/1860] On the generalized Sch||nhage-type bound
28. [2025/1861] FrodoKEM: A CCA-Secure Learning With Errors Key ...
29. [2025/1862] CuKEM: A Concise and Unified Hybrid Key ...
30. [2025/1863] On Limits on the Provable Consequences of Quantum ...
31. [2025/1865] High-Throughput AES Transciphering using CKKS: Less ...
32. [2025/1866] Succinct Line-Point Zero-Knowledge Arguments from ...
33. [2025/1867] Vectorized Falcon-Sign Implementations using SSE2, ...
34. [2025/1868] Is the Hard-Label Cryptanalytic Model Extraction ...
35. [2025/1869] Just How Secure is SRP, Really?
36. [2025/1870] Lookup-Table Evaluation over Key-Homomorphic ...
37. [2025/1871] A Unified Approach to Quantum Key Leasing with a ...
38. [2025/1872] Interoperable Symmetric Message Franking
39. [2025/1873] Threshold Reporting Protocol for Traceability in ...
40. [2025/1874] 0-ART. Asynchronous and Verifiable Group Management ...
41. [2025/1875] Generic-compatible distinguishers for linear ...
42. [2025/1876] SoK: Lookup Table Arguments
43. [2025/1877] Binary Codes for Computationally Bounded Errors ...
44. [2025/1878] MIRANDA: short signatures from a leakage-free full- ...
45. [2025/1879] A Minrank-based Encryption Scheme |a la Alekhnovich- ...
46. [2025/1880] Copy-Protection from Unclonable Puncturable ...
47. [2025/1881] Making Post Quantum Key Exchange Efficient: An ...
48. [2025/1882] MATCHI: formal verification of hardware private ...
49. [2025/1883] On the security of two blind signatures from code ...
50. [2025/1884] PERSEUS rCo Probabilistic Evaluation of Random ...
51. [2025/1885] Correction Fault Attack on CROSS under Unknown Bit ...
52. [2025/1886] Blind Signatures from Arguments of Inequality
53. [2025/1887] Parallel Spooky Pebbling Makes Regev Factoring More ...
54. [2025/1888] HCTR2-FP and HCTR3-FP: Format-Preserving Encryption ...
55. [2025/1889] Gluing Random Unitaries with Inverses and ...
56. [2025/1890] Cryptanalysis on Lightweight Verifiable Homomorphic ...
57. [2025/1891] Fraud Mitigation in Privacy-Preserving Attribution
58. [2025/1892] Optimizing FHEW-Like Homomorphic Encryption Schemes ...
59. [2025/1893] Poseidon2b: A Binary Field Version of Poseidon2
60. [2025/1894] Bounded-Equivocable Pseudorandom Functions
61. [2025/1895] Differential Fault Attacks on MQOM, Breaking the ...
62. [2025/1896] An Approach to Computable Contracts with Verifiable ...
63. [2025/1897] Dynark: Making Groth16 Dynamic
64. [2025/1898] Unique NIZKs and Steganography Detection
## 2025/278
* Title: New Techniques for Random Probing Security and Application to Raccoon Signature Scheme
* Authors: Sonia Bela|>d, Matthieu Rivain, M|-lissa Rossi
* [Permalink](https://eprint.iacr.org/2025/278)
* [Download](https://eprint.iacr.org/2025/278.pdf)
### Abstract
The random probing model formalizes a leakage scenario where each wire in a circuit leaks with probability $p$. This model holds practical relevance due to its reduction to the noisy leakage model, which is widely regarded as the appropriate formalization for power and electromagnetic side-channel attacks. In this paper, we present new techniques for designing efficient masking schemes that achieve tighter random probing security with lower complexity. First, we introduce the notion of \emph{cardinal random probing composability} (Cardinal-RPC), offering a new trade-off between complexity and security for composing masking gadgets. Next, we propose a novel refresh technique based on a simple iterative process: randomly selecting and updating two shares with fresh randomness. While not perfectly secure in the standard probing model, this method achieves arbitrary cardinal-RPC security, making it a versatile tool for constructing random-probing secure circuits. Using this refresh, we develop additional basic gadgets (e.g., linear multiplication, addition, and copy) that satisfy the cardinal-RPC notion. Despite the increased complexity, the gains in security significantly outweigh the overhead, with the number of iterations offering useful flexibility.
To showcase our techniques, we apply them to lattice-based signatures. Specifically, we introduce a new random-probing composable gadget for sampling small noise, a key component in various post-quantum algorithms. To assess security in this context, we generalize the random probing security model to address auxiliary inputs and public outputs. We apply our findings to Raccoon, a masking-friendly signature scheme originally designed for standard probing security. We prove the secure composition of our new gadgets for key generation and signature computation, and show that our masking scheme achieves a superior security-performance tradeoff compared to previous approaches based on random probing expansion. To our knowledge, this is the first fully secure instantiation of a post-quantum algorithm in the random probing model.
## 2025/891
* Title: Obfuscation of Unitary Quantum Programs
* Authors: Mi-Ying (Miryam) Huang, Er-Cheng Tang
* [Permalink](https://eprint.iacr.org/2025/891)
* [Download](https://eprint.iacr.org/2025/891.pdf)
### Abstract
Program obfuscation aims to hide the inner workings of a program while preserving its functionality. In the quantum setting, recent works have obtained obfuscation schemes for specialized classes of quantum circuits. For instance, Bartusek, Brakerski, and Vaikuntanathan (STOC 2024) constructed a quantum state obfuscation scheme, which supports the obfuscation of quantum programs represented as quantum states for pseudo-deterministic quantum programs with classical inputs and outputs in the classical oracle model.
In this work, we improve upon existing results by constructing the first quantum state obfuscation scheme for unitary (or approximately unitary) quantum programs supporting quantum inputs and outputs in the classical oracle model. At the core of our obfuscation scheme are two novel ingredients: a functional quantum authentication scheme that allows key holders to learn specific functions of the authenticated quantum state with simulation-based security, and a compiler that represents an arbitrary quantum circuit as a projective linear-plus-measurement quantum program described by a sequence of non-adaptive Clifford gates interleaved with adaptive and compatible measurements.
## 2025/897
* Title: SQIsign2DPush: Faster Signature Scheme Using 2-Dimensional Isogenies
* Authors: Kohei Nakagawa, Hiroshi Onuki
* [Permalink](https://eprint.iacr.org/2025/897)
* [Download](https://eprint.iacr.org/2025/897.pdf)
### Abstract
Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition for additional signature. SQIsign has attracted much attention because of its very short signature and key size among candidates for the NIST PQC standardization. Recently, many new signature schemes using high-dimensional isogenies have been proposed, such as: SQIsignHD, SQIsign2D-West, SQIsgn2D-East, and SQIPrime. Last year, SQIsign advanced to Round 2 of the NIST competition and was updated to version 2.0 (we call it SQIsign-v2.0), which is based on SQIsign2D-West. SQIsign-v2.0 achieves smaller signature sizes and faster verification. However, the signing costs are relatively high. In this paper, we propose a new signature scheme `SQIsign2DPush', which has a smaller signing cost than SQIsign-v2.0 while the signature size and the verification cost are almost the same.
## 2025/980
* Title: Formal Security and Functional Verification of Cryptographic Protocol Implementations in Rust
* Authors: Karthikeyan Bhargavan, Lasse Letager Hansen, Franziskus Kiefer, Jonas Schneider-Bensch, Bas Spitters
* [Permalink](https://eprint.iacr.org/2025/980)
* [Download](https://eprint.iacr.org/2025/980.pdf)
### Abstract
We present an effective methodology for the formal verification of
practical cryptographic protocol implementations written in
Rust. Within a single proof framework, we show how to develop
machine-checked proofs of diverse properties like runtime safety,
parsing correctness, and cryptographic protocol security. All
analysis tasks are driven by the software developer who writes
annotations in the Rust source code and chooses a backend prover for
each task, ranging from a generic proof assistant like F$\star$ to
dedicated crypto-oriented provers like ProVerif and SSProve Our
main contribution is a demonstration of this methodology on Bert13,
a portable, post-quantum implementation of TLS 1.3 written in Rust
and verified both for security and functional correctness. To our
knowledge, this is the first security verification result for a
protocol implementation written in Rust, and the first verified
post-quantum TLS 1.3 library.
## 2025/991
* Title: MOAI: Module-Optimizing Architecture for Non-Interactive Secure Transformer Inference
* Authors: Linru Zhang, Xiangning Wang, Jun Jie Sim, Zhicong Huang, Jiahao Zhong, Huaxiong Wang, Pu Duan, Kwok Yan Lam
* [Permalink](https://eprint.iacr.org/2025/991)
* [Download](https://eprint.iacr.org/2025/991.pdf)
### Abstract
Privacy concerns have been raised in Large Language Models (LLM) inference when models are deployed in Cloud Service Providers (CSP). Homomorphic encryption (HE) offers a promising solution by enabling secure inference directly over encrypted inputs. However, the high computational overhead of HE remains a major bottleneck. To address this challenge, we propose MOAI, an efficient HE-based, non-interactive framework for secure transformer inference. MOAI gains significant efficiency improvement from: (1) a novel evaluation flow that combines column and diagonal packing with consistent strategies across all layers, eliminating expensive format conversions. (2) rotation-free algorithms for Softmax and LayerNorm that significantly reduce the number of costly HE rotations, removing 2448 HE rotations in BERT-base inference. (3) Column packing removes rotations in plaintextrCociphertext matrix multiplications and interleaved batching further reduces the rotations in ciphertextrCociphertext matrix multiplications. MOAI uses at least 1.7x fewer HE rotations compared to the state-of-the-art works across all matrix multiplications of BERT-base. As a result, We achieve a 52.8% reduction in evaluation time compared to the state-of-the-art HE-based non-interactive secure transformer inference, THOR (Moon et al., CCSrCO25). We then apply MOAI on the PowerformerrCOs framework and achieve a 55.7% reduction in evaluation time compared to Powerformer (Park et al., ACLrCO25), which approximates Softmax and LayerNorm with simpler functions in transformer and proposes HE-based non-interactive transformer inference. We report an amortized time of 2.36 minutes per input on a single GPU environment. We show the extendibility by applying MOAI in LLaMA-3-8B. Our implementation is publicly available as open source.
## 2025/1294
* Title: Interstellar: Efficient GKR-based Folding/IVC Scheme with Collaborative Folding Extension
* Authors: Jieyi Long
* [Permalink](https://eprint.iacr.org/2025/1294)
* [Download](https://eprint.iacr.org/2025/1294.pdf)
### Abstract
In this paper, we present Interstellar, a novel folding and IVC framework built on a technique we call circuit interpolation, designed specifically for circuit satisfiability. By incorporating the GKR protocol, our approach avoids commitments to full computation traces and cross-term vectors, requiring instead only commitments to the actual circuit witness and optionally a small subset of intermediate gate values. This design significantly reduces the size of the vectors to be committed to in each folding step, which is highly advantageous compared to existing schemes, as vector commitments involve costly group multi-scalar multiplications. Moreover, Interstellar is highly flexible. It can be extended to handle high-degree and lookup gates, enable multi-instance folding, and support non-uniform IVC efficiently, making it well-suited for practical applications ranging from zkML to proving program execution for zkVMs. Finally, we introduces a new concept called collaborative folding/IVC which allows multiple provers, each holding a private witness for the same public statement, to jointly perform the folding/IVC computation while preserving witness privacy. This extension makes Interstellar suitable for distributed and privacy-sensitive applications.
## 2025/1301
* Title: Evaluating Larger Lookup Tables using CKKS
* Authors: Jules Dumezy, Andreea Alexandru, Yuriy Polyakov, Pierre-Emmanuel Clet, Olive Chakraborty, Aymen Boudguiga
* [Permalink](https://eprint.iacr.org/2025/1301)
* [Download](https://eprint.iacr.org/2025/1301.pdf)
### Abstract
The Cheon-Kim-Kim-Song (CKKS) scheme is a fully homomorphic encryption scheme that traditionally supports only the evaluation of smooth functions. Recent works have enabled the evaluation of arbitrary (discontinuous) integer functions represented as lookup tables (LUT) on small inputs using the method of functional bootstrapping (FBT). Although well-suited for small integers (up to around 10 bits), the efficiency of FBT quickly declines for large LUTs, and a considerable increase in both runtime and memory requirements is observed. Building on CKKS functional bootstrapping, we propose in this paper two functional bootstrapping algorithms, specifically designed to target larger LUTs (up to 20 bits). For a 16-bit LUT, our implementation in OpenFHE achieves a speed-up of 47.5 in amortized time and 95.1 in latency for single-threaded execution, compared to the state-of-the-art CKKS-based functional bootstrapping method of Alexandru et al. (CRYPTO'25).
## 2025/1601
* Title: Meet-in-the-Middle Attacks on Full ChiLow-32
* Authors: Eran Lambooij, Patrick Neumann, Michiel Verbauwhede, Shichang Wang, Tianyu Zhang
* [Permalink](https://eprint.iacr.org/2025/1601)
* [Download](https://eprint.iacr.org/2025/1601.pdf)
### Abstract
This work presents the first full-round attacks on ChiLow-32 and ChiLow-40, two tweakable low-latency block ciphers presented at EUROCRYPT'25.
We first describe a straightforward Meet-in-the-Middle attack on full ChiLow-32 with multiple known plaintext-ciphertext pairs.To improve this attack, we carefully evaluate the dependencies in ChiLow, to remove equivalent keys and reduce the number of key guesses. With a novel method to propagate differences through multiple ChiChi functions and to map out the state-dependencies, we optimize the attack on ChiLow-32.This results in an attack with time complexity $2^{120.34}$ using $160$ known plaintext-ciphertext pairs, and an attack with time complexity $2^{102.09}$ using $64$ chosen ciphertexts.
To attack ChiLow-40, we introduce a method that uses multiple sets of chosen plaintexts for different tweaks to reduce the amount of key material that has to be guessed in the Meet-in-the-Middle step. The final time complexity of this attack is $2^{123.58}$ with $2^{20}$ chosen plaintexts. All of our attacks are within ChiLow's security model, and are currently the best and only known key recovery attacks on full-round ChiLow-32 and ChiLow-40.
## 2025/1796
* Title: Efficient Fuzzy PSI Based on Prefix Representation
* Authors: Chengrui Dang, Xv Zhou, Bei Liang
* [Permalink](https://eprint.iacr.org/2025/1796)
* [Download](https://eprint.iacr.org/2025/1796.pdf)
### Abstract
Fuzzy PSI is a variant of PSI, which on input a set of points from the receiver and sender respectively, allows the receiver to learn which of the sender's points lie within a threshold distance $\delta$ under a specific distance metric.
Baarsen and Pu (EUROCRYPT'24) first proposed efficient fuzzy PSI protocols for general $L_{p}$ distances (where $p \in [1, \infty]$) in $d$-dimensional space, achieving communication complexity linear in the input size, $\delta$, and $2^d d$. However, they leave open the question of whether the prefix technique of Chakraborti et al. (USENIX Security'23) can further reduce the communication complexity of their fuzzy PSI protocols in both low and high dimensions.
In this work, we thoroughly explore using the prefix technique to reduce the complexity of fuzzy PSI. First, we propose fuzzy matching protocols for $L_{\infty}$ and $L_p$ distances, where the communication complexity is improved from $O(\delta d)$ to $O(\log\delta\, d)$ for $L_\infty$, and from $O(\delta^p)$ to $O((\log \delta)^d p)$ for $L_p$ distance. By applying our fuzzy matching protocol in conjunction with spatial hashing, we propose fuzzy PSI protocols for low-dimensional space. For high-dimensional space, we present the first fuzzy PSI protocols achieving communication and computation complexity that scales logarithmically in $\delta$ and linearly in dimension $d$ and input set sizes.
We implement our fuzzy PSI protocols and compare them with state-of-the-art protocols. Experimental results demonstrate that our protocols achieve superior performance for large $\delta$: for input size $N=2^8$, $d=5$, and $\delta=256$, our protocol requires $10$--$36\times$ less running time and $3$--$4.5\times$ lower communication than existing protocols.
## 2025/1800
* Title: Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs
* Authors: Palash Sarkar
* [Permalink](https://eprint.iacr.org/2025/1800)
* [Download](https://eprint.iacr.org/2025/1800.pdf)
### Abstract
We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In particular, the following statement holds for each of the function families that we propose. Given integers $m_0\geq 0$, $x_0\geq 1$, and $a_0\geq 1$, it is possible to construct an $n$-variable function which has resiliency at least $m_0$, linear bias (which is an equivalent method of expressing nonlinearity) at most $2^{-x_0}$ and algebraic immunity at least $a_0$; further, $n$ is linear in $m_0$, $x_0$ and $a_0$, and the function can be implemented using $O(n)$ 2-input gates, which is essentially optimal.
## 2025/1808
* Title: Variables for Free: Fault Injection Attack on MAYO via Valid Solutions * Authors: Yadi Zhong
* [Permalink](https://eprint.iacr.org/2025/1808)
* [Download](https://eprint.iacr.org/2025/1808.pdf)
### Abstract
Abstract. Multivariate quadratic problem over a finite field, a NP-hard problem, is also considered as one of the hard problems for cryptanalytic-relevant quantum computers. It is the foundation of multivariate quadratic-based cryptography and several post-quantum digital signature schemes initially proposed in 1990s. PatarinrCOs unbalanced Oil-and-Vinegar (UOV) scheme is the oldest MQ signature algorithm that remain secure against large-scale cryptanalytic-relevant quantum computers. UOV has compact signature size and succinct verification time. However, it suffers from a very large public key size. Subsequently, UOV-based variants have focused on minimizing the size of central map. MAYO, a candidate advanced to NISTrCOs round 2 additional post-quantum digital signatures, is based off the UOV algorithm with whipped structure to reduce public key size. In this paper, we present a theoretical framework for fault injection-based attack. It targets the construction of valid signatures during the signing phase. This fault-based analysis allows efficient extraction of secret oil vectors from the public signatures, facilitating the complete recovery of the entire secret oil space O. Finally, we show that this analysis is applicable to parameter sets of all three security level of all versions of MAYO.
## 2025/1820
* Title: On the Plaintext Awareness of AEAD Schemes
* Authors: Mario Marhuenda Beltr|in, Mustafa Khairallah
* [Permalink](https://eprint.iacr.org/2025/1820)
* [Download](https://eprint.iacr.org/2025/1820.pdf)
### Abstract
Plaintext-awareness of AEAD schemes is one of the more obscure and
easily misunderstood notions. Originally proposed by Andreeva et al., Mennink and Talnikar 2025 showed that the original definitions are vague and leave too much room for interpretation. They presented new definitions and analyzed the three main AEAD compositions relative to the new definitions. In particular, they showed that MAC-then-Encrypt (MtE) is not plaintext-aware. However, they showed that an SIV-style variant is indeed plaintext-aware. In this work, we first show that their analysis contains a gap, voiding their proof. We show this by showing several attacks; against their choice of extractor, with trivial complexity, and against any extractor, with birthday-bound complexity. Next, we re-establish their results by designing a new extractor that captures their intended goal and prove a tight PA1 security bound. We also show that the result is not dependent on the encryption scheme used, by showing that an extractor can also be designed for sMtE[+yCB3], a variant where the encryption step is done by an +yCB3-like scheme. Afterwards, we strengthen their results, by revisiting other compositions. In particular, we show that Encrypt-then- MAC (EtM) is in fact PA2-secure. Furthermore, we show that SIV-style MtE cannot be PA2-secure. Additionally, we also show that Encode-then-Encipher is PA2-secure, but not beyond the first successful forgery. More importantly, we show that up to some necessary assumptions, PA2 and RAE are equivalent.
Last but not least, we investigate the value of the notion of plaintext awareness. We look deeper into the relation between plaintext awareness and confidentiality. We show that the problem of confidentiality in the presence of release of unverified plaintext can be seen as a confidentiality-with-leakage problem in the simulatable leakage framework. In this regard, we start, by showing that PA1 security cannot imply confidentiality with leakage. Similarly, we compare our results to the AERUP notion of TOSC 2019. We show that a scheme can be AERUP secure but not secure against a somewhat straightforward left-or-right attack in the same model. This puts into question the meaning and relevance of the PA1 and AERUP security notions. These results can be seen as providing security in a two-phase game, where the adversary does not observe any leakage after the first challenge query, as we argue in the paper. On the positive side, we show that if a scheme achieves IND-CPA, INT-RUP and PA2, then it achieves confidentiality with leakage for the appropriate leakage function. This closes a gap in the literature on the relation between confidentiality with leakage and RUP notions.
## 2025/1831
* Title: Authenticated Garbling with Tensor Gates
* Authors: David Heath, Nakul Khambhati, Rafail Ostrovsky, Turan Vural
* [Permalink](https://eprint.iacr.org/2025/1831)
* [Download](https://eprint.iacr.org/2025/1831.pdf)
### Abstract
Authenticated garbling, introduced by Wang et al., CCS'17, is a leading paradigm for achieving constant-round maliciously-secure 2PC. In this work, we upgrade authenticated garbling to efficiently support tensor gates (introduced in the context of semi-honest garbling by Heath et al., CCS'21) using the one-hot garbling technique. Our maliciously-secure garbled tensor gate computes $\boldsymbol {x}\otimes \boldsymbol{y}$ for $\boldsymbol{x}\in \{0,1\}^n,\boldsymbol{y} \in \{0,1\}^m$ with $O(n+m)\kappa + O(nm)$ bits of communication, where $\kappa$ is the computational security parameter and $n,m$ are logarithmic in $\kappa$. This improves the best prior constant-round maliciously secure approach, which incurs $O(nm)\kappa$ communication.
Our protocol is concretely efficient and improves over state-of-the-art for applications including integer multiplication, matrix multiplication, and more. We benchmark the online phase of our protocol and observe a $5.41\times$ improvement in communication and $3.35\times$ improvement in wall clock time when computing a $128\times 128$ bit tensor product.
## 2025/1832
* Title: Can Quantum Break ZUC? Only with a Million Qubits and a Billion Years to Spare
* Authors: Anik Basu Bhaumik, Suman Dutta, Siyi Wang, Anubhab Baksi, Kyungbae Jang, Amit Saha, Hwajeong Seo, Anupam Chattopadhyay
* [Permalink](https://eprint.iacr.org/2025/1832)
* [Download](https://eprint.iacr.org/2025/1832.pdf)
### Abstract
The ZUC stream cipher is integral to modern mobile communication standards, including 4G and 5G, providing secure data transmission across global networks. Recently, Dutta et al. (Indocrypt, 2024) presented the first quantum resource estimation of ZUC under Grover's search, Although preliminary, this work marks the beginning of quantum security analysis for ZUC. In this paper, we present an improved quantum resource estimation for ZUC, offering tighter bounds for Grover-based exhaustive key search. Beyond traditional quantum resource estimations, we also provide a concrete timescale required to execute such attacks using the specified quantum resources. Our findings show that a full-round, low depth implementation of ZUC-128 can be realized with a maximum of $375$ ancilla qubits, a T-count of $106536$, and a T-depth of $15816$. Furthermore, the Grover-based key search can be performed most efficiently using $1201$ logical qubits, $170681$ T gates, and a T-depth of $78189$, resulting in a runtime of $1.78\times10^{11}$ years, an improvement of 93.43% over the estimated $2.71 \times 10^{12}$ years by the implementation given by Dutta et al., we also provide akin analysis for ZUC-256 with an 99.23% decrease in time. These estimations are done assuming state-of-the-art superconducting qubit error-correcting technology.
## 2025/1841
* Title: Pegasus and PegaRing: Efficient (Ring) Signatures from Sigma-Protocols for Power Residue PRFs with (Q)ROM Security
* Authors: Xinyu Zhang, Ziyi Li, Ron Steinfeld, Raymond K. Zhao, Joseph K. Liu, Tsz Hon Yuen
* [Permalink](https://eprint.iacr.org/2025/1841)
* [Download](https://eprint.iacr.org/2025/1841.pdf)
### Abstract
In this work, we present a novel commit-and-open $\Sigma$-protocol based on the Legendre and power residue PRFs. Our construction leverages the oblivious linear evaluation (OLE) correlations inherent in PRF evaluations and requires only black-box access to a tree-PRG-based vector commitment. By applying the standard Fiat-Shamir transform, we obtain a post-quantum signature scheme, Pegasus, which achieves short signature sizes (6025 to 7878 bytes) with efficient signing (3.910 to 19.438 ms) and verification times (3.942 to 18.999 ms). Furthermore, by pre-computing the commitment phase, the online response time can be reduced to as little as 0.047 to 0.721 ms. We prove the security of Pegasus in both the classical random oracle model (ROM) and the quantum random oracle model (QROM), filling a gap left by prior PRF-based signature schemes.
We further develop a ring signature scheme, PegaRing, that preserves the three-move commit-and-open structure of Pegasus. Compared to previous PRF-based ring signature called DualRing-PRF (ACISP 2024), PegaRing reduces the constant communication overhead by more than half and achieves significantly faster signing and verification. For a ring size of 1024, PegaRing yields signatures of 29 to 32 KB, with signing times of 8 to 44 ms, and verification times of 6 to 31 ms, depending on the parameters. Finally, we prove the security of PegaRing in both the ROM and the QROM, which is, to the best of our knowledge, the first symmetric-key primitives-based ring signature with practical performances and provable QROM security.
## 2025/1843
* Title: Efficiency Improvements for Signal's Handshake Protocol
* Authors: Barbara Jiabao Benedikt, Sebastian Clermont, Marc Fischlin, Tobias Schmalz
* [Permalink](https://eprint.iacr.org/2025/1843)
* [Download](https://eprint.iacr.org/2025/1843.pdf)
### Abstract
Signal's handshake protocol non-interactively generates a shared key between two parties for secure communication. The underlying protocol X3DH, on which the post-quantum hybrid successor, PQXDH, builds, computes three to four individual Diffie-Hellman (DH) keys by combining the long-term identity keys and the ephemeral secrets of the two parties. Each of these DH operations serves a different purpose, either to authenticate the derived key or to provide forward secrecy.
We present here an improved protocol for X3DH, which we call MuDH, and an improved protocol for PQXDH, pq-MuDH. Instead of computing the individual DH keys, we run a single multi-valued DH operation for integrating all contributions simultaneously into a single DH key. Our approach is based on techniques from batch verification (Bellare et al., Eurocrypt 1998), where one randomizes each contribution of the individual keys to get a secure scheme.
The solution results in execution times of roughly 60% of the original protocol, both in theory and in our benchmarks on mobile and desktop platforms. Our modifications are confined to the key derivation step, both SignalrCOs server infrastructure for public key retrieval and the message flow remain unchanged.
## 2025/1850
* Title: Linear*-Time Permutation Check
* Authors: Benedikt B|+nz, Jessica Chen, Zachary DeStefano
* [Permalink](https://eprint.iacr.org/2025/1850)
* [Download](https://eprint.iacr.org/2025/1850.pdf)
### Abstract
Permutation and lookup arguments are at the core of most deployed SNARK protocols today. Most modern techniques for performing them require a grand product check. This requires either committing to large field elements (E.g. in Plonk) or using GKR (E.g. in Spartan) which has worse verifier cost and proof size. Sadly, both have a soundness error that grows linearly with the input size.
We present two permutation arguments that have $\text{polylog}(n)/|\mathbb{F}|$ soundness error -- for reasonable input size $n=2^{32}$ and field size $|\mathbb{F}|=2^{128}$, the soundness error improves significantly from $2^{-96}$ to $2^{-120}$. Moreover, the arguments achieve $\log(n)$ verification cost and proof size without ever needing to commit to anything beyond the witness.
$\mathsf{BiPerm}$ only requires the prover to perform $O(n)$ field operations on top of committing to the witness, but at the cost of limiting the choices of PCS.
We show a stronger construction, $\mathsf{MulPerm}$, which has no restriction on the PCS choice and its prover performs essentially linear field operations, $n\cdot \tilde O(\sqrt{\log(n)})$.
Our permutation arguments generalize to lookups.
We demonstrate how our arguments can be used to improve SNARK systems such as HyperPlonk and Spartan, and build a GKR-based protocol for proving non-uniform circuits.
## 2025/1851
* Title: Locally Recoverable Data Availability Sampling
* Authors: Seunghyun Cho, Eunyoung Seo, Young-Sik Kim
* [Permalink](https://eprint.iacr.org/2025/1851)
* [Download](https://eprint.iacr.org/2025/1851.pdf)
### Abstract
We propose Locally Recoverable Data Availability Sampling (LR-DAS), which upgrades binary, threshold-based availability to graded verification by leveraging optimal locally recoverable codes (e.g., Tamo-Barg). Local groups of size $r+\alpha$ serve as atomic certification units: once $r$ verified openings fix a degree-$<r$ local polynomial, the entire group is certified and accumulates monotonically toward global availability. We formalize a locality-aware commitment with a single algebraic local-global link that binds every accepted local proof to a unique global codeword, preventing cross-group splicing. Our verifier admits a two-tier IOP view (local RS-membership, global TB-proximity, one DEEP-style linking query). We instantiate this with (i) a two-layer KZG design and (ii) a transparent FRI/IOPP stack. Both support batched multi-point openings and cross-block random-weight aggregation, yielding $\mathcal{O}(1)$ verifier work per certified batch with $\mathcal{O}(r+\alpha)$ field payload per block. Security is captured by graded soundness against missing-fraction and missing-group adversaries with explicit overshoot bounds. A lightweight proof-of-custody layerrCoone unpredictable global opening at publish time plus periodic batched local checksrCocomposes seamlessly to enforce possession without altering the core pipeline. Empirically and analytically, LR-DAS certifies availability with fewer samples than required for global recovery under the same encoding, providing a practical univariate alternative to multivariate repair-based DAS while retaining succinct proofs and a simple prover/verifier pipeline. Design levers $(r,\alpha)$ allow tuning responsiveness versus distance, and the transparent instantiation offers a post-quantum-ready option.
## 2025/1852
* Title: A Gaussian Leftover Hash Lemma for Modules over Number Fields
* Authors: Martin R. Albrecht, Jo|2l Felderhoff, Russell W. F. Lai, Oleksandra Lapiha, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2025/1852)
* [Download](https://eprint.iacr.org/2025/1852.pdf)
### Abstract
Leftover Hash Lemma (LHL) states that \(\mathbf{X} \cdot \mathbf{v}\) for a Gaussian \(\mathbf{v}\) is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of \(\mathbf{v}\). We generalise the Gaussian LHL initially stated over \(\mathbb{Z}\) by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: \(\lVert\mathbf{v}\rVert/\lVert\mathbf{X}\rVert\). To this end, we also prove when \(\mathbf{X}\) is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of \(\mathbf{X}\). We also establish when the resulting distribution is independent of the geometry of \(\mathbf{X}\) and establish the hardness of the \(k\)-SIS and \(k\)-LWE problems over modules (\(k\)-MSIS/\(k\)-MLWE) based on the hardness of SIS and LWE over modules (MSIS/MLWE) respectively, which was assumed without proof in prior works.
## 2025/1853
* Title: Compact, Efficient and CCA-Secure Updatable Encryption from Isogenies * Authors: Antonin Leroux, Maxime Rom|-as
* [Permalink](https://eprint.iacr.org/2025/1853)
* [Download](https://eprint.iacr.org/2025/1853.pdf)
### Abstract
Updatable Encryption (UE) allows ciphertexts to be updated under new keys without decryption, enabling efficient key rotation. Constructing post-quantum UE with strong security guarantees is challenging: the only known CCA-secure scheme, COM-UE, uses bitwise encryption, resulting in large ciphertexts and high computational costs.
We introduce DINE, a CCA-secure, isogeny-based post-quantum UE scheme that is both compact and efficient. Each encryption, decryption, or update requires only a few power-of-2 isogeny computations in dimension 2 to encrypt 28B messages, yielding 320B ciphertexts and 224B update tokens at NIST security level 1---significantly smaller than prior constructions. Our full C implementation demonstrates practical performances: updates in 7ms, encryptions in 48ms, and decryptions in 86ms.
Our design builds on recent advances in isogeny-based cryptography, combining high-dimensional isogeny representations with the Deuring correspondence. We also introduce new algorithms for the Deuring correspondence which may be of independent interest. Moreover, the security of our scheme relies on new problems that might open interesting perspectives in isogeny-based cryptography.
## 2025/1854
* Title: Credential Revocation Assisted by a Covertly Corrupted Server
* Authors: Alisa Pankova, Jelizaveta Vakarjuk
* [Permalink](https://eprint.iacr.org/2025/1854)
* [Download](https://eprint.iacr.org/2025/1854.pdf)
### Abstract
European Digital Identity (EUDI) Wallet aims to provide end users with a way to get attested credentials from issuers, and present them to different relying parties. An important property mentioned in the regulatory frameworks is the possibility to revoke a previously issued credential. While it is possible to issue a short-lived credential, in some cases it may be inconvenient, and a separate revocation service which allows to revoke a credential at any time may be necessary.
In this work, we propose a full end-to-end description of a generic credential revocation system, which technically relies on a single server and secure transmission channels between parties. We prove security of the proposed revocation functionality in the universal composability model, and estimate its efficiency based on a proof-of-concept implementation.
## 2025/1855
* Title: Less is More: On Copy Complexity in Quantum Cryptography
* Authors: Prabhanjan Ananth, Eli Goldin
* [Permalink](https://eprint.iacr.org/2025/1855)
* [Download](https://eprint.iacr.org/2025/1855.pdf)
### Abstract
Quantum cryptographic definitions are often sensitive to the number of copies of the cryptographic states revealed to an adversary. Making definitional changes to the number of copies accessible to an adversary can drastically affect various aspects including the computational hardness, feasibility, and applicability of the resulting cryptographic scheme. This phenomenon appears in many places in quantum cryptography, including quantum pseudorandomness and unclonable cryptography.
To address this, we present a generic approach to boost single-copy security to multi-copy security and apply this approach to many settings. As a consequence, we obtain the following new results:
rCo One-copy stretch pseudorandom state generators (under mild assumptions) imply the existence of t-copy stretch pseudorandom state generators, for any fixed polynomial t.
rCo One-query pseudorandom unitaries with short keys (under mild assumptions) imply the existence of t-query pseudorandom unitaries with short keys, for any fixed polynomial t.
rCo Assuming indistinguishability obfuscation and other standard cryptographic assumptions, there exist identical-copy secure unclonable primitives such as public-key quantum money and quantum copy-protection.
## 2025/1856
* Title: Optimal Good-Case Latency for Sleepy Consensus
* Authors: Yuval Efron, Joachim Neu, Ling Ren, Ertem Nusret Tas
* [Permalink](https://eprint.iacr.org/2025/1856)
* [Download](https://eprint.iacr.org/2025/1856.pdf)
### Abstract
In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a BB or BA protocol under certain favorable conditions, namely the designated leader being correct (for BB), or all parties having the same input value (for BA). We provide a full characterization of the feasibility and impossibility of good-case latency, for both BA and BB, in the synchronous sleepy model. Surprisingly to us, we find irrational resilience thresholds emerging: 2-round good-case BB is possible if and only if at all times, at least $\frac{1}{\varphi} \approx 0.618$ fraction of the active parties are correct, where $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ is the golden ratio; 1-round good-case BA is possible if and only if at least $\frac{1}{\sqrt{2}} \approx 0.707$ fraction of the active parties are correct.
## 2025/1857
* Title: On the Quantum Equivalence between S|LWErf- and ISIS
* Authors: Andr|- Chailloux, Paul Hermouet
* [Permalink](https://eprint.iacr.org/2025/1857)
* [Download](https://eprint.iacr.org/2025/1857.pdf)
### Abstract
Chen, Liu, and Zhandry [CLZ22] introduced the problems S|LWErf- and C|LWErf- as quantum analogues of the Learning with Errors problem, designed to construct quantum algorithms for the Inhomogeneous Short Integer Solution (ISIS) problem. Several later works have used this framework for constructing new quantum algorithms in specific cases. However, the general relation between all these problems is still unknown.
In this paper, we investigate the equivalence between S|LWErf- and ISIS. We present the first fully generic reduction from ISIS to S|LWErf-, valid even in the presence of errors in the underlying algorithms. We then explore the reverse direction, introducing an inhomogeneous variant of C|LWErf-, denoted IC|LWErf-, and show that IC|LWErf- reduces to S|LWErf-. Finally, we prove that, under certain recoverability conditions, an algorithm for ISIS can be transformed into one for S|LWErf-. We instantiate this reverse reduction by tweaking a known algorithm for (I)SISreR in order to construct quantum algorithm for S|LWErf- when the alphabet size q is a small power of 2, recovering some results of Bai et al. [BJK+ 25]. Our results thus clarify the landscape of reductions between S|LWErf- and ISIS, and we show both their strong connection as well as the remaining barriers for showing full equivalence.
## 2025/1858
* Title: Testing Security Equivalence in the Random-aProbing-aModel
* Authors: Anna Guinet, Carina Graw, Lukas Koletzko, Jan Richter-Brockmann, Holger Dette, Tim G|+neysu
* [Permalink](https://eprint.iacr.org/2025/1858)
* [Download](https://eprint.iacr.org/2025/1858.pdf)
### Abstract
The random probing model is a theoretical model that abstracts the physical leakage of an embedded device running a cryptographic scheme with more realistic assumptions compared to the threshold probing model. It assumes that the wires of the target device leak their assigned values with probability $p$, and the said values may reveal information about secret data, which could lead to a security violation. From that, we can compute the probability $\epsilon$ that a side-channel adversary may learn secret data from any random combination of wires as a function of the number of wire combinations that breaches security with rate $p$. This model is used to evaluate the security of masked cryptographic implementations, or simply named circuits; and the research community has been focusing so far on approximating or estimating the probability $\epsilon$ for one circuit. Yet, no proposition has been made to quickly compare the probability $\epsilon$ of different circuits, e.g., a circuit and its optimized version. In this context, we present two statistical tests to make decisions about the level of security in the random probing model: the equivalence test compares the security of two circuits in terms of $\epsilon$'s and the superiority test decides whether the undetermined $\epsilon$ of one circuit falls below a security threshold $\epsilon_0$, both with quantified uncertainty about the computations of the probabilities $\epsilon$'s. The validity of these tests is proven mathematically sound and verified via empirical studies on small masked S-boxes.
## 2025/1859
* Title: qt-Pegasis: Simpler and Faster Effective Class Group Actions
* Authors: Pierrick Dartois, Jonathan Komada Eriksen, Riccardo Invernizzi, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2025/1859)
* [Download](https://eprint.iacr.org/2025/1859.pdf)
### Abstract
In this paper, we revisit the recent PEGASIS algorithm that computes an effective group action of the class group of any imaginary quadratic order $R$ on a set of supersingular elliptic curves primitively oriented by $R$. Although PEGASIS was the first algorithm showing the practicality of computing unrestricted class group actions at higher security levels, it is complicated and prone to failures, which leads to many rerandomizations.
In this work, we present a new algorithm, qt-Pegasis, which is much simpler, but at the same time faster and removes the need for rerandomization of the ideal we want to act with, since it never fails. It leverages the main technique of the recent qlapoti approach. However, qlapoti solves a norm equation in a quaternion algebra, which corresponds to the full endomorphism ring of a supersingular elliptic curve. We show that the algorithm still applies in the quadratic setting, by embedding the quadratic ideal into a quaternion ideal using a technique similar to the one applied in KLaPoTi. This way, we can reinterpret the output of qlapoti as four equivalent quadratic ideals, instead of two equivalent quaternion ideals. We then show how to construct a Clapoti-like diagram in dimension $2$, which embeds the action of the ideal in a $4$-dimensional isogeny.
We implemented our qt-Pegasis algorithm in SageMath for the CSURF group action, and we achieve a speedup over PEGASIS of $1.8\times$ for the 500-bit parameters and $2.6\times$ for the 4000-bit parameters.
## 2025/1860
* Title: On the generalized Sch||nhage-type bound
* Authors: Theophilus Agama
* [Permalink](https://eprint.iacr.org/2025/1860)
* [Download](https://eprint.iacr.org/2025/1860.pdf)
### Abstract
We prove an extension of the lower bound due to Sch\"onhage on addition chains. ## 2025/1861
* Title: FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism
* Authors: Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, Fernando Virdia
* [Permalink](https://eprint.iacr.org/2025/1861)
* [Download](https://eprint.iacr.org/2025/1861.pdf)
### Abstract
Large-scale quantum computers capable of implementing Shor's algorithm pose a significant threat to the security of the most widely used public-key cryptographic schemes. This risk has motivated substantial efforts by standards bodies and government agencies to identify and standardize quantum-safe cryptographic systems. Among the proposed solutions, lattice-based cryptography has emerged as the foundation for some of the most promising protocols.
This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, "unstructured" lattices. FrodoKEM is proposed as an alternative to the more efficient lattice schemes that utilize algebraically structured lattices, such as the recently standardized ML-KEM scheme. By relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structures while enabling simple and compact implementations.
Our plain C implementations demonstrate that, despite its conservative design and parameterization, FrodoKEM remains practical. For instance, the full protocol at NIST security level 1 runs in approximately 0.97 ms on a server-class processor, and 4.98 ms on a smartphone-class processor.
FrodoKEM obtains (single-target) IND-CCA security using a variant of the Fujisaki-Okamoto transform, applied to an underlying public-key encryption scheme called FrodoPKE. In addition, using a new tool called the Salted Fujisaki-Okamoto (SFO) transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact, based on the multi-target IND-CPA security of FrodoPKE.
## 2025/1862
* Title: CuKEM: A Concise and Unified Hybrid Key Encapsulation Mechanism
* Authors: Yiting Liu, Biming Zhou, Haodong Jiang
* [Permalink](https://eprint.iacr.org/2025/1862)
* [Download](https://eprint.iacr.org/2025/1862.pdf)
### Abstract
In the post-quantum migration of the traditional key establishment protocol, hybrid key encapsulation mechanisms (KEMs) are recommended by standards bodies, including NIST, ETSI, and national security agencies like NCSC-UK, BSI-Germany etc.
Recently, several hybrid KEMs with CCA security such as XOR-then-MAC, Dual-PRF and X-Wing (being standardized by IETF) are proposed based on CCA KEMs obtained by applying the complicated Fujisaki-Okamoto transform to public-key encryption (PKE) schemes.
In some cryptographic protocols such as PQ-Noise and Signal, 1CCA security (similar to CCA security except that the adversary is restricted to one single decapsulation query) is required.
However, no specific scheme has been designed to specifically achieve 1CCA security (excluding the schemes that aim to achieve CCA security, as they inherently encompass 1CCA security).
In this paper, we propose CUKEM, a concise and unified hybrid KEM framework built directly on PKEs, and its variant CUKEM+, which achieves CCA security by replacing one PKE component with a nominal group. We prove that our schemes, equipped with different modules, achieve standard security notions in both the random oracle model and the quantum random oracle model, including IND-CPA, IND-1CCA, and IND-CCA. Compared to existing KEM-based constructions, CUKEM and CUKEM+ are more concise, as they simplify or even eliminate certain hash operations without compromising security. Our evaluation shows that the CCA-secure CUKEM+ achieves encapsulation and decapsulation speedups of up to 22.28% and 16.22%, respectively, over X-Wing, while the 1CCA-secure CUKEM attains gains of up to 13.97% and 104.31%.
## 2025/1863
* Title: On Limits on the Provable Consequences of Quantum Pseudorandomness
* Authors: Samuel Bouaziz--Ermann, Minki Hhan, Garazi Muguruza, Quoc-Huy Vu
* [Permalink](https://eprint.iacr.org/2025/1863)
* [Download](https://eprint.iacr.org/2025/1863.pdf)
### Abstract
There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), and pseudorandom function-like state generators (PRFSGs). Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relationship between quantum pseudorandomness has yet to be fully established.
We present some evidence suggesting that some quantum pseudorandomness is unlikely to be constructed from others, or at least is hard to construct unless some conjectures are false. This indicates that quantum pseudorandomness could behave quite differently from classical pseudorandomness. We study new oracle worlds where one form of quantum pseudorandomness exists but another does not, under certain assumptions or constraints, and we provide potential directions toward achieving full black-box separation. More precisely:
- We give a unitary oracle relative to which PRFSGs exist, but PRUs without using ancilla do not. This can be extended to general PRUs if a structural property of the PRU algorithm can be proven.
- Assuming a conjecture similar to an isoperimetric inequality, we show a unitary oracle world where log-length output PRFSGs exist, but proving the existence of quantum-computable pseudorandom generators (QPRGs) with negligible correctness error is as hard as proving that BQP rea QCMA. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent.
- Assuming the same conjecture, we prove that some natural methods of constructing super-log-length output PRSGs from log-length output PRFSGs are impossible. This partly complements the known hardness of shrinking the PRSG output lengths. Along the way, we also discuss other potential approaches to extend the PRSG output lengths.
All our worlds are based on (variants of) oracles that output Haar-random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states.
Our results highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting. As one of our key technical tools, we show an intriguing gentle behavior of intermediate measurements in algorithms producing outcome states with high purity, which may be of independent interest.
## 2025/1865
* Title: High-Throughput AES Transciphering using CKKS: Less than 1ms
* Authors: Youngjin Bae, Jung Hee Cheon, Minsik Kang, Taeseong Kim
* [Permalink](https://eprint.iacr.org/2025/1865)
* [Download](https://eprint.iacr.org/2025/1865.pdf)
### Abstract
Fully Homomorphic encryption (FHE) allows computation without decryption, but often suffers from a ciphertext expansion ratio and overhead. On the other hand, AES is a widely adopted symmetric block cipher known for its efficiency and compact ciphertext size. However, its symmetric nature prevents direct computation on encrypted data. Homomorphic transciphering bridges these two approaches by enabling computation on AES-encrypted data using FHE-encrypted AES keys, thereby combining the compactness of AES with the flexibility of FHE.
In this work, we present a high-throughput homomorphic AES transciphering based on the CKKS scheme. Our design takes advantage of the ring conversion technique to the conjugate-invariant ring \cite{real_heaan} during the transciphering circuit, including bootstrapping, along with a suite of optimizations that reduce computational overhead. As a result, we achieved a throughput (per-block evaluation time) of 0.994msrColess than 1msrCo outperforming the state-of-the-art \cite{xboot} by $1.58\times$ when processing $2^{15}$ AES-128 blocks under the same implementation environment, and support processing $2^{9}$ blocks within $3s$ on a single GPU.
## 2025/1866
* Title: Succinct Line-Point Zero-Knowledge Arguments from Homomorphic Secret Sharing
* Authors: Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan, Mengmeng Zhou
* [Permalink](https://eprint.iacr.org/2025/1866)
* [Download](https://eprint.iacr.org/2025/1866.pdf)
### Abstract
Dittmer, Ishai and Ostrovsky (ITC'21) proposed {\em line-point zero-knowledge proof} (LPZK), a simple ``commit-and-prove'' system, motivated by practical protocols for compressing correlated pseudorandomness used in secure multiparty computation (MPC). Typically, LPZK admits concretely efficient ZK protocols with a streaming, linear time prover, {\em but a linear size proof}. A natural question raised in the context is how far can we go in minimizing the proof size, while maintaining the prover efficiency. Though a recent work by Lin, Xing and Yao (ASIACRYPT'24) gives an interactive LPZK with a sublinear proof size $O(n+d^2\log{|\mathcal{C}|})$, it is still far from being {\em succinct}, where $n,d,|\mathcal{C}|$ are referred to as input size, circuit depth, and circuit size, respectively.
In this work, we beat the proof size barrier and propose {\em succinct LPZK arguments}, by distilling techniques from orthogonal studies on homomorphic secret sharing and succinct garbling.
Specifically, under variants of group/lattice-based assumptions, we show the followings:
i) There exist succinct LPZK arguments with common reference string (CRS) size $O(n^{2/3})$, proof size $O(n^{2/3})$, prover time $O(n^{4/3}+|\mathcal{C}|)$, verification time $O(n+|\mathcal{C}|)$, and negligible soundness error, where both the prover and the verifier executions and be run in a streaming fashion.
ii) The above proof size can be further optimized to $O(1)$, at the cost of a larger CRS size $O(n)$, and prover time increased to $O(n^{2}+|\mathcal{C}|)$.
In general, our succinct LPZK arguments pave a new way for building designated-verifier zero-knowledge succinct non-interactive arguments of knowledge (dv-zkSNARKs), and new interesting features (e.g., streaming, constant sized proof with CRS size not proportional to the circuit size) are obtained for the first time along the way.
## 2025/1867
* Title: Vectorized Falcon-Sign Implementations using SSE2, AVX2, AVX-512F, NEON, and RVV
* Authors: Jipeng Zhang, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2025/1867)
* [Download](https://eprint.iacr.org/2025/1867.pdf)
### Abstract
Falcon, a NTRU-based digital signature algorithm, has been selected by NIST as one of the post-quantum cryptography (PQC) standards. Compared to verification, the signature generation of Falcon is relatively slow. One of the core operations in signature generation is discrete Gaussian sampling, which involves a component known as the BaseSampler. The BaseSampler accounts for up to 30% of the time required for signature generation, making it a significant performance bottleneck. This work aims to address this bottleneck.
We design a vectorized version of the BaseSample and provide optimized implementations across six different instruction sets: SSE2, AVX2, AVX-512F, NEON, RISC-V Vector (RVV), and RV64IM. The AVX2 implementation, for instance, achieves an 8.4|u speedup over prior work. Additionally, we optimize the FFT/iFFT operations using RVV and RV64D. For the RVV implementation, we introduce a new method using strided load/store instructions, with 4+4 and 4+5 layer merging strategies for Falcon-512 and Falcon-1024, respectively, resulting in a speedup of more than 4|u.
Finally, we present the results of our optimized implementations across eight different instruction sets for signature generation of Falcon. For instance, our AVX2, AVX-512F, and RV64GCVB implementations achieve performance improvements of 23%, 36%, and 59%, respectively, for signature generation of Falcon-512.
## 2025/1868
* Title: Is the Hard-Label Cryptanalytic Model Extraction Really Polynomial?
* Authors: Akira Ito, Takayuki Miura, Yosuke Todo
* [Permalink](https://eprint.iacr.org/2025/1868)
* [Download](https://eprint.iacr.org/2025/1868.pdf)
### Abstract
Deep Neural Networks (DNNs) have attracted significant attention, and their internal models are now considered valuable intellectual assets. Extracting these internal models through access to a DNN is conceptually similar to extracting a secret key via oracle access to a block cipher. Consequently, cryptanalytic techniques, particularly differential-like attacks, have been actively explored recently. ReLU-based DNNs are the most commonly and widely deployed architectures. While early works (e.g., Crypto 2020, Eurocrypt 2024) assume access to exact output logits, which are usually invisible, more recent works (e.g., Asiacrypt 2024, Eurocrypt 2025) focus on the hard-label setting, where only the final classification result (e.g., "dog" or "car") is available to the attacker. Notably, Carlini et al. (Eurocrypt 2025) demonstrated that model extraction is feasible in polynomial time even under this restricted setting.
In this paper, we first show that the assumptions underlying their attack become increasingly unrealistic as the attack-target depth grows. In practice, satisfying these assumptions requires an exponential number of queries with respect to the attack depth, implying that the attack does not always run in polynomial time. To address this critical limitation, we propose a novel attack method called CrossLayer Extraction. Instead of directly extracting the secret parameters (e.g., weights and biases) of a specific neuron, which incurs exponential cost, we exploit neuron interactions across layers to extract this information from deeper layers. This technique significantly reduces query complexity and mitigates the limitations of existing model extraction approaches.
## 2025/1869
* Title: Just How Secure is SRP, Really?
* Authors: Jiayu Xu, Zhiyuan Zhao
* [Permalink](https://eprint.iacr.org/2025/1869)
* [Download](https://eprint.iacr.org/2025/1869.pdf)
### Abstract
An asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client and a server to agree upon a cryptographic key, with the only information shared in advance being a low-entropy password (memorized by the client) and a corresponding password file (stored in the server). The standard security definition for aPAKE is in the Universally Composable (UC) framework. Since aPAKE does not rely on a PKI, such protocols have received much attention in recent years due to their potential of replacing the traditional rCLpassword-over-TLSrCY approach for client-server authentication on the Internet.
One of the only two aPAKE protocols currently deployed in practice is Secure Remote Password (SRP) (Wu, NDSS 1998), which is used by millions of users on the Internet. A formal security analysis of SRP has long been elusive; the only security proof to date is the one by Dayanikli and Lehmann (CSF 2024) which is in a (somewhat non-standard) variant of UC called UC with angels. This framework allows the simulator access to an additional oracle that solves certain hard cryptographic problems.
In this work, we present a comprehensive new analysis of SRP, and clarify a number of ambiguities about its security:
1. We formally prove that the SRP is UC-secure if and only if one computational problem in the field is hard and one decisional problem is easy. As the decisional problem is likely hard in the field, this strongly suggests that SRP is not UC-secure and hence justifies the usage of UC with angels in the security analysis;
2. On the other hand, we show that the rCLangelrCY given to the simulator in the DayaniklirCoLehmann analysis is stronger than necessary, and can be replaced by a weaker oracle;
3. Finally, we prove that UC-with-angels-security is still stronger than the game-based security for aPAKE, i.e., SRP is still game-based secure under some reasonable assumptions.
Overall, we pinpoint the exact conditions under which SRP can be proven secure, reducing its security to a number of underlying hardness problems. Along the way we also identify and bridge multiple gaps in the DayaniklirCoLehmann analysis rCo most notably, the concrete security bound rCo and apply novel proof techniques that might find application in other contexts.
## 2025/1870
* Title: Lookup-Table Evaluation over Key-Homomorphic Encodings and KP-ABE for Nonlinear Operations
* Authors: Sora Suegami, Enrico Bottazzi
* [Permalink](https://eprint.iacr.org/2025/1870)
* [Download](https://eprint.iacr.org/2025/1870.pdf)
### Abstract
Lattice-based key-homomorphic encodings introduced by Boneh et al.~(Eurocrypt'14)---known as BGG+ encodings---underpin many primitives, including key-policy attribute-based encryption (KP-ABE). Many applications beyond KP-ABE require simulating the homomorphic evaluation of FHE ciphertexts over BGG+ encodings, which involves nonlinear operations on integers of magnitude up to the ciphertext modulus $q$. However, due to noise growth incurred by multiplication, the encodable integers must be kept small, typically bits, thereby forcing nonlinear operations to be simulated by Boolean circuits and incurring a circuit-size blow-up polynomial in $\log_2 q$. Apart from resorting to costly bootstrapping for BGG+ encodings, no method is known to beat this baseline.
We propose a method to evaluate lookup tables~(LUTs) over BGG+ encodings that operates directly on base-$B$ digit representations for $2<B<\sqrt{q}$, with noise growth independent of the magnitudes of the encoded integers. Consequently, this replaces the $\log_2 q$ factor in the circuit-size blow-up with $\log_{B} q$, yielding a reduction in evaluation time by a factor polynomial in $\log_2 B$. We obtain: (i) small-integer arithmetic with base-$B$ outputs in constant size; (ii) modulo-$q$ multiplication with circuit size quadratic in $\log_{B} q$; and (iii) homomorphic ciphertext multiplication in the Gentry--Sahai--Waters FHE scheme~(Crypto'13) with circuit size approximately cubic in $\log_{B} q$. As an application, we build a KP-ABE scheme that is selectively secure under the Ring-LWE assumption and compatible with our LUT evaluation method. This reduces decryption cost by a factor polynomial in $\log_2 B$ at the expense of a polynomial-in-$B$ increase in decryption-key generation cost and decryption-key size, which is an attractive trade-off because decryption is invoked far more frequently than key generation in ABE applications.
## 2025/1871
* Title: A Unified Approach to Quantum Key Leasing with a Classical Lessor
* Authors: Fuyuki Kitagawa, Jiahui Liu, Shota Yamada, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2025/1871)
* [Download](https://eprint.iacr.org/2025/1871.pdf)
### Abstract
Secure key leasing allows a cryptographic key to be leased as a quantum state in such a way that the key can later be revoked in a verifiable manner. In this work, we propose a modular framework for constructing secure key leasing with a classical-lessor, where the lessor is entirely classical and, in particular, the quantum secret key can be both leased and revoked using only classical communication. Based on this framework, we obtain classical-lessor secure key leasing schemes for public-key encryption (PKE), pseudorandom function (PRF), and digital signature. We adopt the strong security notion known as security against verification key revealing attacks (VRA security) proposed by Kitagawa et al. (Eurocrypt 2025) into the classical-lessor setting, and we prove that all three of our schemes satisfy this notion under the learning with errors assumption. Our PKE scheme improves upon the previous construction by Goyal et al. (Eurocrypt 2025), and our PRF and digital signature schemes are respectively the first PRF and digital signature with classical-lessor secure key leasing property.
## 2025/1872
* Title: Interoperable Symmetric Message Franking
* Authors: Carolina Ortega P|-rez, Thomas Ristenpart, Julia Len
* [Permalink](https://eprint.iacr.org/2025/1872)
* [Download](https://eprint.iacr.org/2025/1872.pdf)
### Abstract
The recent Digital Markets Act (DMA), a regulation passed by the European Union in 2022, requires messaging applications with large user bases to support interoperable end-to-end encrypted (E2EE) communication. This raises numerous questions about how to adapt cryptographic protocols to this setting in a way that preserves security and privacy. This question is not only limited to the main messaging protocols, but also extends to protocols for abuse mitigation such as the symmetric message franking protocol first proposed by Facebook. The latter uses symmetric cryptography to enable reporting abusive E2EE messages in a way that allows the platform to cryptographically verify the report's veracity.
In this paper, we initiate a formal treatment of interoperable symmetric message franking (IMF). We focus on a server-to-server messaging flow, where messages are routed sequentially through the sender's and recipient's service providers, but allow the recipient to dynamically choose who to send a report to. We formalize the security definitions for IMF including adapting the sender and recipient binding definitions into various reportability and unforgeability definitions that take into account one of the service providers misbehaving. We also prove relations among these new definitions. Finally, we detail an IMF construction that satisfies the security definitions, and include a discussion of users' identity privacy goals and deployment considerations.
## 2025/1873
* Title: Threshold Reporting Protocol for Traceability in Anonymous Social Networks
* Authors: Olivier Blazy, Lola-Baie Mallordy
* [Permalink](https://eprint.iacr.org/2025/1873)
* [Download](https://eprint.iacr.org/2025/1873.pdf)
### Abstract
As anonymous social networks continue to grow in popularity, they raise serious challenges around abuse, misinformation, and harmful behavior. While traditional de-anonymization techniques can address misuse, they often come at the cost of user privacy. Protecting honest users' privacy while keeping malicious ones accountable remains a complex challenge.
A promising alternative is conditional deanonymization, where anonymity is lifted only when abuse is collectively reported and verified by an authority.
In this work, we present a new cryptographic framework for conditional de-anonymization that preserves user anonymity unless a threshold number of validated abuse reports is reached. Our design leverages threshold cryptography to ensure that de-anonymization can only be triggered under well-defined, collectively enforced conditionsrCoresisting false reports, misuse, and collusion. We formalize the model and provide a generic construction from standard cryptographic primitives, proving strong security guarantees even in the presence of adversarial authorities or malicious users. To illustrate its viability, we also propose a concrete instantiation based on lattice-based assumptions, making it a compelling candidate for post-quantum settings.
## 2025/1874
* Title: 0-ART. Asynchronous and Verifiable Group Management for Decentralized Applications
* Authors: Yevhen Hrubiian, Illia Melnyk, Volodymyr Dubinin, Oleksandr Kurbatov, Serhii Volynets, Roman Perebynos, Yevhenii Serdiukov
* [Permalink](https://eprint.iacr.org/2025/1874)
* [Download](https://eprint.iacr.org/2025/1874.pdf)
### Abstract
The majority of modern e2e private applications face scalability issues that limit their functionality, broader adoption, and overall user experience. Some of them organize private groups as a set of peer-to-peer chats, which leads to an overall quadratic complexity in the size of group communication and a linear time complexity in the number of members for encryption. Others apply more scalable group key establishment constructions (such as ART), but at the same time, they do not support verifiable and concurrent updates. In this paper, we introduce the 0-ART protocol, which aims to address the aforementioned issues by (1) verifiable group operations; (2) a causal tree construction allowing for multiple concurrent updates and efficient member removal; (3) anonymous credentials, making privacy in the group available while keeping operations authentic. We implemented the 0-ART framework and applied it to a decentralized collaborative work application. According to our benchmark, executing the most complex operation (performing the provable $\mathsf{AddMember}$ operation in a group of size $2^{20}$) takes 1.57 seconds on the user's device and $24$Kb of proof size.
## 2025/1875
* Title: Generic-compatible distinguishers for linear regression based attacks * Authors: Sana Boussam
* [Permalink](https://eprint.iacr.org/2025/1875)
* [Download](https://eprint.iacr.org/2025/1875.pdf)
### Abstract
Non profiled attacks are a type of attacks in which an attacker aims at retrieving secret information from any device with no prior knowledge about leakage model characteristics. In practice, Differential Power Analysis (DPA), Correlation Power Analysis (CPA) and Linear Regression based Attack (LRA) which are the most common non profiled attacks require an a priori about leakage model to be used nowadays. The development of a generic attack in which no assumptions are made about the leakage model remains therefore an open issue to this day and has been investigated for over 10 years by the side channel community. Among all state-of-the-art non profiled attacks, it has been showed by Whitnall et al. that Linear Regression based Attack (LRA) corresponds to a generic attack when all predictors are considered i.e. LRA captures the dependencies between the bits of the secret information and their interactions and the physical traces. However, in practice, LRA cannot be carried out considering all predictors, as it is subject to multiple limitations, namely the problem of multicollinearity related to linear regression and the use of inappropriate distinguishers as the latter lose their discriminating ability when targeting injective functions. In this paper, we aim at finding a solution to this issue and providing a significant improvement in generic attacks research topic. First, we show that the use of Walsh-Hadamard basis prevent multicollinearity problem from which LRA suffers and allows thus to perform generic LRA i.e. LRA in which all predictors can be considered, without incuring a loss of precision of the estimated coefficients. From this observation, we demonstrate the limitations of using the classical distinguishers in LRA (i.e. Euclidean distance based distinguishers) and propose novel alternatives that are more suitable for LRA. To motivate the choice of these new distinguishers, we formally demonstrate their soundness against linear and non-linear operations. These choices result in the first generic non profiled attack which considers all predictors. Finally, we experimentally assess and validate all our theoretical results using simulations and publicly available datasets, thus covering a wide range of use-cases.
## 2025/1876
* Title: SoK: Lookup Table Arguments
* Authors: Hossein Hafezi, Gaspard Anthoine, Matteo Campanelli, Dario Fiore
* [Permalink](https://eprint.iacr.org/2025/1876)
* [Download](https://eprint.iacr.org/2025/1876.pdf)
### Abstract
Lookup arguments have become a central tool in proof systems, powering a range of practical applications. They enable the efficient enforcement of non-native operations, such as bit decomposition, range checks, comparisons, and floating-point arithmetic. They underpin zk-VMs by modelling instruction tables, provide set membership proofs in stateful computations, and strengthen extractors by ensuring witnesses belong to small domains.
Despite these broad uses, existing lookup constructions vary widely in assumptions, efficiency, and composability. In this work, we systematize the design of lookup arguments and the cryptographic primitives they rely on. We introduce a unified and modular framework that covers standard, projective, indexed, vector, and decomposable lookups. We classify existing protocols by proof techniquerComultiset equality, Logup-based, accumulators, and subvector extraction (matrixrCovector)rCoas well as by composition style. We survey and evaluate existing protocols along dimensions such as prover cost, dependence on table size, and compatibility with recursive proofs. From this analysis, we distill lessons and guidelines for choosing lookup constructions in practice and highlight the benefits and limitations of emerging directions in literature, such as preprocessing and decomposability.
## 2025/1877
* Title: Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions
* Authors: George Lu, Jad Silbak, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2025/1877)
* [Download](https://eprint.iacr.org/2025/1877.pdf)
### Abstract
We study error-detection and error-correction codes for computationally bounded adversarial channels. We consider seeded codes where the polynomial-time encoding and decoding procedures share a public random seed, but are otherwise deterministic. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct such errors with overwhelming probability, while achieving better trade-offs between rate and error tolerance than those possible for computationally unbounded channels.

For large alphabets, prior work (ITCS '25) achieves essentially optimal parameters under minimal cryptographic assumptions. However, for the binary alphabet, prior works (TCC '20, EUROCRYPT '25) either only achieved a weaker notion of selective security under the learning with errors (LWE) assumption, or relied on non-standard cryptographic assumptions to get the full notion of adaptive security.

In this work, we construct binary codes that achieve the full notion of adaptive security assuming trapdoor hashing, which can in turn be instantiated under a variety of standard cryptographic assumptions such as LWE, or Decisional Diffie-Hellman (DDH), or Quadratic Residuosity (QR), or Decisional Composite Residuosity (DCR). For error detection, our codes get essentially optimal rate $R \approx 1$ and relative error tolerance $p \approx \frac{1}{2}$. For error correction, they can uniquely correct $p < 1/4$ fraction of errors with a rate $R$ matching that of the best known list-decodable codes for this error tolerance.
As a central technical tool of potentially independent interest, we construct multi-input correlation intractable hashing for ``shifted output relations'' under the standard cryptographic assumptions above.
## 2025/1878
* Title: MIRANDA: short signatures from a leakage-free full-domain-hash scheme * Authors: Alain Couvreur, Thomas Debris-Alazard, Philippe Gaborit, Adrien Vin|ootte
* [Permalink](https://eprint.iacr.org/2025/1878)
* [Download](https://eprint.iacr.org/2025/1878.pdf)
### Abstract
We present Miranda, the first family of full-domain-hash signatures based on matrix codes. This signature scheme fulfils the paradigm of Gentry, Peikert and Vaikuntanathan (GPV), which gives strong security guarantees. Our trapdoor is very simple and generic: if we propose it with matrix codes, it can actually be instantiated in many other ways since it only involves a subcode of a decodable code (or lattice) in a unique decoding regime of parameters. Though Miranda signing algorithm relies on a decoding task where there is exactly one solution, there are many possible signatures given a message to sign and we ensure that signatures are not leaking information on their underlying trapdoor by means of a very simple procedure involving the drawing of a small number of uniform bits. In particular Miranda does not use a rejection sampling procedure which makes its implementation a very simple task contrary to other GPV-like signatures schemes such as Falcon or even Wave.
We instantiate Miranda with the famous family of Gabidulin codes represented as spaces of matrices and we study thoroughly its security (in the EUF-CMA security model). For 128 bits of classical security, the signature sizes are as low as 90 bytes and the public key sizes are in the order of 2.6 megabytes.
## 2025/1879
* Title: A Minrank-based Encryption Scheme |a la Alekhnovich-Regev
* Authors: Thomas Debris-Alazard, Philippe Gaborit, Romaric Neveu, Olivier Ruatta
* [Permalink](https://eprint.iacr.org/2025/1879)
* [Download](https://eprint.iacr.org/2025/1879.pdf)
### Abstract
Introduced in 2003 and 2005, Alekhnovich and Regev' schemes were the first public-key encryptions whose security is only based on the average hardness of decoding random linear codes and LWE, without other security assumptions. Such security guarantees made them very popular, being at the origin of the now standardized HQC or Kyber.
We present an adaptation of Alekhnovich and Regev' encryption scheme whose security is only based on the hardness of a slight variation of MinRank, the so-called stationary-MinRank problem. We succeeded to reach this strong security guarantee by showing that stationary-MinRank benefits from a search-to-decision reduction. Our scheme therefore brings a partial answer to the long-standing open question of building an encryption scheme whose security relies solely on the hardness of MinRank.
Finally, we show after a thoroughly security analysis that our scheme is practical and competitive with other encryption schemes admitting such strong security guarantees. Our scheme is slightly less efficient than FrodoKEM, but much more efficient than Alekhnovich and Regev' original schemes, with possibilities of improvements by considering more structure, in the same way as HQC and Kyber.
## 2025/1880
* Title: Copy-Protection from Unclonable Puncturable Obfuscation, Revisited
* Authors: Prabhanjan Ananth, Amit Behera, Zikuan Huang, Fuyuki Kitagawa, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2025/1880)
* [Download](https://eprint.iacr.org/2025/1880.pdf)
### Abstract
Quantum copy-protection is a functionality-preserving compiler that transforms a classical program into an unclonable quantum program. This primitive has emerged as a foundational topic in quantum cryptography, with significant recent developments. However, characterizing the functionalities that can be copy-protected is still an active and ongoing research direction.
Assuming the existence of indistinguishability obfuscation and learning with errors, we show the existence of copy-protection for a variety of classes of functionalities, including puncturable cryptographic functionalities and subclasses of evasive functionalities. This strictly improves upon prior works, which were either based on the existence of heuristic assumptions [Ananth and Behera CRYPTO'24] or were based on the classical oracle model [Coladangelo and Gunn STOC'24]. Moreover, our constructions satisfy a new and much stronger security definition compared to the ones studied in the prior works. To design copy-protection, we follow the blueprint of constructing copy-protection from unclonable puncturable obfuscation (UPO) [Ananth and Behera CRYPTO'24] and present a new construction of UPO by leveraging the recently introduced techniques from [Kitagawa and Yamakawa TCC'25].
## 2025/1881
* Title: Making Post Quantum Key Exchange Efficient: An Implementation with the MLS Protocol
* Authors: Noah Greene, Britta Hale
* [Permalink](https://eprint.iacr.org/2025/1881)
* [Download](https://eprint.iacr.org/2025/1881.pdf)
### Abstract
The development of quantum computing technology poses a serious and credible threat to modern public-key cryptography, which is a pillar of secure communications. Post quantum cryptographic (PQC) algorithms can protect against this threat, but key establishment protocols supporting PQC algorithms pose non-trivial overhead costs. Prior proposals have pointed to the use of strategic traditional/PQC protocol combinations as a means of balancing performance and security, namely as an amortization of PQC overhead. This work provides the first benchmarking of this method within the context of the Messaging Layer Security (MLS) protocol. Comparative metrics include group size, CPU cycles, bytes, and runtime. The results show substantial overhead savings across the board when compared to a simple post-quantum cipher suite use, and marginal increase over traditional cipher suite performance when amortized. At small group sizes such as 1-to-1 channels, the method performs comparably to MLS using a traditional cipher suite. This work shows viability of deploying PQC solutions for constrained settings and and achieving PQC security with efficiency.
## 2025/1882
* Title: MATCHI: formal verification of hardware private circuits
* Authors: Ga|2tan Cassiers
* [Permalink](https://eprint.iacr.org/2025/1882)
* [Download](https://eprint.iacr.org/2025/1882.pdf)
### Abstract
Hardware Private Circuits (HPC) provide a compositional framework for designing masked hardware circuits, ensuring security against side-channel attacks in the robust probing model with glitches and transitions. There is however a gap between the simplified circuit models and real-world implementations. In particular, some parts are of real circuits are ignored in the simplified models. Further, designing implementations such that they have a simple static correspondence to the theory can be challenging (e.g., around the requirement of splitting the computation into gadgets), or even infeasible (e.g., when some hardware elements like memory are used for different purposes during the executions). In this work, we close this gap by introducing a new model for hardware circuits that include the control and randomness distribution logic. It also allows some computation on the shares to be performed outside the delimited gadgets. We introduce a new open-source compositional masking verification tool, MATCHI. Thanks to the formalization of a composition framework for the new circuit model, we prove that any circuit successfully verified by MATCHI is secure in the threshold probing model with glitches and transitions.
## 2025/1883
* Title: On the security of two blind signatures from code equivalence problems * Authors: Valerie Gilchrist, Laurane Marco, Christophe Petit, Gang Tang
* [Permalink](https://eprint.iacr.org/2025/1883)
* [Download](https://eprint.iacr.org/2025/1883.pdf)
### Abstract
The Linear Code Equivalence (LCE) problem and the Matrix Code Equivalence (MCE) problem are two examples of code-based hard problems that have gained attention as candidates for use in post-quantum cryptography.
They are straightforward to implement, can be viewed as group actions, and offer a good trade-off between compactness and performance in the realm of post-quantum group actions.

With the community gaining confidence in the security of these problems, new variants of these problems have been introduced to achieve particular functionalities in advanced protocols or efficiency improvements. A natural question is then whether the problem variants are as secure as the original ones.
In this work, we consider three problem variants of LCE or MCE.

We first consider a variant based on LCE, and reduce it to the original LCE assumption. This increases security confidence in a blind signature scheme, proposed by Duong, Khuc, Qiao, Susilo and Zhang that relied on it.

Second, we analyse an MCE variant, MIMCE, proposed in the context of another blind signature scheme, by Kutcha, Legrow and Persichetti, and show that the parameters proposed are not sufficient to reach the claimed bit security.

Finally, we consider a multi-sample version of MIMCE which we solve in polynomial time.
## 2025/1884
* Title: PERSEUS rCo Probabilistic Evaluation of Random probing SEcurity Using efficient Sampling
* Authors: Sonia Bela|>d, Ga|2tan Cassiers
* [Permalink](https://eprint.iacr.org/2025/1884)
* [Download](https://eprint.iacr.org/2025/1884.pdf)
### Abstract
Cryptographic implementations are inherently vulnerable to side-channel attacks, which exploit physical leakages such as power consumption. Masking has become the most widely adopted countermeasure to mitigate these threats, as it randomizes intermediate values and makes the leakage less exploitable. Yet, a central challenge remains: how to rigorously assess the concrete security level of masked implementations.
To tackle this issue, the random probing model has emerged as a powerful abstraction. It formalizes leakage as random probes in the circuit and, importantly, the security in the noisy leakage model, which closely reflects the behavior of real embedded devices, reduces to security in the random probing model. Hence, proving security in the random probing model provides sound guarantees of practical resistance against side-channel attacks.
Yet, the current state of the art on random probing compilers and verifiers suffers from a clear limitation: scalable approaches yield prohibitively large and inefficient circuits, while tighter methods do not scale to practical circuit sizes. In this work, we bridge this gap by introducing a new methodology that directly estimates the random probing security of large circuits through Monte Carlo sampling, combined with a pruning strategy that drastically reduces the sampling space.
We implement our approach in a new tool, PERSEUS, which supports both gate and wire leakage models. Our experiments demonstrate that PERSEUS can efficiently evaluate masked implementations of AES-128 with $n=8$ shares, achieving security levels beyond 32 bits, thereby significantly advancing the state of the art in practical verification of side-channel countermeasures.
## 2025/1885
* Title: Correction Fault Attack on CROSS under Unknown Bit Flips
* Authors: S||nke Jendral, Elena Dubrova, Qian Guo, Thomas Johansson
* [Permalink](https://eprint.iacr.org/2025/1885)
* [Download](https://eprint.iacr.org/2025/1885.pdf)
### Abstract
Recognising the need for PQC signature schemes with different size and performance trade-offs than the ML-DSA and SLH-DSA standards, in 2023 NIST launched a competition for additional signature algorithms. Among the current candidates in this competition is CROSS, a code-based scheme derived from the syndrome-decoding problem and suitable for memory-constrained devices.
This paper presents a fault attack on CROSS that recovers the secret key by flipping one or more bits in the schemerCOs public parity-check matrix. Unlike previous PQC fault attacks that typically rely on precisely controlled fault injections, which is often an unrealistic assumption, our approach exploits bit flips with unknown position and value, resembling the Rowhammer fault model. The attack builds upon the correction-based methodology introduced for Dilithium (Euro S&PrCO22; CHESrCO24) and exploits structural properties of CROSS to substantially relax attacker requirements. We demonstrate the attack on an ARM Cortex-M4 processor using voltage fault injection. We further show that prior work on partial key exposure attacks (CRYPTO'22) can be extended to CROSS under non-trivial erasure rates, reducing the attack complexity. The attack remains effective in the presence of memory-integrity protection mechanisms such as error-correcting codes. Finally, we propose countermeasures for hardening CROSS implementations against physical attacks.
## 2025/1886
* Title: Blind Signatures from Arguments of Inequality
* Authors: Michael Kloo|f, Russell W. F. Lai, Michael Reichle
* [Permalink](https://eprint.iacr.org/2025/1886)
* [Download](https://eprint.iacr.org/2025/1886.pdf)
### Abstract
Blind signatures are an important tool for privacy-preserving applications with a long history dating back to Chaum's seminal work in Crypto'82. In this work, we focus on the Fiat-Shamir paradigm, i.e., blind signatures based on $\Sigma$-protocols compiled via Fiat-Shamir, in the random oracle model. We resolve the following open problems:
- We give the first lattice-based blind signature that is concurrently-secure based on the Fiat-Shamir paradigm.
- We give the first pairing-free blind signature that is concurrently-secure under the discrete logarithm assumption (without the algebraic group model). On a technical level, our work is inspired by the recent proofs of inequality technique (Kloo|f and Reichle, Crypto'25). This technique relies on statistical puncturing of the verification key. We explore the technique in the computational regime and develop new proof and design techniques to tackle the challenges encountered along the way.
## 2025/1887
* Title: Parallel Spooky Pebbling Makes Regev Factoring More Practical
* Authors: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Katherine Van Kirk
* [Permalink](https://eprint.iacr.org/2025/1887)
* [Download](https://eprint.iacr.org/2025/1887.pdf)
### Abstract
"Pebble games," an abstraction from classical reversible computing, have found use in the design of quantum circuits for inherently sequential tasks. Gidney showed that allowing Hadamard basis measurements during pebble games can dramatically improve costs---an extension termed "spooky pebble games" because the measurements leave temporary phase errors called ghosts. In this work, we define and study parallel spooky pebble games. Previous work by Blocki, Holman, and Lee (TCC 2022) and Gidney studied the benefits offered by either parallelism or spookiness individually; here we show that these resources can yield impressive gains when used together. First, we show by construction that a line graph of length $\ell$ can be pebbled in depth $2\ell$ (which is exactly optimal) using space $\leq 2.47\log \ell$. Then, to explore pebbling schemes using even less space, we use a highly optimized $A^*$ search implemented in Julia to find the lowest-depth parallel spooky pebbling possible for a range of concrete line graph lengths $\ell$ given a constant number of pebbles $s$.
We show that these techniques can be applied to Regev's factoring algorithm (Journal of the ACM 2025) to significantly reduce the cost of its arithmetic. For example, we find that 4096-bit integers $N$ can be factored in multiplication depth 193, which outperforms the 680 required of previous variants of Regev and the 444 reported by Eker|N and G|nrtner for Shor's algorithm (IACR Communications in Cryptology 2025). While space-optimized implementations of Shor's algorithm remain likely the best candidates for first quantum factorization of large integers, our results show that Regev's algorithm may have practical importance in the future, especially given the possibility of further optimization. Finally, we believe our pebbling techniques will find applications in quantum cryptanalysis beyond integer factorization.
## 2025/1888
* Title: HCTR2-FP and HCTR3-FP: Format-Preserving Encryption from Wide-Block Ciphers
* Authors: Frank Denis
* [Permalink](https://eprint.iacr.org/2025/1888)
* [Download](https://eprint.iacr.org/2025/1888.pdf)
### Abstract
Format-preserving encryption (FPE) enables encryption while maintaining syntactic properties such as character sets. The current NIST standard FF1 uses multi-round Feistel networks that sacrifice performance for flexibility, while FF3-1 was withdrawn in 2025 following successful cryptanalytic attacks. FAST, proposed as a faster alternative, has not been widely implemented due to its complexity, leaving limited practical alternatives.
We present HCTR2-FP and HCTR3-FP, format-preserving adaptations of the HCTR2 and HCTR3 wide-block tweakable ciphers.
These variants preserve the single-pass Hash-Encrypt-Hash structure while operating on arbitrary radix domains through base-radix encoding and modular arithmetic. The constructions are simple to implement and analyze, and benchmarks demonstrate significant speedup over FF1.
## 2025/1889
* Title: Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
* Authors: Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin
* [Permalink](https://eprint.iacr.org/2025/1889)
* [Download](https://eprint.iacr.org/2025/1889.pdf)
### Abstract
Gluing theorem for random unitaries [Schuster, Haferkamp, Huang, QIP 2025] have found numerous applications, including designing low depth random unitaries [Schuster, Haferkamp, Huang, QIP 2025], random unitaries in $\mathsf{QAC0}$ [Foxman, Parham, Vasconcelos, Yuen'25] and generically shortening the key length of pseudorandom unitaries [Ananth, Bostanci, Gulati, Lin EUROCRYPT'25]. We present an alternate method of combining Haar random unitaries from the gluing lemma from [Schuster, Haferkamp, Huang, QIP 2025] that is secure against adversaries with inverse query access to the joined unitary. As a consequence, we show for the first time that strong pseudorandom unitaries can generically have their length extended, and can be constructed using only $O(n^{1/c})$ bits of randomness, for any constant $c$, if any family of strong pseudorandom unitaries exists.
## 2025/1890
* Title: Cryptanalysis on Lightweight Verifiable Homomorphic Encryption
* Authors: Jung Hee Cheon, Daehyun Jang
* [Permalink](https://eprint.iacr.org/2025/1890)
* [Download](https://eprint.iacr.org/2025/1890.pdf)
### Abstract
Verifiable Homomorphic Encryption (VHE) is a cryptographic technique that integrates Homomorphic Encryption (HE) with Verifiable Computation (VC). It serves as a crucial technology for ensuring both privacy and integrity in outsourced computation, where a client sends input ciphertexts $\mathsf{ct}$ and a function $f$ to a server and verifies the correctness of the evaluation upon receiving the evaluation result $f(\mathsf{ct})$ from the server.

Chatel et al. (CCS'24) introduced two VHE schemes: Replication Encoding (REP) and Polynomial Encoding (PE). A similar approach to REP was used by Albrecht et al. (EUROCRYPT'24) to develop a Verifiable Oblivious PRF scheme (vADDG).
A key approach in these schemes is to embed specific secret information within ciphertexts and use them to verify homomorphic evaluations.

This paper presents efficient forgery attacks against the verifiability guarantees of these VHE schemes. We introduce two attack strategies. The first targets REP and vADDG, extracting secret information in encrypted form from input ciphertexts and leveraging it to forge output ciphertexts without being detected by the verification algorithm. The second targets PE, exploiting its secret embedding structure to forge output ciphertexts that remain valid on input values for verification, yet violate the verifiability property.

Our forgery attack on vADDG demonstrates that the proposed 80-bit security parameters provide at most 10 bits of concrete security. Our attack on REP and \PE achieves a probability 1 attack with linear time complexity when using fully homomorphic encryption.
## 2025/1891
* Title: Fraud Mitigation in Privacy-Preserving Attribution
* Authors: Rutchathon Chairattana-Apirom, Stefano Tessaro, Nirvan Tyagi
* [Permalink](https://eprint.iacr.org/2025/1891)
* [Download](https://eprint.iacr.org/2025/1891.pdf)
### Abstract
Privacy-preserving advertisement attribution allows websites selling goods to learn statistics on which advertisement campaigns can be attributed to converting sales. Existing proposals rely on users to locally store advertisement history on their browser and report attribution measurements to an aggregation service (instantiated with multiparty computation over non-colluding servers). The service computes and reveals the aggregate statistic. The service hides individual user contributions, but it does not guarantee integrity against misbehaving users that may submit fraudulent measurements.
Our work proposes a new cryptographic primitive, "secret share attestation", in which secret shares input into a multiparty computation protocol are accompanied by an attestation of integrity by a third party: advertisers include signature attestations when serving ads that are later included in contributed measurements. We propose two constructions based on the standards-track BBS signatures and efficient signatures over equivalence classes, respectively. We implement and evaluate our protocols in the context of the advertising application to demonstrate their practicality.
## 2025/1892
* Title: Optimizing FHEW-Like Homomorphic Encryption Schemes with Smooth Performance-Failure Trade-Offs
* Authors: Deokhwa Hong, Yongwoo Lee
* [Permalink](https://eprint.iacr.org/2025/1892)
* [Download](https://eprint.iacr.org/2025/1892.pdf)
### Abstract
FHEW-like homomorphic encryption (HE) schemes, introduced by Ducas and Micciancio (Eurocrypt 2015), represent the most efficient family of HE schemes in terms of both latency and key size.
However, their bootstrapping noise is highly sensitive to parameter selection, leaving only a sparse set of feasible parameters.
Because bootstrapping noise directly affects security and performance, existing approaches tend to choose parameters that drive noise excessively lowrCoresulting in large key sizes and high latency.
In this paper, we propose a new bootstrapping modification that permits an almost continuous spectrum of parameter choices.
In our best knowledge, this is the first practical HE scheme for which the evaluation failure probability is precisely determined without requiring any information about the message distribution.
We further show that, under our method, the parameterrCEoptimization task reduces to a generalized knapsack problem solvable in polynomial time.
As a result, the traditionally cumbersome process of selecting parameters for FHEWrCElike schemes becomes tractable.
Experimental results show that our method improves bootstrapping runtime by approximately 17% and reduces key size by about 45%.
## 2025/1893
* Title: Poseidon2b: A Binary Field Version of Poseidon2
* Authors: Lorenzo Grassi, Dmitry Khovratovic, Katharina Koschatko, Christian Rechberger, Markus Schofnegger, Verena Schr||ppel
* [Permalink](https://eprint.iacr.org/2025/1893)
* [Download](https://eprint.iacr.org/2025/1893.pdf)
### Abstract
We present Poseidon2b, a version of Poseidon2 defined over binary extension fields. It is specifically designed to inherit many of the circuit-friendly properties of its prime field version, and to be used together with binary extension field proving systems such as Binius. Benchmarking demonstrates the merits around proof size, proving time, and especially verification time.
We also revisit recent attacks on Poseidon and Poseidon2 and discuss their applicability in the binary field extension setting, in addition to analyzing attack vectors that were not applicable in the prime field setting. In particular, we lay special focus on algebraic cryptanalysis and subspace trails, techniques which resulted in attacks on initial versions of Poseidon defined over binary extension fields.
## 2025/1894
* Title: Bounded-Equivocable Pseudorandom Functions
* Authors: Paul Gerhart, Davide Li Calsi, Luigi Russo, Dominique Schr||der
* [Permalink](https://eprint.iacr.org/2025/1894)
* [Download](https://eprint.iacr.org/2025/1894.pdf)
### Abstract
We introduce Bounded-Equivocable PRFs, a new variant of pseudorandom functions. They combine standard pseudorandomness with a bounded form of programmability. In our model, an adversary may issue an arbitrary number of queries that remain indistinguishable from random. Bounded equivocability ensures that responses can be programmed consistently with a later-revealed key, up to a fixed bound q. This relaxation avoids known impossibility results, which preclude polynomial unbounded equivocability in the standard model, while preserving the programmability required for applications.
We present standard-model constructions of bounded-equivocable PRFs under the DDH and LWE assumptions, and we show how to make these constructions verifiable. Prior SIM-AC style primitives could not achieve verifiability since their programmability relied on embedding the secret key into the random oracle. We demonstrate applications to (i) adaptively secure private-key encryption, (ii) two-round threshold Schnorr signatures secure against adaptive corruptions, and (iii) leader election in Proof of Stake blockchains. Together, these results establish bounded-equivocable PRFs as a practical primitive that achieves programmability with verifiability in the standard model, and enables applications previously out of reach.
## 2025/1895
* Title: Differential Fault Attacks on MQOM, Breaking the Heart of Multivariate Evaluation
* Authors: Vladimir Sarde, Nicolas Debande
* [Permalink](https://eprint.iacr.org/2025/1895)
* [Download](https://eprint.iacr.org/2025/1895.pdf)
### Abstract
MQOM is one of the fourteen remaining candidates in the
second round of the NIST post-quantum signature standardization process. Introduced in 2023, MQOM instantiates the Multi-Party Computation
in the Head (MPCitH) paradigm over the well-established hard
problem of solving Multivariate Quadratic (MQ) equations. In this paper,
we present the first fault attacks on MQOM targeting the MQ evaluation
phase, which is a central component of the algorithm. We introduce
four differential fault attacks and demonstrate their effectiveness against both unprotected and masked implementations. The first two target the
secret key using a random fault model, making them particularly realistic
and practical. With as little as one or two injected faults, depending
on the variant, the entire secret key can be recovered through linear algebra. The other two attacks exploit faults on the coefficients of the MQ
system directly. Our results highlight that the MQ evaluation, despite
not being identified as a sensitive component until now, can be exploited
using just a few fault injections.
## 2025/1896
* Title: An Approach to Computable Contracts with Verifiable Computation Outsourcing and Blockchain Transactions
* Authors: Carlo Brunetta, Amit Chaudhary, Stefano Galatolo, Massimiliano Sala * [Permalink](https://eprint.iacr.org/2025/1896)
* [Download](https://eprint.iacr.org/2025/1896.pdf)
### Abstract
In this short paper we present an approach to computable contracts, where all roles in a computation may be outsourced, from the servers performing computations, to those providing input, to those performing verifications (on input and on output), including all related communications. Varying levels of confidentiality can be chosen, both on data and calculations.
While the largest part of the computational and communication effort is performed off-chain, our contracts require a specialized underlying blockchain, where they are encoded as transactions, to achieve their decentralized handling and thus enforcing their correct execution via a combination of cryptographic techniques and economic security.
Our delegation architecture allows for the execution of very complex collaborative tasks, such as the deployment of an AI marketplace.
## 2025/1897
* Title: Dynark: Making Groth16 Dynamic
* Authors: Tianyu Zhang, Yupeng Ouyang, Yupeng Zhang
* [Permalink](https://eprint.iacr.org/2025/1897)
* [Download](https://eprint.iacr.org/2025/1897.pdf)
### Abstract
In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes.
In this paper, we introduce DYNARK, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. DYNARK is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting, for an R1CS of size $n$, after a preprocessing of $O(n\log n)$ group operations on the original witness, it only takes $O(d)$ group operations and $O(d\log^2 d)$ field operations to update the proof for a new witness with distance $d$ from the original witness, which is nearly optimal. In the fully-dynamic setting, the update time of DYNARK is $O(d\sqrt{n\log n})$ group operations and $O(d\log^2 d)$ field operations. Both the proof size and the verifier time are $O(1)$, which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from $O(\sqrt{n})$ to $O(1)$ without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of DYNARK are faster in practice.
Experimental results show that for $n=2^{20}$, after a one-time preprocessing of 74.3 seconds, it merely takes 3 milliseconds to update the proof in our semi-dynamic zkSNARK for $d=1$, and 60 milliseconds to update the proof in our fully-dynamic zkSNARK. These are 1433$\times$ and 73$\times$ faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 milliseconds. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.
## 2025/1898
* Title: Unique NIZKs and Steganography Detection
* Authors: Willy Quach, LaKyah Tyner, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2025/1898)
* [Download](https://eprint.iacr.org/2025/1898.pdf)
### Abstract
Non-interactive zero-knowledge (NIZK) proofs tend to be randomized and there are many possible proofs for any fixed NP statement. Can we have NIZKs with only a single unique valid proof per statement? Such NIZKs are known under strong cryptographic assumptions (indistinguishability obfuscation), and are conversely known to require strong cryptographic assumptions (witness encryption). In this work, following Lepinski, Micali, and shelat (TCC '05), we consider the following relaxed notion of unique NIZKs (UNIZKs):
- We only require (computationally) unique proofs for NP statements with a (computationally) unique witness; an adversary that can produce two distinct proofs must also know two distinct witnesses.
- We consider NIZKs with prover setup, where a potentially malicious prover initially publishes a public key $\mathsf{pk}$ and keeps a corresponding secret key $\mathsf{sk}$, which it uses to produce arbitrarily many NIZK proofs $\pi$ in the future. While the public key $\mathsf{pk}$ is not required to be unique, once it is fixed, all the subsequent proofs $\pi$ that the prover can produce should be unique.
We show that both of these relaxations are needed to avoid witness encryption. Prior work constructed such UNIZKs under the quadratic residuosity assumption, and it remained an open problem to do so under any other assumptions. Here, we give a new construction of UNIZKs under the learning with errors (LWE) assumption. We also identify and fix a subtle circularity issue in the prior work.
UNIZKs are a non-interactive version of steganography-free zero-knowledge of Abdolmaleki et al. (TCC '22). As an application of UNIZKs, we get a general steganography detection mechanism that can passively monitor arbitrary functionalities to detect steganographic leakage.
--- Synchronet 3.21a-Linux NewsLink 1.2