[continued from previous message]

Most notably, we consider the discrete logarithm (DLOG) problem in a generic group of $N$ elements. The classical `baby-step giant-step' algorithm for the problem has time complexity $T=O(\sqrt{N})$, uses $O(\sqrt{N})$ bits of space (up to
logarithmic factors in $N$) and achieves constant success probability.

We examine a generalized setting where an algorithm obtains an advice string of $S$ bits and is allowed to make $T$ arbitrary non-adaptive queries that depend on the advice string (but not on the challenge group element for which the DLOG needs to be
computed).

We show that in this setting, the $T=O(\sqrt{N})$ online time complexity of the baby-step giant-step algorithm cannot be improved, unless the advice string is more than $\Omega(\sqrt{N})$ bits long. This lies in stark contrast with the classical
adaptive Pollard's rho algorithm for DLOG, which can exploit preprocessing to obtain the tradeoff curve $ST^2=O(N)$. We obtain similar sharp lower bounds for the problem of breaking the Even-Mansour cryptosystem in symmetric-key cryptography and for
several other problems.

To obtain our results, we present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems in a unified way.

Since previous proof techniques inherently cannot distinguish between adaptive and non-adaptive algorithms for the problems in our model, they cannot be used to obtain our results. Consequently, we rely on information-theoretic tools for handling
distributions and functions over the space $S_N$ of permutations of $N$ elements. Specifically, we use a variant of Shearer's lemma for this setting, due to Barthe, Cordero-Erausquin, Ledoux, and Maurey (2011), and a variant of the concentration
inequality of Gavinsky, Lovett, Saks and Srinivasan (2015) for read-$k$ families of functions, that we derive from it. This seems to be the first time a variant of Shearer's lemma for permutations is used in an algorithmic context, and it is expected to
be useful in other lower bound arguments.



## 2025/784

* Title: SHIP: A Shallow and Highly Parallelizable CKKS Bootstrapping Algorithm * Authors: Jung Hee Cheon, Guillaume Hanrot, Jongmin Kim, Damien Stehlé
* [Permalink](https://eprint.iacr.org/2025/784)
* [Download](https://eprint.iacr.org/2025/784.pdf)

### Abstract

The CKKS fully homomorphic encryption scheme enables
efficient homomorphic operations in terms of throughput, but its bootstrapping algorithm incurs a significant latency. In this work, we introduce
SHIP, a novel bootstrapping algorithm for CKKS ciphertexts. SHIP
enjoys a very shallow homomorphic multiplicative depth compared to state-of-the-art CKKS bootstrapping algorithms. Bootstrapping depth
directly impacts the required Ring-LWE modulus, and hence the Ring-
LWE degree. The massive depth saving allows us to report the first bootstrapping
of CKKS ciphertexts for full-dimensional cleartext vectors in
ring degree N=2^13, without resorting to an expensive scheme switching
to DM/CGGI. SHIP also enjoys great parallelizability, with minimal communication between threads. The combined ring size reduction and
high parallelizability lead to very low latency. In ring degree N=2^13,
our experimental implementation runs in 215ms on a 32-core CPU for
real-valued cleartext vectors. This is 2.5x lower than the smallest latency
we could observe with the HEaaN library (using 48 cores). For binary
cleartext vectors, the latency is lowered to 174ms, which is 2.2x lower
than Bae et al [EurocryptΓÇÖ24] (with 32 cores).



## 2025/785

* Title: DNDK: Combining Nonce and Key Derivation for Fast and Scalable AEAD
* Authors: Shay Gueron, Thomas Ristenpart
* [Permalink](https://eprint.iacr.org/2025/785)
* [Download](https://eprint.iacr.org/2025/785.pdf)

### Abstract

Authenticated encryption with associated data (AEAD) schemes are responsible for securing increasingly critical digital infrastructures, worldwide. Unfortunately, current widely deployed schemes suffer from various limitations that make them difficult to
use securely in practice. For example, schemes like AES-GCM limit the amount of data that can be encrypted with a single key, therefore limiting its secure scaling to modern workloads. At the same time, practitioners may not be able to move away from
the use of AES-GCM due to mature and widely deployed implementations, legacy constraints, and compliance.

In this paper, we provide approaches to improve the secure scaling of AEAD schemes via what we call derived-nonce, derived-key (DNDK) transforms. At a high level, such transforms use a root key to derive a nonce and key for use with an underlying scheme.
The challenge is doing so in a way that introduces as little overhead as possible, and relying on a small number of assumptions on the used primitives. We provide some general results about secure scaling transforms and a concrete design for AES-GCM that
is called DNDK-GCM. It requires as little as three additional AES calls to enable use of the same key to encrypt up to $2^{64}$ bytes of data, even when using random nonces. We also provide a detailed performance analysis. DNDK-GCM is now a draft IETF
standard, and is already deployed at the cloud scale by companies including Meta.



## 2025/786

* Title: Robust and Verifiable MPC with Applications to Linear Machine Learning Inference
* Authors: Tzu-Shen Wang, Jimmy Dani, Juan Garay, Soamar Homsi, Nitesh Saxena
* [Permalink](https://eprint.iacr.org/2025/786)
* [Download](https://eprint.iacr.org/2025/786.pdf)

### Abstract

In this work, we present an efficient secure multi-party computation MPC protocol that provides strong security guarantees in settings with a dishonest majority of participants who may behave arbitrarily. Unlike the popular MPC implementation known as
SPDZ [Crypto ΓÇÖ12], which only ensures security with abort, our protocol achieves both complete identifiability and robustness. With complete identifiability, honest parties can detect and unanimously agree on the identity of any malicious party.
Robustness allows the protocol to continue with the computation without requiring a restart, even when malicious behavior is detected. Additionally, our approach addresses the performance limitations observed in the protocol by Cunningham et al. [ICITS ΓÇ
Ö17], which, while achieving complete identifiability, is hindered by the costly exponentiation operations required by the choice of commitment scheme.

Our protocol is based on the approach by Rivinius et al. [S&P ΓÇÖ22], utilizing lattice-based commitment for better efficiency. We achieves robustness with the help of a semi-honest trusted third party. We benchmark our robust protocol, showing the
efficient recovery from partiesΓÇÖ malicious behavior.

Finally, we benchmark our protocol on a ML-as-a-service scenario, wherein clients off-load the desired computation to the servers, and verify the computation result. We benchmark on linear ML inference, running on various datasets. While our efficiency
is slightly lower compared to SPDZΓÇÖs, we offer stronger security properties that provide distinct advantages.



## 2025/787

* Title: Preprocessing for Life: Dishonest-Majority MPC with a Trusted or Untrusted Dealer
* Authors: Elette Boyle, Niv Gilboa, Matan Hamilis, Yuval Ishai, Ariel Nof
* [Permalink](https://eprint.iacr.org/2025/787)
* [Download](https://eprint.iacr.org/2025/787.pdf)

### Abstract

We put forth a new paradigm for practical secure multiparty computation (MPC) in the preprocessing model, where a feasible one-time setup can enable a lifetime of efficient online secure computations.
Our protocols match the security guarantees and low costs of the cheapest category of MPC solutions, namely 3-party protocols (3PC) secure against a single malicious party, with the qualitative advantages that one party communicates data sublinear in the
circuit size, and can go offline after its initial messages. This "2+1"-party structure can alternatively be instantiated between 2 parties with the aid of a (possibly untrusted) dealer. Within such existing protocols, we provide comparable online
performance while improving the storage and offline dealer-to-party communication requirements by more than 3 orders of magnitude.

At the technical level, we build on a novel combination of the Fully Linear Interactive Oracle Proof (FLIOP)-based protocol design of Boyle et al. (CRYPTO 2021) and pseudorandom correlation generators. We provide an extensive assortment of algorithmic
and implementation-level optimizations, design efficient distributed proofs of well-formedness of complex FLIOP correlations, and make them circuit-independent. We implement and benchmark our end-to-end system against the state of the art in the $(2+1)$
regime, a dealer-aided variant of SPDZ for Boolean circuits.

We additionally extend our techniques to the $(n+1)$ party setting, where a dealer aids general dishonest-majority MPC, and provide a variant of the protocol which further achieves security with identifiable abort.



## 2025/788

* Title: Identity-Based Ring Signature from Quantum Token
* Authors: Nabanita Chakraborty, Ratna Dutta
* [Permalink](https://eprint.iacr.org/2025/788)
* [Download](https://eprint.iacr.org/2025/788.pdf)

### Abstract

An identity-based ring signature (IRS) is an attractive cryptographic primitive having numerous applications including e-cash and e-voting, that enables a user to authenticate sensitive documents on behalf of a ring of user identities chosen by the
signer and provides anonymity and unforgeability. We introduce the first quantum-tokenized identity-based ring signature (QTIRS) scheme qtIRS and its variant D-qtIRS with signature delegation assuming the existence of obfuscated membership-checking
circuits and a computationally sound non-interactive zero-knowledge (NIZK) proof system. We emphasize that our schemes are dynamic where a user can join or leave the system without disturbing others, allow unrestricted ring size with signature size
independent of the ring size and provide security in the standard model. We enhance our security framework by minimizing restrictions for the adversary and allowing a broader domain to forge and introduce the notion of strong existential unforgeability
against adaptive-chosen-message-and-identity attack (sEU-ACMI) and strong anonymity (sAnon). Our scheme qtIRS achieves sEU-ACMI and sAnon security while our scheme D-qtIRS attains strong existential unforgeability against adaptive-chosen-message-and-
identity attack with signature delegation (sEU-ACMID) and sAnon. Most interestingly, our D-qtIRS features signature delegation and leased key revocation in the IRS setting, enabling a lessor to grant a limited signing authority to a lessee and revoke the
delegated authority whenever needed. Additionally, we have shown the existence of obfuscated membership-checking circuits which is of independent interest.



## 2025/789

* Title: Rushing at SPDZ: On the Practical Security of Malicious MPC Implementations
* Authors: Alexander Kyster, Frederik Huss Nielsen, Sabine Oechsner, Peter Scholl
* [Permalink](https://eprint.iacr.org/2025/789)
* [Download](https://eprint.iacr.org/2025/789.pdf)

### Abstract

Secure multi-party computation (MPC) enables parties to compute a function over private inputs while maintaining confidentiality. Although MPC has advanced significantly and attracts a growing industry interest, open-source implementations are still at
an early stage, with no production-ready code and a poor understanding of their actual security guarantees.
In this work, we study the real-world security of modern MPC implementations, focusing on the SPDZ protocol (Damgård et al., CRYPTO 2012, ESORICS 2013), which provides security against malicious adversaries when all-but-one of the participants may be
corrupted. We identify a novel type of MAC key leakage in the MAC check protocol of SPDZ, which can be exploited in concurrent, multi-threaded settings, compromising output integrity and, in some cases, input privacy. In our analysis of three SPDZ
implementations (MP-SPDZ, SCALE-MAMBA, and FRESCO), two are vulnerable to this attack, while we also uncover further issues and vulnerabilities with all implementations. We propose mitigation strategies and some recommendations for researchers,
developers and users, which we hope can bring more awareness to these issues and avoid them reoccurring in future.



## 2025/790

* Title: PULSE: Parallel Private Set Union for Large-Scale Entities
* Authors: Jiahui Gao, Son Nguyen, Marina Blanton, Ni Trieu
* [Permalink](https://eprint.iacr.org/2025/790)
* [Download](https://eprint.iacr.org/2025/790.pdf)

### Abstract

Multi-party private set union (mPSU) allows multiple parties to compute the union of their private input sets without revealing any additional information.
Existing efficient mPSU protocols can be categorized into symmetric key encryption (SKE)-based and public key encryption (PKE)-based approaches. However, neither type of mPSU protocol scales efficiently to a large number of parties, as they fail to fully
utilize available computational resources, leaving participants idle during various stages of the protocol execution.

This work examines the limitation of existing protocols and proposes a unified framework for designing efficient mPSU protocols. We then introduce an efficient Parallel mPSU for Large-Scale Entities (PULSE) that enables parallel computation, allowing
all parties/entities to perform computations without idle time, leading to significant efficiency improvements, particularly as the number of parties increases. Our protocol is based on PKE and secure even when up to $n-1$ semi-honest parties are
corrupted. We implemented PULSE and compared it to state-of-the-art mPSU protocols under different settings, showing a speedup of $1.91$ to $3.57\times$ for $n=8$ parties for various set sizes.



## 2025/791

* Title: Analysis of One Privacy-Preserving Electricity Data Classification Scheme Based on CNN Model With Fully Homomorphism
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2025/791)
* [Download](https://eprint.iacr.org/2025/791.pdf)

### Abstract

We show that the data classification scheme [IEEE Trans. Sustain. Comput., 2023, 8(4), 652-669)] failed to check the compatibility of encoding algorithm and homomorphic encryption algorithm. Some calculations should be revised to ensure all operands
are first encoded using the same scaling factors. The canonical embedding map depending on the natural projection should be explicitly arranged so as to construct an efficient decoding algorithm.



## 2025/792

* Title: A Scrutiny of the Security of AES-based Hashing and One-way Functions * Authors: Shiyao Chen, Jian Guo, Eik List, Danping Shi, Tianyu Zhang
* [Permalink](https://eprint.iacr.org/2025/792)
* [Download](https://eprint.iacr.org/2025/792.pdf)

### Abstract

AES has cemented its position as the primary symmetric-key primitive for a wide range of cryptographic applications, which motivates the analysis on the concrete security of AES's instantiations in practice, for instance, the collision resistance of AES-
based hashing, the key commitment security of AES-based authenticated encryption schemes, and the one-wayness of AES-based one-way functions in ZK and MPC protocols. In this work, we introduce single-color initial structures into meet-in-the-middle (MITM)
attacks, a systematic technique to identify attack trails that enable efficient neutral word generation and low-memory attacks. As a result, we have attained: (1) the first classical one-block collision attack on 7-round AES-MMO/MP, marking the first
advancement in attack rounds for more than a decade and matching the attack rounds in the quantum setting; (2) the first one-block collision attack on 4-round AES-128-DM, which bridges the gap in Taiyama et al.'s claim at Asiacrypt 2024 from an MITM
perspective; (3) the first improvement in single known plaintext key recovery attack on 5-round AES-128 in over a decade; (4) comprehensive results on the security margin of Rijndael-192 and Rijndael-256 in multiple instantiations. These breakthroughs
deepen our understanding of AES-like structure, and contribute as a scrutiny of the security of AES-based instantiations.



## 2025/793

* Title: Solving systems of polynomial equations via Macaulay matrices
* Authors: Shuhei Nakamura
* [Permalink](https://eprint.iacr.org/2025/793)
* [Download](https://eprint.iacr.org/2025/793.pdf)

### Abstract

One approach to solving polynomial systems is to multiply each equation by monomials, which creates a larger system with the coefficient matrix known as the Macaulay matrix.
The eXtended Linearization (XL) method, introduced by Courtois, Klimov, Patarin, and Shamir in 2000, is one such approach and includes a sub-algorithm that performs Gaussian elimination on the Macaulay matrix.
Due to the simplicity of the method, several improvements and variations have been proposed since its introduction, and it remains an active area of research.
In this paper, we focus on sub-algorithms based on Macaulay matrices that are used in the XL method and its variants and investigate the input parameters that produce the desired output, such as a Gr\"{o}bner basis.
In particular, by summarizing some known facts about the standard degree, we provide a foundation for extending the XL method to the multi-degree case.



## 2025/794

* Title: Formal Analysis of Multi-Device Group Messaging in WhatsApp
* Authors: Martin R. Albrecht, Benjamin Dowling, Daniel Jones
* [Permalink](https://eprint.iacr.org/2025/794)
* [Download](https://eprint.iacr.org/2025/794.pdf)

### Abstract

WhatsApp provides end-to-end encrypted messaging to over two billion users. However, due to a lack of public documentation and source code, the specific security guarantees it provides are unclear. Seeking to rectify this situation, we combine the
limited public documentation with information we gather through reverse-engineering its implementation to provide a formal description of the subset of WhatsApp that provides multi-device group messaging. We utilise this description to state and prove
the security guarantees that this subset of WhatsApp provides. Our analysis is performed within a variant of the Device-Oriented Group Messaging model, which we extend to support device revocation. We discuss how to interpret these results, including the
security WhatsApp provides as well as its limitations.



## 2025/795

* Title: Efficient Noncommutative KEMs from Twisted Dihedral Group Ring
* Authors: Ali Raya, Vikas Kumar, Sugata Gangopadhyay, Aditi Kar Gangopadhyay
* [Permalink](https://eprint.iacr.org/2025/795)
* [Download](https://eprint.iacr.org/2025/795.pdf)

### Abstract

NTRU schemes have been extensively studied as post-quantum proposals within the category of lattice-based constructions.
Numerous designs have been introduced with security assumptions based on the NTRU hard problem; some focused on security, and others were motivated by faster computations. Recently, some proposals for noncommutative NTRU have appeared in the literature,
claiming more resistance to some algebraic attacks. While these proposals provide practical cryptosystems, they fail to perform similarly to the original NTRU over the ring of integers. This work introduces the first construction of noncommutative NTRU
that matches the speed of NTRU over the ring of integers.
Additionally, we present another construction over the ring of Eisenstein integers, demonstrating that performance can be further enhanced. We comprehensively implement the Key Encapsulation Mechanisms (KEMs) based on our constructions and compare their
efficiency and compactness to both commutative and noncommutative NTRU variants in the literature. Our findings indicate that the new designs provide competitive memory and time requirements while utilizing noncommutative algebra. For example, our
noncommutative KEM based on the twisted dihedral group ring over the ring of integers achieves encapsulation and decapsulation speeds comparable to NTRU-HPS, with a key generation speed that is 2.5 times faster. Additionally, our construction based on
the ring of Eisenstein integers is at least 1.6 times faster for key generation and 1.3 times faster for both encapsulation and decapsulation compared to NTRU-HPS.



## 2025/796

* Title: Unified MEDS Accelerator
* Authors: Sanjay Deshpande, Yongseok Lee, Mamuri Nawan, Kashif Nawaz, Ruben Niederhagen, Yunheung Paek, Jakub Szefer
* [Permalink](https://eprint.iacr.org/2025/796)
* [Download](https://eprint.iacr.org/2025/796.pdf)

### Abstract

The Matrix Equivalence Digital Signature (MEDS) scheme a code-based candidate in the first round of NISTΓÇÖs Post-Quantum Cryptography (PQC) standardization process, offers competitively small signature sizes but incurs high computational costs for
signing and verification. This work explores how a high-performance FPGA-based hardware implementation can enhance MEDS performance by leveraging the inherent parallelism of its computations, while examining the trade-offs between performance gains and
resource costs. This work in particular proposes a unified hardware architecture capable of efficiently performing both signing and verification operations within a single combined design. The architecture jointly supports all security parameters,
including the dynamic, run-time handling of different prime fields without the need to re-configure the FPGA. This work also evaluates the resource overhead of supporting different prime fields in a single design, which is relevant not only for MEDS but
also for other cryptographic schemes requiring similar flexibility. This work demonstrates that custom hardware for PQC signature schemes can flexibly support different prime fields with limited resource overhead. For example, for NIST security Level I,
our implementation achieves signing times of 4.5 ms to 65.2 ms and verification times of 4.2 ms to 64.5 ms utilizing 22k to 72k LUTs and 66 to 273 DSPs depending on design variant and optimization goal.



## 2025/797

* Title: WEBCAT: Web-based Code Assurance and Transparency
* Authors: Giulio Berra
* [Permalink](https://eprint.iacr.org/2025/797)
* [Download](https://eprint.iacr.org/2025/797.pdf)

### Abstract

Ensuring code integrity in browser-based applications remains a longstanding challenge exacerbated by the complexity of modern web environments. We propose Web-based Code Assurance and Transparency, a novel code integrity verification and enforcement
mechanism that prevents the execution of unverified code, unlike previous approaches premised on user-visible error indicators or permissive failure modes. WEBCAT remains compatible with modern web features, uses existing cryptographic components without
reinventing primitives or requiring expensive infrastructure, and provides verifiable logs of all system components, even under degraded operational conditions. It follows a separation-of-concerns model in which hosting providers require no special trust
or cryptographic keys to deploy developer-signed applications, reflecting real-world deployment scenarios in which trusted applications may be served by multiple less-trusted hosts.

We evaluate our approach by porting Jitsi, GlobaLeaks, Element, CryptPad, Standard Notes, and Bitwarden, demonstrating compatibility across a diverse set of applications. Benchmark results indicate an overhead of up to 2% for non-enrolled domains on cold
starts and up to 20% for enrolled ones. Under warm start conditions, the overhead reaches 25% for enrolled domains and 5% for non-enrolled onesΓÇölower than previous methods while addressing a larger threat model and remaining compatible with existing
applications.



## 2025/798

* Title: CRAFT: Characterizing and Root-Causing Fault Injection Threats at Pre-Silicon
* Authors: Arsalan Ali Malik, Harshvadan Mihir, Aydin Aysu
* [Permalink](https://eprint.iacr.org/2025/798)
* [Download](https://eprint.iacr.org/2025/798.pdf)

### Abstract

Fault injection attacks represent a class of threats that can compromise embedded systems across multiple layers of abstraction, such as system software, instruction set architecture (ISA), microarchitecture, and physical implementation. Early detection
of these vulnerabilities and understanding their root causes, along with their propagation from the physical layer to the system software, is critical in securing the cyberinfrastructure.
This work presents a comprehensive methodology for conducting controlled fault injection attacks at the pre-silicon level and an analysis of the underlying system for root-causing behavior. As the driving application, we use the clock glitch attacks in
AI/ML applications for critical misclassification. Our study aims to characterize and diagnose the impact of faults within the RISC-V instruction set and pipeline stages, while tracing fault propagation from the circuit level to the AI/ML application
software. This analysis resulted in discovering two new vulnerabilities through controlled clock glitch parameters. First, we reveal a novel method for causing instruction skips, thereby preventing the loading of critical values from memory. This can
cause disruption and affect program continuity and correctness. Second, we demonstrate an attack that converts legal instructions into illegal ones, thereby diverting control flow in a manner exploitable by attackers. Our work underscores the complexity
of fault injection attack exploits and emphasizes the importance of preemptive security analysis.

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