From Newsgroup: sci.crypt

## In this issue
1. [2023/1409] Solving the Hidden Number Problem for CSIDH and ...
2. [2024/861] A new multivariate primitive from CCZ equivalence
3. [2025/993] Fully-Homomorphic Encryption from Lattice Isomorphism
4. [2025/1064] From Signature-Based Witness Encryption to RAM ...
5. [2025/1228] Quantum-Safe Hybrid Key Exchanges with KEM-Based ...
6. [2025/1283] Fast AVX-512 Implementation of the Optimal Ate ...
7. [2025/1287] Fault Injection Evaluation with Statistical ...
8. [2025/1314] THF: Designing Low-Latency Tweakable Block Ciphers
9. [2025/1321] Threshold Receipt-Free Voting with Server-Side Vote ...
10. [2025/1322] Generation of Fast Finite Field Arithmetic for ...
11. [2025/1323] Pairing-Based Batch Arguments for NP with a Linear- ...
12. [2025/1324] FPGA-Friendly Compact and Efficient AES-like 8x8 S-Box
13. [2025/1325] Revisiting the IPA-sumcheck connection
14. [2025/1326] New Techniques for Analyzing Differentials with ...
15. [2025/1327] Randomized Agreement, Verifiable Secret Sharing and ...
16. [2025/1328] Private Set Intersection and other Set Operations ...
17. [2025/1329] Cryptanalysis of a multivariate CCZ scheme
18. [2025/1330] Exploring Core Monomial Prediction Further: Weak- ...
19. [2025/1331] Constant-Cycle Hardware Private Circuits
20. [2025/1332] Technical Note: LeanSig for Post-Quantum Ethereum
21. [2025/1333] Policy-Based Redactable Set Signatures
22. [2025/1334] On the use of ECDSA with hierarchical public key ...
23. [2025/1335] A Compact Post-quantum Strong Designated Verifier ...
24. [2025/1336] Representations of Elementary Vectors in VOLE-in- ...
25. [2025/1337] $\textsf{Electrum}$: UC Fail-Stop Server-Supported ...
26. [2025/1338] Limits on the Power of Constrained PRFs and ...
27. [2025/1339] Breaking the Twinkle Authenticated Encryption ...
28. [2025/1340] Zelda: Efficient Multi-server Preprocessing PIR ...
29. [2025/1341] Practical Attack on All Parameters of the HPPC ...
30. [2025/1342] Simultaneous Diophantine Approximation for Compact ...
31. [2025/1343] A Hybrid Asymmetric Password-Authenticated Key ...
32. [2025/1344] Side-Channel Sensitivity Analysis on HQC: Towards a ...
33. [2025/1345] SLVer Bullet: Straight-Line Verification for ...
34. [2025/1346] Cryptanalysis of TFHE-friendly Cipher FRAST
35. [2025/1347] Public Traceability in Threshold Decryption
36. [2025/1348] The CRO Trilemma : a formal incompatibility between ...
37. [2025/1349] $\mathsf{HyperFond}$: A Transparent and Post- ...
38. [2025/1350] Rhyme: A Fiat-Shamir Lattice-based Signature with ...
39. [2025/1351] Revisiting the Generalized Birthday Problem and ...
40. [2025/1352] InsPIRe: Communication-Efficient PIR with Silent ...
41. [2025/1353] Introducing two ROS attack variants: breaking one- ...
42. [2025/1354] Shred-to-Shine Metamorphosis in Polynomial ...
43. [2025/1355] Unconditional Pseudorandomness against Shallow ...
44. [2025/1356] Group Signatures with Message-Dependent Opening ...
45. [2025/1357] How to Copy-Protect Malleable-Puncturable ...
46. [2025/1358] Domain-Oriented Masking Revisited: More Efficient ...
47. [2025/1359] Runtime Code Generation for Constant-Time Secret- ...
48. [2025/1360] Towards more secure constructions of private set ...
49. [2025/1361] Exploring KanekorCOs bound: On multi-edges, loops and ...
50. [2025/1362] Cryptanalysis of the best HFE-LL' Constructions
51. [2025/1363] Universally Composable Adaptor Signatures
52. [2025/1364] A Framework for Witness Encryption from Linearly ...
## 2023/1409
* Title: Solving the Hidden Number Problem for CSIDH and CSURF via Automated Coppersmith
* Authors: Jonas Meers, Julian Nowakowski
* [Permalink](https://eprint.iacr.org/2023/1409)
* [Download](https://eprint.iacr.org/2023/1409.pdf)
### Abstract
We define and analyze the Commutative Isogeny Hidden
Number Problem which is the natural analogue of the Hidden Number Problem in the CSIDH and CSURF setting. In short, the task is as follows: Given two supersingular elliptic curves \(E_A\), \(E_B\) and access to an oracle that outputs some of the most significant bits of the \({\mathsf{CDH}}\) of two curves, an adversary must compute the shared curve \(E_{AB}={\mathsf{CDH}}(E_A,E_B)\).

We show that we can recover \(E_{AB}\) in polynomial time by using Coppersmith's method as long as the oracle outputs \({\frac{13}{24}} + \varepsilon \approx 54\%\) (CSIDH) and \({\frac{31}{41}} + \varepsilon \approx 76\%\) (CSURF) of the most significant bits of the \({\mathsf{CDH}}\), where $\varepsilon > 0$ is an arbitrarily small constant. To this end, we give a purely combinatorial restatement of Coppersmith's method, effectively concealing the intricate aspects of lattice theory and allowing for near-complete automation. By leveraging this approach, we attain recovery attacks with $\varepsilon$ close to zero within a few minutes of computation.
## 2024/861
* Title: A new multivariate primitive from CCZ equivalence
* Authors: Marco Calderini, Alessio Caminata, Irene Villa
* [Permalink](https://eprint.iacr.org/2024/861)
* [Download](https://eprint.iacr.org/2024/861.pdf)
### Abstract
Multivariate Cryptography is one of the candidates for Post-quantum Cryptography. Multivariate schemes are usually constructed by applying two secret affine invertible transformations $\mathcal S,\mathcal T$ to a set of multivariate polynomials $\mathcal{F}$ (often quadratic). The polynomials $\mathcal{F}$ possess a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials $\mathcal G=\mathcal S\circ\mathcal F\circ\mathcal T$ look like random polynomials. The polynomials $\mathcal G$ and $\mathcal F$ are said to be affine equivalent. In this article, we present a more general way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions.
## 2025/993
* Title: Fully-Homomorphic Encryption from Lattice Isomorphism
* Authors: Pedro Branco, Giulio Malavolta, Zayd Maradni
* [Permalink](https://eprint.iacr.org/2025/993)
* [Download](https://eprint.iacr.org/2025/993.pdf)
### Abstract
The lattice isomorphism problem (LIP) asks, given two lattices $\Lambda_0$ and $\Lambda_1$, to decide whether there exists an orthogonal linear map from $\Lambda_0$ to $\Lambda_1$. In this work, we show that the hardness of (a circular variant of) LIP implies the existence of a fully-homomorphic encryption scheme for all classical and quantum circuits. Prior to our work, LIP was only known to imply the existence of basic cryptographic primitives, such as public-key encryption or digital signatures.
## 2025/1064
* Title: From Signature-Based Witness Encryption to RAM Obfuscation: Achieving Blockchain-Secured Cryptographic Primitives
* Authors: Lev Stambler
* [Permalink](https://eprint.iacr.org/2025/1064)
* [Download](https://eprint.iacr.org/2025/1064.pdf)
### Abstract
Goyal and Goyal demonstrated that extractable witness encryption, when combined with smart-contract equipped proof-of-stake blockchains, can yield powerful cryptographic primitives such as one-time programs and pay-to-use programs. However, no standard model construction for extractable witness encryption is known, and instantiations from alternatives like indistinguishability obfuscation are highly inefficient.
This paper circumvents the need for extractable witness encryption by combining signature-based witness encryption (D||ttling et al.) with witness encryption for KZG commitments (Fleischhacker et al.). Inspired by Goyal et al., we introduce $T+1$-Extractable Witness Encryption for Blockchains ($T+1$-eWEB), a novel primitive that encrypts a secret, making its decryption contingent upon the subsequent block's state. Leveraging $T+1$-eWEBs, we then build a conditional one-time memory, leading to a $T+1$ one-time program ($T+1$-OTP) also conditional on the next block state. Finally, using our $T+1$-OTP, we develop a conditional RAM obfuscation scheme where program execution can be contingent on the blockchain state, thereby enabling applications like pay-to-use programs.
Despite its theoretical value, our construction is impractical due to a "bit-by-bit" signing requirement for the state root and an inefficient method for storing validator keys. We thus posit the construction of a practical $T+1$-OTP as a significant open problem. This work provides the first theoretical pathway for building such primitives without extractable witness encryption, representing a novel step for blockchain-secured cryptography.
## 2025/1228
* Title: Quantum-Safe Hybrid Key Exchanges with KEM-Based Authentication
* Authors: Christopher Battarbee, Christoph Striecks, Ludovic Perret, Sebastian Ramacher, Kevin Verhaeghe
* [Permalink](https://eprint.iacr.org/2025/1228)
* [Download](https://eprint.iacr.org/2025/1228.pdf)
### Abstract
Authenticated Key Exchange (AKE) between any two entities is one of the most important security protocols available for securing our digital networks and infrastructures. In PQCrypto 2023, Bruckner, Ramacher and Striecks proposed a novel hybrid AKE (HAKE) protocol dubbed Muckle+ that is particularly useful in large quantum-safe networks consisting of a large number of nodes. Their protocol is hybrid in the sense that it allows key material from conventional, post-quantum, and quantum cryptography primitives to be incorporated into a single end-to-end authenticated shared key.
To achieve the desired authentication properties, Muckle+ utilizes post-quantum digital signatures. However, available instantiations of such signatures schemes are not yet efficient enough compared to their post-quantum key-encapsulation mechanism (KEM) counterparts, particularly in large networks with potentially several connections in a short period of time.
To mitigate this gap, we propose Muckle# that pushes the efficiency boundaries of currently known HAKE constructions. Muckle# uses post-quantum key-encapsulating mechanisms for implicit authentication inspired by recent works done in the area of Transport Layer Security (TLS) protocols, particularly, in KEMTLS (CCS'20).
We port those ideas to the HAKE framework and develop novel proof techniques on the way. Due to our KEM-based approach, the resulting protocol has a slightly different message flow compared to prior work that we carefully align with the HAKE framework and which makes our changes to Muckle+ non-trivial. Lastly, we evaluate the approach by a prototypical implementation and a direct comparison with Muckle+ to highlight the efficiency gains.
## 2025/1283
* Title: Fast AVX-512 Implementation of the Optimal Ate Pairing on BLS12-381
* Authors: Hao Cheng, Georgios Fotiadis, Johann Gro|fsch|ndl, Daniel Page
* [Permalink](https://eprint.iacr.org/2025/1283)
* [Download](https://eprint.iacr.org/2025/1283.pdf)
### Abstract
Non-degenerate bilinear maps on elliptic curves, commonly referred to as pairings, have many applications including short signature schemes, zero-knowledge proofs and remote attestation protocols. Computing a state-of-the-art pairing at the $128$-bit security level, such as the optimal ate pairing over the curve BLS12-381, is very costly due to the high complexity of some of its sub-operations: most notable are the Miller loop and final exponentiation. In the past ten years, a few optimized pairing implementations have been introduced in the literature, but none of those took advantage of the vector (SIMD) extensions of state-of-the-art Intel and AMD CPUs, especially AVX-512; this is surprising, because doing so offers the potential to reach significant speed-ups. Consequently, the questions of 1) how computation of the optimal ate pairing can be effectively vectorized, and 2) what execution time such a vectorized implementation can achieve are still open. This paper addresses said questions by introducing a carefully-optimized AVX-512 implementation of the optimal ate pairing on BLS12-381. A central feature of the implementation is the use of $8$-way Integer Fused Multiply-Add (IFMA) instructions, which are capable to execute eight $52 \times 52$-bit multiplications in a SIMD-parallel fashion. We introduce new vectorization strategies and describe optimizations of existing ones to speed up arithmetic operations in the extension fields $\mathbb{F}_{p^4}$, $\mathbb{F}_{p^6}$, and $\mathbb{F}_{p^{12}}$ as well as certain higher-level functions. Furthermore, we discuss some parallelization bottlenecks and how they impact execution time. We benchmarked our pairing software, which we call avxbls, on an Intel Core i3-1005G1 ("Ice Lake") CPU and found that it needs $1,265,314$ clock cycles (resp. $1,195,236$ clock cycles) for the full pairing, with the Granger-Scott cyclotomic squaring (resp. compressed cyclotomic squaring) being used in the final exponentiation. For comparison, the non-vectorized (i.e., scalar) x64 assembly implementation from the widely-used blst library has an execution time of $2,351,615$ cycles, which is $1.86$ times (resp. $1.97$ times) slower. avxbls also outperforms Longa's implementation (CHES 2023) by almost the same factor. The practical importance of these results is amplified by Intel's recent announcement to support AVX10, which includes IFMA instructions, in all future CPUs.
## 2025/1287
* Title: Fault Injection Evaluation with Statistical Analysis - How to Deal with Nearly Fabricated Large Circuits
* Authors: Felix Uhle, Nicolai M|+ller, Amir Moradi
* [Permalink](https://eprint.iacr.org/2025/1287)
* [Download](https://eprint.iacr.org/2025/1287.pdf)
### Abstract
A critical aspect of securing cryptographic hardware is their resistance to FI attacks, which involve the successful injection of faults into the system in operation. Specifically, a hardware design must be resilient to well-established fault injection techniques, including voltage or clock glitching, laser fault injections, and the more recently introduced EMFI. Ideally, the protection level must be verified before the chip is fabricated.
Although initial efforts to verify the resistance of hardware designs against fault injection have been made, analyzing the security of practical designs with realistic gate counts under fault injections that affect multiple gates or the entire circuit state remains a significant challenge. This scenario, however, is considered more realistic than assessing resistance to a fixed, relatively small number of faults.
In this work, we introduce FIESTA, a versatile automated framework for analyzing the resistance of hardware circuits under the general random fault model. By leveraging a non-exhaustive approach, FIESTA is capable of evaluating larger designs compared to state-of-the-art tools, while maintaining a reasonable level of confidence. FIESTA supports various adversary models, allowing customized resistance analysis against specific adversaries. In particular, we present a concrete procedure for evaluating more realistic precise adversaries, based on practical observations. Using FIESTA, we assessed the resistance of several (protected) AES cores.
## 2025/1314
* Title: THF: Designing Low-Latency Tweakable Block Ciphers
* Authors: Jianhua Wang, Tao Huang, Guang Zeng, Tianyou Ding, Shuang Wu, Siwei Sun
* [Permalink](https://eprint.iacr.org/2025/1314)
* [Download](https://eprint.iacr.org/2025/1314.pdf)
### Abstract
We introduce a concrete instance of the LRW+ paradigm: the Three-Hash Framework (THF), a mode for constructing tweakable block ciphers that employs three hash functions to process tweak inputs. Through a general practical cryptanalysis of THF in both single-tweak and multiple-tweak settings, and by comparing it with two representative modes, 4-LRW1 and 2-LRW2, we demonstrate that THF has the potential to achieve lower latency due to its more balanced resistance to both single- and multiple-tweak attacks.
Based on this framework, we design Blink, a family of tweakable block ciphers specifically optimized for minimal latency. The hash functions in Blink were carefully chosen to align with the low-latency requirements, ensuring both efficiency and strong security. A thorough cryptanalysis of Blink is provided, with an emphasis on its resistance to multiple-tweak attacks.
Finally, hardware evaluations highlight the exceptional low-latency performance of Blink, distinguishing it as one of the most efficient tweakable block ciphers.
## 2025/1321
* Title: Threshold Receipt-Free Voting with Server-Side Vote Validation
* Authors: Thi Van Thao Doan, Olivier Pereira, Thomas Peters
* [Permalink](https://eprint.iacr.org/2025/1321)
* [Download](https://eprint.iacr.org/2025/1321.pdf)
### Abstract
Proving the validity of ballots is a central element of verifiable elections. Such proofs can however create challenges when one desires to make a protocol receipt-free.
We explore the challenges raised by validity proofs in the context of protocols where threshold receipt-freeness is obtained by secret sharing an encryption of a vote between multiple authorities.
In such contexts, previous solutions verified the validity of votes by decrypting them after passing them through a mix-net. This approach however creates subtle privacy risks, especially when invalid votes leak structural patterns that threaten receipt-freeness.
We propose a different approach of threshold receipt-free voting in which authorities re-randomize ballot shares then jointly compute a ZK proof of ballot validity before letting the ballots enter a (possibly homomorphic) tallying phase. Our approach keeps the voter computational costs limited while offering verifiability and improving the ballot privacy of previous solutions.
We present two protocols that enable a group of servers to verify and publicly prove that encrypted votes satisfy some validity properties: Minimix, which preserves prior voter-side behavior with minimal overhead, and Homorand, which requires voters to submit auxiliary data to facilitate validation over large vote domains. We show how to use our two protocols within a threshold receipt-free voting framework. We provide formal security proofs and efficiency analyses to illustrate trade-offs in our designs.
## 2025/1322
* Title: Generation of Fast Finite Field Arithmetic for Cortex-M4 with ECDH and SQIsign Applications
* Authors: Felix Carvalho Rodrigues, D|-cio Gazzoni Filho, Gora Adj, Isaac A. Canales-Mart|!nez, Jorge Ch|ivez-Saab, Julio L||pez, Michael Scott, Francisco Rodr|!guez-Henr|!quez
* [Permalink](https://eprint.iacr.org/2025/1322)
* [Download](https://eprint.iacr.org/2025/1322.pdf)
### Abstract
Finite field arithmetic is central to several cryptographic algorithms on embedded devices like the ARM Cortex-M4, particularly for elliptic curve and isogeny-based cryptography. However, rapid algorithm evolution, driven by initiatives such as NISTrCOs post-quantum standardization, might frequently render hand-optimized implementations obsolete.
We address this challenge with m4-modarith, a library generating C code with inline assembly for the Cortex-M4 that rivals custom-tuned assembly,
enabling agile development in this ever-changing landscape.
Our generated modular multiplications obtains fast performances, competitive with hand-optimized assembly implementations published in the literature, even outperforming some of them for Curve25519.
Two contributions are pivotal to this success.
First, we introduce a novel multiplication strategy that matches the memory access complexity of the operand caching method while being applicable to a larger cache size for Cortex-M4 implementations. Second, we generalize an efficient pseudo-Mersenne reduction strategy, and formally prove its correctness and applicability for most primes of cryptographic interest.
Our generator allowed agile optimization of SQIsignrCOs NIST PQC Round 2 submission, improving level 1 verification from 123 Mcycles to only 54 Mcycles, a $2.3\times$ speedup.
As an additional case study, we use our generator to improve performance of portable implementations of RFC~7748 by up to $2.2\times$.
## 2025/1323
* Title: Pairing-Based Batch Arguments for NP with a Linear-Size CRS
* Authors: Binyi Chen, Noel Elias, David J. Wu
* [Permalink](https://eprint.iacr.org/2025/1323)
* [Download](https://eprint.iacr.org/2025/1323.pdf)
### Abstract
Non-interactive batch arguments (BARGs) for NP allow a prover to prove $\ell$ NP statements with a proof whose size scales sublinearly with $\ell$. In this work, we construct a pairing-based BARG where the size of the common reference string (CRS) scales linearly with the number of instances and the prover's computational overhead is quasi-linear in the number of instances. Our construction is fully black box in the use of the group. Security relies on a $q$-type assumption in composite-order pairing groups.
The best black-box pairing-based BARG prior to this work has a nearly-linear size CRS (i.e., a CRS of size $\ell^{1 + o(1)}$) and the prover overhead is quadratic in the number of instances. All previous pairing-based BARGs with a sublinear-size CRS relied on some type of recursive composition and correspondingly, non-black-box use of the group. The main technical insight underlying our construction is to substitute the vector commitment in previous pairing-based BARGs with a polynomial commitment. This yields a scheme that does not rely on cross terms in the common reference string. In previous black-box pairing-based schemes, the super-linear-size CRS and quadratic prover complexity was due to the need for cross terms.
## 2025/1324
* Title: FPGA-Friendly Compact and Efficient AES-like 8x8 S-Box
* Authors: Ahmet Malal, Cihangir Tezcan
* [Permalink](https://eprint.iacr.org/2025/1324)
* [Download](https://eprint.iacr.org/2025/1324.pdf)
### Abstract
One of the main layers in the Advanced Encryption Standard (AES) is the substitution layer, where an $8 \times 8$ S-Box is used $16$ times. The substitution layer provides confusion and makes the algorithm resistant to cryptanalysis techniques. Therefore, the security of the algorithm is also highly dependent on this layer. However, the cost of implementing $8 \times 8$ S-Box on FPGA platforms is considerably higher than other layers of the algorithm. Since S-Boxes are repeatedly used in the algorithm, the cost of the algorithm highly comes from the substitution layer. In 2005, Canright used different extension fields to represent AES S-Box to get FPGA-friendly compact designs. The best optimization proposed by Canright reduced the gate-area of the AES S-Box implementation by $20\%$.
In this study, we use the same optimization methods that Canright used to optimize AES S-Box on hardware platforms. Our purpose is not to optimize AES S-Box; we aim to create another $8 \times 8$ S-Box which is strong and compact enough for FPGA platforms. We create an $8 \times 8$ S-Box using the inverse field operation as in the case of AES S-Box. We use another irreducible polynomial to represent the finite field and get an FPGA-friendly compact and efficient $8 \times 8$ S-Box. The finite field we propose provides the same level of security against cryptanalysis techniques with a $3.125\%$ less gate-area on Virtex-7 and Artix-7 FPGAs compared to CanrightrCOs results. Moreover, our proposed S-Box requires $11.76\%$ less gate on Virtex-4 FPGAs. These gate-area improvements are beneficial for resource-constraint IoT devices and allow more copies of the S-Box for algorithm parallelism. Therefore, we claim that our proposed S-Box is more compact and efficient than AES S-Box. Cryptographers who need an $8 \times 8$ S-Box can use our proposed S-Box in their designs instead of AES S-Box with the same level of security but better efficiency.
## 2025/1325
* Title: Revisiting the IPA-sumcheck connection
* Authors: Liam Eagen, Ariel Gabizon
* [Permalink](https://eprint.iacr.org/2025/1325)
* [Download](https://eprint.iacr.org/2025/1325.pdf)
### Abstract
Inner Product Arguments (IPA) [BCC+16,BBB+17] are a family of proof systems with $O(\log n)$ sized proofs, $O(n)$ time verifiers, and transparent setup.
Bootle, Chiesa and Sotiraki [BCS21] observed that an IPA can be viewed as a sumcheck protocol [LFKN92] where the summed polynomial is allowed to have coefficients in a group rather than a field. We leverage this viewpoint to improve the performance of multi-linear polynomial commitments based on IPA.
Specifically,
- We introduce a simplified variant of Halo-style accumulation that works for multilinear evaluation claims, rather than only univariate ones as in [BGH19,BCMS20].
- We show that the size $n$ MSM the IPA verifier performs can be replaced by a ``group variant'' of $\mathsf{basefold}$[ZCF23].
This reduces the verifier complexity from $O(n)$ to $O_{\lambda}(\log^2 n)$ time at the expense of an additional $4n$ scalar multiplications for the IPA prover.
## 2025/1326
* Title: New Techniques for Analyzing Differentials with Application to AES
* Authors: Itai Dinur
* [Permalink](https://eprint.iacr.org/2025/1326)
* [Download](https://eprint.iacr.org/2025/1326.pdf)
### Abstract
Differential cryptanalysis is one of the most powerful attacks on modern block ciphers. After many year of research, we have very good techniques for showing that the probability that an input difference leads to an output difference (i.e., the probability of a differential) is either significantly higher, or lower than expected, and such large deviations lead to attacks.
On the other hand, modern techniques cannot estimate with high accuracy the probability of a differential that spans many rounds of the cipher. Therefore, these techniques are sufficient to argue only limited resistance against differential cryptanalysis.
In particular, for the AES, Keliher and Sui proved in 2005 that any 4-round differential has probability at most (about) $2^{-114}$, under the assumption that the round-keys are chosen independently. This establishes limited security arguments against classical differential cryptanalysis. Stronger bounds are only known when considering thousands of AES rounds, whereas at most 14 rounds are used in practice by AES-256.
In this paper, we propose new techniques for estimating the probability of a differential under the assumption that the round-keys of the cipher are chosen independently. We apply our techniques to AES, and show that the probability of every differential in 8-round AES is within an additive factor of $2^{-128} \cdot \frac{1}{50}$ from the expected value of $\frac{1}{2^{128} - 1}$.
We further apply our techniques to prove that 8-round AES is at most $2^{-18}$-close to a pairwise independent permutation, while 40-round AES is at most $2^{-135}$-close. The latter result improves upon the work of Liu, Tessaro and Vaikuntanathan [CRYPTO 2021], who proved a similar bound for 9000-round AES.
To obtain our results, we develop and adapt a variety of techniques for analyzing differentials using functional analysis. We expect these techniques to be useful for analyzing differentials in additional block ciphers besides the AES.
## 2025/1327
* Title: Randomized Agreement, Verifiable Secret Sharing and Multi-Party Computation in Granular Synchrony
* Authors: Ananya Appan, David Heath, Ling Ren
* [Permalink](https://eprint.iacr.org/2025/1327)
* [Download](https://eprint.iacr.org/2025/1327.pdf)
### Abstract
Granular Synchrony (Giridharan et al. DISC 2024) is a new network model that unifies the classic timing models of synchrony and asynchrony.
The network is viewed as a graph consisting of a mixture of synchronous, eventually synchronous, and asynchronous communication links. It has been shown that Granular Synchrony allows deterministic Byzantine agreement protocols to achieve a corruption threshold in between complete synchrony and complete asynchrony if and only if the network graph satisfies the right condition, namely, that no two groups of honest parties of size $n-2t$ can be partitioned from each other.
In this work, we show that the same network condition is also tight for Agreement on a Common Subset (ACS), Verifiable Secret Sharing (VSS), and secure Multi-Party Computation (MPC) with guaranteed output delivery, when the corruption threshold is between one-third and one-half. Our protocols are randomized and assume that all links are either synchronous or asynchronous. %(no partially synchronous links are needed).
Our ACS protocol incurs an amortized communication cost of $O(n^3\lambda)$ bits per input, and our VSS and MPC protocols incur amortized communication costs of $O(n^3)$ and $O(n^4)$ field elements per secret and per multiplication gate, respectively. To design our protocols, we also construct protocols for Reliable Broadcast and Externally Valid Byzantine Agreement (EVBA), which are of independent interest.
## 2025/1328
* Title: Private Set Intersection and other Set Operations in the Third Party Setting
* Authors: Foo Yee Yeo, Jason H. M. Ying
* [Permalink](https://eprint.iacr.org/2025/1328)
* [Download](https://eprint.iacr.org/2025/1328.pdf)
### Abstract
We present a collection of protocols to perform privacy-preserving set operations in the third-party private set intersection (PSI) setting. This includes several protocols for multi-party third party PSI. In this model, there are multiple input parties (or clients) each holding a private set of elements and the receiver is an external party (termed as third-party) with no inputs. Multi-party third party PSI enables the receiver to learn only the intersection result of all input clients' private sets while revealing nothing else to the clients and the receiver. Our solutions include constructions that are provably secure against an arbitrary number of colluding parties in the semi-honest model. Additionally, we present protocols for third-party private set difference and private symmetric difference, whereby the learned output by the inputless third-party is the set difference and symmetric difference respectively of two other input parties, while preserving the same privacy guarantees. The motivation in the design of these protocols stems from their utilities in numerous real-world applications. We implemented our protocols and conducted experiments across various input and output set sizes.
## 2025/1329
* Title: Cryptanalysis of a multivariate CCZ scheme
* Authors: Alessio Caminata, Elisa Gorla, Madison Mabe, Martina Vigorito, Irene Villa
* [Permalink](https://eprint.iacr.org/2025/1329)
* [Download](https://eprint.iacr.org/2025/1329.pdf)
### Abstract
We consider the multivariate scheme $\texttt{Pesto}$, which was introduced by Calderini, Caminata, and Villa. In this scheme, the public polynomials are obtained by applying a CCZ transformation to a set of quadratic secret polynomials. As a consequence, the public key consists of polynomials of degree $4$.
In this work, we show that the public degree $4$ polynomial system can be efficiently reduced to a system of quadratic polynomials. This seems to suggest that the CCZ transformation may not offer a significant increase in security, contrary to what was initially believed.
## 2025/1330
* Title: Exploring Core Monomial Prediction Further: Weak-Key Superpoly Recovery for 852-Round Trivium
* Authors: Jiahui He, Kai Hu, Guowei Liu
* [Permalink](https://eprint.iacr.org/2025/1330)
* [Download](https://eprint.iacr.org/2025/1330.pdf)
### Abstract
The cube attack is one of the most powerful attacks on stream ciphers, with recovering the superpoly as its key step. The core monomial prediction is the state-of-the-art technique for superpoly recovery, which can reach 851 rounds for Trivium thus far (EUROCRYPT 2024). The core monomial prediction heavily relies on the trail enumeration which is the bottleneck for its efficiency.
This paper further explores the potential of the core monomial prediction for Trivium by constructing a composite representation for the superpoly. This representation allows us to detect the algebraic structure of the superpoly under specific conditions on the intermediate variables, without the computational burden of trail enumerations. Leveraging these discovered conditions, we successfully recovered weak-key superpolies for 852-round Trivium, establishing the first cryptanalytic result against 852-round Trivium in the literature to date.
## 2025/1331
* Title: Constant-Cycle Hardware Private Circuits
* Authors: Daniel Lammers, Nicolai M|+ller, Siemen Dhooghe, Amir Moradi
* [Permalink](https://eprint.iacr.org/2025/1331)
* [Download](https://eprint.iacr.org/2025/1331.pdf)
### Abstract
The efficient implementation of Boolean masking with minimal overhead in terms of latency has become a critical topic due to the increasing demand for physically secure yet high-performance cryptographic primitives. However, achieving low latency in masked circuits while ensuring that glitches and transitions do not compromise their security remains a significant challenge. State-of-the-art multiplication gadgets, such as the recently introduced HPC4 (CHES 2024), offer composable security against glitches and transitions, as proven under the robust d-probing model. However, these gadgets require at least one clock cycle per computation, resulting in a latency overhead that increases with the algebraic degree. In contrast, LMDPL gadgets (CHES 2014 & CHES 2020) can achieve fixed latency independent of the algebraic degree, effectively addressing this issue. However, they are limited to two shares, and extending them to guarantee composable security at order d with d+1 shares is considered an open challenge.
In this work, we introduce CCHPC, a novel hardware masking scheme built on the concept of LMDPL. Specifically, CCHPC achieves a fixed latency of d clock cycles by masking a Boolean function of arbitrary algebraic degree with d+1 shares. CCHPC gadgets are secure and trivially composable, as formally proven under the RR d-probing model (CHES 2024). Using CCHPC gadgets, we design a masked AES encryption core which can be instantiated for an arbitrary number of d+1 shares with a total latency of 11 + d clock cycles.
## 2025/1332
* Title: Technical Note: LeanSig for Post-Quantum Ethereum
* Authors: Justin Drake, Dmitry Khovratovich, Mikhail Kudinov, Benedikt Wagner * [Permalink](https://eprint.iacr.org/2025/1332)
* [Download](https://eprint.iacr.org/2025/1332.pdf)
### Abstract
In this note, we present a new instantiation of the hash-based multi-signature framework introduced by Drake, Khovratovich, Kudinov, and Wagner (CiC Vol 2 Issue 1, eprint 2025/055) for EthereumrCOs consensus layer. Inspired by a recent work of Khovratovich, Kudinov, and Wagner (Crypto 2025, eprint 2025/889), we instantiate the framework with a novel incomparable encoding that improves the tradeoff between signature size and verification hashing. The purpose of this document is to make explicit how to use the ideas of the latter work within the framework of Drake, Khovratovich, Kudinov, and Wagner.
## 2025/1333
* Title: Policy-Based Redactable Set Signatures
* Authors: Zachary A Kissel
* [Permalink](https://eprint.iacr.org/2025/1333)
* [Download](https://eprint.iacr.org/2025/1333.pdf)
### Abstract
A redactable set signature scheme is a signature scheme that allows a redactor, without possessing the signing key, to convert a signature on set $S$ to a signature on set $S'$ if $S' \subset S$. This paper introduces a new form of redactable set signature scheme called a policy-based redactable set signature scheme. These redactable set signatures allow for a signer to provide a redaction policy at signing time that limits the possible redactions that can be made by a redactor. In particular, a signature on set $S$ can only be redacted to a signature on $S'$ if $S' \subset S$ and $P\left(S'\right) = 1$.
## 2025/1334
* Title: On the use of ECDSA with hierarchical public key delegation in identity-based scenarios
* Authors: Lucas C. Cardoso, Marcos A. Simplicio Jr
* [Permalink](https://eprint.iacr.org/2025/1334)
* [Download](https://eprint.iacr.org/2025/1334.pdf)
### Abstract
In 2009, Galindo and Garcia proposed the usage of concatenated Schnorr signatures for the hierarchical delegation of public keys, creating a quite efficient identity-based signature scheme (IBS). Essentially, the scheme builds upon the Schnorr signature scheme to generate a primary signature, part of which is then used as a secret key to produce signatures on subsequent messages. The resulting IBS is proven secure against existential forgery on adaptive chosen-message and adaptive identity attacks using variants of the Forking Lemma. In this paper, our goal is to answer the following question: would it be feasible to build upon the widely used elliptic curve digital signature algorithm (ECDSA) scheme to obtain a similarly secure and efficient IBS? We answer this affirmatively, opening interesting possibilities not only for identity-based signatures with ECDSA but also for applications such as secure credential delegation. This latter application is of particular interest considering the wide support for ECDSA in web- and cloud-oriented authentication systems (e.g., based on JSON Web Tokens). The resulting scheme is proven secure, combining the Bijective Random Oracle model and the existential unforgeability game in an identity-based setup. Our results show that even considering ECDSA's non-linear characteristic and more convoluted verification process when compared to Schnorr signatures, it is possible to obtain shorter signatures than Galindo-Garcia's scheme.
## 2025/1335
* Title: A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies
* Authors: Farzin Renan
* [Permalink](https://eprint.iacr.org/2025/1335)
* [Download](https://eprint.iacr.org/2025/1335.pdf)
### Abstract
Digital signatures are essential cryptographic tools that provide authentication and integrity in digital communications. However, privacy-sensitive applicationsrCosuch as e-voting and digital cashrCorequire more restrictive verification models to ensure confidentiality and control. Strong Designated Verifier Signature (SDVS) schemes address this need by enabling the signer to designate a specific verifier, ensuring that only this party can validate the signature. Existing SDVS constructions are primarily based on number-theoretic assumptions and are therefore vulnerable to quantum attacks. Although post-quantum alternativesrCoparticularly those based on latticesrCohave been proposed, they often entail large key and signature sizes.
In this work, we introduce $\mathsf{CSI\text{-}SDVS}$, a novel isogeny-based SDVS scheme that offers a compact, quantum-resistant alternative. Our construction builds on the ideal class group action framework of CSIDH and the signature techniques of CSI-FiSh, and relies on the hardness of the Multi-Target Group Action Inverse Problem (MT-GAIP). $\mathsf{CSI\text{-}SDVS}$ achieves strong security guaranteesrConamely, Strong Unforgeability under Chosen-Message Attacks (SUF-CMA), Non-Transferability (NT), and Privacy of SignerrCOs Identity (PSI)rCoin the random oracle model. Remarkably, both the keys and signatures in $\mathsf{CSI\text{-}SDVS}$ are of size $\mathcal{O}(\lambda)$, representing a significant improvement over the typical $\mathcal{O}(\lambda^2)$ bounds in existing post-quantum SDVS schemes, thereby making it among the most compact PQC-based SDVS schemes and the only post-quantum secure construction based on isogenies.
## 2025/1336
* Title: Representations of Elementary Vectors in VOLE-in-the-head-based Schemes
* Authors: Tung Chou
* [Permalink](https://eprint.iacr.org/2025/1336)
* [Download](https://eprint.iacr.org/2025/1336.pdf)
### Abstract
This paper presents a family of representations of elementary vectors, which covers existing representations as special cases. We make use of the family of representations to reduce signature size of existing signature schemes based on the VOLE-in-the-head framework. In particular, we use new representations to build modelings for the regular syndrome decoding problem in $\mathbb{F}_2$, which is used in the post-quantum signature scheme SDith, and for the permuted kernel problem in characteristic-2 fields, which is used in a post-quantum signature scheme recently proposed by Bettaieb, Bidoux, Gaborit, and Kulkarni. For the rCLshortrCY parameter sets of SDith, which are designed for minimiz-
ing signature size, we achieve a size reduction of 3.6% to 4.2%. For parameter sets of the Bettaieb-Bidoux-Gaborit-Kulkarni signature scheme, we achieve a size reduction of 9% to 12%.
## 2025/1337
* Title: $\textsf{Electrum}$: UC Fail-Stop Server-Supported Signatures
* Authors: Nikita Snetkov, Jelizaveta Vakarjuk, Peeter Laud
* [Permalink](https://eprint.iacr.org/2025/1337)
* [Download](https://eprint.iacr.org/2025/1337.pdf)
### Abstract
Migration to quantum-safe cryptography represents a significant technological shift, addressing the vulnerabilities of traditional cryptographic primitives, such as KEMs and digital signatures. Yet, a number of challenges remain, especially in the development of secure solutions for sophisticated cryptographic applications. One of them is Smart-ID, European server-supported (threshold) signing service.
To address this issue, we present $\textsf{Electrum}$, a fail-stop server-supported signature scheme designed to enhance security of existing Smart-ID service. $\textsf{Electrum}$ combines multiprime RSA-based signatures with fail-stop features: providing not only unforgeability against classical adversaries but also allowing to prove that a given signature is a forgery made by classical and/or quantum adversaries. Proposed protocol can be seen as a temporary remedy against the quantum threat until standardised threshold signature schemes become a common practice. To prove security of $\textsf{Electrum}$, we introduce a new ideal functionality $\mathcal{F}^{\textsf{SplFS}}$ for a fail-stop server-supported signing in the Universal Composability model. We show that $\textsf{Electrum}$ protocol securely realizes the proposed functionality $\mathcal{F}^{\textsf{SplFS}}$.
## 2025/1338
* Title: Limits on the Power of Constrained PRFs and Identity-based Cryptography
* Authors: Roman Langrehr
* [Permalink](https://eprint.iacr.org/2025/1338)
* [Download](https://eprint.iacr.org/2025/1338.pdf)
### Abstract
Constrained PRFs are PRFs that allow the generation of constrained keys, which can be used to evaluate the PRF on a subset of the inputs. The PRF is still pseudorandom for an adversary who obtains multiple of these constrained keys on all inputs where none of the constrained keys allow it to evaluate the PRF. Constrained PRFs are known for some simple constraint classes (such as puncturing or intervals) from one-way functions, but for more powerful constraint classes such as bitfixing the only known constructions need heavy machinery, like indistinguishability obfuscation or multilinear maps.
In this work we show that constrained PRFs (for any constraint class) do not imply key agreement in a black-box way with an oracle separation. The result also applies to delegatable constrained PRFs, where constrained keys can be used to generate other, more restrictive constrained keys.
We show that this result has interesting applications for identity-based cryptography, where users obtain secret keys from a trusted, central authority. Namely, it shows that primitives that allow key agreement in this setting, like identity-based non-interactive key exchange and a weaker variant of identity-based encryption that we introduce in this work, do not imply key agreement and thus can exist even in a world where traditional key agreement and public-key encryption is impossible.
As a side result, we obtain a very simple proof of the classic result by Impagliazzo and Rudich (STOC 89) that separates key agreement from one-way functions. The proof is similar to a proof by Brakerski, Katz, Segev, and Yerukhimovich (TCC 2011), but more general because it applies to key agreement with non-perfect correctness. The proof also shows that Merkle puzzles are optimal, which Barak and Mahmoody (Crypto 2009) have shown before, but our proof is much simpler (and has tighter constants).
## 2025/1339
* Title: Breaking the Twinkle Authenticated Encryption Scheme and Analyzing Its Underlying Permutation
* Authors: Debasmita Chakraborty, Hosein Hadipour, Anup Kumar Kundu, Mostafizar Rahman, Prathamesh Ram, Yu Sasaki, Dilip Sau, Aman Sinha
* [Permalink](https://eprint.iacr.org/2025/1339)
* [Download](https://eprint.iacr.org/2025/1339.pdf)
### Abstract
This paper studies the Twinkle family of low-latency symmetric key schemes designed by Wang et al. (CiC 2024). In particular, it presents cryptanalysis of both the mode and the underlying primitive. Twinkle is a PRF-based design, and an authenticated encryption scheme Twinkle-AE is specified based on a dedicated PRF called Twinkle-PRF. To achieve low latency, Twinkle-PRF uses a large key and state to produce sufficient randomness in a single step. Twinkle-AE uses a 1024- or 512-bit key for authentication and generates a $t$-bit tag, where $t \in \{64, 128\}$. It claims to provide $t$ bits of integrity.
Several Twinkle-AE parameter sets claim higher confidentiality than integrity. In this setup, for any ciphertext, an adversary can obtain the message after $O(2^t)$ decryption attempts by guessing the tag, allowing attacks in the chosen-ciphertext setting. We show that a 1024- or 512-bit authentication key can be recovered using only $O(2^t)$ queries. The recovered authentication key enables the generation of valid ciphertexts for arbitrary plaintexts, thus achieving universal forgery.
In the second part of the paper, we perform cryptanalysis on reduced-round variants of the 1280-bit public permutation Twinkle-P, which serves as a core component of Twinkle-PRF.
We investigate impossible differential, zero-correlation linear, integral, and differential-linear distinguishers by developing automated analytic tools. We provide practical distinguishers for up to 5 rounds, and the longest distinguisher reaches 6 rounds with a complexity of $2^{74.32}$. This surpasses the round bounds evaluated by the designers. We stress that our attacks on mode exploits the gap between the claimed confidentiality and integrity levels, thus have no impact on the parameter sets having the same security level.
Our attacks on the permutation do not have any significant impact on the whole specifications. Moreover, we note that Twinkle-AE-512b/Twinkle-AE-1024b and Twinkle-PA remain secure, and the versions we attacked would also be secure if the claimed confidentiality level matched the integrity level.
## 2025/1340
* Title: Zelda: Efficient Multi-server Preprocessing PIR with Unconditional Security
* Authors: Ashrujit Ghoshal, Mingxun Zhou, Bo Peng, Elaine Shi
* [Permalink](https://eprint.iacr.org/2025/1340)
* [Download](https://eprint.iacr.org/2025/1340.pdf)
### Abstract
Private Information Retreival (PIR) schemes without preprocessing are known to incur linear server computation per client query. Several recent works have shown that by relying on a one-time preprocessing phase, we can get around this barrier, and achieve sublinear computation per query without relying on any cryptographic assumptions. Beimel et al. (CRYPTO'00) first showed a family of schemes whose bandwidth and computation per query scale as fast as $n^{O(1/S)}$ where $S$ denotes the number of servers and $n$ denotes the database size. Unfortunately, their schemes are not practical partly because the servers must each store an encoded version of the database, and the encoding length grows sharply as we increase $S$. The recent work of Singh et al. (TCC'24) showed how to achieve similar bandwidth scaling but without the server space blowup. To get this, they rely on a different type of preprocessing called client-specific preprocessing, where the stateful client stores some hints and the servers store only the original database. Unfortunately, Singh et al.'s result is completely impractical due to the reliance on Dvir and Gopi's PIR as a building block.
We propose Zelda (short for ZEro-Leakage Data Access), the first concretely efficient, information-theoretic multi-server PIR scheme with sublinear computation. Our work makes both theoretical and practical contributions. On the theoretical front, we devise a unified framework for constructing multi-server PIR with client-specific preprocessing. This gives us a parametrizable family of schemes that asymptotically outperform all prior constructions in the same setting, including Singh et al. (TCC'24) and Ishai et al. (CRYPTO'24). On the practical front, Zelda is conceptually simple, self-contained, and does not rely on any underlying PIR as a building block. We implemented Zelda and open sourced our code. We compared the concrete performance of Zelda with a state-of-the-art PIR scheme called QuarterPIR (Eurocrypt'24), which relies on pseudorandom functions for security. Experimental results show that Zelda outperforms QuarterPIR in terms of online response time and client space (assuming typical fiber optical links), at the price of increased costs for offline maintenance operations.
## 2025/1341
* Title: Practical Attack on All Parameters of the HPPC Signature Scheme
* Authors: Pierre Briaud, Maxime Bros, Ray Perlner, Daniel Smith-Tone
* [Permalink](https://eprint.iacr.org/2025/1341)
* [Download](https://eprint.iacr.org/2025/1341.pdf)
### Abstract
HPPC is a multivariate signature scheme submitted to the NIST PQC standardization process in response to the recent call for additional signature schemes. We show that, despite some non-standard notational choices in the submission document, HPPC can be viewed as a special case of the well-studied, but broken for all practical parameters, HFE signature scheme. We further show that the HPPC construction introduces additional structure that further weakens the scheme. For instance, the central map has $Q$-rank $2$ independently from the degree $D$ of the central polynomial that is used.
Using these observations, we show that HPPC is weaker against the direct attack than claimed in the submission document and more crucially that all parameter sets can be practically broken using MinRank techniques. For instance, with a very naive implementation, we have been able to recover an equivalent key in approximately 8 minutes for security level 2, an hour and a half for security level 4, and slightly more than 7 hours for security level 5.
## 2025/1342
* Title: Simultaneous Diophantine Approximation for Compact Discrete Gaussian Sampling
* Authors: Ke Ma, Jiabo Wang, Shanxiang Lyu, Junzuo Lai, Zsolt L|ingi
* [Permalink](https://eprint.iacr.org/2025/1342)
* [Download](https://eprint.iacr.org/2025/1342.pdf)
### Abstract
Discrete Gaussian Sampling (DGS) over the integersrCoalso known as integer Gaussian samplingrCo is used to generate integer values that statistically follow the discrete Gaussian distribution and plays a central role in lattice-based cryptography. Among existing approaches for integer DGS, the cumulative distribution table (CDT) method is widely adopted. However, CDT sampling typically incurs substantial storage costs due to the need to store high-precision fixed-point probability tables, where a precision of $k$ bits is required to achieve a statistical distance of $2^{-k}$ from the ideal distribution.
In this work, we propose a more compact representation of CDT based on Simultaneous Diophantine Approximation (SDA). Instead of storing fixed-point values, our method expresses the probabilities in the CDT as a sequence of rational numbers with a common denominator. With parameter selection guided by SDA, this compact fractional representation enables reducing data width while maintaining the same level of statistical accuracy. Our SDA-CDT construction offers clear advantages in both computation speed and storage compared to classical CDT implementations. For example, in Frodo-1344, our sampler achieves a 19.97% increase in speed (from 12.10 million to 14.51 million samples per second) and a 3.85% reduction in memory usage (from 104 bits to 100 bits). Similarly, in Frodo-976, we observe a 10.88% speedup and a 21.60% decrease in memory cost. In addition, our design eliminates floating-point arithmetic and supports a fully constant-time online sampling procedure, which ensures resistance to timing side-channel attacks without compromising performance.
## 2025/1343
* Title: A Hybrid Asymmetric Password-Authenticated Key Exchange in the Random Oracle Model
* Authors: Jelle Vos, Stanislaw Jarecki, Christopher A. Wood, Cathie Yun, Steve Myers, Yannick Sierra
* [Permalink](https://eprint.iacr.org/2025/1343)
* [Download](https://eprint.iacr.org/2025/1343.pdf)
### Abstract
Symmetric encryption allows us to establish a secure channel based on a shared, strong key. However, users cannot remember or cannot store such keys securely. Password-Authenticated Key Exchange (PAKE) protocols address this by using low-entropy, human-memorizable passwords to establish secure channels. PAKEs are widely used and are foundational in practical cryptographic protocols, but while cryptographic tools like Key Encapsulation Mechanism (KEM) and Signatures have been implemented to resist attacks from quantum computers, PAKEs have gained quantum security only recently.
To hedge against any potential vulnerabilities in recent quantum-secure PAKEs and in their implementations, we primarily focus on hybrid PAKE constructions that compose CPace, a classically-secure PAKE, with a variant of a recently proposed quantum-secure PAKE, which we call OQUAKE. Specifically we introduce and analyze two new hybrid PAKEs designed to be efficient, easy to implement, and utilize a minimized set of standard building blocks. The first, called CPaceOQUAKE, is a hybrid symmetric PAKE that remains secure as long as either a classical or post-quantum assumption holds. The second, called CPaceOQUAKE+, is a hybrid asymmetric PAKE (aPAKE) where the server party holds a verifier that obscures the password, instead of holding the password itself. In our analysis we present the necessary security proofs in the Universal Composability framework. In particular, we prove that OQUAKE, the underlying KEM-based PAKE in our hybrid constructions, realizes a relaxed UC PAKE variant that exposes password equality to passive observers, an observation available anyway in typical applications of PAKEs where the network interactions which follow the PAKE depend on authentication success. Moreover, we prove that our variant of the PAKE(+KEM)-to-aPAKE compiler is a similarly relaxed UC aPAKE.
## 2025/1344
* Title: Side-Channel Sensitivity Analysis on HQC: Towards a Fully Masked Implementation
* Authors: Guillaume Goy, Maxime Spyropoulos, Nicolas Aragon, Philippe Gaborit, Renaud Pacalet, Fabrice Perion, Laurent Sauvage, David Vigilant
* [Permalink](https://eprint.iacr.org/2025/1344)
* [Download](https://eprint.iacr.org/2025/1344.pdf)
### Abstract
Hamming Quasi-Cyclic (HQC) has recently been officially selected for standardization by NIST as a post-quantum KEM alternative to ML-KEM.
This milestone raises new requirements, in particular the need to design and deploy secure implementations of the scheme.
This paper presents two major contributions to secure HQC against Side-Channel Attacks (SCAs).
First, we present a detailed sensitivity analysis of HQC, highlighting the critical variables and critical internal functions that need to be protected.
Second and main contribution, we propose the first fully masked HQC implementation at any order.
It is also the first PQC masked implementation that is formally proved to be secure in the MIMO-SNI security model.
This security, introduced by Cassiers and Standaert in 2020, ensures the security of gadgets composition against propagating probes.
In this paper, we provide benchmarks of our implementation, showing that our masked implementation is competitive in the state-of-the-art masked PQC implementations.
## 2025/1345
* Title: SLVer Bullet: Straight-Line Verification for Bulletproofs
* Authors: Brandon Goodell, Rigo Salazar, Freeman Slaughter, Luke Szramowski
* [Permalink](https://eprint.iacr.org/2025/1345)
* [Download](https://eprint.iacr.org/2025/1345.pdf)
### Abstract
In Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity, Eagen proposes a method for checking whether a sum of points in an elliptic curve group have been computed correctly. Eagen's method verifiably checks elliptic curve group operations only with linear combinations in the base field, allowing very general proofs to be encoded in inner product argument systems and rank-1 constraint systems (R1CS). We call this method "straight-line verification,'' due to how it utilizes straight lines in the verification procedure. In FCMP++ by Parker, the author uses Eagen's method in a R1CS to verify scalar multiplication of group elements, proposing a protocol based on Eagen's arguments. Although the iterative witness construction algorithm proposed by Eagen is correct, the arguments are rather informal, lacking precise protocol descriptions, claims, proofs, or efficiency analyses. We present a method based on Eagen's technique for straight-line verification of cryptographic protocols, offloading the bulk of the computational costs faced by verifiers onto the prover, which is useful for light-weight devices or when verification must be performed repeatedly. Computational improvements are largely due to replacing expensive division operations with lower-cost arithmetic by applying logarithmic derivatives.
Our work, while not fully novel, is a healthy expansion of previous work. In Soundness Proof for an Interactive Protocol for the Discrete Logarithm Relation, Bassa contributed towards formalizing Eagen's method, explicitly describing Parker's proof of scalar multiplication and sketching arguments towards proofs of soundness. However, the soundness arguments in Bassa's work are not without obstacles. Per Eagen, rational solutions to certain systems of polynomial equations are assumed to exist. We point out that these equations do not, in fact, admit rational solutions in general. Bassa lifts to the surface of pairs of elliptic curve group points to avoid this problem, but the verification equations proposed by Eagen and studied by Bassa are not sufficiently justified in those documents.
The verification equations described by Bassa reduce to our verification equations, and therefore they are equivalent. In particular, given a variable choice of a line in the affine plane with three distinct, non-identity, and collinear points on an elliptic curve $\mathcal{E}$, say $P, Q, R$ with interpolating slope $\lambda$ and $x$-coordinates $X_P$, $X_Q$, and $X_R$, these points are necessarily dependent: $\lambda^2 = X_P + X_Q + X_R$. Thus, given any derivation $d$ on the function field $K(\mathcal{E})$ over $K$, we have $dX_R = -dX_P - dX_Q$, allowing computations to reduce further than presented in Bassa's work.
Nonetheless, Bassa's amended approach results in formal arguments, if not proofs, of security. We fully justify the verification equations presented by Bassa, show they reduce further, and reconsider the security of Eagen's approach under the reduced verification equations. We encourage the reader to keep in mind that our verification equations are equivalent reduced versions of those presented by Bassa. Along the way, we exploit the techniques utilized by Eagen to further reduce the total number of field divisions required by prover to just a single one. Our framework is easily applied to generically speed up verification in discrete-logarithm-based protocols.
We present our protocol, and explicitly compute the completeness and soundness errors. We remark on how to complete the scheme, and our soundness error supersedes the previous estimates in the literature. We also show how the corrected scheme can be used to verify scalar multiplication as in Parker's proposed protocol. We then apply this approach to zero-knowledge proof systems such as the Schnorr identification scheme and Bulletproofs to illustrate the generic computational advantage offered by divisors. Because these protocols are simple, secure, and popular, we demonstrate that this work is readily applicable to improve verifier computation in cryptocurrencies such as Monero or Salvium.
## 2025/1346
* Title: Cryptanalysis of TFHE-friendly Cipher FRAST
* Authors: Antoine Bak, Shibam Ghosh, Fukang Liu, Jianqiang Ni, Willi Meier, L|-o Perrin
* [Permalink](https://eprint.iacr.org/2025/1346)
* [Download](https://eprint.iacr.org/2025/1346.pdf)
### Abstract
FRAST is a TFHE-friendly stream cipher that was published at FSE 2025. The cipher is defined over $\mathbb{Z}_{16}$, and makes extensive use of negacyclic S-boxes over $\mathbb Z_{16}$ as they are less costly in TFHE. Like many FHE-friendly ciphers, FRAST randomizes some of its components to increase its security against statistical attacks. In the case of FRAST, some S-boxes are randomized using an XOF that takes a nonce as input.
In this work, we point out a strong structural property of the full FRAST permutation, which leads to a much simpler alternative representation of the primitive. We study the consequences of this representation and find a weak key space of non-negligible size (i.e., much larger than $2^{128}$) on which every ciphertext leaks one bit of plaintext. This corresponds to a distinguishing attack on the full FRAST in the weak-key setting. In particular, we emphasize that, apart from the structural property, the usage of negacyclic S-boxes further leads to a much larger weak-key space for our attack.
Finally, we provide a general framework to mount a linear attack on FRAST in the average key setting. We briefly describe our approach in the end of the paper, and observe that standard assumptions expected to work in the context of linear cryptanalysis do not hold in the case of FRAST: our experiment indicate that a linear attack in the average key setting does not work as expected.
## 2025/1347
* Title: Public Traceability in Threshold Decryption
* Authors: S|-bastien Canard, Nathan Papon, Duong Hieu Phan
* [Permalink](https://eprint.iacr.org/2025/1347)
* [Download](https://eprint.iacr.org/2025/1347.pdf)
### Abstract
Tracing techniques have been used to identify users who have leaked their decryption keys in a secure multi-receiver encryption system. Very recently, in the field of distributed cryptography, where trust is distributed, Boneh et al. extended traitor tracing to the framework of threshold decryption, where a single user doesn't hold the whole secret to decrypt but needs to collaborate with others. However, the tracing capacity in their collusion-secure codes-based schemes is still centralized: only the authority holding the secret tracing key can perform tracing. We continue in the direction of not relying on a single entity and propose decentralizing tracing in this context so that the tracing procedure does not need to rely on any secret key and can be done by anyone. Technically, as binary collusion-secure codes only support secret tracing, we switch to robust $q$-ary IPP codes supporting public tracing. This requires us to generalize the bipartite threshold KEM for two users in Boneh et al.'s paper to $q$-partite KEM for q users. In terms of security, their static one-sided security in the binary case is not appropriate, which requires us to define an adaptive one-sided security notion for $q$-partite KEM to be compatible with $q$-ary IPP codes. Finally, we generalize the Boneh et al. construction to achieve this security notion and achieve public traceability for threshold decryption without degrading efficiency.
## 2025/1348
* Title: The CRO Trilemma : a formal incompatibility between Confidentiality, Reliability and legal Opposability in Post-Quantum proof systems
* Authors: Thierry Emmanuel MINKA MI NGUIDJOI, MANI ONANA Flavien Serge, DJOTIO NDI|e Thomas
* [Permalink](https://eprint.iacr.org/2025/1348)
* [Download](https://eprint.iacr.org/2025/1348.pdf)
### Abstract
This work establishes the CRO Trilemma: no post-quantum proof system can simultaneously satisfy the following three properties beyond negligible failure probability: (i) Confidentiality, quantified by Priv > 1 - negl(lambda); (ii) Reliability, with Rel > 1 - negl(lambda); and (iii) Legal Opposability, measured by contextual entropy H_Opp ree log |V_J|, where V_J denotes the validation space of a polynomial-time institutional verifier J.
The result formalizes the Invisible Authenticity Paradox through contextual entropy H(C) and quantum interpretability loss eta_q(C). Under standard quantum assumptions, we prove the following impossibility bound against QPT adversaries:
H_Opp <= (Priv * Rel) / (epsilon_eff * 2^H(C)) + eta_q(C) + negl(lambda)
A composable framework is introduced, including a composable model with verifier J (Algorithm 1), and an optimal entropy decomposition theorem (Theorem 2.3). Theoretical predictions are supported by empirical evidence indicating consistent violation of the bound (Gamma_CRO > 0.8) across NIST PQC finalists (e.g., Dilithium) and structured ZKPs (e.g., STARKs, Groth16).
## 2025/1349
* Title: $\mathsf{HyperFond}$: A Transparent and Post-Quantum Distributed SNARK with Polylogarithmic Communication
* Authors: Yuanzhuo Yu, Mengling Liu, Yuncong Zhang, Shi-Feng Sun, Tianyi Ma, Man Ho Au, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/1349)
* [Download](https://eprint.iacr.org/2025/1349.pdf)
### Abstract
Recent years have witnessed the surge of academic researches and industrial implementations of succinct non-interactive arguments of knowledge (SNARKs). However, proving time remains a bottleneck for applying SNARKs to large-scale circuits. To accelerate the proof generation process, a promising way is to distribute the workload to several machines running in parallel, the SNARKs with which feature are called distributed SNARKs. Nevertheless, most existing works either require a trusted setup, or rely on quantum-insecure assumptions, or suffer from linear communication costs.
In this paper, we introduce $\mathsf{HyperFond}$, the first distributed SNARK that enjoys a transparent setup, post-quantum security and polylogarithmic communication cost, as well as the field-agnostic property (no reliance on specific choices of fields). To this end, we first propose a distributed proof system based on HyperPlonk (by Chen et al. in EUROCRYPT 2023). To instantiate the system, we then put forward a novel approach to distribute the multilinear polynomial commitment scheme in BaseFold (by Zeilberger et al. in CRYPTO 2024), and also present a trade-off between communication cost and proof size. In $\mathsf{HyperFond}$, after committing to polynomial coefficients with quasilinear complexity, each sub-prover generates proofs with time linear in subcircuit size.
We implement $\mathsf{HyperFond}$ using up to 16 machines. Experimental results demonstrate that the proving time of $\mathsf{HyperFond}$ is 14.3 $\times$ faster than HyperPlonk instantiated with BaseFold. We also compare to deVirgo (by Xie et al. in CCS 2022), so far the only post-quantum distributed SNARK, and achieve a 1.89 $\times$ speedup.
## 2025/1350
* Title: Rhyme: A Fiat-Shamir Lattice-based Signature with 3C Sampling
* Authors: Zhongxiang Zheng, Anyu Wang, Chunhuan Zhao, Guangwu Xu, Zhengtao Jiang, Sibo Feng, Zhichen Yan, Shuang Sun, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2025/1350)
* [Download](https://eprint.iacr.org/2025/1350.pdf)
### Abstract
In this paper, we propose a new postquantum lattice-based digital signature named Rhyme. The scheme is based on the Fiat-Shamir structure and does not rely on flooding, rejection sampling, or Gaussian convolution as previous methods. Instead, its security is based on a variant of LWE combined with a new sampling method (3C sampling). We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency and very compact signature size compared with former results.
## 2025/1351
* Title: Revisiting the Generalized Birthday Problem and Equihash: Single or K Lists?
* Authors: Lili Tang, Yao Sun, Xiaorui Gong
* [Permalink](https://eprint.iacr.org/2025/1351)
* [Download](https://eprint.iacr.org/2025/1351.pdf)
### Abstract
The Generalized Birthday Problem ($\textsf{GBP}$), which seeks $k$ hash values from $k$ lists whose XOR is zero, is a fundamental problem across multiple cryptographic domains. Wagner's \(k\)-list algorithm (Crypto'02) for $\textsf{GBP}$ has advanced the optimization of solving the syndrome decoding problem and established new cryptanalytic benchmarks for incremental cryptography and blind signatures. $\textsf{Equihash}$ (NDSS'16) underscores the critical advantages of $\textsf{GBP}$ in proof-of-work design, particularly its ASIC-resistance in blockchain. While the k-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ utilize a single-list variant (selecting hash values from a single list) without clear theoretical grounding. In this work, we revisit these two long-conflated problems and fill in theoretical gaps in solving the single-list $\textsf{GBP}$.
In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. Our trade-off optimization to Wagner's algorithmic framework further diminishes this resistance by reducing peak memory by at least 50% across most $\textsf{Equihash}$ parameters. To address this, we propose $\textsf{Sequihash}$, a PoW with enhanced ASIC-resistance, rigorously aligned with the $k$-list $\textsf{GBP}$. Furthermore, we explore the implications of $\textsf{GBP}$ in the field of incremental hash and propose a new collision attack on ID-based incremental hash (Eurocrypt'97). Our attack achieves an asymptotic time complexity of $\mathcal{O}(\sqrt{n} \cdot 2^{\sqrt{2n}})$, significantly improving upon the previous Wagner's bound of $\mathcal{O}(2^{\sqrt{4n}})$. Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from \( 2^{256} \) to \( 2^{189} \).
## 2025/1352
* Title: InsPIRe: Communication-Efficient PIR with Silent Preprocessing
* Authors: Rasoul Akhavan Mahdavi, Sarvar Patel, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2025/1352)
* [Download](https://eprint.iacr.org/2025/1352.pdf)
### Abstract
We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication).
Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR [Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]).
In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query.
Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication.
Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput.
We show that InsPIRe enables improvements across a wide
range of applications and database shapes including the InterPlanetary File System and private device enrollment.
At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts.
InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-switching matrices.
We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small.
To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.
## 2025/1353
* Title: Introducing two ROS attack variants: breaking one-more unforgeability of BZ blind signatures
* Authors: Bruno M. F. Ricardo, Lucas C. Cardoso, Leonardo T. Kimura, Paulo S. Barreto, Marcos A. Simplicio Jr
* [Permalink](https://eprint.iacr.org/2025/1353)
* [Download](https://eprint.iacr.org/2025/1353.pdf)
### Abstract
In 2023, Barreto and Zanon proposed a three-round Schnorr-like blind signature scheme, leveraging zero-knowledge proofs to produce one-time signatures as an intermediate step of the protocol. The resulting scheme, called BZ, is proven secure in the discrete-logarithm setting under the one-more discrete logarithm assumption with (allegedly) resistance to the Random inhomogeneities in a Overdetermined Solvable system of linear equations modulo a prime number $p$ attack, commonly referred to as ROS attack. The authors argue that the scheme is resistant against a ROS-based attack by building an adversary whose success depends on extracting the discrete logarithm of the intermediate signing key. In this paper, however, we describe a distinct ROS attack on the BZ scheme, in which a probabilistic polynomial-time attacker can bypass the zero-knowledge proof step to break the one-more unforgeability of the scheme. We also built a BZ variant that, by using one secure hash function instead of two, can prevent this particular attack. Unfortunately, though, we show yet another ROS attack that leverages the BZ scheme's structure to break the one-more unforgeability principle again, thus revealing that this variant is also vulnerable. These results indicate that, like other Schnorr-based strategies, it is hard to build a secure blind signature scheme using BZ's underlying structure.
## 2025/1354
* Title: Shred-to-Shine Metamorphosis in Polynomial Commitment Evolution
* Authors: Weihan Li, Zongyang Zhang, Sherman S. M. Chow, Yanpei Guo, Boyuan Gao, Xuyang Song, Yi Deng, Jianwei Liu
* [Permalink](https://eprint.iacr.org/2025/1354)
* [Download](https://eprint.iacr.org/2025/1354.pdf)
### Abstract
Polynomial commitment schemes (PCSs) enable verifying evaluations of committed polynomials. Multilinear (ML) PCSs from linear codes are favored for their prover time. Distributed MLPCSs further reduce it by enabling multiple provers to distribute both commitment and proof generation.
We propose $\mathsf{PIP}_\mathsf{FRI}$, an FRI-based MLPCS that unites the linear prover time of PCSs from encodable codes with the compact proofs and fast verification of ReedrCoSolomon (RS) PCSs. By cutting FFT and hash overhead for both committing and opening, $\mathsf{PIP}_\mathsf{FRI}$ runs $10\times$ faster in prover than the RS-based DeepFold (Usenix Security'25) while retaining competitive proof size and verifier time, and beats Orion (Crypto'22) from linear codes by $3.5$-fold in prover speed while reducing proof size and verification time by $15$-fold.
Its distributed version $\mathsf{DePIP}_\mathsf{FRI}$ delivers the first code-based distributed SNARK for arbitrary circuits over a single polynomial, and further achieves accountability. $\mathsf{DePIP}_\mathsf{FRI}$ outperforms DeVirgo (CCS'22)---the only prior code-based distributed MLPCS, limited to data-parallel circuits and lacking accountability---by $25\times$ in prover time and $7\times$ in communication, with the same number of provers.
A central insight in both constructions is the shred-to-shine technique. It further yields a group-based MLPCS of independent interest, with $16\times$ shorter structured reference string and $10\times$ faster opening time than multilinear KZG (TCC'13).
## 2025/1355
* Title: Unconditional Pseudorandomness against Shallow Quantum Circuits
* Authors: Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan
* [Permalink](https://eprint.iacr.org/2025/1355)
* [Download](https://eprint.iacr.org/2025/1355.pdf)
### Abstract
Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography, and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity-theoretic assumptions.
In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove the following:
(1) Any quantum state $2$-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0 \circ \mathsf{QNC}^0$ circuits with nearly linear ancillae.
(2) Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes.
(3) Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing.
Our indistinguishability results for $2$-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.
## 2025/1356
* Title: Group Signatures with Message-Dependent Opening Directly Imply Timed-Release Encryption
* Authors: Yuto Imura, Keita Emura
* [Permalink](https://eprint.iacr.org/2025/1356)
* [Download](https://eprint.iacr.org/2025/1356.pdf)
### Abstract
Group signatures (GS, Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove the membership and also allow the special authority called the opener can identify the signer. Group signatures with message-dependent opening (GS-MDO, Sakai et al., Pairing 2012) weakened the power of the opener by introducing another authority called the admitter who issues a message-dependent token. It would be a natural research topic to clarify whether cryptographic primitives that are required to construct GS-MDO are stronger than those of GS or not, according to the enhanced functionality of GS-MDO. In this paper, we propose a generic construction of timed-release encryption (TRE) from GS-MDO. Note that Sakai et al. have shown that GS-MDO implies identity-based encryption (IBE), and Nakai et al. (IWSEC 2009) and Matsuda et al. (Pairing 2010) demonstrated generic constructions of TRE from IBE. Thus, we do not show any new result from the viewpoint of feasibility. We show that (1) GS-MDO directly implies TRE without employing the generic constructions of TRE from IBE, and (2) the proposed TRE construction provides public verifiability, that is not usually supported by TRE, because a TRE ciphertext is a group signature in our construction. We also introduce a new security notion which we call token unforgeability where no adversary can forge a token even the adversary has the opener's secret key, and prove that token unforgeability is implied by opener anonymity which is a fundamental security notion of GS-MDO. Our result implies that GS-MDO is a very strong cryptographic primitive.
## 2025/1357
* Title: How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions
* Authors: Alper |cakan, Vipul Goyal
* [Permalink](https://eprint.iacr.org/2025/1357)
* [Download](https://eprint.iacr.org/2025/1357.pdf)
### Abstract
A quantum copy-protection scheme (Aaronson, CCCrCO09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality. There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of |cakan and Goyal (IACR Eprint, 2025) showed how to copy-protect all cryptographically puncturable schemes with pseudorandom puncturing points.
In this work, we show how to copy-protect even a larger class of schemes. We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is a flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not known how to copy-protect prior to our work.
Going further, we show that our scheme is secure against arbitrary high min-entropy challenge distributions whereas previous work has only considered schemes that are punctured at pseudorandom points.
## 2025/1358
* Title: Domain-Oriented Masking Revisited: More Efficient AES Implementations with Arbitrary Protection Order
* Authors: Feng Zhou, Hua Chen, Limin Fan, Junhuai Yang
* [Permalink](https://eprint.iacr.org/2025/1358)
* [Download](https://eprint.iacr.org/2025/1358.pdf)
### Abstract
Recent years have witnessed significant progress in composable masked AES designs based on Hardware Private Circuits (HPCs) under the Probe-Isolating Non-Interference (PINI) framework. However, these designs still suffer from substantial randomness requirements and area overhead at higher protection orders. In this work, we revisit Domain-Oriented Masking (DOM), originally proposed by Gross et. al. in 2016, and leverage the DOM-$dep$ and DOM-$indep$ multipliers to construct efficient AES implementations based on the Strong Non-Interference (SNI) framework. Our contributions include:
1. a comprehensive security analysis of DOM-$dep$ and DOM-$indep$, including their compositional security under the SNI framework;
2. more efficient masked AES implementations for arbitrary protection orders, reducing randomness and area overhead while maintaining latency comparable to state-of-the-art HPC3-based designs.
Specifically, our masked AES implementations maintain a latency of 41 clock cycles by using the Hadzic's decomposition for $F_2^8$ inverter. When $d <= 4$, they save at least 13% in area (RNG included) and reduce latency by 19.6% compared to the smallest $d$-PINI round-based masked AES implementations provided by Cassiers et.al. (The current version focuses on the core construction and its initial evaluation. Source code has been made publicly available to facilitate verification. Further performance optimizations and theoretical generalizations are underway and will appear in an upcoming revision.)
## 2025/1359
* Title: Runtime Code Generation for Constant-Time Secret-Indexed Array Accesses: Applications to PERK and NTRU
* Authors: D|-cio Luiz Gazzoni Filho, Rafael G. Flores e Silva, Alessandro Budroni, Marco Palumbi, Gora Adj
* [Permalink](https://eprint.iacr.org/2025/1359)
* [Download](https://eprint.iacr.org/2025/1359.pdf)
### Abstract
One of the main guidelines to prevent timing side-channel attacks against cryptographic implementations is to avoid array accesses indexed by secret data. However, alternatives and countermeasures often incur significant performance losses. We propose a novel methodology for secure, constant-time implementation of algorithms that read and write to small arrays with secret-dependent indices, with a constant-factor performance impact compared to timing-unprotected accesses. It is specifically suitable for simple in-order CPUs like those in embedded systems, e.g., the ARM Cortex-M4 core. Although our methodology is general, we illustrate it with secure implementation of permutation operations, such as composition, inversion, and sampling, the latter using the Fisher-Yates shuffle. We apply this methodology to the post-quantum cryptosystems PERK and NTRU, bridging most of the performance gap to unprotected implementations that employ secret-dependent array accesses.
## 2025/1360
* Title: Towards more secure constructions of private set operation schemes
* Authors: Mojtaba Rfiee
* [Permalink](https://eprint.iacr.org/2025/1360)
* [Download](https://eprint.iacr.org/2025/1360.pdf)
### Abstract
A private set operation (PSO) scheme [Rafiee, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud storage, and then when needed, securely issue common set operation queries to the server and receive the results. In [Rafiee, Comput. J. 2020], the only security notion of the PSO schemes, named naSIM, is proposed. This security notion models a weak attacker who is far from the threats of practical environments, and providing stronger security notions has been raised as an open problem. In this paper, we propose a new security notion for the PSO schemes, called aIND, and show that this concept is stronger than naSIM. Furthermore, we propose a new PSO construction that satisfies the security notion aIND. We also show that our construction does not increase the computational and storage overheads compared to other existing constructions, despite covering a much higher level of security.
## 2025/1361
* Title: Exploring KanekorCOs bound: On multi-edges, loops and the diameter of the supersingular $\ell$-isogeny graph
* Authors: Sebastiano Boscardin, Sebastian A. Spindler
* [Permalink](https://eprint.iacr.org/2025/1361)
* [Download](https://eprint.iacr.org/2025/1361.pdf)
### Abstract
We analyze Kaneko's bound to prove that, away from the $j$-invariant $0$, edges of multiplicity at least three can occur in the supersingular $\ell$-isogeny graph $\mathcal{G}_\ell(p)$ only if the base field's characteristic satisfies $p < 4\ell^3$. Further we prove a diameter bound for $\mathcal{G}_\ell(p)$, while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko's bound to deduce that the distance of $0$ and $1728$ in $\mathcal{G}_\ell(p)$ is at least one fourth of the graph's diameter if $p \equiv 11 \mathrel{\operatorname{mod}} 12$. We also study other phenomena in $\mathcal{G}_\ell(p)$ with Kaneko's bound and provide data to demonstrate that the resulting bounds are optimal; for one of these bounds we investigate the connection between loop multiplicities in isogeny graphs and the factorization of the `diagonal' classical modular polynomial $\Phi_\ell(X,X)$ in positive characteristic.
## 2025/1362
* Title: Cryptanalysis of the best HFE-LL' Constructions
* Authors: Daniel Smith-Tone, Cristian Valenzuela
* [Permalink](https://eprint.iacr.org/2025/1362)
* [Download](https://eprint.iacr.org/2025/1362.pdf)
### Abstract
In the last few years, the old idea of internal perturbation for multivariate schemes has been resurrected. A form of this method was proposed with application to HFE and UOV and independently by another team for application to Rainbow. Most recently, a newer and more efficient version of internal perturbation was proposed as an enhanced measure for securing HFE for encryption.
This efficient method, known as the LL' construction, is designed to add little complexity to HFE decryption while increasing the rank of the resulting map to resist the now very effective cryptanalyses powered by MinRank. The basic idea of the construction is to have two small lists of binary linear forms which when multiplied produce rank $1$ quadratic forms. Random linear combinations of these products are then added to each of the HFE equations, resulting in a masked HFE. The main trick to make the scheme usable is to encrypt an send many random messages so that statistically it is likely that the legitimate user can find a ciphertext that is not perturbed by the construction and which may be decrypted as a plain HFE ciphertext.
We show that this approach is not secure. In particular, we present a method to recover the noise support, a collection of quadratic forms spanning the set of LL' quadratic forms. We then are able to filter out the effect of these maps to recover a compatible HFE map. Finally, we are able to complete the key recovery, achieving efficiently an equivalent private key.
## 2025/1363
* Title: Universally Composable Adaptor Signatures
* Authors: Paul Gerhart, Daniel Rausch, Dominique Schr||der
* [Permalink](https://eprint.iacr.org/2025/1363)
* [Download](https://eprint.iacr.org/2025/1363.pdf)
### Abstract
Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations.
Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message.
Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme.
Since adaptor signatures are commonly used as building blocks in larger systemsrCosuch as blockchain protocolsrCoit is natural to seek a security definition within the Universal Composability (UC) framework.
A recent attempt by Tairi et al. (CCS'23) introduced the first UC functionality for adaptor signatures.
This paper makes both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations:
- The functionality fails to guarantee extractability and adaptabilityrCothe core security properties of adaptor signaturesrCoto higher-level protocols.
- No adaptor signature scheme can realize the functionality.
On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT'24).
- Our functionality guarantees extractability, unique extractability, and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols.
- We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments.
## 2025/1364
* Title: A Framework for Witness Encryption from Linearly Verifiable SNARKs and Applications
* Authors: Sanjam Garg, Mohammad Hajiabadi, Dimitris Kolonelos, Abhiram Kothapalli, Guru-Vamsi Policharla
* [Permalink](https://eprint.iacr.org/2025/1364)
* [Download](https://eprint.iacr.org/2025/1364.pdf)
### Abstract
Witness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness encryption schemes, there has been no systematic study of special purpose witness encryption schemes.
In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and further enables us to construct new witness encryption schemes. The framework is designed around simple but powerful building blocks that we refer to as "gadgets". Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger, more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results.
The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have introduced though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being N^{1.58} (Garg et al. [GLWW, CRYPTO 24]). Empowered by our Witness Encryption framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership.
Our second application is a feasibility result for Registered Threshold Encryption (RTE) with succinct ciphertexts. RTE (Branco et al. [ASIACRYPT 2024] is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, CRYPTO 24]) in the Registered Setting. We revisit Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework.
--- Synchronet 3.21a-Linux NewsLink 1.2