From Newsgroup: sci.crypt

## In this issue
1. [2025/895] Blinding Post-Quantum Hash-and-Sign Signatures
2. [2025/1665] Threshold Public-Key Encryption: Definitions, ...
3. [2025/1986] Anonymous Authentication and Key Agreement, Revisited
4. [2025/1987] Single-Trace Key Recovery Attacks on HQC Using ...
5. [2025/1988] Almost NTRU: Revisiting Noncommutativity Against ...
6. [2025/1989] HardCODE: Hardware-based Circuit Obfuscation using ...
7. [2025/1990] Accelerating the Primal Hybrid Attack against ...
8. [2025/1991] TWFalcon: Triple-Word Arithmetic for Falcon; Giving ...
9. [2025/1992] Towards Optimal Concurrent-Secure Blind Schnorr ...
10. [2025/1993] A Simplified Round-by-round Soundness Proof of FRI
11. [2025/1994] Separating Pseudorandom Generators from Logarithmic ...
12. [2025/1995] Device-Bound Anonymous Credentials With(out) ...
13. [2025/1996] Turning Multiple Key-Dependent Attacks into ...
14. [2025/1997] Provable decryption failure security for practical ...
15. [2025/1998] Non-adaptive One-Way to Hiding not only Implies ...
16. [2025/1999] New Security Proofs of MPC-in-the-Head Signatures ...
17. [2025/2000] Trust, But Verify When Using the Powers of Tau
18. [2025/2001] On Computational VSS for General Access Structures
19. [2025/2002] Pseudorandom Correlation Functions for Multiparty ...
20. [2025/2003] A Sparse Polynomial Multiplier for HQC Integrating ...
21. [2025/2004] Re-randomization Attack on the Certificateless ...
22. [2025/2005] Reactive Correctness, sINDCPA-D-Security and ...
23. [2025/2006] OmniBA: Round-Efficient BA with Quadratic ...
24. [2025/2007] k-Anonymous Group Signatures: Addressing Strict ...
25. [2025/2008] Two-Server Private Information Retrieval in ...
26. [2025/2009] When Randomness IsnrCOt Random: Practical Fault ...
27. [2025/2010] On the Distribution of the Distances of Random Words
28. [2025/2011] When the Wrong Key Lives On: The Key-Recovery ...
29. [2025/2012] Head Start: Digit Extraction in TFHE from MSB to LSB
30. [2025/2013] MARS: Low-Leakage Multi Adversarial Owner and ...
31. [2025/2014] Multi-Splitting Forking Based Modular Security of ...
32. [2025/2015] Proving Authenticated Key Exchange via Memory- ...
33. [2025/2016] Constructions of a Family of Nonlinear Permutations ...
34. [2025/2017] Secure Onion Encryption and the Case of Counter ...
35. [2025/2018] Batched and Packed (Publicly) Verifiable Secret ...
36. [2025/2019] Practical Multi-party Private Set Intersection with ...
37. [2025/2020] VerfCNN, Optimal Complexity zkSNARK for ...
38. [2025/2021] TreeCast: Multi-Party Key Establishment Protocol ...
39. [2025/2022] Formal Verification of Privacy Pass
40. [2025/2023] Select-Then-Compute: Encrypted Label Selection and ...
## 2025/895
* Title: Blinding Post-Quantum Hash-and-Sign Signatures
* Authors: Charles Bouillaguet, Thibauld Feneuil, Jules Maire, Matthieu Rivain, Julia Sauvage, Damien Vergnaud
* [Permalink](https://eprint.iacr.org/2025/895)
* [Download](https://eprint.iacr.org/2025/895.pdf)
### Abstract
Blind signature schemes are essential for privacy-preserving applications such as electronic voting, digital currencies or anonymous credentials. In this paper, we revisit Fischlin's framework for round-optimal blind signature schemes and its recent efficient lattice-based instantiations. Our proposed framework compiles any post-quantum hash-and-sign signature scheme into a blind signature scheme. The resulting scheme ensures blindness by design and achieves one-more unforgeability, relying solely on the unforgeability of the underlying signature scheme and the random oracle model.
To achieve this we introduce the notion of commit-append-and-prove (CAP) systems, which generalizes traditional commit-and-prove system by making their commitments updatable before proving. This building block allows us to unlock the technical challenges encountered when generalizing previous variants of the Fischlin's framework to any hash-and-sign signature scheme. We provide efficient CAP system instantiations based on recent MPC-in-the-Head techniques.
We showcase our framework by constructing blind versions of UOV and Wave, thereby introducing the first practical blind signatures based on multivariate cryptography and code-based cryptography. Our blind UOV signatures range from 3.8 KB to 11 KB, significantly outperforming previous post-quantum blind signatures, such as the 22 KB lattice-based blind signatures, which were the most compact until now.
## 2025/1665
* Title: Threshold Public-Key Encryption: Definitions, Relations, and CPA-to-CCA Transforms
* Authors: Chris Brzuska, Michael Kloo|f, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2025/1665)
* [Download](https://eprint.iacr.org/2025/1665.pdf)
### Abstract
Threshold public-key encryption (TPKE) allows $t$ out of $k$ parties to jointly decrypt a ciphertext, while ensuring confidentiality against any coalition of $t-1$ parties. Despite its long history and ongoing standardisation efforts, there has not been a dedicated study on its basic security notions, and a handful of variations are currently in use.
We initiate the systematic study of TPKE confidentiality and develop relations between notions contrasting indistinguishability (IND) vs. simulatability (SIM), passive (CPA) vs. active (CCA) attacks, and static vs. adaptive corruptions. One of our insights is that security under maximal corruptions does not imply security under fewer corruptions when the adversary has access to partial decryptions on challenge ciphertexts. Maximal corruption was adopted by a significant portion of prior works, and this calls for cautious interpretation when using such a notion.

We complement our study by providing two generic CPA-to-CCA transforms for TPKE. The first is effectively the Naor--Yung transform, for which we fix a gap in prior work by requiring the underlying TPKE to achieve semi-malicious CPA security, where the adversary can choose randomness for non-challenge ciphertexts. Our second transform applies to any CPA secure TPKE in the random oracle model. We abstract the underlying technique as a standalone novel primitive called non-interactive proof of randomness (NIPoR), which we consider of independent interest.
## 2025/1986
* Title: Anonymous Authentication and Key Agreement, Revisited
* Authors: Yanqi Zhao, Xiangyu Liu, Min Xie, Xiaoyi Yang, Jianting Ning, Baodong Qin, Haibin Zhang, Yong Yu
* [Permalink](https://eprint.iacr.org/2025/1986)
* [Download](https://eprint.iacr.org/2025/1986.pdf)
### Abstract
In NDSS 2024, Yu~et al. proposed AAKA, an Anonymous Authentication and Key Agreement scheme designed to protect users' privacy from mobile tracking by Mobile Network Operators (MNOs). AAKA aims to provide both anti-tracking privacy and traceability (lawful de-anonymization), allowing subscribers to access the network via anonymous proofs while enabling a Law Enforcement Agency (LEA) to trace the real identity if misbehaviors are detected. However, we identify that the AAKA scheme in NDSS 2024 is insecure since the subscriber's identity is exposed within the protocol, thereby failing to achieve the claimed privacy and traceability.
Building on the repair of AAKA, we propose AAKA+, Anonymous Authentication and Key Agreement with Verifier-Local Revocation, a new mobile authentication scheme, to ensure privacy against mobile tracking. In addition to the privacy and traceability introduced in NDSS 2024, AAKA+ additionally allows the MNO to immediately assert whether the associated subscriber has been traced and revoked upon receiving an anonymous proof. We formally define the syntax and the security model of AAKA+ and propose two concrete schemes, AAKA+BB and AAKA+PS, based on the Boneh-Boyen signature and the Pointcheval-Sanders signature schemes, respectively. Both AAKA+BB and AAKA+PS are pairing-free on the user equipment side and compatible with existing cellular infrastructure. Experimental results show that our schemes are practical, with anonymous proof generation taking approximately 18 milliseconds for a constrained device.
## 2025/1987
* Title: Single-Trace Key Recovery Attacks on HQC Using Valid and Invalid Ciphertexts
* Authors: Haiyue Dong, Qian Guo, Denis Nabokov
* [Permalink](https://eprint.iacr.org/2025/1987)
* [Download](https://eprint.iacr.org/2025/1987.pdf)
### Abstract
As the Hamming Quasi-Cyclic (HQC) cryptosystem was recently selected by NIST for standardization, a thorough evaluation of its implementation security is critical before its widespread deployment.
This paper presents single-trace side-channel attacks that recover the full long-term secret key of HQC, experimentally evaluated on a protected Cortex-M4 implementation. We introduce two distinct attacks that significantly advance the state of the art: a passive attack that uniquely models key recovery as a moderate-density parity-check (MDPC) decoding problem from a single valid ciphertext, and an active chosen-ciphertext attack employing a new probing strategy on a linear combination of secret key components for significantly improved efficiency. Both attacks are enabled by a new information set decoding (ISD) variant that exploits soft side-channel information, a contribution of broader importance to code-based cryptography. Our experiments show that a single trace suffices for full key recovery under realistic conditions, effectively defeating countermeasures such as codeword masking for the first time. We also show that several existing defenses are ineffective against the new attacks.
## 2025/1988
* Title: Almost NTRU: Revisiting Noncommutativity Against Lattice Attacks
* Authors: Ali Raya, Vikas Kumar, Seong Oun Hwang, Sugata Gangopadhyay
* [Permalink](https://eprint.iacr.org/2025/1988)
* [Download](https://eprint.iacr.org/2025/1988.pdf)
### Abstract
NTRU is one of the most extensively studied lattice-based cryptographic schemes and is widely regarded as a strong candidate for post-quantum security. The most effective attacks on NTRU are lattice-based or lattice-related, which naturally guide the choice of parameters to achieve the desired security levels. In 1997, Hoffstein and Silverman proposed a variant of NTRU based on a noncommutative algebraic structure, claiming that it would mitigate lattice attacks. However, their scheme was later shown to be vulnerable to an algebraic attack by Coppersmith. Although several subsequent attempts have been made in the literature to develop noncommutative variants of NTRU, most of these designs have either been shown to be vulnerable to algebraic attacks or have failed to directly address lattice-based attacks.
In this work, we revisit the problem of constructing a noncommutative analog of NTRU that offers stronger resistance against direct lattice attacks. Firstly, we conceptualize the problem by introducing an almost unstructured variant, and then refine this idea towards a more compact instantiation, culminating in a fully structured construction defined over the group ring of the dihedral group. Our proposal may be viewed as a follow-up to the early noncommutative construction of Hoffstein and Silverman.
We further provide a complete reference implementation of the structured construction under two proposed parameter sets, Plausible and Paranoid, demonstrating both the efficiency and compactness of our scheme in comparison with NTRU-HPS and the state-of-the-art non-commutative NTRU variant.
## 2025/1989
* Title: HardCODE: Hardware-based Circuit Obfuscation using Data Encryption
* Authors: Akashdeep Saha, Sayani Sinha, Chandan Kumar, Animesh Singh, Siddhartha Chowdhury, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/1989)
* [Download](https://eprint.iacr.org/2025/1989.pdf)
### Abstract
Indistinguishability Obfuscation (iO) renders indistinguishable any pair of same-sized and functionally identical circuits. Since its introduction by Barak et al. (Crypto rCO01), iO has become the holy grail of modern cryptography due to the myriad of applications it enables. Despite several theoretical constructions (including recent breakthrough results from well-studied assumptions), practically efficient frameworks for iO have remained out of reach. In this paper, we formally introduce the notion of Hardware-based indistinguishability obfuscation (HiO) with an aim to make iO practical. Further, we present a novel framework called Hardware-based Circuit Obfuscation from Data Encryption (HardCODE) for realizing highly efficient HiO.
Given a simple tamper-proof hardware to store a fixed size secret key, our proposed HardCODE framework yields a provably secure hardware module that achieves iO for all poly-sized circuits, while additionally relying on any one-way function and certain (heuristic but widely studied) assumptions on substitution-permutation networks (used extensively in the design of secure block ciphers). We practically instantiate HardCODE from widely deployed realizations of a simple HSM (Hardware Security Module), and the substitution-permutation network underlying the PRESENT block cipher (an ISO standard for lightweight cryptography). We then use this instance of HardCODE to obfuscate, without loss of generality, the C-17 circuit of the ISCAS-85 benchmark suite, while incurring very small practical overheads. To the best of our knowledge, this constitutes the first practical demonstration of iO.
## 2025/1990
* Title: Accelerating the Primal Hybrid Attack against Sparse LWE using GPUs
* Authors: Ludo N. Pulles, Paul Vi|-
* [Permalink](https://eprint.iacr.org/2025/1990)
* [Download](https://eprint.iacr.org/2025/1990.pdf)
### Abstract
Although the lattice-estimator predicts that Learning with Errors instances having small and very sparse secrets can be broken by hybrid attacks with modest computational resources, no efficient open-source implementation of these attacks exists. This work implements the so-called Guess + Verify attack (G+V) analysed by Albrecht et al. (SAC'19), containing three improvements: (1) cuBLASter, a GPU-based implementation of the lattice basis reduction software BLASter by Ducas et al. (ASIACRYPT'25); (2) a dimension reduction technique for the BDD instance; and (3) a batched variant of BabairCOs Nearest Plane algorithm.
On bases of dimension 512 and above, cuBLASter outperforms BLASter. We also integrate the GPU implementation of the General Sieve Kernel by Ducas et al. (EUROCRYPT'21) into cuBLASterrCOs BKZ framework.
Running G+V on the benchmark instances by Wenger et al. (IEEE SP'25), we show that G+V achieves significantly higher success rates than the Cool&Cruel attack (C+C) by Nolte et al. (AFRICACRYPT'24) on almost all instances, and G+V's average CPU and GPU utilization is substantially lower than the minimum reported by C+C.
## 2025/1991
* Title: TWFalcon: Triple-Word Arithmetic for Falcon; Giving Falcon the Precision to Fly Securely
* Authors: Stef Halmans, Christine van Vredendaal, Tobias Schneider, Frank Custers, Tim G|+neysu
* [Permalink](https://eprint.iacr.org/2025/1991)
* [Download](https://eprint.iacr.org/2025/1991.pdf)
### Abstract
The post-quantum signature scheme Falcon is an attractive scheme for constrained devices due to its compactness and verification performance. However, it relies on floating-point arithmetic for signature generation, which - alongside physical security concerns - introduces two additional drawbacks:
Firstly, if implemented using the standard double-precision format, Falcon does not satisfy the
formally proven error bounds required for a secure Gaussian sampler implementation.
Although no practical attacks exploiting this limitation are currently known, it does give future attack concerns.
Secondly, when looking at constrained devices, 32-bit constrained devices can lack hardware support for high-precision floating-point arithmetic and its use introduces significant performance overhead, as it must be emulated using integers.
In this work we present a novel method to address these limitations: We show that Falcon can be implemented using $\textit{single-precision}$ floating-point numbers. Our proposed method uses Triple-Word Floating-Point (TW) arithmetic and achieves a precision of at least 72 bits, compared to the 53 bits of double-precision floating-point arithmetic.
We show our implementation achieves error bounds that meet the formal security requirements for a secure Gaussian sampler implementation, while maintaining other security guarantees. This way, Falcon can run on constrained devices equipped only with a single-precision Floating-Point Unit (FPU) without the need for integer emulation.
We demonstrate the feasibility of our approach on the Nucleo-L4R5ZI board, which features a Cortex-M4F processor enabled with a single-precision FPU. More precisely, we show the cost of increasing the precision of Falcon in this way only increases the computational effort by a factor of approximately 1.84 compared to the CPU cycles required for an implementation using emulated double-precision arithmetic via integers.
## 2025/1992
* Title: Towards Optimal Concurrent-Secure Blind Schnorr Signatures
* Authors: Pierpaolo Della Monica, Ivan Visconti
* [Permalink](https://eprint.iacr.org/2025/1992)
* [Download](https://eprint.iacr.org/2025/1992.pdf)
### Abstract
Since the work of Chaum in rCO82, the problem of designing secure blind signature protocols for existing signature schemes has been of great interest. In particular, when considering Schnorr signatures, nowadays used in Bitcoin, designing corresponding efficient and secure blind signatures is very challenging in light of the ROS attack [BLL+21] (EurocryptrCO21), which affected all previous efficient constructions.
Currently, the main positive result about concurrent-secure blind Schnorr signatures is the one of Fuchsbauer and Wolf [FW24] (EurocryptrCO24). Their construction, is quite demanding, indeed it requires trusted parameters, non-interactive zero-knowledge arguments and CPA-secure public-key encryption. Moreover, it is proven secure under a game-based definition only, is limited to computational blindness and is vulnerable to harvest now rCLlinkrCY later quantum attacks. Nicely, their construction is also a predicate blind signature (PBS) scheme, allowing signers to have some partial control on the content of the blindly signed message.
In this work, we show neat improvements to the state-of-the-art presenting a new construction for concurrent-secure blind Schnorr signatures that relies on milder/reduced cryptographic assumptions, enjoys statistical blindness, replaces the problematic trusted setup with a non-programmable random oracle, and satisfies also a one-sided simulation-based property providing deniability guarantees to users.
Finally, we show that the above improvements come at a very modest additional cost, achieving essentially the same performance of [FW24].
## 2025/1993
* Title: A Simplified Round-by-round Soundness Proof of FRI
* Authors: Albert Garreta, Nicolas Mohnblatt, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2025/1993)
* [Download](https://eprint.iacr.org/2025/1993.pdf)
### Abstract
The FRI protocol (ICALP '18) is one of the most influential and widely deployed building blocks at the core of modern SNARK systems. While its concrete security is well understood, existing security proofs are intricate and technically complex.
In this work, we present a significantly simpler security analysis of FRI, in particular its round-by-round soundness.
Our approach is more accessible to a broader audience, lowering the barrier to understanding this fundamental protocol.
Furthermore, the simplicity of our analysis may pave the way for future formal verification efforts of modern SNARK constructions.
## 2025/1994
* Title: Separating Pseudorandom Generators from Logarithmic Pseudorandom States
* Authors: Mohammed Barhoush
* [Permalink](https://eprint.iacr.org/2025/1994)
* [Download](https://eprint.iacr.org/2025/1994.pdf)
### Abstract
Pseudorandom generators (PRGs) are a foundational primitive in classical cryptography, underpinning a wide range of constructions. In the quantum setting, pseudorandom quantum states (PRSs) were proposed as a potentially weaker assumption that might serve as a substitute for PRGs in cryptographic applications. Two primary size regimes of PRSs have been studied: logarithmic-size and linear-size. Interestingly, logarithmic PRSs have led to powerful cryptographic applications, such as digital signatures and quantum public-key encryption, that have not been realized from their linear counterparts. However, PRGs have only been black-box separated from linear PRSs, leaving open the fundamental question of whether PRGs are also separated from logarithmic PRSs.
In this work, we resolve this open problem. We establish a quantum black-box separation between (quantum-evaluable) PRGs and PRSs of either size regime. Specifically, we construct a unitary quantum oracle with inverse access relative to which no black-box construction of PRG from (logarithmic or linear) PRS exists. As a direct corollary, we obtain separations between PRGs and several primitives implied by logarithmic PRSs, including digital signatures and quantum public-key encryption.
## 2025/1995
* Title: Device-Bound Anonymous Credentials With(out) Trusted Hardware
* Authors: Karla Friedrichs, Franklin Harding, Anja Lehmann, Anna Lysyanskaya
* [Permalink](https://eprint.iacr.org/2025/1995)
* [Download](https://eprint.iacr.org/2025/1995.pdf)
### Abstract
Anonymous credentials enable unlinkable and privacy-preserving user authentication. To ensure non-transferability of credentials among corrupt users, they can additionally be device-bound. Therein, a credential is tied to a key protected by a secure element (SE), usually a hardware component, and any presentation of the credential requires a fresh contribution of the SE. Interestingly, despite being a fundamental aspect of user credentials, device binding for anonymous credentials is relatively unstudied. Existing constructions either require multiple calls to the SE, or need the SE to keep a credential-specific state -- violating core design principles of shielded SEs. Further, constructions that are compatible with the most mature credential scheme BBS rely on the honesty of the SE for privacy, which is hard to vet given that SEs are black-box components.
In this work, we thoroughly study and solve the problem of device-bound anonymous credentials (DBACs). We model DBACs to ensure the unforgeability and non-transferability of credentials, and to guarantee user privacy at the same time. Our definitions cover a range of SE trust levels, including the case of a subverted or fully corrupted SE. We also define blind DBACs, in which the SE learns nothing about the credential presentations it helped compute. This targets the design of a remote, cloud-based SE which is a deployment model considered for the EU Digital Identity (EUDI) wallet to address the fact that most user phones are not equipped with a sufficiently secure SE. Finally, we present three simple and round-optimal constructions for device binding of BBS credentials, and prove their security in the AGM+ROM and privacy unconditionally. The SE therein is extremely lightweight: it only has to compute a BLS or Schnorr signature in a single call. We also give the BLS-based construction in a blind variant, yielding the first protocol that enables privacy-preserving device binding for anonymous credentials when being used with a remote SE.
## 2025/1996
* Title: Turning Multiple Key-Dependent Attacks into Universal Attacks
* Authors: Hosein Hadipour, Yosuke Todo, Mostafizar Rahman, Maria Eichlseder, Ravi Anand, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2025/1996)
* [Download](https://eprint.iacr.org/2025/1996.pdf)
### Abstract
Key-dependent attacks are effective only for specific weak-key classes, limiting their practical impact. We present a generic statistical framework that combines multiple key-dependent distinguishers into universal attacks covering the full key space. Using log-likelihood ratio statistics, our framework tests the secret key against multiple weak-key distinguishers, aggregates their evidence to determine whether the key is weak or strong for each distinguisher, and exploits this classification to reduce the effective key entropy for key recovery.
We apply this to Orthros-PRF, a sum-of-permutations (SoP) design where any differential-based distinguisher holds only for a fraction of keys. This yields the first universal 8-round differential-linear (DL) key-recovery attack with median time complexity $2^{119.58}$, whereas prior work reached at most 7 rounds in the weak-key setting. To discover the required distinguishers, we extend the open-source S-box Analyzer tool with MILP support for deterministic propagation and develop a model integrating distinguisher search with key recovery. This enables automated discovery of multidimensional DL distinguishers covering up to 10 rounds in each Orthros branch, improving prior work by 4 rounds.
Our results demonstrate that statistical aggregation of multiple weak-key distinguishers enables effective universal cryptanalysis. Our framework is generic and is applicable to other primitives with multiple identifiable weak-key classes.
## 2025/1997
* Title: Provable decryption failure security for practical lattice-based PKE
* Authors: Christian Majenz, Fabrizio Sisinni
* [Permalink](https://eprint.iacr.org/2025/1997)
* [Download](https://eprint.iacr.org/2025/1997.pdf)
### Abstract
Recently, H||velmanns, H|+lsing, and Majenz introduced a security notion called Find Failing Plaintext rCo Non Generic (FFP-NG), which captures the ability of an adversary to find decryption failures by making non-trivial use of the public key. A first analysis of this property for lattice-based schemes was presented by Majenz and Sisinni, who showed that the Learning With Errors (LWE) problem reduces to breaking the FFP-NG security of the PVW scheme with discrete Gaussian noise. In this work, we generalize their result by analysing the FFP-NG security of widely used schemes based on Ring-LWE and Module-LWE. To keep our analysis as general as possible, we consider a family of subgaussian distributions that includes, among others, discrete Gaussians
and centered binomials.
## 2025/1998
* Title: Non-adaptive One-Way to Hiding not only Implies Adaptive Quantum Reprogramming, but also Does Better
* Authors: Heming Liao, Jiangxia Ge, Rui Xue
* [Permalink](https://eprint.iacr.org/2025/1998)
* [Download](https://eprint.iacr.org/2025/1998.pdf)
### Abstract
As three frequently used techniques for adaptive reprogramming in the QROM, the adaptive One-Way to Hiding (O2H) proposed by Unruh (CRYPTO 2014), the GHHM adaptive reprogramming proposed by Grilo et al. (ASIACRYPT 2021), and the Pan-Zeng adaptive reprogramming proposed by Pan and Zeng (PKC 2024), address different reprogramming scenarios, and do not appear to imply one another. A recent breakthrough by Jaeger (ASIACRYPT 2025) reveals a surprising connection: all three of these adaptive techniques can be implied by a non-adaptive reprogramming technique called Fixed-Permutation O2H (FP-O2H). Furthermore, Jaeger's result also improves the security bounds for Unruh's adaptive O2H and the Pan-Zeng adaptive reprogramming theorem.
In this paper, we reconsider the implication between FP-O2H and GHHM adaptive reprogramming. We first introduce a variant of FP-O2H, called the Double-Oracle-Fixed-Permutation O2H (DOFP-O2H). Then, by applying this variant, we derive a tighter upper bound for the GHHM adaptive reprogramming. Thereby, our result complements JaegerrCOs findings by addressing the final piece, showing that the non-adaptive O2H not only implies adaptive reprogramming in the QROM but also yields tighter upper bounds. In addition, a direct application of our tighter GHHM adaptive reprogramming yields a tighter \textsf{EUF-CMA} security proof of the FiatrCoShamir transform in the QROM: the security loss with respect to the number of signing queries q_s decreases from O(q_s) to O(\sqrt{q_s}).
Furthermore, we reconsider the implication between FP-O2H and the ABKM permutation resampling proposed by Alagic et al. (EUROCRYPT 2022). By applying our DOFP-O2H, we reprove the ABKM permutation resampling theorem, and derive the same upper bound as that of Alagic et al. This result suggests that the FP-O2H not only can be applied to analyze the reprogramming in the QROM, but also has potential for analyzing reprogramming in the random permutation setting.
## 2025/1999
* Title: New Security Proofs of MPC-in-the-Head Signatures in the Quantum Random Oracle Model
* Authors: Haruhisa Kosuge, Keita Xagawa
* [Permalink](https://eprint.iacr.org/2025/1999)
* [Download](https://eprint.iacr.org/2025/1999.pdf)
### Abstract
The MPC-in-the-Head paradigm is a promising approach for constructing post-quantum signature schemes. Its significance is underscored by NIST's selection of six signatures based on this paradigm and its variants, TC-in-the-Head and VOLE-in-the-Head, among the fourteen round-2 candidates in its additional post-quantum cryptography standardization process.
Recent works by Aguilar-Melchor et al. (ASIACRYPT 2023), H|+lsing et al. (CRYPTO 2024), and Baum et al. (CRYPTO 2025) have established EUF-CMA security for these signatures in the Quantum Random Oracle Model (QROM). However, their proofs do not account for crucial optimization techniques such as rejection sampling and grinding, rendering them inapplicable to practical schemes like the NIST round-2 candidates Mirath and RYDE.
This paper addresses this gap by analyzing the QROM security of MPC-in-the-Head signatures that incorporate these optimizations, with a focus on Mirath and RYDE. We make two main contributions:
1) We provide a new (strong) EUF-CMA security proof that accommodates rejection sampling and grinding. We also present a new EUF-NMA security proof compatible with these optimizations, by extending the techniques of Don et al. (CRYPTO 2022) and Aguilar-Melchor et al. (ASIACRYPT 2023).
2) We also point out a gap in the EUF-CMA security proof of the MPC-in-the-Head signature schemes using correlated-tree techniques, MQOM, SBC (Huth and Joux, CRYPTO 2024), and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025).
## 2025/2000
* Title: Trust, But Verify When Using the Powers of Tau
* Authors: Karim Baghery
* [Permalink](https://eprint.iacr.org/2025/2000)
* [Download](https://eprint.iacr.org/2025/2000.pdf)
### Abstract
To mitigate trust concerns in the setup phase of pairing-based zk-SNARKs, the primary solution has been the sampling of the Structured Reference String (SRS) using an MPC protocol. In 2017, Bowe, Gabizon, and Miers introduced the Powers of Tau MPC protocol for sampling a universal SRS, which has since become the main SRS generation protocol for numerous practical projects. The protocol's designers showed that for a circuit with $2^{21}$ multiplication gates, verifying the universal SRS for Groth16 zk-SNARK could take $55$ minutes for a single update. However, they clarified that "the verification is not run by individual users; it is done by the coordinator and anyone who wishes to verify the transcript of the protocol after completion". This note demonstrates the importance of verifying the final SRS by either $\textit{each}$ individual end-user or $\textit{all}$ ceremony participants to mitigate potential attacks. We discuss simple attack scenarios that highlight vulnerabilities if $\textit{each}$ end-user or $\textit{all}$ participants fail to verify the final SRS. Additionally, by leveraging batching and aggregating techniques, we introduce an efficient verification algorithm for the (original) Powers of Tau protocol, substantially reducing SRS verification time and making it practical even for large-scale ceremonies. In the case of rejection, a more efficient recursive verification approach aids in identifying malicious parties more effectively. This note aims to enhance procedural understanding of SRS generation ceremonies through the Powers of Tau protocol and improve the reliability of current ceremonies against potential threats.
## 2025/2001
* Title: On Computational VSS for General Access Structures
* Authors: Shahla Atapoor, Karim Baghery, Robin Jadoul, Barry van Leeuwen
* [Permalink](https://eprint.iacr.org/2025/2001)
* [Download](https://eprint.iacr.org/2025/2001.pdf)
### Abstract
Verifiable Secret Sharing (VSS) schemes are fundamental building blocks in distributed cryptography. While most existing works focus on threshold structures, many real-world applications require more general access structures, where participants have different levels of power and only certain subsets are authorized to reconstruct the secret. Existing computational VSS schemes for general access structures typically rely on Discrete Logarithm (DL)-based homomorphic commitments, which limits their applicability, particularly in scenarios requiring Post-Quantum (PQ) security. In this work, we present a generalized version of $\mathrm{\Pi}$, a unified framework introduced at PKC 2025 for constructing computational VSS schemes without relying on homomorphic commitments. Our framework supports arbitrary monotone $\mathcal{Q}_2$ access structures, encompassing replicated and threshold secret sharing (e.g., Shamir's scheme), while preserving the efficiency and modularity of $\mathrm{\Pi}$. Notably, it requires only a random oracle and any commitment scheme satisfying hiding and binding, making it compatible with a wide range of instantiations, including PQ-secure commitments. In particular, our hash-based instantiation yields the first symmetric-key-based VSS scheme for general access structures. Compared to prior general-access VSS schemes based on homomorphic commitments (e.g., variants of Pedersen scheme from FC 2003), our DL-based constructions eliminate the need for homomorphic commitments and achieve asymptotic improvements in verification and reconstruction costs. We believe that this extension enhances the versatility of the original $\mathrm{\Pi}$ framework and paves the way for its deployment in a broader range of practical distributed systems.
## 2025/2002
* Title: Pseudorandom Correlation Functions for Multiparty Beaver Triples from Sparse LPN
* Authors: Sebastian Hasler, Pascal Reisert
* [Permalink](https://eprint.iacr.org/2025/2002)
* [Download](https://eprint.iacr.org/2025/2002.pdf)
### Abstract
We construct a pseudorandom correlation function (PCF) for oblivious linear evaluation (OLE) from sparse LPN over any finite field. The programmability property of our PCF implies a PCF for any multiparty degree-two correlation, e.g., Beaver triples. Our PCF is the first PCF for degree-two correlations from a well-established cryptographic assumption, apart from (inefficient) generic PCFs based on homomorphic secret sharing or fully homomorphic encryption. Our PCF outperforms the previously fastest PCF for Beaver triples (Boyle et al., Crypto 2022) by 3.2-28x.
We build on the recent pseudorandom correlation generator (PCG) by Miao et al. (Asiacrypt 2025) and extend it to a PCF using a recursive approach similar to Braun et al. (Asiacrypt 2025). Moreover, we extend these techniques to support authenticated degree-two correlations in the important two-party case.
## 2025/2003
* Title: A Sparse Polynomial Multiplier for HQC Integrating Parallelism and Power-Based Side-Channel Countermeasures
* Authors: Jaeho Jeon, Suseong Lee, Myeongjun Kim, Eunyoung Seo, Myunghyun Cho, Seonggyeom Kim, Bo Gyeong Kang, Young-Sik Kim
* [Permalink](https://eprint.iacr.org/2025/2003)
* [Download](https://eprint.iacr.org/2025/2003.pdf)
### Abstract
The Hamming Quasi-Cyclic (HQC) scheme has recently been standardized as a post-quantum key encapsulation mechanism (KEM), emphasizing the importance of efficient and secure hardware realizations on embedded platforms. However, HQC relies heavily on sparserCodense polynomial multiplications, where conventional shift-and-add architectures remain both performance- and security-critical. In FPGA implementations, these multiplications dominate execution timerCooccupying 59.5%, 56.1%, and 58.3% of the total latency for KeyGen, Encap, and Decap, respectivelyrCoand are further vulnerable to correlation power analysis (CPA) due to deterministic, index-driven memory access patterns. As countermeasures, parallelization improves performance at the cost of additional area. Dummy insertion with random shuffling mitigates leakage but incurs extra cycle overhead.
To address this, we propose a co-designed dummy-inserted parallel shift-and-add multiplier for HQC. The design integrates dummy insertion and two-index parallelism in a complementary manner, achieving reduced cycles with area efficiency while providing intrinsic resistance to CPA. Implemented on a Xilinx Artix-7 FPGA, the proposed architecture achieves up to a 1.25|u speedup over the baseline sequential multiplier while maintaining nearrCostate-of-the-art arearCotime efficiencyrCoincurring only a 1.16|u AT overhead to simultaneously deliver accelerated performance and CPA resistance. Test Vector Leakage Assessment (TVLA) measurements and theoretical analysis confirm that the parallel architecture effectively suppresses power-based side-channel leakage and provides inherent resistance against CPArCoreducing significant leakage points from 4.29% to 0.09%. This work demonstrates that performance and side-channel resistance can be jointly optimized through synergistic hardwarerCoalgorithm co-design, offering a practical and scalable HQC accelerator for post-quantum embedded systems.
## 2025/2004
* Title: Re-randomization Attack on the Certificateless Encryption Scheme proposed by Guo et al.
* Authors: Nobuyuki Sugio, Keita Emura, Toshihiro Ohigashi
* [Permalink](https://eprint.iacr.org/2025/2004)
* [Download](https://eprint.iacr.org/2025/2004.pdf)
### Abstract
Guo, Li, and Qin proposed a lightweight certificateless encryption (CLE) scheme designed for IoT environments (\textit{Discover Computing}, 2025). This paper demonstrates that the proposed scheme does not achieve CCA security, contrary to the authors' claim. Specifically, we identify two critical points. First, since the ciphertext retains a multiplicative ElGamal structure, it can always be re-randomized using arbitrary randomness. Second, based on this property, an adversary can transform a challenge ciphertext into another valid ciphertext of the same plaintext, and then query the decryption oracle with the transformed ciphertext to recover the challenge plaintext. This attack exploits a definitional gap in the CCA game, where only direct decryption queries on the challenge ciphertext are prohibited. In this work, we formalize the attack procedure and verify its validity based on implementation.
## 2025/2005
* Title: Reactive Correctness, sINDCPA-D-Security and Deterministic Evaluation for TFHE
* Authors: Nigel Smart, Michael Walter
* [Permalink](https://eprint.iacr.org/2025/2005)
* [Download](https://eprint.iacr.org/2025/2005.pdf)
### Abstract
We examine the relationship between correctness definitions for Fully Homomorphic Encryption (FHE) and the associated security definitions. We show that reactive notions of correctness imply INDCPA-D and sINDCPA-D security. But that to obtain both INDCPA-D and sINDCPA-D security we need to use a randomized version of the evaluation procedure. Such randomized evaluation procedures cause problems in real life deployments of FHE solutions, so we then go on to show how one can de-randomize the evaluation procedure and still obtain sINDCPA-D security in the random oracle model for the specific FHE scheme of TFHE.
## 2025/2006
* Title: OmniBA: Round-Efficient BA with Quadratic Communication under Mixed Faults
* Authors: Simon Holmgaard Kamp, Julian Loss, Kartik Nayak, Kecheng Shi
* [Permalink](https://eprint.iacr.org/2025/2006)
* [Download](https://eprint.iacr.org/2025/2006.pdf)
### Abstract
We present a simple and efficient Byzantine Agreement protocol in the mixed fault model where up to $t$ parties can be Byzantine, up to $s$ parties can be send-omission, and up to $r$ parties can be receive-omission such that $2t+s+r<n$. Our synchronous protocol greatly improves over the efficiency of the state-of-the-art solution due to Loss and Stern [TCC '23]. Specifically, our protocol incurs an expected communication complexity of $O(n^2)$ instead of $O(n^5)$ in their construction, while maintaining the same resilience. Our protocol terminates in an expected constant number of rounds, provided that a constant fraction of parties are non-faulty.
## 2025/2007
* Title: k-Anonymous Group Signatures: Addressing Strict Content Moderation in End-to-End Secure Messaging Platforms
* Authors: Shalini Banerjee, Andrey Bozhko, Andy Rupp
* [Permalink](https://eprint.iacr.org/2025/2007)
* [Download](https://eprint.iacr.org/2025/2007.pdf)
### Abstract
We review k-anonymity in authentication schemes, group signatures and ring signatures. While existing constructions achieve unlinkability, they typically necessitate maintaining state or relying on computationally expensive tracing algorithms. We propose a stateless variant that is efficiently traceable, albeit necessarily fully linkable. To the best of our knowledge, our variant, which we call k-Anonymous Group Signatures (k-AGS), is the first scheme to combine both statelessness and efficient traceability.
Building upon our k-AGS framework, we design k-Anonymous Set Pre-Constrained Group Signatures (k-ASPCGS) which is a threshold extension of the Set Pre-Constrained Group Signatures (SPCGS) introduced by Bartusek et al. (EUROCRYPT 2023).
We show that our notions arise naturally in the context of lawful surveillance, particularly for end-to-end secure messaging platforms, where controlled traceability is essential. Beyond this setting, they may also help mitigate the impact of strict moderation policies in large-scale distributed asynchronous platforms (e.g. Facebook, whistleblowing portals) as well as in spam control, where false positives remain a persistent challenge.
## 2025/2008
* Title: Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space
* Authors: Alexandra Henzinger, Seyoon Ragavan
* [Permalink](https://eprint.iacr.org/2025/2008)
* [Download](https://eprint.iacr.org/2025/2008.pdf)
### Abstract
We build two-server private information retrieval (PIR) that achieves information-theoretic security and strong double-efficiency guarantees. On a database of $n > 10^6$ bits, the servers store a preprocessed data structure of size $1.5 \sqrt{\log_2 n} \cdot n$ bits and then answer each PIR query by probing $12 \cdot n^{0.82}$ bits in this data structure. To our knowledge, this is the first information-theoretic PIR with any constant number of servers that has quasilinear server storage $n^{1+o(1)}$ and polynomially sublinear server time $n^{1-\Omega(1)}$.
Our work builds on the PIR-with-preprocessing protocol of Beimel, Ishai, and Malkin (CRYPTO 2000). The insight driving our improvement is a compact data structure for evaluating a multivariate polynomial and its derivatives. Our data structure and PIR protocol leverage the fact that Hasse derivatives can be efficiently computed on-the-fly by taking finite differences between the polynomial's evaluations. We further extend our techniques to improve the state-of-the-art in PIR with three or more servers, building on recent work by Ghoshal, Li, Ma, Dai, and Shi (TCC 2025).
On a 55 GB database with 64-byte records, our two-server PIR encodes the database into a 1 TB data structure rCo which is 1,600,000$\times$ smaller than that of prior two-server PIR-with-preprocessing schemes, while maintaining the same communication and time per query. To answer a PIR query, the servers probe 102 MB from this data structure, requiring 550$\times$ fewer memory accesses than linear-time PIR. The main limitation of our protocol is its large communication complexity, which we show how to shrink to $n^{0.31} \cdot \mathsf{poly}(\lambda)$ using compact linearly homomorphic encryption.
## 2025/2009
* Title: When Randomness IsnrCOt Random: Practical Fault Attack on Post-Quantum Lattice Standards
* Authors: Hariprasad Kelassery Valsaraj, Prasanna Ravi, Shivam Bhasin
* [Permalink](https://eprint.iacr.org/2025/2009)
* [Download](https://eprint.iacr.org/2025/2009.pdf)
### Abstract
Post-quantum cryptographic schemes like ML-KEM and ML-DSA have been standardized to secure digital communication against quantum threats. While their theoretical foundations are robust, we identify a critical implementation-level vulnerability in both: a single point of failure centered on the random seed pointer used in polynomial sampling. By corrupting this pointer, an attacker can deterministically compromise the entire scheme, bypassing standard countermeasures. We present the first practical fault-injection attacks exploiting this weakness and validate them on an STM32H7 microcontroller using laser fault injection. Our results demonstrate full key and message recovery for ML-KEM and signature forgery for ML-DSA, with success rates up to 100%. We further verify the presence of this vulnerable implementation style in widely used public libraries, including PQM4, LibOQS, PQClean, and WolfSSL, and propose effective countermeasures to mitigate this overlooked yet severe threat.
## 2025/2010
* Title: On the Distribution of the Distances of Random Words
* Authors: Benjamin E. Diamond, Angus Gruen
* [Permalink](https://eprint.iacr.org/2025/2010)
* [Download](https://eprint.iacr.org/2025/2010.pdf)
### Abstract
For each positive integer $c^*$, we construct an infinite sequence of ReedrCoSolomon codes $C \subset \mathbb{F}_q^n$, together with ball radii $z$, for which the proportion of $\mathbb{F}_q^n$ collectively covered by the radius-$z$ Hamming balls decays asymptotically more slowly than $\frac{n^{c^*}}{q}$ does. To pinpoint this decay rate, we develop various new, sharp combinatorial estimates, pertaining to the volumes of balls and their intersections.
Our result proves that the capacity conjecture of Ben-Sasson, Carmon, Ishai, Kopparty and Saraf (J. ACM '23) is false. Our code families' relative rates converge to 0 and their relative radii converge to 1. We suggest avenues by the means of which the capacity conjecture might be resuscitated; roughly, we suggest that that conjecture be restricted to the case of families whose relative rates are bounded from below by a positive constant. Our work shows that many deployed SNARKs may be less secure than they were formerlyrCooptimisticallyrCoassumed to be.
## 2025/2011
* Title: When the Wrong Key Lives On: The Key-Recovery Procedure in Integral Attacks
* Authors: Christof Beierle, Gregor Leander, Yevhen Perehuda
* [Permalink](https://eprint.iacr.org/2025/2011)
* [Download](https://eprint.iacr.org/2025/2011.pdf)
### Abstract
An integral distinguisher for a block cipher is defined by a nontrivial subset of plaintexts for which the bitwise sum of (parts of) a certain internal state is independent of the secret key. Such a distinguishing property can be turned into a key-recovery procedure by partially decrypting the ciphertexts under all possible keys and then filtering the key candidates using the integral distinguisher. The behavior of this filter has never been analyzed in depth, and we show that the ubiquitous hypothesis about its behavior is incorrect.
Fortunately, the deviation is either limited or can be lifted to improve the underlying attacks. By algorithmically determining the exact subspaces of key candidates to be guessed - whose dimensions are often lower than expected - we are able to improve upon the best known integral key-recovery attacks on various ciphers.
## 2025/2012
* Title: Head Start: Digit Extraction in TFHE from MSB to LSB
* Authors: Jan-Pieter D'Anvers, Xander Pottier, Thomas de Ruijter, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/2012)
* [Download](https://eprint.iacr.org/2025/2012.pdf)
### Abstract
TFHE bootstrapping is typically limited to a small plaintext space, with an exponential increase in cost for larger plaintext spaces. To bootstrap larger integers, one can use digit decomposition, a procedure that iteratively extracts and bootstraps a part of the larger plaintext space. Conventional state-of-the-art methods typically extract bits starting from the least significant bits (LSBs) and progress to the most significant bits (MSBs). However, we introduce a DirtyMSB extraction procedure that enables the digit decomposition from MSBs to LSB for the first time. However, this procedure introduces a small error during the extraction procedure. We demonstrate how to compensate this error in subsequent iterations. Compared to traditional LSB-to-MSB digit decomposition, our method improves the throughput, with for example an increase of 20% for a 5-bit plaintext and 50% increase for an 8-bit plaintext. In contrast to LSB-to-MSB methods, our extracted output ciphertexts have fresh noise, allowing us to directly use the extracted outputs for further computation without the need for an additional bootstrap or less efficient parameters. We demonstrate the applicability of our method by improving large-scale addition and scalar multiplication. Our method is particularly effective for vector addition operations, accelerating the addition of 1000 16-bit numbers by a factor of $\times2.75$. Furthermore, we demonstrate a $\times2.27$ speedup over the state-of-the-art implementation of scalar multiplication.
## 2025/2013
* Title: MARS: Low-Leakage Multi Adversarial Owner and Reader Replication-free Searchable Encryption from Private Information Retrieval
* Authors: Benjamin Fuller, Arinjita Paul, Maryam Rezapour, Ronak Sahu, Amey Shukla
* [Permalink](https://eprint.iacr.org/2025/2013)
* [Download](https://eprint.iacr.org/2025/2013.pdf)
### Abstract
In searchable encryption, a data owner outsources data to a server while allowing efficient search by clients. A multimap associates keywords with a variable number of documents. We consider the setting with multiple owners and multiple clients (Wang and Papadopolous, Cloud Computing 2023). The goal is for each owner to store a multimap and grant access to clients. Prior work shares three weaknesses:
* Restricting patterns of adversarial behavior,
* Duplicating any data shared with a new client, and
* Leaking each client's access pattern and share pattern.
We present MARS, the first SSE for multiple owners and clients that considers security for an arbitrary collection of adversarial parties. Our scheme only leaks the volume of the result size and the number of requested keywords, both of which can be padded. No data is replicated.
Our scheme combines 1) private information retrieval (PIR) to protect search patterns, 2) efficient delegation of the ability to index keywords and decrypt records, and 3) tabulation hashing to allow a single query for locations associated with a keyword. The first two items can be thought of as a keyword unkeyed PIR where the data owner gives the client the identifiers for individual keywords and keys to decrypt records.
Our system is implemented on multimaps up to size $24$ million (the Enron dataset) with total time of $1.2$s for keywords that match $100$ documents. This is in comparison to a time $.500$s for Wang and Papadapolous, which replicates data and has access, sharing, and query equality leakage.
Storage overhead is a factor of $6.6$. Our implementation uses FrodoPIR as the underlying PIR. Our system can incorporate batch or doubly-efficient unkeyed PIR as their performance improves.
## 2025/2014
* Title: Multi-Splitting Forking Based Modular Security of Signatures in Multivariate Quadratic Setting
* Authors: Sanjit Chatterjee, Tapas Pandit, Subhabrata Samajder
* [Permalink](https://eprint.iacr.org/2025/2014)
* [Download](https://eprint.iacr.org/2025/2014.pdf)
### Abstract
This paper proposes modular security proofs for some identification scheme (IDS)-based signature schemes in the multivariate quadratic (MQ) setting. More precisely, our contributions include concrete security reduction for both 3-pass and 5-pass MQDSS signature schemes in the random oracle model. Although no formal security argument for the former was available in the literature, the one for the latter provides only a qualitative treatment. Our concrete analysis shows that the 3-pass scheme enjoys a comparatively tighter reduction. This result, considered in conjunction with a reported attack on the 5-pass MQDSS from the NIST PQC competition, thus indicates that contrary to the initial suggestion, the 3-pass MQDSS could be a better choice at a concrete security level. Our next focus is on the only blind signature scheme available in the MQ-setting, proposed by Petzoldt et al. While the security of the original scheme was discussed in a non-standard and significantly weak model; we propose a concrete security reduction for a slightly modified scheme in the standard one-more unforgeability (OMF) model.
Central to all our modular proofs are new forking algorithms. The forking algorithm/lemma has been widely used in the formal security reduction of numerous cryptographic schemes, mainly in the discrete logarithm and RSA setting. The abstractions proposed here allow multiple forkings at the same index while satisfying certain additional conditions for the underlying IDS in the MQ-setting. Thus, the forking algorithms capture the nuances of the MQ-setting while being agnostic of the underlying structure.
## 2025/2015
* Title: Proving Authenticated Key Exchange via Memory-Efficient Reductions
* Authors: Jiaxin Pan, Runzhi Zeng
* [Permalink](https://eprint.iacr.org/2025/2015)
* [Download](https://eprint.iacr.org/2025/2015.pdf)
### Abstract
We initiate the study of memory efficiency in proving the security of authenticated key exchange (AKE) protocols: We first revise the security model for AKE protocols in order to prove their security in a memory-efficient manner without comprising its capability of capturing usual attacks. We formally show that security in our model implies previous ones, and thus our model captures the same security as before.
After that we propose a generic construction of AKE from key encapsulation mechanisms (KEMs) and digital signature schemes, motivated by the signed Diffie-Hellman protocol. Under the multi-user security of the signature scheme and (relatively weak) oneway-security against plaintext checking attacks of the KEM, our generic construction is proven to be tightly secure (in terms of success probability) via memory-efficient reductions in the random oracle model. We refer to our reductions as memory-efficient rather than memory-tight, since their memory requirements grow proportionally with the number of users. This growth is not an artifact of our analysis, but rather stems from the necessity of solving the dictionary problem within our proof. By the result of Pagh (SIAM J. Computing, 2002), such user-dependent memory consumption is unavoidable. Nevertheless, our proof is more memory-efficient than the previous reductions for AKE, including even those that are non-tight. Given that most post-quantum assumptions (e.g., the Learning-With-Errors and Short-Integer-Solution assumptions) are memory-sensitive, our work holds significant value for post-quantum AKE protocols.
## 2025/2016
* Title: Constructions of a Family of Nonlinear Permutations of Any Possible Algebraic Degrees with the Optimal Threshold Implementations
* Authors: Zhaole Li, Deng Tang
* [Permalink](https://eprint.iacr.org/2025/2016)
* [Download](https://eprint.iacr.org/2025/2016.pdf)
### Abstract
Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. An attack exploiting these leakages is the differential power analysis (DPA). Threshold Implementation (TI), introduced by Nikova et al. [JoC 24(2):292-321, 2011], was proposed to resist DPA on hardware implementations of block ciphers and eliminate information leakage due to glitches. TI is based on secret sharing and multi-party computation. Since the cost of implementing a TI is directly proportional to the number of shares, minimizing the number of shares is of importance. Note that Nikova et al. proved that, for a target function of algebraic degree $t\geq 2$, the lower bound on the number of shares to implement a TI is $t+1$. And we call a TI with $t+1$ shares an optimal TI. However, achieving this bound is challenging. To date, the only universal construction for any bijective function of algebraic degree $t\geq 2$ achieves a TI with $t+2$ shares, which was proposed by Piccione et al. [IEEE TIT 69(10):6700-6710, 2023]. Only two studies managed to implement optimal TIs. They either concentrated on the Feistel structure or were based on Shannon's expansion. It should be noted that adding randomness can meet the $t+1$ bound, but generating randomness is expensive in practice. Consequently, this paper endeavors to fill this gap by systematically investigating the substitution-boxes (S-boxes to be brief) that can achieve optimal TIs without additional randomness. In this paper, inspired by the Feistel structure in the design of S-boxes, we present two constructions of bijective S-boxes with optimal TIs. Of particular interest is the S-boxes constructed from two permutations exhibiting nonzero nonlinearity, making them potential candidates for S-boxes with desirable properties. For applications, our constructions can interpret the existence of $3$-share or $4$-share TIs for certain functions in $3$, $4$ and $5$ variables, as previously reported by Bilgin et al. [CHES 7428:76-91, 2012] and Bo++ilov et al. [ToSC 2017(1):398-404, 2017], including $\mathcal{Q}_5^{25}$, which cannot be interpreted by the previous works. We also give the bijective S-boxes, which are Examples 4 to 11, that possess the optimal TIs by our results.
## 2025/2017
* Title: Secure Onion Encryption and the Case of Counter Galois Onion
* Authors: Jean Paul Degabriele, Alessandro Melloni, Martijn Stam
* [Permalink](https://eprint.iacr.org/2025/2017)
* [Download](https://eprint.iacr.org/2025/2017.pdf)
### Abstract
The recently introduced Counter Galois Onion (CGO) is a new symmetric onion encryption scheme designed to replace the current one used by Tor, with integration in TorrCOs Rust implementation Arti ongoing. Intuitively, CGO uses an updatable tweakable split-domain cipher as its building block, which provides it with the necessary non-malleability properties while attaining better performance than the alternative approach of realising it from a wide blockcipher (with full SPRP security). However, onion encryption as used in Tor with various functionality features and security trade-offs, is not that well-studied by the cryptographic community. As a result, the requirements of this important primitive which protects the privacy of millions of users on a daily basis, is not well understood and whether CGO fulfills all its security goals unclear.
In this work, we initiate the study of real-world symmetric onion encryption by presenting a new security model capturing TorrCOs leaky pipes functionality, associated data, and partial forward security, neither of which were covered previously. We then use this new security model to solidify the security claims of CGO in the forward direction by proving that if the underlying primitive is a suitably secure tweakable split-domain cipher, then CGO is a secure onion encryption scheme.
## 2025/2018
* Title: Batched and Packed (Publicly) Verifiable Secret Sharing: A Unified Framework and Applications
* Authors: Shahla Atapoor, Karim Baghery, Georgio Nicolas, Robi Pedersen, Jannik Spiessens
* [Permalink](https://eprint.iacr.org/2025/2018)
* [Download](https://eprint.iacr.org/2025/2018.pdf)
### Abstract
Verifiable Secret Sharing (VSS) allows a dealer to distribute a secret among $n$ parties so that each can verify their share's validity, and any qualified subset can reconstruct the secret. Publicly Verifiable Secret Sharing (PVSS) extends VSS by enabling anyone to verify the correctness of distributed shares. Both VSS and PVSS schemes are core building blocks in many cryptographic applications. We introduce a $k$-batched and $l$-packed extension of \pie, a unified framework from PKC 2025 for Shamir-based computational VSS in the synchronous setting with optimal resilience. Our framework enables the sharing and verification of $l\times k$ secrets in a single protocol execution, offering a tunable trade-off between efficiency and robustness: the $k$-batched, non-packed variant ($l=1$) improves performance while maintaining optimal resilience, whereas the $k$-batched, $l$-packed variant achieves even greater efficiency at the cost of slightly reduced fault tolerance. Using this framework, we construct several Batched and Packed (BP) VSS and PVSS schemes that significantly reduce both computational and communication costs for the dealer and parties. When sharing many secrets, two of our VSS schemes and our PVSS scheme perform almost as efficiently as plain Shamir sharing. For example, when sharing more than 100 secrets, the overhead of our hash-based BP-VSS is below 3%, for our BP-VSS with information-theoretic privacy it remains around 8%, and for our BP-PVSS it is under 2%. These results show that verifiability in Shamir secret sharing can be achieved in post-quantum and large-scale settings with negligible overhead for the dealer. Our proposed BP-PVSS scheme is the first that can achieve these properties and outperforms existing state-of-the-art protocols. As an application, we show that our BP-PVSS yields substantial performance improvements for the ALBATROSS randomness generation protocol from ASIACRYPT 2020.
## 2025/2019
* Title: Practical Multi-party Private Set Intersection with Reducible Zero-sharing
* Authors: Yewei Guan, Hua Guo, Man Ho Au, Jiarong Huo, Jin Tan, Zhenyu Guan
* [Permalink](https://eprint.iacr.org/2025/2019)
* [Download](https://eprint.iacr.org/2025/2019.pdf)
### Abstract
Multi-party Private Set Intersection (mPSI) enables $n(n\geq3)$ parties, each holding a set of size $m$, to jointly compute their intersection while preserving the confidentiality of each set, which is essential for privacy-preserving data analysis and secure database queries. Existing mPSI protocols have limitations in achieving both sufficient security and practical efficiency.
This paper presents a novel and efficient mPSI construction in the semi-honest model while resisting arbitrary collusion attacks. Our construction works in the offline/online paradigm. Given the corruption threshold $t$, the online phase achieves linear total computational and communication complexity, that is $O((n+t)m)$, and solely uses symmetric operations. This makes our construction theoretically outperform the existing works. The technical core of the construction is our newly extracted primitive called reducible zero-sharing, which allows $t(t<n)$ parties to obtain shares of zero for items in the intersection of $n$ parties' input set, while resisting up to $t-1$ colluding parties. We present a practical construction of reducible zero-sharing in the offline/online paradigm by leveraging the homomorphic property of oblivious key-value store (OKVS).
With extensive experiments, we demonstrate that our construction outperforms state-of-the-art works in terms of online running time and communication cost. Specifically, compared to works with sufficient security, the online running time of our mPSI construction is $9.57-114.46\times$ faster in the LAN setting, $2.69-28.41\times$ faster in the WAN setting, while the communication cost is $0.29-28.70\times$ lower. Notably, the total performance (offline+online) still obtains up to $18.73\times$ improvement. Compared with works with practical efficiency, our mPSI construction achieves similar performance while providing stronger security.
## 2025/2020
* Title: VerfCNN, Optimal Complexity zkSNARK for Convolutional Neural Networks * Authors: Wenjie Qu, Yanpei Guo, Yue Ying, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2025/2020)
* [Download](https://eprint.iacr.org/2025/2020.pdf)
### Abstract
With the widespread deployment of machine learning services, concerns about potential misconduct by service providers have emerged. Providers may deviate from their promised methodologies when delivering their services, undermining customer trust. Zero-knowledge proofs (ZKPs) offer a promising solution for customers to verify service integrity while preserving the intellectual property of the model weights. However, existing ZKP systems for convolutional neural networks (CNNs) impose significant computational overhead on the prover, hindering their practical deployment.
To address this challenge and facilitate real-world deployment of ZKPs for CNNs, we introduce VerfCNN, a novel and efficient ZKP system for CNN inference. The core innovation of VerfCNN lies in a specialized protocol for proving multi-channel convolutions, achieving optimal prover complexity that matches the I/O size of the convolution. Our design significantly reduces the prover overhead for verifiable CNN inference. Experiments on VGG-16 demonstrate that our system achieves a prover time of just 12.6 seconds, offering a 6.7|u improvement over zkCNN (CCS'21).
Remarkably, VerfCNN incurs only a 10|u overhead compared to plaintext inference on CPU, whereas general-purpose zkSNARKs typically impose overheads exceeding 1000|u. These results underscore VerfCNN's strong potential to enhance the integrity and transparency of real-world ML services.
## 2025/2021
* Title: TreeCast: Multi-Party Key Establishment Protocol for IoT Devices
* Authors: Supriyo Banerjee, Sayon Duttagupta
* [Permalink](https://eprint.iacr.org/2025/2021)
* [Download](https://eprint.iacr.org/2025/2021.pdf)
### Abstract
Secure communication in the Internet of Things (IoT) requires lightweight protocols that scale across unicast, multicast, and broadcast settings. Existing solutions typically depend on centralized gateways, which introduce single points of failure and scalability limitations. We present TreeCast, a decentralized group key establishment protocol that organizes devices in a binary tree and derives communication keys through hybrid key exchange. The protocol achieves efficient and scalable key management, supporting dynamic membership with localized rekeying. We provide a formal security analysis and proof, showing that TreeCast achieves authentication, session key confidentiality, post-compromise security, and partial forward secrecy. In addition, we evaluate computational and storage costs of the protocol, demonstrating logarithmic scalability in both communication overhead and device state. By enabling a single framework for unicast, multicast, and broadcast communication, our approach bridges the gap between cryptographic rigor and practical IoT deployment. TreeCast provides a deployable, communication-oriented solution to secure large-scale IoT networks.
## 2025/2022
* Title: Formal Verification of Privacy Pass
* Authors: Kristiana Ivanova, Daniel Gardham, Stephan Wesemeyer
* [Permalink](https://eprint.iacr.org/2025/2022)
* [Download](https://eprint.iacr.org/2025/2022.pdf)
### Abstract
CAPTCHA is a ubiquitous challenge-response system for preventing spam (typically bots) on the internet. Requiring users to solve visual challenges, its design is inherently cumbersome, and can unfairly punish those using low reputation IP addresses, such as anonymous services e.g. TOR.
To minimise the frequency in which a user must solve CAPTCHAs, Privacy Pass (PETS 2018) allows users to collect and spend anonymous tokens instead of solving challenges. Despite 400,000 reported monthly users and standardisation efforts by the IETF, it has not been subject of formal verification, which has been proven to be a valuable tool in security analysis.
In this paper we perform the first analysis of Privacy Pass using formal verification tools, and verify standard security properties hold in the symbolic model. Motivated by concerns of Davidson et al. and the IETF contributors, we also explore a stronger attack model, where additional key leakage uncovers a potential token forgery. We present a new protocol, Privacy Pass Plus, in which we show the attack fails in the symbolic model and give new cryptographic reductions to show our scheme maintains the security properties. Moreover, our work also highlights the complementary nature of analysing protocols in both symbolic and computational models.
## 2025/2023
* Title: Select-Then-Compute: Encrypted Label Selection and Analytics over Distributed Datasets using FHE
* Authors: Nirajan Koirala, Seunghun Paik, Sam Martin, Helena Berens, Tasha Januszewicz, Jonathan Takeshita, Jae Hong Seo, Taeho Jung
* [Permalink](https://eprint.iacr.org/2025/2023)
* [Download](https://eprint.iacr.org/2025/2023.pdf)
### Abstract
Private Set Intersection (PSI) protocols allow a querier to determine whether an item exists in a dataset without revealing the query or exposing non-matching records. It has many applications in fraud detection, compliance monitoring, healthcare analytics, and secure collaboration across distributed data sources. In these cases, the results obtained through PSI can be sensitive and even require some kind of downstream computation on the associated data before the outcome is revealed to the querier, computation that may involve floating-point arithmetic, such as the inference of a machine learning model. Although many such protocols have been proposed, and some of them even enable secure queries over distributed encrypted sets, they fail to address the aforementioned real-world complexities.
In this work, we present the first encrypted label selection and analytics protocol construction, which allows the querier to securely retrieve not just the results of intersections among identifiers but also the outcomes of downstream functions on the data/label associated with the intersected identifiers. To achieve this, we construct a novel protocol based on an approximate CKKS fully homomorphic encryption that supports efficient label retrieval and downstream computations over real-valued data. In addition, we introduce several techniques to handle identifiers in large domains, e.g., 64 or 128 bits, while ensuring high precision for accurate downstream computations.
Finally, we implement and benchmark our protocol, compare it against state-of-the-art methods, and perform evaluation over real-world fraud datasets, demonstrating its scalability and efficiency in large-scale use case scenarios. Our results show up to 1.4$\times$ to 6.8$\times$ speedup over prior approaches and select and analyze encrypted labels over real-world datasets in under 65 sec., making our protocol practical for real-world deployments.
--- Synchronet 3.21a-Linux NewsLink 1.2