[continued from previous message]

The FS transform is known to be sound in the random oracle model (i.e., when the hash function is modeled as a totally random function). However, when instantiating the random oracle using a concrete hash function, there are examples of protocols in
which the transformation is not sound. So far all of these examples have been contrived protocols that were specifically designed to fail.

In this work we show such an attack for a standard and popular interactive succinct argument, based on the GKR protocol, for verifying the correctness of a non-determinstic bounded-depth computation. For every choice of FS hash function, we show that a
corresponding instantiation of this protocol, which was been widely studied in the literature and used also in practice, is not (adaptively) sound when compiled with the FS transform. Specifically, we construct an explicit circuit for which we can
generate an accepting proof for a false statement.

We further extend our attack and show that for every circuit $C$ and desired output $y$, we can construct a functionally equivalent circuit $C^*$, for which we can produce an accepting proof that $C^*$ outputs $y$ (regardless of whether or not this
statement is true). This demonstrates that any security guarantee (if such exists) would have to depend on the specific implementation of the circuit $C$, rather than just its functionality.

Lastly, we also demonstrate versions of the attack that violate non-adaptive soundness of the protocol -- that is, we generate an attacking circuit that is independent of the underlying cryptographic objects. However, these versions are either less
practical (as the attacking circuit has very large depth) or make some additional (reasonable) assumptions on the underlying cryptographic primitives.



## 2025/119

* Title: SoK: PQC PAKEs - Cryptographic Primitives, Design and Security
* Authors: Nouri Alnahawi, David Haas, Erik Mauß, Alexander Wiesmaier
* [Permalink](https://eprint.iacr.org/2025/119)
* [Download](https://eprint.iacr.org/2025/119.pdf)

### Abstract

PAKE protocols are used to establish secure communication channels using a relatively short, often human memorable, password for authentication. The currently standardized PAKEs however rely on classical asymmetric (public key) cryptography. Thus, these
classical PAKEs may no longer maintain their security, should the expected quantum threat become a reality. Unlike prominent security protocols such as TLS, IKEv2 and VPN, quantum-safe PAKEs did not receive much attention from the ongoing PQC integration
efforts. Thus, there is a significant gap in awareness compared to PQC schemes that are subject to the official governmental and institutional standardization processes. In the work at hand, we provide a comprehensive overview of the existing PQC PAKEs
focusing on their design rationales, authentication methods and used asymmetric key agreement primitives. We highlight their performance and properties as per their assumed security assurances and practical usage in applications. Moreover, we address
PAKE designs that are still non-present in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference and derive future work for quantum-safe PAKEs.



## 2025/120

* Title: Module Learning with Errors with Truncated Matrices
* Authors: Katharina Boudgoust, Hannah Keller
* [Permalink](https://eprint.iacr.org/2025/120)
* [Download](https://eprint.iacr.org/2025/120.pdf)

### Abstract

The Module Learning with Errors ($\mathsf{MLWE}$) problem is one of the most commonly used hardness assumption in lattice-based cryptography. In its standard version, a matrix $\mathbf{A}$ is sampled uniformly at random over a quotient ring $R_q$, as
well as noisy linear equations in the form of $\mathbf{A} \mathbf{s}+ \mathbf{e} \bmod q$, where $\mathbf{s}$ is the secret, sampled uniformly at random over $R_q$, and $\mathbf{e}$ is the error, coming from a Gaussian distribution. Many previous works
have focused on variants of $\mathsf{MLWE}$, where the secret and/or the error are sampled from different distributions. Only few works have focused on different distributions for the matrix $\mathbf{A}$. One variant proposed in the literature is to
consider matrix distributions where the low-order bits of a uniform $\mathbf{A}$ are deleted. This seems a natural approach in order to save in bandwidth. We call it truncated $\mathsf{MLWE}$.

In this work, we show that the hardness of standard $\mathsf{MLWE}$ implies the hardness of truncated $\mathsf{MLWE}$, both for search and decision versions. Prior works only covered the search variant and relied on the (module) $\mathsf{NTRU}$
assumption, limitations which we are able to overcome. Overall, we provide two approaches, offering different advantages. The first uses a general Rényi divergence argument, applicable to a wide range of secret/error distributions, but which only works
for the search variants of (truncated) $\mathsf{MLWE}$. The second applies to the decision versions, by going through an intermediate variant of $\mathsf{MLWE}$, where additional hints on the secret are given to the adversary. However, the reduction
makes use of discrete Gaussian distributions.



## 2025/121

* Title: On symbolic computations over arbitrary commutative rings and cryptography with the temporal Jordan-Gauss graphs.
* Authors: Vasyl Ustimenko
* [Permalink](https://eprint.iacr.org/2025/121)
* [Download](https://eprint.iacr.org/2025/121.pdf)

### Abstract

The paper is dedicated to Multivariate Cryptography over general commutative ring K and protocols of symbolic computations for safe delivery of multivariate maps. We consider itera-tive algorithm of generation of multivariate maps of prescribed degree or
density with the trapdoor accelerator, i.e. piece of information which allows to compute the reimage of the map in polynomial time. The concept of Jordan-Gauss temporal graphs is used for the obfus-cation of known graph based public keys and
constructions of new cryptosystems. We sug-gest use of the platforms of Noncommutative Cryptography defined in terms of Multivariate Cryptography over K for the conversion of Multivariate Public Keys into El Gamal type Cryptosystems. Some new platforms
are introduced.



## 2025/122

* Title: Qelect: Lattice-based Single Secret Leader Election Made Practical
* Authors: Yunhao Wang, Fan Zhang
* [Permalink](https://eprint.iacr.org/2025/122)
* [Download](https://eprint.iacr.org/2025/122.pdf)

### Abstract

In a single secret leader election (SSLE) protocol, all parties collectively and obliviously elect one leader. No one else should learn its identity unless it reveals itself as the leader. The problem is first formalized by Boneh \textit{et al.} (AFT'20),
which proposes an efficient construction based on the Decision Diffie-Hellman (DDH) assumption. Considering the potential risk of quantum computers, several follow-ups focus on designing a post-quantum secure SSLE protocol based on pure lattices or
fully homomorphic encryption. However, no concrete benchmarks demonstrate the feasibility of deploying such heavy cryptographic primitives.

In this work, we present Qelect, the first practical constant-round post-quantum secure SSLE protocol. We first adapt the commitment scheme in Boneh \textit{et al.} (AFT'23) into a \textit{multi-party randomizable commitment} scheme, and propose our
novel construction based on an adapted version of ring learning with errors (RLWE) problem. We then use it as a building block and construct a \textit{constant-round} single secret leader election (crSSLE) scheme. We utilize the single instruction
multiple data (SIMD) property of a specific threshold fully homomorphic encryption (tFHE) scheme to evaluate our election circuit efficiently. Finally, we built Qelect from the crSSLE scheme, with performance optimizations including a preprocessing phase
to amortize the local computation runtime and a retroactive detection phase to avoid the heavy zero-knowledge proofs during the election phase. Qelect achieves asymptotic improvements and is concretely practical. We implemented a prototype of Qelect and
evaluated its performance in a WAN. Qelect is at least two orders of magnitude faster than the state-of-the-art.



## 2025/123

* Title: Falcon on ARM Cortex-M4: an Update
* Authors: Thomas Pornin
* [Permalink](https://eprint.iacr.org/2025/123)
* [Download](https://eprint.iacr.org/2025/123.pdf)

### Abstract

This note reports new implementation results for the Falcon signature algorithm on an ARM Cortex-M4 microcontroller. Compared with our previous implementation (in 2019), runtime cost has been about halved.



## 2025/124

* Title: GPU Implementations of Three Different Key-Switching Methods for Homomorphic Encryption Schemes
* Authors: Ali Şah Özcan, Erkay Savaş
* [Permalink](https://eprint.iacr.org/2025/124)
* [Download](https://eprint.iacr.org/2025/124.pdf)

### Abstract

In this work, we report on the latest GPU implementations of the three well-known methods for the key switching operation, which is critical for Fully Homomorphic Encryption (FHE). Additionally, for the first time in the literature, we provide
implementations of all three methods in GPU for leveled CKKS schemes. To ensure a fair comparison, we employ the most recent GPU implementation of the number-theoretic transform (NTT), which is the most time-consuming operation in key switching, and
evaluate the performance across two fully homomorphic schemes: BFV and CKKS. Furthermore, we highlight the advantages and shortcomings of the three methods in the context of leveled HE schemes, and discuss other aspects such as memory requirements. Our
GPU implementation is integrated with HEonGPU Library and delivers up to a ×380 improvement in execution time compared to the Microsoft SEAL Library. Since key switching is a specialized form of the external product common in many HE schemes, our
results are directly relevant to time-intensive homomorphic operations such as relinearization and rotation. As homomorphic rotation is one of the most dominant operations in bootstrapping, our results are also applicable in bootstrapping algorithms of
BFV, BGV and CKKS schemes.



## 2025/125

* Title: A Privacy Model for Classical & Learned Bloom Filters
* Authors: Hayder Tirmazi
* [Permalink](https://eprint.iacr.org/2025/125)
* [Download](https://eprint.iacr.org/2025/125.pdf)

### Abstract

The Classical Bloom Filter (CBF) is a class of Probabilistic Data Structures (PDS) for handling Approximate Query Membership (AMQ). The Learned Bloom Filter (LBF) is a recently proposed class of PDS that combines the Classical Bloom Filter with a
Learning Model while preserving the Bloom Filter's one-sided error guarantees. Bloom Filters have been used in settings where inputs are sensitive and need to be private in the presence of an adversary with access to the Bloom Filter through an API or in
the presence of an adversary who has access to the internal state of the Bloom Filter. Prior work has investigated the privacy of the Classical Bloom Filter providing attacks and defenses under various privacy definitions. In this work, we formulate a
stronger differential privacy-based model for the Bloom Filter. We propose constructions of the Classical and Learned Bloom Filter that satisfy $(\epsilon, 0)$-differential privacy. This is also the first work that analyses and addresses the privacy of
the Learned Bloom Filter under any rigorous model, which is an open problem.

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