## 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

[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)