From Newsgroup: sci.crypt

## In this issue
1. [2025/1004] On Factoring and Power Divisor Problems via Rank-3 ...
2. [2025/1493] Revisit the Boyar-Peralta Algorithm to Solve the ...
3. [2025/2064] Security of Private Set Operation Schemes: ...
4. [2025/2065] TensorSwitch: Nearly Optimal Polynomial Commitments ...
5. [2025/2066] A Comprehensive Analysis of the AKMA+ Protocol
6. [2025/2067] Cryptographic Binding Should Not Be Optional: A ...
7. [2025/2068] Fast Networks for High-Performance Distributed Trust
8. [2025/2069] Shorter Hash-Based Signatures Using Forced Pruning
9. [2025/2070] MIFA: An MILP-based Framework for Improving ...
10. [2025/2071] On Cryptography and Distribution Verification, with ...
11. [2025/2072] Multi-server Fuzzy Message Detection
12. [2025/2073] Recursion Enabled: Improved Cryptanalysis of the ...
13. [2025/2074] VIA: Communication-Efficient Single-Server Private ...
14. [2025/2075] Leveled Isogeny Problems with Hints
15. [2025/2076] Non-Interactive Blind Signatures from RSA ...
16. [2025/2077] Malicious Homomorphic Secret Sharing with ...
17. [2025/2078] Broadcast for Dynamic Committees without Trusted Setup
18. [2025/2079] On the Dangers of RSA Exponent Transforms
19. [2025/2080] Issuer Hiding for BBS-Based Anonymous Credentials
20. [2025/2081] Partial Fraction Techniques for Cryptography
21. [2025/2082] Integrating PQC in OpenSSL via Shallow Providers ...
22. [2025/2083] Improvements to Lucas-sequence modular square roots ...
23. [2025/2084] Postponing the Glitches is Not Enough - A Critical ...
24. [2025/2085] Strong Pseudorandom Functions in $AC^0[2]$ in the ...
25. [2025/2086] On Composing AGM-Secure Functionalities with ...
26. [2025/2087] Leakage-Free Enhanced Private Set Union for ...
27. [2025/2088] UP TO 50% OFF: Efficient Implementation of ...
28. [2025/2089] Traceable Bottom-Up Secret Sharing and Law & Order ...
29. [2025/2090] Quantum Grover Attack on MIBS
30. [2025/2091] Efficient and Proof-of-Useful-Work Friendly Local- ...
31. [2025/2092] CRA and Cryptography: The Story Thus Far
32. [2025/2093] Lore: An LWE-based Key Encapsulation Mechanism with ...
33. [2025/2094] Vega: Low-Latency Zero-Knowledge Proofs over ...
34. [2025/2095] FPS: Flexible Payment System
35. [2025/2096] Laser Fault Injection Attack on the eXtended Merkle ...
36. [2025/2097] Hash-Based Blind Signatures: First Steps
37. [2025/2098] Optical computing of zero-knowledge proof with ...
38. [2025/2099] A Lattice-based Designated Verifier zkSNARK from ...
39. [2025/2100] Tag Functions and Their Applications to Lattice- ...
40. [2025/2101] Fault Attacks against UOV-based Signatures
41. [2025/2102] A Graph-Theoretic Framework for Randomness ...
42. [2025/2103] Threshold Batched Identity-Based Encryption from ...
43. [2025/2104] Quantum Voting Protocol from Classical Assumption
44. [2025/2105] A Lattice-Based Puncturable Attribute-Based Proxy ...
45. [2025/2106] SoK: Blockchain Oracles Between Theory and Practice
46. [2025/2107] Quantum-safe Identity-binding Password ...
## 2025/1004
* Title: On Factoring and Power Divisor Problems via Rank-3 Lattices and the Second Vector
* Authors: Yiming Gao, Yansong Feng, Honggang Hu, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2025/1004)
* [Download](https://eprint.iacr.org/2025/1004.pdf)
### Abstract
We propose a deterministic algorithm based on Coppersmith's method that employs a rank-3 lattice to address factoring-related problems. An interesting aspect of our approach is that we utilize the second vector in the LLL-reduced basis to avoid trivial collisions in the Baby-step Giant-step method, rather than the shortest vector as is commonly used in the literature. Our results are as follows:
- Compared to the result by Harvey and Hittmeir (Math. Comp. 91 (2022), 1367rCo1379), who achieved a complexity of $O\left( \frac{N^{1/5} \log^{16/5} N}{(\log \log N)^{3/5}} \right)$ for factoring a semiprime $N = pq$, we demonstrate that in the balanced $p$ and $q$ case, the complexity can be improved to $O\left( \frac{N^{1/5} \log^{13/5} N}{(\log\log N)^{3/5}} \right).$
- For factoring sums and differences of powers, i.e., numbers of the form $N = a^n \pm b^n$, we improve Hittmeir's result (Math. Comp. 86 (2017), 2947rCo2954) from $O(N^{1/4} \log^{3/2} N)$ to $O\left( {N^{1/5} \log^{13/5} N} \right).$
- For the problem of finding $r$-power divisors, i.e., finding all integers $p$ such that $p^r \mid N$, Harvey and Hittmeir (Proceedings of ANTS XV, Res. Number Theory 8 (2022), no.4, Paper No. 94) recently directly applied Coppersmith's method and achieved a complexity of $O\left(\frac{N^{1/4r} \log^{10+\epsilon} N}{r^3}\right)$. By using faster LLL-type algorithm and sieving on small primes, we improve their result to $O\left(\frac{N^{1/4r} \log^{7+3\epsilon} N}{(\log\log N-\log 4r)r^{2+\epsilon}}\right)$. The worst case running time for their algorithm occurs when $N = p^r q$ with $q = \Theta(N^{1/2})$. By focusing on this case and employing our rank-3 lattice approach, we achieve a complexity of $O\left(r^{1/4} N^{1/4r} \log^{5/2} N \right)$.
In conclusion, we offer a new perspective on these problems, which we hope will provide further insights.
## 2025/1493
* Title: Revisit the Boyar-Peralta Algorithm to Solve the Shortest Linear Program Problem
* Authors: Yao Sun, Runhe Yang, Ting Li
* [Permalink](https://eprint.iacr.org/2025/1493)
* [Download](https://eprint.iacr.org/2025/1493.pdf)
### Abstract
The efficiency of circuit implementations for cryptographic algorithms is crucial for their practical deployment. The implementation cost of the linear layer can be evaluated by the number of XOR operations, typically measured in generalized XOR (g-\xor) and serial XOR (s-XOR). Finding the minimal sequence of g-XOR operations constitutes the Shortest Linear Program (SLP) problem. Existing approaches generally address this problem through a two-stage framework: generating an initial sequence followed by local optimization, both stages essentially solving the SLP problem. The Boyar-Peralta (BP) algorithm serves as a foundational heuristic for addressing the SLP problem and has been extensively adopted in subsequent research; however, its computational inefficiency presents a significant limitation for practical applications, especially in large-scale problems.
This paper proposes a novel implementation framework for the BP algorithm based on linear combinations, significantly enhancing its computational efficiency. We further introduce a new strategy for selecting subsequences during local optimization, replacing the random selection strategy employed in previous works. By analyzing the structural properties of the Advanced Encryption Standard (AES) linear layer matrix and applying our proposed methods, we achieve the first implementation requiring only 89 g-XOR operations, improving upon the previous best result of 91 g-XOR operations reported in prior literature.
## 2025/2064
* Title: Security of Private Set Operation Schemes: Separations and Implications
* Authors: Mojtaba Rafiee
* [Permalink](https://eprint.iacr.org/2025/2064)
* [Download](https://eprint.iacr.org/2025/2064.pdf)
### Abstract
The private set operation (PSO) scheme [Rafiee-Khazaei, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud server, and then when needed, securely issue common set operation queries to the server and receive the results. This primitive has always been of interest to researchers because it supports set operations, which are the most basic mathematical operations and are used in a wide range of real-world applications. In previous research, security notions such as: naSIM and aIND have been introduced for it. In this paper, we develop the standard security notions for PSO schemes: an adaptive version of simulation-based security notion (aSIM) and a non-adaptive version of indistinguishability-based security notion (naIND). We also study the relation between these security notions and determine their implications and separations. In addition to these, we also provide a summary of the available PSO constructions and their security level, and introduce research potentials in this regard.
## 2025/2065
* Title: TensorSwitch: Nearly Optimal Polynomial Commitments from Tensor Codes * Authors: Benedikt B|+nz, Giacomo Fenzi, Ron D. Rothblum, William Wang
* [Permalink](https://eprint.iacr.org/2025/2065)
* [Download](https://eprint.iacr.org/2025/2065.pdf)
### Abstract
A polynomial commitment scheme (PCS) enables a prover to succinctly commit to a large polynomial and later generate evaluation proofs that can be efficiently verified. In recent years, PCSs have emerged as a central focus of succinct non-interactive argument (SNARG) design.
We present TensorSwitch, a hash-based PCS for multilinear polynomials that improves the state-of-the-art in two fundamental bottlenecks: prover time and proof size.
We frame our results as an interactive oracle PCS, which can be compiled into a cryptographic PCS using standard techniques. The protocol uses any linear code with rate $\rho$, list-decoding and correlated agreement up to $\delta$, and encoding time $\tau \cdot \ell$, where $\ell$ is the block length. For a size $n$ polynomial, security parameter $\lambda$, and sufficiently large field, it has the following efficiency measures, up to lower order terms:
- Commitment time: $(\tau/\rho^{2} + \tau/\rho + 3) \cdot n$ field multiplications.
- Opening time: $6 n$ field multiplications.
- Query complexity: $\frac{1}{-\log(1-\delta^{2})} \cdot \lambda$.
- Verification time: $O(\lambda \log n)$.
Moreover, the evaluation proof only contains $O(\log \log n)$ oracles of total size $(\lambda n)^{0.5 + o(1)}$.
With a Reed-Solomon code of rate $1/2$, the query complexity is $2.41 \lambda$ and commitment time is dominated by $(6 \log n + 3) \cdot n$ field multiplications. With an RAA code of rate $1/4$ and distance $0.19$, the query complexity is $19 \lambda$ and the commitment time is $42 n$ field additions and $3 n$ field multiplications. For both instantiations, the opening time is dominated by $6 n$ field multiplications.
## 2025/2066
* Title: A Comprehensive Analysis of the AKMA+ Protocol
* Authors: Yueming Li, Long Chen, Zhenfeng Zhang
* [Permalink](https://eprint.iacr.org/2025/2066)
* [Download](https://eprint.iacr.org/2025/2066.pdf)
### Abstract
With the rapid advancement of 5G networks and the increasing demand for secure application access, the Authentication and Key Management for Applications (AKMA) framework was developed by the 3rd Generation Partnership Project (3GPP) to provide unified authentication and key management for diverse 5G services. In response to the security and privacy concerns identified in the current AKMA protocol, as outlined in 3GPP TR 33.835, Yang et al. proposed an enhanced, standard-compatible 5G AKMA protocol known as AKMA+[14].
This paper presents a comprehensive analysis of AKMA+, discovering two critical vulnerabilities: (1) the compromise of the AKMA Anchor Function (AAnF), which enables adversaries to impersonate legitimate users; and (2) the persistent storage of multiple anchor keys, which heightens the risk of key exposure. These vulnerabilities arise from the reliance on the authentication framework inherent in existing AKMA+ models. This architectural dependency introduces fundamental security risks that cannot be adequately mitigated through incremental modifications to the current design.
Furthermore, we observe that AKMA+ faces challenges in aligning with the standard account-based authentication model, which is incompatible with existing user practices within information systems. Additionally, we find that providing account-based authentication functionality without compromising privacy poses significant difficulties.
## 2025/2067
* Title: Cryptographic Binding Should Not Be Optional: A Formal-Methods Analysis of FIDO UAF Channel Binding
* Authors: Enis Golaszewski, Alan T. Sherman, Edward Zieglar, Jonathan D. Fuchs, Sophia Hamer
* [Permalink](https://eprint.iacr.org/2025/2067)
* [Download](https://eprint.iacr.org/2025/2067.pdf)
### Abstract
As a case study in cryptographic binding, we present a formal-methods analysis of
the cryptographic channel binding mechanisms in the
Fast IDentity Online (FIDO) Universal Authentication Framework (UAF) authentication protocol, which
seeks to reduce the use of traditional passwords in favor of authentication devices.
First, we show that UAF's channel bindings fail to mitigate protocol interaction
by a Dolev-Yao adversary, enabling the adversary to transfer the server's authentication challenge to alternate sessions of the protocol.
As a result, in some contexts, the adversary can masquerade as
a client and establish an authenticated session with a server (e.g., possibly a bank server).
Second, we implement a proof-of-concept man-in-the-middle attack against eBay's open source FIDO UAF implementation.
Third, we propose and formally verify improvements to UAF.
The weakness we analyze is similar to the vulnerability discovered in the Needham-Schroeder protocol over 25 years ago.
That this vulnerability appears in the FIDO UAF standard
highlights the strong need for protocol designers to bind messages properly and to analyze their designs with formal-methods tools.
To our knowledge, we are first to carry out a formal-methods analysis of channel binding in UAF and first to exhibit details of an attack on UAF that exploits the weaknesses of UAF's channel binding.
Our case study illustrates the importance of cryptographically binding context to protocol messages to prevent an adversary from misusing messages out of context.
## 2025/2068
* Title: Fast Networks for High-Performance Distributed Trust
* Authors: Yicheng Liu, Rafail Ostrovsky, Scott Shenker, Sam Kumar
* [Permalink](https://eprint.iacr.org/2025/2068)
* [Download](https://eprint.iacr.org/2025/2068.pdf)
### Abstract
Organizations increasingly need to collaborate by performing a computation on their combined dataset, while keeping their data hidden from each other. Certain kinds of collaboration, such as collaborative data analytics and AI, require a level of performance beyond what current cryptographic techniques for distributed trust can provide. This is because the organizations run software in different trust domains, which can require them to communicate over WANs or the public Internet. In this paper, we explore how to instead run such applications using fast datacenter-type LANs. We show that, by carefully redesigning distributed trust frameworks for LANs, we can achieve up to order-of-magnitude better performance than na|>vely using a LAN. Then, we develop deployment models for Distributed But Proximate Trust (DBPT) that allow parties to use a LAN while remaining physically and logically distinct. These developments make secure collaborative data analytics and AI significantly more practical and set new research directions for developing systems and cryptographic theory for high-performance distributed trust.
## 2025/2069
* Title: Shorter Hash-Based Signatures Using Forced Pruning
* Authors: Mehdi Abri, Jonathan Katz
* [Permalink](https://eprint.iacr.org/2025/2069)
* [Download](https://eprint.iacr.org/2025/2069.pdf)
### Abstract
The stateless hash-based digital signature algorithm (SLH-DSA) is a post-quantum signature scheme based on the SPHINCS+ framework that was recently standardized by NIST. Although it offers many benefits, a drawback of SLH-DSA is that it has relatively large signatures. Several techniques have been proposed to reduce the signature size of SPHINCS-like schemes, and NIST is actively evaluating variants with shorter signatures for possible future standardization.
We explore using forced pruning in the few-time signature scheme used by SPHINCS+ to reduce the overall signature size. Prior work suggested similar ideas, but claimed that the improvement from forced pruning was small.
We re-visit this conclusion by performing a detailed theoretical analysis of forced pruning along with a more thorough exploration of its benefits.
We show that forced pruning can improve upon SPHINCS+C (Oakland 2023) in all respects, and can reduce the overall signature size for the ''smaller SPHINCS+'' variants proposed by Fluhrer and Dang by up to 20% with minimal effect on signing time. Our results thus show that forced pruning can be a beneficial optimization for hash-based signatures.
## 2025/2070
* Title: MIFA: An MILP-based Framework for Improving Differential Fault Attacks * Authors: Hanbeom Shin, Insung Kim, Sunyeop Kim, Byoungjin Seok, Dongjae Lee, Deukjo Hong, Jaechul Sung, Seokhie Hong, Sangjin Lee
* [Permalink](https://eprint.iacr.org/2025/2070)
* [Download](https://eprint.iacr.org/2025/2070.pdf)
### Abstract
At ASIACRYPT 2021, Baksi et al. introduced DEFAULT, a block cipher designed to algorithmically resist Differential Fault Attack (DFA), claiming 64-bit DFA security regardless of the number of injected faults. At EUROCRYPT 2022, Nageler et al. demonstrated that DEFAULTrCOs claimed DFA resistance can be broken by applying an information-combining technique. More recently, at ASIACRYPT 2024, Jana et al. improved DFA by searching for deterministic trails. They showed that, for DEFAULT with a simple key schedule, injecting five faults at the fifth-to-last round reduces the key space to one, and for BAKSHEESH, injecting twelve faults at the third-to-last round achieves the same result. In this paper, we propose a new DFA framework that utilizes a MixedInteger Linear Programming (MILP) solver. This framework makes it possible to attack more rounds than previously achieved, while simultaneously reducing the number of fault injections required for key recovery. Furthermore, we present a method to determine the most efficient fault injection bit positions by systematically analyzing the input differences from all possible single bit-flip faults, thereby further reducing the required number of faults. This systematic analysis has the significant advantage of allowing us to theoretically calculate the required number of faults. Applying our framework, for DEFAULT, injecting three faults at the sixth-to-last round and two faults at the seventh- and eighth-tolast rounds reduces the key space to one, and for BAKSHEESH, injecting six faults at the fourth-to-last round and nine faults at the fifth-to-last round achieves the same result.
## 2025/2071
* Title: On Cryptography and Distribution Verification, with Applications to Quantum Advantage
* Authors: Bruno Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Tomoyuki Morimae
* [Permalink](https://eprint.iacr.org/2025/2071)
* [Download](https://eprint.iacr.org/2025/2071.pdf)
### Abstract
One of the most fundamental problems in the field of hypothesis testing is the identity testing problem: whether samples from some unknown distribution $\mathcal{G}$ are actually from some explicit distribution $\mathcal{D}$. It is known that when the distribution $\mathcal{D}$ has support $[N]$, the optimal sample complexity for the identity testing problem is roughly $O(\sqrt{N})$. However, many distributions of interest, including those which can be sampled efficiently, have exponential support size, and therefore the optimal identity tester also requires exponential samples. In this paper, we bypass this lower bound by considering restricted settings. The above $O(\sqrt{N})$ sample complexity identity tester is constructed so that it is not fooled by any (even inefficiently-sampled) distributions. However, in most applications, the distributions under consideration are efficiently samplable, and therefore it is enough to consider only identity testers that are not fooled by efficiently-sampled distributions. In this setting we can hope to construct efficient identity testers. We investigate relations between efficient verification of classical/quantum distributions with classical/quantum cryptography, showing the following results:
\begin{itemize}
\item Classically efficiently samplable distributions are verifiable if and only if one-way functions do not exist.
\item Quantumly efficiently samplable distributions are verifiable by $\mathbf{P}^\mathbf{PP}$ with a polynomial number of samples.
\item Sampling-based quantum advantage can be verified quantumly (with a polynomial number of samples) if one-way puzzles do not exist.
\item If QEFID pairs exist, then some quantumly efficiently samplable distributions are not verifiable.
\end{itemize}
## 2025/2072
* Title: Multi-server Fuzzy Message Detection
* Authors: Christopher Goes, Yulia Khalniyazova, Enrique Larraia, Xuyang Song
* [Permalink](https://eprint.iacr.org/2025/2072)
* [Download](https://eprint.iacr.org/2025/2072.pdf)
### Abstract
Fuzzy Message Detection, or FMD, outsources detection of messages to an untrusted server, Beck et. al. CCS 2021. In this paper, we extend FMD to the multi-key setting: several servers are given different detection keys, all extracted from a single secret key. Multi-key FMD allows to combine tests from multiple servers locally by each receiver. This allows to set high false-positive rates on the servers, while attaining low rates on the receiver side. Striking this way a better balance between privacy and efficiency. We further formalize the notion of stealth public keys in the FMD setting. Last, we provide two constructions, one with short public keys.
## 2025/2073
* Title: Recursion Enabled: Improved Cryptanalysis of the Permuted Kernel Problem
* Authors: Alessandro Budroni, Marco Defranceschi, Federico Pintore
* [Permalink](https://eprint.iacr.org/2025/2073)
* [Download](https://eprint.iacr.org/2025/2073.pdf)
### Abstract
The Permuted Kernel Problem (PKP) is a computational problem for linear codes over finite fields that has emerged as a promising hard problem for constructing post-quantum cryptographic schemes, with its main application found in the digital signature scheme PERK, submitted to the NIST standardization process for quantum-secure additional signatures. Upon reviewing the first version of PERK, NIST recommended further research on the concrete complexity of PKP.
In this work, we follow this recommendation and investigate algorithmic improvements to the known methods for solving PKP. Specifically, we build upon the state-of-the-art work of Santini, Baldi, and Chiaraluce (IEEE Trans. Inf. Theory, 2024), and introduce a new algorithm that outperforms it over a wide range of parameters, yielding double-digit bit reductions in estimated complexity on representative instances. Nevertheless, our analysis shows that these improvements do not affect the parameter-set choices in PERK, thereby reinforcing confidence in its security.
## 2025/2074
* Title: VIA: Communication-Efficient Single-Server Private Information Retrieval
* Authors: Chenyang Liu, Xukun Wang, Zhifang Zhang
* [Permalink](https://eprint.iacr.org/2025/2074)
* [Download](https://eprint.iacr.org/2025/2074.pdf)
### Abstract
Private Information Retrieval (PIR) is a crucial component in many privacy-preserving systems, with Offline/Online PIR attracting significant attention. Recent works have focused on eliminating offline communication overhead. However, existing constructions incur high online communication costs as a trade-off. To address this, we propose VIA, a single-server PIR scheme that eliminates offline communication while achieving $O{_\lambda}(\log N)$ online communication complexity. Experimental evaluations demonstrate that for a 32 GB database, VIA requires only 690 KB of online communication---a $3.7\times$ reduction compared to state-of-the-art schemes without offline communication---while attaining a throughput of 3.11 GB/s. Furthermore, we introduce VIA-C, a variant of VIA that allows offline communication. Compared to previous communication-efficient schemes, VIA-C achieves a $24.5\times$ reduction in online communication, requiring only 2.1 KB for a 32 GB database (with 14.8 MB offline communication). Moreover, VIA-C can naturally extend to VIA-B that supports batch queries. Compared to previous communication-efficient batch PIR schemes, VIA-B achieves a $3.5\times$ reduction in query size and a $127\times$ reduction in response size for a 1 GB database of 1-byte records. The designs of our schemes rely on a novel DMux-CMux structure and LWE-to-RLWE conversion techniques.
## 2025/2075
* Title: Leveled Isogeny Problems with Hints
* Authors: Subham Das, Riccardo Invernizzi, P|-ter Kutas, Jonas Meers
* [Permalink](https://eprint.iacr.org/2025/2075)
* [Download](https://eprint.iacr.org/2025/2075.pdf)
### Abstract
We define and analyze the Leveled Isogeny Problem with
Hints (LIPH), which is a generalization of the Isogeny Problem with Level Structure first introduced by De Feo, Fuoutsa and Panny at EUROCRYPT'24. In a LIPH instance we are tasked to recover a secret isogeny \(\varphi\) given masked torsion point images \(\Gamma\cdot(\varphi(P),\varphi(Q))^\top\) for some \((P,Q)\) of order \(N\) and unknown \(\Gamma\in GL_2(N)\). Additionally, we are provided a \emph{hint} on \(\Gamma\), revealing some bits of its entries. Instances of LIPH occur naturally in the case of modern isogeny-based key exchanges that use masked torsion points as part of their public key, when additionally some parts of the masking matrix \(\Gamma\) are revealed due to, for instance, a side-channel attack.
We provide efficient algorithms that solve various instances of LIPH, leading to efficient \emph{partial key recovery attacks} in practice. More specifically, we present Coppersmith-type attacks that are able to recover an M-SIDH/POK|e secret key given \(50\%\) (resp. \(86\%\)) of the most-significant bits of an entry of \(\Gamma\), and a FESTA secret key given the 67\% of the most-significant bits of \(\Gamma\).
In the case of FESTA we also present a tailored combinatorial attack running in subexponential time $O(2^{\sqrt{n}})$ when $50\%$ of the bits of $\Gamma$ leak at random.
## 2025/2076
* Title: Non-Interactive Blind Signatures from RSA Assumption and More
* Authors: Lucjan Hanzlik, Eugenio Paracucchi, Riccardo Zanotto
* [Permalink](https://eprint.iacr.org/2025/2076)
* [Download](https://eprint.iacr.org/2025/2076.pdf)
### Abstract
Blind signatures have received increased attention from researchers and practitioners. They allow users to obtain a signature under a message without revealing it to the signer. One of the most popular applications of blind signatures is to use them as one-time tokens, where the issuing is not linkable to the redeeming phase, and the signature under a random identifier forms a valid token. This concept is the backbone of the Privacy Pass system, which uses it to identify honest but anonymous users and protect content delivery networks from botnets.
Non-interactive blind signatures for random messages were introduced by Hanzlik (Eurocrypt'23). They allow a signer to create a pre-signature with respect to a particular public key, while the corresponding secret key can later be used to finalize the signature. This non-interaction allows for more applications than in the case of blind signatures. In particular, the author suggested using regular PKI keys as the recipient public key, allowing for a distribution of one-time tokens to users outside the system, e.g., to public keys of GitHub users, similar to airdropping of cryptocurrencies. Unfortunately, despite introducing this concept, the paper fails to provide schemes that work with keys used in the wild.
We solve this open problem. We introduce a generic construction of non-interactive blind signatures that relies on Yao's garbled circuit techniques and provide particular improvements to this generic setting. We replace oblivious transfer with their non-interactive variant and show how to construct them so that the recipient's public key, encoding the $\mathsf{OT}$ choice, is a standard RSA public key $(e,N)$. To improve the efficiency of the garbling, we show how to garble the signing algorithm of the pairing-based Pointcheval-Sanders (PS) signatures and the RSA-based signature scheme with efficient protocols by Camenisch and Lysyanskaya. Our technique also apply to the well-known BBS signatures. All our improvements are of independent interest and are central to our contribution.
## 2025/2077
* Title: Malicious Homomorphic Secret Sharing with Applications to DV-NIZK and More
* Authors: Pedro Capit|uo, Hila Dahari-Garbian, Lisa Kohl, Zhe Li
* [Permalink](https://eprint.iacr.org/2025/2077)
* [Download](https://eprint.iacr.org/2025/2077.pdf)
### Abstract
Homomorphic Secret Sharing (CRYPTO 2016) allows a secret to be shared among two or more parties in such a way that the parties can locally evaluate a class of functions on their shares. Homomorphic secret sharing (HSS) schemes and their underlying techniques have facilitated a wide range of applications. To account for the fact that parties generating or evaluating the shares might act maliciously, variants of HSS schemes that allow detection of such malicious behavior have been introduced. However, all prior approaches of malicious HSS that capture the class of $\mathsf{NC}1$ circuits either crucially rely on a random oracle or require an non-reusable setup.
In this work, we initiate the study of malicious public-key $2$-party HSS in the standard model with reusable setup, where any malicious behavior during share generation and share evaluation can be detected. Towards constructing malicious HSS, we introduce the notion of homomorphic secret sharing with robust linear reconstruction (RLR-HSS) and show that this notion readily implies malicious HSS. We outline challenges in instantiating RLR-HSS due to the error present in all current HSS constructions not relying on SHE/FHE, and show how to overcome these using derandomization techniques by Dwork et al. (EUROCRYPT 2004). Finally, we show applications of malicious HSS to compact designated verifier non-interactive zero knowledge arguments and maliciously secure $2$-party computation in the standard model (supporting the same function class as the underlying malicious HSS).
## 2025/2078
* Title: Broadcast for Dynamic Committees without Trusted Setup
* Authors: Gabriel Dettling, Chen-Da Liu-Zhang, Elisaweta Masserova, Matthieu Rambaud, Antoine Urban
* [Permalink](https://eprint.iacr.org/2025/2078)
* [Download](https://eprint.iacr.org/2025/2078.pdf)
### Abstract
A significant number of works have considered the problem of multi-party computation over dynamic committees in synchronous networks, including YOSO MPC [Crypto'21], Fluid MPC [Crypto'21], SCALES MPC [TCC'22] and Layered MPC [Crypto'23]. However, prior works assume that every party has access to an ideal synchronous broadcast channel towards the next committee.
While this assumption is partly justified due to the seminal work of Garay [WDAG'94] stating that deterministic broadcast with dynamic committees is impossible, it is open whether there are randomized solutions.
We answer this question in the affirmative, by providing a complete characterization of broadcast with dynamic committees. We use the formalization introduced in the Layered MPC setting and achieve the following results for layered broadcast:
- A $\textbf{statistically secure}$ protocol tolerating $t<n/3$ corruptions with no setup.
- A $\textbf{computationally secure}$ protocol tolerating $t<n/2$ corruptions, assuming only a plain PKI for signatures.
- A matching $\textbf{impossibility result}$ showing that broadcast is impossible for $t \geq n/2$ corruptions.
\end{itemize}
Using our broadcast protocols, we achieve the following results:

- The first YOSO MPC protocols without broadcast (statistical for $t<n/3$ without setup; and computational for $t<n/2$ assuming a plain PKI for signatures).
- Assuming plain PKIs for signatures and public-key encryption, the first Layered MPC protocol without broadcast for $t<n/2$.
- Assuming homomorphic commitments, the first Layered MPC as long as $(t+1)^2 \le n.$ To achieve this, we introduce a secure-message-transmission protocol for $(t+1)^2 \le n$ which has linear communication in $\ell$ and polynomial communication in $n$ when transmitting a message across $\ell$ layers. This result is of independent interest.
## 2025/2079
* Title: On the Dangers of RSA Exponent Transforms
* Authors: Eugene Lau, Laura Shea, Nadia Heninger
* [Permalink](https://eprint.iacr.org/2025/2079)
* [Download](https://eprint.iacr.org/2025/2079.pdf)
### Abstract
We analyze the security of RSA keys where the public exponent $e$ is larger than $\varphi(N)$. While nearly all real-world applications of RSA use a small set of pre-determined constant values for $e$, the literature contains a number of constructions involving large special-form exponents. Examples include proposed countermeasures against Wiener's attack on small RSA private exponents, exponent masking against side channels, a 2018 proposal by Joye and Michalevsky to extend the usefulness of hardware security modules, and a 2023 RSA blind signature construction by Amjad, Yeo, and Yung.
We give an efficient algorithm to factor an RSA modulus $N$ given an integer $a$ that is "close" to a multiple of $\varphi(N)$. That is, we can factor $N$ in polynomial time given $\varphi(N) < a \le N^{3/2}$ if there is an integer $y$ with $|y| \le a N^{-3/4}$ such that $a - y \equiv 0 \bmod \varphi(N)$. Our attack is a special case of Bl||mer and May's 2004 algorithm using Coppersmith's method that enables us to give stronger bounds for our application range of interest.
We instantiate our attack against several constructions and exhibit families of weak public exponents that do not appear to have been analyzed in the literature. In particular, the Joye and Michalevsky exponent transform permits full key recovery if used for small public exponents. While it is well known that RSA is vulnerable for small private exponent $d$, our work suggests that care must also be taken when generating large public exponents, or when publishing transformed exponents.
## 2025/2080
* Title: Issuer Hiding for BBS-Based Anonymous Credentials
* Authors: Jonathan Katz, Marek Sefranek
* [Permalink](https://eprint.iacr.org/2025/2080)
* [Download](https://eprint.iacr.org/2025/2080.pdf)
### Abstract
Anonymous credentials allow users to obtain credentials on various attributes, and then use those credentials to give unlinkable proofs about the values of some attributes without leaking anything about others. They have recently received interest from companies including Google, Apple, and Cloudflare, and are being actively evaluated both at the IETF and in the EU. Anonymous credentials based on BBS signatures are a leading candidate for standardization.
In some natural applications of anonymous credentials, it is beneficial to hide even the issuer of a credential, beyond revealing the fact that the issuer is in some pre-determined set specified by a verifier. Sanders and Traore recently showed a construction of such issuer-hiding anonymous credentials based on the Pointcheval-Sanders signature scheme.
In this work we show how to achieve issuer hiding for BBS-based anonymous credentials. Our construction satisfies a notion of everlasting issuer-hiding anonymity, and is unforgeable in the generic group model. It can be integrated into existing standards, and has several efficiency advantages compared to prior work.
## 2025/2081
* Title: Partial Fraction Techniques for Cryptography
* Authors: Charanjit S. Jutla, Rohit Nema, Arnab Roy
* [Permalink](https://eprint.iacr.org/2025/2081)
* [Download](https://eprint.iacr.org/2025/2081.pdf)
### Abstract
Partial fraction decomposition is a fundamental technique in mathematics where products of rational functions can be expressed as sums of fractions. While rational functions have been used in various cryptographic constructions, their rich algebraic structure has not been systematically explored as a direct foundation for building cryptographic primitives. In this work, we describe and exploit two key properties of partial fraction decomposition:
(1) the decomposition property itself, which enables efficient set membership testing, and (2) a novel linear independence property arising from the non-singularity of Cauchy matrices, which enables threshold cryptography.
We present two main applications. First, we construct a key-value commitment scheme where a dictionary is represented as a linear combination of partial fractions.
Our scheme achieves constant-size commitments (a single group element) and proofs, supports homomorphic updates enabling stateless operation, and provides efficient membership and non-membership proofs through simple pairing equations. We also introduce Credential-based Key-Value Commitments, where keys are registered via Boneh-Boyen signatures, enabling applications in permissioned settings.
Second, we construct a dynamic threshold encryption scheme leveraging the linear independence of partial fraction products. Our scheme achieves compact ciphertexts, supports public preprocessing of public keys to a succinct encryption key, enables dynamic threshold selection at encryption time, and provides robustness through share verification without random oracles.
In particular, we achieve the shortest CPA-secure ciphertext size of 3 group elements, given logarithmic size preprocessed encryption key.
We prove security of our constructions in the standard model under new $q$-type assumptions and establish their generic hardness in the generic bilinear group model. Our work demonstrates that working directly with the algebraic structure of rational fractions, rather than converting to polynomial representations, yields elegant and efficient cryptographic constructions with concrete advantages over prior work.
## 2025/2082
* Title: Integrating PQC in OpenSSL via Shallow Providers for Cryptographic Agility
* Authors: Akif Mehmood, Nicola Tuveri
* [Permalink](https://eprint.iacr.org/2025/2082)
* [Download](https://eprint.iacr.org/2025/2082.pdf)
### Abstract
The emergence of Cryptographically Relevant Quantum Computers (CRQCs) threatens traditional cryptographic systems, necessitating a transition to Post-Quantum Cryptography (PQC). OpenSSL 3.0 introduced `Providers`, enabling modular cryptographic integration.
This work presents the concept of a "shallow `Provider`", facilitating integration of external implementations, to achieve a higher degree of cryptographic agility.
`aurora`, which we introduce as an instance of the "shallow `Provider`" methodology, integrates standardized PQC algorithms in TLS 1.3 for both key establishment and authentication, to support the PQC transition.
It enhances cryptographic agility by allowing OpenSSL to dynamically adapt to evolving PQC standards and the rapidly evolving ecosystem of PQC implementations.
## 2025/2083
* Title: Improvements to Lucas-sequence modular square roots and primality testing
* Authors: Mike Hamburg
* [Permalink](https://eprint.iacr.org/2025/2083)
* [Download](https://eprint.iacr.org/2025/2083.pdf)
### Abstract
Lucas sequences are a helpful tool in mathematical and cryptographic calculations, providing in particular an efficient way to exponentiate in a quotient ring $R[x]/(x^2 - Px + Q)$. As with exponentiation in other finite rings and fields, we can use the periodic nature of these sequences to find roots of polynomials. Since they behave differently in the ring $\mathbb{Z}/N$ depending on whether $N$ is prime, Lucas sequences are also useful for primality testing. In this paper, we discuss improvements to Lucas-sequence algorithms for square roots and heuristic primality testing.
Our first application is modular square roots. It is straightforward to take square roots modulo primes $p\equiv \{3,5,7\}$ mod 8. When $p\equiv 1$ mod 8, and especially when $p-1$ is divisible by many powers of 2, M|+ller's algorithm and Kim-Koo-Kwon are attractive options. Both of these use Lucas sequences. Here we show how to simplify and speed up Kim-Koo-Kwon. We also show a variant on M|+ller's algorithm which works even when $p\equiv 3$ mod 4, which would be useful if $p$ were secret.
Our second application is heuristic primality testing. The Baillie-PSW primality test combines a strong Fermat test with a strong Lucas test. The recent Baillie-Fiori-Wagstaff variant strengthens Baillie-PSW. Here we show an improved variant, $\mathtt{SuperBFPSW}$, which is stronger than Baillie-Fiori-Wagstaff, but also faster than the original Ballie-PSW.
## 2025/2084
* Title: Postponing the Glitches is Not Enough - A Critical Analysis of the DATE 2024 E-ISW Masking Scheme
* Authors: Amir Moradi
* [Permalink](https://eprint.iacr.org/2025/2084)
* [Download](https://eprint.iacr.org/2025/2084.pdf)
### Abstract
The Enhanced ISW (E-ISW) masking scheme, recently proposed at DATE 2024, was introduced as a refinement to the classical ISW construction to restore provable security guarantees in hardware implementations affected by glitches. By enforcing input-complete gate evaluations through the use of artificial delays, E-ISW seeks to mitigate the glitch-induced leakage that compromises standard masking techniques. However, in this work, we demonstrate that this modification is fundamentally insufficient to ensure robust side-channel resistance in realistic hardware environments. We conduct a detailed analysis and present concrete examples where E-ISW fails to prevent information leakage, even when the prescribed countermeasures are correctly applied. These vulnerabilities arise due to deeper conceptual shortcomings in the design, particularly the absence of compositional reasoning about the interaction between glitches and masking. Our results show that the security claims of E-ISW do not hold in practice, and they expose critical limitations in relying on heuristic delay-based fixes without formal and compositional proofs of security. This study serves as a cautionary note for the cryptographic engineering community, emphasizing the necessity of rigorous validation when proposing enhancements to established secure computation techniques.
## 2025/2085
* Title: Strong Pseudorandom Functions in $AC^0[2]$ in the Bounded-Query Setting
* Authors: Marshall Ball, Cl|-ment Ducros, Saroja Erabelli, Lisa Kohl, Nicolas Resch
* [Permalink](https://eprint.iacr.org/2025/2085)
* [Download](https://eprint.iacr.org/2025/2085.pdf)
### Abstract
Understanding the minimal computational power needed to realize a pseudorandom function (PRF) is a long-standing question in cryptography. By the RazborovrCoSmolensky polynomial approximation method, it is known that $AC^0[2]$ cannot support strong pseudorandom functions with subexponential security, since any such function can be distinguished from random with quasipolynomially many samples.
In this work, we initiate the study of low-complexity strong PRFs under a refined framework that separates adversary query complexity from running time, and observe that distinguishing algorithms for $AC^0[2]$ do not apply if the number of queries is below the threshold implied by the RazborovrCoSmolensky approximation bound.
We propose the first candidate strong PRF in $AC^0[2]$, which plausibly offers subexponential security against adversaries limited to a fixed quasipolynomial number of queries.

We show that our candidate lacks heavy Fourier coefficients, resists a natural class of adaptive attacks, has high rational degree, is non-sparse over $\mathbb{F}_2$ in expectation, and has low correlation with fixed function families.
Finally, we show that if any strong PRF exists in $AC^0[2]$ (or a superclass), then we can construct a universal PRF, i.e., a single, fixed function which is guaranteed to be a strong PRF in the same class.
## 2025/2086
* Title: On Composing AGM-Secure Functionalities with Cryptographic Proofs: Applications to Unbounded-Depth IVC and More
* Authors: Matteo Campanelli, Dario Fiore, Mahak Pancholi
* [Permalink](https://eprint.iacr.org/2025/2086)
* [Download](https://eprint.iacr.org/2025/2086.pdf)
### Abstract
Cryptographic proofs are a versatile primitive. They are useful in practice not only when used as a standalone tool (for example in verifiable computation), but also when applied $\textit{on top}$ of other cryptographic functionalities rCo hash functions, signature schemes, and even proofs themselves rCo to $\textit{enhance}$ their security guarantees (for example to provide succinctness). However, when the security of the other primitive is established in the Algebraic Group Model (AGM), the security of the resulting construction does not follow automatically.
We introduce a general methodology of $\textit{provable security}$ for this setting. Our approach guarantees the security of $\Pi \circ X$, the composition of a cryptographic proof $\Pi$ with a functionality $X$, whenever the security of $X$ is analysed in the AGM. Our methodology has general applicability, with immediate relevance to IVC, proof aggregation, and aggregate signatures. We obtain:
- $\textbf{IVC for unbounded depth from AGM-secure proofs.}$ Incrementally Verifiable Computation (IVC) is a canonical example of composing cryptographic proofs with one another. Achieving provable security for IVC beyond constant-depth computations has remained a central open challenge. Using our methodology, we obtain new IVC instantiations that remain secure for unbounded-depth computations, when built from proofs analysed in the AGM. This broadens the class of proofs systems usable in the canonical IVC constructions to include prominent systems such as Groth16 and Marlin rCo proof systems not covered by prior analyses (e.g., Chiesa et al., TCC 2024).
- $\textbf{Succinct aggregation of AGM-secure signatures.}$ Applying our framework, we give the first provable security for the folklore proof-based construction of aggregate signatures from AGM-secure signatures. Prior analyses either exclude AGM-secure signatures or rely on heuristic assumptions. Establishing this result required resolving additional technical challenges beyond applying our framework rCo for example, reasoning about the security of proof systems in the presence of signing oracles.
## 2025/2087
* Title: Leakage-Free Enhanced Private Set Union for Balanced and Unbalanced Scenarios
* Authors: Qiang Liu, JaeYoung Bae, JoonWoo Lee
* [Permalink](https://eprint.iacr.org/2025/2087)
* [Download](https://eprint.iacr.org/2025/2087.pdf)
### Abstract
Private Set Union (PSU) enables two parties to compute the union of their input sets without revealing anything else. Depending on set sizes, PSU is studied in balanced and unbalanced settings. Tu et al. (USENIX Security 2025) presented state-of-the-art enhanced PSU (ePSU) protocols under a unified framework in both settings, achieving enhanced security by preventing during-execution leakage. However, we observe that directly applying hash-to-bin on input sets within their framework introduces potential privacy risks. Moreover, the communication of their unbalanced ePSU still scales with the larger set size, rather than being linear in only the smaller set size. In this work, we address these open problems.
We employ a combination of oblivious pseudorandom function (OPRF) and shuffling to mitigate the potential privacy leakage that arises when directly applying the hash-to-bin within the framework of Tu et al. (USENIX Security 2025). Building upon this, we further optimize their balanced ePSU protocol by leveraging a bidirectional oblivious key-value store (OKVS). Compared with the corrected version of Tu et al.'s balanced ePSU, ours achieves a $1.1-3.0\times$ shrinking in communication and a $1.2-1.6\times$ speedup in runtime.
We design the first unbalanced ePSU whose communication is linear solely in the smaller set size. Since no hash-to-bin is used, it is inherently free from the associated privacy leakage. With the smaller set size fixed at $2^{10}$, ours reduces communication by $1.5-45.8\times$ compared with corrected version of Tu et al.'s unbalanced ePSU, while achieving $1.3-6.7\times$ runtime speedups.
## 2025/2088
* Title: UP TO 50% OFF: Efficient Implementation of Polynomial Masking
* Authors: Jorge Andresen, Paula Arnold, Sebastian Berndt, Thomas Eisenbarth, Sebastian Faust, Marc Gourjon, Eric Landthaler, Elena Micheli, Maximilian Orlt, Pajam Pauls, Kathrin Wirschem, Liang Zhao
* [Permalink](https://eprint.iacr.org/2025/2088)
* [Download](https://eprint.iacr.org/2025/2088.pdf)
### Abstract
While passive probing attacks and active fault attacks have been studied for multiple decades, research has only started to consider combined attacks that use both probes and faults relatively recently. During this period, polynomial masking became a promising, provably secure countermeasure to protect cryptographic computations against such combined attacks. Unlike other countermeasures, such as duplicated additive masking, polynomial masking can be implemented using a linear number of shares, as shown by Berndt et al. at CRYPTO '23. Based upon this fact, Arnold et al. noted at CHES '24 that polynomial masking is particularly well-suited for parallel computation. This characteristic is especially effective in scenarios involving multiple circuits with identical structures, such as the 16 SBoxes in AES. Just recently, Faust et al. showed at CHES '25 that one can also incorporate the technique of packed secret sharing into these masking schemes, given that the state-of-the-art polynomial masking scheme is secure against combined attacks.
In this work, we present provably secure advancements regarding this state-of-the-art scheme in both computational and randomness efficiency, reducing the randomness complexity by up to 50% and the computational complexity even more by going from a quadratic term to a linear one for many parameters. Moreover, we present the first implementation of a polynomial masking scheme against combined attacks along with an extensive experimental evaluation for a wide range of parameters and configurations as well as a statistical leakage detection to evaluate the security of the implementation on an Arm Cortex-M processor. Our implementation is publicly available to encourage further research in practical combined resilience.
## 2025/2089
* Title: Traceable Bottom-Up Secret Sharing and Law & Order on Community Social Key Recovery (Full Version)
* Authors: Rittwik Hajra, Subha Kar, Pratyay Mukherjee, Soumit Pal
* [Permalink](https://eprint.iacr.org/2025/2089)
* [Download](https://eprint.iacr.org/2025/2089.pdf)
### Abstract
A recent work by Kate et al. [EPRINT 2025] proposes a community-based social recovery scheme (SKR), where key-owners can use a subset of other community members as guardians, and in exchange, they play guardians to support other participants' key recovery. Their construction relies on a new concept called bottom-up secret sharing (BUSS). However, they do not consider a crucial feature, called traceability, which ensures that if more than a threshold number of the guardians collude, at least some colluders' identities can be traced -- thereby deterring participants from colluding. In this paper, we incorporate traceability into the community social key recovery as an important feature.
We first introduce the notion of traceable BUSS, which allows tracing colluders by accessing a reconstruction box. Then, extending the work of Boneh et al. [CRYPTO 2024], we propose the first traceable BUSS construction. Finally, we show how to generically use a traceable BUSS scheme to construct a traceable SKR in the aforementioned community setting. Overall, this is the first scheme combining decentralized key management with traceability, marrying BUSSrCOs scalability with the deterrence of traceable secret sharing.
## 2025/2090
* Title: Quantum Grover Attack on MIBS
* Authors: Hasan Ozgur Cildiroglu, Harun Basmaci, Oguz Yayla
* [Permalink](https://eprint.iacr.org/2025/2090)
* [Download](https://eprint.iacr.org/2025/2090.pdf)
### Abstract
The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher's vulnerability to GroverrCOs key-search algorithm under the NIST PQC security constraint $\texttt{MAXDEPTH}$. By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately $2^{94}$ for MIBS-64 and $2^{111}$ for MIBS-80. These values fall below NISTrCOs Level-1 security threshold ($2^{170}$), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.
## 2025/2091
* Title: Efficient and Proof-of-Useful-Work Friendly Local-Search for Distributed Consensus
* Authors: Matthias Fitzi, Aggelos Kiayias, Laurent Michel, Giorgos Panagiotakos, Alexander Russell
* [Permalink](https://eprint.iacr.org/2025/2091)
* [Download](https://eprint.iacr.org/2025/2091.pdf)
### Abstract
Blockchain protocols based on the popular ``Proof-of-Work'' mechanism
yield public transaction ledgers maintained by a group of distributed participants who solve computationally hard puzzles to earn the right
to add a block.
The success and widespread adoption of this mechanism has led to
staggering energy consumption devoted to solving such (otherwise)
``useless'' puzzles. While the environmental impacts of the framework have
been widely criticized, this has been the dominant distributed ledger
paradigm for years.
The Ofelimos ``Proof-of-Useful-Work'' protocol (Fitzi et al.,
CRYPTO 2022) addressed this by establishing that useful
combinatorial problems could replace the conventional hashing puzzles,
yielding a provably secure blockchain that meaningfully utilizes the computational work that underlies the protocol.
The usefulness to wastefulness ratio of Ofelimos hinges on the properties of its underlying generic distributed local-search algorithm---Doubly Parallel Local Search (DPLS). We observe that this search procedure is particularly wasteful when exploring steep regions of the solution
space.
To address this issue, we introduce Frequently Rerandomized Local
Search (FRLS), a new generic distributed local search algorithm that
we show to be consistent with the Ofelimos architecture. While this
algorithm retains ledger security, we show that it also provides compelling performance on benchmark problems arising in practice: Concretely, state-of-art local-search algorithms for cumulative scheduling and warehouse
location can be directly adapted to FRLS and we experimentally
demonstrate the efficiency of the resulting algorithms.
## 2025/2092
* Title: CRA and Cryptography: The Story Thus Far
* Authors: Markku-Juhani O. Saarinen
* [Permalink](https://eprint.iacr.org/2025/2092)
* [Download](https://eprint.iacr.org/2025/2092.pdf)
### Abstract
We report on our experiences with the ongoing European standardisation efforts related to the EU Cyber Resilience Act (CRA) and provide interim (November 2025) estimates on the direction that European cryptography regulation may take, particularly concerning the algorithm ``allow list'' and PQC transition requirements in products.
We also outline some of the risks associated with the partially closed standardisation process, including active impact minimisation by vendors concerned with engineering costs, a lack of public review leading to lower technical quality, and an increased potential for backdoors.
The Cyber Resilience Act came into effect in December 2024, and its obligations will fully take effect for makers of ``products with digital elements'' from 2027. CRA compliance is a requirement for obtaining the CE mark and a prerequisite for selling products in the European Single Market, which comprises approximately 450 million consumers. The CRA has a wide-ranging set of security requirements, including security patching and the use of cryptography (data integrity, confidentiality for data at rest and data in transit). However, the Cyber Resilience Act itself is a legal text devoid of technical detail -- it does not specify the type of cryptography deemed appropriate to satisfy its requirements.
The technical implications of CRA are being detailed in approximately 40 new standards from the three European standardisation organisations, CEN, CENELEC, and ETSI. While the resulting ETSI standards can be expected to be available for free even in the drafting stage, the CEN and CENELEC standards will probably require a per-reader license fee. This, despite recent legal rulings asserting that product security and safety standards are part of EU law due to their legal effects.
Taking a recent (2024) example of cryptographic requirements in such standards, we observe that the definitions and language in the Radio Equipment Directive (RED DA) harmonised standard (EN 18031 series) may allow vendors to take an approach where weak cryptography is considered ``best practice'' right until exploitation is feasible.
Recognising recent developments such as the EU Post-Quantum Cryptography transition roadmap, many CRA standardisation working groups are moving towards a ``State-of-the-Art Cryptography'' (SOTA Cryptography) model where approved mechanism listings are published by the European Cybersecurity Certification Group (ECCG). CRA-compliant products may still support other cryptographic mechanisms, but only SOTA is permitted as a safe default for Internet-connected products.
## 2025/2093
* Title: Lore: An LWE-based Key Encapsulation Mechanism with Variable Modulus and CRT Compression
* 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/2093)
* [Download](https://eprint.iacr.org/2025/2093.pdf)
### Abstract
In this paper, we propose a new post-quantum lattice-based IND-CCA2-secure key encapsulation mechanism (KEM) named Lore. The scheme is based on a variant of MLWR problem following LPR structure with two new technologies called variable modulus and CRT compression, which provide a balance of decryption failure probability and ciphertext size. We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency, compact bandwidth and proper decryption failure rate(DFR) corresponding to its security levels compared with former results.
## 2025/2094
* Title: Vega: Low-Latency Zero-Knowledge Proofs over Existing Credentials
* Authors: Darya Kaviani, Srinath Setty
* [Permalink](https://eprint.iacr.org/2025/2094)
* [Download](https://eprint.iacr.org/2025/2094.pdf)
### Abstract
As digital identity verification becomes increasingly pervasive, existing privacy-preserving approaches are still limited by complex circuit designs, large proof sizes, trusted setups, or high latency. We present Vega, a practical zero-knowledge proof system that proves statements about existing credentials without revealing anything else. Vega is simple, does not require a trusted setup, and is more efficient than the prior state-of-the-art: for a 1920-byte credential, Vega achieves 212 ms proving time, 51 ms verification time, 150 kB proofs, and a 436 kB proving key. At the heart of Vega are two principles that together enable a lightweight proof system that pays only for what it needs. First, fold-and-reuse proving exploits repetition and folding opportunities (i) across presentations, by pushing repeated work to a rerandomizable precomputation; (ii) across uniform hashing steps, by folding many steps into a single step; and (iii) for zero-knowledge, by folding the public-coin transcript with a random one. Second, lookup-centric arithmetization extracts relevant values from credential bytes, both for extracting relevant fields without full in-circuit parsing, and to enable length-hiding hashing.
## 2025/2095
* Title: FPS: Flexible Payment System
* Authors: Adithya Bhat, Srinivasan Raghuraman, Panagiotis Chatzigiannis, Duc V Le, Mohsen Minaei
* [Permalink](https://eprint.iacr.org/2025/2095)
* [Download](https://eprint.iacr.org/2025/2095.pdf)
### Abstract
Existing payment systems make fixed trade-offs between performance and security assumptions. Traditional centralized systems like Visa assume synchronous networks and crash faults to achieve high throughput, while blockchain-based systems (e.g., Algorand, Aptos) adopt Byzantine fault tolerance and partial synchrony for stronger security at the cost of performance. This rigid approach forces all users to accept the same security-performance trade-off regardless of their individual trust and threat models.
We present a flexible payment system where clients independently choose assumptions about (i) network timing (bounded or partial synchrony), (ii) corruption (static or adaptive), and (iii) faults (crash or Byzantine), supporting eight assumption combinations simultaneously. Unlike traditional systems requiring consensus, our approach uses a novel flexible variant of consistent broadcast where clients external to the protocol verify delivery through cryptographic proofs, eliminating the need for global ordering. We implemented our system in Rust and demonstrated that clients choosing partially synchronous network and crash assumptions achieve $+242.1\%$ higher throughput and $+70.4\%$ better latency compared to clients with synchronous network and Byzantine assumptions, confirming that our system enables users to optimize their individual security-performance trade-offs.
## 2025/2096
* Title: Laser Fault Injection Attack on the eXtended Merkle Signature Scheme
* Authors: Alexander Wagner, Marc Schink, Silvan Streit, Dominik Klein, Sven Freud
* [Permalink](https://eprint.iacr.org/2025/2096)
* [Download](https://eprint.iacr.org/2025/2096.pdf)
### Abstract
The interest in hash-based signatures (HBS) has increased since the need for post-quantum cryptography (PQC) emerged that could withstand attacks by quantum computers. Since their standardization, stateful HBS algorithms have been deployed in several products ranging from embedded devices up to servers.
In practice, they are most applicable to verify the integrity and authenticity of data that rarely changes, such as the firmware of embedded devices. The verification procedure then takes place during a secure boot or firmware update process. In past works, the research community has investigated hardware and software optimizations for this use case and vendors brought forward products.
In this study, we practically evaluate a fault attack on the Winternitz One-Time Signature (WOTS) scheme. The attack can be mounted on different HBS schemes, such as LMS, XMSS, and SPHINCS+. Both, the verification as well as the signing operation can be targeted.
The study describes the preparation and implementation of the attack on a standard microcontroller as well as the difficulties the attacker has to overcome. Additionally it presents a countermeasure, which is easy to implement and can increase the effort for an attacker significantly.
## 2025/2097
* Title: Hash-Based Blind Signatures: First Steps
* Authors: Javier Herranz, Hugo Louiso
* [Permalink](https://eprint.iacr.org/2025/2097)
* [Download](https://eprint.iacr.org/2025/2097.pdf)
### Abstract
Hash-based signatures are a strong candidate for post-quantum scenarios requiring authentication and integrity. Their security relies only on (well-studied) properties of hash functions, so they may be thought as being more robust than other schemes that (today) resist quantum attacks, like those based on lattices, coding or isogenies.
Recent works are also studying hash-based signature schemes with additional properties, like group, ring, threshold, or aggregate signature schemes. In this work we do the same for the important case of blind signatures. We describe a possible hash-based instantiation of Fischlin's generic scheme, we motivate our choices and we finally give some benchmarks for running times and memory requirements, resulting from our C implementation.
## 2025/2098
* Title: Optical computing of zero-knowledge proof with single-pixel imaging
* Authors: Wei Huang, Shuming Jiao, Huichang Guan, Huisi Miao, Chao Wang
* [Permalink](https://eprint.iacr.org/2025/2098)
* [Download](https://eprint.iacr.org/2025/2098.pdf)
### Abstract
Optical computing has garnered significant attention in recent years due to its high-speed parallel processing and low power consumption capabilities. It has the potential to replace traditional electronic components and systems for various computation tasks. Among these applications, leveraging optical techniques to address information security issues has emerged as a critical research topic. However, current attempts are predominantly focused on areas such as image encryption and information hiding, with limited exploration of other modern information security concepts, including zero-knowledge proof (ZKP). In this paper, we propose an optical ZKP method based on single-pixel imaging (SPI). By utilizing the flexibility of SPI, our proposed approach can directly acquire randomly permuted results of the source problem's solution in the form of encoded images, thereby encrypting and verifying the original solution. ZKP for the source problem can be realized with optical computing based on a proving protocol without disclosing additional information. Simulated and experimental results show that our proposed method can be effectively applied to two typical ZKP problems: Sudoku and Hamiltonian cycle problem.
## 2025/2099
* Title: A Lattice-based Designated Verifier zkSNARK from Standard Assumptions * Authors: Mohammad Sadegh Ahmadi, Taraneh Eghlidos, Behzad Abdolmaleki, Ngoc Khanh Nguyen
* [Permalink](https://eprint.iacr.org/2025/2099)
* [Download](https://eprint.iacr.org/2025/2099.pdf)
### Abstract
Designated Verifier zero-knowledge Succinct Non-Interactive Arguments of Knowledge (DV-zkSNARKs) are cryptographic argument systems in which the ability to verify proofs is restricted to a designated verifier. Unlike publicly verifiable zkSNARKs, these constructions ensure that only an authorized party can validate the correctness of the proof. Existing lattice-based DV-zkSNARK constructions typically rely on either linear-only encryption (LOE) or linear targeted malleability (LTM). The former does not guarantee security against quantum adversaries, while the latter restricts knowledge soundness to the non-adaptive setting. To address these limitations, we propose an inner product argument system that relies solely on the hardness of the Module Short Integer Solution (MSIS) assumption and achieves knowledge soundness in the random oracle model. This construction enables a designated verifier, holding a secret key, to succinctly verify inner product of a committed witness with an arbitrary vector. By combining our argument system with a linear probabilistic checkable proof (LPCP) compiler, to the best of our knowledge, we obtain the first DV-zkSNARK construction based on standard assumptions. Our implementation achieves prover and verification times comparable to the state of the art, while reducing public parameter size by a factor of 10, at the cost of a 2.5|u increase in proof size.
## 2025/2100
* Title: Tag Functions and Their Applications to Lattice-based Signatures and IBEs rCo Compact Designs and Tighter Security
* Authors: Parhat Abla
* [Permalink](https://eprint.iacr.org/2025/2100)
* [Download](https://eprint.iacr.org/2025/2100.pdf)
### Abstract
The existing lattice-based signature and IBE schemes suffer from the non-compactness of
public keys or larger reduction loss in the security analysis. Thus we solve and improve those deficiencies
as follows:
rCo First, we construct a lattice-based short signature scheme with a compact verification key in the
standard model based on the ring short integer solution (RSIS) assumption. Under the same com-
pactness, the ring modulus of our signature scheme is significantly smaller than the compact sig-
nature scheme of Alperin-Sheriff (PKC 2015). More importantly, our signature scheme achieves
better reduction loss than all the previous confined guessing-based signatures. In other words, our
signature scheme achieves better security and efficiency simultaneously.
rCo Secondly, we further design a short signature scheme with a nearly compact public key size and an
even smaller reduction loss. Our second signature scheme achieves even better reduction loss than
our first signature scheme yet at the cost of increasing the public key to a super-constant number
of ring vectors.
rCo Last but not least, we construct an adaptively secure compact IBE scheme from the lattice as-
sumptions and the truncation collision-resistant hash functions (TCRHF) introduced by Jager and
Kurek (ASIACRYPT 2018). Note that the previous TCRHF-based IBE schemes are not even close
to compactness.
The above improvements mainly benefited from our compact design of the tag functions and their more
compact homomorphic evaluations. We also believe that our newly designed tag function may find new
applications in designing other cryptographic schemes, like ABE and others.
## 2025/2101
* Title: Fault Attacks against UOV-based Signatures
* Authors: Sven Bauer, Fabrizio De Santis, Kristjane Koleci
* [Permalink](https://eprint.iacr.org/2025/2101)
* [Download](https://eprint.iacr.org/2025/2101.pdf)
### Abstract
The Unbalanced Oil and Vinegar (UOV) construction is the foundation of several post-quantum digital signature algorithms currently under consideration in NIST's standardization process for additional post-quantum digital signature schemes. This paper introduces new single fault injection attacks against the signing procedure of deterministic variants of signature schemes based on the UOV construction. We show how these attacks can be applied to attack MAYO and PROV, two signature schemes submitted to the NIST call for additional post-quantum signature schemes. The attacks are demonstrated with reference implementations that run on an ARM Cortex-M4 processor. Our attacks do not require precise triggering or precise fault injection capabilities. Any type of fault in large portions of the code has the potential to result in successful key recovery. We demonstrate our attacks with very cheap equipment and simple clock glitching techniques, enabling the recovery of the secret key with either two faulty signatures or one correct signature and one faulty signature in the case of MAYO and one correct signature and two faulty signatures in case of PROV. The fact that our attacks do not require precise fault injection capabilities and can be successful with only a few signatures makes them particularly powerful, hence harmful for the implementation security of post-quantum digital signature schemes.
## 2025/2102
* Title: A Graph-Theoretic Framework for Randomness Optimization in First-Order Masked Circuits
* Authors: Dilip Kumar S. V., Benedikt Gierlichs, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/2102)
* [Download](https://eprint.iacr.org/2025/2102.pdf)
### Abstract
We present a generic, automatable framework to reduce the demand for fresh randomness in first-order masked circuits while preserving security in the glitch-extended probing model. The method analyzes the flow of randomness through a circuit to establish security rules based on the glitch-extended probing model. These rules are then encoded as an interference graph, transforming the optimization challenge into a graph coloring problem, which is solved efficiently with a DSATUR heuristic. Crucially, the optimization only rewires randomness inputs without altering core logic, ensuring seamless integration into standard EDA flows and applicability to various gadgets like DOM-indep (Domain-Oriented Masking) and HPC (Hardware Private Circuits). On 32-bit adder architectures, the framework substantially reduces randomness requirements by 79rCo90%; for instance, the KoggerCoStone adder's requirement of 259 unique random inputs is reduced to 27. All optimized designs were evaluated using PROLEAD, with the leakage results indicating compliance with first-order glitch-extended probing security.
## 2025/2103
* Title: Threshold Batched Identity-Based Encryption from Pairings in the Plain Model
* Authors: Junqing Gong, Brent Waters, Hoeteck Wee, David J. Wu
* [Permalink](https://eprint.iacr.org/2025/2103)
* [Download](https://eprint.iacr.org/2025/2103.pdf)
### Abstract
In a batched identity-based encryption (IBE) scheme, ciphertexts are associated with a batch label $\mathsf{tag}^*$ and an identity $\mathsf{id}^*$ while secret keys are associated with a batch label $\mathsf{tag}$ and a set of identities $S$. Decryption is possible whenever $\mathsf{tag} = \mathsf{tag}^*$ and $\mathsf{id}^* \in S$. The primary efficiency property in a batched IBE scheme is that the size of the decryption key for a set $S$ should be independent of the size of $S$. Batched IBE schemes provide an elegant cryptographic mechanism to support encrypted memory pools in blockchain applications.
In this work, we introduce a new algebraic framework for building pairing-based batched IBE. Our framework gives the following:
First, we obtain a selectively-secure batched IBE scheme under a $q$-type assumption in the plain model. Both the ciphertext and the secret key consist of a constant number of group elements. This is the first pairing-based batched IBE scheme in the plain model. Previous pairing-based schemes relied on the generic group model and the random oracle model.
Next, we show how to extend our base scheme to a threshold batched IBE scheme with silent setup. In this setting, users independently choose their own public and private keys, and there is a non-interactive procedure to derive the master public key (for a threshold batched IBE scheme) for a group of users from their individual public keys. We obtain a statically-secure threshold batched IBE scheme with silent setup from a $q$-type assumption in the plain model. As before, ciphertexts and secret keys in this scheme contain a constant number of group elements. Previous pairing-based constructions of threshold batched IBE with silent setup relied on the generic group model, could only support a polynomial number of identities (where the size of the public parameters scaled linearly with this bound), and ciphertexts contained $O(\lambda / \log \lambda)$ group elements, where $\lambda$ is the security parameter.
Finally, we show that if we work in the generic group model, then we obtain a (threshold) batched IBE scheme with shorter ciphertexts (by 1 group element) than all previous pairing-based constructions (and without impacting the size of the secret key).
Our constructions rely on classic algebraic techniques underlying pairing-based IBE and do not rely on the signature-based witness encryption viewpoint taken in previous works.
## 2025/2104
* Title: Quantum Voting Protocol from Classical Assumption
* Authors: Tingyu Ge, Mingqiang Wang, Xiaolei Wang, Xinyuan Zhao
* [Permalink](https://eprint.iacr.org/2025/2104)
* [Download](https://eprint.iacr.org/2025/2104.pdf)
### Abstract
Quantum voting allows us to design voting scheme by quantum mechanics. The existing quantum voting protocols mainly use quantum entangled states. However, the existing protocols rarely consider the problem of repeated voting and tampered voting by malicious voters, and hybrid quantum voting protocol has not been discussed. In this paper, we use EFI pairs (Entity-Friendly Integer pairs) instead quantum entangled states to address the shortage of existing protocols, and propose a new quantum voting protocol. Our protocol is structured to avoid repeated voting by any voter, and can prevent the leakage of voters' voting information. The security of our protocol can be finally reduced to a classical assumption i.e. BQP = QMA. Combined with quantum key distribution (QKD), we further optimize the protocol to prevent malicious adversaries from interfering with the final voting results. Moreover, we use extended noisy trapdoor claw-free function (ENTCF) to construct the first hybrid quantum voting protocol, which allows a classical voter to interact with a quantum center through a classical channel to complete the voting process.
## 2025/2105
* Title: A Lattice-Based Puncturable Attribute-Based Proxy Re-Encryption with HRA Security and Switchable Tags for Cloud Data Sharing
* Authors: Tianqiao Zhang, Mingming Jiang, Fucai Luo, Yuyan Guo, Jinqiu Hou
* [Permalink](https://eprint.iacr.org/2025/2105)
* [Download](https://eprint.iacr.org/2025/2105.pdf)
### Abstract
With the rapid advancement of cloud computing technology, outsourcing massive datasets to cloud servers has become a prominent trend, making secure and efficient data sharing mechanisms a critical requirement. Attribute-based proxy re-encryption (ABPRE) has emerged as an ideal solution due to its support for fine-grained, one-to-many access control and robust ciphertext transformation capabilities. However, existing ABPRE schemes still exhibit shortcomings in addressing forward security issues caused by long-term private key leakage, threats from quantum computer attacks, and vulnerabilities to honest re-encryption attacks (HRA). To simultaneously resolve these challenges, this paper introduces a novel cryptographic primitive termed puncturable attribute-based proxy re-encryption with switchable tags (PABPRE-ST), constructing a secure cloud data sharing scheme that supports fine-grained revocation. By integrating puncturable encryption (PE) mechanisms into the ABPRE framework, the scheme achieves fine-grained ciphertext revocation based on tags. In PABPRE-ST, data owners embed tags into ciphertexts, enabling data users to puncture specific tags and thereby revoke access to corresponding ciphertexts at a granular level. Furthermore, the scheme allows delegators to switch ciphertext tags, enhancing sharing flexibility. We formalize the security definitions for the proposed puncturable attribute-based proxy re-encryption scheme and prove its security under the learning with errors (LWE) assumption, which is widely believed to be resistant to quantum computer attacks. Security analysis demonstrates that the proposed scheme achieves HRA security in the standard model.
## 2025/2106
* Title: SoK: Blockchain Oracles Between Theory and Practice
* Authors: Colin Finkbeiner, Ghada Almashaqbeh
* [Permalink](https://eprint.iacr.org/2025/2106)
* [Download](https://eprint.iacr.org/2025/2106.pdf)
### Abstract
Smart contract-based decentralized applications (dApps) have become an ever-growing way to facilitate complex on-chain operations. Oracle services strengthened this trend by enabling dApps to access real-world data and respond to events happening outside the blockchain ecosystem. A large number of academic and industrial oracle solutions have emerged, capturing various designs, capabilities, and security assumptions/guarantees. This rapid development makes it challenging to comprehend the landscape of oracles, understand their trade-offs, and build on them.
To address these challenges, we develop a systematization of knowledge for blockchain oracle services. To the best of our knowledge, our work is the first to provide extensive study of oracles while empirically investigating their capabilities in practice. After examining the general design framework of oracles, we develop a multi-dimensional systematization framework assessing existing solutions based on their capabilities, trust and security assumption/guarantees, and their underlying design architecture. To further aid in this assessment, we conduct a number of empirical experiments to examine oracle deployed in practice, thus offering additional insights about their deployment maturity, usage popularity, performance, and ease-of-use. We go on to distill a number of insights and gaps, thus providing a guide for practitioners (on the use of these oracles) and researchers (by highlighting gaps and open problems).
## 2025/2107
* Title: Quantum-safe Identity-binding Password Authenticated Key Exchange Protocols
* Authors: Pratima Jana, Ratna Dutta
* [Permalink](https://eprint.iacr.org/2025/2107)
* [Download](https://eprint.iacr.org/2025/2107.pdf)
### Abstract
Password-based Authenticated Key Exchange (${\sf PAKE}$) is a widely acknowledged, promising security mechanism for establishing secure communication between devices. It enables two parties to mutually authenticate each other over insecure networks and generate a session key using a low-entropy password. However, the existing $\mathsf{PAKE}$ protocols encounter significant challenges concerning both security and efficiency in the context of the \textit{Internet of Things} (IoT). In response to these challenges, we contribute to the advancement of post-quantum secure $\mathsf{PAKE}$ protocols tailored for IoT applications, enriching the existing landscape. In this study, we introduce two novel protocols, $\mathsf{PAKE}$-\textup{I} and $\mathsf{PAKE}$-\textup{II}, designed to address these concerns and enhance the security standards of $\mathsf{PAKE}$ protocol. While $\mathsf{PAKE}$-\textup{I} is secure under lattice-based hardness assumptions, $\mathsf{PAKE}$-\textup{II} derives its security from isogeny-based hard problems. Our lattice-based protocol $\mathsf{PAKE}$-\textup{I} is secure based on the \textit{Pairing with Errors} ($\mathsf{PWE}$) assumption and the \textit{Decision Ring Learning with Errors} ($\mathsf{DRLWE}$) assumption and our isogeny-based protocol $\mathsf{PAKE}$-\textup{II} is secure based on the hardness of the \textit{Group Action Inverse Problem} ($\mathsf{GAIP}$) and the \textit{Commutative SuperSingular Diffie-Hellman} ($\mathsf{CSSDH}$) problem in the Random Oracle Model $(\mathsf{ROM})$. We present a comprehensive security proof in a conventional game-based indistinguishability security model that addresses offline dictionary attacks, replay attacks, compromise attacks for both parties (client and server) and perfect forward secrecy. Additionally, our proposed $\mathsf{PAKE}$ protocols are the first post-quantum secure $\mathsf{PAKE}$s that achieve identity privacy and resistance to pre-computation attacks. Through rigorous performance evaluations, the paper demonstrates that the proposed $\mathsf{PAKE}$ schemes are ultralight and exhibit notable advantages in terms of total computation cost and enhanced security properties when compared to the existing protocols. More positively, both the proposed $\mathsf{PAKE}$ are optimal in the sense that they achieve mutual authentication explicitly in only three rounds which is the least number of rounds required for acquiring mutual authentication between two parties.
--- Synchronet 3.21a-Linux NewsLink 1.2