[digest] 2025 Week 5

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

1. [2025/126] Always by Your Side: Constructing Traceable ...
2. [2025/127] A Revision of CROSS Security: Proofs and Attacks ...
3. [2025/128] Asynchronous YOSO a la Paillier
4. [2025/129] DewTwo: a transparent PCS with quasi-linear prover, ...
5. [2025/130] Symmetric Perceptrons, Number Partitioning and Lattices
6. [2025/131] On the Anonymity of Linkable Ring Signatures
7. [2025/132] Distributional Private Information Retrieval
8. [2025/133] Cryptanalysis of an Efficient Signature Based on ...
9. [2025/134] TockOwl: Asynchronous Consensus with Fault and ...
10. [2025/135] PRISM: Simple And Compact Identification and ...
11. [2025/136] Isogeny-based Cryptography using Isomorphisms of ...
12. [2025/137] FINAL bootstrap acceleration on FPGA using DSP-free ...
13. [2025/138] Preprocessing Security in Multiple Idealized Models ...
14. [2025/139] Path Privacy and Handovers: Preventing Insider ...
15. [2025/140] HELP: Everlasting Privacy through Server-Aided ...
16. [2025/141] Space-Lock Puzzles and Verifiable Space-Hard ...
17. [2025/142] hax: Verifying Security-Critical Rust Software ...
18. [2025/143] A New Way to Achieve Round-Efficient Asynchronous ...
19. [2025/144] KZH-Fold: Accountable Voting from Sublinear ...
20. [2025/145] Breaking RSA with Overclocking-induced GPU Faults
21. [2025/146] SHIFT SNARE: Uncovering Secret Keys in FALCON via ...
22. [2025/147] Efficient algorithms for the detection of ...
23. [2025/148] A Comprehensive Formal Security Analysis of OPC UA
24. [2025/149] Practical Asynchronous Distributed Key ...
25. [2025/150] On pairs of primes with small order reciprocity
26. [2025/151] Quantum function secret sharing
27. [2025/152] Efficient Quantum-safe Distributed PRF and ...
28. [2025/153] Error floor prediction with Markov models for QC- ...
29. [2025/154] Shadowfax: Combiners for Deniability
30. [2025/155] Cycles and Cuts in Supersingular L-Isogeny Graphs
31. [2025/156] TallyGuard: Privacy Preserving Tallied-as-cast ...
32. [2025/157] Breaking the Blindfold: Deep Learning-based Blind ...
33. [2025/158] Optimizing Key Recovery in Impossible Cryptanalysis ...

## 2025/126

* Title: Always by Your Side: Constructing Traceable Anonymous Credentials with Hardware-Binding
* Authors: Chang Chen, Guoyu Yang, Qi Chen, Wei Wang, Jin Li
* [Permalink](https://eprint.iacr.org/2025/126)
* [Download](https://eprint.iacr.org/2025/126.pdf)

### Abstract

With the development of decentralized identity (DID), anonymous credential (AC) technology, as well as its traceability, is receiving more and more attention. Most works introduce a trusted party (regulator) that holds a decryption key or backdoor to directly deanonymize the user identity of anonymous authentication. While some cryptographic primitives can help regulators handle complex tracing tasks among large amounts of user profiles (stored by the issuer) and authentication records (stored by the service provider), additional security primitives are still needed to ensure the privacy of other users. Besides, hardware-binding anonymous credential (hbAC) systems have been proposed to prevent credential sharing or address platform resource constraints, the traceability of hbAC has yet to be discussed.

In this paper, we introduce a public key encryption with equality test as a regulatory text for each authentication record to address the above-mentioned challenges. The security of this feature is guaranteed by the verifiability, non-frameability, and round isolation of the proposed scheme. We compared the asymptotic complexity of our scheme with other traceable AC schemes and shows our scheme has advantages in tracing tasks as well as securely outsourcing them. The key feature of our scheme is that the ability of equality test of regulatory texts is independent of the public key, but rather depends on the round identifier of the authentication. We instantiate a traceable, hardware-binding AC scheme based on smart cards and BBS+ signature and give the performance analysis of it.



## 2025/127

* Title: A Revision of CROSS Security: Proofs and Attacks for Multi-Round Fiat-Shamir Signatures
* Authors: Michele Battagliola, Riccardo Longo, Federico Pintore, Edoardo Signorini, Giovanni Tognolini
* [Permalink](https://eprint.iacr.org/2025/127)
* [Download](https://eprint.iacr.org/2025/127.pdf)

### Abstract

Signature schemes from multi-round interactive proofs are becoming increasingly relevant in post-quantum cryptography. A prominent example is CROSS, recently admitted to the second round of the NIST on-ramp standardisation process for post-quantum digital signatures. While the security of these constructions relies on the Fiat-Shamir transform, in the case of CROSS the use of the fixed-weight parallel-repetition optimisation makes the security analysis fuzzier than usual. A recent work has shown that the fixed-weight parallel repetition of a multi-round interactive proof is still knowledge sound, but no matching result appears to be known for the non-interactive version.
In this paper we provide two main results. First, we explicitly prove the EUF-CMA security of CROSS, filling a gap in the literature. We do this by showing that, in general, the Fiat-Shamir transform of an HVZK and knowledge-sound multi-round interactive proof is EUF-CMA secure. Second, we present a novel forgery attack on signatures obtained from fixed-weight repetitions of 5-round interactive proofs, substantially improving upon a previous attack on parallel repetitions due to Kales and Zaverucha. Our new attack has particular relevance for CROSS, as it shows that several parameter sets achieve a significantly lower security level than claimed, with reductions up to 24% in the worst case.



## 2025/128

* Title: Asynchronous YOSO a la Paillier
* Authors: Ivan Bjerre Damgård, Simon Holmgaard Kamp, Julian Loss, Jesper Buus Nielsen
* [Permalink](https://eprint.iacr.org/2025/128)
* [Download](https://eprint.iacr.org/2025/128.pdf)

### Abstract

We present the first complete asynchronous MPC protocols for the YOSO (You Speak Only Once) setting. Our protocols rely on threshold additively homomorphic Paillier encryption and are adaptively secure. We rely on the paradigm of Blum et al. (TCC `20) in order to recursively refresh the setup needed for running future steps of YOSO MPC, but replace any use of heavy primitives such as threshold fully homomorphic encryption in their protocol with more efficient alternatives. In order to obtain an efficient YOSO MPC protocol, we also revisit the consensus layer upon which our protocol is built. To this end, we present a novel total-order broadcast protocol with subquadratic communication complexity in the total number $M$ of parties in the network and whose complexity is optimal in the message length. This improves on recent work of Banghale et al. (ASIACRYPT `22) by giving a simplified and more efficient broadcast extension protocol for the asynchronous setting that avoids the use of cryptographic accumulators.



## 2025/129

* Title: DewTwo: a transparent PCS with quasi-linear prover, logarithmic verifier and 4.5KB proofs from falsifiable assumptions
* Authors: Benedikt Bünz, Tushar Mopuri, Alireza Shirzad, Sriram Sridhar
* [Permalink](https://eprint.iacr.org/2025/129)
* [Download](https://eprint.iacr.org/2025/129.pdf)

### Abstract

We construct the first polynomial commitment scheme (PCS) that has a transparent setup, quasi-linear prover time,  $\log N$ verifier time, and $\log \log N$ proof size, for multilinear polynomials of size $N$. Concretely, we have the smallest proof size amongst transparent PCS, with proof size less than $4.5$KB for $N\leq 2^{30}$. We prove that our scheme is secure entirely under falsifiable assumptions about groups of unknown order. The scheme significantly improves on the prior work of Dew (PKC 2023), which has super-cubic prover time and relies on the Generic Group Model (a non-falsifiable assumption). Along the way, we make several contributions that are of independent interest: PoKEMath, a protocol for efficiently proving that an arbitrary predicate over committed integer vectors holds; SIPA, a bulletproofs-style inner product argument in groups of unknown order; we also distill out what prior work required from the Generic Group Model and frame this as a falsifiable assumption.



## 2025/130

* Title: Symmetric Perceptrons, Number Partitioning and Lattices
* Authors: Neekon Vafa, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2025/130)
* [Download](https://eprint.iacr.org/2025/130.pdf)

### Abstract

The symmetric binary perceptron ($\mathrm{SBP}_{\kappa}$) problem with parameter $\kappa : \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq \kappa(m/n) \cdot \sqrt{m}~.$$
The number partitioning problem ($\mathrm{NPP}_{\kappa}$) corresponds to the special case of setting $n=1$. There is considerable evidence that both problems exhibit large computational-statistical gaps.
   
In this work, we show (nearly) tight average-case hardness for these problems, assuming the worst-case hardness of standard approximate shortest vector problems on lattices.

For $\mathrm{SBP}_\kappa$, statistically, solutions exist with $\kappa(x) = 2^{-\Theta(x)}$ (Aubin, Perkins and Zdeborova, Journal of Physics 2019). For large $n$, the best that efficient algorithms have been able to achieve is a far cry from the statistical bound, namely $\kappa(x) = \Theta(1/\sqrt{x})$ (Bansal and Spencer, Random Structures and Algorithms 2020). The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kizildag, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, $\kappa(x) = \widetilde{\Theta}(1/\sqrt{x})$ is the optimal value achieved by computationally efficient algorithms.
       
We prove their conjecture assuming the worst-case hardness of approximating the shortest vector problem on lattices.

For $\mathrm{NPP}_\kappa$, statistically, solutions exist with $\kappa(m) = \Theta(2^{-m})$ (Karmarkar, Karp, Lueker and Odlyzko, Journal of Applied Probability 1986). Karmarkar and Karp's classical differencing algorithm achieves $\kappa(m) = 2^{-O(\log^2 m)}~.$
       
We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve $\kappa(m) = 2^{-\Omega(\log^3 m)}$, once again assuming the  worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor.

Our hardness results are versatile, and hold with respect to different distributions of the matrix $\mathbf{A}$ (e.g., i.i.d. uniform entries from $[0,1]$) and weaker requirements on the solution vector $\mathbf{x}$.



## 2025/131

* Title: On the Anonymity of Linkable Ring Signatures
* Authors: Xavier Bultel, Charles Olivier-Anclin
* [Permalink](https://eprint.iacr.org/2025/131)
* [Download](https://eprint.iacr.org/2025/131.pdf)

### Abstract

Security models provide a way of formalising security properties in a rigorous way, but it is sometimes difficult to ensure that the model really fits the concept that we are trying to formalise. In this paper, we illustrate this fact by showing the discrepancies between the security model of anonymity of linkable ring signatures and the security that is actually expected for this kind of signature. These signatures allow a user to sign anonymously within an ad hoc group generated from the public keys of the group members, but all their signatures can be linked together. Reading the related literature, it seems obvious that users' identities must remain hidden even when their signatures are linked, but we show that, surprisingly, almost none have adopted a security model that guarantees it. We illustrate this by presenting two counter-examples which are secure in most anonymity model of linkable ring signatures, but which trivially leak a signer's identity after only two signatures.

  A natural fix to this model, already introduced in some previous work, is proposed in a corruption model where the attacker can generate the keys of certain users themselves, which seems much more coherent in a context where the group of users can be constructed in an ad hoc way at the time of signing. We believe that these two changes make the security model more realistic. Indeed, within the framework of this model, our counter-examples becomes insecure. Furthermore, we show that most of the schemes in the literature we surveyed appear to have been designed to achieve the security guaranteed by the latest model, which reinforces the idea that the model is closer to the informal intuition of what anonymity should be in linkable ring signatures.



## 2025/132

* Title: Distributional Private Information Retrieval
* Authors: Ryan Lehmkuhl, Alexandra Henzinger, Henry Corrigan-Gibbs
* [Permalink](https://eprint.iacr.org/2025/132)
* [Download](https://eprint.iacr.org/2025/132.pdf)

### Abstract

A private-information-retrieval (PIR) scheme lets a client fetch a record from a remote database without revealing which record it fetched. Classic PIR schemes treat all database records the same but, in practice, some database records are much more popular (i.e., commonly fetched) than others. We introduce distributional PIR, a new type of PIR that can run faster than classic PIR---both asymptotically and concretely---when the popularity distribution is skewed. Distributional PIR provides exactly the same cryptographic privacy as classic PIR. The speedup comes from a relaxed form of correctness: distributional PIR guarantees that in-distribution queries succeed with good probability, while out-of-distribution queries succeed with lower probability. Because of its relaxed correctness, distributional PIR is best suited for applications where "best-effort" retrieval is acceptable. Moreover, for security, a client's decision to query the server must be independent of whether its past queries were successful.

We construct a distributional-PIR scheme that makes black-box use of classic PIR protocols, and prove a lower bound on the server runtime of a natural class of distributional-PIR schemes. On two real-world popularity distributions, our construction reduces compute costs by $5$-$77\times$ compared to existing techniques. Finally, we build CrowdSurf, an end-to-end system for privately fetching tweets, and show that distributional-PIR reduces the end-to-end server cost by $8\times$.



## 2025/133

* Title: Cryptanalysis of an Efficient Signature Based on Isotropic Quadratic Forms
* Authors: Henry Bambury, Phong Q. Nguyen
* [Permalink](https://eprint.iacr.org/2025/133)
* [Download](https://eprint.iacr.org/2025/133.pdf)

### Abstract

We present a key-recovery attack on DEFI, an efficient signature scheme proposed recently by Feussner and Semaev, and based on isotropic quadratic forms, borrowing from both multivariate and lattice cryptography.
Our lattice-based attack is partially heuristic, but works on all proposed parameters: experimentally, it recovers the secret key in a few minutes, using less than ten (message,signature) pairs.



## 2025/134

* Title: TockOwl: Asynchronous Consensus with Fault and Network Adaptability
* Authors: Minghang Li, Qianhong Wu, Zhipeng Wang, Bo Qin, Bohang Wei, Hang Ruan, Shihong Xiong, Zhenyang Ding
* [Permalink](https://eprint.iacr.org/2025/134)
* [Download](https://eprint.iacr.org/2025/134.pdf)

### Abstract

BFT protocols usually have a waterfall-like degradation in performance in the face of crash faults. Some BFT protocols may not experience sudden performance degradation under crash faults. They achieve this at the expense of increased communication and round complexity in fault-free scenarios. In a nutshell, existing protocols lack the adaptability needed to perform optimally under varying conditions.

We propose TockOwl, the first asynchronous consensus protocol with fault adaptability. TockOwl features quadratic communication and constant round complexity, allowing it to remain efficient in fault-free scenarios. TockOwl also possesses crash robustness, enabling it to maintain stable performance when facing crash faults. These properties collectively ensure the fault adaptability of TockOwl.

Furthermore, we propose TockOwl+ that has network adaptability. TockOwl+ incorporates both fast and slow tracks and employs hedging delays, allowing it to achieve low latency comparable to partially synchronous protocols without waiting for timeouts in asynchronous environments. Compared to the latest dual-track protocols, the slow track of TockOwl+ is simpler, implying shorter latency in fully asynchronous environments.



## 2025/135

* Title: PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies
* Authors: Andrea Basso, Giacomo Borin, Wouter Castryck, Maria Corte-Real Santos, Riccardo Invernizzi, Antonin Leroux, Luciano Maino, Frederik Vercauteren, Benjamin Wesolowski
* [Permalink](https://eprint.iacr.org/2025/135)
* [Download](https://eprint.iacr.org/2025/135.pdf)

### Abstract

The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers.
In this work, we first build a two-round identification protocol whose security reduces to this problem.  The challenge consists of a random large prime $q$ and the prover simply replies with an efficient representation of an isogeny of degree $q$ from its public key.
Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model.
Our optimized C implementation of the signature scheme shows that signing is roughly $1.8\times$ faster than all SQIsign variants, whereas verification is $1.4\times$ times slower.  The sizes of the public key and signature are comparable to existing schemes.



## 2025/136

* Title: Isogeny-based Cryptography using Isomorphisms of Superspecial Abelian Surfaces
* Authors: Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer
* [Permalink](https://eprint.iacr.org/2025/136)
* [Download](https://eprint.iacr.org/2025/136.pdf)

### Abstract

We investigate the algorithmic problem of computing isomorphisms between products of supersingular elliptic curves, given their endomorphism rings. This computational problem seems to be difficult when the domain and codomain are fixed, whereas we provide efficient algorithms to compute isomorphisms when part of the codomain is built during the construction. We propose an authentication protocol whose security relies on this asymmetry. Its most prominent feature is that the endomorphism rings of the elliptic curves are not hidden. Furthermore, it does not require a trusted setup.
Quickly after this preprint was published, Benjamin Wesolowski found a way to solve efficiently Problem 5.1 that we assumed to be hard. This kills our authentication protocol.



## 2025/137

* Title: FINAL bootstrap acceleration on FPGA using DSP-free constant-multiplier NTTs
* Authors: Jonas Bertels, Hilder V. L. Pereira, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/137)
* [Download](https://eprint.iacr.org/2025/137.pdf)

### Abstract

This work showcases Quatorze-bis, a state-of-the-art Number Theoretic Transform circuit for TFHE-like cryptosystems on FPGAs. It contains a novel modular multiplication design for modular multiplication with a constant for a constant modulus. This modular multiplication design does not require any DSP units or any dedicated multiplier unit, nor does it require extra logic when compared to the state-of-the-art modular multipliers. Furthermore, we present an implementation of a constant multiplier Number Theoretic Transform design for TFHE-like schemes. Lastly, we use this Number Theoretic Transform design to implement a FINAL hardware accelerator for the AMD Alveo U55c which improves the Throughput metric of TFHE-like cryptosystems on FPGAs by a factor 9.28x over Li et al.'s NFP CHES 2024 accelerator and by 10-25% over the absolute state-of-the-art design FPT while using one third of FPTs DSPs.



## 2025/138

* Title: Preprocessing Security in Multiple Idealized Models with Applications to Schnorr Signatures and PSEC-KEM
* Authors: Jeremiah Blocki, Seunghoon Lee
* [Permalink](https://eprint.iacr.org/2025/138)
* [Download](https://eprint.iacr.org/2025/138.pdf)

### Abstract

In modern cryptography, relatively few instantiations of foundational cryptographic primitives are used across most cryptographic protocols. For example, elliptic curve groups are typically instantiated using P-256, P-384, Curve25519, or Curve448, while block ciphers are commonly instantiated with AES, and hash functions with SHA-2, SHA-3, or SHAKE. This limited diversity raises concerns that an adversary with nation-state-level resources could perform a preprocessing attack, generating a hint that might later be exploited to break protocols built on these primitives. It is often notoriously challenging to analyze and upper bound the advantage of a preprocessing attacker even if we assume that we have idealized instantiations of our cryptographic primitives (ideal permutations, ideal ciphers, random oracles, generic groups). Coretti et al. (CRYPTO/EUROCRYPT'18) demonstrated a powerful framework to simplify the analysis of preprocessing attacks, but they only proved that their framework applies when the cryptographic protocol uses a single idealized primitive. In practice, however, cryptographic constructions often utilize multiple different cryptographic primitives.

We verify that Coretti et al. (CRYPTO/EUROCRYPT'18)'s framework extends to settings with multiple idealized primitives and we apply this framework to analyze the multi-user security of (short) Schnorr Signatures and the CCA-security of PSEC-KEM against pre-processing attackers in the Random Oracle Model (ROM) plus the Generic Group Model (GGM). Prior work of Blocki and Lee (EUROCRYPT'22) used complicated compression arguments to analyze the security of {\em key-prefixed} short Schnorr signatures where the random oracle is salted with the user's public key. However, the security analysis did not extend to standardized implementations of Schnorr Signatures (e.g., BSI-TR-03111 or ISO/IEC 14888-3) which do not adopt key-prefixing, but take other measures to protect against preprocessing attacks by disallowing signatures that use a preimage of $0$.  Blocki and Lee (EUROCRYPT'22) left the (in)security of such "nonzero Schnorr Signature" constructions as an open question. We fully resolve this open question demonstrating that (short) nonzero Schnorr Signatures are also secure against preprocessing attacks. We also analyze PSEC-KEM in the ROM+GGM demonstrating that this Key Encapsulation Mechanism (KEM) is CPA-secure against preprocessing attacks.



## 2025/139

* Title: Path Privacy and Handovers: Preventing Insider Traceability Attacks During Secure Handovers
* Authors: Rabiah Alnashwan, Benjamin Dowling, Bhagya Wimalasiri
* [Permalink](https://eprint.iacr.org/2025/139)
* [Download](https://eprint.iacr.org/2025/139.pdf)

### Abstract

The rise of 5G and IoT has shifted secure communication from centralized and homogeneous to a landscape of heterogeneous mobile devices constantly travelling between myriad networks. In such environments, it is desirable for devices to securely extend their connection from one network to another, often referred to as a handover. In this work we introduce the first cryptographic formalisation of secure handover schemes. We leverage our formalisation to propose path privacy, a novel security property for handovers that has hitherto remained unexplored. We further develop a syntax for secure handovers, and identify security properties appropriate for secure handover schemes. Finally, we introduce a generic handover scheme that captures all the strong notions of security we have identified, combining our novel path privacy concept with other security properties characteristic to existing handover schemes, demonstrating the robustness and versatility of our framework.



## 2025/140

* Title: HELP: Everlasting Privacy through Server-Aided Randomness
* Authors: Yevgeniy Dodis, Jiaxin Guan, Peter Hall, Alison Lin
* [Permalink](https://eprint.iacr.org/2025/140)
* [Download](https://eprint.iacr.org/2025/140.pdf)

### Abstract

Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker.

In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices).

We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).



## 2025/141

* Title: Space-Lock Puzzles and Verifiable Space-Hard Functions from Root-Finding in Sparse Polynomials
* Authors: Nico Döttling, Jesko Dujmovic, Antoine Joux
* [Permalink](https://eprint.iacr.org/2025/141)
* [Download](https://eprint.iacr.org/2025/141.pdf)

### Abstract

Timed cryptography has initiated a paradigm shift in the design of cryptographic protocols: Using timed cryptography we can realize tasks fairly, which is provably out of range of standard cryptographic concepts. To a certain degree, the success of timed cryptography is rooted in the existence of efficient protocols based on the sequential squaring assumption.

    In this work, we consider space analogues of timed cryptographic primitives, which we refer to as space-hard primitives. Roughly speaking, these notions require honest protocol parties to invest a certain amount of space and provide security against space constrained adversaries. While inefficient generic constructions of timed-primitives from strong assumptions such as indistinguishability obfuscation can be adapted to the space-hard setting, we currently lack concrete and versatile algebraically structured assumptions for space-hard cryptography.
 
    In this work, we initiate the study of space-hard primitives from concrete algebraic assumptions relating to the problem of root-finding of sparse polynomials. Our motivation to study this problem is a candidate construction of VDFs by Boneh et al. (CRYPTO 2018) which are based on the hardness of inverting permutation polynomials. Somewhat anticlimactically, our first contribution is a full break of this candidate. However, we then revise this hardness assumption by dropping the permutation requirement and considering arbitrary sparse high degree polynomials. We argue that this type of assumption is much better suited for space-hardness rather than timed cryptography. We then proceed to construct both space-lock puzzles and verifiable space-hard functions from this assumption.



## 2025/142

* Title: hax: Verifying Security-Critical Rust Software using Multiple Provers
* Authors: Karthikeyan Bhargavan, Maxime Buyse, Lucas Franceschino, Lasse Letager Hansen, Franziskus Kiefer, Jonas Schneider-Bensch, Bas Spitters
* [Permalink](https://eprint.iacr.org/2025/142)
* [Download](https://eprint.iacr.org/2025/142.pdf)

### Abstract

We present hax, a verification toolchain for Rust targeted at security-critical software such as cryptographic libraries, protocol imple- mentations, authentication and authorization mechanisms, and parsing and sanitization code. The key idea behind hax is the pragmatic observation that different verification tools are better at handling different kinds of verification goals. Consequently, hax supports multiple proof backends, including domain-specific security analysis tools like ProVerif and SSProve, as well as general proof assistants like Coq and F*. In this paper, we present the hax toolchain and show how we use it to translate Rust code to the input languages of different provers. We describe how we systematically test our translated models and our models of the Rust system libraries to gain confidence in their correctness. Finally, we briefly overview various ongoing verification projects that rely on hax.



## 2025/143

* Title: A New Way to Achieve Round-Efficient Asynchronous Byzantine Agreement
* Authors: Simon Holmgaard Kamp
* [Permalink](https://eprint.iacr.org/2025/143)
* [Download](https://eprint.iacr.org/2025/143.pdf)

### Abstract

We translate the expand-and-extract framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting.
While they use it to obtain a synchronous BA with $2^{-\lambda}$ error probability in $\lambda+1$ rounds, we make it work in asynchrony in $\lambda+3$ rounds. At the heart of their solution is a generalization of crusader agreement and graded agreement to any number of grades called proxcensus. They achieve graded consensus with $2^r+1$ grades in $r$ rounds by reducing proxcensus with $2s-1$ grades to proxcensus with $s$ grades in one round. The expand-and-extract paradigm uses proxcensus to expand binary inputs to $2^\lambda+1$ grades in $\lambda$ rounds before extracting a binary output by partitioning the grades using a $\lambda$ bit common coin. However, the proxcensus protocol by Fitzi et al. does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step.

This is resolved by attaching justifiers to all messages: forcing the adversary to choose between being ignored by the honest parties, or sending messages with certain validity properties. Using these we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. In asynchrony the extraction phase incurs a security loss of one bit which is recovered by expanding to twice as many grades using an extra round of communication. This results in a $\lambda+2$ round VABA and a $\lambda+3$ round BA, both with $2^{-\lambda}$ error probability and communication complexity matching Fitzi et al.



## 2025/144

* Title: KZH-Fold: Accountable Voting from Sublinear Accumulation
* Authors: George Kadianakis, Arantxa Zapico, Hossein Hafezi, Benedikt Bünz
* [Permalink](https://eprint.iacr.org/2025/144)
* [Download](https://eprint.iacr.org/2025/144.pdf)

### Abstract

Accumulation schemes are powerful primitives that enable distributed and incremental verifiable computation with less overhead than recursive SNARKs. However, existing schemes with constant-size accumulation verifiers, suffer from linear-sized accumulators and deciders, leading to linear-sized proofs that are unsuitable in distributed settings. Motivated by the need for bandwidth efficient accountable voting protocols, (I) We introduce KZH, a novel polynomial commitment scheme, and (II) KZH-fold, the first sublinear accumulation scheme where the verifier only does $3$ group scalar multiplications and $O(n^{1/2})$ accumulator size and decider time. Our scheme generalizes to achieve accumulator and decider complexity of $k \cdot n^{1/k}$ with verifier complexity $k$. Using the BCLMS compiler, (III) we build an IVC/PCD scheme with sublinear proof and decider. (IV) Next, we propose a new approach to non-uniform IVC, where the cost of proving a step is proportional only to the size of the step instruction circuit, and unlike previous approaches, the witness size is not linear in the number of instructions. (V) Leveraging these advancements, we demonstrate the power of KZH-fold by implementing an accountable voting scheme using a novel signature aggregation protocol supporting millions of participants, significantly reducing communication overhead and verifier time compared to BLS-based aggregation. We implemented and benchmarked our protocols and KZH-fold achieves a 2000x reduction in communication and a 50x improvement in decider time over Nova when proving 2000 Poseidon hashes, at the cost of 3x the prover time.



## 2025/145

* Title: Breaking RSA with Overclocking-induced GPU Faults
* Authors: Reuven Yakar, Avishai Wool, Eyal Ronen
* [Permalink](https://eprint.iacr.org/2025/145)
* [Download](https://eprint.iacr.org/2025/145.pdf)

### Abstract

Overclocking is a a supported functionality of Nvidia GPUs, and is a common performance enhancement practice. However, overclocking poses a danger for cryptographic applications. As the temperature in the overclocked GPU increases, spurious computation faults occur. Coupled with well known fault attacks against RSA implementations, one can expect such faults to allow compromising RSA private keys during decryption or signing.

We first validate this hypothesis: We evaluate two commercial-grade GPU-based implementations of RSA within openSSL (called RNS and MP), under a wide range of overclocking levels and temperatures, and demonstrate that both implementations are vulnerable.

However, and more importantly, we show for the first time that even if the GPU is benignly overclocked to a seemingly ``safe'' rate, a successful attack can still be mounted, over the network, by simply sending requests at an aggressive rate to increase the temperature. Hence, setting any level of overclocking on the GPU is risky.

Moreover, we observe a huge difference in the implementations'
vulnerability: the rate of RSA breaks for RNS is 4 orders of magnitude higher than that of MP. We attribute this difference to the implementations' memory usage patterns: RNS makes heavy use of the GPU's global memory, which is accessed via both the Unified (L1) cache and the L2 cache; MP primarily uses ``shared'' on-chip memory, which is local to each GPU Streaming MultiProcessor (SM) and is uncached,  utilizing the memory banks used for the L1 cache. We believe that the computation faults are caused by reads from the global memory, which under a combination of overclocking, high temperature and high memory contention, occasionally return stale values.



## 2025/146

* Title: SHIFT SNARE: Uncovering Secret Keys in FALCON via Single-Trace Analysis
* Authors: Jinyi Qiu, Aydin Aysu
* [Permalink](https://eprint.iacr.org/2025/146)
* [Download](https://eprint.iacr.org/2025/146.pdf)

### Abstract

This paper presents a novel single-trace side-channel attack on FALCON---a lattice-based post-quantum digital signature protocol recently approved for standardization by NIST. We target the discrete Gaussian sampling operation within the FALCON key generation scheme and use a single power measurement trace to succeed. Notably, negating the 'shift right 63-bit' operation (for 64-bit values) leaks critical information about the '-1' vs. '0' assignments to intermediate coefficients. These leaks enable full recovery of the generated secret keys. The proposed attack is implemented on an ARM Cortex-M4 microcontroller running both reference and optimized software implementation from FALCON's NIST Round 3 package.
 Statistical analysis with 500k tests reveals a per coefficient success rate of 99.9999999478% and a full key recovery success rate of 99.99994654% for FALCON-512. This work highlights the vulnerability of current software solutions to single-trace attacks and underscores the urgent need to develop single-trace resilient software for embedded systems.



## 2025/147

* Title: Efficient algorithms for the detection of $(N,N)$-splittings and endomorphisms
* Authors: Maria Corte-Real Santos, Craig Costello, Sam Frengley
* [Permalink](https://eprint.iacr.org/2025/147)
* [Download](https://eprint.iacr.org/2025/147.pdf)

### Abstract

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally $(N, N)$-split for each integer $N \leq 11$. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime $p$ is 100 bits, the attack is sped up by a factor of $25$; when the underlying prime is 200 bits, the attack is sped up by a factor of $42$; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of $160$. Furthermore, we describe a more general algorithm to find endomorphisms of superspecial genus 2 Jacobians.



## 2025/148

* Title: A Comprehensive Formal Security Analysis of OPC UA
* Authors: Vincent Diemunsch, Lucca Hirschi, Steve Kremer
* [Permalink](https://eprint.iacr.org/2025/148)
* [Download](https://eprint.iacr.org/2025/148.pdf)

### Abstract

OPC UA is a standardized Industrial Control System (ICS) protocol, deployed in critical infrastructures, that aims to ensure security. The forthcoming version 1.05 includes major changes in the underlying cryptographic design, including a Diffie-Hellmann based key exchange, as opposed to the previous RSA based version. Version 1.05 is supposed to offer stronger security, including Perfect Forward Secrecy (PFS).

We perform a formal security analysis of the security protocols specified in OPC UA v1.05 and v1.04, for the RSA-based and the new DH-based mode, using the state-of-the-art symbolic protocol verifier ProVerif. Compared to previous studies, our model is much more comprehensive, including the new protocol version, combination of the different sub-protocols for establishing secure channels, sessions and their management, covering a large range of possible configurations. This results in one of the largest models ever studied in ProVerif raising many challenges related to its verification mainly due to the complexity of the state machine. We discuss how we mitigated this complexity to obtain meaningful analysis results. Our analysis uncovered several new vulnerabilities, that have been reported to and acknowledged by the OPC Foundation. We designed and proposed provably secure fixes, most of which are included in the upcoming version of the standard.



## 2025/149

* Title: Practical Asynchronous Distributed Key Reconfiguration and Its Applications
* Authors: Hanwen Feng, Yingzi Gao, Yuan Lu, Qiang Tang, Jing Xu
* [Permalink](https://eprint.iacr.org/2025/149)
* [Download](https://eprint.iacr.org/2025/149.pdf)

### Abstract

In this paper, we study practical constructions of asynchronous distributed key reconfiguration ($\mathsf{ADKR}$), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation ($\mathsf{ADKG}$) protocols theoretically solve $\mathsf{ADKR}$, they fail to deliver satisfactory scalability due to cubic communication overhead, even with simplifications to the reconfiguration setting.

We introduce a more efficient \textit{share-dispersal-then-agree-and-recast} paradigm for constructing $\mathsf{ADKR}$ with preserving adaptive security. The method replaces expensive $O(n)$ asynchronous verifiable secret sharing   protocols in   classic $\mathsf{ADKG}$ with $O(n)$ cheaper dispersals of publicly-verifiable sharing transcripts;  after consensus confirms a set of finished dispersals, it selects a small $\kappa$-subset of finished dispersals for verification, reducing the total overhead to $O(\kappa n^2)$ from $O(n^3)$, where $\kappa$ is a small constant (typically $\sim$30 or less). To further optimize concrete efficiency, we propose an interactive protocol with linear communication to generate publicly verifiable secret sharing (PVSS) transcripts, avoiding computationally expensive non-interactive PVSS. Additionally, we introduce a distributed PVSS verification mechanism, minimizing redundant computations across different parties and reducing the dominating PVSS verification cost by about one-third.

Our design also enables diverse applications: (i) given a quadratic-communication asynchronous coin-flipping protocol, it implies the first quadratic-communication $\mathsf{ADKG}$; and (ii) it can   be extended to realize the first quadratic-communication asynchronous dynamic proactive secret sharing (ADPSS) protocol with adaptive security. Experimental evaluations on a global network of 256 AWS servers show up to 40\% lower latency compared to state-of-the-art $\mathsf{ADKG}$ protocols (with simplifications to the reconfiguration setting), highlighting the practicality of our $\mathsf{ADKR}$ in large-scale asynchronous systems.



## 2025/150

* Title: On pairs of primes with small order reciprocity
* Authors: Craig Costello, Gaurish Korpal
* [Permalink](https://eprint.iacr.org/2025/150)
* [Download](https://eprint.iacr.org/2025/150.pdf)

### Abstract

We give a sieving algorithm for finding pairs of primes with small multiplicative orders modulo each other. This problem is a necessary condition for obtaining constructions of $2$-cycles of pairing-friendly curves, which have found use in cryptographic applications. Our database of examples suggests that, with the exception of a well-known infinite family of such primes, instances become increasingly rare as the size of the primes increase. This leads to some interesting open questions for which we hope our database prompts further investigation.



## 2025/151

* Title: Quantum function secret sharing
* Authors: Alex B. Grilo, Ramis Movassagh
* [Permalink](https://eprint.iacr.org/2025/151)
* [Download](https://eprint.iacr.org/2025/151.pdf)

### Abstract

We propose a quantum function secret sharing scheme in which the communication is exclusively classical. In this primitive, a classical dealer distributes a secret quantum circuit $C$ by providing shares to  $p$ quantum parties. The parties on an input state $\ket{\psi}$ and a projection $\Pi$, compute values $y_i$ that they then classically communicate back to the dealer, who can then compute $\lVert\Pi C\ket{\psi}\rVert^2$ using only classical resources. Moreover,  the shares do not leak much information about the secret circuit $C$.
Our protocol for quantum secret sharing uses the Cayley path, a tool that has been extensively used to support quantum primacy claims. More concretely, the shares of $C$ correspond to randomized version of $C$ which are delegated to the quantum parties, and the reconstruction can be done by extrapolation. Our scheme has two limitations, which we prove to be inherent to our techniques: First, our scheme is only secure against single adversaries, and we show that if two parties collude, then they can break its security. Second, the evaluation done by the parties requires exponential time in the number of gates.



## 2025/152

* Title: Efficient Quantum-safe Distributed PRF and Applications: Playing DiSE in a Quantum World
* Authors: Sayani Sinha, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/152)
* [Download](https://eprint.iacr.org/2025/152.pdf)

### Abstract

We propose the first $\textit{distributed}$ version of a simple, efficient, and provably quantum-safe pseudorandom function (PRF). The distributed PRF (DPRF) supports arbitrary threshold access structures based on the hardness of the well-studied Learning with Rounding (LWR) problem. Our construction (abbreviated as $\mathsf{PQDPRF}$) practically outperforms not only existing constructions of DPRF based on lattice-based assumptions, but also outperforms (in terms of evaluation time) existing constructions of: (i) classically secure DPRFs based on discrete-log hard groups, and (ii) quantum-safe DPRFs based on any generic quantum-safe PRF (e.g. AES). The efficiency of $\mathsf{PQDPRF}$ stems from the extreme simplicity of its construction, consisting of a simple inner product computation over $\mathbb{Z}_q$, followed by a rounding to a smaller modulus $p < q$. The key technical novelty of our proposal lies in our proof technique, where we prove the correctness and post-quantum security of $\mathsf{PQDPRF}$ (against semi-honest corruptions of any less than threshold number of parties) for a polynomial $q/p$ (equivalently, "modulus to modulus")-ratio.

Our proposed DPRF construction immediately enables efficient yet quantum-safe instantiations of several practical applications, including key distribution centers, distributed coin tossing, long-term encryption of information, etc. We showcase a particular application of $\mathsf{PQDPRF}$ in realizing an efficient yet quantum-safe version of distributed symmetric-key encryption ($\mathsf{DiSE}$ -- originally proposed by Agrawal et al. in CCS 2018), which we call $\mathsf{PQ-DiSE}$. For semi-honest adversarial corruptions across a wide variety of corruption thresholds, $\mathsf{PQ-DiSE}$ substantially outperforms existing instantiations of $\mathsf{DiSE}$ based on discrete-log hard groups and generic PRFs (e.g. AES). We illustrate the practical efficiency of our $\mathsf{PQDPRF}$ via prototype implementation of $\mathsf{PQ-DiSE}$.



## 2025/153

* Title: Error floor prediction with Markov models for QC-MDPC codes
* Authors: Sarah Arpin, Jun Bo Lau, Ray Perlner, Angela Robinson, Jean-Pierre Tillich, Valentin Vasseur
* [Permalink](https://eprint.iacr.org/2025/153)
* [Download](https://eprint.iacr.org/2025/153.pdf)

### Abstract

Quasi-cyclic moderate-density parity check (QC-MDPC) code-based encryption schemes under iterative decoders offer highly-competitive performance in the quantum-resistant space of cryptography, but the decoding-failure rate (DFR) of these algorithms are not well-understood. The DFR decreases extremely rapidly as the ratio of code-length to error-bits increases, then decreases much more slowly in regimes known as the waterfall and error-floor, respectively.

This work establishes three, successively more detailed probabilistic models of the DFR for iterative decoders for QC-MPDC codes: the simplified model, the refined model for perfect keys, and the refined model for all keys. The models are built upon a Markov model introduced by Sendrier and Vasseur that closely predicts decoding behavior in the waterfall region but does not capture the error floor behavior. The simplified model introduces a modification which captures the dominant contributor to error floor behavior which is convergence to near codewords introduced by Vasseur in his PhD thesis. The refined models give more accurate predictions taking into account certain structural features of specific keys.

Our models are based on the step-by-step decoder, which is highly simplified and experimentally displays worse decoding performance than parallel decoders used in practice.  Despite the use of the simplified decoder, we obtain an accurate prediction of the DFR in the error floor and demonstrate that the error floor behavior is dominated by convergence to a near codeword during a failed decoding instance.  Furthermore, we have run this model for a simplified version of the QC-MDPC code-based cryptosystem BIKE to better ascertain whether the DFR is low enough to achieve IND-CCA2 security.  Our model for a modified version of BIKE 1 gives a DFR which is below $2^{-129.5}$, using a block length $r = 13477$ instead of the BIKE 1 parameter $r = 12323$.



## 2025/154

* Title: Shadowfax: Combiners for Deniability
* Authors: Phillip Gajland, Vincent Hwang, Jonas Janneck
* [Permalink](https://eprint.iacr.org/2025/154)
* [Download](https://eprint.iacr.org/2025/154.pdf)

### Abstract

As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining pre-quantum and post-quantum assumptions. However, this shift often introduces trade-offs in terms of efficiency, compactness, and in some cases, even security. One such example is deniability, which enables users, such as journalists or activists, to deny authorship of potentially incriminating messages. While deniability was once mainly of theoretical interest, protocols like X3DH, used in Signal and WhatsApp, provide it to billions of users. Recent work (Collins et al., PETS'25) has further bridged the gap between theory and real-world applicability. In the post-quantum setting, however, protocols like PQXDH, as well as others such as Apple’s iMessage with PQ3, do not support deniability. This work investigates how to preserve deniability in the post-quantum setting by leveraging unconditional (statistical) guarantees instead of computational assumptions - distinguishing deniability from confidentiality and authenticity.

As a case study, we present a hybrid authenticated key encapsulation mechanism (AKEM) that provides statistical deniability, while maintaining authenticity and confidentiality through a combination of pre-quantum and post-quantum assumptions. To this end, we introduce two combiners at different levels of abstraction. First, at the highest level, we propose a black-box construction that combines two AKEMs, showing that deniability is preserved only when both constituent schemes are deniable. Second, we present Shadowfax, a non-black-box combiner that integrates a pre-quantum NIKE, a post-quantum KEM, and a post-quantum ring signature. We demonstrate that Shadowfax ensures deniability in both dishonest and honest receiver settings. When instantiated, we rely on statistical security for the former, and on a pre- or post-quantum assumption in the latter. Finally, we provide an optimised, yet portable, implementation of a specific instantiation of Shadowfax yielding ciphertexts of 1781 bytes and public keys of 1449 bytes. Our implementation achieves competitive performance: encapsulation takes 1.9 million cycles and decapsulation takes 800000 cycles on an Apple M1 Pro.



## 2025/155

* Title: Cycles and Cuts in Supersingular L-Isogeny Graphs
* Authors: Sarah Arpin, Ross Bowden, James Clements, Wissam Ghantous, Jason T.. LeGrow, Krystal Maughan
* [Permalink](https://eprint.iacr.org/2025/155)
* [Download](https://eprint.iacr.org/2025/155.pdf)

### Abstract

Supersingular elliptic curve isogeny graphs underlie isogeny-based cryptography. For isogenies of a single prime degree $\ell$, their structure has been investigated graph-theoretically.
We generalise the notion of $\ell$-isogeny graphs to $L$-isogeny graphs (studied in the prime field case by Delfs and Galbraith), where $L$ is a set of small primes dictating the allowed isogeny degrees in the graph. We analyse the graph-theoretic structure of $L$-isogeny graphs. Our approaches may be put into two categories: cycles and graph cuts.

On the topic of cycles, we provide: a count for the number of non-backtracking cycles in the $L$-isogeny graph using traces of Brandt matrices; an efficiently computable estimate based on this approach; and a third ideal-theoretic count for a certain subclass of $L$-isogeny cycles. We provide code to compute each of these three counts.  

On the topic of graph cuts, we compare several algorithms to compute graph cuts which minimise a measure called the edge expansion, outlining a cryptographic motivation for doing so. Our results show that a greedy neighbour algorithm out-performs standard spectral algorithms for computing optimal graph cuts.. We provide code and study explicit examples.

Furthermore, we describe several directions of active and future research.



## 2025/156

* Title: TallyGuard: Privacy Preserving Tallied-as-cast Guarantee
* Authors: Athish Pranav Dharmalingam, Sai Venkata Krishnan, KC Sivaramakrishnan, N.S. Narayanaswamy
* [Permalink](https://eprint.iacr.org/2025/156)
* [Download](https://eprint.iacr.org/2025/156.pdf)

### Abstract

This paper presents a novel approach to verifiable vote tallying using additive  homomorphism, which can be appended to existing voting systems without modifying the underlying infrastructure.  Existing End-to-End Verifiable (E2E-V) systems like Belenios and ElectionGuard rely on distributed trust models or are vulnerable to decryption compromises, making them less suitable for general elections. Our approach introduces a tamper-evident commitment to votes through cryptographic hashes derived from homomorphic encryption schemes such as Paillier. The proposed system provides tallied-as-cast verifiability without revealing individual votes, thereby preventing coercion. The system also provides the ability to perform public verification of results. We also show that this system can be transitioned to quantum-secure encryption like Regev for future-proofing the system.  We discuss how to deploy this system in a real-world scenario, including for general political elections, analyzing the security implications and report on the limitations of this system. We believe that the proposed system offers a practical solution to the problem of verifiable vote tallying in general elections.



## 2025/157

* Title: Breaking the Blindfold: Deep Learning-based Blind Side-channel Analysis
* Authors: Azade Rezaeezade, Trevor Yap, Dirmanto Jap, Shivam Bhasin, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2025/157)
* [Download](https://eprint.iacr.org/2025/157.pdf)

### Abstract

Physical side-channel analysis (SCA) operates on the foundational assumption of access to known plaintext or ciphertext. However, this assumption can be easily invalidated in various scenarios, ranging from common encryption modes like Cipher Block Chaining (CBC) to complex hardware implementations, where such data may be inaccessible. Blind SCA addresses this challenge by operating without the knowledge of plaintext or ciphertext. Unfortunately, prior such approaches have shown limited success in practical settings.

In this paper, we introduce the Deep Learning-based Blind Side-channel Analysis (DL-BSCA) framework, which leverages deep neural networks to recover secret keys in blind SCA settings. In addition, we propose a novel labeling method, Multi-point Cluster-based (MC) labeling, accounting for dependencies between leakage variables by exploiting multiple sample points for each variable, improving the accuracy of trace labeling.
We validate our approach across four datasets, including symmetric key algorithms (AES and Ascon) and a post-quantum cryptography algorithm, Kyber, with platforms ranging from high-leakage 8-bit AVR XMEGA to noisy 32-bit ARM STM32F4. Notably, previous methods failed to recover the key on the same datasets. Furthermore, we demonstrate the first successful blind SCA on a desynchronization countermeasure enabled by DL-BSCA and MC labeling. All experiments are validated with real-world SCA measurements, highlighting the practicality and effectiveness of our approach.



## 2025/158

* Title: Optimizing Key Recovery in Impossible Cryptanalysis and Its Automated Tool
* Authors: Jianing Zhang, Haoyang Wang
* [Permalink](https://eprint.iacr.org/2025/158)
* [Download](https://eprint.iacr.org/2025/158.pdf)

### Abstract

Impossible differential (ID) cryptanalysis and impossible boomerang (IB) cryptanalysis are two methods of impossible cryptanalysis against block ciphers. Since the seminal work introduced by Boura et al. in 2014, there have been no substantial advancements in the key recovery process for impossible cryptanalysis, particularly for the IB attack.In this paper, we propose a generic key recovery framework for impossible cryptanalysis that supports arbitrary key-guessing strategies, enabling optimal key recovery attacks. Within the framework, we provide a formal analysis of probabilistic extensions in impossible cryptanalysis for the first time. Besides, for the construction of IB distinguishers, we propose a new method for finding contradictions in multiple rounds.

By incorporating these techniques, we propose an Mixed-Integer Linear Programming (MILP)-based tool for finding full ID and IB attacks. To demonstrate the power of our methods, we applied it to several block ciphers, including SKINNY, SKINNYee, Midori, and Deoxys-BC. Our approach yields a series of optimal results in impossible cryptanalysis, achieving significant improvements in time and memory complexities. Notably, our IB attack on SKINNYee is the first 30-round attack.

Date Sujet#  Auteur
3 Feb 25 o [digest] 2025 Week 51IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal