From Newsgroup: sci.crypt

## In this issue
1. [2025/886] PaCo: Bootstrapping for CKKS via Partial CoeffToSlot
2. [2025/1297] On the Relations between Matchmaking Public Key ...
3. [2025/2200] Privacy-Preserving Identifier Checking in 5G
4. [2025/2201] On $k$-sum algorithms for $\{-1,1\}^m$ vectors
5. [2025/2202] Disproving the Linearity of the Polynomials after ...
6. [2025/2203] Hash-based Signature Schemes for Bitcoin
7. [2025/2204] Consistency Verification for Zero-Knowledge Virtual ...
8. [2025/2205] ML-Guided Beam Search for Differential Trail ...
9. [2025/2206] LifeXP+: Secure, Usable and Reliable Key Recovery ...
10. [2025/2207] A General Framework for Registered Functional ...
11. [2025/2208] Vectorized SVE2 Optimization of the Post-Quantum ...
12. [2025/2209] A New Practical Cube Attack via Recovering Numerous ...
13. [2025/2210] Multi-Client Functional Encryption for Small Domains
14. [2025/2211] Architecture-private Zero-knowledge Proof of Neural ...
15. [2025/2212] Architecture-private Zero-knowledge Proof of Neural ...
16. [2025/2213] Simplified Meet-in-the-middle Preimage Attacks on ...
17. [2025/2214] Accelerating TFHE with Sorted Bootstrapping Techniques
18. [2025/2215] Obfuscating Pseudorandom Functions is Post-Quantum ...
19. [2025/2216] AgentCrypt: Advancing Privacy and (Secure) ...
20. [2025/2217] Ideal Private Simultaneous Messages Schemes and ...
21. [2025/2218] The Syndrome Weight Distribution in Quasi-Cyclic ...
22. [2025/2219] HATSolver: Learning Groebner Bases with ...
23. [2025/2220] Performance Improvements of ZK-Prover for rWasm: A ...
24. [2025/2221] Sparse Vector Reconstruction from Distance Spectrum ...
25. [2025/2222] Improved Pseudorandom Codes from Permuted Puzzles
26. [2025/2223] Analysis of the Security Design, Engineering, and ...
27. [2025/2224] Beyond Ethernet: Reusing MACsec for CANsec
28. [2025/2225] Learning with Errors with Output Dependencies: LWE, ...
29. [2025/2226] Learning With Physical Rounding for Linear and ...
30. [2025/2227] Time Memory Trade-off For Enumeration
31. [2025/2228] PIRANHAS: PrIvacy-Preserving Remote Attestation in ...
32. [2025/2229] Practically Implementable Minimal Universal Gate ...
33. [2025/2230] Efficient Algorithms for $\mathbb{G}_2$ Subgroup ...
34. [2025/2231] NeevAs: An AEAD Design for Lightweight Cryptography
35. [2025/2232] Toward Practical Lattice-based Unbounded Inner ...
36. [2025/2233] Quantum Authentication: Security against ...
37. [2025/2234] ZeroOS: A Universal Modular Library OS for zkVMs
38. [2025/2235] MLWErCOs impact on Web Metrics, mTLS TTLB, and AWS ...
39. [2025/2236] Extending the SPHINCS+ Framework: Varying the Tree ...
40. [2025/2237] Distributed Broadcast Encryption for Confidential ...
## 2025/886
* Title: PaCo: Bootstrapping for CKKS via Partial CoeffToSlot
* Authors: Jean-S|-bastien Coron, Tim Seur|-
* [Permalink](https://eprint.iacr.org/2025/886)
* [Download](https://eprint.iacr.org/2025/886.pdf)
### Abstract
We introduce PaCo, a novel and efficient bootstrapping procedure for the CKKS homomorphic encryption scheme, where PaCo stands for rCL(Bootstrapping via) Partial CoeffToSlotrCY. At a high level, PaCo reformulates the CKKS decryption equation in terms of blind rotations and modular additions. This reformulated decryption circuit is then evaluated homomorphically within the CKKS framework. Our approach makes use of the circle group in the complex plane to simulate modular additions via complex multiplication, and utilizes alternative polynomial ring structures to support blind rotations. These ring structures are enabled by a variant of the CoeffToSlot operation, which we call a partial CoeffToSlot. This yields a new bootstrapping approach within CKKS, achieving a computational complexity which is logarithmic in the number of complex slots. We further introduce a parallelized variant that enables bootstrapping over all CKKS slots with enhanced throughput, highlighting PaCorCOs suitability for practical and large-scale homomorphic applications. In addition to the bootstrapping technique itself, we develop several supporting tools rCo particularly in the context of bit-reversing and alternative ring structures for CKKS rCo which can be of independent interest to the community. Finally, a proof-of-concept implementation confirms that PaCo achieves performance competitive with state-of-the-art methods for CKKS bootstrapping.
## 2025/1297
* Title: On the Relations between Matchmaking Public Key Encryption and Public Key Authenticated Encryption with Keyword Search
* Authors: Takeshi Yoshida, Keita Emura
* [Permalink](https://eprint.iacr.org/2025/1297)
* [Download](https://eprint.iacr.org/2025/1297.pdf)
### Abstract
Ateniese et al. (CRYPTO 2019/JoC 2021) introduced a cryptographic primitive which they call matchmaking encryption (ME), and Identity-based ME (IB-ME) is its identity-based variant. IB-ME supports an equality matching where a sender (encryptor) indicates a receiver's (decryptor's) identity (rcv) in addition to their own ID ($\sigma$), and a receiver indicates a sender's identity (snd) in addition to the own identity ($\rho$). A ciphertext is decrypted if $(\sigma,\rho)=$(snd,rcv). In this paper, we pay attention to the search condition of public key authenticated encryption with keyword search (PAEKS) (Huang-Li, Information Sciences 2017) is reminiscent of the equality matching. We introduce a public key variant of ME which we call PK-ME, and propose a generic construction of PK-ME from PAEKS. As a conceptual contribution, our work lies in revealing a connection between ME and public key searchable encryption, which were independently researched so far. Due to the generic construction of PAEKS (Li-Boyen, IACR CiC 2024), we can instantiate the proposed generic construction from pairings or lattices. We also introduce a weaker version of authenticity and show that it can be instantiated from several complexity assumptions. Finally, we discuss the advantage/disadvantage of PK-ME compared to IB-ME.
## 2025/2200
* Title: Privacy-Preserving Identifier Checking in 5G
* Authors: Marcel D.S.K. Gr|nfenstein, Stefan K||psell, Maryam Zarezadeh
* [Permalink](https://eprint.iacr.org/2025/2200)
* [Download](https://eprint.iacr.org/2025/2200.pdf)
### Abstract
Device identifiers like the International Mobile Equipment Identity (IMEI) are crucial for ensuring device integrity and meeting regulations in 4G and 5G networks. However, sharing these identifiers with Mobile Network Operators (MNOs) brings significant privacy risks by enabling long-term tracking and linking of user activities across sessions. In this work, we propose a privacy-preserving identifier checking method in 5G. This paper introduces a protocol for verifying device identifiers without exposing them to the network while maintaining the same functions as the 3GPP-defined Equipment Identity Register (EIR) process. The proposed solution modifies the PEPSI protocol [USENIX, 2024] for a Private Set Membership (PSM) setting using the BFV homomorphic encryption scheme. This lets User Equipment (UE) prove that its identifier is not on an operatorrCOs blacklist or greylist while ensuring that the MNO only learns the outcome of the verification. The protocol allows controlled deanonymization through an authorized Law Enforcement (LE) hook, striking a balance between privacy and accountability. Implementation results show that the system can perform online verification within five seconds and requires about 15 to 16 MB of communication per session. This confirms its practical use under post-quantum security standards. The findings highlight the promise of homomorphic encryption for managing identifiers while preserving privacy in 5G, laying the groundwork for scalable and compliant verification systems in future 6G networks.
## 2025/2201
* Title: On $k$-sum algorithms for $\{-1,1\}^m$ vectors
* Authors: Pabasara Athukorala, Steven D. Galbraith
* [Permalink](https://eprint.iacr.org/2025/2201)
* [Download](https://eprint.iacr.org/2025/2201.pdf)
### Abstract
We study a new variant of the $k$-sum problem. In the classical formulation, one is given $k$ lists of binary vectors and must find one vector from each list such that their sum is the zero vector. In our variant, vectors are instead chosen from the set $\{-1,1\}^m$. First, we analyse how the complexity of the original problem changes when one use $\pm 1$ vectors. We show that this variant achieves better than square-root complexity when using more than two lists, although its overall complexity for $k \geq 4$ is worse than that for the binary case. As an application of our algorithms, we present a combinatorial attack strategy for a recently proposed variant of the Inhomogeneous Short Integer Solution (ISIS) problem known as the randomised one-more ISIS assumption. Our combinatorial attack is more effective than previous combinatorial attacks on this problem.
We further consider a generalised setting of the $k$-sum problem in which the target sum is not the zero vector, but a given integer vector $Y \in \mathbb{Z}_p^m$ that is known to be a sum of $\pm 1$ vectors. We study the complexity of reconstructing such a decomposition of $Y$ using $k$ lists of candidate vectors. Our analysis shows that, as the number of lists increases, the problem becomes solvable in approximately cube-root time.
## 2025/2202
* Title: Disproving the Linearity of the Polynomials after the Pre-image Substitution in the System of the Third Attempt of MAYO
* Authors: Anna Stefano Narivelomanana
* [Permalink](https://eprint.iacr.org/2025/2202)
* [Download](https://eprint.iacr.org/2025/2202.pdf)
### Abstract
In this work, we analyze the mathematical aspect of the MAYO signature scheme. Following the specification of MAYO, we generate the keys where the secret key is a matrix and the public key is a system of quadratic polynomial of multiple variables; then use them to sign. During the signing procedure, we disprove the claim that the polynomial only has a constant part and a linear part after sampling values for the vinegar variables. Technically, we provide the mathematical expression of an arbitrarily polynomial of the system after substitution and discover that in addition of having a constant part and a linear part, the polynomial also has a quadratic part. The quadratic state of the polynomials after substitution allows us to conclude that signing fails with the third attempt of MAYO.
## 2025/2203
* Title: Hash-based Signature Schemes for Bitcoin
* Authors: Mikhail Kudinov, Jonas Nick
* [Permalink](https://eprint.iacr.org/2025/2203)
* [Download](https://eprint.iacr.org/2025/2203.pdf)
### Abstract
Hash-based signature schemes offer a promising post-quantum alternative for Bitcoin, as their security relies solely on hash function assumptions similar to those already underpinning Bitcoin's design. We provide a comprehensive overview of these schemes, from basic primitives to SPHINCS+ and its variants, and investigate parameter selection tailored to Bitcoin's specific requirements. By applying recent optimizations such as SPHINCS+C, TL-WOTS-TW, and PORS+FP, and by reducing the allowed number of signatures per public key, we achieve significant size improvements over the standardized SPHINCS+ (SLH-DSA).We provide public scripts for reproducibility and discuss limitations regarding key derivation, multi-signatures, and threshold signatures.
## 2025/2204
* Title: Consistency Verification for Zero-Knowledge Virtual Machine on Circuit-Irrelevant Representation
* Authors: Jingyu Ke, Boxuan Liang, Guoqiang Li
* [Permalink](https://eprint.iacr.org/2025/2204)
* [Download](https://eprint.iacr.org/2025/2204.pdf)
### Abstract
Zero-knowledge virtual machines (zkVMs) rely on tabular constraint systems whose verification semantics include gate, lookup, and permutation relations, making correctness auditing substantially more challenging than in arithmetic-circuit DSLs such as Circom. In practice, ensuring that witness-generation code is consistent with these constraints has become a major source of subtle and hard-to-detect bugs. To address this problem, we introduce a high-level semantic model for tabular constraint systems that provides a uniform, circuit-irrelevant interpretation of row-wise constraints and their logical interactions. This abstraction enables an inductive, row-indexed reasoning principle that checks consistency without expanding the full circuit, significantly improving scalability. We implement this methodology in ZIVER and show that it faithfully captures real zkVM designs and automatically validates the consistency of diverse SP1 chip components.
## 2025/2205
* Title: ML-Guided Beam Search for Differential Trail Discovery in SPN Ciphers: A Case Study on GIFT-64
* Authors: Alireza Gholizadeh Shahrbejari, Reza Ebrahimi Atani
* [Permalink](https://eprint.iacr.org/2025/2205)
* [Download](https://eprint.iacr.org/2025/2205.pdf)
### Abstract
This paper introduces an ML-guided scoring heuristic for differential trail beam search in substitution--permutation network (SPN) ciphers. Instead of replacing classical search procedures or relying on heavy learning architectures, we take a residual-learning approach: a gradient boosting regressor is trained to predict the error of a simple nibble-count lower bound on the remaining trail cost. At search time, the predicted residual is fused multiplicatively into the beam scoring function, using per-layer robust normalization and a conservative floor to preserve safety. This design keeps the underlying search structure such as beam width, pruning rules, and lower-bound guarantees unchanged, while aiming to improve the ranking of partial trails. We instantiate the method on the 64-bit block cipher GIFT-64 under the classical Markov differential model. Our implementation reproduces state of the art differential trails with identical weights and round by round differences, and achieves 10--40\% reductions in the number of expanded nodes in moderate-depth searches, with runtime trade-offs analyzed across different model horizons. The results suggest a practical, non-invasive paradigm for enhancing classical cryptanalytic search with learned corrections, without redesigning existing algorithms or probability models, and are in principle applicable to a range of SPN designs.
## 2025/2206
* Title: LifeXP+: Secure, Usable and Reliable Key Recovery for Web3 Applications
* Authors: Panagiotis Chatzigiannis, Suvradip Chakraborty, Shimaa Ahmed
* [Permalink](https://eprint.iacr.org/2025/2206)
* [Download](https://eprint.iacr.org/2025/2206.pdf)
### Abstract
In the Web2 world, users control their accounts using credentials such as usernames and passwords, which can be reset or recovered by centralized servers if the user loses them.
In the decentralized Web3 world however, users control their accounts through cryptographic private-public key pairs which are much more complex to manage securely. In addition, the decentralized nature of Web3 makes account recovery impossible in the absence of predetermined recovery mechanisms. With the proliferation of blockchains and cryptocurrencies over the last years, it is crucial to provide users secure, usable and reliable ways to recover their accounts and assets. However, up to this day, no Web3 recovery method has adequately achieved all three of the above required properties. For instance, conventional ``mnemonic" backups which can deterministically reconstruct a private key require verbatim recall of a fixed word list, creating an unpleasant usability/security trade-off.
In this work, we present a fully-offline protocol called LifeXP$^{+}$, that allows a user to reconstruct a cryptographically-secure private key from a natural-language story, which a user always remembers, such an memorable life event. To ensure usability of our protocol, key reconstruction can work even when the story is later retold with different wording or grammar, only requiring to preserve the semantics.
The protocol combines pre-trained sentence embeddings to capture semantics, locality-sensitive hashing to quantize embeddings into stable bit strings, a cryptographic fuzzy extractor that corrects bit errors caused by paraphrasing, and a biometric factor that is fused with the linguistic factor to boost entropy and enhance security. In our paper we describe the design, show that the protocol achieves the required properties, and provide an evaluation based on publicly-available datasets
which runs completely offline on commodity hardware, showcasing its feasibility.
## 2025/2207
* Title: A General Framework for Registered Functional Encryption via User-Specific Pre-Constraining
* Authors: Tapas Pal, Robert Sch|ndlich
* [Permalink](https://eprint.iacr.org/2025/2207)
* [Download](https://eprint.iacr.org/2025/2207.pdf)
### Abstract
We present a unified framework for constructing registered attribute-based encryption (RABE) and registered functional encryption (RFE) from the standard (bilateral) $k$-Lin assumption in asymmetric bilinear pairing groups. Specifically, our schemes capture the following functionalities.
- RABE for logspace Turing machines. We present the first RABE for deterministic and nondeterministic logspace Turing machines (TMs), corresponding to the uniform complexity classes $\mathsf L$ and $\mathsf{NL}$. That is, we consider policies $g$ computable by a TM with a polynomial time bound $T$ and a logarithmic space bound $S$. The public parameters of our schemes scale only with the number of states of the TM, but remain independent of the attribute length and the bounds $T,S$. Thus, our system is capable of verifying unbounded-length attributes $\mathbf y$ while the maximum number of states needs to be fixed upfront.
- RFE for attribute-based attribute-weighted sums (AB-AWS). Building upon our RABE, we develop RFE for AB-AWS. In this functionality, a function is described by a tuple $f=(g,h)$, takes $(\mathbf y, \{(\mathbf x_j, \mathbf z_j)\}_{j\in[N]})$ as input for an unbounded integer $N$, and outputs $\sum_{j\in[N]}\mathbf z_jh(\mathbf x_j)^\top$ if and only if $g(\mathbf y) = 0$. Here, $\{\mathbf z_j\}_j$ are private inputs that are hidden in the ciphertext, whereas $\mathbf y$ and $\{\mathbf x_j\}_j$ can be public. Our construction can instantiate $g,h$ with deterministic logspace TMs, while a previous construction due to [Pal and Sch|ndlich, Eprint 2025] only supports arithmetic branching programs (ABPs), i.e. a non-uniform model of computation.
- RFE for attribute-based quadratic functions (AB-QF). Furthermore, we build the first RFE for AB-QF with compact ciphertexts. In this functionality, a function is described by a tuple $f=(g,\mathbf h)$, takes input $(\mathbf y,(\mathbf z_1,\mathbf z_2))$ and outputs $(\mathbf z_1\otimes\mathbf z_2)\mathbf h^\top$ if and only if $g(\mathbf y)=0$. Here, $(\mathbf z_1, \mathbf z_2)$ are private inputs whereas the attribute $\mathbf y$ is public. Policies can be computed by ABPs or deterministic logspace TMs. Prior to our work, the only known construction of RFE for quadratic functions from standard assumptions [Zhu et al., Eurocrypt 2024] did not provide any access control.
Conceptually, we transfer the framework of [Lin and Luo, Eurocrypt 2020], which combines linear FE with information-theoretic garbling schemes, from standard to registered FE. At the core of our constructions, we introduce a novel RFE for inner products with user-specific pre-constraining of the functions which enables the on-the-fly randomization of garbling schemes akin to standard inner-product FE. This solves an open question raised in [Zhu et al., Asiacrypt 2023] who constructed RABE from predicate encodings but left open the problem of building RABE in a more general setting from linear garbling schemes.
## 2025/2208
* Title: Vectorized SVE2 Optimization of the Post-Quantum Signature ML-DSA on ARMv9-A Architecture
* Authors: Hanyu Wei, Wenqian Li, Shiyu Shen, Hao Yang, Wenbo Guo, Yunlei Zhao * [Permalink](https://eprint.iacr.org/2025/2208)
* [Download](https://eprint.iacr.org/2025/2208.pdf)
### Abstract
Post-quantum cryptography (PQC) is essential to securing data in the quantum computing era, and standardization efforts led by NIST have driven extensive research on practical and efficient implementations. With the emerging deployment of ARMv9-A processors in mobile and edge devices, optimizing PQC algorithms for this architecture is becoming increasingly important. Among the NIST-selected digital signature schemes, ML-DSA stands out due to its strong security and efficiency, making it suitable for general purposes. In this work, we present a highly optimized implementation of ML-DSA for the ARMv9-A architecture, leveraging the SVE2 vector instruction set. We propose a vector-friendly sparse polynomial multiplication scheme and introduce an early-check mechanism that significantly reduces redundant computation in the signature validity check. We also design a tailored conditional instruction pipeline to further enhance efficiency. Our implementation achieves a 70.7% performance improvement in signature generation compared to the baseline implementation, establishing the first highly vectorized ML-DSA implementation on ARMv9-A by SVE2 extension. These results demonstrate the practicality of deploying high-performance post-quantum signatures on next-generation mobile and edge platforms.
## 2025/2209
* Title: A New Practical Cube Attack via Recovering Numerous Superpolys
* Authors: Min Zhang, Yao Sun
* [Permalink](https://eprint.iacr.org/2025/2209)
* [Download](https://eprint.iacr.org/2025/2209.pdf)
### Abstract
Cube attack is one of the most powerful approaches for recovering keys of stream ciphers. Practical cube attacks generate several superpolys first and solve the system constructed by these superpolys afterward. Unlike previous practical attacks, we propose a new cube attack that transfers the difficulty of generating easy-solving superpolys to solving the system built by numerous nonlinear ones. In the offline phase, we recovered lots of nonlinear superpolys by improving the approach proposed by Delaune et al. at SAC 2022 in theory. In the online phase, taking advantage of the sparsity and asymmetry of these numerous superpolys, we present a new testing method to solve the constructed system efficiently. As applications, the latest attack could practically recover the keys for 820- and 832-round Trivium with the time complexity no more extensive than $2^{46}$ and $2^{50}$, while the previous highest number of rounds of Trivium that can be attacked practically is 830. We believe the proposed approach can be used to attack more rounds of Trivium and other stream ciphers.
## 2025/2210
* Title: Multi-Client Functional Encryption for Small Domains
* Authors: Suvasree Biswas, Mohit Vaid, Arkady Yerukhimovich
* [Permalink](https://eprint.iacr.org/2025/2210)
* [Download](https://eprint.iacr.org/2025/2210.pdf)
### Abstract
In this paper, we revisit the problem of multi-client functional encryption (MCFE) for general functions. Specifically, we consider
the setting of private-key MCFE for constant-arity functions where the
input domain is polynomial in the security parameter. Surprisingly, we
show that in this setting it is possible to construct a private-key MCFE
scheme secure for a bounded number of key and encryption queries based
only on the minimal assumption that one-way functions exist. In contrast, all prior constructions of MCFE for general functions require very
strong assumptions such as indistinguishability obfuscation or multilinear maps.
Our main technique is to show that private-key MCFE for polynomial
input domain can be built from any private-key multi-input functional encryption (MIFE) while inheriting the security properties of the underlying MIFE. Instantiating our construction with the MIFE of Brakerski et
al. (Eurocrypt 2016) gives us a construction based only on the existence
of one-way functions.
## 2025/2211
* Title: Architecture-private Zero-knowledge Proof of Neural Networks
* Authors: Yanpei Guo, Zhanpeng Guo, Wenjie Qu, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2025/2211)
* [Download](https://eprint.iacr.org/2025/2211.pdf)
### Abstract
A zero-knowledge proof of machine learning (zkML) enables a party to prove that it has correctly executed a committed model using some public input, without revealing any information about the model itself. An ideal zkML scheme should conceal both the model architecture and the model parameters. However, existing zkML approaches for neural networks primarily focus on hiding model parameters. For convolutional neural network (CNN) models, these schemes reveal the entire architecture, including number and sequence of layers, kernel sizes, strides, and residual connections.
In this work, we initiate the study of architecture-private zkML for neural networks, with a focus on CNN models. Our core contributions includes 1) parametrized rank-one constraint system (pR1CS), a generalization of R1CS, allowing the prover to commit to the model architecture in a more friendly manner; 2) a proof of functional relation scheme to demonstrate the committed architecture is valid.
Our scheme matches the prover complexity of BFG+23 (CCS'23), the current state-of-the-art in zkML for CNNs. Concretely, on VGG16 model, when batch proving 64 instances, our scheme achieves only 30% slower prover time than BFG+23 (CCS'23) and 2.3$\times$ faster than zkCNN (CCS'21). This demonstrates that our approach can hide the architecture in zero-knowledge proofs for neural networks with minor overhead. In particular, proving a matrix multiplication using our pR1CS can be at least 3$\times$ faster than using conventional R1CS, highlighting the effectiveness of our optimizations.
## 2025/2212
* Title: Architecture-private Zero-knowledge Proof of Neural Networks
* Authors: Yanpei Guo, Zhanpeng Guo, Wenjie Qu, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2025/2212)
* [Download](https://eprint.iacr.org/2025/2212.pdf)
### Abstract
A zero-knowledge proof of machine learning (zkML) enables a party to prove that it has correctly executed a committed model using some public input, without revealing any information about the model itself. An ideal zkML scheme should conceal both the model architecture and the model parameters. However, existing zkML approaches for neural networks primarily focus on hiding model parameters. For convolutional neural network (CNN) models, these schemes reveal the entire architecture, including number and sequence of layers, kernel sizes, strides, and residual connections.
In this work, we initiate the study of architecture-private zkML for neural networks, with a focus on CNN models. Our core contributions includes 1) parametrized rank-one constraint system (pR1CS), a generalization of R1CS, allowing the prover to commit to the model architecture in a more friendly manner; 2) a proof of functional relation scheme to demonstrate the committed architecture is valid.
Our scheme matches the prover complexity of BFG+23 (CCS'23), the current state-of-the-art in zkML for CNNs. Concretely, on VGG16 model, when batch proving 64 instances, our scheme achieves only 30% slower prover time than BFG+23 (CCS'23) and 2.3$\times$ faster than zkCNN (CCS'21). This demonstrates that our approach can hide the architecture in zero-knowledge proofs for neural networks with minor overhead. In particular, proving a matrix multiplication using our pR1CS can be at least 3$\times$ faster than using conventional R1CS, highlighting the effectiveness of our optimizations.
## 2025/2213
* Title: Simplified Meet-in-the-middle Preimage Attacks on AES-based Hashing
* Authors: Mathieu Degr|-, Patrick Derbez, Andr|- Schrottenloher
* [Permalink](https://eprint.iacr.org/2025/2213)
* [Download](https://eprint.iacr.org/2025/2213.pdf)
### Abstract
The meet-in-the-middle (MITM) attack is a powerful cryptanalytic technique leveraging time-memory tradeoffs to break cryptographic primitives. Initially introduced for block cipher cryptanalysis, it has since been extended to hash functions, particularly preimage attacks on AES-based compression functions. Over the years, various enhancements such as superposition MITM (Bao et al., CRYPTO 2022) and bidirectional propagations have significantly improved MITM attacks, but at the cost of increasing complexity of automated search models. In this work, we propose a unified mixed integer linear programming (MILP) model designed to improve the search for optimal pre-image MITM attacks against AES-based compression functions.
Our model generalizes previous approaches by simplifying both the modeling and the corresponding attack algorithm. In particular, it ensures that all identified attacks are valid. The results demonstrate that our framework not only recovers known attacks on AES and Whirlpool but also discovers new attacks with lower memory complexities, and new quantum attacks.
## 2025/2214
* Title: Accelerating TFHE with Sorted Bootstrapping Techniques
* Authors: Loris Bergerat, Jean-Baptiste Orfila, Adeline Roux-Langlois, Samuel Tap
* [Permalink](https://eprint.iacr.org/2025/2214)
* [Download](https://eprint.iacr.org/2025/2214.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) enables secure computation over encrypted data, offering a breakthrough in privacy-preserving computing. Despite its promise, the practical deployment of FHE has been hindered by the significant computational overhead, especially in general-purpose bootstrapping schemes. In this work, we build upon the recent advancements of [LY23] to introduce a variant of the functional/programmable bootstrapping. By carefully sorting the steps of the blind rotation, we reduce the overall number of external products without compromising correctness. To further enhance efficiency, we propose a novel modulus-switching technique that increases the likelihood of satisfying pruning conditions, reducing computational overhead.
Extensive benchmarks demonstrate that our method achieves a speedup ranging from 1.75x to 8.28x compared to traditional bootstrapping and from 1.26x to 2.14x compared to [LY23] bootstrapping techniques.
Moreover, we show that this technique is better adapted to the IND-CPA-D security model by reducing the performance downgrade it implies.
## 2025/2215
* Title: Obfuscating Pseudorandom Functions is Post-Quantum Complete
* Authors: Pedro Branco, Abhishek Jain, Akshayaram Srinivasan
* [Permalink](https://eprint.iacr.org/2025/2215)
* [Download](https://eprint.iacr.org/2025/2215.pdf)
### Abstract
The last decade has seen remarkable success in designing and uncovering new applications of indistinguishability obfuscation (i$\mathcal{O}$). The main pressing question in this area is whether post-quantum i$\mathcal{O}$ exists. All current lattice-based candidates rely on new, non-standard assumptions, many of which are known to be broken.

To make systematic progress on this front, we investigate the following question: can general-purpose i$\mathcal{O}$ be reduced, assuming only learning with errors (LWE), to obfuscating a smaller class of functions? The specific class of functions we consider are {\em pseudorandom functions} (PRFs), which constitute a natural functionality of independent interest. We show the following results:
- We construct exponentially-efficient i$\mathcal{O}$ (xi$\mathcal{O}$) for general circuits based on LWE in the pseudorandom oracle model -- a variant of the Random Oracle model (Jain et al., CRYPTO'23). Our construction requires the pseudorandom oracle model heuristic to hold for a specific pseudorandom function and we prove its security against classical adversaries.
- We construct (post-quantum) i$\mathcal{O}$ for general circuits in the standard model based on (post-quantum) sub-exponentially secure LWE and (post-quantum) sub-exponentially secure {\em average-case} i$\mathcal{O}$ -- a natural notion of i$\mathcal{O}$ for pseudorandom functions that we define.
To obtain these results, we generalize the ``encrypt-evaluate-decrypt'' paradigm used in prior works by replacing the use of fully homomorphic encryption with succinct secure two-party computation where parties obtain additive output shares (Boyle et al., EUROCRYPT'25 and Abram et al., STOC'25).
## 2025/2216
* Title: AgentCrypt: Advancing Privacy and (Secure) Computation in AI Agent Collaboration
* Authors: Harish Karthikeyan, Yue Guo, Leo de Castro, Antigoni Polychroniadou, Leo Ardon, Udari Madhushani Sehwag, Sumitra Ganesh, Manuela Veloso
* [Permalink](https://eprint.iacr.org/2025/2216)
* [Download](https://eprint.iacr.org/2025/2216.pdf)
### Abstract
As AI agents increasingly operate in real-world, multi-agent environments, ensuring reliable and context-aware privacy in agent communication is critical, especially to comply with evolving regulatory requirements. Traditional access controls are insufficient, as privacy risks often arise after access is granted; agents may use information in ways that compromise privacy, such as messaging humans, sharing context with other agents, making tool calls, persisting data, or generating derived private information. Existing approaches often treat privacy as a binary constraint, whether data is shareable or not, overlooking nuanced, role-specific, and computation-dependent privacy needs essential for regulatory compliance.
Agents, including those based on large language models, are inherently probabilistic and heuristic. There is no formal guarantee of how an agent will behave for any query, making them ill-suited for operations critical to security. To address this, we introduce AgentCrypt, a four-tiered framework for fine-grained, encrypted agent communication that adds a protection layer atop any AI agent platform. AgentCrypt spans unrestricted data exchange (Level 1) to fully encrypted computation using techniques such as homomorphic encryption (Level 4). Crucially, it guarantees the privacy of tagged data is always maintained, prioritizing privacy above correctness.
AgentCrypt ensures privacy across diverse interactions and enables computation on otherwise inaccessible data, overcoming barriers such as data silos. We implemented and tested it with Langgraph and Google ADK, demonstrating versatility across platforms. We also introduce a benchmark dataset simulating privacy-critical tasks at all privacy levels, enabling systematic evaluation and fostering the development of regulatable machine learning systems for secure agent communication and computation.
## 2025/2217
* Title: Ideal Private Simultaneous Messages Schemes and Their Applications
* Authors: Keitaro Hiwatashi, Reo Eriguchi
* [Permalink](https://eprint.iacr.org/2025/2217)
* [Download](https://eprint.iacr.org/2025/2217.pdf)
### Abstract
Private Simultaneous Messages (PSM) is a minimal model for secure computation, where two parties, Alice and Bob, have private inputs $x,y$ and a shared random string. Each of them sends a single message to an external party, Charlie, who can compute $f(x,y)$ for a public function $f$ but learns nothing else. The problem of narrowing the gap between upper and lower bounds on the communication complexity of PSM has been widely studied, but the gap still remains exponential. In this work, we study the communication complexity of PSM from a different perspective and introduce a special class of PSM, referred to as \textit{ideal PSM}, in which each party's message length attains the minimum, that is, their messages are taken from the same domain as inputs. We initiate a systematic study of ideal PSM with a complete characterization, several positive results, and applications. First, we provide a characterization of the class of functions that admit ideal PSM, based on permutation groups acting on the input domain. This characterization allows us to derive asymptotic upper bounds on the total number of such functions and a complete list for small domains. We also present several infinite families of functions of practical interest that admit ideal PSM. Interestingly, by simply restricting the input domains of these ideal PSM schemes, we can recover most of the existing PSM schemes that achieve the best known communication complexity in various computation models. As applications, we show that these ideal PSM schemes yield novel communication-efficient PSM schemes for functions with sparse or dense truth-tables and those with low-rank truth-tables. Furthermore, we obtain a PSM scheme for general functions that improves the constant factor in the dominant term of the best known communication complexity. An additional advantage is that our scheme simplifies the existing construction by avoiding the hierarchical design of internally invoking PSM schemes for smaller functions.
## 2025/2218
* Title: The Syndrome Weight Distribution in Quasi-Cyclic Codes, Applications to BIKE and HQC
* Authors: Antoine Mesnard, Jean-Pierre Tillich, Valentin Vasseur
* [Permalink](https://eprint.iacr.org/2025/2218)
* [Download](https://eprint.iacr.org/2025/2218.pdf)
### Abstract
Many important code-based cryptographic schemes such as the NIST post-quantum competition finalist BIKE and the to be standardized HQC scheme rely on Quasi-Cyclic Moderate-Density Parity-Check codes (QC-MDPC). A very important issue here is to predict accurately the Decoding Failure Rate (DFR).
This DFR is intimately connected to the syndrome weight distribution of the QC-MDPC codes used in these schemes. This problem is treated in HQC by modeling the syndrome bits by Bernoulli variables which is known to be inaccurate. The rationale is that it gives a pessimistic estimate of the DFR. In BIKE the syndrome weight is modeled by the syndrome weight of a regular MDPC code which is itself computed by a simplified model. The accuracy of this modeling is not well understood. NIST perceived that BIKE DFR estimation lacked maturity. This led to its dismissal in the competition. The purpose of this paper is to advance on this difficult issue of understanding the syndrome weight distribution of quasi-cyclic codes.
Our contribution here is threefold. First we provide a rigorous tool for computing the syndrome weight of a regular code through a generating function and a saddle point approximation. We use this approach to show that the Markov chain model used for estimating the syndrome weight in [ABP24] is remarkably accurate. Second, we also prove that the regular model is not accurate for very low syndrome weights and provide a complete model of the syndrome weight distribution of a QC-MDPC code which can at the same time be computed quickly and fits remarkably well the experiments. We use this to show that for BIKE the probability of the events where the regular model differs from the QC-MDPC syndrome distribution is too low to be of concern. We also show that the variance of the syndrome weight distribution of a QC-MDPC code can be computed efficiently and is a handy tool for estimating accurately
the syndrome weight distribution in the moderate deviation regime. We use it to give an accurate prediction of the DFR for a given key of HQC. This gives compelling evidence that the DFR of a typical secret key of HQC is significantly below $2^{- \lambda}$ where $\lambda$ is the security parameter and that weak keys for HQC are too rare to be of concern.
## 2025/2219
* Title: HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers
* Authors: Mohamed Malhou, Ludovic Perret, Kristin Lauter
* [Permalink](https://eprint.iacr.org/2025/2219)
* [Download](https://eprint.iacr.org/2025/2219.pdf)
### Abstract
At NeurIPS 2024, Kera et al. introduced the use of transformers for computing Groebner bases, a central object in computer algebra with numerous practical applications. In this paper, we improve this approach by applying Hierarchical Attention Transformers (HATs) to solve systems of multivariate polynomial equations via Groebner bases computation. The HAT architecture incorporates a tree-structured inductive bias that enables the modeling of hierarchical relationships present in the data and thus achieves significant computational savings compared to conventional flat attention models. We generalize to arbitrary depths and include a detailed computational cost analysis. Combined with curriculum learning, our method solves instances that are much larger than those in Kera et al. (2024 Learning to compute Groebner bases)
## 2025/2220
* Title: Performance Improvements of ZK-Prover for rWasm: A Sound and Efficient AIR for 32-bit Division and Remainder
* Authors: Suleyman Kardas, Mehmet Sabir Kiraz, Dmitry Savonin, Yao Wang, Aliaksei Dziadziuk
* [Permalink](https://eprint.iacr.org/2025/2220)
* [Download](https://eprint.iacr.org/2025/2220.pdf)
### Abstract
Zero-knowledge virtual machines (zkVMs) must correctly model all edge cases of lowlevel machine instructions, including division and remainder, while keeping algebraic constraints simple enough for efficient STARK proving. This work presents a focused but meaningful redesign of the DivRemChip used in the SP1 zkVM (as adapted to rWasm) to implement WASMrCOs 32-bit division and remainder instructions (i32.div{u,s}, i32.rem{u,s}) over the BabyBear field. Our chip remains local (single-row AIR) and is purpose-built so that all rCLsmall aggregaterCY expressions are strictly bounded by the BabyBear modulus, allowing us to use inverses securely without ever inverting zero. We replace heavier constant-equality logic and trap gadgets with:
(a) a lightweight small-aggregate zero-test for magnitudes that is sound in BabyBear,
(b) a simple, byte-level mechanism for detecting the special value INT MIN using only degree-2 constraints,
(c) a low-degree test for c = reA1 based on checking |c| = 1 together with the sign bit, and
(d) a constraint pattern ensuring that divide-by-zero and the overflow case i32.div s(INT MIN,-1) are not provable, matching WASM trap semantics.
The resulting AIR has maximal degree 3, removes all rCLinvert-zerorCY failure modes in BabyBear, and enforces the correct semantics for every non-trapping instruction. A malicious prover test framework based on the SP1 CPU bus shows that any incorrect witness causes constraint failure, while honest execution traces for extensive boundary tests and mixed programs produce valid proofs over BabyBear. Our design also improves efficiency: the trace width drops from 102 to 74 columns, all Mul/Add/Lt/MSB cross-chip calls are removed, and each row requires only a single CPU-bus interaction. Prover benchmarks on unsigned, signed, and mixed workloads with up to 125,000 division/remainder operations show a consistent 4rCo6% reduction in single-threaded proving time compared to the original SP1 DivRemChip as adapted to rWasm, with a paired t-test across program sizes confirming that the improvement is statistically significant at the 95% confidence level.
## 2025/2221
* Title: Sparse Vector Reconstruction from Distance Spectrum using Soft Information
* Authors: Magali Salom, Nicolas Sendrier, Valentin Vasseur
* [Permalink](https://eprint.iacr.org/2025/2221)
* [Download](https://eprint.iacr.org/2025/2221.pdf)
### Abstract
QC-MDPC based schemes feature secret sparse cyclic binary vectors. When those vectors are sparse enough, they can be reconstructed from their distance spectrum, that is the set of all distances between the coordinates of the non-zero coefficients. In this work, we revisit the reconstruction algorithms and we explore to what extent a secret sparse vector can be recovered from a partial knowledge of its distance spectrum. In particular, we show how to efficiently use reliability (soft information) in the reconstruction process. Another aspect of this work is to investigate which kind of side-channel leaks information about the distance spectrum and to understand the models that enable us to quantify the reliability on leaking data depending on the amount of side-channel observations (or queries). For instance, we show that for BIKE level 1, assuming that a side-channel leaks information about the syndrome weight, using soft information in the reconstruction process reduces the number of queries by a factor 10. Our technique can also be applied to HQC, which also features sparse secret vector, with similar figures, assuming there exists a side-channel leaking relevant information, the error weight in the case of HQC.
## 2025/2222
* Title: Improved Pseudorandom Codes from Permuted Puzzles
* Authors: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs * [Permalink](https://eprint.iacr.org/2025/2222)
* [Download](https://eprint.iacr.org/2025/2222.pdf)
### Abstract
Watermarks are an essential tool for identifying AI-generated content. Recently, Christ and Gunn (CRYPTO '24) introduced pseudorandom error-correcting codes (PRCs), which are equivalent to watermarks with strong robustness and quality guarantees. A PRC is a pseudorandom encryption scheme whose decryption algorithm tolerates a high rate of errors. Pseudorandomness ensures quality preservation of the watermark, and error tolerance of decryption translates to the watermark's ability to withstand modification of the content.
In the short time since the introduction of PRCs, several works (NeurIPS '24, RANDOM '25, STOC '25) have proposed new constructions. Curiously, all of these constructions are vulnerable to quasipolynomial-time distinguishing attacks. Furthermore, all lack robustness to edits over a constant-sized alphabet, which is necessary for a meaningfully robust LLM watermark. Lastly, they lack robustness to adversaries who know the watermarking detection key. Until now, it was not clear whether any of these properties was achievable individually, let alone together.
We construct pseudorandom codes that achieve all of the above: plausible subexponential pseudorandomness security, robustness to worst-case edits over a binary alphabet, and robustness against even computationally unbounded adversaries that have the detection key. Pseudorandomness rests on a new assumption that we formalize, the permuted codes conjecture, which states that a distribution of permuted noisy codewords is pseudorandom. We show that this conjecture is implied by the permuted puzzles conjecture used previously to construct doubly efficient private information retrieval. To give further evidence, we show that the conjecture holds against a broad class of simple distinguishers, including read-once branching programs.
## 2025/2223
* Title: Analysis of the Security Design, Engineering, and Implementation of the SecureDNA System
* Authors: Alan T. Sherman, Jeremy J. Romanik Romano, Edward Zieglar, Enis Golaszewski, Jonathan D. Fuchs, William E. Byrd
* [Permalink](https://eprint.iacr.org/2025/2223)
* [Download](https://eprint.iacr.org/2025/2223.pdf)
### Abstract
We analyze security aspects of the SecureDNA system regarding its system design, engineering, and implementation. This system enables DNA synthesizers to screen order requests against a database of hazards. By applying novel cryptography involving distributed oblivious pseudorandom functions, the system aims to keep order requests and the database of hazards secret. Discerning the detailed operation of the system in part from source code (Version 1.0.8), our analysis examines key management, certificate infrastructure, authentication, and rate-limiting mechanisms. We also perform the first formal-methods analysis of the mutual authentication, basic request, and exemption-handling protocols.
Without breaking the cryptography, our main finding is that SecureDNA's custom mutual authentication protocol SCEP achieves only one-way authentication: the hazards database and keyservers never learn with whom they communicate. This structural weakness violates the principle of defense in depth and enables an adversary to circumvent rate limits that protect the secrecy of the hazards database, if the synthesizer connects with a malicious or corrupted keyserver or hashed database. We point out an additional structural weakness that also violates the principle of defense in depth: inadequate cryptographic bindings prevent the system from detecting if responses, within a TLS channel, from the hazards database were modified. Consequently, if a synthesizer were to reconnect with the database over the same TLS session, an adversary could replay and swap responses from the database without breaking TLS. Although the SecureDNA implementation does not allow such reconnections, it would be stronger security engineering to avoid the underlying structural weakness. We identify these vulnerabilities and suggest and verify mitigations, including adding strong bindings. Software Version 1.1.0 fixes SCEP with our proposed SCEP+ protocol.
Our work illustrates that a secure system needs more than sound mathematical cryptography; it also requires formal specifications, sound key management, proper binding of protocol message components, and careful attention to engineering and implementation details.
## 2025/2224
* Title: Beyond Ethernet: Reusing MACsec for CANsec
* Authors: Friedrich Wiemer, Arthur Mutter, Jonathan Ndop, Julian G||ppert, Axel Sikora, Thierry Walrant
* [Permalink](https://eprint.iacr.org/2025/2224)
* [Download](https://eprint.iacr.org/2025/2224.pdf)
### Abstract
In the past, Secure Onboard Communication (SecOC) has been defined to serve as the foundational mechanism for securing in-vehicle networks. For over a decade, it has been used in hundreds of millions of automotive systems. Its application-layer design and AUTOSAR-based specification have enabled broad adoption across diverse platforms. However, this design also introduces challenges: software-centric dependencies complicate full hardware integration and can limit scalability in resource-constrained electronic control units, particularly as bandwidth demands continue to grow.
To address these constraints, CANsec has been proposed to address the security objectives of CAN XL. As a Layer 2 security protocol, CANsec aims to overcome SecOCrCOs shortcomings and offer modern guarantees comparable to MACsec. However, the CANsec specification remains under active development even after several years of work, leaving a gap between conceptual goals and practical deployment.
This paper proposes a pragmatic and standards-aligned solution: it re-uses existing MACsec specifications and implementations as the security engine for CAN XL.
MACsec, standardized for over two decades and widely scrutinized in both academic and industrial contexts, offers robust and well-understood security functions. Our approach introduces a lightweight wrapper that maps CAN XL frames to virtual Ethernet frames, enabling MACsec to provide confidentiality, integrity, authenticity, and freshness. We formally define the wrapping process, frame formats, and protocol data units, while preserving MACsecrCOs security properties, adapting them to the constraints and requirements of automotive networks. This enables a practical and secure path forward for CAN XL deployment, leveraging mature cryptographic algorithms and protocols without compromising performance or assurance.
To support standardization and practical adoption, we have submitted this approach to the CAN in Automation (CiA) CANsec specification task force, CiA's IG 04 SIG 01 TF 03 CAN XL security, contributing to the ongoing effort to define an efficient, standardized and interoperable security solution for CAN XL.
## 2025/2225
* Title: Learning with Errors with Output Dependencies: LWE, LWR, and Physical Learning Problems under the Same Umbrella
* Authors: Cl|-ment Hoffmann, Pierrick M|-aux, M|-lissa Rossi, Fran|oois-Xavier Standaert
* [Permalink](https://eprint.iacr.org/2025/2225)
* [Download](https://eprint.iacr.org/2025/2225.pdf)
### Abstract
Learning problems have become a foundational element for constructing quantum-resistant cryptographic schemes, finding broad application even beyond, such as in Fully Homomorphic Encryption. The increasing complexity of this field, marked by the rise of physical learning problems due to research into side-channel leakage and secure hardware implementations, underscores the urgent need for a more comprehensive analytical framework capable of encompassing these diverse variants.
In response, we introduce Learning With Error with Output Dependencies (LWE-OD), a novel learning problem defined by an error distribution that depends on the inner product value and therefore on the key. LWE-OD instances are remarkably versatile, generalizing both established theoretical problems like Learning With Errors (LWE) or Learning With Rounding (LWR), and emerging physical problems such as Learning With Physical Rounding (LWPR).
Our core contribution is establishing a reduction from LWE-OD to LWE. This is accomplished by leveraging an intermediate problem, denoted qLWE. Our reduction follows a two-step, simulator-based approach, yielding explicit conditions that guarantee LWE-OD is at least as computationally hard as LWE. While this theorem provides a valuable reduction, it also highlights a crucial distinction among reductions: those that allow explicit calculation of target distributions versus weaker ones with conditional results.
To further demonstrate the utility of our framework, we offer new proofs for existing results, specifically the reduction from LWR to LWE and from Learning Parity with Noise with Output Dependencies (LPN-OD) to LPN. This new reduction opens the door for a potential reduction from LWPR to LWE.
## 2025/2226
* Title: Learning With Physical Rounding for Linear and Quadratic Leakage Functions
* Authors: Cl|-ment Hoffmann, Pierrick M|-aux, Charles Momin, Yann Rotella, Fran|oois-Xavier Standaert, Balazs Udvarhelyi
* [Permalink](https://eprint.iacr.org/2025/2226)
* [Download](https://eprint.iacr.org/2025/2226.pdf)
### Abstract
Fresh re-keying is a countermeasure against side-channel analysis where an ephemeral key is derived from a long-term key using a public random value. Popular instances of such schemes rely on key-homomorphic primitives, so that the re-keying process is easy to mask and the rest of the (e.g., block cipher) computations can run with cheaper countermeasures. The main requirement for these schemes to be secure is that the leakages of the ephemeral keys do not allow recovering the long-term key. The Learning with Physical Rounding (LWPR) problem formalizes this security in a practically-relevant model where the adversary can observe noise-free leakages. It can be viewed as a physical version of the Learning With Rounding (LWR) problem, where the rounding is performed by a leakage function and therefore does not have to be computed explicitly. In this paper, we first consolidate the intuition that LWPR cannot be secure in a serial implementation context without additional countermeasures (like shuffling), due to attacks exploiting worst-case leakages that can be mounted with practical data complexity. We then extend the understanding of LWPR in a parallel implementation setting. On the one hand, we generalize its robustness against cryptanalysis taking advantage of any (i.e., not only worst-case) leakage. A previous work claimed security in the specific context of a Hamming weight leakage function. We clarify necessary conditions to maintain this guarantee, based on the degree of the leakage function and the accuracy of its coefficients. On the other hand, we show that parallelism inherently provides good security against attacks exploiting worst-case leakages. We finally confirm the practical relevance of these findings by validating our assumptions experimentally for an exemplary implementation.
## 2025/2227
* Title: Time Memory Trade-off For Enumeration
* Authors: Yuanmi Chen, Zhao Chen, Tingting Guo, Chao Sun, Weiqiang Wen, Yu Yu * [Permalink](https://eprint.iacr.org/2025/2227)
* [Download](https://eprint.iacr.org/2025/2227.pdf)
### Abstract
We incorporate a meet-in-the-middle strategy into the enumeration algorithm, enabling a tunable time-memory trade-off. The algorithm can achieve a minimum asymptotic time complexity of \(n^{n/(4e) + o(n)}\), which, in return, demands memory of the same order. This represents a square-root improvement over the state-of-the-art enumeration algorithms. More generally, our approach attains a time complexity of~$n^{cn/(2e) + o(n)}$ with memory usage \(n^{(1-c)n/(2e) + o(n)}\), where $c$ is any constant satisfying \(\frac{1}{2} \leq c < 1\).
Our approach decouples the head and tail blocks of the lattice basis. For a properly selected parameter, each enumeration space becomes asymptotically the square root of the original search space. Each tail vector is then extended to the head block space to find its closest vectors using an efficient neighboring search algorithm. Among all pairs of neighboring vectors that we iterate through, the shortest difference vector is then the solution to the Shortest Vector Problem (SVP).
Apart from the exact version of the algorithm which is of theoretical interest, we also propose heuristic strategies to improve the practical efficiency. First, we show the adaptation of our algorithm to pruned enumeration. Then we show that with a particularly chosen backbone lattice (rescaled~\(\mathbb{Z}^n\)), we are able to accelerate the neighboring search process to an extremely efficient degree. Finally, we optimize parameters and give a practical cost estimation to show how much acceleration we could bring using this new algorithm.
## 2025/2228
* Title: PIRANHAS: PrIvacy-Preserving Remote Attestation in Non-Hierarchical Asynchronous Swarms
* Authors: Jonas Hofmann, Philipp-Florens Lehwalder, Shahriar Ebrahimi, Parisa Hassanizadeh, Sebastian Faust
* [Permalink](https://eprint.iacr.org/2025/2228)
* [Download](https://eprint.iacr.org/2025/2228.pdf)
### Abstract
Remote attestation is a fundamental security mechanism for assessing the integrity of remote devices. In practice, widespread adoption of attestation schemes is hindered by a lack of public verifiability and the requirement for interaction in existing protocols. A recent work by Ebrahimi et al. (NDSS'24) constructs publicly verifiable, non-interactive remote attestation, disregarding another important requirement for attesting sensitive systems: privacy protection.
Similar needs arise in IoT swarms, where many devices, potentially processing sensitive data, should produce a single attestation.
In this paper, we take on both challenges. We present PIRANHAS, a publicly verifiable, asynchronous, and anonymous attestation scheme for individual devices and swarms. We leverage zk-SNARKs to transform any classical, symmetric remote attestation scheme into a non-interactive, publicly verifiable, and anonymous one. Verifiers only ascertain the validity of the attestation, without learning any identifying information about the involved devices.
For IoT swarms, PIRANHAS aggregates attestation proofs for the entire swarm using recursive zk-SNARKs. Our system supports arbitrary network topologies and allows nodes to dynamically join and leave the network. We provide formal security proofs for the single-device and swarm setting, showing that our construction meets the desired security guarantees. Further, we provide an open-source implementation of our scheme using the Noir and Plonky2 framework, achieving an aggregation runtime of just 356ms.
## 2025/2229
* Title: Practically Implementable Minimal Universal Gate Sets for Multi-Qudit Systems with Cryptographic Validation
* Authors: Anisha Dutta, Sayantan Chakraborty, Chandan Goswami, Avishek Adhikari
* [Permalink](https://eprint.iacr.org/2025/2229)
* [Download](https://eprint.iacr.org/2025/2229.pdf)
### Abstract
The rapid growth of quantum technologies highlights the need for
scalable models of computation that go beyond qubits and exploit the richer structure of Qudits. This paper introduces a novel and efficient approach for defining universal gate sets specifically designed for higher-dimensional Qudit systems (N reN 2), addressing the limitations of traditional qubit-based approaches. We present a systematic methodology for constructing fundamental Qudit gates through the inherent structure of Qudit operators, providing a robust theoretical foundation for universal quantum computation with Qudits. Our rigorously proven universal and minimal gate set enables more efficient quantum circuit design. We demonstrate the construction of multidimensional extensions of controlled operations from these fundamental elements. To facilitate practical application, we provide a Python-based algorithm for decomposing arbitrary multi-Qudit operations, accompanied by detailed time- and space-complexity analyses. The framework is further validated through end-to-end implementations of GroverrCOs algorithm and QKD, comparing traditional gate constructions with circuits entirely synthesized from the proposed universal gate set. These validations demonstrate not only the functional equivalence of the decomposed circuits, but also their direct relevance to the advancement of cryptographic protocols, paving the way for more efficient and secure Qudit-based quantum cryptography.
## 2025/2230
* Title: Efficient Algorithms for $\mathbb{G}_2$ Subgroup Membership testing on Pairing-friendly Curves
* Authors: Jianming Lin, Yu Dai, Chang-An Zhao, Yuhao Zheng
* [Permalink](https://eprint.iacr.org/2025/2230)
* [Download](https://eprint.iacr.org/2025/2230.pdf)
### Abstract
Subgroup membership testing serves as a crucial countermeasure against small subgroup attacks, thereby ensuring the security of pairing-based cryptographic protocols. Despite its vital importance, the expensive computational requirements for membership testing on specific pairing-friendly curves pose a non-negligible challenge.
In this paper, we revisit the $\mathbb{G}_2$ membership testing algorithms on KSS16 curves and propose a novel approach specifically designed for the families constructed by the KSS method (Kachisa-Schaefer-Scott method).
Moreover, we generalize several previous methods for $\mathbb{G}_2$ membership testing, rendering them applicable to more generic pairing-friendly curves.
Specifically, we implement an efficient $\mathbb{G}_2$ membership testing on three well-known curves KSS16-329, KSS16-330, and KSS16-766 for verification. The experimental results illustrate that our new method achieves improvements of $24.0\%$, $33.3\%$, and $29.2\%$ in terms of clock cycles compared to the state-of-the-art, respectively.
## 2025/2231
* Title: NeevAs: An AEAD Design for Lightweight Cryptography
* Authors: Varsha Jarali, Hari Preeth S, Khushboo Bussi, Shashi Kant Pandey
* [Permalink](https://eprint.iacr.org/2025/2231)
* [Download](https://eprint.iacr.org/2025/2231.pdf)
### Abstract
Authenticity and confidentiality are crucial for maintaining a secure information infrastructure. Confidentiality prevents unauthorized disclosure, while authenticity ensures origin of the data.. Authenticated encryption ensures both simultaneously by protecting data from access and verifying integrity. This paper presents a NeevAs cipher suite offering authenticated encryption with associated data (AEAD) and hashing, based on a sponge-based duplex construction. The scheme included concurrent absorption, a novel sponge method, where associated data is absorbed into the capacity part and plaintext into the rate part simultaneously. This reduces permutation calls typically required for associated data processing compared to existing sponge based designs. In the NeevAs cipher suite, the modified Neeva hash function generates the security tag, and the Ascon S-box provides efficiency and resistance against differential and boomerang attacks. The design targets lightweight cryptography, minimizing permutation calls to enhance efficiency and reduce resource consumption, making it well-suited for resource-constrained devices.
## 2025/2232
* Title: Toward Practical Lattice-based Unbounded Inner Product Functional Encryption: Construction and Implementation
* Authors: Suprava Roy, Ratna Dutta
* [Permalink](https://eprint.iacr.org/2025/2232)
* [Download](https://eprint.iacr.org/2025/2232.pdf)
### Abstract
Cloud computing enables data processing, storing and sharing in untrusted environments whose growing adoption necessitates a focus on data security and privacy. Inner product functional encryption (IPFE) is a promising cryptographic technique that enables fine-grained access control over sensitive data in untrusted cloud environments. Post-quantum cryptography focuses on developing cryptographic protocols resilient to quantum computer attacks, with lattice structures being crucial in designing these protocols.
This paper aims to implement the lattice-based public key unbounded IPFE (uIPFE) scheme proposed by Dutta et al. (2022) [1] which ensures that no specific vectorrCOs length bound needs to be fixed during public parameter generation.
Furthermore, we extend the ALS-IPFE scheme of Agrawal et al. (2016) [2] to create a new public key scheme uIPFE #1, achieving adaptive indistinguishability security in the random oracle model under the Learning with Errors assumption, while avoiding trapdoor generation and pre-image sampling algorithms.
This work aims to enhance the practical applicability of uIPFE in cloud computing environments. We implement both the schemes uIPFE and uIPFE #1 in C programming language and execute the code on IBM Power 9 server. Moreover, we analyze the running time and discuss the performance of both schemes based on varying message vector lengths.
## 2025/2233
* Title: Quantum Authentication: Security against Authentication and Verification Queries
* Authors: Shaoquan Jiang
* [Permalink](https://eprint.iacr.org/2025/2233)
* [Download](https://eprint.iacr.org/2025/2233.pdf)
### Abstract
Quantum authentication is a procedure that sends a quantum message to a receiver without being imperceptibly changed in the channel. How to formalize a proper authentication model is a highly non-trivial task. Existing models have various flaws: they either do not capture serious concerns or are over restricted. Most importantly, none of them have addressed the threat from the verification queries. We show that there is a quantum authentication scheme that is secure when no verification query is allowed while it is completely insecure when verification queries are additionally permitted. The threat of verification queries is not artificial. Our attack only needs to know if a forged authentication message is valid or not. It captures the concern that the adversary can watch if the receiver accepts an authentication or not, without even reading the message authenticated. We propose a quantum authentication model that captures the authentication of multiple messages under the same key as well as the verification queries. We allow the attacker to have his own state entangled with the authentication message. Finally, we propose an authentication framework abstracted from the AQA method in Garg et al. (CRYPTO'17) and prove the security in our model. Our result reduces the security of an authentication protocol to certain properties of its component primitives. We also prove that an impersonation attack implies a substitution attack. To our knowledge, this is the first time to confirm this result.
## 2025/2234
* Title: ZeroOS: A Universal Modular Library OS for zkVMs
* Authors: Guangxian Zou, Isaac Zhang, Ryan Zarick, Kelvin Wong, Thomas Kim, Daniel L.-K. Wong, Saeid Yazdinejad, Dan Boneh
* [Permalink](https://eprint.iacr.org/2025/2234)
* [Download](https://eprint.iacr.org/2025/2234.pdf)
### Abstract
zkVMs promise general-purpose verifiable computation through ISA-level compatibility with modern programs and toolchains. However, compatibility extends further than just the ISA; modern programs often cannot run or even compile without an operating system and libc. zkVMs attempt to address this by maintaining forks of language-specific runtimes and statically linking them into applications to create self-contained unikernels, but this ad-hoc approach leads to version hell and burdens verifiable applications (vApps) with an unnecessarily large trusted computing base. We solve this problem with ZeroOS, a modular library operating system (libOS) for vApp unikernels; vApp developers can use off-the-shelf toolchains to compile and link only the exact subset of the Linux ABI their vApp needs. Any zkVM team can easily leverage the ZeroOS ecosystem by writing a ZeroOS bootloader for their platform, resulting in a reduced maintainence burden and unifying the entire zkVM ecosystem with consolidated development and audit resources. ZeroOS is free and open-sourced at https://github.com/LayerZero-Labs/ZeroOS
## 2025/2235
* Title: MLWErCOs impact on Web Metrics, mTLS TTLB, and AWS service endpoint connections
* Authors: Mila Anastasova, Panos Kampanakis
* [Permalink](https://eprint.iacr.org/2025/2235)
* [Download](https://eprint.iacr.org/2025/2235.pdf)
### Abstract
Migrating to quantum-resistant cryptographic algorithms, specifically the NIST-standardized Module Learning with Errors (MLWE) primitives, would inevitably result in data transmission overhead in secure transport protocols due to their larger key, ciphertext, and signature sizes. Would the connection setup cost noticeably affect application performance? This study evaluates MLWE's performance impact on practical use cases that rely on TLS 1.3 via real-world experiments. We analyze three distinct scenarios by sharing empirical and experimental data of applications interfacing with cloud service TLS endpoints, Web user metrics, and mutual TLS connections. We argue that some cloud applications will not be significantly affected due to their unconstrained environment. We show that Web performance degradation will remain below 10% for common webpages, corresponding to time delays of under 100ms, which users are unlikely to perceive. For mutual TLS applications, our experiments show that MLWE noticeably affects Time-to-First-Byte, almost doubling the connection times compared to plain TLS. However, when evaluating Time-to-Last-Byte, a metric more closely tied to application performance, the overall impact drops to about 15% for ~150KB data transfers in fast or slow networks. This impact is much lower for large client-server round trips. While these results are reassuring that MLWE could unnoticeably be introduced in common TLS use cases, they do not diminish the value of data trimming techniques proposed in the literature (e.g., session resumption, intermediate certificate authority suppression) to speed up connections.
## 2025/2236
* Title: Extending the SPHINCS+ Framework: Varying the Tree Heights and Chain Lengths
* Authors: Zhen Qin, Siwei Sun
* [Permalink](https://eprint.iacr.org/2025/2236)
* [Download](https://eprint.iacr.org/2025/2236.pdf)
### Abstract
The SPHINCS+ framework provides the underlying architecture for modern quantum resistant stateless hash-based signatures. Notable examples include the NIST standard SLH-DSA and its recent variants such as SPHINCS-$\alpha$ and SPHINCS+C. We extend the hypertree structure that underlies the SPHINCS+ framework by allowing trees of different heights to appear on different layers, and we plug generalized hash-based one-time signatures with chains of different lengths into the hypertree. While these structural generalizations do not affect the original security proof for the SPHINCS+ framework as long as the encoding function employed by the underlying one-time signature is injective and incomparable, they lead to enlarged design space, opening up the possibility for finer-grained trade-offs. We perform a systematic exploration of the parameter space for the generalized structure guided by a thorough theoretical cost analysis that minimizes the number of variables to be enumerated in the searching process. As a result, we identify many parameter sets superior to state-of-the-art stateless hash-based signature schemes in terms of signature size, signing or verification efficiency. In particular, we provide some parameter settings not only enjoying smaller signature size, but also more efficient in signing and verification. The improvement can be significant if we do not pursue optimizing all performance metrics simultaneously. One of our constructions with 128-bit security is 8.1% smaller than SPHINCS+C-128s (26.2% smaller than SPHINCS+-128s and 16.7% smaller than SPHINCS-$\alpha$-128s). At the same time, it is faster in verification but slower in signing than SPHINCS+C-128s. Further size reduction is possible with a greater sacrifice in speed. We provide implementations and benchmark results for representative parameter sets.
## 2025/2237
* Title: Distributed Broadcast Encryption for Confidential Interoperability across Private Blockchains
* Authors: Angelo De Caro, Kaoutar Elkhiyaoui, Sandeep Nishad, Sikhar Patranabis, Venkatraman Ramakrishna
* [Permalink](https://eprint.iacr.org/2025/2237)
* [Download](https://eprint.iacr.org/2025/2237.pdf)
### Abstract
Interoperation across distributed ledger technology (DLT) networks hinges upon the secure transmission of ledger state from one network to another. This is especially challenging for private networks whose ledger access is limited to enrolled members. Existing approaches rely on a trusted centralized proxy that receives encrypted ledger state of a network, decrypts it, and sends it to members of another network. Though effective, this approach goes against the founding principle of DLT, namely avoiding single points of failure (or single sources of trust).
In this paper, we leverage fully-distributed broadcast encryption (FDBE in short) to build a fully decentralized protocol for confidential information-sharing across private networks. Compared to traditional broadcast encryption (BE), FDBE is characterized by distributed setup and key generation, where mutually distrusting parties agree on a BErCOs public key without a trusted setup, and securely derive their decryption keys. Given any FDBE, two private networks can securely share information as follows: a sender in one network uses the other networkrCOs FDBE public key to encrypt a message for its members; and the resulting construction is secure in the simplified universal composability framework.
To further demonstrate the practicality of our approach, we present the first instantiation of an FDBE that enjoys constant-sized decryption keys and ciphertexts, and evaluate the resulting performances through a reference implementation that considers two private Hyperledger Fabric networks within the Hyperledger Cacti interoperation framework.
--- Synchronet 3.21a-Linux NewsLink 1.2