## In this issue
1. [2024/746] The Art of Bonsai: How Well-Shaped Trees Improve ...
2. [2025/378] Side-Channel and Fault Injection Attacks on VOLEitH ...
3. [2025/612] More NTRU+Sign Signatures from Cyclotomic Trinomials
4. [2025/621] SPHINCSLET: An Area-Efficient Accelerator for the ...
5. [2025/622] Byzantine Reliable Broadcast and Tendermint ...
6. [2025/623] CertainSync: Rateless Set Reconciliation with Certainty
7. [2025/624] Trapdoor one-way functions from tensors
8. [2025/625] FHECAP: An Encrypted Control System with Piecewise ...
9. [2025/626] Tree-based Quantum Carry-Save Adder
10. [2025/627] Everlasting Fully Dynamic Group Signatures
11. [2025/628] Improving the Masked Division for the FALCON Signature
12. [2025/629] Audience Injection Attacks: A New Class of Attacks ...
13. [2025/630] Charge Your Clients: Payable Secure Computation and ...
14. [2025/631] Dyna-hinTS: Silent Threshold Signatures for Dynamic ...
15. [2025/632] On breaking McEliece keys using brute force
16. [2025/633] Hybrid-query bounds with partial input control - ...
17. [2025/634] Cryptography based on 2D Ray Tracing
18. [2025/635] Towards Scalable YOSO MPC via Packed Secret-Sharing
19. [2025/636] Impossible Differential Attack on SAND-64
20. [2025/637] A Study of Blockchain Consensus Protocols
21. [2025/638] Round-Efficient Adaptively Secure Threshold ...
22. [2025/639] Cryptomania v.s. Minicrypt in a Quantum World
23. [2025/640] Multi-Party Private Set Operations from Predicative ...
24. [2025/641] Scalable Non-Fungible Tokens on Bitcoin
25. [2025/642] A Meta-Complexity Characterization of Quantum ...
26. [2025/643] Obfuscation for Deep Neural Networks against Model ...
27. [2025/644] Attacking at non-harmonic frequencies in screaming- ...
28. [2025/645] GIGA Protocol: Unlocking Trustless Parallel ...
29. [2025/646] Secret-Key PIR from Random Linear Codes
30. [2025/647] Anamorphic Voting: Ballot Freedom Against Dishonest ...
31. [2025/648] HQC Beyond the BSC: Towards Error Structure-Aware ...
32. [2025/649] Guaranteed Termination Asynchronous Complete Secret ...
33. [2025/650] ADC-BE: Optimizing Worst-Case Bandwidth in ...
34. [2025/651] Low-Latency Bootstrapping for CKKS using Roots of Unity
35. [2025/652] MultiCent: Secure and Scalable Centrality Measures ...
36. [2025/653] Fission: Distributed Privacy-Preserving Large ...
37. [2025/654] ECDSA Cracking Methods
38. [2025/655] Taking AI-Based Side-Channel Attacks to a New Dimension
39. [2025/656] Unbounded Multi-Hop Proxy Re-Encryption with HRA ...
40. [2025/657] Key Derivation Functions Without a Grain of Salt
41. [2025/658] Efficient Verifiable Mixnets from Lattices, Revisited
42. [2025/659] Scalable and Fine-Tuned Privacy Pass from Group ...
43. [2025/660] Eccfrog512ck2: An Enhanced 512-bit Weierstrass ...
44. [2025/661] An LLM Framework For Cryptography Over Chat Channels
45. [2025/662] Attribute-Based Publicly Verifiable Secret Sharing
46. [2025/663] Intermundium-DL: Assessing the Resilience of ...
47. [2025/664] Publicly Verifiable Generalized Secret Sharing ...
48. [2025/665] MProve-Nova: A Privacy-Preserving Proof of Reserves ...
49. [2025/666] Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
50. [2025/667] Vector Commitment Design, Analysis, and ...
## 2024/746
* Title: The Art of Bonsai: How Well-Shaped Trees Improve the Communication Cost of MLS
* Authors: Céline Chevalier, Guirec Lebrun, Ange Martinelli, Jérôme Plût
* [Permalink](
https://eprint.iacr.org/2024/746)
* [Download](
https://eprint.iacr.org/2024/746.pdf)
### Abstract
Messaging Layer Security (MLS) is a Secure Group Messaging protocol that uses for its handshake a binary tree – called a Ratchet Tree – in order to reach a logarithmic communication cost in the number of group members. This Ratchet Tree represents users as its leaves; therefore any change in the group membership results in adding or removing a leaf in the tree. MLS consequently implements what we call a tree evolution mechanism, consisting of a user add algorithm – determining where to insert a new leaf – and a tree expansion process – stating how to increase the size of the tree when no space is available for a new user. The tree evolution mechanism currently used by MLS is designed so that it naturally left-balances the Ratchet Tree. However, such a tree structure is often quite inefficient in terms of communication cost. Furthermore, one may wonder whether the binary Ratchet Tree has a degree optimized for the features of MLS.
Therefore, we study in this paper how to improve the communication cost of the handshake in MLS – realized through an operation called a commit – by considering both the tree evolution mechanism and the tree degree used for the Ratchet Tree. To do so, we determine the tree structure that optimizes its communication cost and we propose algorithms for both the user add and the tree expansion processes, that allow to remain close to that optimal structure and thus to have a communication cost as close as possible to the optimum. We also find out the Ratchet Tree degree that is best suited to a given set of parameters induced by the encryption scheme used by MLS. This study shows that when using classical (i.e. pre-quantum) ciphersuites, a binary tree is indeed the most appropriate Ratchet Tree; nevertheless, with post-quantum algorithms, it generally becomes more interesting to use instead a ternary tree.
Our improvements do not change the TreeKEM protocol and are easy to implement.. With parameter sets corresponding to practical ciphersuites, they reduce TreeKEM’s communication cost by 5 to 10%. In particular, the gain of 10% appears in the post-quantum setting – when both an optimized tree evolution mechanism and a ternary tree are necessary –, which is precisely the context where any optimization of the protocol’s communication cost is welcome, due to the large bandwidth of PQ encrypted communication.
## 2025/378
* Title: Side-Channel and Fault Injection Attacks on VOLEitH Signature Schemes: A Case Study of Masked FAEST
* Authors: Sönke Jendral, Elena Dubrova
* [Permalink](
https://eprint.iacr.org/2025/378)
* [Download](
https://eprint.iacr.org/2025/378.pdf)
### Abstract
Ongoing efforts to transition to post-quantum public-key cryptosystems have created the need for algorithms with a variety of performance characteristics and security assumptions.
Among the candidates in NIST's post-quantum standardisation process for additional digital signatures is FAEST, a Vector Oblivious Linear Evaluation in-the-Head (VOLEitH)-based scheme, whose security relies on the one-wayness of the Advanced Encryption Standard (AES).
The VOLEitH paradigm enables competitive performance and signature sizes under conservative security assumptions.
However, since it was introduced recently, in 2023, its resistance to physical attacks has not yet been analysed. In this paper, we present the first security analysis of VOLEitH-based signature schemes in the context of side-channel and fault injection attacks. We demonstrate four practical attacks on a masked implementation of FAEST in ARM Cortex-M4 capable of recovering the full secret key with high probability (greater than 0.87) from a single signature. These attacks exploit vulnerabilities of components specific to VOLEitH schemes and FAEST, such as the parallel all-but-one vector commitments, the VOLE generation, and the AES proof generation. Finally, we propose countermeasures to mitigate these attacks and enhance the physical security of VOLEitH-based signature schemes.
## 2025/612
* Title: More NTRU+Sign Signatures from Cyclotomic Trinomials
* Authors: Ga Hee Hong, Joo Woo, Jonghyun Kim, Minkyu Kim, Hochang Lee, Jong Hwan Park
* [Permalink](
https://eprint.iacr.org/2025/612)
* [Download](
https://eprint.iacr.org/2025/612.pdf)
### Abstract
Recently, $\mathsf{NTRU}$+$\mathsf{Sign}$ was proposed as a new compact signature scheme, following `Fiat-Shamir with Aborts' (FSwA) framework. Its compactness is mainly based on their novel NTRU-based key structure that fits well with bimodal distributions in the FSwA framework. However, despite its compactness, $\mathsf{NTRU}$+$\mathsf{Sign}$ fails to provide a diverse set of parameters that can meet some desired security levels. This limitation stems from its reliance on a ring $\mathbb{Z}_q[x]/\langle x^n+1 \rangle$, where $n$ is restricted to powers of two, limiting the flexibility in selecting appropriate security levels. To overcome this limitation, we propose a revised version of $\mathsf{NTRU}$+$\mathsf{Sign}$ by adopting a ring $\mathbb{Z}_q[x]/\langle x^n-x^{n/2}+1\rangle$ from cyclotomic trinomials, where $n=2^{i}3^{j}$ for some positive integers $i$ and $j$. Our parameterization offers three distinct security levels: approximately $120$, $190$, and $260$ bits, while preserving the compactness in $\mathbb{Z}_q[x]/\langle x^n+1 \rangle$. We implement these re-parameterized $\mathsf{NTRU}$+$\mathsf{Sign}$ schemes, showing that the performance of $\mathsf{NTRU}$+$\mathsf{Sign}$ from cyclotomic trinomials is still comparable to previous lattice-based signature schemes such as $\mathsf{Dilithium}$ and $\mathsf{HAETAE}$.
## 2025/621
* Title: SPHINCSLET: An Area-Efficient Accelerator for the Full SPHINCS+ Digital Signature Algorithm
* Authors: Sanjay Deshpande, Yongseok Lee, Cansu Karakuzu, Jakub Szefer, Yunheung Paek
* [Permalink](
https://eprint.iacr.org/2025/621)
* [Download](
https://eprint.iacr.org/2025/621.pdf)
### Abstract
This work presents SPHINCSLET, the first fully standard-compliant and area-efficient hardware implementation of the SLH-DSA algorithm, formerly known as SPHINCS+, a post-quantum digital signature scheme. SPHINCSLET is designed to be parameterizable across different security levels and hash functions, offering a balanced trade-off between area efficiency and performance. Existing hardware implementations either feature a large area footprint to achieve fast signing and verification or adopt a coprocessor-based approach that significantly slows down these operations. SPHINCSLET addresses this gap by delivering a 4.7$\times$ reduction in area compared to high-speed designs while achieving a 2.5$\times$ to 5$\times$ improvement in signing time over the most efficient coprocessor-based designs for a SHAKE256-based SPHINCS+ implementation. The SHAKE256-based SPHINCS+ FPGA implementation targeting the AMD Artix-7 requires fewer than 10.8K LUTs for any security level of SLH-DSA. Furthermore, the SHA-2-based SPHINCS+ implementation achieves a 2$\times$ to 4$\times$ speedup in signature generation across various security levels compared to existing SLH-DSA hardware, all while maintaining a compact area footprint of 6K to 15K LUTs. This makes it the fastest SHA-2-based SLH-DSA implementation to date.. With an optimized balance of area and performance, SPHINCSLET can assist resource-constrained devices in transitioning to post-quantum cryptography.
## 2025/622
* Title: Byzantine Reliable Broadcast and Tendermint Consensus with trusted components
* Authors: Yackolley Amoussou-Guenou, Lionel Beltrando, Maurice Herlihy, Maria Potop-Butucaru
* [Permalink](
https://eprint.iacr.org/2025/622)
* [Download](
https://eprint.iacr.org/2025/622.pdf)
### Abstract
Byzantine Reliable Broadcast is one of the most popular communication primitives in distributed systems. Byzantine reliable broadcast ensures that processes agree to deliver a message from an initiator, even if some processes (possibly including the initiator) are Byzantine. In asynchronous settings, it is known since the prominent work of Bracha \cite{Bracha87} that Byzantine reliable broadcast can be implemented deterministically if the total number of processes, denoted by $n$, satisfies $n \geq 3t+1$ where $t$ is an upper bound on the number of Byzantine processes. Here, we study Byzantine Reliable Broadcast when processes are equipped with \emph{trusted components}, special software or hardware designed to prevent equivocation. Our contribution is threefold. First, we show that, despite common belief, when each process is equipped with a trusted component, Bracha's algorithm still needs $n \geq 3t+1$. Second, we present a novel algorithm that uses a single trusted component (at the initiator) that implements Byzantine Reliable Asynchronous Broadcast with $n \geq 2t+1$.
\yag{Lastly, building on our broadcast algorithm, we present TenderTee, a transformation of the Tendermint consensus algorithm by using trusted component, giving better Byzantine resilience. Tendertee works with $n \geq 2t+1$, where Tendermint needed $n=3t+1$.}
## 2025/623
* Title: CertainSync: Rateless Set Reconciliation with Certainty
* Authors: Tomer Keniagin, Eitan Yaakobi, Ori Rottenstreich
* [Permalink](
https://eprint.iacr.org/2025/623)
* [Download](
https://eprint.iacr.org/2025/623.pdf)
### Abstract
Set reconciliation is a fundamental task in distributed systems, particularly in blockchain networks, where it enables the synchronization of transaction pools among peers and facilitates block dissemination. Existing traditional set reconciliation schemes are either statistical, providing success probability as a function of the communication overhead and the size of the symmetric difference, or require parametrization and estimation of the size of the symmetric difference, which can be prone to error. In this paper, we present CertainSync, a novel reconciliation framework that, to the best of our knowledge, is the first to guarantee successful set reconciliation without any parametrization or estimators in use. The framework is rateless and adapts to the unknown symmetric difference size. The set reconciliation is guaranteed to be completed successfully whenever the communication overhead reaches a lower bound derived from the symmetric difference size and the universe size. Our framework is based on recent constructions of Invertible Bloom Lookup Tables (IBLTs) ensuring successful element listing as long as the number of elements is bounded. We provide a theoretical analysis to prove the certainty in the set reconciliation for multiple constructions. The approach is also validated by simulations, showing the ability to synchronize sets with efficient communication costs while maintaining reconciliation guarantees compared to other baseline schemes for set reconciliation. To further improve communication overhead for large universes as blockchain networks, CertainSync is extended with a universe reduction technique to minimize communication overhead. We compare and validate the extended framework UniverseReduceSync against the basic CertainSync framework through simulations using real blockchain transaction hash data from the Ethereum blockchain network. The results illustrate a trade-off between improved communication costs and maintaining reconciliation guarantees without relying on parametrization or estimators, offering a comprehensive solution for set reconciliation in diverse scenarios.
## 2025/624
* Title: Trapdoor one-way functions from tensors
* Authors: Anand Kumar Narayanan
* [Permalink](
https://eprint.iacr.org/2025/624)
* [Download](
https://eprint.iacr.org/2025/624.pdf)
### Abstract
Weyman and Zelevinsky generalised Vandermonde matrices to higher dimensions, which we call Vandermonde-Weyman-Zelevinsky tensors.
We generalise Lagrange interpolation to higher dimensions by devising a nearly linear time algorithm that given a Vandermonde-Weyman-Zelevinsky tensor and a sparse target vector, finds a tuple of vectors that hit the target under tensor evaluation. Tensor evaluation to us means evaluating the usual multilinear form associated with the tensor in all but one chosen dimension. Yet, this interpolation problem phrased with respect to a random tensor appears to be a hard multilinear system. Leveraging this dichotomy, we propose preimage sampleable trapdoor one-way functions in the spirit of Gentry-Peikert-Vaikuntanathan (GPV) lattice trapdoors. We design and analyse ``Hash-and-Sign'' digital signatures from such trapdoor one-way functions, yielding short signatures whose lengths scale nearly linearly in the security parameter. We also describe an encryption scheme.
Our trapdoor is a random Vandermonde-Weyman-Zelevinsky tensor over a finite field and a random basis change. We hide the Vandermonde-Weyman-Zelevinsky tensor under the basis change and publish the resulting pseudorandom tensor. The one way function is the tensor evaluation derived from the public tensor, restricted so as to only map to sparse vectors. We then design the domain sampler and preimage sampler demanded by the GPV framework. The former samples inputs that map to uniform images under the one-way function. The latter samples preimages given supplementary knowledge of the trapdoor. Preimage sampling is a randomised version of interpolation and knowing the basis change allows efficient translation between interpolation corresponding to the public and trapdoor tensors. An adversary seeking a preimage must solve a pseudorandom multilinear system, which seems cryptographically hard.
## 2025/625
* Title: FHECAP: An Encrypted Control System with Piecewise Continuous Actuation
* Authors: Song Bian, Yunhao Fu, Dong Zhao, Haowen Pan, Yuexiang Jin, Jiayue Sun, Hui Qiao, Zhenyu Guan
* [Permalink](
https://eprint.iacr.org/2025/625)
* [Download](
https://eprint.iacr.org/2025/625.pdf)
### Abstract
We propose an encrypted controller framework for linear time-invariant systems with actuator non-linearity based on fully homomorphic encryption (FHE). While some existing works explore the use of partially homomorphic encryption (PHE) in implementing linear control systems, the impacts of the non-linear behaviors of the actuators on the systems are often left unconcerned. In particular, when the inputs to the controller become too small or too large, actuators may burn out due to unstable system state oscillations. To solve this dilemma, we design and implement FHECAP, an FHE-based controller framework that can homomorphically apply non-linear functions to the actuators to rectify the system inputs. In FHECAP, we first design a novel data encoding scheme tailored for efficient gain matrix evaluation. Then, we propose a high-precision homomorphic algorithm to apply non-arithmetic piecewise function to realize the actuator normalization. In the experiments, compared with the existing state-of-the-art encrypted controllers, FHECAP achieves $4\times$--$1000\times$ reduction in computational latency. We evaluate the effectiveness of FHECAP in the real-world application of encrypted control for spacecraft rendezvous. The simulation results show that the FHECAP achieves real-time spacecraft rendezvous with negligible accuracy loss.
## 2025/626
* Title: Tree-based Quantum Carry-Save Adder
* Authors: Hyunjun Kim, Sejin Lim, Kyungbae Jang, Siyi Wang, Anubhab Baksi, Anupam Chattopadhyay, Hwajeong Seo
* [Permalink](
https://eprint.iacr.org/2025/626)
* [Download](
https://eprint.iacr.org/2025/626.pdf)
### Abstract
Quantum computing is regarded as one of the most significant upcoming advancements in computer science.
Although fully operational quantum computers have yet to be realized, they are expected to solve specific problems that are difficult to solve using classical computers.
Given the limitations of quantum computing resources, it is crucial to design compact quantum circuits for core operations, such as quantum arithmetic.
In this paper, we focus on optimizing the circuit depth of quantum multi-operand addition, which is a fundamental component in quantum implementations (as an example, SHA-2).
Building on the foundational quantum carry-save approach by Phil Gossett, we introduce a tree-based quantum carry-save adder.
Our design integrates the Wallace and Dadda trees to optimize carry handling during multi-operand additions.
To further reduce circuit depth, we utilize additional ancilla qubits for parallel operations and introduce an efficient technique for reusing these ancilla qubits.
Our tree-based carry-save adder achieves the lowest circuit depth ($T$-depth) and provides an improvement of over 82% (up to 99%) in the qubit count–circuit depth product for multi-operand addition.
Furthermore, we apply our method to multiplication, achieving the lowest circuit depth and an improvement of up to 87% in the qubit count–circuit depth product.
## 2025/627
* Title: Everlasting Fully Dynamic Group Signatures
* Authors: Yimeng He, San Ling, Khai Hanh Tang, Huaxiong Wang
* [Permalink](
https://eprint.iacr.org/2025/627)
* [Download](
https://eprint.iacr.org/2025/627.pdf)
### Abstract
Group signatures allow a user to sign anonymously on behalf of a group of users while allowing a tracing authority to trace the signer's identity in case of misuse. In Chaum and van Heyst's original model (EUROCRYPT'91), the group needs to stay fixed. Throughout various attempts, including partially dynamic group signatures and revocations, Bootle et al. (ACNS'16, J. Cryptol.) formalized the notion of fully dynamic group signatures (FDGS), enabling both enrolling and revoking users of the group. However, in their scheme, the verification process needs to take into account the latest system information, and a previously generated signature will be invalidated as soon as, for example, there is a change in the group. We therefore raise a research question: Is it possible to construct an FDGS under which the validity of a signature can survive future changes in the system information?
In this paper, we propose Everlasting Fully Dynamic Group Signatures (EFDGS) that allow signers to generate signatures that do not require verification with any specific epoch. Specifically, once the signatures are created, they are valid forever. It also guarantees that the signer can only output such a signature when she is a valid user of the system. We realize the above new model by constructing a plausibly post-quantum standard-lattice-based EFDGS.
## 2025/628
* Title: Improving the Masked Division for the FALCON Signature
* Authors: Pierre-Augustin Berthet, Justine Paillet, Cédric Tavernier, Lilian Bossuet, Brice Colombier
* [Permalink](
https://eprint.iacr.org/2025/628)
* [Download](
https://eprint.iacr.org/2025/628.pdf)
### Abstract
FALCON is a post-quantum signature selected by the National Institute of Standards and Technology (NIST). Although its side-channel resilience has been studied and a masking countermeasure proposed, the division is a major performance bottleneck. This work proposes a different approach to the masked FALCON division. We use the Newton method and a convergent sequence to approximate this operation. The performance of the masked division is improved by a factor 6.7 for two shares and 6.98 for three shares. For the Gaussian sampler, the improvements are of a factor 1.45 for two shares and 1.43 for three shares. Formal security proofs using the MIMO-SNI criteria are also provided.
## 2025/629
* Title: Audience Injection Attacks: A New Class of Attacks on Web-Based Authorization and Authentication Standards
* Authors: Pedram Hosseyni, Ralf Kuesters, Tim Würtele
* [Permalink](
https://eprint.iacr.org/2025/629)
* [Download](
https://eprint.iacr.org/2025/629.pdf)
### Abstract
We introduce audience injection attacks, a novel class of vulnerabilities that impact widely used Web-based authentication and authorization protocols, including OAuth 2.0, OpenID Connect, FAPI, CIBA, the Device Authorization Grant, and various well-established extensions, such as Pushed Authorization Requests, Token Revocation, Token Introspection, and their numerous combinations.
These protocols underpin services for billions of users across diverse ecosystems worldwide, spanning low-risk applications like social logins to high-risk domains such as open banking, insurance, and healthcare.
Audience injection attacks exploit a critical weakness in a core security mechanism of these protocols - the handling of so-called audiences in signature-based client authentication mechanisms. This vulnerability allows attackers to compromise fundamental security objectives whenever these mechanisms are utilized across two or more server endpoints. They enable the attacker to impersonate users and gain unauthorized access to their resources, even in high-security protocol families specifically designed for sensitive applications.
We responsibly disclosed these vulnerabilities to the relevant standardization bodies, which recognized their severity.
In collaboration with these organizations, we developed fixes and supported a coordinated response, leading to an ongoing effort to update a dozen of standards, numerous major implementations, and far-reaching ecosystems.
## 2025/630
* Title: Charge Your Clients: Payable Secure Computation and Its Applications
* Authors: Cong Zhang, Liqiang Peng, Weiran Liu, Shuaishuai Li, Meng Hao, Lei Zhang, Dongdai Lin
* [Permalink](
https://eprint.iacr.org/2025/630)
* [Download](
https://eprint.iacr.org/2025/630.pdf)
### Abstract
The online realm has witnessed a surge in the buying and selling of data, prompting the emergence of dedicated data marketplaces. These platforms cater to servers (sellers), enabling them to set prices for access to their data, and clients (buyers), who can subsequently purchase these data, thereby streamlining and facilitating such transactions. However, the current data market is primarily confronted with the following issues. Firstly, they fail to protect client privacy, presupposing that clients submit their queries in plaintext. Secondly, these models are susceptible to being impacted by malicious client behavior, for example, enabling clients to potentially engage in arbitrage activities.
To address the aforementioned issues, we propose payable secure computation, a novel secure computation paradigm specifically designed for data pricing scenarios. It grants the server the ability to securely procure essential pricing information while protecting the privacy of client queries. Additionally, it fortifies the server's privacy against potential malicious client activities. As specific applications, we have devised customized payable protocols for two distinct secure computation scenarios: Keyword Private Information Retrieval (KPIR) and Private Set Intersection (PSI).
We implement our two payable protocols and compare them with the state-of-the-art related protocols that do not support pricing as a baseline. Since our payable protocols are more powerful in the data pricing setting, the experiment results show that they do not introduce much overhead over the baseline protocols.
Our payable KPIR achieves the same online cost as baseline, while the setup is about $1.3-1.6\times$ slower than it. Our payable PSI needs about $2\times$ more communication cost than that of baseline protocol, while the runtime is $1.5-3.2\times$ slower than it depending on the network setting.
## 2025/631
* Title: Dyna-hinTS: Silent Threshold Signatures for Dynamic Committees
* Authors: Aniket Kate, Pratyay Mukherjee, Samipa Samanta, Pratik Sarkar
* [Permalink](
https://eprint.iacr.org/2025/631)
* [Download](
https://eprint.iacr.org/2025/631.pdf)
### Abstract
The works of Garg et al. [S&P'24] (aka hinTS) and Das et al. [CCS'23] introduced the notion of silent threshold signatures (STS) - where a set of signers silently perform local computation to generate a public verification key. To sign a message, any set of $t$ signers sign the message non-interactively and these are aggregated into a constant-sized signature. This paradigm avoids performing expensive Distributed Key Generation procedure for each set of signers while keeping the public verification key constant-sized.
In this work, we propose the notion of committee-based silent threshold signature (c-STS) scheme. In a c-STS scheme, a set of signers initially perform a one-time setup to generate the verification key, and then a subset of signers are randomly chosen for an epoch to perform the threshold signing while the other signers are not authorized to sign during that epoch. This captures existing systems like Ethereum Altair and Dfinity where only a specific committee is authorized to sign in a designated epoch. The existing STS schemes cannot be extended to the committee setting because the signature verification only attests to the number of signing parties, not which committee they belong to.
So, we upgrade hinTS to the committee setting by proposing Dyna-hinTS. It is the $first$ c-STS scheme and it requires a one-time silent setup and generates a one-time public verification key that does not vary with the committee. Assuming a set of 1024 signers (with corrupt 682 signers), hinTS generates an aggregated signature in 1.7s whereas Dyna-hinTS generates it in $0.35$s within a committee of $80$ signers. This yields a $4.9\times$ improvement over hinTS for signature generation at the cost of increasing signature verification time by $4\%$ over hinTS. Dyna-hinTS supports general access structure, weighted signatures and improves existing multiverse threshold signatures.
## 2025/632
* Title: On breaking McEliece keys using brute force
* Authors: Lorenz Panny
* [Permalink](
https://eprint.iacr.org/2025/632)
* [Download](
https://eprint.iacr.org/2025/632.pdf)
### Abstract
In the McEliece public-key encryption scheme, a private key is almost always not determined uniquely by its associated public key. This paper gives a structural characterization of equivalent private keys, generalizing a result known for the more approachable special case $\lvert L\rvert=q$.
These equivalences reduce the cost estimate for a simple private-key search using the support-splitting algorithm (SSA) by a polynomial but practically very substantial factor.
We provide an optimized software implementation of the SSA for this kind of key search and demonstrate its capabilities in practice by solving a key-recovery challenge with a naïve a‑priori cost estimate of $2^{83}$ bit operations in just ${\approx}\,1400$ core days, testing ${\approx}\,9400$ private-key candidates per core and second in the process.
We stress that the speedup from those equivalences is merely polynomial and does not indicate any weakness in realistic instantiations of the McEliece cryptosystem, whose parameter choices are primarily constrained by decoding attacks rather than ludicrously more expensive key-recovery attacks.
## 2025/633
* Title: Hybrid-query bounds with partial input control - framework and application to tight M-eTCR
* Authors: Andreas Hülsing, Mikhail Kudinov, Christian Majenz
* [Permalink](
https://eprint.iacr.org/2025/633)
* [Download](
https://eprint.iacr.org/2025/633.pdf)
### Abstract
In this paper, we present an improved framework for proving query bounds in the Quantum Random Oracle Model (QROM) for algorithms with both quantum and classical query interfaces, where the classical input is partially controlled by the adversary. By extending existing techniques, we develop a method to bound the progress an adversary can make with such partial-control classical queries. While this framework is applicable to different hash function properties, we decided to demonstrate the impact of the new techniques by giving an analysis of the multi-target extended target collision resistance property (m-eTCR). This new approach allows us to achieve an improved bound that significantly reduces the required function key size. Our proof is tight in terms of query complexity and has significant implications for cryptographic applications, especially for signature schemes in the hash & sign paradigm, enabling more efficient instantiations with reduced salt sizes and smaller signature lengths. For an example of multiple signatures aggregation, we achieve a signature size of 30 kB smaller.
## 2025/634
* Title: Cryptography based on 2D Ray Tracing
* Authors: Sneha Mohanty, Christian Schindelhauer
* [Permalink](
https://eprint.iacr.org/2025/634)
* [Download](
https://eprint.iacr.org/2025/634.pdf)
### Abstract
We introduce a novel symmetric key cryptographic scheme involving a light ray's interaction with a 2D cartesian coordinate setup, several smaller boxes within this setup, of either reflection or refraction type and $1^{st}$, $2^{nd}$ or $3^{rd}$ degree polynomial curves inside each of these smaller boxes. We also incorporate boolean logic gates of types XOR, NOT-Shift and Permutation which get applied to the light ray after each interaction with a reflecting or refracting polynomial curve. This alternating interaction between Optical gates (polynomial curves) and Non-optical gates creates a complex and secure cryptographic system. Furthermore, we design and launch customized attacks on our cryptographic system and discuss the robustness of it against these.
## 2025/635
* Title: Towards Scalable YOSO MPC via Packed Secret-Sharing
* Authors: Daniel Escudero, Elisaweta Masserova, Antigoni Polychroniadou
* [Permalink](
https://eprint.iacr.org/2025/635)
* [Download](
https://eprint.iacr.org/2025/635.pdf)
### Abstract
The YOSO (You Only Speak Once) model, introduced by Gentry et al. (CRYPTO 2021), helps to achieve strong security guarantees in cryptographic protocols for distributed settings, like blockchains, with large number of parties. YOSO protocols typically employ smaller anonymous committees to execute individual rounds of the protocol instead of having all parties execute the entire protocol. After completing their tasks, parties encrypt protocol messages for the next anonymous committee and erase their internal state before publishing ciphertexts, thereby enhancing security in dynamically changing environments.
In this work, we consider the problem of secure multi-party computation (MPC), a fundamental problem in cryptography and distributed computing. We assume honest majority among the committee members, and work in the online-offline, i.e., preprocessing, setting.
In this context, we present the first YOSO MPC protocol where efficiency---measured as communication complexity---improves as the number of parties increases. Specifically, for $0<\epsilon<1/2$ and an adversary corrupting $t<n(\frac{1}{2}-\epsilon)$ out of $n$ parties, our MPC protocol exhibits enhanced scalability as $n$ increases, where the online phase communication becomes independent of $n$.
Prior YOSO MPC protocols considered $t$ as large as $(n-1)/2$, but a significant hurdle persisted in obtaining YOSO MPC with communication that does not scale linearly with the number of committee members, a challenge that is exagerbated when the committee size was large per YOSO's requirements.
We show that, by considering a small ``gap'' of $\epsilon>0$, the sizes of the committees are only marginally increased, while online communication is significantly reduced.
Furthermore, we explicitly consider fail-stop adversaries, i.e., honest participants who may inadvertently fail due to reasons such as denial of service or software/hardware errors. In prior YOSO work, these adversaries were grouped with fully malicious parties. Adding explicit support for them allows us to achieve even better scalability.
## 2025/636
* Title: Impossible Differential Attack on SAND-64
* Authors: Nobuyuki Sugio
* [Permalink](
https://eprint.iacr.org/2025/636)
* [Download](
https://eprint.iacr.org/2025/636.pdf)
### Abstract
SAND is an AND-RX-based lightweight block cipher proposed by Chen et al. There are two variants of SAND, namely SAND-64 and SAND-128, due to structural differences. In this paper, we search for impossible differential distinguishers of SAND-64 using the Constraint Programming (CP) and reveal 56 types of impossible differential distinguishers up to 11 rounds. Furthermore, we demonstrate a key recovery attack on 17-round SAND-64. The complexities for the attack require $2^{56}$ data, $2^{127}$ encryptions, and $2^{60}$ bytes of memory, respectively. Although this result currently achieves the best attack on round-reduced SAND-64, this attack does not threaten the security of SAND-64 against impossible differential attack.
## 2025/637
* Title: A Study of Blockchain Consensus Protocols
* Authors: Shymaa M. Arafat
* [Permalink](
https://eprint.iacr.org/2025/637)
* [Download](
https://eprint.iacr.org/2025/637.pdf)
### Abstract
When Nakamoto invented Bitcoin, the first generation of cryptocurrencies followed it in applying POW (Proof of Work) consensus mechanism; due to its excessive energy consumption and heavy carbon footprints, new innovations evolved like Proof of Space, POS (Proof of Stake), and a lot more with many variants for each. Furthermore, the emergence of more blockchain applications and kinds beyond just cryptocurrencies needed more consensus mechanisms that is optimized to fit requirements of each application or blockchain kind; examples range from IoT (Internet of Things) blockchains for sustainability applications that often use variants of BFT (Byzantine Fault Tolerance) algorithm, and consensus needed to relay transactions and/or assets between different blockchains in interoperability solutions. Previous studies concentrated on surveying and/or proposing different blockchain consensus rules, on a specific consensus issue like attacks, randomization, or on deriving theoretical results. Starting from discussing most important theoretical results, this paper tries to gather and organize all significant existing material about consensus in the blockchain world explaining design challenges, tradeoffs and research areas. We realize that the topic could fit for a complete textbook, so we summarize the basic concepts and support with tables and appendices. Then we highlight some case examples from interoperability solutions to show how flexible and wide the design space is to fit both general and special purpose systems. The aim is to provide researchers with a comprehensive overview of the topic, along with the links to go deeper into every detail.
## 2025/638
* Title: Round-Efficient Adaptively Secure Threshold Signatures with Rewinding
* Authors: Yanbo Chen
* [Permalink](
https://eprint.iacr.org/2025/638)
* [Download](
https://eprint.iacr.org/2025/638.pdf)
### Abstract
A threshold signature scheme allows distributing a signing key to $n$ users, such that any $t$ of them can jointly sign, but any $t-1$ cannot. It is desirable to prove \emph{adaptive security} of threshold signature schemes, which considers adversaries that can adaptively corrupt honest users even after interacting with them. For a class of signatures that relies on security proofs with rewinding, such as Schnorr signatures, proving adaptive security entails significant challenges.
This work proposes two threshold signature schemes that are provably adaptively secure with rewinding proofs. Our proofs are solely in the random oracle model (ROM), without relying on the algebraic group model (AGM).
- We give a 3-round scheme based on the algebraic one-more discrete logarithm (AOMDL) assumption. The scheme outputs a standard Schnorr signature.
- We give a 2-round scheme based on the DL assumption. Signatures output by the scheme contain one more scalar than a Schnorr signature.
We follow the recent work by Katsumata, Reichle, and Takemure (Crypto 2024) that proposed the first threshold signature scheme with a rewinding proof of full adaptive security. Their scheme is a 5-round threshold Schnorr scheme based on the DL assumption. Our results significantly improve the round complexity.
Katsumata et al.'s protocol can be viewed as applying a masking technique to Sparkle, a threshold Schnorr signature scheme by Crites, Komlo, and Maller (Crypto 2023). This work shows wider applications of the masking technique. Our first scheme is obtained by masking FROST, a threshold Schnorr protocol by Komlo and Goldberg (SAC 2020). The second scheme is obtained by masking a threshold version of HBMS, a multi-signature scheme by Bellare and Dai (Asiacrypt 2021).
Katsumata et al. masked Sparkle at the cost of 2 additional rounds. Our main insight is that this cost varies across schemes, especially depending on how to simulate signing in the security proofs. The cost is 1 extra round for our first scheme, and is 0 for our second scheme.
## 2025/639
* Title: Cryptomania v.s. Minicrypt in a Quantum World
* Authors: Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu
* [Permalink](
https://eprint.iacr.org/2025/639)
* [Download](
https://eprint.iacr.org/2025/639.pdf)
### Abstract
We prove that it is impossible to construct perfect-complete quantum public-key encryption (QPKE) with classical keys from quantumly secure one-way functions (OWFs) in a black-box manner, resolving a long-standing open question in quantum cryptography.
Specifically, in the quantum random oracle model (QROM), no perfect-complete QPKE scheme with classical keys, and classical/quantum ciphertext can be secure. This improves the previous works which require either unproven conjectures or imposed restrictions on key generation algorithms. This impossibility even extends to QPKE with quantum public key if the public key can be uniquely determined by the secret key, and thus is tight to all existing QPKE constructions.
## 2025/640
* Title: Multi-Party Private Set Operations from Predicative Zero-Sharing
* Authors: Minglang Dong, Yu Chen, Cong Zhang, Yujie Bai, Yang Cao
* [Permalink](
https://eprint.iacr.org/2025/640)
* [Download](
https://eprint.iacr.org/2025/640.pdf)
### Abstract
Typical protocols in the multi-party private set operations (MPSO) setting enable $m > 2$ parties to perform certain secure computation on the intersection or union of their private sets, realizing a very limited range of MPSO functionalities. Most works in this field focus on just one or two specific functionalities, resulting in a large variety of isolated schemes and a lack of a unified framework in MPSO research. In this work, we present an MPSO framework, which allows $m$ parties, each holding a set, to securely compute any set formulas (arbitrary compositions of a finite number of binary set operations, including intersection, union and difference) on their private sets. Our framework is highly versatile and can be instantiated to accommodate a broad spectrum of MPSO functionalities. To the best of our knowledge, this is the first framework to achieve such a level of flexibility and generality in MPSO, without relying on generic secure multi-party computation (MPC) techniques.
Our framework exhibits favorable theoretical and practical performance. The computation and communication complexity scale linearly with the set size $n$, and it achieves optimal complexity that is on par with the naive solution for widely used functionalities, such as multi-party private set intersection (MPSI), MPSI with cardinality output (MPSI-card), and MPSI with cardinality and sum (MPSI-card-sum), in the standard semi-honest model. Furthermore, the instantiations of our framework mainly from symmetric-key techniques yield efficient protocols for MPSI, MPSI-card, MPSI-card-sum, and multi-party private set union (MPSU), with online performance surpassing or matching the state of the art.
At the technical core of our framework is a newly introduced primitive called predicative zero-sharing. This primitive captures the universality of a number of MPC protocols and is composable. We believe it may be of independent interest.
## 2025/641
* Title: Scalable Non-Fungible Tokens on Bitcoin
* Authors: Jordi Herrera-Joancomartí, Cristina Pérez-Solà, Toni Mateos
* [Permalink](
https://eprint.iacr.org/2025/641)
* [Download](
https://eprint.iacr.org/2025/641.pdf)
### Abstract
This paper presents a protocol for scaling the creation, management, and trading of non-fungible tokens (NFTs) on Bitcoin by extending bridgeless minting patterns previously used on other blockchains. The protocol leverages on-chain Bitcoin data to handle all aspects of token ownership, including trading, while integrating a secondary consensus system for minting and optionally modifying token metadata. To minimize its on-chain footprint, the protocol utilizes the OP_RETURN mechanism for ownership records, while complementary NFT-related actions are stored on the LAOS blockchain. All data remains permanently on-chain, with no reliance on bridges or third-party operators.
## 2025/642
* Title: A Meta-Complexity Characterization of Quantum Cryptography
* Authors: Bruno P. Cavalar, Eli Goldin, Matthew Gray, Peter Hall
* [Permalink](
https://eprint.iacr.org/2025/642)
* [Download](
https://eprint.iacr.org/2025/642.pdf)
### Abstract
We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in $\mathbf{NP}$ or $\mathbf{QMA}$, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.
## 2025/643
* Title: Obfuscation for Deep Neural Networks against Model Extraction: Attack Taxonomy and Defense Optimization
* Authors: Yulian Sun, Vedant Bonde, Li Duan, Yong Li
* [Permalink](
https://eprint.iacr.org/2025/643)
* [Download](
https://eprint.iacr.org/2025/643.pdf)
### Abstract
Well-trained deep neural networks (DNN), including large
language models (LLM), are valuable intellectual property assets. To defend against model extraction attacks, one of the major ideas proposed in a large body of previous research is obfuscation: splitting the original DNN and storing the components separately. However, systematically analyzing the methods’ security against various attacks and optimizing the efficiency of defenses are still challenging. In this paper, We propose a taxonomy of model-based extraction attacks, which enables us to identify vulnerabilities of several existing obfuscation methods. We also propose an extremely efficient model obfuscation method called O2Splitter using trusted execution environment (TEE). The secrets we store in TEE have O(1)-size, i.e., independent of model size. Although O2Splitter relies on a pseudo-random function to provide a quantifiable guarantee for protection and noise compression, it does not need any complicated training or filtering of the weights. Our comprehensive experiments show that O2Splitter can mitigate norm-clipping and fine-tuning attacks. Even for
small noise (ϵ = 50), the accuracy of the obfuscated model is close to
random guess, and the tested attacks cannot extract a model with comparable accuracy. In addition, the empirical results also shed light on discovering the relation between DP parameters in obfuscation and the risks of concrete extraction attacks.
## 2025/644
* Title: Attacking at non-harmonic frequencies in screaming-channel attacks
* Authors: Jeremy Guillaume, Maxime Pelcat, Amor Nafkha, Ruben Salvador
* [Permalink](
https://eprint.iacr.org/2025/644)
* [Download](
https://eprint.iacr.org/2025/644.pdf)
### Abstract
Screaming-channel attacks enable Electromagnetic (EM) Side-Channel Attacks (SCAs) at larger distances due to higher EM leakage energies than traditional SCAs, relaxing the requirement of close access to the victim. This attack can be mounted on devices integrating Radio Frequency (RF) modules on the same die as digital circuits, where the RF can unintentionally capture, modulate, amplify, and transmit the leakage along with legitimate signals. Leakage results from digital switching activity, so the hypothesis of previous works was that this leakage would appear at multiples of the digital clock frequency, i.e.., harmonics. This work demonstrates that compromising signals appear not only at the harmonics and that leakage at non-harmonics can be exploited for successful attacks. Indeed, the transformations undergone by the leaked signal are complex due to propagation effects through the substrate and power and ground planes, so the leakage also appears at other frequencies. We first propose two methodologies to locate frequencies that contain leakage and demonstrate that it appears at non-harmonic frequencies. Then, our experimental results show that screaming-channel attacks at non-harmonic frequencies can be as successful as at harmonics when retrieving a 16-byte AES key. As the RF spectrum is polluted by interfering signals, we run experiments and show successful attacks in a more realistic, noisy environment where harmonic frequencies are contaminated by multi-path fading and interference. These attacks at non-harmonic frequencies increase the attack surface by providing attackers with an increased number of potential frequencies where attacks can succeed.
## 2025/645
* Title: GIGA Protocol: Unlocking Trustless Parallel Computation in Blockchains
* Authors: Alberto Garoffolo, Dmytro Kaidalov, Roman Oliynykov, Daniele Di Tullio, Mariia Rodinko
* [Permalink](
https://eprint.iacr.org/2025/645)
* [Download](
https://eprint.iacr.org/2025/645.pdf)
### Abstract
The scalability of modern decentralized blockchain systems is constrained by the requirement that the participating nodes execute the entire chains transactions without the ability to delegate the verification workload across multiple actors trustlessly. This is further limited by the need for sequential transaction execution and repeated block validation, where each node must re-execute all transactions before accepting blocks, also leading to delayed broadcasting in many architectures.
Consequently, throughput is limited by the capacity of individual nodes, significantly preventing scalability.
In this paper, we introduce GIGA, a SNARK-based protocol that enables trustless parallel execution of transactions, processing non-conflicting operations concurrently, while preserving security guarantees and state consistency. The protocol organizes transactions into non-conflicting batches which are executed and proven in parallel, distributing execution across multiple decentralized entities. These batch proofs are recursively aggregated into a single succinct proof that validates the entire block.
As a result, the protocol both distributes the execution workload and removes redundant re-execution from the network, significantly improving blockchain throughput while not affecting decentralization.
Performance estimates demonstrate that, under the same system assumptions (e.g., consensus, networking, and virtual machine architecture) and under high degrees of transaction parallelism (i.e., when most transactions operate on disjoint parts of the state), our protocol may achieve over a 10000x throughput improvement compared to popular blockchain architectures that use sequential execution models, and over a 500x improvement compared to blockchain architectures employing intra-node parallelization schemes.
Furthermore, our protocol enables a significant increase in transaction computational complexity, unlocking a wide range of use cases that were previously unfeasible on traditional blockchain architectures due to the limited on-chain computational capacity.
Additionally, we propose a reward mechanism that ensures the economic sustainability of the proving network, dynamically adjusting to computational demand while fostering competition among provers based on cost-efficiency and reliability.
## 2025/646
* Title: Secret-Key PIR from Random Linear Codes
* Authors: Caicai Chen, Yuval Ishai, Tamer Mour, Alon Rosen
* [Permalink](
https://eprint.iacr.org/2025/646)
* [Download](
https://eprint.iacr.org/2025/646.pdf)
### Abstract
Private information retrieval (PIR) allows to privately read a chosen bit from an $N$-bit database $x$ with $o(N)$ bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing $x$ into an encoded database $\hat x$, it suffices to access only $polylog(N)$ bits of $\hat x$ per query. This requires $|\hat x|\ge N\cdot polylog(N)$, and prohibitively large server circuit size.
We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding $\hat x$ depends on a client's short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with $O(N^\epsilon)$ communication, for any constant $\epsilon>0$, from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR.
Under a new conjecture related to the hardness of learning a hidden linear subspace of $\mathbb{F}_2^n$ with noise, we construct sk-PIR with similar communication and encoding size $|\hat x|=(1+\epsilon)\cdot N$ in which the server is implemented by a Boolean circuit of size $(4+\epsilon)\cdot N$. This is the first candidate PIR scheme with such a circuit complexity.
## 2025/647
* Title: Anamorphic Voting: Ballot Freedom Against Dishonest Authorities
* Authors: Rosario Giustolisi, Mohammadamin Rakeei, Gabriele Lenzini
* [Permalink](
https://eprint.iacr.org/2025/647)
* [Download](
https://eprint.iacr.org/2025/647.pdf)
### Abstract
Electronic voting schemes typically ensure ballot privacy by
assuming that the decryption key is distributed among tallying authorities, preventing any single authority from decrypting a voter’s ballot.
However, this assumption may fail in a fully dishonest environment where
all tallying authorities collude to break ballot privacy.
In this work, we introduce the notion of anamorphic voting, which enables voters to convey their true voting intention to an auditor while
casting an (apparently) regular ballot. We present new cryptographic
techniques demonstrating that several existing voting schemes can support anamorphic voting.
## 2025/648
* Title: HQC Beyond the BSC: Towards Error Structure-Aware Decoding
* Authors: Marco Baldi, Sebastian Bitzer, Nicholas Lilla, Paolo Santini
* [Permalink](
https://eprint.iacr.org/2025/648)
* [Download](
https://eprint.iacr.org/2025/648.pdf)
### Abstract
In Hamming Quasi-Cyclic (HQC), one of the finalists in the NIST competition for the standardization of post-quantum cryptography, decryption relies on decoding a noisy codeword through a public error-correcting code. The noise vector has a special form that depends on the secret key (a pair of sparse polynomials). However, the decoder, which is currently employed in HQC, is agnostic to the secret key, operating under the assumption that the error arises from a Binary Symmetric Channel (BSC). In this paper, we demonstrate that this special noise structure can instead be leveraged to develop more powerful decoding strategies.
We first study the problem from a coding-theoretic perspective. The current code design, which admits a non-zero decryption failure rate, is close to optimal in the setting of a decoder that is agnostic to the error structure. We show that there are code-decoder pairs with a considerably shorter code length that can guarantee unique decoding by taking the error structure into account. This result is non-constructive, i.e., we do not provide an explicit code construction and it remains open whether efficient decoding is possible. Nevertheless, it highlights the potential that can be tapped by taking the error structure into account.
We then argue that, in practice, the matter of decoding in HQC can be related to solving an instance of the noisy syndrome decoding problem, in which the parity-check matrix is constituted by the polynomials in the secret key. We show that, using decoders for Low-Density Parity-Check (LDPC) and Moderate-Density Parity-Check (MDPC) codes, one can significantly reduce the entity of the noise and, de facto, also the Decoding Failure Rate (DFR) of the HQC decoder.
This preliminary study leaves some open questions and problems. While it shows that decoding in HQC can be improved, the modeling of the DFR gets more complicated: even for the basic decoder we propose in this paper, we have not been able to devise a reliable DFR model. This is likely due to the fact that the decoder structure resembles the iterative nature of LDPC/MDPC decoders, for which devising a reliable DFR estimation is a well-known difficult problem.
## 2025/649
* Title: Guaranteed Termination Asynchronous Complete Secret Sharing with Lower Communication and Optimal Resilience
* Authors: Ying Cai, Chengyi Qin, Mingqiang Wang
* [Permalink](
https://eprint.iacr.org/2025/649)
* [Download](
https://eprint.iacr.org/2025/649.pdf)
### Abstract
Asynchronous Complete Secret Sharing (ACSS) is a foundational module for asynchronous networks, playing a critical role in cryptography. It is essential for Asynchronous Secure Multi-Party Computation (AMPC) and, with termination, is widely applied in Validated Asynchronous Byzantine Agreement (VABA) and Asynchronous Distributed Key Generation (ADKG) to support secure distributed systems.
Currently, there are relatively few statistical secure ACSS protocols that can guarantee termination, and their communication complexity is relatively high. To reduce communication complexity, we propose a new multi-receiver signature scheme, ARICP, which supports linear operations on signatures. Leveraging the ARICP scheme and the properties of symmetric polynomials, we propose an ACSS protocol that ensures termination and optimal resilience ($t < n / 3$) with $\mathcal{O}(n^{2}\kappa$) bits per sharing. Compared with the best-known result of ACSS protocols that guarantee termination [CP23], the amortized communication complexity of our protocol is reduced by a factor of $\mathcal{O}(n)$.
## 2025/650
* Title: ADC-BE: Optimizing Worst-Case Bandwidth in Broadcast Encryption with Boolean Functions
* Authors: Yadi Zhong
* [Permalink](
https://eprint.iacr.org/2025/650)
* [Download](
https://eprint.iacr.org/2025/650.pdf)
### Abstract
Recently, Dupin and Abelard proposed a broadcast encryption scheme which outperforms the Complete Subtree-based and Subset Difference broadcast encryption in terms of encryption cost and bandwidth requirement. However, Dupin and Abelard acknowledge that the worst-case bound for bandwidth requirement of Complete Subtree approach can be reached in their scheme as well. In this paper, we answer the call to further reduce this bandwidth bottleneck. We first provide concrete analysis to show how this worst-case upper-bound is reached from concrete Boolean functions. Then we present two improved broadcast encryption schemes to significantly reduce this worst-case bandwidth consumption for further optimization of Dupin and Abelard’s technique. Our proposed approach ADC-BE, composed of two algorithms, AD-BE and AC-BE, can significantly optimize this worst-case complexity from n/2 down to 1 for a system of n users. This is efficient especially for large number of users in the system. Our proposed schemes combines the algebraic normal form, disjunctive normal form, and conjunctive normal form to optimize a Boolean function to its minimized representation. In addition, our approaches can be made secure against quantum adversaries and are therefore post-quantum, where both algorithms AD-BE and AC-BE require minimal assumptions based on existence of one-way function.
## 2025/651
* Title: Low-Latency Bootstrapping for CKKS using Roots of Unity
* Authors: Jean-Sébastien Coron, Robin Köstler
* [Permalink](
https://eprint.iacr.org/2025/651)
* [Download](
https://eprint.iacr.org/2025/651.pdf)
### Abstract
We introduce a new bootstrapping equation for the CKKS homomorphic encryption scheme of approximate numbers. The original bootstrapping approach for CKKS consists in homomorphically evaluating a polynomial that approximates the modular reduction modulo q. In contrast, our new bootstrapping equation directly embeds the additive group modulo q into the complex roots of unity, which can be evaluated natively in the CKKS scheme. Due to its reduced multiplicative depth, our new bootstrapping equation achieves a 7x latency improvement for a single slot compared to the original CKKS bootstrapping, though it scales less efficiently when applied to a larger number of slots.
## 2025/652
* Title: MultiCent: Secure and Scalable Centrality Measures on Multilayer Graphs
* Authors: Andreas Brüggemann, Nishat Koti, Varsha Bhat Kukkala, Thomas Schneider
* [Permalink](
https://eprint.iacr.org/2025/652)
* [Download](
https://eprint.iacr.org/2025/652.pdf)
### Abstract
As real-world networks such as social networks and computer networks are often complex and distributed, modeling them as multilayer graphs is gaining popularity. For instance, when studying social interactions across platforms like LinkedIn, Facebook, TikTok, and Bluesky, users may be connected on several of these platforms. To identify important nodes/users, the platforms might wish to analyze user interactions using, e.g., centrality measures when accounting for connections across all platforms. That raises the challenge for platforms to perform such computation while simultaneously protecting their user data to shelter their own business as well as uphold data protection laws. This necessitates designing solutions that allow for performing secure
computation on a multilayer graph which is distributed among mutually distrusting parties while keeping each party's data hidden.
The work of Asharov et al. (WWW'17) addresses this problem by designing secure solutions for centrality measures that involve computing the truncated Katz score and reach score on multilayer graphs. However, we identify several limitations in that work which render the solution inefficient or even unfeasible for realistic networks with significantly more than 10k nodes. We address these limitations by designing secure solutions that are significantly more efficient and scalable. In more detail, given that real-world graphs are known to be sparse, our solutions move away from an expensive matrix-based representation to a more efficient list-based representation. We design novel, secure, and efficient solutions for computing centrality measures and prove their correctness. Our solutions drastically reduce the asymptotic complexity from the prohibitive $\mathcal{O}(|\mathsf{V}|^2)$ even for the fastest solution by Asharov et al. down to $\mathcal{O}(|\mathsf{V}|\log |\mathsf{V}|)$, for $|\mathsf{V}|$ nodes. To design our solutions, we extend upon the secure graph computation framework of Koti et al. (CCS'24), providing a novel framework with improved capabilities in multiple directions. Finally, we provide an end-to-end implementation of our secure graph analysis framework and establish concrete efficiency improvements over prior work, observing several orders of magnitude improvement.
## 2025/653
* Title: Fission: Distributed Privacy-Preserving Large Language Model Inference
* Authors: Mehmet Ugurbil, Dimitris Mouris, Manuel B. Santos, José Cabrero-Holgueras, Miguel de Vega, Shubho Sengupta
* [Permalink](
https://eprint.iacr.org/2025/653)
* [Download](
https://eprint.iacr.org/2025/653.pdf)
### Abstract
The increased popularity of large language models (LLMs) raises serious privacy concerns, where users' private queries are sent to untrusted servers. Many cryptographic techniques have been proposed to provide privacy, such as secure multiparty computation (MPC), which enables the evaluation of LLMs directly on private data. However, cryptographic techniques have been deemed impractical as they introduce large communication and computation. On the other hand, many obfuscation techniques have been proposed, such as split inference, where part of the model is evaluated on edge devices to hide the input data from untrusted servers, but these methods provide limited privacy guarantees.
We propose Fission, a privacy-preserving framework that improves latency while providing strong privacy guarantees. Fission utilizes an MPC network for linear computations, while nonlinearities are computed on a separate evaluator network that receives shuffled values in the clear and returns nonlinear functions evaluated at these values back to the MPC network. As a result, each evaluator only gets access to parts of the shuffled data, while the model weights remain private. We evaluate fission on a wide set of LLMs and compare it against prior works. Fission results in up to eight times faster inference and eight times reduced bandwidth compared to prior works while retaining high accuracy. Finally, we construct an attack on obfuscation techniques from related works that show significant information leakage, and we demonstrate how Fission enhances privacy.
## 2025/654
* Title: ECDSA Cracking Methods
* Authors: William J Buchanan, Jamie Gilchrist, Keir Finlow-Bates
* [Permalink](
https://eprint.iacr.org/2025/654)
* [Download](
https://eprint.iacr.org/2025/654.pdf)
### Abstract
The ECDSA (Elliptic Curve Digital Signature Algorithm) is used in many blockchain networks for digital signatures. This includes the Bitcoin and the Ethereum blockchains. While it has good performance levels and as strong current security, it should be handled with care. This care typically relates to the usage of the nonce value which is used to create the signature. This paper outlines the methods that can be used to break ECDSA signatures, including revealed nonces, weak nonce choice, nonce reuse, two keys and shared nonces, and fault attack.
## 2025/655
* Title: Taking AI-Based Side-Channel Attacks to a New Dimension
* Authors: Lucas David Meier, Felipe Valencia, Cristian-Alexandru Botocan, Damian Vizár
* [Permalink](
https://eprint.iacr.org/2025/655)
* [Download](
https://eprint.iacr.org/2025/655.pdf)
### Abstract
This paper revisits the Hamming Weight (HW) labelling function for machine learning assisted side channel attacks. Contrary to what has been suggested by previous works, our investigation shows that, when paired with modern deep learning architectures, appropriate pre-processing and normalization techniques; it can perform as well as the popular identity labelling functions and sometimes even beat it. In fact, we hereby introduce a new machine learning method, dubbed, that helps solve the class imbalance problem associated to HW, while significantly improving the performance of unprofiled attacks. We additionally release our new, easy to use python package that we used in our experiments, implementing a broad variety of machine learning driven side channel attacks as open source, along with a new dataset AES_nRF, acquired on the nRF52840 SoC.
## 2025/656
* Title: Unbounded Multi-Hop Proxy Re-Encryption with HRA Security: An LWE-Based Optimization
* Authors: Xiaohan Wan, Yang Wang, Haiyang Xue, Mingqiang Wang
* [Permalink](
https://eprint.iacr.org/2025/656)
* [Download](
https://eprint.iacr.org/2025/656.pdf)
### Abstract
Proxy re-encryption (PRE) schemes enable a semi-honest proxy to transform a ciphertext of one user $i$ to another user $j$ while preserving the privacy of the underlying message. Multi-hop PRE schemes allow a legal ciphertext to undergo multiple transformations, but for lattice-based multi-hop PREs, the number of transformations is typically bounded due to the increase of error terms. Recently, Zhao et al. (Esorics 2024) introduced a lattice-based unbounded multi-hop (homomorphic) PRE scheme that supports an unbounded number of hops. Nevertheless, their scheme only achieves the selective CPA security. In contrast, Fuchsbauer et al. (PKC 2019) proposed a generic framework for constructing HRA-secure unbounded multi-hop PRE schemes from FHE. Despite this, when instantiated with state-of-the-art FHEW-like schemes, the overall key size and efficiency remain unsatisfactory.
In this paper, we present a lattice-based unbounded multi-hop PRE scheme with the stronger adaptive HRA security (i.e. security against honest re-encryption attacks), which is more suitable for practical applications. Our scheme features an optimized re-encryption process based on the FHEW-like blind rotation, which resolves the incompatibility between the noise flooding technique and Fuchsbauer et al. 's framework when instantiated with FHEW-like schemes. This results in reduced storage requirements for public keys and offers higher efficiency. Moreover, our optimized unbounded multi-hop PRE scheme can be modified to an unbounded homomorphic PRE, a scheme allowing for arbitrary homomorphic computations over fresh, re-encrypted, and evaluated ciphertexts.
## 2025/657
* Title: Key Derivation Functions Without a Grain of Salt
* Authors: Matilda Backendal, Sebastian Clermont, Marc Fischlin, Felix Günther
* [Permalink](
https://eprint.iacr.org/2025/657)
* [Download](
https://eprint.iacr.org/2025/657.pdf)
### Abstract
Key derivation functions (KDFs) are integral to many cryptographic protocols. Their functionality is to turn raw key material, such as a Diffie-Hellman secret, into a strong cryptographic key that is indistinguishable from random. This guarantee was formalized by Krawczyk together with the seminal introduction of HKDF (CRYPTO 2010), in a model where the KDF only takes a single key material input. Modern protocol designs, however, regularly need to combine multiple secrets, possibly even from different sources, with the guarantee that the derived key is secure as long as at least one of the inputs is good. This is particularly relevant in settings like hybrid key exchange for quantum-safe migration. Krawczyk's KDF formalism does not capture this goal, and there has been surprisingly little work on the security considerations for KDFs since then.
In this work, we thus revisit the syntax and security model for KDFs to treat multiple, possibly correlated inputs. Our syntax is assertive: We do away with salts, which are needed in theory to extract from arbitrary sources in the standard model, but in practice, they are almost never used (or even available) and sometimes even misused, as we argue. We use our new model to analyze real-world multi-input KDFs—in Signal's X3DH protocol, ETSI's TS 103 744 standard, and MLS' combiner for pre-shared keys—as well as new constructions we introduce for specialized settings—e.g., a purely blockcipher-based one. We further discuss the importance of collision resistance for KDFs and finally apply our multi-input KDF model to show how hybrid KEM key exchange can be analyzed from a KDF perspective.
## 2025/658
* Title: Efficient Verifiable Mixnets from Lattices, Revisited
* Authors: Jonathan Bootle, Vadim Lyubashevsky, Antonio Merino-Gallardo
* [Permalink](
https://eprint.iacr.org/2025/658)
* [Download](
https://eprint.iacr.org/2025/658.pdf)
### Abstract
Mixnets are powerful building blocks for providing anonymity
in applications like electronic voting and anonymous messaging. The en-
cryption schemes upon which traditional mixnets are built, as well as the
zero-knowledge proofs used to provide verifiability, will, however, soon
become insecure once a cryptographically-relevant quantum computer is
built. In this work, we construct the most compact verifiable mixnet that
achieves privacy and verifiability through encryption and zero-knowledge
proofs based on the hardness of lattice problems, which are believed to
be quantum-safe.
A core component of verifiable mixnets is a proof of shuffle. The starting
point for our construction is the proof of shuffle of Aranha et al. (CT-
RSA 2021). We first identify an issue with the soundness proof in that
work, which is also present in the adaptation of this proof in the mixnets
of Aranha et al. (ACM CCS 2023) and Hough et al. (IACR CiC 2025).
The issue is that one cannot directly adapt classical proofs of shuffle
to the lattice setting due to the splitting structure of the rings used in
lattice-based cryptography. This is not just an artifact of the proof, but
a problem that manifests itself in practice, and we successfully mount an
attack against the implementation of the first of the mixnets. We fix the
problem and introduce a general approach for proving shuffles in split-
ting rings that can be of independent interest.
The efficiency improvement of our mixnet over prior work is achieved by
switching from re-encryption mixnets (as in the works of Aranha et al.
and Hough et al.) to decryption mixnets with very efficient layering based
on the hardness of the LWE and LWR problems over polynomial rings.
The ciphertexts in our scheme are smaller by approximately a factor of
10X and 2X over the aforementioned instantiations, while the linear-size
zero-knowledge proofs are smaller by a factor of 4X and 2X.
## 2025/659
* Title: Scalable and Fine-Tuned Privacy Pass from Group Verifiable Random Functions
* Authors: Dnnis Faut, Julia Hesse, Lisa Kohl, Andy Rupp
* [Permalink](
https://eprint.iacr.org/2025/659)
* [Download](
https://eprint.iacr.org/2025/659.pdf)
### Abstract
Abstract—Anonymous token schemes are cryptographic
protocols for limiting the access to online resources to
credible users. The resource provider issues a set of access
tokens to the credible user that they can later redeem
anonymously, i.e., without the provider being able to link
their redemptions. When combined with credibility tests such
as CAPTCHAs, anonymous token schemes can significantly
increase user experience and provider security, without
exposing user access patterns to providers.
Current anonymous token schemes such as the Privacy
Pass protocol by Davidson et al. rely on oblivious
pseudorandom functions (OPRFs), which let server and user
jointly compute randomly looking access tokens. For those
protocols, token issuing costs are linear in the number of
requested tokens.
In this work, we propose a new approach for building
anonymous token schemes. Instead of relying on two-party
computation to realize a privacy-preserving pseudorandom
function evaluation, we propose to offload token generation
to the user by using group verifiable random functions
(GVRFs). GVRFs are a new cryptographic primitive
that allow users to produce verifiable pseudorandomness.
Opposed to standard VRFs, verification is anonymous within
the group of credible users. We give a construction of group
VRFs from the Dodis-Yampolskiy VRF and Equivalence-
Class Signatures, based on pairings and a new Diffie-
Hellman inversion assumption that we analyze in the Generic
Group Model. Our construction enjoys compact public keys
and proofs, while evaluation and verification costs are only
slightly increased compared to the Dodis-Yampolskiy VRF.
By deploying a group VRF instead of a OPRF, we
obtain an anonymous token scheme where communication
as well as server-side computation during the issuing phase
is constant and independent of the number of tokens a
user requests. Moreover, by means of our new concept of updatable token policies, the number of unspent tokens in
circulation can retrospectively (i.e., even after the credibility
check) be decreased or increased in order to react to
the current or expected network situation. Our tokens are
further countable and publicly verifiable. This comes at the
cost of higher computational efforts for token redemption
and verification as well as somewhat weaker unlinkability
guarantees compared to Privacy Pass.
## 2025/660
* Title: Eccfrog512ck2: An Enhanced 512-bit Weierstrass Elliptic Curve
* Authors: Víctor Duarte Melo, William J Buchanan
* [Permalink](
https://eprint.iacr.org/2025/660)
* [Download](
https://eprint.iacr.org/2025/660.pdf)
### Abstract
Whilst many key exchange and digital signature methods use the NIST P256 (secp256r1) and secp256k1 curves, there is often a demand for increased security. With these curves, we have a 128-bit security. These security levels can be increased to 256-bit security with NIST P-521 Curve 448 and Brainpool-P512.. This paper outlines a new curve - Eccfrog512ck2 - and which provides 256-bit security and enhanced performance over NIST P-521. Along with this, it has side-channel resistance and is designed to avoid weaknesses such as related to the MOV attack. It shows that Eccfrog512ck2 can have a 61.5% speed-up on scalar multiplication and a 33.3% speed-up on point generation over the NIST P-521 curve.
## 2025/661
* Title: An LLM Framework For Cryptography Over Chat Channels
* Authors: Danilo Gligoroski, Mayank Raikwar, Sonu Kumar Jha
* [Permalink](
https://eprint.iacr.org/2025/661)
* [Download](
https://eprint.iacr.org/2025/661.pdf)
### Abstract
Recent advancements in Large Language Models (LLMs) have transformed communication, yet their role in secure messaging remains underexplored, especially in surveillance-heavy environments. At the same time, many governments all over the world are proposing legislation to detect, backdoor, or even ban encrypted communication. That emphasizes the need for alternative ways to communicate securely and covertly over open channels. We propose a novel cryptographic embedding framework that enables covert Public Key or Symmetric Key encrypted communication over public chat channels with human-like produced texts. Some unique properties of our framework are: 1. It is LLM agnostic, i.e., it allows participants to use different local LLM models independently; 2. It is pre- or post-quantum agnostic; 3. It ensures indistinguishability from human-like chat-produced texts. Thus, it offers a viable alternative where traditional encryption is detectable and restricted.
## 2025/662
* Title: Attribute-Based Publicly Verifiable Secret Sharing
* Authors: Liang Zhang, Xingyu Wu, Qiuling Yue, Haibin Kan, Jiheng Zhang
* [Permalink](
https://eprint.iacr.org/2025/662)
* [Download](
https://eprint.iacr.org/2025/662.pdf)
### Abstract
Can a dealer share a secret without knowing the shareholders? We provide a positive answer to this question by introducing the concept of an attribute-based secret sharing (AB-SS) scheme. With AB-SS, a dealer can distribute a secret based on attributes rather than specific individuals or shareholders. Only authorized users whose attributes satisfy a given access structure can recover the secret. Furthermore, we introduce the concept of attribute-based publicly verifiable secret sharing (AB-PVSS). An AB-PVSS scheme allows external users to verify the correctness of all broadcast messages from the dealer and shareholders, similar to a traditional PVSS scheme. Additionally, AB-SS (or AB-PVSS) distinguishes itself from traditional SS (or PVSS) by enabling a dealer to generate shares according to an arbitrary monotone access structure. To construct an AB-PVSS scheme, we first implement a decentralized ciphertext-policy attribute-based encryption (CP-ABE) scheme. The proposed CP-ABE scheme offers a smaller ciphertext size and requires fewer computational operations, although it is not fully-fledged as a trade-off. We then incorporate non-interactive zero-knowledge (NIZK) proofs to enable public verification of the CP-ABE ciphertext. Based on the CP-ABE and NIZK proofs, we construct an AB-PVSS primitive. Furthermore, we present an intuitive implementation of optimistic fair exchange based on the AB-PVSS scheme. Finally, we conduct security analysis and comprehensive experiments on the proposed CP-ABE and AB-PVSS schemes. The results demonstrate that both schemes exhibit plausible performance compared to related works.
## 2025/663
* Title: Intermundium-DL: Assessing the Resilience of Current Schemes to Discrete-Log-Computation Attacks on Public Parameters
* Authors: Mihir Bellare, Doreen Riepel, Laura Shea
* [Permalink](
https://eprint.iacr.org/2025/663)
* [Download](
https://eprint.iacr.org/2025/663.pdf)
### Abstract
We consider adversaries able to perform a nonzero but small number of discrete logarithm computations, as would be expected with near-term quantum computers. Schemes with public parameters consisting of a few group elements are now at risk; could an adversary knowing the discrete logarithms of these elements go on to easily compromise the security of many users? We study this question for known schemes and find, across them, a perhaps surprising variance in the answers. In a first class are schemes, including Okamoto and Katz-Wang signatures, that we show fully retain security even when the discrete logs of the group elements in their parameters are known to the adversary. In a second class are schemes like Cramer-Shoup encryption and the SPAKE2 password-authenticated key exchange protocol that we show retain some partial but still meaningful and valuable security. In the last class are schemes we show by attack to totally break. The distinctions uncovered by these results shed light on the security of classical schemes in a setting of immediate importance, and help make choices moving forward.
## 2025/664
* Title: Publicly Verifiable Generalized Secret Sharing Schemes and Their Applications
* Authors: Liang Zhang, Dongliang Cai, Tao Liu, Haibin Kan, Jiheng Zhang
* [Permalink](
https://eprint.iacr.org/2025/664)
* [Download](
https://eprint.iacr.org/2025/664.pdf)
### Abstract
Generalized secret sharing (GSS), which accommodates monotone access structures, has been under-explored in distributed computing over the past decades. In this paper, we propose the publicly verifiable generalized secret sharing (PVGSS) scheme, enhancing the applicability of GSS in transparent systems. PVGSS not only enables a dealer to share a secret with fine-grained access structures, but also allows anyone to verify whether the dealer and shareholders are acting honestly or not. We begin by introducing two approaches to implement GSS schemes: one based on recursive Shamir secret sharing and another utilizing linear secret sharing scheme (LSSS). Then, we present PVGSS constructions by integrating non-interactive zero-knowledge proofs into the GSS schemes. Further, we prove that the proposed PVGSS schemes achieve IND1-secrecy under DDH assumption. To showcase the practical applicability of PVGSS schemes, we implement a decentralized exchange (DEX) protocol that enables fair atomic swaps of ERC-20 tokens. A sophisticated access structure is devised to: (1) enable fair atomic swaps during normal protocol execution, and (2) incorporate fault-tolerant passive watchers to provide accountable arbitration when disputes occur. Our benchmarks on the BN128 curve demonstrate the computational efficiency of PVGSS schemes, while Ethereum gas cost analysis confirms the viability of the DEX implementation.
## 2025/665
* Title: MProve-Nova: A Privacy-Preserving Proof of Reserves Protocol for Monero
* Authors: Varun Thakore, Saravanan Vijayakumaran
* [Permalink](
https://eprint.iacr.org/2025/665)
* [Download](
https://eprint.iacr.org/2025/665.pdf)
### Abstract
A proof of reserves (PoR) protocol enables a cryptocurrency exchange to prove to its users that it owns a certain amount of coins, as a first step towards proving that it is solvent. We present the design, implementation, and security analysis of MProve-Nova, a PoR protocol for Monero that leverages the Nova recursive SNARK to achieve two firsts (without requiring any trusted setup).. It is the first Monero PoR protocol that reveals only the number of outputs owned by an exchange; no other information about the outputs or their key images is revealed. It is also the first Monero PoR protocol where the proof size and proof verification time are constant, i.e. they are independent of the number of outputs on the Monero blockchain and the number of outputs owned by the exchange. To achieve constant verification times, MProve-Nova requires a pre-processing step which creates two Merkle trees from all the outputs and key images on the Monero blockchain.
MProve-Nova consists of two Nova-based subprotocols, a reserves commitment generator (RCG) protocol used to compute a commitment to the total reserves owned by an exchange and a non-collusion (NC) protocol used to prove non-collusion between two exchanges. For the RCG protocol, we observed proof sizes of about 28 KB and verification times of 4.3 seconds. For the NC protocol, we observed proof sizes of about 24 KB and verification times of 0.2 seconds. Proving times for both protocols increase linearly with the number of outputs owned by the exchange but remain independent of the number of outputs on the Monero blockchain. On average, the RCG protocol required about 42 minutes per 1000 outputs and the NC protocol required about 5 minutes per 1000 outputs.
## 2025/666
* Title: Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
* Authors: Andrej Bogdanov, Alon Rosen, Neekon Vafa, Vinod Vaikuntanathan
* [Permalink](
https://eprint.iacr.org/2025/666)
* [Download](
https://eprint.iacr.org/2025/666.pdf)
### Abstract
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for $n > m$, a scaled random projection $\mathbf{A}$ from $\mathbb{R}^n$ to $\mathbb{R}^m$ is an approximate isometry on any set $S$ of size at most exponential in $m$. If $S$ is larger, however, its points can contract arbitrarily under $\mathbf{A}$. In particular, the hypergrid $([-B, B] \cap \mathbb{Z})^n$ is expected to contain a point that is contracted by a factor of $\kappa_{\mathsf{stat}} = \Theta(B)^{-1/\alpha}$, where $\alpha = m/n$.
We give evidence that finding such a point exhibits a statistical-computational gap precisely up to $\kappa_{\mathsf{comp}} = \widetilde{\Theta}(\sqrt{\alpha}/B)$. On the algorithmic side, we design an online algorithm achieving $\kappa_{\mathsf{comp}}$, inspired by a discrepancy minimization algorithm of Bansal and Spencer (Random Structures \& Algorithms, 2020). On the hardness side, we show evidence via a multiple overlap gap property (mOGP), which in particular captures online algorithms; and a reduction-based lower bound, which shows hardness under standard worst-case lattice assumptions.
As a cryptographic application, we show that the rounded Johnson-Lindenstrauss embedding is a robust property-preserving hash function (Boyle, Lavigne and Vaikuntanathan, TCC 2019) on the hypergrid for the Euclidean metric in the computationally hard regime. Such hash functions compress data while preserving $\ell_2$ distances between inputs up to some distortion factor, with the guarantee that even knowing the hash function, no computationally bounded adversary can find any pair of points that violates the distortion bound.
## 2025/667
* Title: Vector Commitment Design, Analysis, and Applications: A Survey
* Authors: Vir Pathak, Sushmita Ruj, Ron van der Meyden
* [Permalink](
https://eprint.iacr.org/2025/667)
* [Download](
https://eprint.iacr.org/2025/667.pdf)
### Abstract
Due to their widespread applications in decentralized and privacy preserving technologies, commitment schemes have become increasingly important cryptographic primitives. With a wide variety of applications, many new constructions have been proposed, each enjoying different features and security guarantees. In this paper, we systematize the designs, features, properties, and applications of vector commitments (VCs). We define vector, polynomial, and functional commitments and we discuss the relationships shared between these types of commitment schemes. We first provide an overview of the definitions of the commitment schemes we will consider, as well as their security notions and various properties they can have. We proceed to compare popular constructions, taking into account the properties each one enjoys, their proof/update information sizes, and their proof/commitment complexities. We also consider their effectiveness in various decentralized and privacy preserving applications. Finally, we conclude by discussing some potential directions for future work.