[digest] 2025 Week 6

Liste des GroupesRevenir à s crypt 
Sujet : [digest] 2025 Week 6
De : noreply (at) *nospam* example.invalid (IACR ePrint Archive)
Groupes : sci.crypt
Date : 10. Feb 2025, 04:21:32
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <ILbQ4YxsECHZtHLxw5waVlCn8YZmC1Rb@eprint.iacr.org.invalid>
## In this issue

1. [2023/700] PIE: $p$-adic Encoding for High-Precision ...
2. [2024/1590] Matching radar signals and fingerprints with MPC
3. [2025/159] A Holistic Framework for Impossible Boomerang Attacks
4. [2025/160] The Nonlinear Filter Model of Stream Cipher Redivivus
5. [2025/161] Secure Showing of Partial Attributes
6. [2025/162] Learning from Functionality Outputs: Private Join ...
7. [2025/163] Bootstrapping (T)FHE Ciphertexts via Automorphisms: ...
8. [2025/164] Multi-Authority Functional Encryption with Bounded ...
9. [2025/165] Shuffle Shamir Secret Shares Uniformly with Linear ...
10. [2025/166] Polynomial Inversion Algorithms in Constant Time ...
11. [2025/167] Wiretapping LLMs: Network Side-Channel Attacks on ...
12. [2025/168] Revisiting Beimel-Weinreb Weighted Threshold Secret ...
13. [2025/169] Efficient Pseudorandom Correlation Generators for ...
14. [2025/170] Efficient Error Detection Methods for the Number ...
15. [2025/171] A light white-box masking scheme using Dummy ...
16. [2025/172] SoK: Understanding zk-SNARKs: The Gap Between ...
17. [2025/173] A Critical Analysis of Deployed Use Cases for ...
18. [2025/174] VITARIT: Paying for Threshold Services on Bitcoin ...
19. [2025/175] Updatable Public-Key Encryption, Revisited
20. [2025/176] HyperLoop: Rationally secure efficient cross-chain ...
21. [2025/177] On the Power of Sumcheck in Secure Multiparty ...
22. [2025/178] Improved Differential and Linear Cryptanalysis on ...
23. [2025/179] Higher-Order Deterministic Masking with Application ...
24. [2025/180] On the Atomicity and Efficiency of Blockchain ...
25. [2025/181] Improved NTT and CRT-based RNR Blinding for Side- ...
26. [2025/182] Deny Whatever You Want: Dual-Deniable Public-Key ...
27. [2025/183] OBLIVIATOR: Oblivious Parallel Joins and other ...
28. [2025/184] NodeChain: Cheap Data Integrity Without Consensus
29. [2025/185] AutoDiVer: Automatically Verifying Differential ...
30. [2025/186] Computing Quaternion Embeddings and Endomorphism ...
31. [2025/187] Asymptotic improvements to provable algorithms for ...
32. [2025/188] BulletCT: Towards More Scalable Ring Confidential ...
33. [2025/189] Experimentally studying path-finding problem ...
34. [2025/190] Binary Codes for Error Detection and Correction in ...

## 2023/700

* Title: PIE: $p$-adic Encoding for High-Precision Arithmetic in Homomorphic Encryption
* Authors: Luke Harmon, Gaetan Delavignette, Arnab Roy, David Silva
* [Permalink](https://eprint.iacr.org/2023/700)
* [Download](https://eprint.iacr.org/2023/700.pdf)

### Abstract

A large part of current research in homomorphic encryption (HE) aims towards making HE practical for real-world applications. In any practical HE, an important issue is to convert the application data (type) to the data type suitable for the HE.
  The main purpose of this work is to investigate an efficient HE-compatible encoding method that is generic, and can be easily adapted to apply to the HE schemes over integers or polynomials.
  $p$-adic number theory provides a way to transform rationals to integers, which makes it a natural candidate for encoding rationals. Although one may use naive number-theoretic techniques to perform rational-to-integer transformations without reference to $p$-adic numbers, we contend that the theory of $p$-adic numbers is the proper lens to view such transformations.
   In this work we identify mathematical techniques (supported by $p$-adic number theory) as appropriate tools to construct a generic rational encoder which is compatible with HE. Based on these techniques, we propose a new encoding scheme PIE, that can be easily combined with both AGCD-based and RLWE-based HE to perform high precision arithmetic. After presenting an abstract version of PIE, we show how it can be attached to two well-known HE schemes: the AGCD-based IDGHV scheme and the RLWE-based (modified) Fan-Vercauteren scheme. We also discuss the advantages of our encoding scheme in comparison with previous works.



## 2024/1590

* Title: Matching radar signals and fingerprints with MPC
* Authors: Benjamin Hansen Mortensen, Mathias Karsrud Nordal, Martin Strand
* [Permalink](https://eprint.iacr.org/2024/1590)
* [Download](https://eprint.iacr.org/2024/1590.pdf)

### Abstract

Vessels can be recognised by their navigation radar due to the characteristics of the emitted radar signal. This is particularly useful if one wants to build situational awareness without revealing one's own presence. Most countries maintain databases of radar fingerprints but will not readily share these due to national security regulations. Sharing of such information will generally require some form of information exchange agreement.

However, all parties in a coalition benefit from correct identification. We use secure multiparty computation to match a radar signal measurement against secret databases and output plausible matches with their likelihoods. We also provide a demonstrator using MP-SPDZ.



## 2025/159

* Title: A Holistic Framework for Impossible Boomerang Attacks
* Authors: Yincen Chen, Qinggan Fu, Ning Zhao, Jiahao Zhao, Ling Song, Qianqian Yang
* [Permalink](https://eprint.iacr.org/2025/159)
* [Download](https://eprint.iacr.org/2025/159.pdf)

### Abstract

In 2011, Lu introduced the impossible boomerang attack at DCC. This powerful cryptanalysis technique combines the strengths of the impossible differential and boomerang attacks, thereby inheriting the advantages of both cryptographic techniques. In this paper, we propose a holistic framework comprising two generic and effective algorithms and a MILP-based model to search for the optimal impossible boomerang attack systematically. The first algorithm incorporates any key guessing strategy, while the second integrates the meet-in-the-middle (MITM) attack into the key recovery process. Our framework is highly flexible, accommodating any set of attack parameters and returning the optimal attack complexity. When applying our framework to Deoxys-BC-256, Deoxys-BC-384, Joltik-BC-128, Joltik-BC-192, and SKINNYe v2, we achieve several significant improvements. We achieve the first 11-round impossible boomerang attacks on Deoxys-BC-256\ and Joltik-BC-128. For SKINNYe v2, we achieve the first 33-round impossible boomerang attack, then using the MITM approach in the key recovery attack, the time complexity is significantly reduced. Additionally, for the 14-round Deoxys-BC-384 and Joltik-BC-192, the time complexity of the impossible boomerang attack is reduced by factors exceeding 2^{27} and 2^{12}, respectively.



## 2025/160

* Title: The Nonlinear Filter Model of Stream Cipher Redivivus
* Authors: Claude Carlet, Palash Sarkar
* [Permalink](https://eprint.iacr.org/2025/160)
* [Download](https://eprint.iacr.org/2025/160.pdf)

### Abstract

The nonlinear filter model is an old and well understood approach to the design of secure stream ciphers. Extensive research over several decades has shown how to attack stream ciphers based on this model and has identified the security properties required of the Boolean function used as the filtering function to resist such attacks. This led to the problem of constructing Boolean functions which provide adequate security and at the same time are efficient to implement. Unfortunately, over the last two decades no good solutions to this problem appeared in the literature. The lack of good solutions has effectively led to nonlinear filter model becoming more or less obsolete. This is a big loss to the cryptographic design toolkit, since the great advantages of the nonlinear filter model are its simplicity, well understood security and the potential to provide low cost solutions for hardware oriented stream ciphers. In this paper we construct balanced functions on an odd number $n\geq 5$ of variables with the following provable properties: linear bias equal to $2^{-\lfloor n/2\rfloor -1}$, algebraic degree equal to $2^{\lfloor \log_2\lfloor n/2\rfloor \rfloor}$, algebraic immunity at least $\lceil (n-1)/4\rceil$, fast algebraic immunity at least $1+\lceil (n-1)/4\rceil $, and can be implemented using $O(n)$ NAND gates. The functions are obtained from a simple modification of the well known class of Maiorana-McFarland bent functions. By appropriately choosing $n$ and the length $L$ of the linear feedback shift register, we show that it is possible to obtain examples of stream ciphers which are $\kappa$-bit secure against known types of attacks for various values of $\kappa$. We provide concrete proposals for $\kappa=80,128,160,192,224$ and $256$. For the $80$-bit, $128$-bit, and the $256$-bit security levels, the circuits for the corresponding stream ciphers require about 1743.5, 2771.5, and 5607.5 NAND gates respectively. For the $80$-bit and the $128$-bit security levels, the gate count estimates compare quite well to the famous ciphers Trivium and Grain-128a respectively, while for the $256$-bit security level, we do not know of any other stream cipher design which has such a low gate count.



## 2025/161

* Title: Secure Showing of Partial Attributes
* Authors: Foteini Baldimtsi, Julia Kastner, Julian Loss, Omar Renawi
* [Permalink](https://eprint.iacr.org/2025/161)
* [Download](https://eprint.iacr.org/2025/161.pdf)

### Abstract

Anonymous Attribute-Based Credentials (ABCs) allow users to prove possession of attributes while adhering to various authentication policies and without revealing unnecessary information. Single-use ABCs are particularly appealing for their lightweight nature and practical efficiency. These credentials are typically built using blind signatures, with Anonymous Credentials Light (ACL) being one of the most prominent schemes in the literature. However, the security properties of single-use ABCs, especially their secure showing property, have not been fully explored, and prior definitions and corresponding security proofs fail to address scenarios involving partial attribute disclosure effectively. In this work, we propose a stronger secure showing definition that ensures robust security even under selective attribute revelation. Our definition extends the winning condition of the existing secure showing experiment by adding various constraints on the subsets of opened attributes. We show how to represent this winning condition as a matching problem in a suitable bipartite graph, thus allowing for it to be verified efficiently. We then prove that ACL satisfies our strong secure showing notion without any modification. Finally, we define double-spending prevention for single-use ABCs, and show how ACL satisfies the definition.



## 2025/162

* Title: Learning from Functionality Outputs: Private Join and Compute in the Real World
* Authors: Francesca Falzon, Tianxin Tang
* [Permalink](https://eprint.iacr.org/2025/162)
* [Download](https://eprint.iacr.org/2025/162.pdf)

### Abstract

Private Join and Compute (PJC) is a two-party protocol recently proposed by Google for various use-cases, including ad conversion (Asiacrypt 2021) and which generalizes their deployed private set intersection sum (PSI-SUM) protocol (EuroS&P 2020).

PJC allows two parties, each holding a key-value database, to privately evaluate the inner product of the values whose keys lie in the intersection. While the functionality output is not typically considered in the security model of the MPC literature, it may pose real-world privacy risks, thus raising concerns about the potential deployment of protocols like PJC.

In this work, we analyze the risks associated with the PJC functionality output. We consider an adversary that is a participating party of PJC and describe four practical attacks that break the other party's input privacy, and which are able to recover both membership of keys in the intersection and their associated values.  Our attacks consider the privacy threats associated with deployment and highlight the need to include the functionality output as part of the MPC security model.



## 2025/163

* Title: Bootstrapping (T)FHE Ciphertexts via Automorphisms: Closing the Gap Between Binary and Gaussian Keys
* Authors: Olivier Bernard, Marc Joye
* [Permalink](https://eprint.iacr.org/2025/163)
* [Download](https://eprint.iacr.org/2025/163.pdf)

### Abstract

The GINX method in TFHE offers low-latency ciphertext bootstrapping with relatively small bootstrapping keys, but is limited to binary or ternary key distributions. In contrast, the AP method supports arbitrary key distributions, however at the cost of significantly large bootstrapping keys. Building on AP, automorphism-based methods (LMK⁺, EUROCRYPT 2023) achieve smaller keys, though each automorphism application necessitates a key switch, introducing computational overhead and noise.
This paper advances automorphism-based methods in two important ways. First, it proposes a novel traversal blind rotation algorithm that optimizes the number of key switches for a given key material. Second, it introduces an automorphism-parametrized external product that seamlessly applies an automorphism to one of the input ciphertexts. Together, these techniques substantially reduce the number of key switches, resulting in faster bootstrapping and improved noise control.  As an independent contribution, this paper also introduce a comprehensive theoretical framework for analyzing the expected number of automorphism key switches, whose predictions perfectly align with the results of extensive numerical experiments, demonstrating its practical relevance.
In a typical setting, by utilizing additional key material, the LLW⁺ approach (TCHES 2024) reduces key switches by 17% compared to LMK⁺. Our combined techniques achieve a 46% reduction using similar key material and can eliminate an arbitrary large number (e.g., > 99%) of key switches  with only a moderate (9x) increase in key material size.



## 2025/164

* Title: Multi-Authority Functional Encryption with Bounded Collusions from Standard Assumptions
* Authors: Rishab Goyal, Saikumar Yadugiri
* [Permalink](https://eprint.iacr.org/2025/164)
* [Download](https://eprint.iacr.org/2025/164.pdf)

### Abstract

Multi-Authority Functional Encryption ($\mathsf{MA}$-$\mathsf{FE}$) [Chase, TCC'07; Lewko-Waters, Eurocrypt'11; Brakerski et al., ITCS'17] is a popular generalization of functional encryption ($\mathsf{FE}$) with the central goal of decentralizing the trust assumption from a single central trusted key authority to a group of multiple, independent and non-interacting, key authorities.. Over the last several decades, we have seen tremendous advances in new designs and constructions for $\mathsf{FE}$ supporting different function classes, from a variety of assumptions and with varying levels of security. Unfortunately, the same has not been replicated in the multi-authority setting. The current scope of $\mathsf{MA}$-$\mathsf{FE}$ designs is rather limited, with positive results only known for (all-or-nothing) attribute-based functionalities, or need full power of general-purpose code obfuscation. This state-of-the-art in $\mathsf{MA}$-$\mathsf{FE}$ could be explained in part by the implication provided by Brakerski et al. (ITCS'17). It was shown that a general-purpose obfuscation scheme can be designed from any $\mathsf{MA}$-$\mathsf{FE}$ scheme for circuits, even if the $\mathsf{MA}$-$\mathsf{FE}$ scheme is secure only in a bounded-collusion model, where at most two keys per authority get corrupted.

In this work, we revisit the problem of $\mathsf{MA}$-$\mathsf{FE}$, and show that existing implication from $\mathsf{MA}$-$\mathsf{FE}$ to obfuscation is not tight. We provide new methods to design $\mathsf{MA}$-$\mathsf{FE}$ for circuits from simple and minimal cryptographic assumptions. Our main contributions are summarized below

  1. We design a $\mathsf{poly}(\lambda)$-authority $\mathsf{MA}$-$\mathsf{FE}$ for circuits in the bounded-collusion model. Under the existence of public-key encryption, we prove it to be statically simulation-secure. Further, if we assume sub-exponential security of public-key encryption, then we prove it to be adaptively simulation-secure in the Random Oracle Model.
  2. We design a $O(1)$-authority $\mathsf{MA}$-$\mathsf{FE}$ for circuits in the bounded-collusion model. Under the existence of 2/3-party non-interactive key exchange, we prove it to be adaptively simulation-secure.
  3. We provide a new generic bootstrapping compiler for $\mathsf{MA}$-$\mathsf{FE}$ for general circuits to design a simulation-secure $(n_1 + n_2)$-authority $\mathsf{MA}$-$\mathsf{FE}$ from any two $n_1$-authority and $n_2$-authority $\mathsf{MA}$-$\mathsf{FE}$.



## 2025/165

* Title: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication
* Authors: Jiacheng Gao, Yuan Zhang, Sheng Zhong
* [Permalink](https://eprint.iacr.org/2025/165)
* [Download](https://eprint.iacr.org/2025/165.pdf)

### Abstract

In this paper, we revisit shuffle protocol for Shamir secret sharing. Upon examining previous works, we observe that existing constructions either produce non-uniform shuffle or require large communication and round complexity, e.g.. exponential in the number of parties. We propose two shuffle protocols, both of which shuffle uniformly within $O(\frac{k + l}{\log k}n^2m\log m)$ communication for shuffling rows of an $m\times l$ matrix shared among $n$ parties, where $k\leq m$ is a parameter balancing communication and computation. Our first construction is more concretely efficient, while our second construction requires only $O(nml)$ online communication within $O(n)$ round. In terms of overall communication and online communication, both shuffle protocols outperform current optimal shuffle protocols for Shamir secret sharing.
       
At the core of our constructions is a novel permutation-sharing technique, which can be used to permute arbitrarily many vectors by computing matrix-vector products. Once shared, applying a permutation becomes much cheaper, which results in a faster online phase. Letting each party share one secret uniform permutation in the offline phase and applying them sequentially in the online phase, we obtain our first shuffle protocol. To further optimize online complexity and simplify the trade-off, we adopt the shuffle correlation proposed by Gao et al. and obtain the second shuffle protocol with $O(nml)$ online communication and $O(n^2ml)$ online computation. This brings an additional benefit that the online complexity is now independent of offline complexity, which reduces parameter optimization to optimizing offline efficiency.

Our constructions require only most basic primitives in Shamir secret sharing scheme, and work for arbitrary field $\mathbb{F}$ of size larger than $n$. As shuffle is a frequent operation in algorithm design, we expect them to accelerate many other primitives in context of Shamir secret sharing MPC, such as sorting, oblivious data structure, etc.



## 2025/166

* Title: Polynomial Inversion Algorithms in Constant Time for Post-Quantum Cryptography
* Authors: Abhraneel Dutta, Emrah Karagoz, Edoardo Persichetti, Pakize Sanal
* [Permalink](https://eprint.iacr.org/2025/166)
* [Download](https://eprint.iacr.org/2025/166.pdf)

### Abstract

The computation of the inverse of a polynomial over a quotient ring or a finite field plays a very important role during the key generation of post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. It is therefore important that there exist an efficient algorithm capable of running in constant time, to prevent timing side-channel attacks. In this article, we study both constant-time algorithms based on Fermat's Little Theorem and the Extended $GCD$ Algorithm, and provide a detailed comparison in terms of performance. According to our conclusion, we see that the constant-time Extended $GCD$-based Bernstein-Yang's algorithm shows a better performance with 1.76x-3.76x on \texttt{x86} platforms compared to FLT-based methods. Although we report numbers from a software implementation, we additionally provide a short glimpse of some recent results when these two algorithms are implemented on various hardware platforms. Finally, we also explore other exponentiation algorithms that work similarly to the Itoh-Tsuji inversion method. These algorithms perform fewer polynomial multiplications and show a better performance with 1.56x-1.96x on \texttt{x86} platform compared to Itoh-Tsuji inversion method.



## 2025/167

* Title: Wiretapping LLMs: Network Side-Channel Attacks on Interactive LLM Services
* Authors: Mahdi Soleimani, Grace Jia, In Gim, Seung-seob Lee, Anurag Khandelwal
* [Permalink](https://eprint.iacr.org/2025/167)
* [Download](https://eprint.iacr.org/2025/167.pdf)

### Abstract

Recent server-side optimizations like speculative decoding significantly enhance the interactivity and resource efficiency of Large Language Model (LLM) services. However, we show that these optimizations inadvertently introduce new side-channel vulnerabilities through network packet timing and size variations that tend to be input-dependent. Network adversaries can leverage these side channels to learn sensitive information contained in \emph{encrypted} user prompts to and responses from public LLM services. 

This paper formalizes the security implications using a novel indistinguishability framework and introduces a novel attack that establishes the insecurity of real-world LLM services with streaming APIs under our security framework.

Our proposed attack effectively deconstructs encrypted network packet traces to reveal the sizes of underlying LLM-generated tokens and whether the tokens were generated with or without certain server-side optimizations. Our attack can accurately predict private attributes in real-world privacy-sensitive LLM applications in medicine and finance with $71$--$92\%$ accuracy on an open-source vLLM service and $50$--$90\%$ accuracy on the commercial ChatGPT service. Finally, we show that solutions that hide these side channels to different degrees expose a tradeoff between security and performance --- specifically, interactivity and network bandwidth overheads.



## 2025/168

* Title: Revisiting Beimel-Weinreb Weighted Threshold Secret Sharing Schemes
* Authors: Oriol Farràs, Miquel Guiot
* [Permalink](https://eprint.iacr.org/2025/168)
* [Download](https://eprint.iacr.org/2025/168.pdf)

### Abstract

A secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets. In a weighted threshold secret sharing scheme, each party is assigned a weight according to its importance, and the authorized subsets are those in which the sum of their weights is at least the threshold value.

For these access structures, the best general constructions were presented by Beimel and Weinreb [IPL 2006]: The scheme with perfect security has share size $n^{O(\log n)}$, while the scheme with computational security has share size polynomial in $n$. However, these constructions require the use of shallow monotone sorting networks, which limits their practical use.

In this context, we revisit this work and provide variants of these constructions that are feasible in practice. This is done by considering alternative circuits and formulas for weighted threshold functions that do not require monotone sorting networks. We show that, under the assumption that subexponentially secure one-way functions exist, any WTAS over $n$ parties and threshold $\sigma$ admits a computational secret sharing scheme where the size of the shares is $\mathrm{polylog}(n)$ and the size of the public information is $O(n^2\log n\log \sigma)$. Moreover, we show that any authorized subset only needs to download $O(n\log n\log \sigma)$ bits of public information to recover the secret.



## 2025/169

* Title: Efficient Pseudorandom Correlation Generators for Any Finite Field
* Authors: Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan
* [Permalink](https://eprint.iacr.org/2025/169)
* [Download](https://eprint.iacr.org/2025/169.pdf)

### Abstract

Correlated randomness lies at the core of efficient modern secure multi-party computation (MPC) protocols. Costs of generating such correlated randomness required for the MPC online phase protocol often constitute a bottleneck in the overall protocol.
A recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) offers an appealing solution to this issue. In sketch, each party is given a short PCG seed, which can be locally expanded into long correlated strings, satisfying the target correlation. Among various types of correlations, there is oblivious linear evaluation (OLE), a fundamental and useful primitive for typical MPC protocols on arithmetic circuits.
Towards efficient generating a great amount of OLE, and applications to MPC protocols, we establish the following results:

(i) We propose a novel {\em programmable} PCG construction for OLE over any field $\mathbb{F}_p$.  For $kN$ OLE correlations, we require $O(k\log{N})$ communication and $O(k^2N\log{N})$ computation, where $k$ is an arbitrary integer $\geq 2$. Previous works either have quadratic computation (Boyle et al. Crypto'19), or can only support fields of size larger than $2$ (Bombar et al. Crypto'23).

(ii) We extend the above OLE construction to provide various types of correlations for any finite field. One of the fascinating applications is an efficient PCG for two-party {\em authenticated Boolean multiplication triples}. For $kN$ authenticated triples, we offer PCGs with seed size of $O(k^2\log{N})$ bits. To our best knowledge, such correlation has not been realized with sublinear communication and quasi-linear computation ever before.

(iii) In addition, the \emph{programmability} admits efficient PCGs for multi-party Boolean triples, and thus the first efficient MPC protocol for Boolean circuits with {\em silent} preprocessing. In particular, we show $kN$ $m$-party Boolean multiplication triples can be generated in $O(m^2k\log{N})$-bit communication, while the state-of-the-art FOLEAGE (Asiacrypt'24) requires a broadcast channel and takes $mkN+O(m^2\log{kN})$ bits communication.

(iv) Finally, we present efficient PCGs for circuit-dependent preprocessing, matrix multiplications triples, and string OTs etc. Compared to previous works, each has its own right.



## 2025/170

* Title: Efficient Error Detection Methods for the Number Theoretic Transforms in Lattice-Based Algorithms
* Authors: Mohamed Abdelmonem, Lukas Holzbaur, Håvard Raddum, Alexander Zeh
* [Permalink](https://eprint.iacr.org/2025/170)
* [Download](https://eprint.iacr.org/2025/170.pdf)

### Abstract

The Number Theoretic Transform (NTT) is a crucial component in many post-quantum cryptographic (PQC) algorithms, enabling efficient polynomial multiplication. However, the reliability of NTT computations is an important concern, especially for safety-critical applications. This work presents novel techniques to improve the fault tolerance of NTTs used in prominent PQC schemes such as Kyber, Dilithium, and Falcon. The work first establishes a theoretical framework for error detection in NTTs, exploiting the inherent algebraic properties of these transforms. It derives necessary and sufficient conditions for constructing error-detecting vectors that can identify single faults without the need for costly recomputation. For the Dilithium scheme, the work further advances the state-of-the-art by developing the first algorithm capable of detecting up to two maliciously placed faults. The proposed error detection methods are shown to reduce the number of required multiplications by half, leading to significant improvements in computational efficiency compared to existing single error-detecting algorithms. Concrete implementations for Kyber, Dilithium, and Falcon demonstrate the practicality and effectiveness of the error-detection scheme.



## 2025/171

* Title: A light white-box masking scheme using Dummy Shuffled Secure Multiplication
* Authors: Alex Charlès, Aleksei Udovenko
* [Permalink](https://eprint.iacr.org/2025/171)
* [Download](https://eprint.iacr.org/2025/171.pdf)

### Abstract

In white-box cryptography, early encoding-based countermeasures have been broken by the DCA attack, leading to the utilization of masking schemes against a surge of automated attacks. The recent filtering attack from CHES 2024 broke the last viable masking scheme from CHES 2021 resisting both computational and algebraic attacks, raising the need for new countermeasures.

In this work, we perform the first formal study of the combinations of existing countermeasures and demonstrate that applying Dummy Shuffling (EUROCRYPT 2021) then ISW masking (CRYPTO 2003) to a circuit carries algebraic, correlation, and filtering security - necessary conditions to withstand state-of-the-art automated attacks. We also show that applying these two countermeasures in the opposite order leads to a Higher-Order Filtering attack, highlighting the importance of the order of application of the combined countermeasures.

We also propose a new masking scheme called S5, standing for the Semi-Shuffled Secret Sharing Scheme, a scheme merging Dummy Shuffling and ISW in a single countermeasure more efficiently than a direct composition.



## 2025/172

* Title: SoK: Understanding zk-SNARKs: The Gap Between Research and Practice
* Authors: Junkai Liang, Daqi Hu, Pengfei Wu, Yunbo Yang, Qingni Shen, Zhonghai Wu
* [Permalink](https://eprint.iacr.org/2025/172)
* [Download](https://eprint.iacr.org/2025/172.pdf)

### Abstract

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are a powerful tool for proving computation correctness, attracting significant interest from researchers, developers, and users. However, the complexity of zk-SNARKs has created gaps between these groups, hindering progress. Researchers focus on constructing efficient proving systems with stronger security and new properties, while developers and users prioritize toolchains, usability, and compatibility.

In this work, we provide a comprehensive study of zk-SNARK, from theory to practice, pinpointing gaps and limitations. We first present a master recipe that unifies the main steps in converting a program into a zk-SNARK. We then classify existing zk-SNARKs according to their key techniques. Our classification addresses the main difference in practically valuable properties between existing zk-SNARK schemes. We survey over 40 zk-SNARKs since 2013 and provide a reference table listing their categories and properties. Following the steps in master recipe, we then survey 11 general-purpose popular used libraries. We elaborate on these libraries' usability, compatibility, efficiency and limitations. Since installing and executing these zk-SNARK systems is challenging, we also provide a completely virtual environment in which to run the compiler for each of them. We identify that the proving system is the primary focus in cryptography academia. In contrast, the constraint system presents a bottleneck in industry. To bridge this gap, we offer recommendations and advocate for the opensource community to enhance documentation, standardization and compatibility.



## 2025/173

* Title: A Critical Analysis of Deployed Use Cases for Quantum Key Distribution and Comparison with Post-Quantum Cryptography
* Authors: Nick Aquina, Bruno Cimoli, Soumya Das, Kathrin Hövelmanns, Fiona Johanna Weber, Chigo Okonkwo, Simon Rommel, Boris Škorić, Idelfonso Tafur Monroy, Sebastian Verschoor
* [Permalink](https://eprint.iacr.org/2025/173)
* [Download](https://eprint.iacr.org/2025/173.pdf)

### Abstract

Quantum Key Distribution (QKD) is currently being discussed as a technology to safeguard communication in a future where quantum computers compromise traditional public-key cryptosystems. In this paper, we conduct a comprehensive security evaluation of QKD-based solutions, focusing on real-world use cases sourced from academic literature and industry reports. We analyze these use cases, assess their security and identify the possible advantages of deploying QKD-based solutions. We further compare QKD-based solutions with Post-Quantum Cryptography (PQC), the alternative approach to achieving security when quantum computers compromise traditional public-key cryptosystems, evaluating their respective suitability for each scenario. Based on this comparative analysis, we critically discuss and comment on which use cases QKD is suited for, considering factors such as implementation complexity, scalability, and long-term security. Our findings contribute to a better understanding of the role QKD could play in future cryptographic infrastructures and offer guidance to decision-makers considering the deployment of QKD.



## 2025/174

* Title: VITARIT: Paying for Threshold Services on Bitcoin and Friends
* Authors: Lucjan Hanzlik, Aniket Kate, Easwar Vivek Mangipudi, Pratyay Mukherjee, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2025/174)
* [Download](https://eprint.iacr.org/2025/174.pdf)

### Abstract

Blockchain service offerings have seen a rapid rise
in recent times. Many of these services realize a decentralized
architecture with a threshold adversary to avoid a single
point of failure and to mitigate key escrow issues. While
payments to such services are straightforward in systems
supporting smart contracts, achieving fairness poses challenges
in systems like Bitcoin, adhering to the UTXO model with
limited scripting capabilities. This is especially challenging
without smart contracts, as we wish to pay only the required
threshold of t + 1 out of the n servers offering the service
together, without any server claiming the payment twice.

In this paper, we introduce VITARIT 1, a novel payment
solution tailored for threshold cryptographic services in UTXO
systems like Bitcoin. Our approach guarantees robust provable
security while facilitating practical deployment. We focus on
the t-out-of-n distributed threshold verifiable random function
(VRF) service with certain properties, such as threshold BLS
signatures, a recently highlighted area of interest. Our protocol
enables clients to request verifiable random function (VRF)
values from the threshold service, triggering payments to up
to t + 1 servers of the distributed threshold VRF.

Our efficient design relies on simple transactions using
signature verification scripts, making it immediately applicable
in Bitcoin-like systems. We also introduce new tools and
techniques at both the cryptographic and transaction layers,
including a novel signature-VRF exchange protocol for standard
constructions, which may be of independent interest. Addition-
ally, our transaction flow design prevents malicious servers
from claiming payments twice, offering broader implications for
decentralized payment systems. Our prototype implementation
shows that in the two-party interaction, the client takes 126.4
msec, and the server takes 204 msec, demonstrating practicality
and deployability of the system



## 2025/175

* Title: Updatable Public-Key Encryption, Revisited
* Authors: Joël Alwen, Georg Fuchsbauer, Marta Mularczyk
* [Permalink](https://eprint.iacr.org/2025/175)
* [Download](https://eprint.iacr.org/2025/175.pdf)

### Abstract

We revisit Updatable Public-Key Encryption (UPKE), which was introduced as a practical mechanism for building forward-secure cryptographic protocols. We begin by observing that all UPKE notions to date are neither syntactically flexible nor secure enough for the most important multi-party protocols motivating UPKE. We provide an intuitive taxonomy of UPKE properties -- some partially or completely overlooked in the past -- along with an overview of known (explicit and implicit) UPKE constructions. We then introduce a formal UPKE definition capturing all intuitive properties needed for multi-party protocols.

Next, we provide a practical pairing-based construction for which we provide concrete security bounds under a standard assumption in the random oracle and the algebraic group model. The efficiency profile of the scheme compares very favorably with existing UPKE constructions (despite the added flexibility and stronger security). For example, when used to improve the forward security of the Messaging Layer Security protocol [RFC9420], our new UPKE construction requires $\approx 1\%$ of the bandwidth of the next-most efficient UPKE construction satisfying the strongest UPKE notion previously considered.



## 2025/176

* Title: HyperLoop: Rationally secure efficient cross-chain bridge
* Authors: Aniket Kate, Easwar Vivek Mangipudi, Charan Nomula, Raghavendra Ramesh, Athina Terzoglou, Joshua Tobkin
* [Permalink](https://eprint.iacr.org/2025/176)
* [Download](https://eprint.iacr.org/2025/176.pdf)

### Abstract

Cross-chain bridges, realizing the transfer of information and assets between blockchains, form the core of blockchain interoperability solutions. Most existing bridge networks are modeled in an honest-malicious setting, where the bridge nodes are either honest or malicious. Rationality allows the nodes to deviate from the protocol arbitrarily for an economic incentive. In this work, we present HyperLoop, an efficient cross-chain multi-signature bridge and prove that it is safe and live game-theoretically, under the more realistic rational-malicious model.

As rational bridge nodes are allowed to deviate from the protocol and even collude, a monitor mechanism is necessitated, which we realize by introducing whistle-blower nodes. These whistle-blowers constantly check the operations of the bridge and raise complaints to a complaint resolution network in case of discrepancies. To enforce punishments, it is necessary for the nodes to stake an amount before participating as bridge nodes. Consequently, a cap on the volume of funds transferred over the bridge is established. We describe a sliding window mechanism and establish a relation between the stake and the sliding window limit necessary for the safety of the bridge.

Our design yields an economic, computation, and communication-efficient bridge. We realize and deploy our bridge prototype bridging Ethereum and Polygon chains over testnets. For a 19-node bridge network, each bridge node takes an average of only 3 msec to detect and sign a source chain request, showing the highly efficiency and low-latency of the bridge.



## 2025/177

* Title: On the Power of Sumcheck in Secure Multiparty Computation
* Authors: Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan
* [Permalink](https://eprint.iacr.org/2025/177)
* [Download](https://eprint.iacr.org/2025/177.pdf)

### Abstract

Lund et al. (JACM 1992) invented the powerful Sumcheck protocol that has been extensively used in complexity theory and also for designing concretely efficient (zero-knowledge) arguments. In this work, we systematically study Sumcheck in the context of secure multi-party computation (MPC). Our main result is a new generic framework for lifting semi-honest MPC protocols to malicious security, with a {\em constant} multiplicative overhead in {\em both} computation and communication, and even additional logarithmic communication in the best case. In general, our approach applies to any semi-honest linear secret-sharing based MPC secure up to additive attacks, where secret-sharings can be added with an authentication property. At a high-level, our approach has a highly distributive flavor, where the parties jointly emulate a Sumcheck prover that proves the correctness of MPC semi-honest evaluations in zero-knowledge, meanwhile they also jointly emulate a Sumcheck verifier and verify the proof themselves. Along the way, we provide a new angle of view on the {\em fully linear interactive oracle proof} (FLIOP) systems proposed by Boneh et al. (CRYPTO 2019). That is, essentially distributed sumcheck on proving a batch of multiplications is an optimized concrete instantiation of the FLIOP-based approach.

As concrete applications of our techniques, we first consider semi-honest MPC protocols based on Shamir secret-sharing with an honest majority. Suppose $M$-party and circuit size $N$, to achieve malicious security, our approach only introduces additional $10MN+O(M\log{N})$ total computation,  communication of reconstructions of $4\log{N}+6$ secret-shared values, $O(\log{N})$ rounds and $O(\log{N})$ correlated randomness. This shows that malicious security with abort in honest majority MPC comes {\em free} in terms of both computation and communication.

We then consider dishonest majority MPC, where the best known semi-honest protocol achieves $2N$ online communication per party and sublinear preprocessing by using programmable pseudorandom correlation generators (PCGs). We realize malicious MPC with $4N+O(\log{N})$ online communication as well as sublinear preprocessing, matching the optimal $2\times$ communication overhead in Hazay et al. (JOC 2024). Our protocol is essentially obtained by using Sumcheck techniques to check authenticated multiplication triple relations, which requires only $N+1$ {\em standard Beaver triples} and $O(\log{N})$ random authenticated shares for $N$ semi-honestly generated authenticated triples. Compared to the FLIOP-based checking mechanism (Boyle et al. CRYPTO 2022) that requires $O(\sqrt{N})$ communication and $O(N^{1.5})$ computation, we do not introduce any cryptographic assumption beyond PCGs, and have $O(N)$ computation.



## 2025/178

* Title: Improved Differential and Linear Cryptanalysis on Round-Reduced SIMON
* Authors: Chao Niu, Muzhou Li, Jifu Zhang, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/178)
* [Download](https://eprint.iacr.org/2025/178.pdf)

### Abstract

SIMON is a lightweight block cipher proposed by the National Security Agency.
According to previous cryptanalytic results on SIMON, differential and linear cryptanalysis are the two most effective attacks on it.
Usually, there are many trails sharing the same input and output differences (resp. masks).
These trails comprise the differential (resp. linear hull) and can be used together when mounting attacks.
In ASIACRYPT 2021, Leurent et al. proposed a matrix-based method on SIMON-like ciphers, where only trails whose active bits stay in a $w$-bit window are considered.
The static window in each round is chosen to be $w$ least significant bits.
They applied this efficient framework on SIMON and SIMECK, and have obtained many better differentials and linear hulls than before. For SIMON, they also found that there seems to be some potential for improvement, which should be further investigated.

In this paper, we dynamically choose window for each round to achieve better distinguishers. Benefiting from these dynamic windows, we can obtain stronger differentials and linear hulls than previously proposed for almost all versions of SIMON.
Finally, we provided the best differential/linear attacks on SIMON48, SIMON64, and SIMON96 in terms of round number, complexity, or success rate.



## 2025/179

* Title: Higher-Order Deterministic Masking with Application to Ascon
* Authors: Vahid Jahandideh, Bart Mennink, Lejla Batina
* [Permalink](https://eprint.iacr.org/2025/179)
* [Download](https://eprint.iacr.org/2025/179.pdf)

### Abstract

Side-channel attacks (SCAs) pose a significant threat to the implementations of lightweight ciphers, particularly in resource-constrained environments where masking—the primary countermeasure—is constrained by tight resource limitations.
This makes it crucial to reduce the resource and randomness requirements of masking schemes. In this work, we investigate an approach to minimize the randomness complexity of masking algorithms. Specifically, we explore the theoretical foundations of
deterministic higher-order masking, which relies solely on offline randomness present in the initial input shares and eliminates the need for online (fresh) randomness during internal computations.
We demonstrate the feasibility of deterministic masking for ciphers such as Ascon, showing that their diffusion layer can act as a refresh subcircuit. This ensures that, up to a threshold number, probes placed in different rounds remain independent. Based on this observation, we propose composition theorems for deterministic masking
schemes. On the practical side, we extend the proof of first- and second-order probing security for Ascon’s protected permutation from a single round to an arbitrary number of rounds



## 2025/180

* Title: On the Atomicity and Efficiency of Blockchain Payment Channels
* Authors: Di Wu, Shoupeng Ren, Yuman Bai, Lipeng He, Jian Liu, Wu Wen, Kui Ren, Chun Chen
* [Permalink](https://eprint.iacr.org/2025/180)
* [Download](https://eprint.iacr.org/2025/180.pdf)

### Abstract

Payment channels have emerged as a promising solution to address the performance limitations of cryptocurrencies payments, enabling efficient off-chain transactions while maintaining security guarantees. However, existing payment channel protocols, including the widely-deployed Lightning Network and the state-of-the-art Sleepy Channels, suffer from a fundamental vulnerability: non-atomic state transitions create race conditions that can lead to unexpected financial losses. We first formalize current protocols into a common paradigm and prove that this vulnerability is fundamental—any protocol following this paradigm cannot guarantee balance security due to the inherent race conditions in their design. To address this limitation, we propose a novel atomic paradigm for payment channels that ensures atomic state transitions, effectively eliminating race conditions while maintaining all desired functionalities. Based on this paradigm, we introduce Ultraviolet, a secure and efficient payment channel protocol that achieves both atomicity and high performance, while avoiding the introduction of unimplemented Bitcoin features. Ultraviolet reduces the number of required messages per transaction by half compared to existing solutions, while maintaining comparable throughput. We formally prove the security of Ultraviolet under the universal composability framework and demonstrate its practical efficiency through extensive evaluations across multiple regions. This results in a 37% and 52% reduction in latency compared to the Lightning Network and Sleepy Channels, respectively. Regarding throughput, Ultraviolet achieves performance comparable to the Lightning Network and delivers 2× the TPS of Sleepy Channels.



## 2025/181

* Title: Improved NTT and CRT-based RNR Blinding for Side-Channel and Fault Resistant Kyber
* Authors: Max Duparc, Mounir Taha
* [Permalink](https://eprint.iacr.org/2025/181)
* [Download](https://eprint.iacr.org/2025/181.pdf)

### Abstract

In this paper, we build upon the blinding methods introduced in recent years to enhance the protection of lattice-based cryptographic schemes against side-channel and fault injection attacks. Specifically, we propose a cost-efficient blinded Number Theoretic Transform (NTT) that impedes the convergence of Soft Analytical Side-Channel Attacks (SASCA), even with limited randomness sampling. Additionally, we extend the blinding mechanism based on the Chinese Remainder Theorem (CRT) and  Redundant Number Representation (RNR) introduced by Heiz and Pöppelmann by reducing the randomness sampling overhead and accelerating the verification phase.

These two blinding mechanisms are nicely compatible with each other's and, when combined, provide enhanced resistance against side-channel attacks, both classical and soft analytical, as well as fault injection attacks, while maintaining high performance and low overhead, making the approach well-suited for practical applications, particularly in resource-constrained IoT environments.



## 2025/182

* Title: Deny Whatever You Want: Dual-Deniable Public-Key Encryption
* Authors: Zhiyuan An, Fangguo Zhang
* [Permalink](https://eprint.iacr.org/2025/182)
* [Download](https://eprint.iacr.org/2025/182.pdf)

### Abstract

We introduce an enhanced requirement of deniable public key encryption that we call dual-deniability. It asks that a sender who is coerced should be able to produce fake randomness, which can explain the target ciphertext as the encryption of any alternative message under any valid key she/he desires to deny. Compared with the original notion of deniability (Canetti et al. in CRYPTO ’97, hereafter named message-deniability), this term further provides a shield for the anonymity of the receiver against coercion attacks.
      We first give a formal definition of dual-deniability, along with its weak-mode variant. For conceptual understanding, we then show dual-deniability implies semantic security and anonymity against CPA, separates full robustness, and even contradicts key-less or mixed robustness, while is (constructively) implied by key-deniability and full robustness with a minor assumption for bits encryption. As for the availability of dual-deniability, our main scheme is a generic approach from ciphertext-simulatable PKE, where we devise a subtle multi-encryption schema to hide the true message within random masking ciphertexts under plan-ahead setting. Further, we leverage the weak model to present a more efficient scheme having negligible detection probability and constant ciphertext size. Besides, we revisit the notable scheme (Sahai and Waters in STOC ’14) and show it is inherently dual-deniable. Finally, we extend the Boneh-Katz transform to capture CCA security, deriving dual-deniable and CCA-secure PKE from any selectively dual-deniable IBE under multi-TA setting. Overall our work mounts the feasibility of anonymous messaging against coercion attacks.



## 2025/183

* Title: OBLIVIATOR: Oblivious Parallel Joins and other Operators in Shared Memory Environments
* Authors: Apostolos Mavrogiannakis, Xian Wang, Ioannis Demertzis, Dimitrios Papadopoulos, Minos Garofalakis
* [Permalink](https://eprint.iacr.org/2025/183)
* [Download](https://eprint.iacr.org/2025/183.pdf)

### Abstract

We introduce oblivious parallel operators designed for both non-foreign key and foreign key equi-joins. Obliviousness ensures nothing is revealed about the data besides input/output sizes, even against a strong adversary that can observe memory access patterns.
Our solution achieves this by combining trusted hardware with efficient oblivious primitives for compaction and sorting, and two oblivious algorithms: (i) an oblivious aggregation tree, which can be described as a variation of the parallel prefix sum, customized for trusted hardware, and (ii) a novel algorithm for obliviously expanding the elements of a relation.
In the sequential setting, our oblivious join performs $4.6\times$- $5.14\times$ faster than the prior state-of-the-art solution (Krastnikov et al., VLDB 2020) on data sets of size $n=2^{24}$. In the parallel setting, our algorithm achieves a speedup of up to roughly $16\times$ over the sequential version, when running with 32 threads (becoming up to $80\times$ compared to the sequential algorithm of Krastnikov et al.).
Finally, our oblivious operators can be used independently to support other oblivious relational database queries, such as oblivious selection and oblivious group-by.



## 2025/184

* Title: NodeChain: Cheap Data Integrity Without Consensus
* Authors: Orfeas Stefanos Thyfronitis Litos, Zhaoxuan Wu, Alfredo Musumeci, Songyun Hu, James Helsby, Michael Breza, William Knottenbelt
* [Permalink](https://eprint.iacr.org/2025/184)
* [Download](https://eprint.iacr.org/2025/184.pdf)

### Abstract

Blockchains enable decentralised applications that withstand Byzantine failures and do not need a central authority. Unfortunately, their massive replication requirements preclude their use on constrained devices.

We propose a novel blockchain-based data structure which forgoes replication without affecting the append-only nature of blockchains, making it suitable for maintaining data integrity over networks of storage-constrained devices. Our solution does not provide consensus, which is not required by our motivating application, namely securely storing sensor data of containers in cargo ships.

We elucidate the practical promise of our technique by following a multi-faceted approach: We (i) formally prove the security of our protocol in the
Universal Composition (UC) setting, as well as (ii) provide a small-scale proof-of-concept implementation, (iii) a performance simulation for large-scale deployments which showcases a reduction in storage of more than $1000$x compared to traditional blockchains, and (iv) a resilience simulation that predicts the practical effects of network jamming attacks.



## 2025/185

* Title: AutoDiVer: Automatically Verifying Differential Characteristics and Learning Key Conditions
* Authors: Marcel Nageler, Shibam Ghosh, Marlene Jüttler, Maria Eichlseder
* [Permalink](https://eprint.iacr.org/2025/185)
* [Download](https://eprint.iacr.org/2025/185.pdf)

### Abstract

Differential cryptanalysis is one of the main methods of cryptanalysis and has been applied to a wide range of ciphers. While it is very successful, it also relies on certain assumptions that do not necessarily hold in practice. One of these is the hypothesis of stochastic equivalence, which states that the probability of a differential characteristic behaves similarly for all keys. Several works have demonstrated examples where this hypothesis is violated, impacting the attack complexity and sometimes even invalidating the investigated prior attacks. Nevertheless, the hypothesis is still typically taken for granted. In this work, we propose AutoDiVer, an automatic tool that allows to thoroughly verify differential characteristics. First, the tool supports calculating the expected probability of differential characteristics while considering the key schedule of the cipher. Second, the tool supports estimating the size of the space of keys for which the characteristic permits valid pairs, and deducing conditions for these keys. AutoDiVer implements a custom SAT modeling approach and takes advantage of a combination of features of advanced SAT solvers, including approximate model counting and clause learning. To show applicability to many different kinds of block ciphers like strongly aligned, weakly aligned, and ARX ciphers, we apply AutoDiVer to GIFT, PRESENT, RECTANGLE, SKINNY, WARP, SPECK, and SPEEDY.



## 2025/186

* Title: Computing Quaternion Embeddings and Endomorphism rings of Supersingular Oriented Elliptic curves
* Authors: Maher Mamah
* [Permalink](https://eprint.iacr.org/2025/186)
* [Download](https://eprint.iacr.org/2025/186.pdf)

### Abstract

In this paper, we investigate several computational problems motivated by post-quantum cryptosystems based on isogenies and ideal class group actions on oriented elliptic curves. Our main technical contribution is an efficient algorithm for embedding the ring of integers of an imaginary quadratic field \( K \) into some maximal order of the quaternion algebra \( B_{p,\infty} \) ramified at a prime \( p \) and infinity. Assuming the Generalized Riemann Hypothesis (GRH), our algorithm runs in probabilistic polynomial time, improving upon previous results that relied on heuristics or required the factorization of \( \textnormal{disc}(K) \). Notably, this algorithm may be of independent interest.
    Our approach enhances the work of Love and Boneh on computing isogenies between \( M \)-small elliptic curves by eliminating heuristics and improving computational efficiency. Furthermore, given a quadratic order \( \mathfrak{O} \) in \( K \), we show that our algorithm reduces the computational endomorphism ring problem of \( \mathfrak{O} \)-oriented elliptic curves to the Vectorization problem in probabilistic polynomial time, assuming the conductor of \( \mathfrak{O} \) can be efficiently factorized. Previously, the best known result required the full factorization of \( \textnormal{disc}(\mathfrak{O}) \), which may be exponentially large.
    Additionally, when the conductor of \( \mathfrak{O} \) can be efficiently factorized, we establish a polynomial-time equivalence between the Quaternion Order Embedding Problem, which asks to embed a quadratic order \( \mathfrak{O} \) into a maximal order in \( B_{p,\infty} \), and computing horizontal isogenies between \( \mathfrak{O} \)-oriented elliptic curves. Leveraging this reduction, we propose a rigorous algorithm, under GRH, that solves the quaternion order embedding problem in time \( \tilde{O}(|\mathrm{disc}(\mathfrak{O})|^{1/2}) \), improving upon previous methods that required higher asymptotic time and relied on several heuristics.



## 2025/187

* Title: Asymptotic improvements to provable algorithms for the code equivalence problem
* Authors: Huck Bennett, Drisana Bhatia, Jean-François Biasse, Medha Durisheti, Lucas LaBuff, Vincenzo Pallozzi Lavorante, Philip Waitkevich
* [Permalink](https://eprint.iacr.org/2025/187)
* [Download](https://eprint.iacr.org/2025/187.pdf)

### Abstract

We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block length $n$ and dimension $k$ over any finite field $\mathbb{F}_q$, we show:
1) A deterministic algorithm running in $2^{n + o(n+q)}$ time for LCE.
2) A randomized algorithm running in $2^{n/2 + o(n+q)}$ time for LCE and PCE.
3) A quantum algorithm running in $2^{n/3 + o(n+q)}$ time for LCE and PCE.
The first algorithm complements the deterministic roughly $2^n$-time algorithm of Babai (SODA 2011) for PCE.
The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times, but only for code equivalence on \emph{random} codes and only over fields of order $q \geq 7$.



## 2025/188

* Title: BulletCT: Towards More Scalable Ring Confidential Transactions With Transparent Setup
* Authors: Nan Wang, Qianhui Wang, Dongxi Liu, Muhammed F. Esgin, Alsharif Abuadbba
* [Permalink](https://eprint.iacr.org/2025/188)
* [Download](https://eprint.iacr.org/2025/188.pdf)

### Abstract

RingCT signatures are essential components of Ring Confidential Transaction (RingCT) schemes on blockchain platforms, enabling anonymous transaction spending and significantly impacting the scalability of these schemes. This paper makes two primary contributions:

We provide the first thorough analysis of a recently developed Any-out-of-N proof in the discrete logarithm (DLOG) setting and the associated RingCT scheme, introduced by ZGSX23 (S&P '23). The proof conceals the number of the secrets to offer greater anonymity than K-out-of-N proofs and uses an efficient "K-Weight" technique for its construction. However, we identify for the first time several limitations of using Any-out-of-N proofs, such as increased transaction sizes, heightened cryptographic complexities and potential security risks. These limitations prevent them from effectively mitigating the longstanding scalability bottleneck.

We then continue to explore the potential of using K-out-of-N proofs to enhance scalability of RingCT schemes. Our primary innovation is a new DLOG-based RingCT signature that integrates a refined "K-Weight"-based K-out-of-N proof and an entirely new tag proof. The latter is the first to efficiently enable the linkability of RingCT signatures derived from the former, effectively resisting double-spending attacks.

Finally, we identify and patch a linkability flaw in ZGSX23's signature. We benchmark our scheme against this patched one to show that our scheme achieves a boost in scalability, marking a promising step forward.



## 2025/189

* Title: Experimentally studying path-finding problem between conjugates in supersingular isogeny graphs: Optimizing primes and powers to speed-up cycle finding
* Authors: Madhurima Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/189)
* [Download](https://eprint.iacr.org/2025/189.pdf)

### Abstract

We study the problem of finding a path between conjugate supersingular elliptic curves over $\mathbb{F}_{p^2}$ for a prime $p$, which is important for cycle finding in supersingular isogeny graphs. We see that for any given $p$, there is some $l$ corresponding to $p$ which accelerates the process of conjugate path-finding. Also, time-wise, the most efficient way of overviewing the graph is seeing $i(=3)$ steps at once. We have outlined methods in which the next vertex of any pseudo-random walk should be chosen to reach conjugate vertex faster. We have experimentally investigated the paths between frobenius conjugates for wide ranges of small prime $l$. We introduce sets to experimentally learn about the structure of the isogeny graphs when short cycles are present.



## 2025/190

* Title: Binary Codes for Error Detection and Correction in a Computationally Bounded World
* Authors: Jad Silbak, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2025/190)
* [Download](https://eprint.iacr.org/2025/190.pdf)

### Abstract

We study error detection and correction in a computationally bounded world, where errors are introduced by an arbitrary $\textit{polynomial-time}$ adversarial channel. Our focus is on $\textit{seeded}$ codes, where the encoding and decoding procedures can share a public random seed, but are otherwise deterministic. We can ask for either $\textit{selective}$ or $\textit{adaptive}$ security, depending on whether the adversary can choose the message being encoded before or after seeing the seed. For large alphabets, a recent construction achieves essentially optimal rate versus error tolerance trade-offs under minimal assumptions, surpassing information-theoretic limits. However, for the binary alphabet, the only prior improvement over information theoretic codes relies on non-standard assumptions justified via the random oracle model. We show the following:

$\textbf{Selective Security under LWE:}$ Under the learning with errors (LWE) assumption, we construct selectively secure codes over the binary alphabet. For error detection, our codes achieve essentially optimal rate $R \approx 1$ and relative error tolerance $\rho \approx \frac{1}{2}$. For error correction, they can uniquely correct $\rho < 1/4$ relative errors with a rate $R$ that essentially matches that of the best list-decodable codes with error tolerance $\rho$. Both cases provide significant improvements over information-theoretic counterparts. The construction relies on a novel form of 2-input correlation intractable hash functions that we construct from LWE.

$\textbf{Adaptive Security via Crypto Dark Matter:}$  Assuming the exponential security of a natural collision-resistant hash function candidate based on the ``crypto dark matter'' approach  of mixing linear functions over different moduli, we construct adaptively secure codes over the binary alphabet, for both error detection and correction. They achieve essentially the same trade-offs between error tolerance $\rho$ and rate $R$ as above, with the caveat that for error-correction they only do so for sufficiently small values of $\rho$.

Date Sujet#  Auteur
10 Feb 25 o [digest] 2025 Week 61IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal