From Newsgroup: sci.crypt

## In this issue
1. [2025/1835] Who Verifies the Verifiers? Lessons Learned From ...
2. [2025/2238] arya-STARK: Aggregation-Robust Yet Authentic ...
3. [2025/2239] Rejection-Free Framework of Zero-Knowledge Proof ...
4. [2025/2240] On the Cryptographic Resilience of MDS Matrices
5. [2025/2241] LEAF: Lightweight and Efficient Hardware ...
6. [2025/2242] Sanitizable Signatures with Different Admissibility ...
7. [2025/2243] On The Dolev-Yao Model of Symmetric Cascade Protocol
8. [2025/2244] Swarm in EM Hay: Particle Swarm-guided Probe ...
9. [2025/2245] An Extended PUF-based Protocol
10. [2025/2246] Too Easy Fault Injection Attacks on Learning with ...
11. [2025/2247] Beyond Incentive Compatibility: Rational Harm-Proof ...
12. [2025/2248] Learning from Leakage: Database Reconstruction from ...
13. [2025/2249] Revisiting Sum-check-based Polynomial Commitment ...
14. [2025/2250] Nimbus: Secure and Efficient Two-Party Inference ...
15. [2025/2251] An Efficient Private GPT Never Autoregressively Decodes
16. [2025/2252] Bridging Keyword PIR and Index PIR via MPHF and ...
17. [2025/2253] Efficient Privacy-Preserving Blueprints for ...
18. [2025/2254] Multi-Party Private Join
19. [2025/2255] LPG: Raise Your Location Privacy Game in Direct-to- ...
20. [2025/2256] Scalable Private Set Intersection over Distributed ...
21. [2025/2257] \textsc{Npir}: High-Rate PIR for Databases with ...
22. [2025/2258] On the Equivalence of Polynomial Commitments for an ...
23. [2025/2259] HQC Beyond the Standard: Ciphertext Compression and ...
24. [2025/2260] Tight Generic PRF Security of HMAC and NMAC
25. [2025/2261] TSS-PV: Traceable Secret Sharing with Public ...
26. [2025/2262] Certified-Everlasting Quantum NIZK Proofs
27. [2025/2263] Completing Policy-based Anonymous Tokens: Private ...
28. [2025/2264] Leakage-Resilient Multi-Party Computation: ...
29. [2025/2265] PRGUE Schemes: Efficient Updatable Encryption With ...
30. [2025/2266] Breaking UOV Encryption: Key Recovery Attack On Olivier
31. [2025/2267] How to Compare Bandwidth Constrained Two-Party ...
32. [2025/2268] On the Pitfalls of Modeling Individual Knowledge
33. [2025/2269] Accelerating FrodoKEM in Hardware
34. [2025/2270] HHGS: Forward-secure Dynamic Group Signatures from ...
35. [2025/2271] ARION: Attention-Optimized Transformer Inference on ...
36. [2025/2272] High Exponents May Not Suffice to Patch AIM N+eOn ...
37. [2025/2273] Benchmarking SLH-DSA: A Comparative Hardware ...
38. [2025/2274] Post-Quantum Security of the Sum of Even-Mansour
39. [2025/2275] Random-Access AEAD for Fast Lightweight Online ...
40. [2025/2276] E2E-AKMA: An End-to-End Secure and Privacy- ...
## 2025/1835
* Title: Who Verifies the Verifiers? Lessons Learned From Formally Verified Line-Point Zero-Knowledge
* Authors: Sabine Oechsner, Vitor Pereira, Peter Scholl
* [Permalink](https://eprint.iacr.org/2025/1835)
* [Download](https://eprint.iacr.org/2025/1835.pdf)
### Abstract
Computer-aided cryptography, with particular emphasis on formal verification, promises an interesting avenue to establish strong guarantees about cryptographic primitives. The appeal of formal verification is to replace the error-prone pen-and-paper proofs with a proof that was checked by a computer and, therefore, does not need to be checked by a human. In this paper, we ask the question of how reliable are these machine-checked proofs by analyzing a formally verified implementation of the Line-Point Zero-Knowledge (LPZK) protocol (Dittmer, Eldefrawy, Graham-Lengrand, Lu, Ostrovsky and Pereira, CCS 2023). The implementation was developed in EasyCrypt and compiled into OCaml code that was claimed to be high-assurance, i.e., that offers the formal guarantees of guarantees of completeness, soundness, and zero knowledge.
We show that despite these formal claims, the EasyCrypt model was flawed, and the implementation (supposed to be high-assurance) had critical security vulnerabilities. Concretely, we demonstrate that: 1) the EasyCrypt soundness proof was incorrectly done, allowing an attack on the scheme that leads honest verifiers into accepting false statements; and 2) the EasyCrypt formalization inherited a deficient model of zero knowledge for a class of non-interactive zero knowledge protocols that also allows the verifier to recover the witness. In addition, we demonstrate 3) a gap in the proof of the perfect zero knowledge property of the LPZK variant of Dittmer, Ishai, Lu and Ostrovsky (CCS 2022) that the EasyCrypt proof is based, which, depending on the interpretation of the protocol and security claim, could allow a malicious verifier to learn the witness.
Our findings highlight the importance of scrutinizing machine-checked proofs, including their models and assumptions. We offer lessons learned for both users and reviewers of tools like EasyCrypt, aimed at improving the transparency, rigor, and accessibility of machine-checked proofs. By sharing our methodology and challenges, we hope to foster a culture of deeper engagement with formal verification in the cryptographic community.
## 2025/2238
* Title: arya-STARK: Aggregation-Robust Yet Authentic Training via STARK Proofs * Authors: Abdoul Ahad FALL
* [Permalink](https://eprint.iacr.org/2025/2238)
* [Download](https://eprint.iacr.org/2025/2238.pdf)
### Abstract
We present arya-STARK, a unified post-quantum secure framework that enables Aggregation-Robust Yet Authentic training in Federated Learning through transparent zk-STARK proofs. Current federated learning deployments remain vulnerable to malicious or Byzantine clients capable of submitting statistically valid yet adversarial gradients, while also relying on quantum-fragile primitives for authentication. arya-STARK bridges these gaps by combining (i) transparent, hash-based zk-STARK proofs to verify gradient-descent updates at the AIR level, (ii) CRYSTALS-Dilithium signatures to guarantee post-quantum authentication of client commitments, and (iii) a Byzantine-resilient aggregation layer integrating $\ell_2$-clipping and trimmed-mean filtering to mitigate poisoning and backdoor attacks. We introduce a new finite-field encoding scheme that supports exact reconstruction of signed real-valued gradients inside STARK execution traces, enabling full verifiability without leaking client data. Our Rust-based proof-of-concept demonstrates that arya-STARK achieves scalable proof generation, microsecond-level verification, and strong robustness against up to 20% Byzantine clients while preserving high model accuracy. To our knowledge, this is the first system to unify post-quantum authentication, transparent zero-knowledge verification, and Byzantine-robust aggregation into a single architecture for secure federated learning.
## 2025/2239
* Title: Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE
* Authors: Antoine Douteau, Adeline Roux-Langlois
* [Permalink](https://eprint.iacr.org/2025/2239)
* [Download](https://eprint.iacr.org/2025/2239.pdf)
### Abstract
Commit-and-prove zero-knowledge proofs are a generalized version of zero-knowledge protocols that permit proving relations over the committed elements in addition testifying to its knowledge of the initial message. For example, the existing framework (LNP, Crypto22) allow a user to prove that the secret element committed satisfies quadratic relations with bounded norm (rao2 or raoreR). Security of these frameworks, regarding the zero knowledge property, is mainly assumed by the use of rejection sampling introduced by Lyubashevsky (Asiacrypt09). The main problems with rejection sampling are non-constant time execution and the cost of protecting this step from side-channel attacks.
Our contribution is a new framework of proof for zero-knowledge property that proves knowledge and quadratic relations over lattices without basing the security over rejection sampling. The security of our framework is based on the recent Hint-MLWE (KLSS, Crypto23) assumption.
This variant of MLWE gives additional hints about the secret in addition to the original input, and is shown to be as hard as its associated MLWE instance when secrets follow discrete Gaussian distributions.
## 2025/2240
* Title: On the Cryptographic Resilience of MDS Matrices
* Authors: Kamil Otal, Ali Mert S|+l|oe, O-fuz Yayla
* [Permalink](https://eprint.iacr.org/2025/2240)
* [Download](https://eprint.iacr.org/2025/2240.pdf)
### Abstract
The zero-difference attack on AES, introduced by Bardeh and Rijmen in [ToSC 2022(2):43--62], exploits some structural properties -referred to as related differentials- in the AES MDS matrix. Daemen and Rijmen earlier demonstrated that these related differentials appear not only in the AES MixColumns matrix but in all $4\times 4$ circulant MDS matrices [CCDS 2009(1):47--69]. In the same paper, they also showed an example of $4\times 4$ Hadamard MDS matrices for which there exists no related differentials. Combining both results, we can say for example that some $4\times 4$ Hadamard MDS matrices are more ``secure" than any $4\times 4$ circulant MDS matrices.

Recently, Jha et al. investigated whether it is possible to characterize $4\times 4$ Hadamard MDS matrices for which we can find no related differentials in [ IACR Commun. Cryptol. 2(1): 37 (2025)]. As a result, they gave a systematic method to construct such ``secure" matrices with respect to their parameters.

In this paper, we investigate the same problem for all $2\times 2$ and $3\times 3$ matrices to understand the cryptographic resilience of MDS matrices both theoretically and practically. As a result, we obtain the following results:
- There are no related differentials for any $2\times 2$ MDS matrices.
- There exist related differentials for all $3\times 3$ circulant MDS matrices. - There exist related differentials for all $3\times 3$ involutory MDS matrices when the finite field has even size.
- We characterize all $3\times 3$ MDS matrices for which there exist no related differentials when the size of the finite field is even.

In this way, we fill a gap for the cryptographic resilience problem of MDS matrices over finite fields.
## 2025/2241
* Title: LEAF: Lightweight and Efficient Hardware Accelerator for Signature Verification of FALCON
* Authors: Samuel Coulon, Jinjun Xiong, Jiafeng Xie
* [Permalink](https://eprint.iacr.org/2025/2241)
* [Download](https://eprint.iacr.org/2025/2241.pdf)
### Abstract
Along with the National Institute of Standards and
Technology (NIST) post-quantum cryptography (PQC) stan-
dardization process, efficient hardware acceleration for PQC
has become a priority. Among the NIST-selected PQC digital
signature schemes, FALCON shows great promise due to its
compact key sizes and efficient Signature Verification procedure.
However, FALCON is regarded as highly computationally com-
plex, and as a result, few works for hardware acceleration of
FALCON can be found in the literature, where the few existing
ones only target high-performance. To fill the gap, this paper
presents a Lightweight and Efficient hardware accelerator for the
Signature Verification portion of FALCON (LEAF), specifically for resource-constrained applications. We propose an efficient design
strategy, including a novel data dependence flow, to maximize the
utilization of very small resources for all arithmetic procedures.
Then, the proposed full-hardware LEAF is built, containing an
ultra-lightweight number theoretical transform (NTT) core with
a novel twiddle factor access pattern. Finally, we conduct a
thorough evaluation to demonstrate the efficiency of LEAF. To
the best of our knowledge, this is the first lightweight and mean-
while most resource-efficient FALCON Signature Verification full-
hardware accelerator in the literature, offering 65% and 66%
less aggregate resource usage and achieving 24% and 14% less
equivalent area-time product (eATP), compared to the state-of-
the-art for FALCON-512 and FALCON-1024, respectively. We hope
that this work can spur further research in the field.
## 2025/2242
* Title: Sanitizable Signatures with Different Admissibility Policies for Multiple Sanitizers
* Authors: Osama Allabwani, Olivier Blazy, Pascal Lafourcade, Charles Olivier-Anclin, Olivier Raynaud
* [Permalink](https://eprint.iacr.org/2025/2242)
* [Download](https://eprint.iacr.org/2025/2242.pdf)
### Abstract
Sanitizable signatures authorize semi-trusted sanitizers to modify admissible blocks of a signed message. Most works consider only one sanitizer while those considering multiple sanitizers are limited by their capacity to manage admissible blocks which must be the same for all of them. We study the case where different sanitizers with different roles can be trusted to modify different blocks of the message. We define a model for multi-sanitizer sanitizable signatures which allow managing authorization for each sanitizer independently. We also provide formal definitions of its security properties. We propose two secure generic constructions FSV-k-SAN and IUT-k-SAN with different security properties. We implement both constructions and evaluate their performance on a server and a smartphone.
## 2025/2243
* Title: On The Dolev-Yao Model of Symmetric Cascade Protocol
* Authors: Varsha Jarali, Shashi Kant Pandey
* [Permalink](https://eprint.iacr.org/2025/2243)
* [Download](https://eprint.iacr.org/2025/2243.pdf)
### Abstract
Security protocols enable authentication, key distribution, and secure information exchange, making them essential for network security, yet flaws in their design can lead to attacks. To prevent this, formal verification methods are vital for analyzing protocol correctness. The DolevrCoYao (DY) \cite{Dy} model introduced formalization for name-stamp and cascade protocols, where users apply public-key operations on messages. Brook and Otto \cite{DY-extension} later distinguished between symmetric and non-symmetric cascade protocols, noting that all DY cases were symmetric and that attacker choices were not fully addressed. They highlighted the incomplete characterization of an attackerrCOs power as an open problem. In this work, we extend the DY model by systematically analyzing all remaining symmetric two-party cascade protocol cases, aiming to provide a more complete foundation for building formal verification tools.
## 2025/2244
* Title: Swarm in EM Hay: Particle Swarm-guided Probe Placement for EM SCA
* Authors: Dev Mehta, Seyedmohammad Nouraniboosjin, Maryam S. Safa, Shahin Tajik, Fatemeh Ganji
* [Permalink](https://eprint.iacr.org/2025/2244)
* [Download](https://eprint.iacr.org/2025/2244.pdf)
### Abstract
Despite decades of research in electromagnetic (EM) side-channel analysis (SCA), practical attacks still require manual effort and domain expertise to identify informative probe locations on target devices.
Existing approaches rely heavily on exhaustive grid scanning or handcrafted alignment, limiting attack scalability and realism.
In this work, we present the first automated and adaptive EM SCA framework that uses particle swarm optimization (PSO) to navigate the probe.
Particles are guided by mutual information (MI) leakage maps, enabling efficient recovery of secret-dependent emissions.
We introduce a novel application of the Nystr||m approximation to accelerate MI estimation across EM trace windows, allowing real-time swarm guidance without full kernel computations.
Unlike prior work, our method requires no leakage templates, manual tuning, or alignment assistance, enabling automated attacks with minimal assumptions.
We validate our framework on both microcontroller and FPGA platforms running AES-128.
PSO-guided scanning identifies high-leakage points faster than grid search and reduces the number of traces required for successful CPA-based key recovery by up to a factor of 16, i.e., saving tens of thousands of traces.
## 2025/2245
* Title: An Extended PUF-based Protocol
* Authors: Francesco Berti, Itamar Levi
* [Permalink](https://eprint.iacr.org/2025/2245)
* [Download](https://eprint.iacr.org/2025/2245.pdf)
### Abstract
We extend a PUF-based authentication protocol with
key refresh, hierarchical groups, and revocation. Our framework
enables secure communication among enrolled devices without
server interaction, allowing group leaders to derive subordinate
keys and the server to exclude compromised parties through
controlled key updates.
## 2025/2246
* Title: Too Easy Fault Injection Attacks on Learning with Rounding (LWR)
* Authors: Francesco Berti, Sasha Petri, Itamar Levi
* [Permalink](https://eprint.iacr.org/2025/2246)
* [Download](https://eprint.iacr.org/2025/2246.pdf)
### Abstract
We present an extend-and-prune fault Injection
attack on serial implementations of Learning With Rounding
that drop the least-significant bits. By iteratively isolating and
recovering progressively larger key portions via faults, the attack
recovers the secret key.
## 2025/2247
* Title: Beyond Incentive Compatibility: Rational Harm-Proof Transaction Fee Mechanisms
* Authors: Forest Zhang, Elain Park, Ke Wu
* [Permalink](https://eprint.iacr.org/2025/2247)
* [Download](https://eprint.iacr.org/2025/2247.pdf)
### Abstract
On a blockchain, users compete for scarce block space in an auction run by the miner to get their transactions confirmed in the block. This auction is called transaction fee mechanism (TFM). Recent work [Rou21, CS23, SCW23] has been focused on incentive compatibility (IC), requiring that honest behavior maximizes the payoff for each type of strategic player: users, the miner, or minerrCouser coalitions. In this work, we introduce rational-harm proofness (RHP), which rules out any deviation that harms honest parties without also reducing the deviatorrCOs own utility. RHP closes a gap left by IC: IC does not forbid utility neutral yet externally harmful deviations. For example, in a second-price auction, the second-highest bidder can increase the winnerrCOs payment without affecting their own payoff. Such deviation is eliminated by RHP.
We characterize TFMs satisfying RHP alongside incentive compatibility for users (UIC) and miners (MIC). For finite block size, we develop a complete characterization in two models:
- In the plain model rCowhere a single miner unilaterally implements the auctionrCowe prove a tetrilemma (3-out-of-4 impossibility): among the four desired properties positive miner revenue, UIC, MIC, RHP against minerrCouser coalitions, no mechanism achieves all four simultaneously. Meanwhile, any three are jointly achievable in the plain model.
- In the MPC-assisted model rCowhere a committee of miners jointly implement the auction via multi-party computation (MPC)rCowe construct a randomized TFM with a positive miner revenue that achieves UIC, MIC, and RHP against all three types of strategic players. We further show that randomness is necessary: any deterministic TFM satisfying UIC and RHP in this model must confirm no transactions when the number of users exceeds the block size.
Finally, we show that IC and RHP are incomparable: for each strategic role, there are mechanisms satisfying one but not the other in both models. Our results broaden the design objectives for TFMs: beyond incentive compatibility, mechanisms should also preclude costless harm to honest participants
## 2025/2248
* Title: Learning from Leakage: Database Reconstruction from Just a Few Multidimensional Range Queries
* Authors: Peijie Li, Huanhuan Chen, Evangelia Anna Markatou, Kaitai Liang
* [Permalink](https://eprint.iacr.org/2025/2248)
* [Download](https://eprint.iacr.org/2025/2248.pdf)
### Abstract
Searchable Encryption (SE) has shown a lot of promise towards enabling secure and efficient queries over encrypted data. In order to achieve this efficiency, SE inevitably leaks some information, and a big open question is how dangerous this leakage is. While prior reconstruction attacks have demonstrated effectiveness in one-dimensional settings, extending them to high-dimensional datasets remains challenging. Existing methods either demand excessive query information (e.g. an attacker that has observed all possible responses) or produce low-quality reconstructions in sparse databases. In this work, we present REMIN, a new leakage-abuse attack against SE schemes in multi-dimensional settings, based on access and search pattern leakage from range queries. Our approach leverages unsupervised representation learning to transform query co-occurrence frequencies into geometric signals, allowing the attacker to infer relative spatial relationships between records. This enables accurate and scalable reconstruction of high-dimensional datasets under minimal leakage. We begin with a passive adversary that persistently observes all encrypted queries and responses, and later extend our analysis to an more active attacker capable of poisoning the dataset. Furthermore, we introduce REMIN-P, a practical variant of the attack that incorporates a poisoning strategy. By injecting a small number of auxiliary anchor points REMIN-P significantly improves reconstruction quality, particularly in sparse or boundary regions. We evaluate our attacks extensively on both synthetic and real-world structured datasets. Compared to state-of-the-art reconstruction attacks, our reconstruction attack achieves up to 50% reduction in mean squared error (MSE), all while maintaining fast and scalable runtime. Our poisoning attack can further reduce MSE by an additional 50% on average, depending on the poisoning strategy.
## 2025/2249
* Title: Revisiting Sum-check-based Polynomial Commitment Schemes
* Authors: Yuncong Zhang
* [Permalink](https://eprint.iacr.org/2025/2249)
* [Download](https://eprint.iacr.org/2025/2249.pdf)
### Abstract
The sum-check protocol is a fundamental building block in succinct arguments. However, its security formalization is often tightly coupled with the larger protocol in which it is embedded, making modular design and analysis challenging. To address this limitation, we introduce \emph{functional proof systems (FPS)}, generalizing interactive proof systems by viewing the verifier as a function parameterized by the prover, and defining security by asserting properties of this function. This novel perspective not only enables a clean, self-contained security definition for sum-check, but also opens possibility for designing and formalizing security of protocols that prove statements dynamically generated during the protocol---both tasks are difficult for traditional proof systems.
We develop a framework for composing multiple FPSs by executing them in parallel, and analyzing security of the composite protocol. We apply this framework to analyze existing protocols, including BaseFold, a popular polynomial commitment scheme, and BulletProofs, a well-known inner product argument, providing more modular and simpler security proofs than their original analysis. Particularly for BaseFold, our security proof avoids the need for introducing a new variant of correlated agreement theorem, thus building its security directly on the well-studied theorems of FRI. Finally, we construct a new transparent, pairing-free, doubly efficient, and homomorphically additive polynomial commitment scheme by composing existing protocols, demonstrating the practical utility of our framework for designing novel cryptographic schemes.
## 2025/2250
* Title: Nimbus: Secure and Efficient Two-Party Inference for Transformers
* Authors: Zhengyi Li, Kang Yang, Jin Tan, Wen-jie Lu, Haoqi Wu, Xiao Wang, Yu Yu, Derun Zhao, Yancheng Zheng, Minyi Guo, Jingwen Leng
* [Permalink](https://eprint.iacr.org/2025/2250)
* [Download](https://eprint.iacr.org/2025/2250.pdf)
### Abstract
Transformer models have gained significant attention due to their power in machine learning tasks. Their extensive deployment has raised concerns about the potential leakage of sensitive information during inference. However, when being applied to Transformers, existing approaches based on secure two-party computation (2PC) bring about efficiency limitations in two folds: (1) resource-intensive matrix multiplications in linear layers, and (2) complex non-linear activation functions like $\mathsf{GELU}$ and $\mathsf{Softmax}$. This work presents a new two-party inference framework $\mathsf{Nimbus}$ for Transformer models. For the linear layer, we propose a new 2PC paradigm along with an encoding approach to securely compute matrix multiplications based on an outer-product insight, which achieves $2.9\times \sim 12.5\times$ performance improvements compared to the state-of-the-art (SOTA) protocol. For the non-linear layer, through a new observation of utilizing the input distribution, we propose an approach of low-degree polynomial approximation for $\mathsf{GELU}$ and $\mathsf{Softmax}$, which improves the performance of the SOTA polynomial approximation by $2.9\times \sim 4.0\times$, where the average accuracy loss of our approach is 0.08\% compared to the non-2PC inference without privacy. Compared with the SOTA two-party inference, $\mathsf{Nimbus}$ improves the end-to-end performance of BERT inference by $2.7\times \sim 4.7\times$ across different network settings.
## 2025/2251
* Title: An Efficient Private GPT Never Autoregressively Decodes
* Authors: Zhengyi Li, Yue Guan, Kang Yang, Yu Feng, Ning Liu, Yu Yu, Jingwen Leng, Minyi Guo
* [Permalink](https://eprint.iacr.org/2025/2251)
* [Download](https://eprint.iacr.org/2025/2251.pdf)
### Abstract
The wide deployment of the generative pre-trained transformer (GPT) has raised privacy concerns for both clients and servers. While cryptographic primitives can be employed for secure GPT inference to protect the privacy of both parties, they introduce considerable performance overhead. To accelerate secure inference, this study proposes a public decoding and secure verification approach that utilizes public GPT models, motivated by the observation that securely decoding one and multiple tokens takes a similar latency. The client uses the public model to generate a set of tokens, which are then securely verified by the private model for acceptance. The efficiency of our approach depends on the acceptance ratio of tokens proposed by the public model, which we improve from two aspects: (1) a private sampling protocol optimized for cryptographic primitives and (2) model alignment using knowledge distillation. Our approach improves the efficiency of secure decoding while maintaining the same level of privacy and generation quality as standard secure decoding. Experiments demonstrate a $2.1\times \sim 6.0\times$ speedup compared to standard decoding across three pairs of public-private models and different network conditions.
## 2025/2252
* Title: Bridging Keyword PIR and Index PIR via MPHF and Batch PIR
* Authors: Huiqiang Liang, Haining Yu, Changtong Xu, Dongyang Zhan, Jinbo Yang, Hongli Zhang
* [Permalink](https://eprint.iacr.org/2025/2252)
* [Download](https://eprint.iacr.org/2025/2252.pdf)
### Abstract
This paper presents a Keyword Private Information Retrieval (Keyword PIR) scheme that achieves a constant-factor online computation and communication overhead compared to the underlying Index PIR, bridging the gap between Keyword PIR and Index PIR, and enabling efficient and privacy-preserving queries over diverse databases. We introduce a new Key-Value Store (KVS) instantiate by Minimal Perfect Hash Function, referred to as MPHF-KVS, in which each keyword query requires only a single index query. We then develop a generic Batch PIR framework that converts Index PIR into Keyword PIR using KVS encoding.
In particular, when the KVS is instantiated using a Binary Fuse Filter (BFF-KVS), Keyword PIR can be reduced to Batch PIR. Leveraging the updatable hint structure of PIR with side information, we propose a novel {Rewind \& Skip} technique that enables the execution of multiple queries within a single round.
In MPHF-KVS, the online computation and communication costs are at most $2\times$ those of Index PIR. In our Batch PIR with BFF-KVS, building upon three recent PIR schemes with sublinear server-side online computation and communication cost and without extra hint store, our approach inherits their advantages and achieves keyword query costs of less than $7\times$ the cost of an index query, while still maintaining sublinear online complexity.
## 2025/2253
* Title: Efficient Privacy-Preserving Blueprints for Threshold Comparison
* Authors: Pratyush Ranjan Tiwari, Harry Eldridge, Matthew Green
* [Permalink](https://eprint.iacr.org/2025/2253)
* [Download](https://eprint.iacr.org/2025/2253.pdf)
### Abstract
Privacy-Preserving Blueprints (PPBs), introduced by Kohlweiss et al. in in EUROCRYPT 2023, offer a method for balancing user privacy and bad-actor detection in private cryptocurrencies. A PPB scheme allows a user to append a verifiable escrow to their transactions which reveals some identifying information to an authority in the case that the user misbehaved. A natural PPB functionality is for escrows to reveal user information if the user sends an amount of currency over a certain threshold. However, prior works constructing PPBs for such a functionality have severe limitations when it comes to efficiency: escrows are either computationally infeasible to compute, or too large to be plausibly stored on a large-scale distributed ledger. We address these gaps by constructing a space and computation-efficient PPB for threshold comparison, producing escrows under 2kb that can be computed in seconds. The scheme can be instantiated using well-known cryptographic primitives, namely variants of the ElGamal encryption scheme and generic non-interactive zero-knowledge proofs. As an additional contribution, we implement one of the theoretical generic PPB constructions originally proposed by Kohlweiss et al. and find that it performs surprisingly well in practice. For the threshold comparison functionality it requires approximately 14kb escrows, and can be computed in around 12 seconds.
## 2025/2254
* Title: Multi-Party Private Join
* Authors: Anja Lehmann, Christian Mouchet, Andrey Sidorenko
* [Permalink](https://eprint.iacr.org/2025/2254)
* [Download](https://eprint.iacr.org/2025/2254.pdf)
### Abstract
A multi-party private join (MPPJ) protocol enables multiple source parties to provide a receiver party with the inner joins over their respective datasets, while revealing as little information as possible. There is currently no protocol that directly and efficiently enables such a MPPJ beyond the two- or three-party setting. The presently known protocols either achieve weaker functionality (e.g., multi- party private set intersection protocols) or more general ones (e.g., private-join-compute and generic secure multi-party computation protocols) and are therefore more costly to run for the sources. This work formally introduces MPPJ as an explicit goal, and proposes an efficient, helper-assisted protocol that achieves EYac-party inner joins with small leakage and close-to-optimal overhead for the sources. Specifically, for EYac databases with EYaU rows, it requires only a single EYae (EYaU) upload from the sources to the helper, and a single EYae (EYac -+ EYaU) download from the helper to the receiver. Moreover, the helper is entirely oblivious: it enables the efficiency and simplicity goals we are striving for, but it does not learn anything about the computation it facilitates. We formally model and prove the security of our protocol from standard assumptions, in the passive-adversary model. Then, we provide an open-source implementation and an extensive performance evaluation. According to our experiments, our protocol requires 1.02 to 20 times less communication than a current private-join-compute protocol (with no computation over the join) for 2 to 6 parties and input database sizes from 1.5K to 250K records. Finally, we demonstrate the versatility of our approach by extending our protocol to threshold-joins.
## 2025/2255
* Title: LPG: Raise Your Location Privacy Game in Direct-to-Cell LEO Satellite Networks
* Authors: Quan Shi, Liying Wang, Prosanta Gope, Qi Liang, Haowen Wang, Qirui Liu, Chenren Xu, Shangguang Wang, Qing Li, Biplab Sikdar
* [Permalink](https://eprint.iacr.org/2025/2255)
* [Download](https://eprint.iacr.org/2025/2255.pdf)
### Abstract
Multi-tenant direct-to-cell (D2C) Low Earth Orbit (LEO) satellite networks pose significant risks to usersrCO location privacy by linking Mobile Network Operator (MNO)- managed identities with Satellite Network Operator (SNO)- visible locations. Existing privacy solutions are ill-suited to the resource-constrained hardware and orbital dynamics of these satellite environments. We present LPG (Location Privacy Game), the first protocol-layer solution offering user-configurable location privacy for D2C LEO. LPG achieves this via identity-location decoupling: SNOs provide connectivity without visibility of user identity, while MNOs manage service and billing without access to precise location information. LPG enables offline secure authentication and key agreement without revealing user identity to satellites, supports user-configurable location disclosure at chosen geographic granularity for essential service needs, and ensures fair billing between MNOs and SNOs through privacy-preserving settlement. Our implementation on a real-world in-orbit LEO satellite and commercial mobile phones demonstrates that LPG is practical and viable in resource-constrained, highly-dynamic LEO environments.
## 2025/2256
* Title: Scalable Private Set Intersection over Distributed Encrypted Data
* Authors: Seunghun Paik, Nirajan Koirala, Jack Nero, Hyunjung Son, Yunki Kim, Jae Hong Seo, Taeho Jung
* [Permalink](https://eprint.iacr.org/2025/2256)
* [Download](https://eprint.iacr.org/2025/2256.pdf)
### Abstract
Finding intersections across sensitive data is a core operation in many real-world data-driven applications, such as healthcare, anti-money laundering, financial fraud, or watchlist applications. These applications often require large-scale collaboration across thousands or more independent sources, such as hospitals, financial institutions, or identity bureaus, where all records must remain encrypted during storage and computation, and are typically outsourced to dedicated/cloud servers. Such a highly distributed, large-scale, and encrypted setting makes it very challenging to apply existing solutions, e.g., (multi-party) private set intersection (PSI) or private membership test (PMT).
In this paper, we present Distributed and Outsourced PSI (DO-PSI), an efficient and scalable PSI protocol over outsourced, encrypted, and highly distributed datasets. Our key technique lies in a generic threshold fully homomorphic encryption (FHE) based framework that aggregates equality results additively, which ensures high scalability to a large number of data sources. In addition, we propose a novel technique called \textit{nonzero-preserving mapping}, which maps a zero vector to zero and preserves nonzero values. This allows homomorphic equality tests over a smaller base field, substantially reducing computation while enabling higher-precision representations. We implement DO-PSI and conduct extensive experiments, showing that ours substantially outperforms existing methods in both computation and communication overheads. Our protocol handles a billion-scale set distributed and outsourced to a thousand data owners within one minute, directly reflecting large-scale deployment scenarios, and achieves up to an 11.16$\times$ improvement in end-to-end latency over prior state-of-the-art methods.
## 2025/2257
* Title: \textsc{Npir}: High-Rate PIR for Databases with Moderate-Size Records * Authors: Yuliang Lin, Baosheng Wang, Yi Wang, Rongmao Chen
* [Permalink](https://eprint.iacr.org/2025/2257)
* [Download](https://eprint.iacr.org/2025/2257.pdf)
### Abstract
Private information retrieval (PIR) is a widely used technique in privacy-preserving applications that enables users to retrieve records from a database without revealing any information about their queries. This study focuses on a type of PIR that has a high ratio between the size of the record retrieved by the client and the server's response. Although significant progress has been made in high-rate PIR in recent years, the computational overhead on the server side remains rather high. This results in low server throughput, particularly for applications involving databases with moderate-size records (i.e. tens of kilobytes), such as private advertising system.
In this paper, we present \textsc{Npir}, a high-rate single-server PIR that is based on NTRU encoding and outperforms the state-of-the-art Spiral (Menon \& Wu, S\&P 2022) and NTRUPIR (Xia \& Wang, EuroS\&P 2024) in terms of server throughput for databases with moderate-size records. In specific, for databases ranging from 1 GB to 32 GB with 32 KB records, the server throughput of \textsc{Npir} is 1.50 to 2.84 times greater than that of Spiral and 1.77 to 2.55 times greater than that of NTRUPIR.
To improve server throughput without compromising the high-rate feature, we propose a novel tool called NTRU packing, which compresses the constant terms of underlying polynomials of multiple NTRU encodings into a single NTRU encoding, thereby reducing the size of the server's response. Furthermore, \textsc{Npir} naturally supports batch processing for moderate-size records, and can easily handle retrieving for records of varying sizes.tions, we advance secure communication protocols under challenging conditions.
## 2025/2258
* Title: On the Equivalence of Polynomial Commitments for an Identical Polynomial under Different Bases
* Authors: Dengji Ma, Jingyu Ke, Sinka Gao, Guoqiang Li
* [Permalink](https://eprint.iacr.org/2025/2258)
* [Download](https://eprint.iacr.org/2025/2258.pdf)
### Abstract
We propose a Pairing-based Polynomial Consistency Protocol (PPCP) that verifies the equivalence of polynomial commitments generated under different basis representations, such as the coefficient and Lagrange bases. By leveraging pairing relations, PPCP proves that two commitments correspond to an identical underlying polynomial vector without revealing the polynomial itself. This enables efficient proof aggregation and recursive composition across heterogeneous SNARK systems that adopt distinct polynomial encodings.
## 2025/2259
* Title: HQC Beyond the Standard: Ciphertext Compression and Refined DFR Analysis
* Authors: Sebastian Bitzer, Jean-Christophe Deneuville, Emma Munisamy, Bharath Purtipli, Stefan Ritterhoff, Antonia Wachter-Zeh
* [Permalink](https://eprint.iacr.org/2025/2259)
* [Download](https://eprint.iacr.org/2025/2259.pdf)
### Abstract
Hamming Quasi-Cyclic (HQC), recently selected by NIST for standardization, does not employ ciphertext compression, unlike its lattice-based counterpart Kyber. In lattice-based encryption, ciphertext compression is a standard post-processing step, typically implemented through coefficient-wise rounding. In contrast, analogous methods have not yet been explored in code-based cryptography. We address this gap by developing techniques to reduce ciphertext sizes in schemes defined over the Hamming metric, with a particular focus on HQC.
To support this approach, the decryption failure rate (DFR) analysis is generalized. Specifically, we revisit the modeling of the error that must be correctable with probability $2^{-\lambda}$ to achieve $\lambda$ bits of security; previously, only tractable under an independence assumption. We propose a more accurate model of the error distribution, which takes dependencies between the coefficients into account. Confirmed by extensive simulations, the proposed model sharpens the DFR analysis and, hence, our understanding of the security of HQC.
Building on this generalized framework, we present a ciphertext compression mechanism that enables a precise DFR analysis and is therefore transparent with respect to security. This is achieved by carefully designing a quantization code with a direct-product structure, aligned with HQC's error-correcting code. For the parameters proposed in the round 4 submission, our techniques reduce HQC ciphertext sizes by up to 4.7%; a proof-of-concept implementation confirms that this improvement comes without noticeable loss in efficiency. Reductions of up to 10% are achievable through a trade-off with public-key size.
## 2025/2260
* Title: Tight Generic PRF Security of HMAC and NMAC
* Authors: Yaobin Shen, Xiangyang Zhang, Lei Wang, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/2260)
* [Download](https://eprint.iacr.org/2025/2260.pdf)
### Abstract
HMAC and its variant NMAC are among the most widely used methods for keying a cryptographic hash function to obtain a PRF or a MAC. Yet, even after nearly three decades of research, their generic PRF security still remains poorly understood, where the compression function of the underlying hash function is treated as a black box and accessible to the adversary. Although a series of works have exploited compression function queries to mount generic attacks, proving tight bounds on the generic PRF security of HMAC and NMAC remains a challenging open question until now.
In this paper, we establish tight bounds on the generic PRF security of HMAC and NMAC. Our bounds capture the influence of the number of construction queries, the number of compression function queries, and the maximal block length of a message on their security. The proofs are carried out in the multi-user setting and the bounds hold regardless of the number of users. In addition, we present matching attacks to demonstrate that our bounds are essentially tight. Taken together, our results close a longstanding gap in the generic PRF security analysis of HMAC and NMAC.
## 2025/2261
* Title: TSS-PV: Traceable Secret Sharing with Public Verifiability
* Authors: Duc Anh Luong, Jong Hwan Park, Changmin Lee, Hyoseung Kim
* [Permalink](https://eprint.iacr.org/2025/2261)
* [Download](https://eprint.iacr.org/2025/2261.pdf)
### Abstract
High-value custodial systems require both Public Verifiability (PVSS) to
audit key distribution and Traceability (TSS) to identify insider leakage
via black-box ``reconstruction boxes.'' Existing schemes achieve one
property but not both, leaving practical systems exposed to either undetectable dealer misbehavior or untraceable share leakage. Combining these properties introduces the ``Provenance Paradox'': a verifiability-aware reconstruction box with access to verification predicates and public transcripts can reject dummy shares used for tracing because they have no provenance in the public transcript.
We present TSS-PV, the first publicly verifiable traceable secret sharing scheme that resolves this paradox. Our key insight is to inject indistinguishable dummy shares during the sharing phase itself, ensuring
they are committed to the public transcript before any reconstruction box
is constructed. We formalize syntax and security under a modular
adversarial model: public verifiability holds against fully malicious
dealers and parties; traceability identifies leaking parties after honest distribution; and non-imputability prevents a malicious dealer from
framing honest parties. Both tracing properties assume a verifiability-aware (perfect) reconstruction box.
We instantiate TSS-PV over cyclic groups using Schnorr-based NIZKs and a recent generic tracing framework (CRYPTO'24). Public verification costs
scale linearly in the number of parties; tracing costs are quadratic. A Curve25519 prototype on commodity hardware demonstrates practicality: for $32\text{ - }256$ parties, distribution verification completes in
$14\text{ - }127$ ms, tracing in $0.24\text{ - }76$ s, and trace
verification in $0.15\text{ - }25$ s.
## 2025/2262
* Title: Certified-Everlasting Quantum NIZK Proofs
* Authors: Nikhil Pappu
* [Permalink](https://eprint.iacr.org/2025/2262)
* [Download](https://eprint.iacr.org/2025/2262.pdf)
### Abstract
We study non-interactive zero-knowledge proofs (NIZKs) for NP satisfying: 1) statistical soundness, 2) computational zero-knowledge and 3) certified-everlasting zero-knowledge (CE-ZK). The CE-ZK property allows a verifier of a quantum proof to revoke the proof in a way that can be checked (certified) by the prover. Conditioned on successful certification, the verifier's state can be efficiently simulated with only the statement, in a statistically indistinguishable way. Our contributions regarding these certified-everlasting NIZKs (CE-NIZKs) are as follows:
- We identify a barrier to obtaining CE-NIZKs in the CRS model via generalizations of known interactive proofs that satisfy CE-ZK.
- We circumvent this by constructing CE-NIZK from black-box use of NIZK for NP satisfying certain properties, along with OWFs. As a result, we obtain CE-NIZKs for NP in the CRS model, based on polynomial hardness of the learning with errors (LWE) assumption.
- In addition, we observe that the aforementioned barrier does not apply to the shared EPR model. Consequently, we present a CE-NIZK for NP in this model based on any statistical binding hidden-bits generator, which can be based on LWE. The only quantum computation in this protocol involves single-qubit measurements of the shared EPR pairs.
## 2025/2263
* Title: Completing Policy-based Anonymous Tokens: Private Bits, Public Metadata and more...
* Authors: David Kretzler, Yong Li, Codrin Ogreanu
* [Permalink](https://eprint.iacr.org/2025/2263)
* [Download](https://eprint.iacr.org/2025/2263.pdf)
### Abstract
Anonymous tokens are cryptographic protocols for restricting the access to online resources to eligible users. After proving eligibility to the token issuer, the client receives a set of tokens. Later, it can prove eligibility to a resource provider by sending one of the tokens received from the issuer. The anonymous token protocol ensures that the resource provider cannot link received tokens to their issuance, even if it colludes with the token issuer. Recently, Faut et al. (EuroS\&PrCO25) introduced the concept of policy-based anonymous tokens, in which an issuer provides a single pre-token to a client, who can locally derive multiple tokens according to a publicly announced policy. The major advantage of policy-based tokens is that the communication complexity of the issuance phase is constant. While the work of Faut et al. constitutes a promising step in a new direction, their protocol still lacks several desirable properties known from standard anonymous tokens -- most notably, the ability to bind a pre-token and all tokens derived from it to a private metadata bit or a publicly known metadata string.
In this work, we present a new framework for policy-based anonymous token schemes in the random oracle model. Our framework includes two concretely practical constructions -- one based on equivalence class signatures and one on algebraic MACs -- as well as a communication-optimized, though less practical, construction based on zkSNARKs. All three constructions can be configured to support private metadata bits, public metadata, or both. We formalize the notion of policy-based anonymous tokens with a private metadata bit and public metadata, and we prove security of the two primary constructions: the equivalence-class-signature-based scheme and the algebraic-MAC-based scheme. Finally, we provide an experimental evaluation and comparison of all our constructions alongside the most relevant related work. Our results demonstrate that our two primary constructions achieve significant efficiency improvements over the scheme of Faut et al., both in terms of computation communication.
## 2025/2264
* Title: Leakage-Resilient Multi-Party Computation: Protecting the Evaluator in Circuits Garbling
* Authors: Francesco Berti, Itamar Levi
* [Permalink](https://eprint.iacr.org/2025/2264)
* [Download](https://eprint.iacr.org/2025/2264.pdf)
### Abstract
Garbling schemes allow two parties to compute a
joint function on private inputs without revealing them. Yet,
a semi-honest garbler might exploit hardware/software sidechannel
leakages from the evaluator. An alarming threat with
no concrete solution yet. Using the homomorphic properties of
ElGamal encryption, we can prevent such leakage-based attacks.
## 2025/2265
* Title: PRGUE Schemes: Efficient Updatable Encryption With Robust Security From Symmetric Primitives
* Authors: Elena Andreeva, Andreas Weninger
* [Permalink](https://eprint.iacr.org/2025/2265)
* [Download](https://eprint.iacr.org/2025/2265.pdf)
### Abstract
Securing sensitive data for long-term storage in the cloud is a challenging problem.
Updatable encryption (UE) enables changing the encryption key of encrypted data in the cloud while the plaintext and all versions of the key remain secret from the cloud storage provider, making it an efficient alternative for companies that seek to outsource their data storage.
The most secure UE schemes to date follow robust security models, such as the one by Boyd et al. from CRYPTO 2020, and rely exclusively on asymmetric cryptography, thus incurring a substantial performance cost.
In contrast, the Nested UE construction of Boneh et al. from ASIACRYPT 2020 achieves much better efficiency with symmetric cryptography, but it provides weaker security guarantees.
Boyd et al. further suggest that attaining robust UE security inherently requires the use of asymmetric cryptography.
In this work, we show for the first time that symmetric UE schemes are not inherently limited in their security and can achieve guarantees on par with, and even beyond, BoydrCOs UE model.
To this end, we extend BoydrCOs framework to encompass the class of ciphertext-dependent UE schemes and introduce indistinguishability-from-random (IND\$) as a stronger refinement of indistinguishability.
While our IND\$ notion primarily streamlines the proofs of advanced security properties within the model, it yields practical privacy advantages: ciphertexts do not exhibit a recognizable structure that could otherwise distinguish them from arbitrary data.
We then introduce two robustly secure symmetric UE constructions, tailored to different target security levels.
Our schemes are built on a novel design paradigm that combines symmetric authenticated encryption with ciphertext re-randomization, leveraging for the first time the use of pseudorandom number generators in a one-time-pad style. This approach enables both robust security and high efficiency, including in AES-based implementations.
Our first scheme, PUE-List, delivers encryption up to 600|u faster than prior asymmetric schemes of similar robustness, while matching Boneh et al.rCOs efficiency and achieving the stronger security level of Boyd et al.
Our second scheme, PUE-One, further boosts performance with constant-time decryption 24|u faster than all previously known UE schemes, overcoming the main bottleneck in BonehrCOs design, while trading off some security, yet still significantly surpassing the guarantees of BonehrCOs Nested scheme.
## 2025/2266
* Title: Breaking UOV Encryption: Key Recovery Attack On Olivier
* Authors: Emanuele Cornaggia
* [Permalink](https://eprint.iacr.org/2025/2266)
* [Download](https://eprint.iacr.org/2025/2266.pdf)
### Abstract
The Oil and Vinegar (OV) trapdoor is widely used in signature schemes such as UOV and MAYO. Recently, Esposito et al. proposed OliVier, an encryption scheme based on this trapdoor. However, the OV trapdoor was originally designed for signatures, and adapting it to encryption introduces inherent challenges.
We identify two such challenges and analyze how OliVier addresses the first, while showing that the unresolved second challenge enables a practical key-recovery attack. We conclude that any scheme using the OV trapdoor for encryption must also solve this second problem, for which no efficient solution is currently known.
## 2025/2267
* Title: How to Compare Bandwidth Constrained Two-Party Secure Messaging Protocols: A Quest for A More Efficient and Secure Post-Quantum Protocol
* Authors: Benedikt Auerbach, Yevgeniy Dodis, Daniel Jost, Shuichi Katsumata, Rolfe Schmidt
* [Permalink](https://eprint.iacr.org/2025/2267)
* [Download](https://eprint.iacr.org/2025/2267.pdf)
### Abstract
Transitioning existing classical two-party secure messaging protocols to post-quantum protocols has been an active movement in practice in recent years: ApplerCOs PQ3 protocol and the recent Triple Ratchet protocol being investigated by the Signal team with academics (Dodis et al. EurocryptrCO25). However, due to the large communication overhead of post-quantum primitives, numerous design choices non-existent in the classical setting are being explored, rendering comparison of secure messaging protocols difficult, if not impossible.
In this work, we thus propose a new pragmatic metric to measure how secure a messaging protocol is given a particular communication pattern, enabling a concrete methodology to compare secure messaging protocols. We uncover that there can be no rCLoptimalrCY protocol, as different protocols are often incomparable with the respect to worst-case (adversarial) messaging behaviors, especially when faced with real-world
bandwidth constraints. We develop a comprehensive framework to experimentally compare various messaging protocols under given bandwidth limits and messaging behaviors. Finally, we apply our framework to compare several new and old messaging protocols. Independently, we also uncover untapped optimizations which we call opportunistic sending, leading to better post-quantum messaging protocols. To capture these optimizations, we further propose sparse continuous key agreement as a fundamental building block for secure messaging protocols, which could be of independent interest.
## 2025/2268
* Title: On the Pitfalls of Modeling Individual Knowledge
* Authors: Wojciech Ciszewski, Stefan Dziembowski, Tomasz Lizurej, Marcin Mielniczuk
* [Permalink](https://eprint.iacr.org/2025/2268)
* [Download](https://eprint.iacr.org/2025/2268.pdf)
### Abstract
The concept of knowledge has been central in cryptography, especially within cryptographic proof systems. Traditionally, research in this area considers an abstract \emph{prover} defending a claim that it knows a message $M$. Recently, a stronger conceptrCotermed ``individual'' (Dziembowski et al., CRYPTO'23) or ``complete'' (Kelkar et al., CCS'24) knowledgerCohas emerged. This notion ensures the prover physically stores $M$ on a machine that it controls. As we argue in the paper, this concept also appears in earlier work on ``non-outsourceable puzzles'' (Miller et al., CCS'15), which implicitly assumes that performing quickly complex computation on a string $M$ implies storing it on a single machine.
In this line of work, the authors typically rely on the algorithms whose computation requires a massive number of queries to a hash function $H$. This paper highlights a subtle issue in the modeling used in some of these papers, more concretely, the assumption that H can be modeled as an atomic random oracle on long messages. Unfortunately, this does not correspond well to how the hash functions are constructed in practice. For example, the real-world hash functions (e.g., Merkle-Damgard or sponge-based) allow partial evaluation on long inputs, violating this assumption. Another example is the hashing used in Bitcoin mining, which permits similar precomputation. This undermines some protocols relying on individual knowledge. We demonstrate practical attacks against Miller et al.'s and Kelkar et al.'s schemes based on this observation, and discuss secure alternatives. Our alternative constructions, which are modifications of the original ones, avoid reliance on the random oracle behavior of hash functions on long messages. In the full version of this paper, we will provide their formal security analysis in the individual cryptography model of Dziembowski et al. (CRYPTO'23).
## 2025/2269
* Title: Accelerating FrodoKEM in Hardware
* Authors: Sanjay Deshpande, Patrick Longa, Jakub Szefer
* [Permalink](https://eprint.iacr.org/2025/2269)
* [Download](https://eprint.iacr.org/2025/2269.pdf)
### Abstract
FrodoKEM, a conservative post-quantum key encapsulation mechanism based on the plain Learning with Errors (LWE) problem, has been recommended for use by several government cybersecurity agencies and is currently undergoing standardization by the International Organization for Standardization (ISO). Despite its robust security guarantees, FrodoKEM's performance remains one of the main challenges to its widespread adoption. This work addresses this concern by presenting a fully standard-compliant, high-performance hardware implementation of FrodoKEM targeting both FPGA and ASIC platforms. The design introduces a scalable parallelization architecture that supports run-time configurability across all twelve parameter sets, covering three security levels (L1, L3, L5), two PRNG variants (SHAKE-based and AES-based), and both standard and ephemeral modes, alongside synthesis-time tunability through a configurable performance parameter to balance throughput and resource utilization. For security level L1 on Xilinx Ultrascale+ FPGA, the implementation achieves 3,164, 2,846, and 2,614 operations per second for key generation, encapsulation, and decapsulation, respectively, representing the fastest standard-compliant performance reported to date while consuming only 27.8K LUTs, 64 DSPs, and 8.1K flip-flops. These results significantly outperform all prior specification-compliant implementations and even surpass non-compliant designs that sacrifice specification adherence for speed. Furthermore, we present the first ASIC evaluation of FrodoKEM using the NANGATE45 45 nm technology library, achieving 7,194, 6,471, and 5,943 operations per second for key generation, encapsulation, and decapsulation, respectively, with logic area of 0.235 mm$^2$. The ASIC implementation exhibits favorable sub-linear area scaling and competitive energy efficiency across different performance parameter configurations, establishing a baseline for future comparative studies. The results validate FrodoKEM's practical viability for deployment in high-throughput, resource-constrained, and power-sensitive cryptographic applications, demonstrating that conservative post-quantum security can be achieved without compromising performance.
## 2025/2270
* Title: HHGS: Forward-secure Dynamic Group Signatures from Symmetric Primitives
* Authors: Xuelian Cao, Zheng Yang, Daniel Reijsbergen, Jianting Ning, Junming Ke, Zhiqiang Ma, Jianying Zhou
* [Permalink](https://eprint.iacr.org/2025/2270)
* [Download](https://eprint.iacr.org/2025/2270.pdf)
### Abstract
Group signatures allow a group member to sign messages on behalf of the group while preserving the signerrCOs anonymity, making them invaluable for privacy-sensitive applications. As quantum computing advances, post-quantum security in group signatures becomes essential. Symmetric primitives (SP) offer a promising pathway due to their simplicity, efficiency, and well-understood security foundations. In this paper, we introduce the first \textit{forward-secure dynamic group signature} (FSDGS) framework relying solely on SP. We begin with \textit{hierarchical hypertree group signatures} (HHGS), a basic scheme that securely organizes keys of one-time signatures (OTS) in a hypertree using puncturable pseudorandom functions to enable on-demand key generation and forward security, dynamic enrollment, and which provides resilience against attacks that exploit registration patterns by obfuscating the assignment and usage of keys. We then extend this foundation to HHGS^+, which orchestrates multiple HHGS instances in a generic way, significantly extending the total signing capacity to $O(2^{60})$, which outperforms HHGS's closest competitors while keeping signatures below 8 kilobytes. We prove the security of both schemes in the standard model. Our results outline a practical SP-driven pathway toward post-quantum-secure group signatures suitable for resource-constrained client devices.
## 2025/2271
* Title: ARION: Attention-Optimized Transformer Inference on Encrypted Data
* Authors: Linhan Yang, Jingwei Chen, Wangchen Dai, Shuai Wang, Wenyuan Wu, Yong Feng
* [Permalink](https://eprint.iacr.org/2025/2271)
* [Download](https://eprint.iacr.org/2025/2271.pdf)
### Abstract
Privacy-preserving Transformer inference (PPTI) is essential for deploying large language models (LLMs) such as BERT and LLaMA in sensitive domains. In these models, the attention mechanism is both the main source of expressiveness and the dominant performance bottleneck under fully homomorphic encryption (FHE), due to large ciphertext matrix multiplications and the softmax nonlinearity. This paper presents Arion, a non-interactive FHE-based PPTI protocol that specifically optimizes the computation of encrypted attention. First, for the three consecutive ciphertext matrix multiplications in multi-head attention, we introduce the double Baby-Step Giant-Step algorithm, which significantly reduces the number of ciphertext rotations. On BERT-Base, Arion achieves an 82.5% reduction in rotations over the state-of-the-art PPTI protocol MOAI (2025), corresponding to a 5.7x reduction in rotation cost. Second, we propose a linearrCononlinear fusion technique tailored to the softmax evaluation in attention. By decomposing softmax into shift-by-maximum, exponentiation, and reciprocal sub-steps and fusing them with the surrounding encrypted matrix operations, Arion enables efficient attention evaluation while remaining compatible with diverse ciphertext packing formats. We implement Arion using Lattigo and first evaluate attention kernels on popular LLMs including BERT-Tiny, BERT-Base, and LLaMA, confirming the practicality and scalability of the proposed optimizations for encrypted attention computation. For end-to-end applications, on classification tasks for several benchmark datasets, Arion attains accuracy comparable to plaintext inference and yields up to 2.5x end-to-end speedups over MOAI for BERT-Base.
## 2025/2272
* Title: High Exponents May Not Suffice to Patch AIM N+eOn Attacks, Weak Parameters, and Patches for AIM2N+e
* Authors: Yimeng Sun, Shiyao Chen, Guowei Liu, Meiqin Wang, Chao Niu
* [Permalink](https://eprint.iacr.org/2025/2272)
* [Download](https://eprint.iacr.org/2025/2272.pdf)
### Abstract
The growth of advanced cryptographic applications has driven the development of arithmetization-oriented (AO) ciphers over large finite fields, which are designed to minimize multiplicative complexity. However, this design advantage of AO ciphers could also serve as an attack vector. For instance, the \textsf{AIM} one-way function in the post-quantum signature \AIMer proposed at CCS 2023 has been broken by several works soon after its publication. The designers then promptly developed secure patches and proposed an enhanced version, \textsf{AIM2}, which was updated to the latest version of \AIMer that has been selected as one of the winners of the Korean PQC Competition in early 2025.
In this paper, we focus on the algebraic security of AIM2 over $\mathbb{F}_{2^n}$. First, we introduce a resultant-minimized model that reduces eliminations by using a non-$k$ based substitution strategy and linearized-polynomial decomposition,
achieving an attack time complexity of $2^{188.76}$ ($2^{195.05}$) primitive calls of \textsf{AIM2-III} when $\omega=2$ ($\omega=2.373$), indicating that the designers have been over-optimistic in the evaluation of their security margin; Second, we propose a subfield reduction technique for the case that exponents approach subfield extension sizes, equation degrees collapse sharply, \textit{e.g.,} the exponent $e_2=141\mapsto 13$ in \textsf{AIM2-V} when considering the subfield $\mathbb{F}_{2^{128}}$. This can lower the algebraic attack complexity to $2^{295.97}$ primitive calls at $\omega=2$, which improves upon designers' estimated bound of Gr\"{o}bner basis attack by about $2^{100}$. Besides, based on our attack methods, we have identified some weak parameter choices, which could provide concrete design guidance for \textsf{AIM2} construction, especially for the exponent of its Mersenne S-box. Finally, to address the potential vulnerabilities, we further propose \textsf{AIM2-patch} with a simple secure patch on \textsf{AIM2}, which can prevent key elimination, neutralize linearized-polynomial decomposition, and raise algebraic attack complexity, while incurring negligible overheads in \AIMer scheme.
## 2025/2273
* Title: Benchmarking SLH-DSA: A Comparative Hardware Analysis Against Classical Digital Signatures for Post-Quantum Security
* Authors: Jayalaxmi H, H M Brunda, Sumith Subraya Nayak, Sathya M, Anirudh S Hegde
* [Permalink](https://eprint.iacr.org/2025/2273)
* [Download](https://eprint.iacr.org/2025/2273.pdf)
### Abstract
The advent of large-scale quantum computers poses a fundamental threat to widely deployed public-key cryptographic schemes such as RSA and elliptic curve digital signatures. In response, the National Institute of Standards and Technology has standardized several post-quantum cryptographic algorithms, including the Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) specified in FIPS 205. While SLH-DSA offers strong, conservative security guarantees based solely on cryptographic hash functions, its practical adoption depends on a clear understanding of its hardware cost and performance characteristics relative to classical standards.
This paper presents a unified hardware benchmarking study of SLH-DSA against RSA, DSA, ECDSA, and EdDSA. All algorithms are implemented at the register-transfer level in Verilog HDL and synthesized on the same Xilinx Artix-7 FPGA platform to ensure a fair comparison. The evaluation focuses on key hardware metrics, including logic utilization, memory usage, DSP consumption, operational latency, maximum clock frequency, and throughput for key generation, signing, and verification.
The results demonstrate that SLH-DSA is logic- and memory-intensive, with significantly higher signing latency and larger signature sizes compared to classical schemes. However, its verification performance is highly competitive, and its public key size remains extremely small. In contrast, classical schemes are primarily arithmetic-bound and rely heavily on DSP resources. The findings highlight that SLH-DSA represents a viable post-quantum solution for applications prioritizing long-term security assurance and efficient verification, such as firmware authentication and digital archiving, despite its higher signing cost.
## 2025/2274
* Title: Post-Quantum Security of the Sum of Even-Mansour
* Authors: YanJin Tan, JunTao Gao, XueLian Li
* [Permalink](https://eprint.iacr.org/2025/2274)
* [Download](https://eprint.iacr.org/2025/2274.pdf)
### Abstract
The Sum of Even-Mansour (SoEM) construction was proposed by Chen et al. at Crypto 2019. This construction implements a pseudorandom permutation via the modular addition of two independent Even-Mansour structures and can spawn multiple variants by altering the number of permutations or keys. It has become the design basis for some symmetric schemes, such as the nonce-based encryption scheme CENCPP* and the nonce-based message authentication code scheme nEHTm. This paper provides a proof of the quantum security of the SoEM21 construction under the Q1 model: when an attacker has quantum access to the random permutations but only classical access to the keyed construction, the SoEM21 construction ensures security of up to \(n/3\) bits. This exactly matches the complexity \(O(2^{n/3})\) of the quantum key recovery attack in the Q1 model recently proposed by Li et al., thus establishing a tight bound.
## 2025/2275
* Title: Random-Access AEAD for Fast Lightweight Online Encryption
* Authors: Andr|-s F|ibrega, Julia Len, Thomas Ristenpart, Gregory Rubin
* [Permalink](https://eprint.iacr.org/2025/2275)
* [Download](https://eprint.iacr.org/2025/2275.pdf)
### Abstract
We study the problem of random-access authenticated encryption. In this setting, one wishes to encrypt (resp., decrypt) a large payload in an online matter, i.e., using a limited amount of memory, while allowing for the processing of plaintext (resp., ciphertext) segments to be in a random order. Prior work has studied online AE for in-order (streaming) encryption and decryption, and later work added additional constraints to support random access decryption. The result is complicated notions that are not built from the start to account for random access.
We thus provide a new, clean-state treatment to the random-access setting. We introduce random-access authenticated encryption (raAE) schemes, which captures AEAD that provides random-access encryption and decryption. We introduce formal security definitions for raAE schemes that cover confidentiality, integrity, and commitment. We prove relationships with existing notions, showing that our simpler treatment does not sacrifice achievable security. Our implications also result in the first treatment of commitment security for online AEAD as well, an increasingly important security goal for AEAD.
We then exercise our formalization with a practice-motivated case study: FIPS-compliant raAE. We introduce an raAE scheme called FLOE (Fast Lightweight Online Encryption) that is FIPS compliant, compatible with existing AES-GCM APIs that mandate random nonces, and yet can provide secure, random-access, committing encryption of orders of magnitude more data than naive approaches that utilize AES-GCM. FLOE was designed in close collaboration with leading cloud data platform Snowflake, where it will soon be used in production to protect sensitive data.
## 2025/2276
* Title: E2E-AKMA: An End-to-End Secure and Privacy-Enhancing AKMA Protocol Against the Anchor Function Compromise
* Authors: Yueming Li, Long Chen, Qianwen Gao, Zhenfeng Zhang
* [Permalink](https://eprint.iacr.org/2025/2276)
* [Download](https://eprint.iacr.org/2025/2276.pdf)
### Abstract
The Authentication and Key Management for Applications (AKMA) system represents a recently developed protocol established by 3GPP, which is anticipated to become a pivotal component of the 5G standards. AKMA enables application service providers to delegate user authentication processes to mobile network operators, thereby eliminating the need for these providers to store and manage authentication-related data themselves. This delegation enhances the efficiency of authentication procedures but simultaneously introduces certain security and privacy challenges that warrant thorough analysis and mitigation.
The 5G AKMA service is facilitated by the AKMA Anchor Function (AAnF), which may operate outside the boundaries of the 5G core network. A compromise of the AAnF could potentially allow malicious actors to exploit vulnerabilities, enabling them to monitor user login activities or gain unauthorized access to sensitive communication content. Furthermore, the exposure of the Subscription Permanent Identifier (SUPI) to external Application Functions poses substantial privacy risks, as the SUPI could be utilized to correlate a user's real-world identity with their online activities, thereby undermining user privacy.
To mitigate these vulnerabilities, we propose a novel protocol named E2E-AKMA, which facilitates the establishment of a session key between the User Equipment (UE) and the Application Function (AF) with end-to-end security, even in scenarios where the AAnF has been compromised. Furthermore, the protocol ensures that no entity, aside from the 5G core network, can link account activities to the user's actual identity. This architecture preserves the advantages of the existing AKMA scheme, such as eliminating the need for complex dynamic secret data management and avoiding reliance on specialized hardware (apart from standard SIM cards). Experimental evaluations reveal that the E2E-AKMA framework incurs an overhead of approximately 9.4\% in comparison to the original 5G AKMA scheme, which indicates its potential efficiency and practicality for deployment.
--- Synchronet 3.21a-Linux NewsLink 1.2