From Newsgroup: sci.crypt

## In this issue
1. [2023/712] Optimizing Attribute-based Encryption for Circuits ...
2. [2025/368] Polynomial Secret Sharing Schemes and Algebraic ...
3. [2025/382] On the Security and Privacy of CKKS-based ...
4. [2025/877] Towards Improving Throughput and Scalability of ...
5. [2025/975] Incompressible Encryption with Everlasting Security
6. [2025/992] Improved Private Simultaneous Messages Protocols ...
7. [2025/1606] Collatz Hash: Cryptographic Hash Algorithm Using ...
8. [2025/1660] Dory: Streaming PCG with Small Memory
9. [2025/1721] Q-Stream: A Practical System for Operational ...
10. [2025/1722] From OT to OLE with Subquadratic Communication
11. [2025/1723] Space-Deniable Proofs
12. [2025/1724] Efficient Aggregate Anonymous Credentials for ...
13. [2025/1725] Blockchain-based Economic Voting with Posterior ...
14. [2025/1726] How (not) to Build Identity-Based Encryption from ...
15. [2025/1727] Rhizomes and the Roots of EfficiencyrCoImproving Prio
16. [2025/1728] Precision Strike: Targeted Misclassification of ...
17. [2025/1729] GuardianMPC: Backdoor-resilient Neural Network ...
18. [2025/1730] On the Impossibility of Actively Secure Distributed ...
19. [2025/1731] ECCFROG522PP: An Enhanced 522-bit Weierstrass ...
20. [2025/1732] Zero-Knowledge AI Inference with High Precision
21. [2025/1733] Differentially Private Compression and the ...
22. [2025/1734] Compressed Permutation Oracles
23. [2025/1735] Edge Encryption using Iterative Management Framework
24. [2025/1736] Breaking the Barrier for Asynchronous MPC with a Friend
25. [2025/1737] WaterSQI and PRISMO: Quaternion Signatures for ...
26. [2025/1738] Optimal Byzantine Agreement in the Presence of ...
27. [2025/1739] Attacking an RSA-like Cryptosystem Using Continued ...
28. [2025/1740] Improved Radix-based Approximate Homomorphic ...
29. [2025/1741] Full L1 On-Chain ZK-STARK+PQC Verification on ...
30. [2025/1742] Broadcast Encryption with Size N^1/3 and More from ...
31. [2025/1743] NISQ Security and Complexity via Simple Classical ...
32. [2025/1744] Randomness beacons from financial data in the ...
33. [2025/1745] Fault Attacks on MPCitH Signature Schemes
34. [2025/1746] Cross-chain Lightning Trades: Getting the ...
35. [2025/1747] Masked Circuit Compiler in the Cardinal Random ...
36. [2025/1748] Post-Quantum TLS 1.3 Handshake from CPA-Secure KEMs ...
37. [2025/1749] Sandwich BUFF: Achieving Non-Resignability Using ...
38. [2025/1750] Modeling Emails: On the Deniability of BCCs
39. [2025/1751] On the Existence and Construction of Very Strong ...
40. [2025/1752] Foundations of Dynamic Group Signatures: The Case ...
41. [2025/1753] Bootstrapping over Free $\mathcal{R}$-Module
42. [2025/1754] Machine Learning and Side-Channel Attacks on Post- ...
43. [2025/1755] DAKE: Bandwidth-Efficient (U)AKE from Double-KEM
44. [2025/1756] Are Neural Networks Collision Resistant?
45. [2025/1757] New key establishment protocol based on random 1 ...
46. [2025/1758] Revisiting PQ WireGuard: A Comprehensive Security ...
47. [2025/1759] Plonk is Simulation Extractable in ROM Under ...
48. [2025/1760] Vive Galois! Part 1: Optimal SIMD Packing and ...
49. [2025/1761] Automated Proof for Quadratic Functional ...
50. [2025/1762] Threshold Signatures from One-Way Functions
51. [2025/1763] A High Throughput Kyber NTT
## 2023/712
* Title: Optimizing Attribute-based Encryption for Circuits using Compartmented Access Structures
* Authors: Alexandru Ionita
* [Permalink](https://eprint.iacr.org/2023/712)
* [Download](https://eprint.iacr.org/2023/712.pdf)
### Abstract
Attribute-based encryption (ABE) is an asymmetric encryption method that allows expressive access granting mechanisms, with high applicability in modern IT infrastructure, such as Cloud or IoT systems. (Ezhilarasi et al., 2021; Touati and Challal, 2016) One open problem regarding ABE is using Boolean circuits as access structures. While Boolean Formulae were supported since the first ABE scheme proposed, there is still no efficient construction that supports Boolean circuits. We propose a new ABE scheme for a new access structure type, situated between Boolean formulae and Boolean circuits in terms of expressiveness. This key point in our construction is the usage of CAS-nodes, a structure modeling compartmented groups access structures. We also show that our CAS-nodes can be used to improve the efficiency of existing ABE schemes for Boolean circuits. Our construction is secure in the Selective Set Model under the bilinear Decisional Diffie-Hellman Assumption.
## 2025/368
* Title: Polynomial Secret Sharing Schemes and Algebraic Matroids
* Authors: Amos Beimel, Oriol Farr|as, Adriana Moya
* [Permalink](https://eprint.iacr.org/2025/368)
* [Download](https://eprint.iacr.org/2025/368.pdf)
### Abstract
Polynomial secret sharing schemes generalize the linear ones by adding more expressivity and giving room for efficiency improvements. In these schemes, the secret is an element of a finite field, and the shares are obtained by evaluating polynomials on the secret and some random field elements, i.e., for every party there is a set of polynomials that computes the share of the party. Notably, for general access structures, the best known polynomial schemes have better share size than the best known linear ones. This work investigates the properties of the polynomials and the fields that allow these efficiency gains and aims to characterize the access structures that benefit from them.
We focus first on ideal schemes, which are optimal in the sense that the size of each share is the size of the secret. We prove that, under some restrictions, if the degrees of the sharing polynomials are not too big compared to the size of the field, then its access structure is a port of an algebraic matroid. This result establishes a new connection between ideal schemes and matroids, extending the known connection between ideal linear schemes and linearly representable matroids.
For general polynomial schemes, we extend these results and analyze their privacy and correctness. Additionally, we show that given a set of polynomials over a field of large characteristic, one can construct linear schemes that realize the access structure determined by these polynomials; as a consequence, polynomial secret sharing schemes over these fields are not stronger than linear schemes.
While there exist ports of algebraic matroids that do not admit ideal schemes, we demonstrate that they always admit schemes with statistical security and information ratio tending to one. This is achieved by considering schemes where the sharings are points in algebraic varieties.
## 2025/382
* Title: On the Security and Privacy of CKKS-based Homomorphic Evaluation Protocols
* Authors: Intak Hwang, Seonhong Min, Jinyeong Seo, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2025/382)
* [Download](https://eprint.iacr.org/2025/382.pdf)
### Abstract
CKKS is a homomorphic encryption (HE) scheme that supports approximate arithmetic over complex numbers. While it is widely used in privacy-preserving machine learning (PPML) protocols, the approximate nature of the scheme makes it challenging to formally define the security guarantees of those protocols. In particular, in a sender-receiver protocol, where the sender performs homomorphic evaluation using a private circuit, characterizing the sender's privacy remains an important open problem. Moreover, there are currently no known methods for handling malicious receivers due to the absence of a zero-knowledge argument of knowledge (ZKAoK) for the CKKS scheme.
In this paper, we address these open challenges. First, we introduce a new security definition, called differentially private homomorphic evaluation (DPHE), to formalize sender privacy in CKKS-based protocols. Next, we present a general compilation method that transforms a plain CKKS protocol into a DPHE protocol. Finally, we construct a zero-knowledge argument of knowledge (ZKAoK) for CKKS to achieve the DPHE property in the presence of malicious receivers, and provide concrete benchmarks of our ZKAoK implementation.
To the best of our knowledge, this is the first work to formally address security and privacy issues in CKKS-based protocols through the lens of differential privacy. We also remark that our ZKAoK is the first construction to ensure the well-formedness of CKKS public keys and ciphertexts.
## 2025/877
* Title: Towards Improving Throughput and Scalability of DAG-based BFT SMR
* Authors: Nibesh Shrestha, Aniket Kate
* [Permalink](https://eprint.iacr.org/2025/877)
* [Download](https://eprint.iacr.org/2025/877.pdf)
### Abstract
Directed Acyclic Graph (DAG)-based BFT consensus protocols often suffer from limited throughput and scalability due to bandwidth-intensive data replication to all participants. However, it is sufficient to replicate data to a smaller sub-committee of parties that holds an honest majority with high probability.
In this work, we introduce tribe-assisted reliable broadcast, a novel primitive that ensures reliable broadcast (RBC) properties within a smaller honest-majority sub-committeerCoreferred to as a clanrCodrawn from the entire network, called the tribe. Leveraging this primitive, we develop two efficient DAG-based BFT consensus protocols. First, we present a single-clan protocol, in which a single clan is elected from the tribe, and data is disseminated exclusively to this designated clan using tribe-assisted RBC. We then extend this design to a multi-clan setting, where multiple clans are elected and data is distributed within each respective clan via the same mechanism. Experimental results demonstrate that both protocols offer substantial improvements in throughput and latency over existing DAG-based BFT protocols, even at moderately large scales.
## 2025/975
* Title: Incompressible Encryption with Everlasting Security
* Authors: Eylon Yogev, Shany Ben-David
* [Permalink](https://eprint.iacr.org/2025/975)
* [Download](https://eprint.iacr.org/2025/975.pdf)
### Abstract
Recently, the concept of incompressible encryption has emerged as a powerful enhancement to key-leakage resilience. In an incompressible encryption scheme, an adversary who intercepts ciphertexts is forced to dedicate a significant amount of memory to store them in full if they wish to extract any information about the plaintext later when the secret key becomes available. Given two messages, the security game involves two adversaries: the first adversary receives an encryption of one of the messages and produces a compressed state. Then, the second adversary, given both the secret key and the compressed state, attempts to determine which message was encrypted.
Several positive results exist in incompressible cryptography. On the one hand, there are constructions based on minimal assumptions but with a poor rate (i.e., rate tends to 0). On the other hand, there are rate-1 constructions that achieve optimal efficiency but rely on strong cryptographic assumptions, such as obfuscation.
A stronger security notion, known as everlasting security, has been proposed for incompressible encryption. In this formulation, the second adversary, who receives the compressed state and the secret key, is allowed to be computationally unbounded. While this notion is conceptually appealing, no constructions of everlasting incompressible encryption are currently known, regardless of the underlying assumption or even in idealized models.
In this work, we give the first construction of everlasting incompressible encryption. In fact, we show that everlasting incompressible encryption is inherent in any sufficiently secure public-key encryption scheme. Specifically, we prove that any public-key encryption scheme with subexponential security (when instantiated with an appropriate security parameter) already satisfies the definition of everlasting incompressible encryption with subexponential security. Furthermore, our scheme achieves rate-1, improving upon existing results even for the weaker notion of standard incompressible encryption.
Our results raise concerns about whether the current definition of incompressible encryption adequately captures the expected efficiency properties of such schemes, indicating that refinements may be needed. As one concrete step in this direction, we propose a storage-rate definition for ciphertexts, and show how to construct schemes with constant storage-rate.
## 2025/992
* Title: Improved Private Simultaneous Messages Protocols for Symmetric Functions with Universal Reconstruction
* Authors: Koji Nuida
* [Permalink](https://eprint.iacr.org/2025/992)
* [Download](https://eprint.iacr.org/2025/992.pdf)
### Abstract
Private Simultaneous Messages (PSM) is a kind of secure multiparty computation with minimal interaction pattern and minimal security requirement. A PSM protocol is said to be with universal reconstruction for a given function family if the algorithm of the referee (the output party) is independent of a function to be computed and the referee cannot infer the function from a protocol execution. In a recent work by Eriguchi and Shinagawa (EUROCRYPT 2025), the authors proposed a compiler to obtain a PSM protocol for symmetric functions from PSM protocols with universal reconstruction for symmetric functions with smaller domains. The authors also constructed the latter PSM protocols with universal reconstruction, by which the former PSM protocol achieves communication complexity better than the previously known protocols. In this paper, we construct the latter PSM protocols with universal reconstruction for symmetric functions more efficiently; the communication complexity is exponentially (in the input range) smaller than the protocols by Eriguchi and Shinagawa. As a consequence, we also obtain a PSM protocol (and also an ad-hoc PSM protocol and a robust PSM protocol) for symmetric functions that is more efficient than their protocol. Technically, a main ingredient of their protocols is a linear and injective encoding of histograms for the input elements, and our improvement is realized by finding a more efficient encoding of the histograms.
## 2025/1606
* Title: Collatz Hash: Cryptographic Hash Algorithm Using 3x+1 Conjecture
* Authors: Shaurya Pratap Singh, Bhupendra Singh, Alok Mishra
* [Permalink](https://eprint.iacr.org/2025/1606)
* [Download](https://eprint.iacr.org/2025/1606.pdf)
### Abstract
In this paper, we introduce a new cryptographic hash algorithm in that we used the Collatz problem, focusing on its conditional branching structure, an element often overlooked despite the fame of the 3x + 1 conjecture. This hash algorithm takes an arbitrary-length input and produces a fixed length 512/384/256 bit output. The presented hash algorithm is in the category of Collision Resistance Hash Function (CRHF), and this hash algorithm is designed by focusing on its use in password storing, HMAC, digital signatures, etc.
Until now, quantum computers also didnrCOt show any speedup in the Collatz conjecture problem, so still the proving and disproving of the Collatz conjecture is a big question, so we believe that there is no structural attack on this hash algorithm.
## 2025/1660
* Title: Dory: Streaming PCG with Small Memory
* Authors: Xiaojie Guo, Hanlin Liu, Zhicong Huang, Hongrui Cui, Wenhao Zhang, Cheng Hong, Xiao Wang, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2025/1660)
* [Download](https://eprint.iacr.org/2025/1660.pdf)
### Abstract
Pseudorandom correlation generators (PCGs) have been popular in generating a huge amount of correlated randomness, a critical resource in secure computation. However, existing PCGs are memory-consuming and not friendly to resource-constrained devices. Even for moderate devices, the need for large memory can also be a disadvantage in applications like zero-knowledge proofs or large-scale secure computation. In this paper, we propose a malicious streaming PCG (sPCG), which generates a bounded number of tuples of subfield vector oblivious linear evaluation (sVOLE) on-the-fly, each with sublinear memory and computation.
1. We propose an efficient protocol that replaces the relaxed distributed comparison function in the best pseudorandom correlation function (PCF) for sVOLE (CRYPTO'22), which has the same streaming features for any polynomial number of tuples. With this protocol, our sPCG is doubly efficient in memory and the computation per sVOLE. Moreover, we augment the black-box distributed setup to malicious security and yield 4x communication improvement. Our sPCG can be extended to a more efficient sVOLE PCF with the same improvements in memory and computation, and a 2x faster malicious non-black-box distributed setup.
2. We present a practical attack on the Learning Parity with Noise (LPN) assumption for expand-accumulate codes with regular noise, revealing that some previous parameters provide around 14~22 bits of security over binary noises, far below the target 128 bits. To address this, we introduce a low-Hamming-weight noise distribution to withstand the attack. We then derive some updated LPN parameters with the new noise distribution, restoring 128-bit security and reducing the noise-related computation and communication.
3. We provide an implementation of our sPCG for the special case of correlated oblivious transfer (COT). In addition to the improvements over the best PCF, our sPCG can have a comparable end-to-end performance to Ferret (CCS'20) and the PCG from expand-convolute codes (CRYPTO'23), two state-of-the-art PCGs, with the advantage of being able to produce 10 million COTs on-the-fly and reducing the memory from 337 MB and 624 MB to 20 MB, respectively.
## 2025/1721
* Title: Q-Stream: A Practical System for Operational Perfect Secrecy
* Authors: Adrian Neal
* [Permalink](https://eprint.iacr.org/2025/1721)
* [Download](https://eprint.iacr.org/2025/1721.pdf)
### Abstract
Information-theoretic security (ITS) offers the strongest known form of cryptographic protection, guaranteeing confidentiality even against adversaries with unbounded computational power. However, ShannonrCOs perfect secrecy theorem requires keys as long as the message, which has made ITS widely regarded as impractical for real-world deployment.
This paper updates Q-Stream, introduced in prior work (rCLA Quantum-Safe Key-Distribution Mechanism having Non-Conjectured Hardness, while scalable for a Vernam Cipher, under Shannon Conditions,rCY Proceedings of the Future Technologies Conference (FTC 2025), Springer LNNS, Munich, 2025), the first practical system to achieve ITS under the framework of Operational Perfect Secrecy (OPS), having also been introduced in prior work. Q-Stream uses ephemeral public quantum-random blocks (Q-Blocks) combined with short secret defragmentation keys (DFKs) to produce one-time pads with provable OPS security levels. The system implements both Combinatorial ITS (C-ITS) and Dimensional Ambiguity ITS (DA-ITS) modes, providing tunable secrecy levels while drastically reducing the burden of key distribution.
We describe Q-StreamrCOs architecture, protocol design, security analysis, and implementation, and evaluate its performance against conventional and post-quantum cryptography. Our results show that Q-Stream delivers high-throughput, low-latency encryption while providing provable information-theoretic confidentiality, demonstrating that OPS-based security is practical at scale.
## 2025/1722
* Title: From OT to OLE with Subquadratic Communication
* Authors: Jack Doerner, Iftach Haitner, Yuval Ishai, Nikolaos Makriyannis
* [Permalink](https://eprint.iacr.org/2025/1722)
* [Download](https://eprint.iacr.org/2025/1722.pdf)
### Abstract
Oblivious Linear Evaluation (OLE) is an algebraic generalization of oblivious transfer (OT) that forms a critical part of a growing number of applications. An OLE protocol over a modulus $q$ enables the receiver party to securely evaluate a line $a\cdot X+b$ chosen by the sender party on a secret point $x\in\mathbb{Z}_q$.
Motivated by the big efficiency gap between OLE and OT and by fast OT extension techniques, we revisit the question of reducing OLE to OT, aiming to improve the communication cost of known reductions.
We start by observing that the Chinese Remainder Theorem (CRT) can be combined with a prior protocol of Gilboa (Crypto rCO99) to reduce its communication cost from $O(\ell^2)$ to $\tilde O(\ell)$ bits, for $\ell=\log q$. Unfortunately, whereas Gilboa's protocol is secure against a semi-honest sender and a malicious receiver, a direct application of the CRT technique is only semi-honest secure (it is insecure against malicious receivers). Thus, we employ number-theoretic techniques to protect our CRT-based protocol against malicious receivers, while still retaining a concrete advantage over Gilboa's protocol (e.g., $10.2\times$ less communication for $\ell=256$). Furthermore, we obtain a fully malicious OLE-to-OT reduction by applying either information-theoretic techniques with moderate overhead, or RSA-based cryptographic techniques with very low overhead.
We demonstrate the usefulness of our results in the context of OLE applications, including a post-quantum oblivious pseudorandom function (OPRF) and distributed signatures. In particular, assuming pre-existing random OT correlations, we can use our malicious-receiver OLE protocol to realize (a single instance of) the power-residue based OPRF candidate with security against a malicious client and a semi-honest server using only 1.14 KB of communication, a $16\times$ improvement over the best previous protocol in this setting. Using our RSA-based fully malicious OLE protocol, we achieve a $5\times$ communication improvement over previous OT and EC-based distributed ECDSA protocols. Compared to other ECDSA protocols (including ones that use Paillier and class groups), the communication gains are more modest, but come at only a fraction of the computational cost as we avoid all expensive group operations.
## 2025/1723
* Title: Space-Deniable Proofs
* Authors: Jesko Dujmovic, Christoph U. G|+nther, Krzysztof Pietrzak
* [Permalink](https://eprint.iacr.org/2025/1723)
* [Download](https://eprint.iacr.org/2025/1723.pdf)
### Abstract
We introduce and construct a new proof system called Non-interactive Arguments of Knowledge or Space (NArKoS), where a space bounded prover can convince a verifier they know a secret, while having access to sufficient space allows one to forge indistinguishable proofs without the secret.
An application of NArKoS are space-deniable proofs, which are proofs of knowledge (say for authentication in access control) that are sound when executed by a lightweight device like a smart-card or an RFID chip that cannot have much storage, but are deniable (in the strong sense of online deniability) as the verifier, like a card reader, can efficiently forge such proofs.
We construct NArKoS in the random oracle model using an OR-proof combining a sigma protocol (for the proof of knowledge of the secret) with a new proof system called simulatable Proof of Transient Space (simPoTS). We give two different constructions of simPoTS, one based on labelling graphs with high pebbling complexity, a technique used in the construction of memory-hard functions and proofs of space, and a more practical construction based on the verifiable space-hard functions from TCC'24 where a prover must compute a root of a sparse polynomial. In both cases, the main challenge is making the proofs efficiently simulatable.
## 2025/1724
* Title: Efficient Aggregate Anonymous Credentials for Decentralized Identity
* Authors: Rebekah Mercer, Kaoutar El Khiyaoui, Angelo De Caro, Elli Androulaki * [Permalink](https://eprint.iacr.org/2025/1724)
* [Download](https://eprint.iacr.org/2025/1724.pdf)
### Abstract
Anonymous credential schemes allow users to prove claims about themselves in a privacy-preserving manner. Put simply, a user can prove that she has an attribute value (e.g., she is a citizen) without revealing any other information about herself. Traditional schemes (including those with multiple credential issuers) operate under the assumption that each recognized issuer produces credentials for all user attributes. This assumption, however, is not practical: in the real world, no such issuer exists; an identity provider today issues a user credentials for a subset of user attributes, not all. A promising approach to support this setting is aggregate anonymous credentials, which allow a user to receive credentials from several issuers such that she can aggregate them and prove various claims about her attribute values in one shot. In this paper, we first introduce what we call aggregate tag-based signatures and describe an efficient instantiation. We then leverage the latter together with structure-preserving signatures and signatures of knowledge to construct an efficient aggregate anonymous credential scheme. We finally, formally evaluate the security of the proposed schemes and run benchmarks to showcase the practicality of the resulting scheme and its relevance for decentralized identity applications.
## 2025/1725
* Title: Blockchain-based Economic Voting with Posterior Security from Lattices * Authors: Navid Abapour, Amir Goharshady, Catalin Dragan, Mahdi Mahdavi
* [Permalink](https://eprint.iacr.org/2025/1725)
* [Download](https://eprint.iacr.org/2025/1725.pdf)
### Abstract
Electronic voting has demonstrated that it streamlines the democratic process, making it more convenient for citizens and enhancing the accuracy and speed of election results in real-world scenarios in the US, Estonia, Switzerland, and many other countries. One major challenge for e-voting, especially online voting, is ensuring that voting and tallying devices behave honestly, particularly in cases involving monetary transactions. These are addressed by economic voting, where everything is on-chain; in essence, voters utilize smart contracts to conduct all voting stages. There are very few results on economic voting, and none post-quantum secure. The challenge comes from having the entire voting system run by smart contracts. In this work, we propose the first post-quantum economic voting scheme, which combines hybrid on- and off-chain operations, called the Post-Quantum Blind Vote (PQBV). The core idea is to utilize smart contracts that enable blind signatures during the voting process. We enhance our contribution by introducing a post-quantum blind signature with Posterior Security, as proposed by Yuen et al. (CCS 2025), which retroactively enhances the privacy of already generated signatures. This has a significant impact on PQBV, as it is able to satisfy formal cryptographic privacy definitions, including ballot privacy. Our efficiency analysis reveals competitive performance compared to existing state-of-the-art post-quantum e-voting systems, such as Epoque (EuroS&P 2021), which is done without blockchain.
## 2025/1726
* Title: How (not) to Build Identity-Based Encryption from Isogenies
* Authors: Elif Ozbay Gurler, Patrick Struck
* [Permalink](https://eprint.iacr.org/2025/1726)
* [Download](https://eprint.iacr.org/2025/1726.pdf)
### Abstract
In this work we show obstacles when constructing identity-based encryption (IBE) from isogenies. We first give a modular description for IBEs, what we call a canonical IBE, that consists of two components: an identity key derivation scheme and a public-key encryption scheme. This allows us to investigate the identity key derivation scheme (where the obstacles are rooted in) in isolation. We present several approaches, showing that they can either not be realizedrCoextracting the secret keys would require to solve the underlying hardness assumptionrCoor result in IBE schemes that are insecurerCousers can use their secret keys to compute secret keys of other users. Finally, we identify properties for isogeny-based trapdoor functions that one would need in order to overcome the identified obstacles.
## 2025/1727
* Title: Rhizomes and the Roots of EfficiencyrCoImproving Prio
* Authors: Armando Faz-Hernandez
* [Permalink](https://eprint.iacr.org/2025/1727)
* [Download](https://eprint.iacr.org/2025/1727.pdf)
### Abstract
Prio, tailored under privacy-by-design principles, is a protocol for aggregating client-provided measurements between non-colluding entities. The validity of measurements is determined by using a fully linear probabilistically-checkable proof (FLPCP). The Prover distributes secret shares of the measurement and the proof to multiple Verifiers. These Verifiers can only use linear queries on the input statement for validation without accessing the actual measurement. Efficiency is key for the practical application of Prio. The FLPCP operates with polynomials represented in the Lagrange basis using roots of unity as the nodes. However, we observe opportunities to improve its performance by embracing the Lagrange basis more extensively. For instance, we show an inversion-free O(n) time-complexity algorithm for polynomial evaluation in the Lagrange basis (an alternative to the classic rational barycentric formula). By applying our methods to libprio-rs, a cutting-edge Rust implementation, the Sharding phase (proof generation) runs a 36% faster and the Prep-Init phase (proof verification) is twice as fast, showing a substantial acceleration of the most time-consuming phases of Prio.
## 2025/1728
* Title: Precision Strike: Targeted Misclassification of Accelerated CNNs with a Single Clock Glitch
* Authors: Arsalan Ali Malik, Furkan Aydin, Aydin Aysu
* [Permalink](https://eprint.iacr.org/2025/1728)
* [Download](https://eprint.iacr.org/2025/1728.pdf)
### Abstract
Fault injection attacks (FIAs) present a significant threat to the integrity of deep neural networks (DNNs), particularly in hardware-accelerated deployments on field-programmable gate arrays (FPGAs). These attacks intentionally introduce faults into the system, leading the DNN to generate incorrect outputs. This work presents the first successful targeted misclassification attack against a convolutional neural network (CNN) implemented on FPGA hardware, achieved by injecting a single clock glitch at the final layer (argmax) to manipulate the predicted output class. Our attack targets the commonly adopted argmax layer, a lightweight replacement for softmax in resource-constrained implementations. By precisely injecting a single clock glitch during the comparison phase of the argmax operation, the attack reliably induces misclassifications, forcing the model to 'skip' a specifically chosen class and output an incorrect label for it without affecting the computed scores of other classes.
Unlike prior works that only cause random misclassifications, our attack achieves a high success rate of 80rCo87% for a targeted class, without inducing collateral misclassifications of other classes. Our evaluations show a significant reduction in classification accuracy, with the modelrCOs performance dropping from an initial 94.7% to an average final accuracy ranging from 7.7rCo14.7%. Our attack is demonstrated on a CNN model implemented using a common systolic array architecture, which is well-suited for resource-constrained edge devices and artificial intelligence (AI) accelerators. Our study confirms the vulnerability of hardware-accelerated machine learning systems to low-cost physical attacks, emphasizing the critical need for hardware-level countermeasures in safety-critical machine learning applications.
## 2025/1729
* Title: GuardianMPC: Backdoor-resilient Neural Network Computation
* Authors: Mohammad Hashemi, Domenic Forte, Fatemeh Ganji
* [Permalink](https://eprint.iacr.org/2025/1729)
* [Download](https://eprint.iacr.org/2025/1729.pdf)
### Abstract
The rapid growth of deep learning (DL) has raised
serious concerns about usersrCO data and neural network (NN)
modelsrCO security and privacy, particularly the risk of backdoor
insertion when outsourcing the training or employing pre-trained
models. To ensure resilience against such backdoor attacks, this
work presents GuardianMPC, a novel framework leveraging
secure multiparty computation (MPC). GuardianMPC is built
upon garbled circuits (GC) within the LEGO protocol framework
to accelerate oblivious inference on FPGAs in the presence of
malicious adversaries that can manipulate the model weights
and/or insert a backdoor in the architecture of a pre-trained
model. In this regard, GuardianMPC is the first to offer private
function evaluation in the LEGO family. GuardianMPC
also supports private training to effectively counter backdoor
attacks targeting NN model architectures and parameters. With
optimized pre-processing, GuardianMPC significantly accelerates
the online phase, achieving up to x13.44 faster computation than
its software counterparts. Our experimental results for multilayer
perceptrons (MLPs) and convolutional neural networks (CNNs)
assess GuardianMPCrCOs time complexity and scalability across
diverse NN model architectures. Interestingly, GuardianMPC
does not adversely affect the training accuracy, as opposed to
many existing private training frameworks. These results confirm
GuardianMPC as a high-performance, model-agnostic solution
for secure NN computation with robust security and privacy
guarantees.
## 2025/1730
* Title: On the Impossibility of Actively Secure Distributed Samplers
* Authors: Damiano Abram, Serge Fehr, Maciej Obremski, Peter Scholl
* [Permalink](https://eprint.iacr.org/2025/1730)
* [Download](https://eprint.iacr.org/2025/1730.pdf)
### Abstract
One-round secure computation is generally believed impossible due to the residual function attack: any honest-but-curious participant can replay the protocol in their head changing their input, and learn, in this way, a new output. Inputless functionalities are among the few that are immune to this problem.
This paper studies one-round, multi-party computation protocols (MPC) that implement the most natural inputless functionality: one that generates a random sample from a fixed distribution. These are called distributed samplers. At Eurocrypt 2022, Abram, Scholl and Yakoubov showed how to build this primitive in the semi-honest model with dishonest majority. In this work, we give a lower bound for constructing distributed samplers with a malicious adversary in the standard model. More in detail, we show that for any construction in the stand-alone model with black-box simulation, even with a CRS and honest majority, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Our proof is based on an entropic argument, drawing a new connection between computationally secure MPC, information theory and learning theory.
## 2025/1731
* Title: ECCFROG522PP: An Enhanced 522-bit Weierstrass Elliptic Curve
* Authors: V-#ctor Duarte Melo, William J Buchanan
* [Permalink](https://eprint.iacr.org/2025/1731)
* [Download](https://eprint.iacr.org/2025/1731.pdf)
### Abstract
Whilst many key exchange and digital signature systems still rely on NIST P-256 (secp256r1) and secp256k1, offering around 128-bit security, there is an increasing demand for transparent and reproducible curves at the 256-bit security level. Standard higher-security options include NIST P-521, Curve448, and Brainpool-P512. This paper presents ECCFROG522PP ('Presunto Powered'), a 522-bit prime-field elliptic curve that delivers security in the same classical $\sim$260-bit ballpark as NIST P-521, but with a fundamentally different design philosophy. All of the curve parameters are deterministically derived from a fixed public seed via BLAKE3, with zero hidden choices. The curve has prime order (cofactor = 1), a verified twist with a proven approximate 505-bit prime factor, safe embedding degree, and passes anti-MOV checks up to k <200 and CM discriminant sanity up to 100k. Unlike prior opaque or ad-hoc constructions, ECCFROG522PP is fully reproducible: anyone can regenerate and verify it byte-for-byte using the published scripts. The intent is not to outperform NIST P-521 in raw speed, but to maximise trust, verifiability, and long-term auditability in a practical curve of equivalent security level.
## 2025/1732
* Title: Zero-Knowledge AI Inference with High Precision
* Authors: Arman Riasi, Haodi Wang, Rouzbeh Behnia, Viet Vo, Thang Hoang
* [Permalink](https://eprint.iacr.org/2025/1732)
* [Download](https://eprint.iacr.org/2025/1732.pdf)
### Abstract
Artificial Intelligence as a Service (AIaaS) enables users to query a model hosted by a service provider and receive inference results from a pre-trained model. Although AIaaS makes artificial intelligence more accessible, particularly for resource-limited users, it also raises verifiability and privacy concerns for the client and server, respectively. While zero-knowledge proof techniques can address these concerns simultaneously, they incur high proving costs due to the non-linear operations involved in AI inference and suffer from precision loss because they rely on fixed-point representations to model real numbers.
In this work, we present ZIP, an efficient and precise commit and prove zero-knowledge SNARK for AIaaS inference (both linear and non-linear layers) that natively supports IEEE-754 double-precision floating-point semantics while addressing reliability and privacy challenges inherent in AIaaS. At its core, ZIP introduces a novel relative-error-driven technique that efficiently proves the correctness of complex non-linear layers in AI inference computations without any loss of precision, and hardens existing lookup-table and range proofs with novel arithmetic constraints to defend against malicious provers. We implement ZIP and evaluate it on standard datasets (e.g., MNIST, UTKFace, and SST-2). Our experimental results show, for non-linear activation functions, ZIP reduces circuit size by up to three orders of magnitude while maintaining the full precision required by modern AI workloads.
## 2025/1733
* Title: Differentially Private Compression and the Sensitivity of LZ77
* Authors: Jeremiah Blocki, Seunghoon Lee, Brayan Sebastian Yepes-Garcia
* [Permalink](https://eprint.iacr.org/2025/1733)
* [Download](https://eprint.iacr.org/2025/1733.pdf)
### Abstract
We initiate the study of differentially private data-compression schemes motivated by the insecurity of the popular "Compress-Then-Encrypt" framework. Data compression is a useful tool which exploits redundancy in data to reduce storage/bandwidth when files are stored or transmitted. However, if the contents of a file are confidential then the length of a compressed file might leak confidential information about the content of the file itself. Encrypting a compressed file does not eliminate this leakage as data encryption schemes are only designed to hide the content of confidential message instead of the length of the message. In our proposed Differentially Private Compress-Then-Encrypt framework, we add a random positive amount of padding to the compressed file to ensure that any leakage satisfies the rigorous privacy guarantee of $(\epsilon,\delta)$-differential privacy. The amount of padding that needs to be added depends on the sensitivity of the compression scheme to small changes in the input, i.e., to what degree can changing a single character of the input message impact the length of the compressed file. While some popular compression schemes are highly sensitive to small changes in the input, we argue that effective data compression schemes do not necessarily have high sensitivity. Our primary technical contribution is analyzing the fine-grained sensitivity of the LZ77 compression scheme (IEEE Trans. Inf. Theory 1977) which is one of the most common compression schemes used in practice. We show that the global sensitivity of the LZ77 compression scheme has the upper bound $\mathcal{O}(W^{2/3}\log n)$ where $W\leq n$ denotes the size of the sliding window. When $W=n$, we show the lower bound $\Omega(n^{2/3}\log^{1/3}n)$ for the global sensitivity of the LZ77 compression scheme which is tight up to a sublogarithmic factor.
## 2025/1734
* Title: Compressed Permutation Oracles
* Authors: Joseph Carolan
* [Permalink](https://eprint.iacr.org/2025/1734)
* [Download](https://eprint.iacr.org/2025/1734.pdf)
### Abstract
The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle.
We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.
## 2025/1735
* Title: Edge Encryption using Iterative Management Framework
* Authors: Manoja Shridhar, Bala Puruvana, Alex Cravill, Joey Wolff
* [Permalink](https://eprint.iacr.org/2025/1735)
* [Download](https://eprint.iacr.org/2025/1735.pdf)
### Abstract
Securing data in heterogeneous, latency-sensitive edge environments demands encryption that adapts to device churn, intermittent connectivity, and evolving threat models without sacrificing real-time performance. We present an Iterative Management Framework (IMF) for edge encryption that closes the loop between policy intent, cryptographic configuration, runtime telemetry, and automated remediation. IMF organizes encryption management as a continuous control cyclerComodel, deploy, observe, and refinerCospanning device, edge-cluster, and cloud control planes. Concretely, IMF (i) encodes encryption policies as declarative, verifiable profiles; (ii) performs constraint-aware rollout and staged key rotation using topology- and load-aware schedulers; (iii) leverages streaming telemetry (cryptographic error rates, handshake retries, path RTT, and drift in device trust scores) to trigger bounded updates; and (iv) resolves conflicts via policy iteration with formal safety checks to prevent downgrade, orphaned keys, or split-brain trust roots. The framework supports heterogeneous primitivesrCoincluding AEAD ciphers, forward-secure rekeying, TEE/HSM-anchored key custody, and post-quantum negotiationrCowhile tolerating partial connectivity through opportunistic convergence and cryptographic state caching at the edge. In a prototype across 1,200 edge nodes, IMF sustained line-rate encryption with ren1.8% median throughput overhead and <35 ms p95 added latency during rolling rekeys, reduced key-exposure windows by 57% via adaptive rotation, and cut control traffic by 41% using differential rollout plans. These results indicate that iterative, telemetry-driven management can deliver robust encryption at the edge while preserving tight performance envelopes.
## 2025/1736
* Title: Breaking the Barrier for Asynchronous MPC with a Friend
* Authors: Banashri Karmakar, Aniket Kate, Shravani Patil, Arpita Patra, Sikhar Patranabis, Protik Paul, Divya Ravi
* [Permalink](https://eprint.iacr.org/2025/1736)
* [Download](https://eprint.iacr.org/2025/1736.pdf)
### Abstract
Multiparty computation (MPC) is a topic of growing interest for privacy-preserving computation tasks. A few MPC libraries have been developed, and newer protocols are regularly proposed to reduce the latency overhead, improve scalability, and achieve strong termination guarantees. However, most current MPC protocols are designed and implemented assuming network synchrony: in theory, they assume that all messages are delivered within a known time bound, while for experimental analysis, most assume all nodes to be honest, such that the time bounds are never deployed. While deploying MPC systems in the wild and trying to minimize the latency, network synchrony is indeed a strong assumption to make: natural adverse network conditions can break the safety and/or liveness of the protocol due to simply delayed messages.
Asynchronous MPC (AMPC) protocols can overcome the challenge as they
do not assume fixed time bounds for message delivery delays; however, AMPC faces a natural threshold barrier of 2/3rd honest majority and introduces significant computation and/or communication overheads. This work aims to achieve the best-of-both network models by designing a practical AMPC protocol that has stronger resilience guarantees matching those for synchronous MPC.
We achieve this by adopting the emerging helper-aided model, and designing protocols that achieve fairness not only in the simple honest majority setting but also in the dishonest majority setting. Our protocols follow the standard preprocessing-online paradigm, enabling a lightweight and fast input-dependent online phase. In the honest majority setting, our protocol relies solely on lightweight cryptographic operations. In the dishonest majority setting, the protocol requires oblivious transfer (OT) during preprocessing, which we prove is necessary in this setting. We implement our constructions and provide a thorough performance comparison with state-of-the-art MPC protocols in the helper-aided model. Our experiments demonstrate that our protocols substantially outperform the state-of-the-art helper-aided MPC scheme, while being significantly more resilient to network delays.
## 2025/1737
* Title: WaterSQI and PRISMO: Quaternion Signatures for Supersingular Isogeny Group Actions
* Authors: Tako Boris Fouotsa
* [Permalink](https://eprint.iacr.org/2025/1737)
* [Download](https://eprint.iacr.org/2025/1737.pdf)
### Abstract
Isogeny group action based signatures are obtained from a sigma protocol with high soundness error, say $\frac{1}{2}$ for its most basic variant. One needs to independently repeat the sigma protocol $O(\lambda)$ times to reduce the soundness error to negligible (with $\lambda$ being the security parameter). These repetitions come with a considerable efficiency and size overhead. On the other hand, quaternion isogeny-based signatures such as SQIsign and PRISM are directly obtained from a sigma protocol with a negligible soundness error. The secret key in the SQIsign and PRISM is a random supersingular isogeny, and both schemes are insecure when the secret isogeny arises from the supersingular isogeny group action setting.
In this paper, we propose WaterSQI and PRISMO, variants of SQIsign and PRISM respectively, suited for secret isogenies that arise from the supersingular isogeny group action setting. They use a sigma protocol whose soundness error is negligible without requiring parallel repetitions. They are hence more compact and $O(\lambda)$ times more efficient compared to Generalised CSI-FiSh (the generalisation of CSI-FiSh to large parameters using generic isogeny group action evaluation algorithms such as Clapotis/KLaPoTi/PEGASIS). For example, for our proof of concept implementation with a 2000 bits prime in sagemath, PRISMO, when compared to Generalised CSI-FiSh with the same public key size, is about 3x faster for key generation, 273x faster for signing and 4900x faster for verification, while also being 29x more compact (signature size).
## 2025/1738
* Title: Optimal Byzantine Agreement in the Presence of Message Drops
* Authors: Hanwen Feng, Zhenliang Lu, Qiang Tang, Yuchen Ye
* [Permalink](https://eprint.iacr.org/2025/1738)
* [Download](https://eprint.iacr.org/2025/1738.pdf)
### Abstract
To more accurately capture real-world network and adversarial behaviors, recent research has explored Byzantine Agreement (BA) under various mixed fault models. The breakthroughs by Loss et al. (TCC'23, TCC'24) have established the feasibility of optimally resilient BA in these settings. Specifically, their protocols tolerate up to $t$ byzantine parties, $r$ receive faulty parties, and $s$ send faulty parties in a network of $n > 2t + r + s$ parties. Initially, Loss et al. (TCC'23) considers a model that a party will be either receive faulty or send faulty but not at the same time (called non-overlapping model). The extended model in Loss et al. (TCC'24) further accommodates the overlapping model, where a party can simultaneously exhibit both receive faulty and send faulty behaviors. However, despite this flexibility, both protocols incur a prohibitively high $O(n^5)$-bit communication cost, leaving open the fundamental question of whether the optimal $O(n^2)$-bit complexity achieved by many classical BA protocols is attainable in the optimally resilient mixed fault model (with overlapping faults or not).
In this work, we answer these open questions affirmatively. We present a mixed-fault BA protocol that achieves the optimal expected $O(n^2\lambda)$ communication complexity while maintaining expected $O(1)$ round complexity and optimal (strongly adaptive) resilience. Our protocol supports the strongest overlapping model, while matching the best-known complexity of classical BA protocols. To achieve this, we develop a series of novel techniques, carefully designed to ensure efficient and secure agreement even under mixed faults. Beyond binary BA, we extend our protocol to a multi-valued BA setting, achieving an expected communication complexity of $O(\frac{n^2}{t}L + n^2\lambda^2)$ and an expected round complexity of $O(1)$, where $t$ is the number of byzantine faults, and $L$ is the bit-length of the input values. In particular, for $t = O(n)$, the communication reduces to $O(nL + n^2\lambda^2)$. Notably, our protocols operate under the same setup and cryptographic assumptions as those in Loss et al.
## 2025/1739
* Title: Attacking an RSA-like Cryptosystem Using Continued Fractions and Lattices
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2025/1739)
* [Download](https://eprint.iacr.org/2025/1739.pdf)
### Abstract
Let $N = pq$ be the product of two balanced primes. Cotan and Te\c seleanu (2023) introduced a family of RSA-like cryptosystems defined by $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$, encompassing classical RSA ($n=1$) and the ElkamchouchirCoElshenawyrCoShaban variant ($n=2$). We present a new attack for $n=3$ that integrates continued fractions with lattice-based methods, naturally extending previous results for $n = 1, 2, 4, 6$.
## 2025/1740
* Title: Improved Radix-based Approximate Homomorphic Encryption for Large Integers via Lightweight Bootstrapped Digit Carry
* Authors: Gyeongwon Cha, Dongjin Park, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2025/1740)
* [Download](https://eprint.iacr.org/2025/1740.pdf)
### Abstract
Homomorphic encryption (HE) for high-precision integers has been steadily researched through various schemes; however, these approaches incurred severe overhead as the bit-width grew, requiring larger parameters to support integers of several hundred to a thousand bits.
A significant breakthrough was recently made by Boneh et al.(Crypto'25). Their scheme constructs a residue number system from the different slots of a single CKKS ciphertext. This enables arithmetic on thousand-bit integers without increasing parameters.
However, RNS approach in Boneh et al., which performs approximate reduction, fundamentally cannot support non-arithmetic operations. Alternatively, radix-based approach proposed by Kim(CHES'25) can perform non-arithmetic operations, but they require $O(k)$ bootstraps for a bit-width $k$. This makes them highly inefficient, and thus impractical, for non-arithmetic operations requiring thousand-bit precision.
This paper proposes an improved radix-based CKKS scheme, centered on a 2-step algorithm that optimizes the number of bootstraps required for the digit carry operation to $O(\log k)$. The proposed scheme requires only 3-6 bootstraps to restore the result of a 32-2048 bit integer multiplication to its unique representation, which enables the efficient implementation of non-arithmetic operations such as comparison. Furthermore, our scheme extends the radix-based system, previously limited to prime-power moduli, to support an efficient homomorphic reduction algorithm for arbitrary moduli.
Furthermore, our experiments demonstrate substantial efficiency gains compared to Boneh et al. For example, for moduli used in homomorphic signatures(Curve25519, P-384, and 2048-bit RSA), our scheme can process up to 4$\times$ more integers in a single ciphertext. Specifically for Curve25519, we also reduce the latency by 1.4$\times$, shortening the amortized time by 5.6$\times$ compared to Boneh et. al. and achieving a final processing time of 1.34 seconds per data point.
## 2025/1741
* Title: Full L1 On-Chain ZK-STARK+PQC Verification on Solana: A Measurement Study
* Authors: Jotaro Yano
* [Permalink](https://eprint.iacr.org/2025/1741)
* [Download](https://eprint.iacr.org/2025/1741.pdf)
### Abstract
Blockchains preserve public data indefinitely, creating tension between verifiability today and secrecy decades hence. In particular, pairing-based SNARKs (e.g., Groth16, PLONK) rely on discrete-log assumptions that are structurally vulnerable to Shor-type quantum attacks, motivating hash-based alternatives. This work investigates whether a fully on-chain pipeline that verifies both a ZK-STARK and a post-quantum signature can operate within Solana L1's compute and memory constraints. Our prototype adapts Winterfell 0.12 with a dedicated SHA-256 hashv syscall path to reduce hashing overhead, suppresses inlining in FRI hotspots to respect SBF (Solana BPF) stack limits, and uses a custom bump allocator synchronized with requested heap frames. Artifacts are uploaded in ren900 byte chunks under a rolling hash chain and finalized in two steps: (i) SLH-DSA (SPHINCS+) signature verification over a length-delimited transcript, and (ii) STARK verification bound to SHA256(cipher) via public inputs. The result is an L1 verifier that is CPI-friendly, reproducible from a public repository, and engineered for predictable cost. On devnet, across n=100 runs, we measure mean finalize_sig cost of 5.01|u10^5 CU (median 4.999|u10^5) and mean verify_stark cost of 1.10|u10^6 CU (median 1.11|u10^6), with maxima below 1.19|u10^6 CU; all runs fit within Solana's 1.4|u10^6 CU transaction budget. At representative sizes, the derived intensities are ree63.8 CU/Sig-byte (7,856 B) and ree248.9 CU/Proof-byte (4,437 B), and verification scales approximately linearly with proof bytes under a fixed FRI policy. We systematize DoS and fee controls (fixed-offset appends, rolling-hash checks), justify the binding of public inputs to the ciphertext, and outline engineering levers (single-call hashing, stack discipline, phase separation) that make full L1 STARK+PQC verification practical at ree128-bit settings.
## 2025/1742
* Title: Broadcast Encryption with Size N^1/3 and More from k-Lin
* Authors: Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2025/1742)
* [Download](https://eprint.iacr.org/2025/1742.pdf)
### Abstract
We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree $3$ polynomials with compact parameters: the public key, ciphertext and secret keys comprise $O(n)$ group elements, where $n$ is input length for the
function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for $N$ users with $O(N^{1/3})$-sized parameters, breaking the long-standing $\sqrt{N}$ barrier for pairing-based
broadcast encryption. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) $k$-Lin assumption in prime-order bilinear groups.
## 2025/1743
* Title: NISQ Security and Complexity via Simple Classical Reasoning
* Authors: Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song
* [Permalink](https://eprint.iacr.org/2025/1743)
* [Download](https://eprint.iacr.org/2025/1743.pdf)
### Abstract
We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models.
We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth.
At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning.

As applications, we derive the first direct product theorems in the average case, in the hybrid setting - i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.
## 2025/1744
* Title: Randomness beacons from financial data in the presence of an active attacker
* Authors: Daji Landis, Joseph Bonneau
* [Permalink](https://eprint.iacr.org/2025/1744)
* [Download](https://eprint.iacr.org/2025/1744.pdf)
### Abstract
Using stock market data as a source of public randomness has deep historical roots and has seen renewed interest with the development of verifiable delay functions. Prior work has estimated that asset prices contain ample entropy to prevent prediction by a passive observer, but has not considered an active attacker making trades in the marketplace. VDFs can make manipulation more difficult, forcing an attacker to precompute beacon results for some number of potential outcomes and then force the market into one of them by price manipulation. To date, there has been no analysis of the difficulty of such an attack. We propose a framework for evaluating this attack using standard finance models for price movement and the price impact of trades. We then estimate from empirical data that, even under generous assumptions, for a basket of large-cap stocks (the S&P 100) an active adversary would require huge capital reserves (on the order of billions of US dollars) and incur major losses to slippage (millions of US dollars).
## 2025/1745
* Title: Fault Attacks on MPCitH Signature Schemes
* Authors: Harrison Banda, Jan Brinkmann, Juliane Kr|nmer
* [Permalink](https://eprint.iacr.org/2025/1745)
* [Download](https://eprint.iacr.org/2025/1745.pdf)
### Abstract
In this work, we present two fault attacks against MPCitH-based signature schemes: we present a key recovery attack and a signature forgery attack, both of which only need a single successful fault injection to succeed. We analyze all five MPCitH-based schemes which are currently analyzed in round 2 of NIST's additional signature standardization process: Mirath, MQOM, PERK, RYDE, and SDitH. Our analysis shows that all five schemes are vulnerable to at least one of the attacks. We validate the practicality of our attacks using the ChipWhisperer setup and discuss countermeasures to prevent the attacks.
## 2025/1746
* Title: Cross-chain Lightning Trades: Getting the Advantages of a Custodial Exchange while Keeping Your Assets
* Authors: Michele Ciampi, Muhammad Ishaq, Rafail Ostrovsky, Ioannis Tzannetos, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2025/1746)
* [Download](https://eprint.iacr.org/2025/1746.pdf)
### Abstract
Payment channels are a cornerstone of a scalable blockchain infrastructure that enables transacting parties to lock assets on the blockchain and perform rapid off-chain updates with minimal latency and overhead. These protocols dramatically reduce on-chain interaction and improve throughput, with blockchain consensus only invoked in the event of disputes or final closure. While widely adopted in single-chain settingsrCosuch as in the Lightning Network for BitcoinrCoexisting constructions have several limitations, in particular they suffer from at least one of the following limitations:
1) No cross-chain. They do not enable fast trading of assets that reside on multiple isolated blockchains.
2) Non-optimal round complexity. The off-chain round complexity is not optimal (i.e., parties require more than two rounds to update the channel).
3) No bitcoin compatibility. They require a more advanced scripting language that prevents cross-chain interaction between chains that only have a simple (Bitcoin-like) scripting language.
In this work, we introduce a novel payment channel protocol that breaks through all the above limitations. Our construction supports bidirectional, multiasset, and off-chain interaction across an arbitrary set of blockchains, where each update of the channel requires the parties to send only one message each. Our protocol is fully compatible with Bitcoin and can be deployed on chains with only minimal scripting capabilities, making it broadly applicable to real-world blockchain networks.
Crucially, our design ensures atomic settlement across blockchains without relying on trusted intermediaries.
We formally prove the security of our protocol together with a novel definition of the cross-chain payment channel that we introduce. Finally, we empirically validate our protocol, showing the minimal costs that our payment channel incurs in the setting where two parties make multiple exchanges of assets that reside on three different blockchains.
## 2025/1747
* Title: Masked Circuit Compiler in the Cardinal Random Probing Composability Framework
* Authors: Victor Normand, Sonia Bela|>d, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2025/1747)
* [Download](https://eprint.iacr.org/2025/1747.pdf)
### Abstract
Designing practically secure masked circuits remains a central problem in the field of cryptographic implementation. While most masking schemes have been proven secure in the classical probing model, this model fails to capture more advanced side-channel attacks such as horizontal attacks. In recent years, the community has shifted toward the more realistic random probing model, which offers stronger guarantees. Yet, balancing strong security with practical efficiency continues to be a significant challenge.
In this work, we introduce new tools and constructions that significantly improve the design and analysis of random probing secure circuits. First, we formalize new security notions that combine the benefits of cardinal and general Random Probing Composability (RPC), two recently introduced notions enabling more flexible and efficient composition of secure gadgets. We then show how uniformly random permutations can be applied to transform any cardinal or general RPC gadget into a so-called uniformly cardinal RPC gadget, thereby enhancing security at low cost. Using these techniques, we propose the first non-linear multiplication gadget, inspired by the recursive construction from CHES 2016, that achieves concrete cardinal RPC security. We provide a detailed comparison with state-of-the-art multiplication gadgets in terms of both random probing advantage and implementation complexity. Building upon this gadget, we design a tighter random probing compiler that strategically uses permutations to improve security bounds while preserving efficiency. Finally, we apply our compiler to the AES and demonstrate improved performance and security compared to existing methods.
## 2025/1748
* Title: Post-Quantum TLS 1.3 Handshake from CPA-Secure KEMs with Tighter Reductions
* Authors: Jinrong Chen, Biming Zhou, Rongmao Chen, Haodong Jiang, Yi Wang, Xinyi Huang, Yunlei Zhao, Moti Yung
* [Permalink](https://eprint.iacr.org/2025/1748)
* [Download](https://eprint.iacr.org/2025/1748.pdf)
### Abstract
TLS 1.3 is at the heart of secure modern internet communications. With the rise of quantum attacks, post-quantum TLS 1.3, built on post-quantum key encapsulation mechanisms (KEMs), has naturally become a major research focus. At Eurocrypt 2022, Huguenin-Dumittan and Vaudenay demonstrated that KEMs secure against chosen-plaintext attacks (CPA) are sufficient to construct a secure TLS 1.3 handshake in the random oracle model (ROM), but their security reduction incurs an $\mathcal{O}(q^6)$ loss, where $q$ is the number of random oracle queries. Improving their security bounds was left as an open problem. To address this problem, Zhou et al. took the first step at Asiacrypt 2024, improving the loss factor to $\mathcal{O}(q^2)$ in the ROM and $\mathcal{O}(q^4)$ in the quantum ROM (QROM) for OW-CPA secure KEMs, and to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for IND-CPA secure KEMs.
In this work, we further advance the state-of-the-art by providing tighter security reductions for the post-quantum TLS 1.3 handshake based on CPA-secure KEMs. We introduce a new security notion, \textit{IND-1CCA-1MAC}, and demonstrate that the loss factors can be further improved with a slight ciphertext expansion, i.e., $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for OW-CPA secure KEMs, and only $\mathcal{O}(1)$ in both models for IND-CPA secure KEMs. Furthermore, we prove that without ciphertext expansion, the loss factor of $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) is unavoidable. Given the above theoretical results, we investigate the security of TLS 1.3 based on CPA-secure KEMs in the hybrid key exchange and experimentally demonstrate that ciphertext expansion is indeed a viable trade-off for mitigating reduction losses.
## 2025/1749
* Title: Sandwich BUFF: Achieving Non-Resignability Using Iterative Hash Functions
* Authors: Serge Fehr, Yu-Hsuan Huang, Julia Kastner
* [Permalink](https://eprint.iacr.org/2025/1749)
* [Download](https://eprint.iacr.org/2025/1749.pdf)
### Abstract
We revisit the BUFF transform, which was proposed by Cremers et al. (S&P'21) as a means to achieve security properties beyond standard unforgeability for digital signature schemes. One of these properties, non-resignability (NR), has recently drawn some attention due to a strong impossibility result for the original definition of the property. Recent follow-up work then considered a variant (sNR) of the original definition, and showed that it is satisfied by the BUFF transform when the underlying hash function is modeled as a random oracle - while the original impossibility result still applies for the plain model. This raises the natural question of whether the BUFF transform satisfies sNR in a more fine-grained use of the random oracle model, when we consider a real-life iterative-hash-function design (such as Merkle-Damgaard or Sponge) and instead idealize the round function. Our discoveries in this direction are two-fold:
First, contrary to what one might expect, we show that there is a simple attack on the non-resignability property sNR of the BUFF-transform when instantiated with an iterative hash function. The attack relies on leaking an intermediate result of the hash computation to the adversary who is challenged to "resign" the message. This negative result once more shows the subtlety in the non-resignability property.
Second, on the positive side, we propose a small modification to the original BUFF transform, which we call Sandwich BUFF (for reasons to become clear), and prove the non-resignability property sNR of Sandwich BUFF both for Merkle-Damgaard-based hash functions in the random oracle model, and for Sponge-based hash functions in the random permutation model.
## 2025/1750
* Title: Modeling Emails: On the Deniability of BCCs
* Authors: Jonas Janneck, Aysan Nishaburi, Guilherme Rito
* [Permalink](https://eprint.iacr.org/2025/1750)
* [Download](https://eprint.iacr.org/2025/1750.pdf)
### Abstract
Emails are one of the main forms of digital communication. They were designed to provide many guarantees that have surprisingly not yet been formalized in cryptography. Yet many of the guarantees emails were designed to provide have not been formalized in cryptography. This paper models an important feature of email applications: the plausible deniability of including Bcc recipients. Concretely,
- we define a basic (theoretical) email application capturing these guarantees in Constructive Cryptography (Maurer and Renner, ICS '11)
- we introduce Email Encryption: a new cryptographic primitive that is tailor-made to construct our email application
- we define game-based notions for Email Encryption schemes, proving that their combination is sufficient to construct our simple email application and
- we give a generic (proof-of-concept) construction of an Email Encryption scheme that provides all these guarantees.
Our work identifies and formalizes missing theoretical foundations for the security of emails providing the first step towards practical solutions.
## 2025/1751
* Title: On the Existence and Construction of Very Strong Elliptic Curves
* Authors: Andrey S. Shchebetov
* [Permalink](https://eprint.iacr.org/2025/1751)
* [Download](https://eprint.iacr.org/2025/1751.pdf)
### Abstract
This paper introduces and formalizes new, stringent security notions for elliptic curves, establishing a higher benchmark for cryptographic strength. We define two new classes of secure elliptic curves, which offer resilience against a broader range of known attacks, including those leveraging the curve's endomorphism ring or the twist's group structure. To construct curves satisfying these exceptional criteria, we develop a highly scalable, parallel framework based on the complex multiplication method. Our approach efficiently navigates the vast parameter space defined by safe primes and fundamental discriminants. The core of our method is an efficient scanning algorithm that postpones expensive curve construction until after orders are confirmed to meet our security definitions, enabling significant search efficiency. As a concrete demonstration of our definitions and techniques, we conducted a large-scale computational experiment. This resulted in the first known construction of 91 very strong 256-bit curves with extreme twist order (i.e., curve order is a safe prime and twist order is prime) and cofactor $u=1$ along with 4 such 512-bit curves meeting the extreme twist order criteria. Among these, one 512-bit curve has both its order (a safe prime) and its twist order being prime, while the other three have a small cofactor ($u=7$) but their twist orders are primes. All curves are defined over finite fields whose orders are safe primes. These results not only prove the existence of these cryptographically superior curves but also provide a viable path for their systematic generation, shifting the paradigm from constructing curves faster to constructing curves that are fundamentally stronger.
## 2025/1752
* Title: Foundations of Dynamic Group Signatures: The Case of Malicious Openers and Issuers
* Authors: Stephan Krenn, Kai Samelin, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2025/1752)
* [Download](https://eprint.iacr.org/2025/1752.pdf)
### Abstract
Group signatures enable users to sign on behalf of a group while preserving anonymity, with accountability provided by a designated opener. The first rigorous model for dynamic groups (Bellare, Shi, Zhang, CT--RSA '05) captured anonymity, non-frameability, and traceability, later extended with trace-soundness (Sakai et al., PKC '12) and non-claimability (introduced as ``opening-soundness'' by Bootle et al., ACNS '16 & JoC '20).
In practice, issuer and opener are often distinct entities, often implemented by different organizations and/or hardware modules. We therefore formalize and prove the consequences of a model that enforces their complete separation, allows key reuse across groups, treats issuer and opener as stateless, and makes both joining and opening non-interactive.
This separation makes it necessary to reformulate traceability against a corrupt issuer and to introduce three additional unforgeability notions-key-unforgeability, certificate-unforgeability, and opening-unforgeability-for the case of a corrupt opener. Following this line of reasoning, we also develop strengthened formulations of trace-soundness and non-claimability.
We prove that in this model the eight resulting properties are fully distinct: even the conjunction of any seven does not imply the eighth. This yields the first comprehensive map of group signature security in a stateless, reusable-key, and non-interactive framework, and formally demonstrates the impact of complete issuer--opener separation.
## 2025/1753
* Title: Bootstrapping over Free $\mathcal{R}$-Module
* Authors: Ruida Wang, Jikang Bai, Yijian Liu, Xinxuan Zhang, Xianhui Lu, Lutan Zhao, Kunpeng Wang, Rui Hou
* [Permalink](https://eprint.iacr.org/2025/1753)
* [Download](https://eprint.iacr.org/2025/1753.pdf)
### Abstract
Bootstrapping, introduced by Gentry at STOC 2009, remains the only known method for realizing fully homomorphic encryption (FHE). Since Alperin-Sheriff and PeikertrCOs 2014 breakthrough on symmetric group accumulator (ACC) based bootstrapping, algebraic ACC designs have offered the lowest bootstrapping latency. The work of Ducas and Micciancio further advanced this paradigm by embedding $\mathbb{Z}_q$ into the multiplicative subgroup of the cyclotomic ring $\mathcal{R}_N$ and exploiting FFT/NTT for fast computation, leading to the milestone constructions FHEW and TFHE. Despite their efficiency, these ring-based schemes face a fundamental limitation: correctness requires $q < 2N$, rigidly coupling precision, performance, and key size to the polynomial dimension.
We address this limitation by introducing a new accumulator structure - a free $\mathcal{R}_N$-module $\bigoplus_{i=0}^{\tau-1} \mathcal{R}_N X^i$. This generalization decouples $q$ and $N$ through a tunable factor $\tau$, with the classical ring-based construction recovered as the special case $\tau=1$. The computation over resulting $\mathcal{R}_N$-algebra enables efficient computation over $\bigoplus_{i=0}^{\tau-1} \mathcal{R}_N X^i$ can be effectively reduced to the base ring $\mathcal{R}_N$. Based on this structure, we design a bootstrapping scheme that achieves asymptotic improvements in precision, performance, and key size. Experimental results further demonstrate significant concrete gains, confirming the practicality of our approach.
## 2025/1754
* Title: Machine Learning and Side-Channel Attacks on Post-Quantum Cryptography * Authors: Abiodun Olaluwe, Nouf Nur Nabilah, Sheikh Tareq, Akshay Raghavendra Kulkarni, Annamalai Annamalai
* [Permalink](https://eprint.iacr.org/2025/1754)
* [Download](https://eprint.iacr.org/2025/1754.pdf)
### Abstract
The transition to post-quantum cryptography (PQC) is accelerating due to the potential of quantum computing to compromise classical public-key cryptosystems. While standardized schemes such as CRYSTALS-Kyber, CRYSTALS-Dilithium, and SPHINCS+ offer strong theoretical security, practical deployments remain susceptible to physical-layer vulnerabilities, notably side-channel attacks (SCAs). SCAs exploit unintentional leakages in hardware and software implementationsrCosuch as power traces, electromagnetic emissions, and timing variationsrCoto recover secret keys without altering the target system. These attacks are non-invasive, cost-effective, and applicable across diverse platforms, making them a critical threat vector for PQC in embedded and resource-constrained environments.
This survey provides a structured, in-depth review of SCAs targeting PQC implementations, encompassing both classical methodsrCosuch as Simple Power Analysis, Differential Power Analysis, Correlation Power Analysis, Template Attacks, and Mutual Information AnalysisrCoand emerging machine learning (ML)-driven approaches. Special attention is given to deep learning models, including CNNs, RNNs, and MLPs, which have demonstrated superior performance in profiling attacks by automatically learning leakage patterns from high-dimensional trace data, even in the presence of countermeasures like masking and desynchronization.
We categorize and compare recent attack strategies, analyze their effectiveness against various PQC schemes, and examine the limitations of existing countermeasures. Finally, we identify open research challenges and outline hybrid defense strategies that integrate classical protections with adaptive, ML-aware mitigation techniques. This comprehensive synthesis aims to bridge the gap between PQC algorithm design and secure, implementation-level deployment in the quantum era.
## 2025/1755
* Title: DAKE: Bandwidth-Efficient (U)AKE from Double-KEM
* Authors: Hugo Beguinet, C|-line Chevalier, Guirec Lebrun, Thomas Legavre, Thomas Ricosset, Maxime Rom|-as, |eric Sageloli
* [Permalink](https://eprint.iacr.org/2025/1755)
* [Download](https://eprint.iacr.org/2025/1755.pdf)
### Abstract
Bandwidth remains a major bottleneck for post-quantum cryptography, especially in authenticated key exchange (AKE). We propose DAKE, a bandwidth-efficient AKE protocol built from double-KEM constructions. DAKE comes in two main versions, achieving weak and full perfect forward secrecy, and admits two further variants: a unilateral version, and one where a signature replaces a KEM on one side. DAKE is proven secure in the standard model under strong variants of the extended Canetti--Krawczyk framework, namely eCKw and eCK-PFS.
At the heart of DAKE lies the double-KEM, a primitive that encapsulates one key under two public keys. To broaden the range of double-KEMs compatible with DAKE, we introduce the chosen-key Fujisaki--Okamoto transform (CK-FO), which upgrades IND-CPA security to IND-CCA and one-sided chosen-key security, proven in the QROM.
As a concrete instantiation, we present Maul, a compact double-KEM derived from ML-KEM and based on the Hint-MLWE assumption. Maul reuses ciphertext components to cut size by up to 40\% compared to two parallel ML-KEMs, while achieving the left-sided chosen-key IND-CCA security required by DAKE via our CK-FO. Instantiating DAKE with Maul yields global communication reductions of about 17% in the mutual setting and 21% in the unilateral setting, outperforming both the double-KEM AKE of Xue et al. (ASIACRYPT 2018) and standard ML-KEM-based AKEs. These results show that double-KEMs offer a practical path toward bandwidth-efficient post-quantum key exchange.
## 2025/1756
* Title: Are Neural Networks Collision Resistant?
* Authors: Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc M|-zard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina
* [Permalink](https://eprint.iacr.org/2025/1756)
* [Download](https://eprint.iacr.org/2025/1756.pdf)
### Abstract
When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity of finding a collision in a single-layer neural net, where a collision is defined as two distinct sets of weights that assign the same labels to all data. For binary perceptrons with oscillating activation functions, we establish the emergence of an overlap gap property in the space of collisions. This is a topological property believed to be a barrier to the performance of efficient algorithms. The hardness is supported by numerical experiments using approximate message passing algorithms, for which the algorithms stop working well below the value predicted by our analysis. Neural networks provide a new category of candidate collision resistant functions, which for some parameter setting depart from constructions based on lattices. Beyond relevance to cryptography, our work uncovers new forms of computational hardness emerging in large neural networks which may be of independent interest.
## 2025/1757
* Title: New key establishment protocol based on random 1 walks in infinite forest
* Authors: Vasyl Ustimenko, Tymoteusz Chojecki
* [Permalink](https://eprint.iacr.org/2025/1757)
* [Download](https://eprint.iacr.org/2025/1757.pdf)
### Abstract
We suggest post quantum secure protocol based on pseudorandom walk on infinite q-regular forest D(q) where q = 2^m, m > 1. Correspondents share positive integer n, pseudorandom tuple from (Fq) ^n and two pseudorandom input words in the alphabet F_q of length O(1). They use the group of cubic multivariate transformations of the vector space of points of D(q) induced by walks on the forest of
even length as the platform for the implementation of modified Twisted Diffie-Hellman protocol of Noncommutative Cryptography based on the complexity of the Conjugacy Power Problem. The output of the protocol is a vector from (F_q)^n. In fact the action of the group on the partition set of the bipartite homomorphic image D(n, q) of the forest is used. Correspondents elaborate the collision vector in time O(n^2) in the case when the length of input words is O(1) and the size of private integer parameters is O(n). If length of the input words is also O(n) then the complexity of protocol will be O(n^3). We suggest also the obfuscation of the scheme with hidden graph of the
1complexity O(n^5) for which the output of the algorithm is a symbolic cubic transformation F of (Fq)^n. It can be used symbiotically with the symmetric encryption via the adding to the ciphertext from (F_q)^n the vector F(b_1, b_2, . . . , b_n) where the tuple (b_1, b_2, . . . , b_n) of pseudorandom nature is known publicly.
## 2025/1758
* Title: Revisiting PQ WireGuard: A Comprehensive Security Analysis With a New Design Using Reinforced KEMs
* Authors: Keitaro Hashimoto, Shuichi Katsumata, Guilhem Niot, Thom Wiggers
* [Permalink](https://eprint.iacr.org/2025/1758)
* [Download](https://eprint.iacr.org/2025/1758.pdf)
### Abstract
WireGuard is a VPN based on the Noise protocol, known for its high performance, small code base, and unique security features. Recently, H|+lsing et al. (IEEE S&P'21) presented post-quantum (PQ) WireGuard, replacing the Diffie-Hellman (DH) key exchange underlying the Noise protocol with key-encapsulation mechanisms (KEMs). Since WireGuard requires the handshake message to fit in one UDP packet of size roughly 1200 B, they combined Classic McEliece and a modified variant of Saber. However, as Classic McEliece public keys are notoriously large, this comes at the cost of severely increasing the server's memory requirement. This hinders deployment, especially in environments with constraints on memory (allocation), such as a kernel-level implementations.
In this work, we revisit PQ WireGuard and improve it on three fronts: design, (computational) security, and efficiency. As KEMs are semantically, but not syntactically, the same as DH key exchange, there are many (in hindsight) ad-hoc design choices being made, further amplified by the recent finding on the binding issues with PQ KEMs (Cremers et al., CCS'24). We redesign PQ WireGuard addressing these issues, and prove it secure in a new computational model by fixing and capturing new security features that were not modeled by H|+lsing et al. We further propose 'reinforced KEM' (RKEM) as a natural building block for key exchange protocols, enabling a PQ WireGuard construction where the server no longer needs to store Classical McEliece keys, reducing public key memory by 190 to 390|u. In essence, we construct a RKEM named 'Rebar' to compress two ML-KEM-like ciphertexts which may be of an independent interest.
## 2025/1759
* Title: Plonk is Simulation Extractable in ROM Under Falsifiable Assumptions
* Authors: Helger Lipmaa
* [Permalink](https://eprint.iacr.org/2025/1759)
* [Download](https://eprint.iacr.org/2025/1759.pdf)
### Abstract
Solving a long-standing open problem, Faonio, Fiore, and Russo proved that the widely used Plonk zk-SNARK is simulation extractable. However, their proof assumes both the random oracle model (ROM) and the algebraic group model. We prove that the same holds in the ROM under falsifiable assumptions. We combine the template of Faust et al., who proved that simulation extractability follows from knowledge soundness, (weak) unique response, and trapdoorless zero-knowledge, with the recent result of Lipmaa, Parisella, and Siim (Crypto 2025), who proved that Plonk has knowledge soundness in the ROM under falsifiable assumptions. For this, we prove that Plonk satisfies new variants of the weak unique response and trapdoorless zero-knowledge properties. We prove that several commonly used gadgets, like the linearization trick, are not trapdoorless zero-knowledge when considered as independent commit-and-prove zk-SNARKs.
## 2025/1760
* Title: Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE
* Authors: Chris Peikert, Zachary Pepin
* [Permalink](https://eprint.iacr.org/2025/1760)
* [Download](https://eprint.iacr.org/2025/1760.pdf)
### Abstract
The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption~(FHE), has relied on *cyclotomic* number fields and rings. This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on "packed" plaintexts, automorphisms, and ring-switching. However, selecting a suitable cyclotomic that has the desired number and type of plaintext "slots," while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency.
This work provides a suite of tools for instantiating ring-based lattice cryptography to work over *subfields* of cyclotomics, which provide more flexibility and better-fitting parameters for applications. A particular focus is on realizing FHE with *optimal plaintext packing* and homomorphic SIMD parallelism for *any* plaintext characteristic, along with efficient *packed bootstrapping* that fully exploits this parallelism.
Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory:
-- For sampling and decoding errors in encryption and decryption (respectively), we construct geometrically short, structured bases for the number rings of arbitrary subfields of prime-power cyclotomics (and hence their composites as well).
-- For fast ring arithmetic, we define and establish analogous structural properties for Chinese Remainder Theorem (CRT) bases in *abelian* number rings, and give specialized fast transforms that map between CRT bases and any similarly structured bases.
-- For packed bootstrapping and homomorphic linear algebra, we give a general framework for *homomorphic evaluation of structured linear transforms* in abelian number rings, and show that CRT transforms can be evaluated using relatively few homomorphic operations.
## 2025/1761
* Title: Automated Proof for Quadratic Functional Encryption: Finding Attacks and New Constructions
* Authors: Geng Wang, Ruoyi Kong, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/1761)
* [Download](https://eprint.iacr.org/2025/1761.pdf)
### Abstract
Quadratic functional encryption (QFE for short) is a cryptographic primitive which can output the value of a quadratic function between two vectors, without leaking other information on the plaintext vectors. Since the first breakthrough of Baltico et al. (Crypto 2017), there are already many constructions for QFE from bilinear groups. However, constructing more efficient QFE schemes and proving their security has always been a challenging task. While generic bilinear group model (GBGM for short) can be used to construct highly efficient QFE schemes and proving their security, obtaining a security proof under GBGM is difficult and may contain undiscovered mistakes.

In this paper, we solve this problem by presenting new techniques which finally lead to an automated proof tool for QFE schemes, and can also be used to find potential attacks. Our automated proof tool shows that the RPB+19 scheme (Riffel et al, NIPS'19) which is the most efficient QFE scheme in the literature and already used in several works, is in fact insecure, and also gives an attack for the scheme. Finally, we present two new QFE schemes, each shares same efficiency with the RPB+19 scheme from one aspect, and prove their security using our automated proof tool. Our new schemes are more efficient than all existing QFE schemes other than the RPB+19 scheme, which means that they are most efficient among all existing ``secure'' QFE schemes.
## 2025/1762
* Title: Threshold Signatures from One-Way Functions
* Authors: Pedro Branco, Giulio Malavolta
* [Permalink](https://eprint.iacr.org/2025/1762)
* [Download](https://eprint.iacr.org/2025/1762.pdf)
### Abstract
A threshold signature allows one to delegate its signing rights to $n$ parties, such that any subset of size $t$ can sign a message on their behalf. In this work, we show how to construct threshold signatures for any $t$ and $n$ from one way functions, thus establishing the latter as a necessary and sufficient computational assumption. Our protocol makes non-black box use of one-way functions, and can be generalized to other access structures, such as monotone policies.
## 2025/1763
* Title: A High Throughput Kyber NTT
* Authors: Jonas Bertels, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/1763)
* [Download](https://eprint.iacr.org/2025/1763.pdf)
### Abstract
NIST recently selected Kyber as a standard for key encapsulation and decapsulation. As such, servers will soon need dedicated hardware for these encapsulation protocols. The computationally critical operation of Kyber is its Number Theoretic Transform, which is commonly accelerated by dedicated hardware such as FPGAs.
This work presents an extremely high-throughput design for the Kyber NTT. By utilizing the LUT-based modular multiplication technique used by us in CHES 2025, its area delay product is generally between one and two orders of magnitude better than similar designs in literature. For instance, where Yaman et al. with 16 Processing Elements requires 9500 LUTs and 16 DSPs to perform an NTT in 69 clock cycles, our design requires 67210 LUTs and no DSPs to perform an NTT every clock cycle.
--- Synchronet 3.21a-Linux NewsLink 1.2