[continued from previous message]

## 2025/764

* Title: Security of a secret sharing protocol on the Qline
* Authors: Alex B. Grilo, Lucas Hanouz, Anne Marin
* [Permalink](https://eprint.iacr.org/2025/764)
* [Download](https://eprint.iacr.org/2025/764.pdf)

### Abstract

Secret sharing is a fundamental primitive in cryptography, and it can be achieved even with perfect security. However, the distribution of shares requires computational assumptions, which can compromise the overall security of the protocol. While
traditional Quantum Key Distribution (QKD) can maintain security, its widespread deployment in general networks would incur prohibitive costs.

In this work, we present a quantum protocol for distributing additive secret sharing of 0, which we prove to be composably secure within the Abstract Cryptography framework.
Moreover, our protocol targets the Qline, a recently proposed quantum network architecture designed to simplify and reduce the cost of quantum communication.
Once the shares are distributed, they can be used to securely perform a wide range of cryptographic tasks, including standard additive secret sharing, anonymous veto, and symmetric key establishment.



## 2025/765

* Title: ZKPoG: Accelerating WitGen-Incorporated End-to-End Zero-Knowledge Proof on GPU
* Authors: Muyang Li, Yueteng Yu, Bangyan Wang, Xiong Fan, Shuwen Deng
* [Permalink](https://eprint.iacr.org/2025/765)
* [Download](https://eprint.iacr.org/2025/765.pdf)

### Abstract

Zero-Knowledge Proof (ZKP) is a cornerstone technology in privacy-preserving computing, addressing critical challenges in domains such as finance and healthcare by ensuring data confidentiality during computation. However, the high computational overhead
of ZKP, particularly in proof generation and verification, limits its scalability and usability in real-world applications. Existing efforts to accelerate ZKP primarily focus on specific components, such as polynomial commitment schemes or elliptic curve
operations, but fail to deliver an integrated, flexible, and efficient end-to-end solution that includes witness generation.

In this work, we present ZKPoG, a GPU-based ZKP acceleration platform that achieves full end-to-end optimization. ZKPoG addresses three key challenges: (1) designing a witness-generation-incorporated flow for Plonkish circuits, enabling seamless
integration of frontend and backend with GPU acceleration; (2) optimizing memory usage to accommodate large-scale circuits on affordable GPUs with limited memory; and (3) introducing an automated compiler for custom gates, simplifying adaptation to
diverse applications. Experimental results on an NVIDIA RTX 4090 GPU show on average $22.8\times$ end-to-end acceleration compared to state-of-the-art CPU implementations and on average $12.7\times$ speedup over existing GPU-based approaches.



## 2025/766

* Title: Unbiasable Verifiable Random Functions from Generic Assumptions
* Authors: Nicholas Brandt
* [Permalink](https://eprint.iacr.org/2025/766)
* [Download](https://eprint.iacr.org/2025/766.pdf)

### Abstract

We present conceptually simple constructions of verifiable random functions (VRF) that fulfill strong notions of unbiasability recently introduced by Giunta and Stewart [EC:GS24]. VRFs with such strong properties were previously only known in the random
oracle model or from the decisional Diffie–Hellman assumption with preprocessing. In contrast, our constructions are based on generic assumptions and are thus the first to be plausibly post-quantum secure. Moreover, our constructions fulfill several
additional properties such as:
• If the underlying VRF is aggregate, key-homomorphic or computable in \(\mathsf{NC}^1\), then so is our VRF.
• For any verification key, the VRF output has almost the same min-entropy as the VRF input.
Lastly, we outline a path towards a lattice-based VRF (without setup).



## 2025/767

* Title: ALPACA: Anonymous Blocklisting with Constant-Sized Updatable Proofs
* Authors: Jiwon Kim, Abhiram Kothapalli, Orestis Chardouvelis, Riad S. Wahby, Paul Grubbs
* [Permalink](https://eprint.iacr.org/2025/767)
* [Download](https://eprint.iacr.org/2025/767.pdf)

### Abstract

In recent years, online anonymity has become increasingly important but is under threat due to the challenges of moderating anonymous spaces. A promising cryptographic solution, known as anonymous blocklisting, allows users to post anonymously while
still enabling moderation. Moderation via anonymous blocklisting roughly works by requiring that when users post a message they attach a cryptographic proof that they did not author any posts on a “blocklist”.
Existing anonymous blocklisting schemes are unfortunately still far from achieving practical performance for large blocklists. This is essentially due to all prior works requiring a user to (cryptographically) reprocess blocklist entries many times.
Relatedly, prior works have relatively high verification times and proof sizes. In this work, we introduce ALPACA, the first anonymous blocklisting system with the property that a user only needs to do a constant amount of work per blocklist entry. Thus, our scheme has asymptotically optimal performance. Our scheme is also the first
to have verification times and proof sizes that are independent of the number of blocklist entries.
Our key technique is a new variant of incrementally verifiable computation (IVC), designed to ensure anonymity. Along the way, we introduce new definitions to formally establish security. On a mid-range laptop, ALPACA’s proof generation time is always
6.15 seconds and proof size is 25.6KBs. On a server, the verification time is always 400ms.



## 2025/768

* Title: Incompleteness in Number-Theoretic Transforms: New Tradeoffs and Faster Lattice-Based Cryptographic Applications
* Authors: Syed Mahbub Hafiz, Bahattin Yildiz, Marcos A. Simplicio Jr, Thales B. Paiva, Henrique Ogawa, Gabrielle De Micheli, Eduardo L. Cominetti
* [Permalink](https://eprint.iacr.org/2025/768)
* [Download](https://eprint.iacr.org/2025/768.pdf)

### Abstract

Lattices are the basis of most NIST-recommended post-quantum cryptography (PQC) schemes, required to thwart the threat posed by the eventual construction of large-scale quantum computers. At the same time, lattices enable more advanced cryptographic
constructions, such as fully homomorphic encryption (FHE), which is increasingly used for privacy-preserving applications like machine learning. This work delves into the efficiency and trade-off assessment of polynomial multiplication algorithms and
their applications to PQC, FHE, and other schemes. Such algorithms are at the core of lattice-based cryptography and may become a critical bottleneck when deploying PQC- and FHE-based solutions on resource-constrained devices. We propose a formal
analysis of so-called incompleteness in the Number Theoretic Transform (NTT). Although this concept is not new, our systematization shows how to optimize polynomial multiplication in quotient rings, considering factors such as the degree of
incompleteness, the associated prime moduli, constraints of the target platform, and target security level. Besides efficiency, we formally show that the systematized family of incomplete NTT variants supports a larger set of prime moduli. This property
enables new trade-offs for algorithms like the FIPS-approved module-lattice-based key encapsulation mechanism (ML-KEM) and faster amortized bootstrapping in FHE schemes. Our results include shorter ciphertexts in ML-KEM with only a modest hit in
performance and a 6-42% performance boost in the NTT computation of a state-of-the-art FHE solution.



## 2025/769

* Title: Finding the Inverse of some Shift Invariant Transformations
* Authors: Fukang Liu, Vaibhav Dixit, Santanu Sarkar, Willi Meier, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2025/769)
* [Download](https://eprint.iacr.org/2025/769.pdf)

### Abstract

We study the problem of how to find the inverse of shift invariant (SI) transformations proposed in Daemen's thesis. In particular, two of them have been used in practice: $y_i=x_i\oplus \overline{x_{i+1}}x_{i+2}$ and $y_i=x_i\oplus \overline{x_{i+1}}x_{
i+2}x_{i+3}$. The first one is the well-known $\chi$ transformation used in \textsf{SHA-3}, \textsf{Subterranean 2.0} and \textsf{Rasta}, while the second one is used in a recently proposed ZK-friendly hash function called Monolith. While the concrete
formula of the inverse of $\chi$ of arbitrary size has been given and proved by Liu et al. at JoC 2022, it remains unknown how to deduce such a formula and how to systematically study other SI transformations.
In this work, we aim to provide a general method and flow to find the inverse of SI transformations, though it is still limited to some specific types and it may not work for all such transformations. However, such a general method does shed new
insight on how to find their inverse, as we can apply this method to several different SI transformations, including the one used in Monolith. We expect that this method can be further generalized and applied to more SI transformations.



## 2025/770

* Title: ZHE: Efficient Zero-Knowledge Proofs for HE Evaluations
* Authors: Zhelei Zhou, Yun Li, Yuchen Wang, Zhaomin Yang, Bingsheng Zhang, Cheng Hong, Tao Wei, Wenguang Chen
* [Permalink](https://eprint.iacr.org/2025/770)
* [Download](https://eprint.iacr.org/2025/770.pdf)

### Abstract

Homomorphic Encryption (HE) allows computations on encrypted data without decryption. It can be used where the users’ information are to be processed by an untrustful server, and has been a popular choice in privacy-preserving applica- tions. However,
in order to obtain meaningful results, we have to assume an honest-but-curious server, i.e., it will faithfully follow what was asked to do. If the server is malicious, there is no guarantee that the computed result is correct. The notion of verifiable
HE (vHE) is introduced to detect malicious server’s behaviors, but current vHE schemes are either more than four orders of magnitude slower than the underlying HE operations (Atapoor et. al, CIC 2024) or fast but incompatible with server- side private
inputs (Chatel et. al, CCS 2024).

In this work, we propose a vHE framework ZHE: effi- cient Zero-Knowledge Proofs (ZKPs) that prove the correct execution of HE evaluations while protecting the server’s private inputs. More precisely, we first design two new highly- efficient ZKPs for
modulo operations and (Inverse) Number Theoretic Transforms (NTTs), two of the basic operations of HE evaluations. Then we build a customized ZKP for HE evaluations, which is scalable, enjoys a fast prover time and has a non-interactive online phase. Our
ZKP is applicable to all Ring-LWE based HE schemes, such as BGV and CKKS. Finally, we implement our protocols for both BGV and CKKS and conduct extensive experiments on various HE workloads. Compared to the state-of-the-art works, both of our prover time
and verifier time are improved; especially, our prover cost is only roughly 27-36× more expensive than the underlying HE operations, this is two to three orders of magnitude cheaper than state-of-the-arts.



## 2025/771

* Title: Differential Fault Attacks on TFHE-friendly cipher $\textsf{FRAST}$
* Authors: Weizhe Wang, Deng Tang
* [Permalink](https://eprint.iacr.org/2025/771)
* [Download](https://eprint.iacr.org/2025/771.pdf)

### Abstract

Differential Fault Attacks (DFAs) have recently emerged as a significant threat against stream ciphers specifically designed for Hybrid Homomorphic Encryption (HHE).
In this work, we propose DFAs on the $\textsf{FRAST}$ cipher, which is a cipher specifically tailored for Torus-based Fully Homomorphic Encryption (TFHE). The round function of $\textsf{FRAST}$ employs random S-boxes to minimize the number of rounds, and
can be efficiently evaluated in TFHE. With our specific key recovery strategy, we can mount the DFA with a few faults. Under the assumption of precise fault injection, our DFA can recover the key within one second using just 4 or 6 faults. When
discarding the assumption and considering a more practical fault model, we can still achieve key recovery in a few minutes without increasing the number of faults. To the best of our knowledge, this is the first third-party cryptanalysis on $\textsf{
FRAST}$. We also explored countermeasures to protect $\textsf{FRAST}$. Our analysis revealed that negacyclic S-boxes, a key component of TFHE-friendly ciphers, are unsuitable for incorporating linear structures to resist DFA. Consequently, we recommend
removing the negacyclic restriction in the penultimate round of FRAST and introducing non-zero linear structures into the S-boxes of the last two rounds. We believe that our work will provide valuable insights for the design of TFHE-friendly ciphers.



## 2025/772

* Title: Publicly Auditable Garbled Circuit
* Authors: San Ling, Chan Nam Ngo, Khai Hanh Tang, Huaxiong Wang
* [Permalink](https://eprint.iacr.org/2025/772)
* [Download](https://eprint.iacr.org/2025/772.pdf)

### Abstract

Generic Secure Multiparty Computation (Generic MPC) recently received much attraction in the blockchain realm as it allows mutually distrustful parties to jointly compute a global function using their private inputs while keeping them private; and more
so; the expression of the function can be done in a programmable manner (hence `generic'); as opposed to the first rising star cryptographic technique Zero-Knowledge Proof (ZKP) which only allows computation on private input of a single party (via the `
commit-and-prove' approach). While ZKP, by nature, allows public verifiability, Generic MPC is not so: Generic MPC mostly focuses on Malicious Security in which the computing result is verifiable only among the computing parties. Yet, in the blockchain
realm, public verifiability is important, as the consensus protocol is not just among the computing parties but also external servers. A few works were done to bridge this gap (albeit not in the blockchain realm), i.e., Public Auditable MPC. Public
Audtitability is a stronger property than Public Verifiability: the first one certifies the computation done in the MPC, while the latter certifies only the relation between the outputs and the inputs. However, they are non-constant round protocols and
only for Secret-Sharing-based MPC, i.e., round complexity scales linearly with the circuit multiplicative depth, while round latency is an important cost metric in the blockchain domain. We address this problem by providing a Public Auditable Garbled
Circuit protocol that is maliciously secure, publicly auditable, and constant-round. Our protocol is efficient, with only minimal overhead in terms of round, communication, and public transcript size.



## 2025/773

* Title: Exploring Adversarial Attacks on the MaSTer Truncation Protocol
* Authors: Martin Zbudila, Aysajan Abidin, Bart Preneel
* [Permalink](https://eprint.iacr.org/2025/773)
* [Download](https://eprint.iacr.org/2025/773.pdf)

### Abstract

At CANS 2024, Zbudila et al. presented MaSTer, a maliciously secure multi-party computation protocol for truncation. It allows adversaries to manipulate outputs with a bounded additive error while avoiding detection with a certain probability. In this
work, we analyse the broader implications of adversarial exploitation in probabilistic truncation protocols, specifically in relation to MaSTer. We propose three attack strategies aimed at inducing misclassification in deep neural network (DNN) inference.
Our empirical evaluation across multiple datasets demonstrates that while adversarial influence remains negligible under realistic constraints, certain configurations and network architectures exhibit increased vulnerability. By improving the
understanding of the risks associated with probabilistic truncation protocols in privacy-preserving machine learning, our work demonstrates that the MaSTer protocol is robust in realistic settings.



## 2025/774

* Title: Towards a Modern LLL Implementation
* Authors: Léo Ducas, Ludo N. Pulles, Marc Stevens
* [Permalink](https://eprint.iacr.org/2025/774)
* [Download](https://eprint.iacr.org/2025/774.pdf)

### Abstract

We propose BLASter, a proof of concept LLL implementation that demonstrates the practicality of multiple theoretical improvements. The implementation uses the segmentation strategy from Neumaier–Stehlé (ISSAC 2016), parallelism and Seysen's reduction
that was proposed by Kirchner–Espitau–Fouque (CRYPTO 2021) and implemented in OptLLL, and the BLAS library for linear algebra operations. It consists of only 1000 significant lines of C++ and Python code, and is made publicly available.

For q-ary lattices that fplll can handle without multiprecision (dimension <180), BLASter is considerably faster than fplll, OptLLL and Ryan–Heninger's flatter (CRYPTO 2023), without degrading output reduction quality. Thanks to Seysen's reduction it
can further handle larger dimension without resorting to multiprecision, making it more than 10x faster than flatter and OptLLL, and 100x faster than fplll in dimensions 256 to 1024.

It further includes segmented BKZ and segmented deep-LLL variants. The latter provides bases as good as BKZ-15 and has a runtime that is only a couple of times more than our LLL baseline.

This remains a proof of concept: the effective use of higher precision — which is needed to handle \(\textit{all}\) lattices — has further obstacles and is left for future work. Still, this work contains many lessons learned, and is meant to motivate
and guide the development of a robust and modern lattice reduction library, which shall be much faster than fplll.



## 2025/775

* Title: AuthOr: Lower Cost Authenticity-Oriented Garbling of Arbitrary Boolean Circuits
* Authors: Osman Biçer, Ali Ajorian
* [Permalink](https://eprint.iacr.org/2025/775)
* [Download](https://eprint.iacr.org/2025/775.pdf)

### Abstract

Authenticity-oriented (previously named as privacy-free) garbling
schemes of Frederiksen et al. Eurocrypt ’15 are designed to satisfy
only the authenticity criterion of Bellare et al. ACM CCS ’12, and to be
more efficient compared to full-fledged garbling schemes. In this work,
we improve the state-of-the-art authenticity-oriented version of half gates (HG) garbling of Zahur et al. Crypto ’15 by allowing it to be bandwidth-free if any of the input wires of an AND gate is freely settable by the
garbler. Our full solution AuthOr then successfully combines the ideas
from information-theoretical garbling of Kondi and Patra Crypto ’17 and
the HG garbling-based scheme that we obtained. AuthOr has a lower
communication cost (i.e. garbled circuit or GC size) than HG garbling
without any further security assumption. Theoretically, AuthOr’s GC
size reduction over HG garbling lies in the range between 0 to 100%,
and the exact improvement depends on the circuit structure. We have
implemented our scheme and conducted tests on various circuits that are constructed by independent researchers. Our experimental results show
that in practice, the GC size gain may be up to roughly 98%.



## 2025/776

* Title: Clementine: A Collateral-Efficient, Trust-Minimized, and Scalable Bitcoin Bridge
* Authors: Ekrem Bal, Lukas Aumayr, Atacan İyidoğan, Giulia Scaffino, Hakan Karakuş, Cengiz Eray Aslan, Orfeas Stefanos Thyfronitis Litos
* [Permalink](https://eprint.iacr.org/2025/776)
* [Download](https://eprint.iacr.org/2025/776.pdf)

### Abstract

This whitepaper introduces Clementine, a secure, collateral-efficient, trust-minimized, and scalable Bitcoin bridge based on BitVM2 that enables withdrawals from rollups or other side systems to Bitcoin. Clementine proposes a new Bitcoin light client
that remains secure against adversaries controlling less than 50% of Bitcoin’s hash rate, assuming at least one honest Watchtower in a permissioned set. The protocol is collateral-efficient, reusing locked funds over time and reducing unnecessary dust
outputs through the strategic use of 0-value outputs, and scalable, enabling a single challenge per Operator to slash multiple misbehaviors. This increases throughput and reduces on-chain load without compromising security. Clementine enables trust-
minimized and efficient peg-outs from Citrea to Bitcoin, making zk-rollups on Bitcoin practical and unlocking new paths for native scalability and interoperability.



## 2025/777

* Title: Seamless Switching Between PBS and WoPBS for Scalable TFHE
* Authors: Rostin Shokri, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2025/777)
* [Download](https://eprint.iacr.org/2025/777.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) enables arbitrary and unlimited computations directly on encrypted data. Notably, the TFHE scheme allows users to encrypt bits or small numbers (4-6 bits) and compute any univariate function using programmable
bootstrapping (PBS), while simultaneously refreshing the ciphertext noise. Since both linear and non-linear functions can be evaluated using PBS, it is possible to compute arbitrary functions and circuits of unlimited depth without any accuracy loss.
Nevertheless, a major limitation of TFHE, compared to other FHE schemes, is that it operates on a single ciphertext at a time, and the underlying message size remains small. For larger messages with longer bit sizes, the execution overhead of PBS grows
exponentially with the number of message bits. A recent approach, called Without-padding PBS (WoPBS), enables computation of much larger lookup tables (10-28 bits), with the execution cost scaling linearly with the number of message bits. The significant
encoding mismatch between the PBS and WoPBS, however, complicates the use of both approaches within the same circuit execution.

In this work, we introduce novel switching algorithms that enable ciphertexts to be converted back and forth between the PBS and WoPBS contexts without impacting the input noise. Moreover, we introduce a new method to bootstrap ciphertexts within the
WoPBS context, allowing for unlimited XOR operations at negligible cost. To enhance runtime, we further introduce optimized parameters for both contexts. We validate our techniques through the homomorphic evaluation of AES encryption and decryption,
demonstrating transciphering applications that outperform related works.



## 2025/778

* Title: Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond * Authors: Pouria Fallahpour, Alex B. Grilo, Garazi Muguruza, Mahshid Riahinia * [Permalink](https://eprint.iacr.org/2025/778)
* [Download](https://eprint.iacr.org/2025/778.pdf)

### Abstract

One-way functions (OWFs) form the foundation of modern cryptography, yet their unconditional existence remains a major open question. In this work, we study this question by exploring its relation to lossy reductions, i.e., reductions $R$ for which it
holds that $I(X;R(X)) \ll n$ for all distributions $X$ over inputs of size $n$. Our main result is that either OWFs exist or any lossy reduction for any promise problem $\Pi$ runs in time $2^{\Omega(\log\tau_\Pi / \log\log n)}$, where $\tau_\Pi(n)$ is the infimum of the runtime of all (worst-case) solvers of $\Pi$ on instances of
size $n$. More precisely, by having a reduction with a better runtime, for an arbitrary promise problem $\Pi$, and by using a non-uniform advice, we construct (a family of) OWFs. In fact, our result requires a milder condition, that $R$ is lossy for
sparse uniform distributions (which we call mild-lossiness). It also extends to $f$-reductions as long as $f$ is a non-constant permutation-invariant Boolean function, which includes $\text{And-, Or-, Maj-, Parity-}$, $\text{Mod}_k$-, and $\text{
Threshold}_k$-reductions.

Additionally, we show that worst-case to average-case Karp reductions and randomized encodings are special cases of mild-lossy reductions and improve the runtime above as $2^{\Omega(\log \tau_\Pi)}$ when these mappings are considered. Restricting to weak
fine-grained OWFs, this runtime can be further improved as $\Omega(\tau_\Pi)$. Intuitively, the latter asserts that if weak fine-grained OWFs do not exist then any instance randomization of any $\Pi$ has the same runtime (up to a constant factor) as the best worst-case solver of $\Pi$.

Taking $\Pi$ as $k\text{Sat}$, our results provide sufficient conditions under which (fine-grained) OWFs exist assuming the Exponential Time Hypothesis (ETH). Conversely, if (fine-grained) OWFs do not exist, we obtain impossibilities on instance
compressions (Harnik and Naor, FOCS 2006) and instance randomizations of $k\text{Sat}$ under the ETH.
Moreover, the analysis can be adapted to studying such properties of any $\text{NP}$-complete problem.

Finally, we partially extend these findings to the quantum setting; the existence of a pure quantum mildly-lossy reduction for $\Pi$ within the runtime $2^{o(\log\tau_\Pi / \log\log n)}$ implies the existence of one-way state generators, where $\tau_\Pi$
is defined with respect to quantum solvers.



## 2025/779

* Title: Improving the Round Complexity of MiniCast
* Authors: Thomas Locher, Victor Shoup
* [Permalink](https://eprint.iacr.org/2025/779)
* [Download](https://eprint.iacr.org/2025/779.pdf)

### Abstract

For very long messages, the reliable broadcast protocol with the best communication complexity to date is the Minicast protocol of Locher & Shoup [2024]. To reliably broadcast a message $m$ to $n$ parties, Minicast has communication complexity $\sim 1.
5 |m| n$, when $|m|$ is large. However, the round complexity of Minicast is 4, which is worse than the 3 rounds of the classical protocol of Bracha. We give a new reliable broadcast protocol whose communication complexity is essentially the same as
that of Minicast, but whose round complexity is just 3. Like Minicast, our new protocol does not rely on any cryptography other than hash functions. We also give a new 2-round protocol that relies on signatures. For large $|m|$, its communication
complexity is also $\sim 1.5 |m| n$, unless the sender provably misbehaves, in which case its communication complexity may degrade to at most $\sim 2 |m| n$.



## 2025/780

* Title: The Planted Orthogonal Vectors Problem
* Authors: David Kühnemann, Adam Polak, Alon Rosen
* [Permalink](https://eprint.iacr.org/2025/780)
* [Download](https://eprint.iacr.org/2025/780.pdf)

### Abstract

In the $k$-Orthogonal Vectors ($k$-OV) problem we are given $k$ sets, each containing $n$ binary vectors of dimension $d=n^{o(1)}$, and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a
central problem in fine-grained complexity, conjectured to require $n^{k-o(1)}$ time in the worst case.

We propose a way to plant a solution among vectors with i.i.d. $p$-biased entries, for appropriately chosen $p$, so that the planted solution is the unique one. Our conjecture is that the resulting $k$-OV instances still require time $n^{k-o(1)}$ to
solve, on average.

Our planted distribution has the property that any subset of strictly less than $k$ vectors has the same marginal distribution as in the model distribution, consisting of i.i.d. $p$-biased random vectors. We use this property to give average-case search-
to-decision reductions for $k$-OV.



## 2025/781

* Title: Generalizing the Augot-Finiasz PKE to Other Code Classes
* Authors: Anmoal Porwal, Anna Baumeister, Violetta Weger, Antonia Wachter-Zeh, Pierre Loidreau
* [Permalink](https://eprint.iacr.org/2025/781)
* [Download](https://eprint.iacr.org/2025/781.pdf)

### Abstract

The Augot-Finiasz system is a public-key encryption (PKE) scheme based on Reed-Solomon codes and was later followed by analogous versions in the rank metric. Although these schemes were eventually broken, their fundamental idea remains exciting. Notably,
these schemes are significantly different from the McEliece system as there is no need to hide the code and, as such, promise much better parameters. Further, they admit a simple description where both the public key and ciphertext are just corrupted
codewords of a public code. An interesting question is whether the general idea can be made to work, i.e., resist all known attacks, by using other code classes. This paper shows how to generalize the Augot-Finiasz system to other code families. We
reduce the correctness and security of this framework to simple assertions about the code class with which it is instantiated. Specifically, its correctness is equivalent to the existence of an efficient error-erasure decoder, and its security reduces to
an easily understood hardness assumption, called "supercode decoding", close to the syndrome decoding problem.



## 2025/782

* Title: AES Is Not Enough: the Block Ciphers Zoo Goes Homormorphic (over TFHE) * Authors: Daphné Trama, Aymen Boudguiga, Renaud Sirdey
* [Permalink](https://eprint.iacr.org/2025/782)
* [Download](https://eprint.iacr.org/2025/782.pdf)

### Abstract

The dream of achieving data privacy during external computations has
become increasingly concrete in recent years. Indeed, since the early days of Fully Homomorphic Encryption (FHE) more than a decade ago, new cryptosystems and techniques have constantly optimized the efficiency of computation on encrypted data.
However, one of the main disadvantages of FHE, namely its significant ciphertext expansion factor, remains at the center of the efficiency bottleneck of FHE schemes. To tackle the issue of slow uplink FHE data transmission, we use transciphering. With
transciphering, the client naturally encrypts its data under a symmetric scheme and sends them to the server with (once and for all) an FHE encryption of the symmetric scheme’s key. With its larger computing power, the server then evaluates the
symmetric scheme’s decryption algorithm within the homomorphic domain to obtain homomorphic ciphertexts that allow it to perform the requested calculations.
Since the first use of this method a bit more than ten years ago, papers on the homomorphic evaluation of AES have been numerous. And as the AES execution is the application chosen by NIST in the FHE part of its recent call for proposals on threshold
encryption, the stakes of such work go up another level. But what about other standardized block ciphers? Is the AES the more efficient option? In this work, we leverage on two methods which have successfully been applied to the
homomorphic evaluation of AES to study several state-of-the-art symmetric block ciphers (namely CLEFIA, PRESENT, PRINCE, SIMON, SKINNY). That is to say, we implement a representative set of symmetric block ciphers using TFHE.
These implementations allow us to compare the efficiency of this set of symmetric schemes and to categorize them. We highlight the characteristics of block ciphers that are fast to execute in the homomorphic domain and those that are particularly costly.
Finally, this classification of operation types enables us to sketch out what the ideal block cipher for transciphering homomorphic data in integer mode might look like.



## 2025/783

* Title: Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
* Authors: Itai Dinur, Nathan Keller, Avichai Marmor
* [Permalink](https://eprint.iacr.org/2025/783)
* [Download](https://eprint.iacr.org/2025/783.pdf)

### Abstract

The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in
cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.


[continued in next message]

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