---
title: "Tulva: Practical Asynchronous Threshold FHE"
authors: "Valerio Cini, Antonio Guimarães, Russell W. F. Lai, Michał Osadnik, Ivy K. Y. Woo"
venue: "2027 IEEE Symposium on Security and Privacy (S&P)"
source: "arXiv:2610.20521 (official copy)"
source_version: 2026-10-15
canonical: https://antonioguimaraes.org/publications/tulva/
pdf: https://arxiv.org/pdf/2610.20521
generator: scripts/fulltext.py (pdftotext)
---

# Tulva: Practical Asynchronous Threshold FHE

*Valerio Cini, Antonio Guimarães, Russell W. F. Lai, Michał Osadnik, Ivy K. Y. Woo*. 2027 IEEE Symposium on Security and Privacy (S&P).

> Automatic plain-text transcript of the author version, provided for search and AI assistants. Formulas, tables, figures and footnotes are not reproduced faithfully. Read and cite the paper: https://arxiv.org/pdf/2610.20521

<!-- page 1 -->

Tulva: Practical Asynchronous Threshold FHE (Full version)

Valerio Cini 1 , Antonio Guimarães 2 , Russell W. F. Lai 3 , Michał Osadnik 3 , and Ivy K. Y. Woo 3

Bocconi University, Milan, Italy IMDEA Software Institute, Madrid, Spain Aalto University, Espoo, Finland

Abstract. Fully homomorphic encryption (FHE) allows arbitrary computation over encrypted data, but its secret key presents a single point of failure which limits its applications. Threshold FHE patches this gap by distributing the secret key to K parties, requiring a threshold t ≤ K of them to cooperate for decryption. We focus on the asynchronous setting where a ciphertext can be decrypted by collecting decryption shares from any t parties who do not need to coordinate or even be online simultaneously. Asynchronous schemes are sought in applications such as privacy-preserving Ethereum Virtual Machines (EVM), processing of long-lived private data with quorum-based decryption and the thresholdisation of any cryptographic primitive in general. We present Tulva, a practical threshold FHE scheme which equips a base FHE scheme with an asynchronous threshold decryption mechanism in a modular way. Our scheme simultaneously (1) is compatible with virtually any base FHE scheme and leaves its ciphertexts unchanged apart from an appended random tag, (2) supports a wide range of threshold profiles (t, K) and ring degrees ≥ 256 with 6–25 bits partial decryption per plaintext bit, and (3) achieves security in the presence of partial decryption queries on challenge ciphertexts based on the standard LWE assumption. We provide an open-source implementation, benchmark its threshold decryption performance and evaluate the end-to-end costs for typical privacy-preserving EVM use cases. For 16-out-of-512 threshold and a publicly preprocessed ciphertext, computing secret-dependent partial decryption and public share combination requires only 3.7ms and 0.5ms, respectively, on commodity hardware. Compared with the state-of-the-art synchronous scheme [Zyskind et al., CCS’25], we replace their ciphertext-independent yet interactive preparation of secret-correlated randomness with a public, ciphertext-dependent 0.5s preprocessing step, eliminate interaction in the online phase while maintaining similar decryption time on the same machine, and support 32× more total users.

This is the full version of a paper to appear in the proceedings of the 48th IEEE Symposium on Security and Privacy (S&P 2027) with the same title. This version includes additional proofs that are omitted in the proceedings version.

<!-- page 2 -->

Table of Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Threshold FHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Requirements on Underlying FHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 From FHE to Threshold FHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Threshold FHE Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Requirements on Underlying FHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Threshold FHE Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Threshold FHE from FHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Practical Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Parameter Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Examples of FHEVM Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Algorithms for FHEVM Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B Additional Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C Proof of Lemma 4 (Quality of Subtractive Sets) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D Proof of Theorem 1 (FHE Leakage Security) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E Proof of Theorem 2 (Tulva Correctness) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F Proofs for Theorem 3 (Tulva Security) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.1 Theorem Statement and Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2 Proofs of Lemmas 12 to 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G A Utility Lemma and Intermediate Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.1 Intermediate lattice assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.2 Utility Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.3 Theorem 4 and proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.4 Theorem 5 and proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

<!-- page 3 -->

Introduction

Fully homomorphic encryption (FHE) has rapidly emerged in the past decade as a practically viable tool for computing over private data. However, in many real-world applications, storing the secret decryption key on a single device is undesirable. Threshold FHE distributes the single point of trust by splitting the secret key among K parties, such that any subset of at least t parties can jointly decrypt a ciphertext, while any coalition of fewer than t parties learns nothing about the underlying message. 1 The practical significance of threshold FHE is recognised: it constitutes a standalone category in NIST’s call for multiparty threshold schemes [BP26].

Threshold FHE

Threshold FHE can be roughly classified into two classes: asynchronous and synchronous/interactive. For an asynchronous scheme (e.g. [BGG + 18, BS23, BFM + 25]), any of the K shareholders can locally compute a partial decryption without coordinating with other parties. Anyone can recover the encrypted message by collecting t partial decryptions in any order and possibly across an extended time period. In contrast, the decrypting parties of a synchronous scheme (e.g. [BCD + 25b, ZZLP25]) must be aware of the set of t participating parties in advance to produce valid partial decryptions. Some synchronous schemes are further interactive (e.g. [ZZLP25]), i.e. the partial decryptors must engage in at least two rounds of communication to decrypt the ciphertext, meaning that all decrypting parties must be simultaneously online during the decryption process. 2 The above differences dictate where a threshold FHE can be deployed, and the non-interactivity of asynchronous schemes makes them particularly suited for decentralised, dynamic environments. A prominent application is FHEVM [Zam23a], a confidential smart-contract platform where encrypted account balances and contract states reside on a public ledger. A validator set homomorphically executes smart-contract logic over these ciphertexts, while a separate, rotating committee of decrypting parties is invoked to decrypt only specific outputs (e.g. a transaction-success bit or an auction’s clearing price). The rise of production FHEVM stacks from companies such as Zama [Zam23a] and Fhenix [Fhe24] highlights the growing demand for this architecture. Because contracts trigger decryption requests unpredictably and the decryption committee rotates across epochs, the underlying decryption pattern is inherently asynchronous. Synchronous schemes, which require the decrypting parties to be agreed in advance and/or simultaneously online, are structurally incompatible. Beyond FHEVMs, asynchronous threshold FHE further enables generically thresholdising cryptographic primitives [BGG + 18] without imposing constraints on set-agreement or communication that are inherent to synchronous alternatives. Despite strong market demand, existing threshold FHE schemes struggle to meet all practical constraints simultaneously. Constructing schemes that simultaneously maximise the range of threshold profiles while minimising partial decryption size, time and communication rounds is challenging, even without asynchronous decryption. This forces a trade-off between asynchrony and efficiency. Among the best benchmarked schemes, Noah’s Ark [DDEK + 23] is asynchronous only when t = O(1): It requires interactive offline K-party preprocessing for t ≥ ω(1), such that each decryption process consumes one preprocessing run; Zyskind et al. [ZZLP25] is restricted to the K-out-of-K setting and is highly interactive. Beyond efficiency trade-offs, there is also a subtlety in how threshold FHE security is typically modeled. While the exact security definition of threshold FHE differs greatly from work to work (cf. Section 1.3), none of the definitions that we are aware of models attack scenarios where the adversary can learn partial decryptions of “challenge ciphertexts”, whose underlying plaintexts are (supposedly) unknown to the adversary. 3 This is a strict [BKW26] limitation that is especially significant when the threshold FHE is used to thresholdise another cryptographic primitive. Taking threshold signatures as an example, the ability to learn partial decryptions of challenge ciphertexts corresponds to that of learning transcripts of

For some schemes, the recovery threshold could be much larger than the corruption threshold. Some schemes have a synchronous/interactive offline phase and an asynchronous online phase. This restriction is sometimes explicit (e.g. [BS23]), but is more often implicitly implied by restricting the adversary to corrupt exactly t − 1 users (e.g. [BGG + 18, OT25, BFM + 25]), so that any additional partial decryption leads to trivial decryption. In the context of proof, assuming the corruption of exactly t − 1 users seems to make a proof much easier, since any partial decryption would imply recovery of the plaintext, which can then be trivially simulated.

<!-- page 4 -->

unfinished threshold signing protocols, the latter of which is captured in the strongest TS-UF-4 security definition of threshold signatures defined in [BCK + 22].

Our Contributions

We present Tulva, a practical compiler that turns virtually any 4 FHE into an asynchronous threshold FHE. The instantiation with TFHE, tulva-tfhe, efficiently supports a wide range of threshold profiles 5 , e.g. any t ≤ K ≤ 128 or any t with min{t, K − t} ≤ 16 for up to K = 512, with λ = 128 bits of estimated security. Our headline result is a 16-out-of-512 scheme whose threshold decryption process can be decomposed into a 0.5s public ciphertext preprocessing step, a 3.7ms partial decryption step, and a 0.5ms public share combination step, where the median timing measurements are obtained from an AWS c7a.32xlarge instance with AMD EPYC CPU.

Modular construction. Tulva consists of a decryption process which first performs a (public) key-switch operation on the FHE ciphertext, turning it into a threshold public-key encryption (PKE) ciphertext of a compatible threshold PKE scheme, and then performs the threshold decryption procedure of the threshold PKE. Such a modular construction is essentially agnostic to the underlying FHE scheme, hence enabling flexible instantiations depending on the use cases. We highlight two advantages of key-switching to a dedicated threshold PKE scheme: 1. It enables cleaner decryption noise management and parameter selection: The FHE layer only needs to expose a small set of parameters (e.g. plaintext and ciphertext moduli, decryption noise budget) to the threshold layer, making the parameter selection process of the two layers mostly independent; 2. It allows us to inject additional (pseudo)randomness to ciphertexts to be decrypted. This is crucial for proving that Tulva remains secure even when the adversary learns partial decryptions of challenge ciphertexts, under the standard (module) learning with errors (LWE) assumption.

Security given partial decryptions of challenge ciphertexts. Proving this strong security property requires constructing a reduction which simulates partial decryptions that are jointly correlated with all key shares instead of only those of corrupt parties. While proof techniques for this scenario have recently been developed in the simpler context of threshold PKE [CLW25], the threshold FHE setting introduces more complications since many correlated FHE ciphertexts can be derived from a single one. The injection of additional randomness to ciphertexts allows us to extend the technique of [CLW25] to the threshold FHE setting.

Implementation, benchmark and use cases. Our TFHE-based instantiation tulva-tfhe consumes ciphertexts produced by the tfhe-rs [Zam23b] library directly: a thin compatibility layer repacks and key-switches them into the form expected by our threshold layer, whose performance-critical routines are written in C with AVX-512 optimisations and orchestrated from Python. We benchmark across ring degrees φ ∈ {256, 2048} and threshold profiles up to K = 512 parties; the small ring minimises single-ciphertext latency, while the large ring packs φ = 2048 messages per batch for throughput. We further provide end-to-end benchmarks for four confidential smart contract use cases in an FHEVM (Section 6): a sealed-bid auction, a confidential ERC-20 transfer, a dark-pool DEX, and a median price oracle.

Related Work

There is a substantial literature on threshold FHE, including [AJL + 12, BGG + 18, BS23, PS24, OT25, BFM + 25]. In the following, we focus on comparing with [DDEK + 23, KLL + 26, ZZLP25] which are the most practically relevant, of which [ZZLP25] is the only work that makes its implementation publicly available. Pilvi [CLW25] is a threshold PKE scheme that uses subtractive-set elements as the evaluation points of Shamir sharing, and it is secure even when the adversary obtains partial decryptions of challenge ciphertexts. Tulva takes from Pilvi the subtractive-set evaluation points, the security model, and its proof techniques. Applying Pilvi directly to threshold FHE would mean secret-sharing the FHE secret

We require the FHE to satisfy a “linear decryption” property (Definition 4) which holds for virtually all practical FHE families except CKKS. There is no hard limit and the costs scale gracefully.

<!-- page 5 -->

key itself in the same way, as [KLL + 26] does, which requires non-black-box changes to the FHE and its parameters. Instead, Tulva keeps the FHE and threshold layers separate: a public key switch moves an FHE ciphertext to a dedicated decryption key, and only that key is secret-shared, so the FHE is used as a black box and its ciphertexts and evaluation are unchanged apart from an appended random tag. On the proof side, these random tags are what let us adapt Pilvi’s proof techniques to homomorphically evaluated ciphertexts (see Section 2.3). In terms of construction, both Tulva and Noah’s Ark [DDEK + 23] secret-share a dedicated decryption key , while the schemes of [ZZLP25, KLL + 26] perform threshold decryption “in place”. All three schemes, Tulva and [DDEK + 23, KLL + 26], use noise flooding to mask leakages of the FHE decryption noise and the secret key share. The scheme of [ZZLP25] avoids noise flooding using a rounding protocol based on multiparty computation (MPC), at the cost of having online interactions. Tulva and [BFM + 25, KLL + 26] consider the asynchronous model. Noah’s Ark [DDEK + 23] is only asynchronous for t = O(1). For t ≥ ω(1), each threshold decryption consumes a ciphertext-independent K-party interactive offline preprocessing, although the online phase is asynchronous. The scheme of [ZZLP25] requires interactions among all K parties in both offline and online phases. There are mainly two formal models of threshold FHE which define the notion either (1) as a standalone primitive (e.g. this work and [KLL + 26]) or (2) as MPC protocols for key generation and threshold decryption associated to a base FHE scheme (e.g. [DDEK + 23, ZZLP25]). Typically, security in the former model is described via security experiments for individual properties, and in the latter via ideal functionalities. All compared works use distinct security definitions, and we are not aware of any result that connects game-/simulation-/UC-based security definitions for threshold FHE, making them difficult to compare. This work inherits the strong security model for threshold PKE considered in [CLW25, BKW26] where the adversary can non-maximally corrupt |C| < t parties and make less than t − |C| partial decryption queries on each challenge ciphertext. The model in [KLL + 26] is weaker [BKW26] in the sense that it forces |C| = t − 1. Understanding the correspondence of this property in UC-based models [DDEK + 23, ZZLP25] is beyond the scope of this work.

Technical Overview

We overview our construction and the security proof. Throughout, we work over a cyclotomic field K = Q(ζ) and its ring of integers R = Z[ζ] with norms measured in the coefficient embedding. The fractional part of x ∈ K wrt. the coefficient embedding is written as {x} := x − ⌊x⌉.

Requirements on Underlying FHE

Our transformation assumes an FHE scheme FHE to satisfy a structural property and a security property.

Structural property. We assume that FHE has “linear decryption” 7 (Definition 4), i.e. the following (typical) properties:

– The decryption key is a vector sk FHE = ŝ ∈ R n̂ q . – There exists a deterministic transformation Preproc that turns a ciphertext into a tuple

(ĉ 0 , ĉ 1 ) ← Preproc(ctxt FHE ) ∈ R n̂ q × R q .

In particular, we do not require the FHE scheme to operate over the same ring R q (e.g. it can work over entirely different rings or moduli), as long as the above Preproc procedure exists. – If a ciphertext ctxt FHE is intended to encrypt a message µ ∈ R p (potentially after some homomorphic evaluations), then it holds that ĉ 1 − ŝ · ĉ 0 = · µ + ê mod q with ∥ê∥ ∞ ≤ B,

for some j noise budget B m depending on the FHE scheme. n We o call ê the FHE decryption noise. This implies q · (ĉ 1 − ŝ · ĉ 0 ) = µ mod p when q/2p > B + p .

A subtle difference is that in Tulva a ciphertext is key-switched to one under the decryption key while in Noah’s Ark [DDEK + 23] it is bootstrapped. The formal definition involves a “slack” factor ξ. We assume ξ = 1 in this overview for simplicity.

<!-- page 6 -->

Virtually all lattice-based constructions of FHE have linear decryption. For most of them, Preproc can be implemented with well-known and relatively inexpensive procedures, such as Ring Switching [GHPS12] and Packing Key Switching [CGGI16, MS18, CDKS21]. In fact, some schemes (e.g. BFV [Bra12, FV12]) already often work with ciphertexts satisfying our requirements. An exception is CKKS [CKKS17], which, being an approximate scheme, would not immediately satisfy our correct decryption condition, requiring more complex procedures. We discuss the potential instantiations of Preproc and their compatibility with different FHE schemes in Section 5. For our proof-of-concept implementation, we consider the TFHE scheme [CGGI16], as provided by the tfhe-rs library [Zam23b], and implement Preproc using bootstrappings (to increase moduli) and packing key switching.

Security property. We assume that FHE has IND-CPA-with-leakage security (Definition 5). Informally, this means that FHE remains IND-CPA secure even when the adversary has access to a leakage oracle that, on input an honestly generated ciphertext of its choice, returns the corresponding FHE decryption noise ê masked by additional noise. We show (Theorem 1) that any IND-CPA-secure FHE scheme with linear decryption satisfies this notion, provided the masking noise is super-polynomially large. We leave the case of polynomially large masking noise to future work. Apart from these structural and security requirements, our transformation only requires the modulusto-noise ratio q/B of the underlying FHE scheme to be sufficiently large (super-polynomial in our current analysis). The transformation is otherwise oblivious to the homomorphic evaluation procedures of the underlying FHE scheme. Hence, it preserves any optimisations implemented in the underlying FHE scheme.

From FHE to Threshold FHE

Next, we describe our generic compiler, Tulva, that turns any FHE scheme satisfying the requirements in Section 2.1 into a threshold FHE scheme. Conceptually, our transformation is to pair the FHE with an external linearly-homomorphic threshold PKE (tPKE) scheme which takes care of threshold decryption. The basic idea is to encrypt the FHE secret key under the tPKE, and homomorphically evaluate (the linear part) of the FHE’s decryption function on an FHE ciphertext, i.e. perform a key-switching operation to turn an FHE ciphertext into a tPKE ciphertext. The partial decryption procedure of the tPKE can then be applied. Looking ahead, we will instantiate the tPKE with the classic threshold Regev-PKE scheme. The construction involves two moduli p ≤ q for plaintexts and threshold layer ciphertexts, respectively. It is agnostic to the FHE layer modulus, which is left implicit. Our modular framework offers two major advantages: (1) The parameters for the FHE and tPKE layers are almost decoupled: only the noise budget, the plaintext and ciphertext moduli and some dimensions of the former are exposed to the latter, allowing a simpler parameter selection process. (2) Our security proof can be decomposed into distinct parts concerning solely the FHE or the tPKE components, which allows us to borrow techniques for tPKE to argue strong threshold FHE security (see Section 2.3).

Key Generation. A trusted dealer first generates the FHE key pair (pk FHE , sk FHE ), where sk FHE = ŝ. It then generates a key-switching key (A, b) which allows anyone to turn an FHE ciphertext into a tPKE ciphertext, as follows: Sample the matrices A ← $ R n×m and R ← $ R t×n uniformly at random. Compute r = v 0 · R mod q, where v 0 = (1, 0, . . . , 0) denotes the t-dimensional first unit vector, i.e. r T is the first row of R. Sample a short error vector e ← $ R m . Compute

b := r T · A + e T + (ŝ T , 0 T h ) · G mod q,

where G is an appropriate gadget matrix [MP12]. The public key is pk = (pk FHE , A, b). The secret key sk k for the k-th party is the k-th Shamir’s secret-share of the vector r, which can be expressed as the k-th row of V · R mod q, where V ∈ R K×t is the Vandermonde matrix with the evaluation points as entries. 8 The norm growth issue can be handled by carefully chosen evaluation points, similar to other recent works [CLW25, KLL + 26] (see Section 2.3 “optimisations”).

Remark 1 (Distributed key generation). Removing the trusted-dealer assumption requires generating the underlying FHE key material, our key-switching key, and the secret shares in a distributed manner.

Our security proof will not directly rely on the security of secret-sharing, but via analysing the structure of the Vandermonde matrix.

<!-- page 7 -->

Generic secure MPC can in principle implement KGen, but an efficient distributed key generation protocol must address both distributed key generation for the underlying FHE scheme and joint sampling of the Gaussian error in the key-switching key. We leave its design and evaluation to future work.

Encryption and Homomorphic Evaluation. The encryption and homomorphic evaluation algorithms are almost exactly those of FHE, except that each ciphertext ctxt = (ctxt FHE , t) is accompanied by an independently uniformly random tag t ← $ R hq , which is generated during encryption and refreshed every time a homomorphic operation is performed. This seemingly useless tag injects additional randomness to a ciphertext and is crucial for proving the strong security property in Section 2.3. In practice, t could e.g. be derived by hashing ctxt FHE with a hash function (fixed in the public parameters) that can reasonably be modelled as a random oracle (cf. Remarks 3 and 6). We note again that fresh FHE ciphertexts ctxt FHE and those undergoing homomorphic evaluations may be over rings different from R q , as long as they can be transformed to take the form (ĉ 0 , ĉ 1 ) ∈ R n̂ q × R q by the procedure Preproc.

Partial Decryption. For a ciphertext ctxt = (ctxt FHE , t), any party k who wants to contribute its partial decryption first runs the deterministic procedure Preproc to obtain (ĉ 0 , ĉ 1 ) ← Preproc(ctxt FHE ), then performs (part of) a key-switching operation to obtain 9 ĉ c 0 := A · G −1 0 mod q, t

where G −1 (·) is the “gadget-decomposition” operation [MP12]. Each party k then releases the partial decryption pd k = s T k · c 0 + e k mod q

where e k ← $ R is a fresh masking noise.

Remark 2. In applications where ciphertexts are processed by a dedicated entity, e.g. a server, before they are partial-decrypted, Preproc can be run only once by this entity, instead of multiple times by individual partial decryptors.

Combining. After collecting t partial decryptions (pd k ) k∈T from a set T ⊆ t [K] of parties, the ciphertext can be fully decrypted by a public share combination First, the combiner completes the procedure. ĉ 0 −1 key-switching operation, i.e. computes c 1 := b · G mod q. Next, it combines the set of partial t decryptions (pd k ) k∈T into pd := v 0 T · V T −1 · (pd k ) k∈T mod q,

where V T is the submatrix of V corresponding to the set T of parties. Equivalently, v 0 T · V T −1 are the recovery coefficients of the secret-sharing. Then, it removes the encryption in the threshold layer by computing := := µ̂ ⌊ĉ 1 − (c 1 − pd)⌉ mod q then µ · µ̂ mod p.

Analysis

Main parameter constraint. In our transformation, each partial decryptor k adds a moderate amount of noise e k to the partial decryption pd k . On the one hand, for security, this noise e k must be large enough to mask out the FHE decryption noise ê. This ultimately allows us to argue the security of the resulting threshold FHE scheme based on the IND-CPA-with-Leakage security of the underlying FHE scheme. On the other hand, for correctness, the modulus-to-noise ratio q/B of the underlying FHE scheme must be large enough to accommodate the extra masking noise e k in addition to the existing FHE decryption noise ê.

In practice, the computation of c 0 can alternatively be done by a designated party, e.g. whoever is performing the last homomorphic evaluation step on the ciphertext.

<!-- page 8 -->

Security model. Following recent works which studied and refined tPKE security [CLW25, BKW26], we define an analogously refined IND-CPA security model for threshold FHE (Definition 7). For a threshold t, our model supports corrupting a subset of arbitrary ≤ t − 1 many users, and allows an adversary A to access limited partial decryptions even for ciphertexts that it is unauthorised to decrypt, which captures security under thresholdisation. In more detail, our IND-CPA model is as follows:

– The adversary A statically corrupts a subset C of size ≤ t − 1 (instead of exactly t − 1) users. – A is given the public key and the secret keys of all corrupt users. – A has access to a challenge oracle ChalO, an encryption oracle EncO, an evaluation oracle EvalO, and a partial decryption oracle ParDecO, which do the following: • ChalO encrypts one of the two challenge messages µ 0 , µ 1 chosen by A. • EncO encrypts any message µ chosen by A. • EvalO allows A to instruct any homomorphic evaluation on any set of ciphertexts that have been honestly generated (and possibly evaluated) by the experiment. • ParDecO adaptively answers partial decryption queries of any user on any honestly generated (and possibly evaluated) ciphertext, with a condition: for each ciphertext whose underlying plaintext is different in games 0 and 1, the number of partial decryption queries is less than t − |C|.

Relative to prior works [BGG + 18, BS23, OT25, BFM + 25, KLL + 26], the main distinction lies in ParDecO, where we model security even when giving < t − |C| (instead of 0) partial decryptions for each “challenge ciphertext” 10 to A.

Security analysis. We show (Theorem 3) that under appropriate parameter constraints, if the underlying FHE has linear decryption and is IND-CPA-with-Leakage secure, and if the standard LWE assumption holds, then our threshold FHE transformation satisfies the above IND-CPA security. Since IND-CPA- with-Leakage is implied by plain IND-CPA up to appropriate masking noise (Theorem 1), overall, our threshold FHE can be based on any IND-CPA secure FHE with linear decryption and the LWE assumption (Corollary 1). Our security proof goes via a hybrid argument consisting of two main parts, corresponding to the “threshold layer” and the “FHE layer” of the construction.

Threshold Layer. The first part (Hyb b,0 ≈ c Hyb b,1 via Lemma 12 and Hyb b,1 ≡ Hyb b,2 via Lemma 13) unwraps the threshold layer. We hop from the real experiment, where the challenge oracle ChalO encrypts message µ b , to a hybrid experiment with the following main changes:

– The vector b in the public key which encodes the FHE secret key ŝ (ref. Eq. (2)) is swapped to uniformly random. In exchange, the correlation between b and all partial decryptions pd k ’s (which arises naturally from decryption correctness) is embedded in the pd k ’s. – For ciphertexts whose underlying plaintexts differ in games 0 and 1 (i.e. the “challenges”), their partial decryptions are swapped to uniformly random.

The proof ideas for this part borrow those in [CLW25] established for tPKE: The first change is by carefully manipulating the underlying linear correlations and invoking LWE along the way; the second change relies on the algebraic structure of the Vandermonde matrix, together with the leverage that only ≤ t − |C| partial decryptions of each “challenge” are handed to the adversary. Relative to [CLW25], however, we need to handle a new complication: During partial decryption, the ĉ component (A, b) is multiplied with x := G −1 0 mod q (Eq. (3)), where the top part G −1 (ĉ 0 ) is (the t encoding of) an arbitrary honestly generated (and possibly evaluated) FHE ciphertext. Since we do not assume any specific FHE scheme, the experiment has no guarantee on the distribution of ĉ 0 . Yet, it needs to adaptively answer partial decryption queries on these – possibly adversarially influenced – ciphertexts. This is in contrast to the tPKE setting of [CLW25] where x is simply the encryption randomness which the security experiment has full control over.

In the simpler case of threshold PKE, one may easily classify ciphertexts from ChalO as “challenges”, which an adversary is unauthorised to decrypt, and those from EncO as “non-challenges”, see e.g. [DLN + 21, CLW25, BKW26]. For threshold FHE, because of the freedom of homomorphic evaluation, alternative classification is needed. In our model, any (possibly evaluated) ciphertext is considered “challenge” if the underlying plaintext is different in games 0 and 1, else it is “non-challenge”. This aspect is consistent with the model of [BS23].

<!-- page 9 -->

We tackle the above issue as follows. First, we utilise the random tag t appended to the threshold FHE ciphertext, which serves as a rerandomisation (in the form of G −1 (t)), allowing us to invoke standard LWE w.r.t. G −1 (t) when analysing the modified partial decryptions. Second, to handle the adaptivity issue, we rely on standard LWE and a super-polynomial masking error, with which we argue the distribution of partial decryptions in an information-theoretic way. The formal security proof, which we provide in the appendices, involves reestablishing the counterparts of all lemmas in [CLW25] with the above modifications incorporated.

FHE Layer. The second part handles partial decryptions for the ciphertexts which an adversary is authorised to fully decrypt and recover the plaintexts. For this, we further rewrite these partial decryptions, this time relying on the linear decryption (Eq. (1)) of the underlying FHE (Hyb b,2 ≡ Hyb b,3 via Lemma 14), such that they can be simulated given the leakages from the IND-CPA-with-Leakage experiment of the FHE (Hyb 0,3 ≈ c Hyb 1,3 via Lemma 15).

Optimisations. As in [BFM + 25, CLW25, KLL + 26], to support t-out-of-K decryption, our transformation utilises ξ-subtractive sets [AL21, KLNO24b] of cardinality K, where ξ = ξ(t) : N → R is a slack function. In brief, if Ξ ⊂ R is a ξ-subtractive set, then for any t-subset T ⊆ Ξ which defines a Vandermonde matrix V T , it holds that ξ(t) · V T −1 is integral, i.e. has entries in R. This allows choosing the modulus q such that ξ(t) · V T −1 has low norm relative to q. Since the norm of ξ(t) · V T −1 is empirically only moderate-sized and especially small with small thresholds, this means the modulus q can also be kept practically small, leading to the concrete efficiency of our threshold FHE. To further compress partial decryption size, we also adopt the standard bit-dropping technique, where the errornous low-order bits are dropped. Finally, in our formal security proof, we use an intermediate computational assumption called Leaky LWE to modularise proof steps and ease presentation. In more detail, [LSW25] and [HKM + 26] gave reductions from standard LWE to the semi-adaptive and fully-adaptive versions of Leaky LWE, respectively, both in the polynomial modulus-to-noise ratio regime. The security proof of Tulva (Appendices G.3 and G.4) assumes fully-adaptive Leaky LWE (implied by LWE) and uses proof techniques adapted from the semi-adaptive reduction of [LSW25] in a non-black-box way.

Preliminaries

Let λ ∈ N and δ ∈ N denote the computational and statistical security parameters respectively. For any n ∈ N, we write poly(n) and negl(n) for the sets of all polynomials and negligible functions in n, respectively. For k, n ∈ N, k ≤ n, we write [n] for {1, . . . , n} and [k, n] for {k, . . . , n}. If S is a set, we write x ← $ S for sampling a uniformly random element from S. If D is a distribution over S, denoted as D ∼ S, we write x ← $ D for sampling a random element from S according to the distribution D. We use bold capital and lower-case letters, e.g. A and b, to denote matrices and vectors, respectively. Let K = Q(ζ) be a cyclotomic field of conductor f and degree φ = φ(f) and R = Z[ζ] its ring of integers. For q ∈ N, define the quotient ring R q := R/qR. We denote by R × and R × q the sets of units in R and R q respectively. For any x ∈ R, we write ⌊x⌉ for the nearest integer to x with an arbitrary fixed tie-breaking rule. The fractional part of x is defined as {x} := x − ⌊x⌉. This notation is extended naturally to vectors of real numbers. For x ∈ Z and z ∈ N, we write ⌊x⌉ 2 z := 2 z · ⌊x/2 z ⌉ for x rounded to the nearest multiple of 2 z . For x ∈ Z q , ⌊x⌉ 2 z is computed on the representative of x in [−q/2, q/2), i.e. the one with the smallest absolute value, and the result is read again in Z q . The notation extends coefficient-wise to ring elements and vectors. We abuse the notation of modular arithmetic so that it expresses two meanings depending on the context: e.g. a = b mod q means a and b are congruent modulo q but a mod q = b means b is the smallest (in absolute value) of all integers congruent to a modulo q. Relatedly, pq · (x mod q) means n o multiplying the smallest representative of x mod q by p/q. Note that p q = q mod

Embeddings and norms. We write ψ : K → Q φ and σ = (σ i ) i∈Z × : K → C φ for the coefficient (wrt. the

f

standard power basis) and canonical embeddings of K, respectively. For x ∈ K, its ℓ p -norm is measured via its coefficient embedding, i.e. ∥x∥ p := ∥ψ(x)∥ p , and p = ∞ when omitted. If K is a power-of-two field, then it is known that ∥ψ(x)∥ ≤ ∥σ(x)∥ and ∥σ(x)∥ 2 = φ · ∥ψ(x)∥ 2 . The field expansion factor of K w.r.t. the coefficient ℓ p -norm is defined as c p := max a,b∈K ∥a · b∥ p /(∥a∥ p · ∥b∥ p ).

<!-- page 10 -->

For a vector x ∈ K m , the embedding is extended component-wise, e.g. ψ(x) = (ψ(x i )) i∈[m] , and ∥x∥ p := ∥ψ(x)∥ p , and p = ∞ when omitted. For a matrix M ∈ K n×m , we write Ψ (M) ∈ Q φn×φm for the matrix of the Q-linear map x 7→ Mx from K m to K n in the coefficient embedding, i.e. ψ(Mx) = Ψ (M)·ψ(x) for all x ∈ K m . For a matrix M = (m 1 , . . . , m m ) ∈ K n×m , its ℓ p -induced-norm is ∥M∥ p,p := sup x∈K m ∥M · x∥ p /∥x∥ p . Consequently, ∥Mx∥ p ≤ ∥M∥ p,p · ∥x∥ p and ∥MN∥ p,p ≤ ∥M∥ p,p · ∥N∥ p,p . Similarly, by default we write ∥M∥ for ∥M∥ ∞,∞ = ∥Ψ (M)∥ ∞,∞ . For a real or complex matrix B, we write s max (B) for its largest singular value, i.e. the square root of the largest eigenvalue of B ∗ B, where B ∗ is the conjugate transpose of B, and we define its ℓ 2 -induced norm as ∥B∥ 2,2 := s max (B). By [LSW25, Lemma 2], for any M ∈ K n×m , it holds that ∥M∥ 2,2 = ∥Ψ (M)∥ 2,2 = s max (Ψ (M)). We note that matrices over K are not identified as complex matrices: a complex matrix arises from M only as σ i (M) for some i ∈ Z × f , obtained by applying the i-th component σ i of the canonical embedding σ entrywise. In particular, ∥M∥ 2,2 is in general not s max (σ i (M)) for a fixed i (cf. Lemma 2).

Subtractive sets. We rely on the notion of subtractive sets, proposed by [AL21], further studied by e.g. [KLNO24b], and used by e.g. [CLW25] for constructing threshold PKE.

Definition 1 (Subtractive Sets). For a set Ξ = {µ 1 , . . . , µ K } ⊆ R, any t ≤ K, and any subset T ⊆ {0} ∪ Ξ, let V T (with implicit dependency on t) denote the (row-style) T × t Vandermonde matrix, i.e. its rows are indexed by T and row µ ∈ T is given by (1, µ, . . . , µ t−1 ). Let ξ = ξ(t) : [K] → R. The set Ξ is said to be ξ-subtractive [AL21] if for any t ∈ [K] and any size-t subset T ⊆ Ξ, it holds that ξ · V T −1 ∈ R t×t . Consider Ξ with 0 ∈ / Ξ. Denote by v 0 T := V {0} = (1, 0, . . . , 0) the first unit vector. We measure the quality of Ξ by the following “quality measurements”:

ρ(t) := max ξ · v 0 T · V T −1 ,

T ⊆ t Ξ

−1 ξ · V Ξ\T ∗ · V {0}∪T ∗ · v 0 ,

θ(t) :=

max

T ∗ ⊆

t−1 Ξ

−1 ξ · V Ξ · V {0}∪T ∗

γ(t) :=

,

max

T ∗ ⊆ t−1 Ξ

2,2

where the top row of V {0}∪T ∗ corresponds to the index 0. Here ρ and θ use the default coefficient ℓ ∞ -norm, whereas γ uses the ℓ 2 -induced operator norm ∥·∥ 2,2 .

The Vandermonde matrix V Ξ defined above is equivalent to the share-generating matrix of the t-out-of-K Shamir’s secret sharing with evaluation points in Ξ. The subtractive property ensures that multiplying V T −1 by ξ clears its denominators for every size-t subset T ⊆ Ξ. The quality measurements provide norm bounds for various scaled interpolation maps and associated coefficient vectors. These bounds control noise growth and the parameters required by our later analysis. The quantity ρ(t) bounds the norm of the ξ-scaled interpolation coefficients used to reconstruct the value at zero from any t shares. It therefore controls the noise growth when Combine combines partial decryptions, and hence correctness (Theorem 2). The quantity γ(t) bounds the growth in size when interpolating from the value at zero and the evaluations at t − 1 points in Ξ to the evaluations at all points in Ξ, scaled by ξ. It appears in the conditions of the security theorem (Theorem 3). Finally, fix the evaluations at any t − 1 points in Ξ. Each remaining evaluation, scaled by ξ, can be written as an interpolation coefficient times the value at zero, plus a term determined by the fixed evaluations. The quantity θ(t) bounds the sizes of these interpolation coefficients. It determines how wide the flooding noise χ must be to hide the FHE decryption noise (cf. Corollary 1). We always have θ(t) ≤ γ(t). Upper bounds on these quantities for power-of-two fields are given in Lemma 4 in Appendix B.

Discrete Gaussians. We denote by D R,χ the (centred) discrete Gaussian distribution over R m with parameter χ, i.e. the distribution over R where for all x ∈ R m , the probability mass function D R,χ (x) ∝ −π∥x∥ /χ ρ is the Gaussian function of width χ, extended to a set S by ρ χ (S) := χ (x) where ρ χ (x) := e P m √ (x). More generally, for a positive definite Σ ∈ R φm×φm we denote by D R, the discrete ρ χ x∈S Σ Gaussian over R with covariance Σ, i.e. the distribution with probability mass function proportional T −1 to e −π·ψ(x) Σ ψ(x) , which for Σ = χ 2 · I φm is D R,χ . We recall the smoothing parameter [MR04]: for a full-rank lattice Λ and ϵ > 0, η ϵ (Λ) is the smallest χ > 0 such that ρ 1/χ (Λ ∗ \ {0}) ≤ ϵ, where Λ ∗ is the

<!-- page 11 -->

dual lattice. Throughout, η ϵ (R m ) denotes the smoothing parameter of R m identified with Z φm via the coefficient embedding.

Lattice assumption. We recall the LWE assumption with the matrix A sampled from a specified, not necessarily uniform distribution D A . This formulation accommodates both instances used in our security proof: uniform matrices and matrices whose columns are gadget decompositions of uniformly sampled vectors. Their hardness follows from the usual LWE assumption with uniform matrices, using [BLMR13, Theorem 4.3] for the latter.

Definition 2 (LWE). Let par = (R, n, m, t, q, χ, D A ) be parametrised by λ. The (decision) LWE par assumption states that for any PPT adversary A, it holds that Adv LWE par,A (λ) :=

A ← D A





" A ← D A  t×m  t×n Pr  A(A, B) = 1 R ← $ R q ; E ← $ D R,χ  − Pr A(A, B) = 1 ≤ negl(λ). B ← $ R t×m B := R · A + E mod q

The parameter t is suppressed if t = 1. The parameter D A is suppressed if it is the uniform distribution over R n×m . We write m = poly(λ) for the version where A is given unbounded polynomially many LWE samples, in which case D A is the distribution per sample which is over R nq .

:= (β 0 , β 1 , . . . , β ⌈ log β q ⌉ −1 ) for the gadget Gadget Matrix. For any β, q ∈ N with β ≤ q, we write g β,q vector and G β,q := I n ⊗ g β,q for the gadget matrix respectively [MP12]. We denote by G −1 β,q (·) the

−1 corresponding balanced β-ary decomposition operation, i.e. it holds G β,q · G −1 β,q (x) = x and G β,q (x) ≤

β/2 for any x ∈ R nq .

Fully-Homomorphic Encryption. A fully-homomorphic encryption (FHE) for a message space M consists of PPT algorithms (Setup, KGen, Enc, Eval, Dec) with the syntax:

pp ← Setup(1 λ ): The setup algorithm generates the public parameters pp. (pk, sk) ← KGen(pp): The key generation algorithm, on input the public parameters pp, generates the public and secret keys (pk, sk). ctxt ← Enc(pk, µ): The encryption algorithm encrypts a message µ ∈ M w.r.t. the public key pk. ctxt ′ ← Eval(pk, f, (ctxt i ) i∈I ): The evaluation algorithm takes the public key pk, a function f , and a set of ciphertexts (ctxt i ) i∈I indexed by I, and returns an evaluated ciphertext ctxt ′ . ′ µ ← Dec (sk, ctxt): The decryption algorithm, on input a secret key sk and ciphertext ctxt, outputs some µ ′ .

Because of the homomorphic nature of FHE, defining the correctness requirement is not straightforward and multiple proposals have appeared in the literature (e.g. [BCF + 25, BJSW25, ABMP26]). We state a version that follows the spirit of that in [ABMP26], which formalises correctness as an experiment so as to capture the adaptiveness of an adversary in choosing ciphertext evaluations, except that we further allow the flexibility to decrypt unevaluated ciphertexts.

Definition 3 (FHE Correctness). An FHE FHE is said to have correctness error ε, if for any PPT A, it holds that Pr Dec (sk, ctxt) = µ (sk, ctxt, µ) ← Correct FHE,A (1 λ ) ≥ 1 − ε(λ),

where Correct FHE,A is defined in Fig. 1. Furthermore, we say that FHE is correct if ε is negligible in λ.

Threshold FHE Construction

Requirements on Underlying FHE

Definition 4 (FHE with Linear Decryption). Let ξ ∈ R be coprime to q. An FHE scheme FHE has (R, n̂, p, q, ξ, B)-linear-decryption with error ε, if the following hold:

<!-- page 12 -->

Correct FHE,A (1 λ )

Correct thFHE,A (1 λ )

## L Query := ∅

## L Query := ∅

λ

λ

pp ← Setup(1 )

pp ← Setup(1 )

(pk, sk) ← KGen(pp)

EncO(id, µ ∈ M)

ctxt ← Enc(pk, µ)

## L Query [id] := (ctxt, µ)

(pk, (sk k ) k∈[K] ) ← KGen(pp)

EncO,EvalO

EvalO(id, f, (id i ) i∈I )

(T, id) ← A EncO,EvalO (pp, pk, (sk k ) k∈[K] )

id ← A

(pp, pk, sk)

parse (ctxt, µ) ← L Query [id]

parse (ctxt, µ) ← L Query [id]

for i ∈ I :

assert L Query [id i ] ̸ = ∅

pd k ← ParDec(pk, sk k , ctxt) ∀k ∈ T

return (sk, ctxt, µ)

parse (ctxt i , µ i ) ← L Query [id i ]

if µ ̸ = Combine(T, (pd k ) k∈T , ctxt)

then return 1

else return 0

ctxt ′ ← Eval(pk, f, (ctxt i ) i∈I )

## L Query [id] := (ctxt ′ , f ((µ i ) i∈I ))

Fig. 1: Correctness experiment for FHE and threshold FHE (Definitions 3 and 6).

1. The secret key space is R n̂ q , i.e. a secret key is a vector sk = ŝ ∈ R n̂ q . 2. There exists a deterministic Preproc algorithm, which inputs a ciphertext ctxt and outputs (ĉ 0 , ĉ 1 ) ∈ R n̂ q × R q ← Preproc(ctxt). 3. For any PPT A, it holds that   ĉ 1 − ŝ T · ĉ 0 mod q (sk, ctxt, µ) ← Correct FHE,A (1 λ )   Pr  = ξ −2 · ⌊q/p⌉ · µ + ê parse sk = ŝ 

∧ ∥ê∥ ≤ B

≥ 1 − ε(λ), where Correct FHE,A is defined in Fig. 1.

(ĉ 0 , ĉ 1 ) ← Preproc(ctxt)

If ε(λ) is negligible, we simply say that FHE has (R, n̂, p, q, ξ, B)-linear-decryption.

We will also require the FHE scheme to satisfy a security notion that we call “IND-CPA-with-leakage”. This notion says that, for an FHE scheme with linear decryption, the scheme is IND-CPA secure even when additionally giving out a masked leakage on its error term arising from the linear part of the decryption algorithm. Below, we recall standard IND-CPA and define the above variant.

Definition 5 (FHE IND-CPA(-with-Leakage) Security). Let FHE be an FHE scheme. We define the IND-CPA, and IND-CPA-with-(D, L, χ)-Leakage experiments Exp b FHE,A in Fig. 2. The IND-CPA and IND-CPA-with-(D, L, χ)-Leakage advantage functions of a PPT A against FHE are defined as

IND-CPA -wL

(λ) := Pr Exp 0 FHE,A (1 λ ) = 1 − Pr Exp 1 FHE,A (1 λ ) = 1 .

Adv

FHE,A ,(D, L, χ)

FHE is IND-CPA secure, respectively IND-CPA-with-(D, L, χ)-Leakage secure, if for any PPT A it holds

IND-CPA -wL

(λ) ≤ negl(λ).

that Adv

FHE,A ,(D, L, χ)

It is easy to see that the IND-CPA-with-Leakage security is implied by standard IND-CPA security if the masking noise for the leakage is large enough, specifically when it is super-polynomially larger than the error term being masked. This follows from a standard noise-flooding lemma, formalised below. Its proof is given in Appendix D.

Theorem 1 (Leakage Security). Let K = Q(ζ) be a cyclotomic field of degree φ and expansion factor c ∞ w.r.t. the coefficient ℓ ∞ -norm. Let R = Z[ζ] be its ring of integers. Let L, D ∈ N and FHE be an FHE scheme with (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE . Then, for any PPT adversary A against the IND-CPA-with-(D, L, χ)-Leakage security of FHE that makes at most Q ∈ poly(λ) queries to the oracle LeakO, there exists a PPT adversary B against the IND-CPA security of FHE such that C · Q · φ · L · c ∞ · D · B Adv IND-CPA-wL (λ) ≤ · Q · ε + + Adv IND-CPA FHE FHE,A,(D,L,χ) FHE,B (λ) χ where C = π/2 is a constant. In particular, if χ > λ ω(1) · Q · φ · L · c ∞ · D · B, FHE has (R, n̂, p, q, ξ, B)linear-decryption and is IND-CPA secure, then it is also IND-CPA-with-(D, L, χ)-Leakage secure.

<!-- page 13 -->

Exp b FHE,A (1 λ )

Exp b thFHE,A (1 λ )

λ

λ

pp ← Setup(1 )

pp ← Setup(1 )

(pk, sk) ← KGen(pp)

C ← A(pp)

// corrupt set C

## L Query := ∅; L leak := ∅

assert C ⊂ <t [K]

(pk, (sk k ) k∈[K] ) ← KGen(pp)

ChalO, EncO, EvalO, LeakO

′

b ←A

(pp, pk)

ChalO(id, µ 0 , µ 1 )

if L Query [id] = ∅ then

ctxt ← Enc(pk, µ b )

## L Query [id] := (ctxt, µ 0 , µ 1 )

return L Query [id]

## L Query := ∅; L Share := ∅; L Party := ∅

return b ′

EncO(id, µ)

b ′ ← A EncO,ChalO,EvalO,ParDecO pk, (sk k ) k∈C

assert |L Share | ≤ Q

LeakO(id, u ∈ R L )

if L Query [id] = ∅ then

ctxt ← Enc(pk, µ)

// partial decryptions for ≤ Q ciphertexts

if L leak [id] = ∅ then

return b ′

assert ∥u∥ ≤ D

// norm check

assert L Query [id] ̸ = ∅

ParDecO(id, k ∈ [K])

// query id honestly generated

assert L Query [id] ̸ = ∅

parse (ctxt, µ 0 , µ 1 ) ← L Query [id]

// queries id honestly generated

assert µ 0 = µ 1

## L Party [id] := L Party [id] ∪ {k}

// same plaintext in games 0 and 1

## L Query [id] := (ctxt, µ, µ)

return L Query [id]

EvalO(id, f, (id i ) i∈I )

if L Query [id] = ∅ then

for i ∈ I :

parse (ctxt, µ 0 , µ 1 ) ← L Query [id]

(ĉ 0 , ĉ 1 ) ← Preproc(ctxt)

assert L Query [id i ] ̸ = ∅

if µ 0 ̸ = µ 1 then assert |L Party [id] ∪ C| < t

µ := µ 0 = µ 1

// queries id i honestly generated

// if different plaintext in games 0 and 1,

ê := ĉ 1 − sk T · ĉ 0 − ξ −2 µ mod q

// unauthorised to decrypt

if L Share [id] = ∅ then

L f ← $ D R,χ

parse (ctxt i , µ 0,i , µ 1,i ) ← L Query [id i ]

ctxt ′ ← Eval(pk, f, (ctxt i ) i∈I )

µ ′ 0 := f ((µ 0,i ) i∈I )

µ ′ 1 := f ((µ 1,i ) i∈I )

pd k ← ParDec (pk, sk k , ctxt) ∀k ∈ [K]

L leak [id] ← u · ê + f

## L Share [id] := (pd k ) k∈[K]

// error u · ê masked by fresh f

## L Query [id] := (ctxt ′ , µ ′ 0 , µ ′ 1 )

parse (pd k ) k∈[K] ← L Share [id]

return L leak [id]

return pd k

return L Query [id]

Fig. 2: IND-CPA(-with-(D, L, χ)-Leakage) experiments Exp b FHE,A (1 λ ) for FHE (Definition 5), and IND-CPA

experiment Exp b thFHE,A (1 λ ) for threshold FHE (Definition 7). Code in dashed box , i.e. the oracles EncO, EvalO and LeakO, applies only to IND-CPA-with-(D, L, χ)-Leakage. Code in gray for the Q-bounded version of the experiment.

Threshold FHE Definitions

A t-out-of-K threshold fully-homomorphic encryption, or (t, K)-threshold FHE, for a set of K parties, threshold t ≤ K, and a message space M, consists of PPT algorithms (Setup, KGen, Enc, Eval, ParDec, Combine) with the syntax:

pp ← Setup(1 λ ): The setup algorithm generates the public parameters pp. (pk, (sk k ) k∈[K] ) ← KGen(pp): The key generation algorithm, on input the public parameters pp, generates the public key pk and a tuple of K secret keys (sk k ) k∈[K] for each user k ∈ [K]. ctxt ← Enc(pk, µ): The encryption algorithm encrypts a message µ ∈ M w.r.t. the public key pk. ctxt ′ ← Eval(pk, f, (ctxt i ) i∈I ): The evaluation algorithm takes the public key pk, a function f , and a set of ciphertexts (ctxt i ) i∈I indexed by I, and returns an evaluated ciphertext ctxt ′ . pd k ← ParDec (pk, sk k , ctxt): The partial decryption algorithm takes the secret key sk k of a user k and a ciphertext ctxt, and outputs a partial decryption pd k . µ ′ ← Combine pk, T, (pd k ) k∈T , ctxt : The combine algorithm, on input a tuple of partial decryptions (pd k ) k∈T from a set T of t users and a ciphertext ctxt, outputs some µ ′ .

Analogous to a (non-threshold) FHE, we define correctness of a threshold FHE by an experiment, in order to capture the adaptive nature of an adversary in choosing ciphertext evaluations and decryption.

Definition 6 (Threshold FHE Correctness). A (t, K)-threshold FHE thFHE is said to have correctness error ε(λ), if for any PPT A, Pr Correct thFHE,A (1 λ ) = 1 ≤ ε(λ),

where Correct thFHE,A is defined in Fig. 1. Furthermore, we say that thFHE is correct if ε is negligible in λ.

<!-- page 14 -->

Setup(1 λ )

Enc(pk, µ)

λ

pp FHE ← FHE.Setup(1 )

parse pk = (pk FHE , A, b)

Eval(pk, f, (ctxt i ) i∈I )

parse pk = (pk FHE , A, b)

ctxt FHE ← FHE.Enc(pk FHE , µ)

return pp := pp FHE

t ← $ R hq

KGen(pp)

parse ctxt i = (ctxt FHE,i , t i ) ∀i ∈ I

ctxt ′ FHE ← FHE.Eval(pk FHE , f, (ctxt FHE,i ) i∈I )

t ← $ R hq

return ctxt := (ctxt FHE , t)

parse pp = pp FHE

(pk FHE , sk FHE ) ← FHE.KGen(pp FHE )

ParDec(pk, sk k , ctxt)

// sk FHE = ŝ ∈ R n̂ q

A ← $ R n×m R ← $ R t×n r T := v 0 T · R mod q e ← $ D R, χ̄ z := (ŝ T , 0 T h ) · G β,q mod q ∈ R m

parse pk = (pk FHE , A, b)

parse sk k = s k

parse ctxt = (ctxt FHE , t)

return ctxt ′ := (ctxt ′ FHE , t)

Combine(pk, T, (pd k ) k∈T , ctxt)

parse pk = (pk FHE , A, b)

parse ctxt = (ctxt FHE , t)

(ĉ 0 , ĉ 1 ) ← FHE.Preproc(ctxt FHE ) ĉ 0 x := G −1 β,q t

(ĉ 0 , ĉ 1 ) ← FHE.Preproc(ctxt FHE ) ĉ 0 x := G −1 β,q t

b := r A + e + z mod q

c 0 := A · x mod q

pk := (pk FHE , A, b)

e k ← $ D R,χ

(s k ) k∈[K] := ξ · V · R mod q

pd k := s T k · c 0 + e k mod q

(sk k ) k∈[K] := (s k ) k∈[K]

return (pk, (sk k ) k∈[K] )

pd k ← ⌊pd k ⌉ 2 z

return pd k

c 1 := ξ 2 · b T · x mod q

pd ← ξ · v 0 T · V T −1 · (pd k ) k∈T mod q

µ̂ := ξ 2 · ĉ 1 − (c 1 − pd) mod q ∈ R q

µ ′ ← ⌊p/q · µ̂⌉ mod p ∈ R p

return µ ′

Fig. 3: thFHE from FHE. m = (n̂ + h) · log β q .

Definition 7 (Threshold FHE IND-CPA Security). A (t, K)-threshold FHE thFHE is (resp. Q- bounded) IND-CPA secure, if for any PPT adversary A it holds that λ λ Adv IND-CPA thFHE,A (λ) := Pr Exp thFHE,A (1 ) = 1 − Pr Exp thFHE,A (1 ) = 1 ≤ negl(λ),

where Exp b thFHE,A (resp. augmented with code in gray) is defined in Fig. 2.

Remark 3 (Alternative definition for threshold FHE security.). In Definition 7, more specifically in the security experiment defined in Fig. 2, the oracles keep track of ciphertexts ctxt by their identifiers id. An alternative would be to track ciphertexts ctxt by (the representation of) the ciphertexts ctxt themselves. This alternative definition is polynomially equivalent to that stated in Fig. 2 if ciphertexts are collision resistant, i.e. for honestly generated pk, it is infeasible to produce the same ciphertext ctxt by two distinct sequences of Enc(pk, ·) and Eval(pk, ·, ·) operations with honestly sampled randomness. This alternative definition has some practical benefits, to be elaborated in Remark 6.

Threshold FHE from FHE

Construction. Let 1 < p ≤ q be integers. We require two ingredients:

– FHE is an FHE scheme which has (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE (Definition 4). – Ξ is a ξ-subtractive set of cardinality K, with quality measurements (ρ, γ, θ) = (ρ(t), γ(t), θ(t)) (Definition 1).

Given the above, in Fig. 3 we construct a (t, K)-threshold FHE scheme thFHE par with parameters par = (FHE, R, n, m, h, q, β, χ̄, χ, z, Ξ).

Theorem 2 (Correctness). If ξ ∈ Z, FHE has (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE and |q mod p| β z−1 ≥ + ξ · B + c ∞ · λ · m · ξ · χ̄ · + t · ρ · ( λ · χ + 2 ) . 2p

Then, thFHE in Fig. 3 has correctness error ε ≤ ε FHE +φ·(m+t)·2 −λ . In particular, if min{log(1/ε FHE ), λ− log φ − log(m + t)} ≥ ω(log λ), then thFHE is correct.

<!-- page 15 -->

The proof of Theorem 2 is given in Appendix E. Here we provide a brief sketch of the proof.

Proof (Proof Sketch). The proof compares the value reconstructed by threshold decryption with the linear-decryption equation of the underlying FHE scheme. Both ParDec and Combine compute the same gadget preimage −1 ĉ 0 x = G β,q t

For a recovery set T , linearly combining the partial decryptions recovers the shared secret r and gives

pd = ξ 2 r T Ax + ξv 0 T V T −1 e T mod q.

On the other hand, the corresponding ciphertext component satisfies

c 1 = ξ 2 r T Ax + ξ 2 e T x + ξ 2 ŝ T ĉ 0 mod q.

Hence c 1 − pd cancels the common term ξ 2 r T Ax and leaves the FHE linear-decryption term, ξ 2 ŝ T ĉ 0 , plus a residual error f := ξ 2 · e T · x − ξ · v 0 T · V T −1 · e T .

In the final rounding in Combine one has to additionally account for the error ξ 2 ê arising from the (R, n̂, p, q, ξ, B)-linear-decryption property of FHE. The correctness condition in Eq. (5) is set so that the norm of the whole error term remains below q/(2p), ensuring the scaling by p/q recovers µ except with the stated failure probability.

Remark 4 (“Average-case” correctness analysis.). √ In the proof of correctness (Theorem 2) we (probabilistically) upper bound ∥e T · x∥ by c ∞ · m · χ̄ · λ · β/2. This is known as the so called “worst-case” correctness analysis. A standard heuristic is the so-called “average-case” correctness analysis where one would upper bound the norm of e T · x directly by treating it as a discrete Gaussian rather than bounding e and x separately. Over Z, this would shave off a square-root-dimension factor, i.e. φ · m from the bound. Taking the potential skewness of R into account, however, we conservatively shave a factor of c ∞ √ · ≤ φ · instead, i.e. we take ∥e · x∥ ≤ c · · χ̄ · λ · β/2. We can apply the same treatment c 2 −1 to the term ξ √ · v 0 · V T · e T and upper bound its norm by c 2 · t · ρ · (χ + 2 z−1 ) · λ instead of by c ∞ · t · ρ · (χ · λ + 2 z−1 ). Here e T contains the rounding errors d k of ParDec, and the heuristic treats each e k + d k as noise of width at most χ + 2 z−1 . To summarise, with the “average-case” heuristic, we can replace the constraint Eq. (5) with |q mod p| β √ ≥ + ξ 2 · B + c 2 · λ · m · ξ 2 · χ̄ · + t · ρ · (χ + 2 z−1 ) . 2p

Theorem 3 (Security). Let FHE be an FHE scheme with (R, n̂, p, q, ξ, B)-linear-decryption and Ξ be a ξ-subtractive set of cardinality K with √ quality measurements (ρ, γ, θ) (Definition 1). Let ϵ ∈ (0, p 1/2], Q ∈ poly(λ), q, ξ be coprime, χ ∗ 1 √ ≥ 2 · η ϵ (R t ) be such that there exists χ̂ > √ 0 with γ ≤ ∗ ∗ t −1 −2 χ · (2η ϵ (R ) + (χ 1 ) ) − χ̂ , and χ 2 ≥ 2 · η ϵ (R m ) be such that γ · φm · β/2 ≥ 1 and 2QK · φm · ∗ 2 −1 − χ̄ −2 , where c ⊗ := 1 if f is a power of two and c ⊗ := m 2 t c 2 · c ⊗ t t t · γ · β/2 ≤ χ · n (2η ϵ (R ) + (χ 2 ) ) o

otherwise. Let D t := t̃ : t ← $ R hq , t̃ := G −1 β,q (t) . Define the parameter sets:

– thFHE: par = (FHE, R, n, m, h, q, β, χ̄, χ, z, Ξ), – LWE: par 1 := (R, h log β q , poly(λ), q, χ ∗ 1 , D t ), – LWE: par 2 := (R, n, m, q, χ ∗ 2 ), – FHE: par 3 := (θ, K, χ).

Consider the (t, K)-threshold FHE scheme thFHE par in Fig. 3. For all PPT A that requests partial decryptions on at most Q ciphertexts (i.e. in the Q-bounded IND-CPA experiment of Definition 7), there exist PPT B 1 , B 2 , B 3 such that Adv IND-CPA thFHE,A (λ) ≤ ε where

12·Q·ϵ LWE ε := 2·t· Adv LWE +Adv IND-CPA-wL par 1 ,B 1 (λ)+Adv par 2 ,B 2 (λ) + FHE,par 3 ,B 3 (λ) 1−ϵ +4·t· 2QK + ·ϵ. 1−ϵ

<!-- page 16 -->

The proof of Theorem 3 is given in Appendix F. Here we provide a brief sketch of the proof.

Proof (Proof Sketch). Since the rounding ⌊·⌉ 2 z in ParDec is a deterministic public post-processing of each partial decryption, it suffices to prove security for the scheme without it. The proof proceeds through hybrids, Hyb b,i for i = 0, 1, 2, 3, that first remove the threshold layer and then reduce the remaining indistinguishability to the security of the underlying FHE. Starting from the real experiment Hyb b,0 , the first hop to Hyb b,1 rewrites b and the partial decryptions pd k so that the threshold-layer correlations are simulated explicitly. This step is justified by standard LWE: the term Adv LWE par 1 ,B 1 (λ) comes from the tag- LWE −1 dependent rerandomisation via G (t), while Adv par 2 ,B 2 (λ) comes from replacing the key-switching-key component b. The two statistical terms in ε are losses involved in the reductions from LWE. The next hop, Hyb b,1 ≡ Hyb b,2 , replaces the partial decryptions of challenge ciphertexts by uniform values. This uses the Vandermonde structure induced by the ξ-subtractive set Ξ and the fact that A receives fewer than t − |C| honest partial decryptions for every ciphertext whose plaintext differs between games 0 and 1. Finally, Hyb b,2 ≡ Hyb b,3 handles ciphertexts whose plaintext is the same in both games. Using the linear-decryption equation from Definition 4, the corresponding partial decryptions are rewritten so that the only remaining dependence on sk FHE = ŝ is through the FHE decryption noise ê. These values are simulated by the leakage oracle in the IND-CPA-with-Leakage experiment, giving the term Adv IND-CPA-wL FHE,par 3 ,B 3 (λ). At this point, challenge shares are uniform and non-challenge shares are simulated from the leakage oracle, so summing the hybrid losses gives the stated bound ε.

Remark 5 (Relation to IND-CPA D security of FHE). By setting K = t = 1, so that thFHE collapses to a plain FHE scheme, we recover from Definition 7 the IND-CPA D security notion for FHE defined in [LM21]. This means that our construction thFHE in Fig. 3 is also a compiler which turns any FHE satisfying the requirements in Section 4.1 into an FHE that is IND-CPA D secure [LM21].

Remark 6 (Pseudorandom tag and context-dependent decryption.). In our construction in Fig. 3, the tag t in a ciphertext ctxt = (ctxt FHE , t) is randomly sampled during encryption and refreshed during homomorphic evaluation, independent of the main part ctxt FHE of the ciphertext. If the underlying FHE has collision-resistant ciphertexts in the sense described in Remark 3, then our construction would be secure wrt. the alternative security definition described in Remark 3 where the oracles keep track of ciphertexts via their own representations rather than identifiers. This means that the security proof would also go through, in the random oracle model, if we replace the truly random tag t ← $ R hq by a pseudorandom t := H(ctxt FHE ) where H is a hash function modelled as a random oracle. Deriving tags in a pseudorandom manner has the obvious advantages of reducing ciphertext size and more importantly reducing use of randomness, which could be scarce in constrained devices. Furthermore, we can easily upgrade our construction to support context-dependent decryption [BBN + 25] by hashing ctxt FHE together with the context string.

Remark 7 (Optimised Lagrange interpolation in Combine). One optimisation that may not arise naturally from the protocol description concerns Combine, where the message is reconstructed from the t partial decryptions using the (scaled) first row ξ · v 0 T V T −1 of the inverse Vandermonde matrix V T of the active nodes {ζ k } k∈T . Instead of inverting the t × t matrix V T over R q , we use that Q this row is the vector of Lagrange basis polynomials evaluated at 0, namely L k (0) k∈T with L k (0) = j∈T \{k} ζ j /(ζ j − ζ k ), which costs O(t 2 ) to form since the nodes are exactly the K-th roots of unity, the identity Q Q directly. Moreover, K (x − ζ ) (x − ζ ) = x − 1 lets us rewrite each weight as a product over the complement, c m∈T Q m∈T Q c L k (0) = − K m∈T (−ζ m ) m∈T c (ζ k − ζ m ). Evaluating the row over whichever of T or T is smaller thus costs O(t · min{t, K − t}), keeping Combine cheap for large committees whenever t is close to 1 or to K. 11

Practical Instantiation

Tulva is a generic construction to build threshold FHE from an FHE scheme. Concretely, its implementation consists of two main components: Preproc and the threshold decryption layer. The first establishes the

Asymptotically, the row can be built in quasi-linear time O(t log 2 t) via fast multipoint evaluation [vzGG13]; this appears less efficient at the committee sizes we consider, but could be relevant for larger ones.

<!-- page 17 -->

bridge between the FHE scheme and our threshold layer: given a generic FHE ciphertext, it produces a ciphertext satisfying the requirements described in Section 4. This design makes our threshold decryption layer generic wrt. the choice of FHE scheme, at the cost of making Preproc scheme dependent. Let us start by discussing potential instantiations of Preproc for some of the most popular modern FHE schemes:

BFV/BGV/CKKS [Bra12, FV12, BGV12, CKKS17]: These schemes usually operate over rings that can be directly used by our threshold decryption layer, admitting Preproc to be just the identity in some scenarios. Definition 4 expects a BFV-style ciphertext, which can be achieved for BGV through simple transforms (see Appendix A of [AP13]) and for (discrete [BCKS24]) CKKS through bootstrapping (e.g., [Kim25]). For the original (approximate) CKKS [CKKS17], on the other hand, an additional challenge is in separating message from noise, a non-trivial security problem [LM21] that afflicts approximate schemes whenever the existence of decryption oracles is considered. This problem is mostly orthogonal to the threshold setting, and considering potential solutions (e.g., [BCD + 25a]) is left as future work.

FHEW/TFHE [DM15, CGGI16]: These schemes are typically built on top of ring variants [DM15] of AP- style [AP14] bootstrapping for LWE ciphertexts in the form Z n̂ q × Z q , which cannot be directly used by our threshold layer. For these cases, we employ Packing Key Switching [CGGI16, MS18, CDKS21] techniques, which, given a vector of k LWE ciphertexts encrypting messages {m i } i∈[0,k) ∈ Z kq , produces a single P k−1 ciphertext of the form R n̂ q × R q (for some ring of degree at least k) encrypting i=0 m i X i ∈ R q . This ciphertext can either be defined over the ring required by the threshold layer, or ring switched [GHPS12] to it. Alternatively, these schemes could also be instantiated with AP-style bootstrapping for RLWE ciphertexts [MS18, GP25], which already perform similar packing by construction.

Remark 8 (Bootstrapping). In addition to structural requirements, our construction also requires the FHE scheme to provide a minimum ratio between ciphertext modulus and noise magnitude at the end of the homomorphic evaluation. For leveled schemes, one could consider increasing parameters to account for it, but this would introduce performance overheads for the entire computation. A more generic and modular solution is to perform a bootstrapping over the results of the evaluation procedure. We do not specify this bootstrapping as part of Preproc, as schemes may have different ways of performing it, but, in practice, including a bootstrapping at the beginning of Preproc is a natural solution for most scenarios, and we adopt it in our implementation.

Implementation Details

To demonstrate compatibility with existing FHE schemes, our implementation 12 natively consumes TFHE ciphertexts produced by the tfhe-rs library. A thin compatibility layer (written in Rust, with Python bindings) performs the necessary repacking and key-switching within tfhe-rs: since tfhe-rs operates on LWE ciphertexts over Z q , up to φ of them are gathered into a single ciphertext over R q , as required by our threshold layer. As a first step of Preproc, the ciphertext is bootstrapped to reduce the noise magnitude, include the ξ −2 slack, and switch to the modulus q required by our construction, which is significantly larger than the 2 64 modulus tfhe-rs typically operates on. We provide our own implementation of the [CGGI16] and [GP25] bootstrappings: the former is generally faster for small plaintext spaces (p = 2 4 , as used in our examples), at the cost of higher memory usage and a larger public key, while the latter is more efficient for larger plaintext spaces (p = 2 6 or p = 2 8 ). We report runtimes only for [CGGI16], since our example parameters use the small plaintext space, but also include [GP25] (with the [CDKS21] repacking technique) for use in other parameter regimes. Before this bootstrapping step, all homomorphic operations are performed in the smaller modulus and require no parameter adaptation compared to a non-threshold setting; we use the parameters suggested by tfhe-rs for 2 −128 security and correctness errors. The threshold layer is orchestrated in Python, with the most computationally intensive operations implemented in C and exposed via bindings; this keeps the critical code easy to optimise and the overall implementation simple to modify. The C layer is mainly an adaptation of the code given in [CCC + 25], and Gaussian sampling, used for both key generation and noise flooding, is a generalised and optimised implementation of the one in [LSS24]. We operate on power-of-two cyclotomic rings, the most common in practical FHE implementations, and employ standard RNS and NTT polynomial arithmetic (also known as double-CRT [GHS12]). We

Available at https://github.com/osdnk/tulva.

<!-- page 18 -->

applied standard AVX-512 optimisations, especially in the NTT transforms, while also optimising for cache locality and parallelism; the code remains portable to any platform, with a performance hit where AVX-512 is unavailable.

Parameter Selection

Summary of constraints. For the convenience of referencing, we summarise Theorems 1 to 3 and Remark 4 in the following Corollary 1. We note that Item 4 is associated to the “average-case” correctness heuristic.

Corollary 1. Let R = Z[ζ] be of ring degree φ and with field expansion factor c p w.r.t. the coefficient ℓ p norm. Let FHE be an FHE scheme. Let Ξ be a ξ-subtractive set of cardinality K with quality measurements (ρ, γ, θ) (Definition 1). Let δ = δ(λ) be an independent parameter such that 2 δ ∈ λ ω(1) . Suppose par = (FHE, R, n, m, h, q, β, χ̄, χ, z, Ξ), χ ∗ 1 , χ ∗ 2 > 0, ϵ ∈ (0, 1/2] ∩ negl(λ) and Q ∈ poly(λ) satisfy:

1. FHE has (R, n̂, p, q, ξ, B)-linear-decryption (Definition 4). 2. FHE is IND-CPA secure. 3. q, ξ are coprime. √ √ p| β z−1 4. |q mod + ξ · B + c · λ · · ξ · χ̄ · + t · ρ · (χ + ) + 12 ≤ 2p (Eq. (6)). δ · θ. 5. χ ≥ 2 · Q · φ · K · c ∞ · B √ 6. LWE R,h,poly(λ),q,χ ∗ 1 14 , χ ∗ 1 ≥ 2 · η ϵ (R t ), χ̂ > 0 and

γ 2 + 2 ≤ t χ χ̂ 2η ϵ (R ) + (χ ∗ 1 ) 2

φm · β/2 ≥ 1, and, with c ⊗ t := 1 if f is a power of two and

## 7 LWE R,n,m,q,χ ∗ 2 , χ ∗ 2 ≥ c ⊗ t otherwise, t :=

2 · η ϵ (R m ), γ ·

Q · K · φ · m · c 22 · (c ⊗ t ) · γ · β + 2 ≤ 2 · χ 2 χ̄ 2η ϵ (R m ) 2 + (χ ∗ 2 ) 2

8. 8 · (3Q + t · QK + 3t) · ϵ ≤ 2 −δ . 15

Then, the (t, K)-threshold FHE scheme thFHE par in Fig. 3 is correct (with “average-case” correctness) and Q-bounded IND-CPA secure. In particular, if par, χ ∗ 1 and χ ∗ 2 are such that conditions 6, 7 and 8 hold for all Q ∈ poly(λ), then thFHE par in Fig. 3 is also (unbounded) IND-CPA secure.

Proof. Follows from putting Theorems 1 to 3 and Remark 4 together: Items 3–4 imply the correctness constraints in Theorem 2 and Remark 4; Items 1, 2, 5 imply that FHE is IND-CPA-with-(D, K, χ)-Leakage secure with D = θ by Theorem 1; security follows from Items 3, 6, 7, 8 by invoking Theorem 3.

We search for parameter sets that minimise the public-key |pk| and partial-decryption |pd| sizes, while keeping (partial) decryption reasonably efficient, subject to the correctness and security constraints of Theorems 1 to 3 and Remark 4. We set the plaintext modulus p = 2 4 = 16, a common choice for FHEW/TFHE-based applications [BBB + 23], and target λ = 128 bits of computational security, δ = 64 bits of statistical security, and Q = 2 64 partial decryption queries. Recall that the underlying FHE must have (R, n̂, p, q, ξ, B)-linear-decryption; we insist on a noise bound B ≤ 2 70 to leave enough room for FHE.Preproc. When searching for parameters using the Lattice Estimator [APS15], we keep the degree ℓ of gadget decomposition low, for faster partial decryption and decryption, and require β ∈ [2 35 , 2 50 ] so that it corresponds to one “limb” in the RNS decomposition, allowing a more efficient gadget decomposition. Following this methodology, we found parameter sets for conductors f ∈ {512, 4096} and various threshold profiles. The small ring is selected for low latency (a single decryption is fast to compute, with reasonable per-sample efficiency), the large ring for high throughput (when many messages are to be

We let 2 δ absorb the π/2 factor. This implies LWE R,h ⌈ log q ⌉ ,poly(λ),q,χ ∗ ,D t where D t = U([−β/2, β/2) ∩ Z) h ⌈ log β q ⌉ [BLMR13, Theorem 4.3].

β

This makes the statistical terms of Theorem 3 total at most 2 −δ , using 1/(1 − ϵ) ≤ 2.

<!-- page 19 -->

Table 1: tulva-tfhe parameters across conductors f ∈ {512, 4096} (ring degree φ = f/2), Q = 2 64 , p = 2 4 . A set of width w supports every threshold t ∈ [2, w] ∪ [K − w, K]. Here the gadget base β is constrained to a single RNS limb. The column |ctxt| gives the size of the input ciphertext, i.e. before Preproc.

K

w

λ

χ

ℓ n̂ n h

S.1 8 4 130 2 5 32 10 1 165 2 2 97 S.2 32 16 131 2 5 36 16 3 195 2 2 81 S.3 128 16 129 2 300 6 45 27 9 324 2 240 2 72 S.4 128 64 128 2 329 7 49 38 17 462 2 253 2 45 S.5 512 16 128 2 368 8 55 37 17 576 2 276 2 71

30 2 196 2 98 30 2 208 2 82 56 2 247 2 82 70 2 259 2 48 80 2 283 2 75

L.1 8 4 162 2 215 5 L.2 32 16 144 2 240 5 L.3 128 16 134 2 308 7 L.4 128 64 137 2 336 7 L.5 512 16 128 2 376 8

χ̄ |ctxt| [kB] |pk| [kB] |pd| [kB] |pd|/bit [b]

decrypted). Instead of specifying the threshold t directly, we specify the number of parties K and a window size w, covering all profiles with t ∈ {2, . . . , w} ∪ {K − w, . . . , K}. Since the partial decryption size and time scale with min{t, K − t}, a window of size w collects exactly the profiles whose cost is no worse than that at min{t, K − t} = w. The resulting parameters are listed in Table 1. When calculating the size of a public key, we assume that A in the public key is sampled using a 256-bit seed, and that the public key only stores this seed and the vector b.

Experiments

All experiments were conducted on a single AWS c7a.32xlarge instance, equipped with 128 AMD EPYC 9R14 (Genoa) vCPUs and 256 GB of RAM. For S.[1-5], we considered two types of experiments: decryption of a single message and decryption of φ messages (the full ring), the latter having a substantial impact on the Preproc phase. For L.[1-5], we report only the full-ring decryption results, as employing such a large ring for single-message decryption is unreasonable. The reported times are available in Table 2. We do not report the KGen time as it was not optimised (it takes at most 36 seconds) and is a one-time cost that can be amortised over many decryptions. We report Preproc as a subroutine separate from ParDec and Combine to highlight the cost of the pre-decryption phase, which is the most expensive part (yet, secret independent). Table 2 confirms the expected scaling of tulva-tfhe. For the small ring, a single decryption is fast across all profiles: the pre-decryption stays below one second and the online cost is at most a few milliseconds of partial decryption followed by a combination step of tens to hundreds of microseconds (e.g. 0.13 s, 0.64 ms and 39 µs for S.1). Preproc is by far the most expensive step and, as expected, scales with the number of decrypted messages, growing from sub-second for a single message to between 6 and 31 s for the full φ = 256 ring. At the same time, the per-message partial-decryption and combination times stay within a factor of three. Decrypting the full ring therefore amortises this fixed cost over many messages, and the large ring (L.[1-5]) pushes this further by packing φ = 2048 messages per batch. Finally, the online cost scales with min{t, K − t} rather than by K: for instance L.5 (t/K = 16/512) combines in 0.88 ms, faster than L.4 (t/K = 64/128) at 1.50 ms, which stays consistent with Remark 7.

Comparison with [ZZLP25]. The concurrent work of [ZZLP25] also targets LWE threshold decryption, removing the decryption noise through an interactive MPC rounding rather than masking it. We compare their secret-dependent online latency for a single ciphertext [ZZLP25, Table 2] with our ParDec + (network delay) + Combine, matching their party count to our active threshold t (Table 3). For Tulva, the reported latency covers partial decryption, communication, and share combination after public ciphertext preprocessing has completed. Preprocessing is excluded from this comparison and reported separately in Table 2. The results show lower latency for Tulva and a smaller increase as network delay grows, consistent with its single communication round. Their “preparation” phase is interactive and generates secret correlated randomness, whereas our Preproc is public, non-interactive, and ciphertextdependent, and can be performed by an untrusted server. Tulva’s shorter secret-dependent phase comes

<!-- page 20 -->

Table 2: Runtimes of the threshold layer on the parameter sets of Table 1, using the [CGGI16] bootstrapping.

Set

t/K

msgs Preproc [s] ParDec [ms] Combine [µs]

φ φ φ φ φ

S.1 4/8

S.2 16/32

S.3 16/128

S.4 64/128

S.5 16/512

L.1 4/8 L.2 16/32 L.3 16/128 L.4 64/128 L.5 16/512

φ φ φ φ φ

Table 3: Secret-dependent online-phase latency for a single ciphertext.

Set

ping

t

1 ms 1 ms 10 ms 10 ms

S.1 S.2 S.1 S.2

[ZZLP25] [ms]

ours [ms]

at the cost of ciphertext-dependent preprocessing, which takes 0.13 s for S.1 and 0.16 s for S.2 (Table 2). The preparation phase of [ZZLP25] can instead be completed before the ciphertext becomes available.

Examples of FHEVM Programs

Threshold FHE can be used to implement confidential smart contracts: many users encrypt private inputs under one FHE public key, a neutral evaluator (the validator set) applies a public function f to the ciphertexts while learning nothing about the inputs, and a t-of-K committee runs the ParDec and Combine procedures of the threshold FHE scheme to reveal only a chosen part of the output. The parties that hold the data are thus separated from the party that computes and from the parties that decrypt. Furthermore, the committee composition can change dynamically over time. We describe four concrete FHEVM programs and report the runtimes of their implementations using tulva-tfhe. Detailed descriptions of the functions f are deferred to Appendix A. Since every value occupies a single Z p element, each program is correct only under explicit domain constraints that bound its inputs, e.g. the value ranges such as [0, B) below. The exact constraints are given in Appendix A. For each program we report runtimes over the five small-ring parameter sets S.1–S.5 of Table 1: homomorphic evaluation of f (Eval), the functional bootstrap that carries each revealed value to the committee (Preproc), and the committee’s partial and final decryption (ParDec, Combine). The three profile-dependent phases (Preproc, ParDec, Combine) are listed per profile and Eval is listed once. As in Section 5.3, we omit key generation, a one-time cost that is amortised over many reveals.

1. Sealed-Bid Auction (Table 4). A pool of n users encrypt their bids over [0, B) and submit them to the contract, which homomorphically computes the winning bid and bidder index. The contract reveals the winner and the price at which the auction clears but not the losing bids.

2. Confidential ERC-20 Transfer (Table 5). ERC-20 is the standard smart-contract interface for fungible Ethereum tokens. In our specific example, account balances [0, B) are encrypted, and a transfer

<!-- page 21 -->

Table 4: Sealed-bid auction (Algorithm 1).

Set t/K

Eval [ms] Preproc [ms] ParDec [ms] Combine [µs]

S.1 4/8 S.2 16/32 S.3 16/128 S.4 64/128 S.5 16/512

Parameters: n = 4 bidders, max. bid B = 4.

Table 5: Confidential ERC-20 (Algorithm 2).

Set t/K

Eval [s] Preproc [ms] ParDec [ms] Combine [µs]

S.1 4/8 S.2 16/32 S.3 16/128 S.4 64/128 S.5 16/512

Parameters: n = 256 accounts, R = 10 rounds, max. balance B = 4, max. amount A = 4.

Table 6: Dark-pool DEX (Algorithm 3).

Set t/K

Eval [s] Preproc [ms] ParDec [ms] Combine [µs]

S.1 4/8 S.2 16/32 S.3 16/128 S.4 64/128 S.5 16/512

Parameters: S = 4 resting orders, R = 10 rounds, max. price P = 4, max. volume V = 4.

Table 7: Median price oracle (Algorithm 4).

Set t/K

Eval [s] Preproc [ms] ParDec [ms] Combine [µs]

S.1 4/8 S.2 16/32 S.3 16/128 S.4 64/128 S.5 16/512

Parameters: n = 128 submissions, max. value H = 8.

moves an encrypted amount over [0, A) between accounts. Throughout the protocol, multiple transfers can be processed sequentially (each with its own round). The contract only reveals the final balances of selected accounts. The rest of the state remains encrypted.

3. Dark-Pool DEX (Table 6). The contract holds an encrypted order book. It matches incoming requests against it, publishing only the executed fills while prices over [0, P ), volumes over [0, V ), and unmatched orders remain encrypted. After removing the matched orders, the contract updates the order book with new encrypted submissions. This process repeats for R rounds, and the unmatched orders are never revealed.

4. Median Price Oracle (Table 7). The contract aggregates n encrypted submissions over [0, H) from many nodes into their median. Computing the median homomorphically requires obliviously sorting the inputs, for which we employ Batcher’s odd–even mergesort.

Across all four programs, the threshold reveal (Preproc + ParDec + Combine) costs at most a few hundred milliseconds for the small committees and stays below 1.2 seconds even for K = 512. For the computa-

<!-- page 22 -->

tionally heavy programs this overhead is negligible relative to the evaluation. Thus, for any non-trivial computation, tulva-tfhe adds little overhead over a non-threshold deployment.

AI Disclosure

The construction, all proof ideas and the parameter analysis are due to the authors. The first version of this work was written entirely by hand and was then proofread by Claude Opus 5 and 5.5 as well as by GPT-5.6 Sol. The models pointed out small gaps in some proofs and proposed corrections, which the authors verified before adopting, and the authors revised every passage edited by the models in subsequent editing rounds. The scripts that select the parameters of Table 1 were first written by hand, and Claude Opus 5 and 5.5 were then used to optimise their search logic and to refactor them. The authors checked that the resulting scripts are consistent with the analysis in the paper. The algorithms in the implementation were first written by hand, and Claude Opus 5 and 5.5 as well as GPT-6 Astra were used extensively to rewrite and optimise existing parts of the implementation.

## Acknowledgements

Russell W. F. Lai and Micha l Osadnik are supported by the Research Council of Finland grant 358951 and the Future Makers Program project SPICED of the Technology Industries of Finland Centennial Foundation. Ivy K. Y. Woo is supported by the Research Council of Finland grant 358950. Antonio Guimarães is partially supported by grants JDC2024-055789-I and CEX2024-001471-M funded by MICIU/AEI/10.13039/501100011033 and ESF+, and by the ERC Proof of Concept grant VERIFHE (GA: 101287502). Valerio Cini is supported by the European Union’s Horizon Europe research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 101202597 (ACryL). Ivy K. Y. Woo would like to thank Yongsoo Song for sharing the reduction in [HKM + 26] during the Novel Lattice Assumptions Workshop in July 2026, which significantly improved the results of this work.

## References

ABMP26.

Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, and Yuriy Polyakov. Applicationaware approximate homomorphic encryption: Configuring FHE for practical use. CiC, 2(4):3, 2026. doi:10.62056/ayl83z10k. 11 Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty computation with low communication, computation and interaction via threshold FHE. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 483–501. Springer, Berlin, Heidelberg, April 2012. doi:10.1007/978-3-642-29011-4_29. Martin R. Albrecht and Russell W. F. Lai. Subtractive sets over cyclotomic rings - limits of Schnorr-like arguments over lattices. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 519–548, Virtual Event, August 2021. Springer, Cham. doi:10.1007/978-3-030-84245-1_18. 9, 10, 28, 30 Jacob Alperin-Sheriff and Chris Peikert. Practical bootstrapping in quasilinear time. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 1–20. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/978-3-642-40041-4_1. 17 Jacob Alperin-Sheriff and Chris Peikert. Faster bootstrapping with polynomial error. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 297–314. Springer, Berlin, Heidelberg, August 2014. doi:10.1007/978-3-662-44371-2_17. 17 Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. J. Math. Cryptol., 9(3):169–203, 2015. doi:10.1515/jmc-2015-0016. 18 Wojciech Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296:625–635, 1993. doi:10.1007/BF01445125. 30 Loris Bergerat, Anas Boudi, Quentin Bourgerie, Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Parameter optimization and larger precision for (T)FHE. Journal of Cryptology, 36(3):28, July 2023. doi:10.1007/s00145-023-09463-5. 18 Dan Boneh, Benedikt Bünz, Kartik Nayak, Lior Rotem, and Victor Shoup. Context-dependent threshold decryption and its applications. In Goichiro Hanaoka and Bo-Yin Yang, editors, ASI- ACRYPT 2025, Part VI, volume 16250 of LNCS, pages 506–538. Springer, Singapore, December 2025. doi:10.1007/978-981-95-5119-4_16. 16

AJL + 12.

AL21.

AP13.

AP14.

APS15.

Ban93.

BBB + 23.

BBN + 25.

<!-- page 23 -->

BCD + 25a. Flávio Bergamaschi, Anamaria Costache, Dana Dachman-Soled, Hunter Kippen, Lucas LaBuff, and Rui Tang. Revisiting the security of approximate FHE with noise-flooding countermeasures. In Tibor Jager and Jiaxin Pan, editors, PKC 2025, Part V, volume 15678 of LNCS, pages 102–134. Springer, Cham, May 2025. doi:10.1007/978-3-031-91832-2_4. 17 BCD + 25b. Carl Bootland, Kelong Cong, Daniel Demmler, Tore Kasper Frederiksen, Benoit Libert, Jean- Baptiste Orfila, Dragos Rotaru, Nigel P. Smart, Titouan Tanguy, Samuel Tap, and Michael Walter. Threshold (fully) homomorphic encryption. Cryptology ePrint Archive, Report 2025/699, 2025. URL: https://eprint.iacr.org/2025/699. 3 BCF + 25. Chris Brzuska, Sébastien Canard, Caroline Fontaine, Duong Hieu Phan, David Pointcheval, Marc Renard, and Renaud Sirdey. Relations among new CCA security notions for approximate FHE. CiC, 2(1):20, 2025. doi:10.62056/aee0iv7sf. 11 BCK + 22. Mihir Bellare, Elizabeth C. Crites, Chelsea Komlo, Mary Maller, Stefano Tessaro, and Chenzhi Zhu. Better than advertised security for non-interactive threshold signatures. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part IV, volume 13510 of LNCS, pages 517–550. Springer, Cham, August 2022. doi:10.1007/978-3-031-15985-5_18. 4 BCKS24. Youngjin Bae, Jung Hee Cheon, Jaehyung Kim, and Damien Stehlé. Bootstrapping bits with CKKS. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part II, volume 14652 of LNCS, pages 94–123. Springer, Cham, May 2024. doi:10.1007/978-3-031-58723-8_4. 17 BFM + 25. Zvika Brakerski, Offir Friedman, Avichai Marmor, Dolev Mutzari, Yuval Spiizer, and Ni Trieu. Threshold FHE with efficient asynchronous decryption. Cryptology ePrint Archive, Report 2025/712, 2025. URL: https://eprint.iacr.org/2025/712. 3, 4, 5, 8, 9 BGG + 18. Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold cryptosystems from threshold fully homomorphic encryption. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 565–596. Springer, Cham, August 2018. doi:10.1007/978-3-319-96884-1_19. 3, 4, 8 BGV12. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, pages 309–325. ACM, January 2012. doi:10.1145/2090236.2090262. 17 BJSW25. Olivier Bernard, Marc Joye, Nigel P. Smart, and Michael Walter. Drifting towards better error probabilities in fully homomorphic encryption schemes. In Serge Fehr and Pierre-Alain Fouque, editors, EUROCRYPT 2025, Part VIII, volume 15608 of LNCS, pages 181–211. Springer, Cham, May 2025. doi:10.1007/978-3-031-91101-9_7. 11 BKW26. Chris Brzuska, Michael Klooß, and Ivy K. Y. Woo. Threshold public-key encryption: Definitions, relations, and CPA-to-CCA transforms. In Shi Bai and Edoardo Persichetti, editors, PKC 2026, Part IV, volume 16554 of LNCS, pages 162–197. Springer, Cham, May 2026. doi: 10.1007/978-3-032-26740-5_6. 3, 5, 8 BLMR13. Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. Key homomorphic PRFs and their applications. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 410–428. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/ 978-3-642-40041-4_23. 11, 18 BP26. Luı́s T. A. N. Brandão and René Peralta. NIST first call for multi-party threshold schemes. NIST IR 8214C, 2026. URL: https://csrc.nist.gov/pubs/ir/8214/c/final. 3 Bra12. Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 868–886. Springer, Berlin, Heidelberg, August 2012. doi:10.1007/978-3-642-32009-5_50. 6, 17 BS23. Katharina Boudgoust and Peter Scholl. Simple threshold (fully homomorphic) encryption from LWE with polynomial modulus. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part I, volume 14438 of LNCS, pages 371–404. Springer, Singapore, December 2023. doi:10.1007/ 978-981-99-8721-4_12. 3, 4, 8 CCC + 25. Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, and Eduardo Soria-Vazquez. Verifiable computation for approximate homomorphic encryption schemes. In Yael Tauman Kalai and Seny F. Kamara, editors, CRYPTO 2025, Part VII, volume 16006 of LNCS, pages 643–677. Springer, Cham, August 2025. doi:10.1007/978-3-032-01907-3_21. 17 CDKS21. Hao Chen, Wei Dai, Miran Kim, and Yongsoo Song. Efficient homomorphic conversion between (ring) LWE ciphertexts. In Kazue Sako and Nils Ole Tippenhauer, editors, ACNS 2021, Part I, volume 12726 of LNCS, pages 460–479. Springer, Cham, June 2021. doi:10.1007/978-3-030-78372-3_18. 6, 17 CGGI16. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, pages 3–33. Springer, Berlin, Heidelberg, December 2016. doi:10.1007/978-3-662-53887-6_1. 6, 17, 20

<!-- page 24 -->

CKKS17.

Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASI- ACRYPT 2017, Part I, volume 10624 of LNCS, pages 409–437. Springer, Cham, December 2017. doi:10.1007/978-3-319-70694-8_15. 6, 17 Valerio Cini, Russell W. F. Lai, and Ivy K. Y. Woo. Pilvi: Lattice threshold PKE with small decryption CLW25. shares and improved security. In Goichiro Hanaoka and Bo-Yin Yang, editors, ASIACRYPT 2025, Part VI, volume 16250 of LNCS, pages 539–569. Springer, Singapore, December 2025. doi:10.1007/ 978-981-95-5119-4_17. 4, 5, 6, 8, 9, 10, 34, 39, 43, 51, 59 DDEK + 23. Morten Dahl, Daniel Demmler, Sarah El Kazdadi, Arthur Meyre, Jean-Baptiste Orfila, Dragos Rotaru, Nigel P. Smart, Samuel Tap, and Michael Walter. Noah’s Ark: Efficient threshold-FHE using noise flooding. In Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 35–46, 2023. doi:10.1145/3605759.3625259. 3, 4, 5 DLN + 21. Julien Devevey, Benoı̂t Libert, Khoa Nguyen, Thomas Peters, and Moti Yung. Non-interactive CCA2-secure threshold cryptosystems: Achieving adaptive security in the standard model without pairings. In Juan Garay, editor, PKC 2021, Part I, volume 12710 of LNCS, pages 659–690. Springer, Cham, May 2021. doi:10.1007/978-3-030-75245-3_24. 8 DM15. Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping homomorphic encryption in less than a second. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 617–640. Springer, Berlin, Heidelberg, April 2015. doi:10.1007/978-3-662-46800-5_24. Fhe24. Fhenix. Fhenix: Private DeFi on Ethereum with fully homomorphic encryption. https://www.fhenix. io/, 2024. Accessed: 2026-06-09. 3 FV12. Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144, 2012. URL: https://eprint.iacr.org/2012/144. 6, 17 GHPS12. Craig Gentry, Shai Halevi, Chris Peikert, and Nigel P. Smart. Ring switching in BGV-style homomorphic encryption. In Ivan Visconti and Roberto De Prisco, editors, SCN 12, volume 7485 of LNCS, pages 19–37. Springer, Berlin, Heidelberg, September 2012. doi:10.1007/978-3-642-32928-9_2. 6, GHS12. Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic evaluation of the AES circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 850–867. Springer, Berlin, Heidelberg, August 2012. doi:10.1007/978-3-642-32009-5_49. 17 GMPW20. Nicholas Genise, Daniele Micciancio, Chris Peikert, and Michael Walter. Improved discrete gaussian and subgaussian analysis for lattice cryptography. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part I, volume 12110 of LNCS, pages 623–651. Springer, Cham, May 2020. doi:10.1007/978-3-030-45374-9_21. 47, 48 GP25. Antonio Guimarães and Hilder V. L. Pereira. Fast amortized bootstrapping with small keys and polynomial noise overhead. In Chun-Ying Huang, Jyh-Cheng Chen, Shiuh-Pyng Shieh, David Lie, and Véronique Cortier, editors, ACM CCS 2025, pages 2967–2981. ACM Press, October 2025. doi:10.1145/3719027.3765181. 17 HKM + 26. Yisol Hwang, Shuichi Katsumata, Seonhong Min, Guilhem Niot, and Yongsoo Song. Proving threshold Regev PKE from adaptive hint-MLWE: Efficient, non-interactive, and CCA secure. Cryptology ePrint Archive, Paper 2026/1585, 2026. URL: https://eprint.iacr.org/2026/1585. 9, 22, 46, 48, 50 Kim25. Jaehyung Kim. Bootstrapping GBFV with CKKS. Cryptology ePrint Archive, Report 2025/888, 2025. URL: https://eprint.iacr.org/2025/888. 17 KLL + 26. Won Kim, Changmin Lee, JeongHwan Lee, Alain Passelègue, and Damien Stehlé. Asynchronous Lagrange-based threshold FHE with smaller modulus overhead. In CRYPTO 2026, 2026. doi: 10.1007/978-3-032-35374-0_1. 4, 5, 6, 8, 9, 30, 31, 32, 34 KLNO24a. Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, and Micha l Osadnik. RoK, paper, SISsors – toolkit for lattice-based succinct arguments. Cryptology ePrint Archive, Report 2024/1972, 2024. URL: https://eprint.iacr.org/2024/1972. 28 KLNO24b. Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, and Michal Osadnik. RoK, paper, SISsors toolkit for lattice-based succinct arguments - (extended abstract). In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part V, volume 15488 of LNCS, pages 203–235. Springer, Singapore, December 2024. doi:10.1007/978-981-96-0935-2_7. 9, 10 KLSS23. Duhyeong Kim, Dongwon Lee, Jinyeong Seo, and Yongsoo Song. Toward practical lattice-based proof of knowledge from hint-MLWE. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 549–580. Springer, Cham, August 2023. doi:10.1007/ 978-3-031-38554-4_18. 46 LM21. Baiyu Li and Daniele Micciancio. On the security of homomorphic encryption on approximate numbers. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part I, volume 12696 of LNCS, pages 648–677. Springer, Cham, October 2021. doi:10.1007/978-3-030-77870-5_23. 16,

<!-- page 25 -->

LSS24.

Vadim Lyubashevsky, Gregor Seiler, and Patrick Steuer. The LaZer library: Lattice-based zero knowledge and succinct proofs for quantum-safe privacy. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, ACM CCS 2024, pages 3125–3137. ACM Press, October 2024. doi: 10.1145/3658644.3690330. 17 Russell W. F. Lai, Monisha Swarnakar, and Ivy K. Y. Woo. Leaky LWE: Learning with errors with semi-adaptive secret- and error-leakage. CiC, 2(3):21, 2025. doi:10.62056/ah89ksuc2. 9, 10, 29, 46, 47, 51, 55 Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 700–718. Springer, Berlin, Heidelberg, April 2012. doi:10.1007/978-3-642-29011-4_41. 6, 7, 11 Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. In 45th FOCS, pages 372–381. IEEE Computer Society Press, October 2004. doi: 10.1109/FOCS.2004.72. 10 Daniele Micciancio and Jessica Sorrell. Ring packing and amortized FHEW bootstrapping. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 100:1–100:14. Schloss Dagstuhl, July 2018. doi:10.4230/LIPIcs.ICALP. 2018.100. 6, 17 Hiroki Okada and Tsuyoshi Takagi. Low communication threshold FHE from standard (module-)LWE. In Goichiro Hanaoka and Bo-Yin Yang, editors, ASIACRYPT 2025, Part VII, volume 16251 of LNCS, pages 165–198. Springer, Singapore, December 2025. doi:10.1007/978-981-95-5122-4_6. 3, 4, 8 Alain Passelègue and Damien Stehlé. Low communication threshold fully homomorphic encryption. In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part I, volume 15484 of LNCS, pages 297–329. Springer, Singapore, December 2024. doi:10.1007/978-981-96-0875-1_10. 4 Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 2013. doi:10.1017/CBO9781139856065. 16 Zama. fhEVM: Confidential EVM smart contracts using fully homomorphic encryption. Whitepaper, https://github.com/zama-ai/fhevm/blob/main/fhevm-whitepaper.pdf, 2023. Accessed: 2026-06- 09. 3 Zama. TFHE-rs: A pure Rust implementation of the TFHE scheme for Boolean and integer arithmetics over encrypted data, version 1.4.1. https://github.com/zama-ai/tfhe-rs, 2023. Accessed: 2026- 02-01. 4, 6 Guy Zyskind, Doron Zarchy, Max Leibovich, and Chris Peikert. High-throughput universally composable threshold FHE decryption. In Chun-Ying Huang, Jyh-Cheng Chen, Shiuh-Pyng Shieh, David Lie, and Véronique Cortier, editors, ACM CCS 2025, pages 2339–2353. ACM Press, October 2025. doi:10.1145/3719027.3744884. 3, 4, 5, 19, 20

LSW25.

MP12.

MR04.

MS18.

OT25.

PS24.

vzGG13.

Zam23a.

Zam23b.

ZZLP25.

<!-- page 26 -->

Table 8: Functional-bootstrap tables instantiated by the FHEVM programs.

Definition

Description

Table

One-input table T =c 1{x = c} T ≤a,b (x ≤ a) ? x : b T refresh x

Program(s)

equality test of x against a public constant c keep x when x ≤ a, otherwise lift it to b identity bootstrap (a “refresh”): clears accumulated noise

Two-input table T > 1{x > y} T sel x ? y : 0 T debit (x ≥ y) ? x−y : x T credit (x ≥ y) ? y : 0 T = 1{x = y} T scan 1{x = 1 ∧ y = 0}

Auction, Dark-pool Dark-pool Dark-pool

greater-than test of two bids multiplexer: pass value y when bit x is set, else 0 new sender balance: x less amount y when affordable amount credited to the receiver, or 0 if balance x < y equality test of two encrypted values prefix-scan step: fires when equality bit x = 1 and carry y =0 logical AND (one-hot x, empty-slot bit y): the replace flag

x ∧ y

T ∧

Two-input sort T sort (min(x, y), max(x, y))

Auction Auction, Dark-pool ERC-20 ERC-20 Dark-pool Dark-pool

Dark-pool

sort the pair (x, y) into (min, max)

Algorithm 1: Sealed-bid first-price auction.

Input: distinct bids b 0 , . . . , b n−1 ∈ {0, . . . , B − 1} Output: winner index w and clearing price b w

for i ← 0 to n − 1 do s i ← 0 for j ← 0 to n − 1 with j ̸ = i do if b i > b j then s i ← s i + 1 // s i ← s i + T > (b i , b j ): n(n−1) bts P 5 o i ← 1{s i = n − 1} for all i, then w ← i i · o i P (o ? b : 0) 6 b w ← i i i 7 return (w, b w )

A

Algorithms for FHEVM Programs

Dark-pool, Oracle

// win count of i.

P // w ← P i i · T =c (s i ): n bts // b w ← i T sel (o i , b i ): n bts

For each of the four programs in Section 6, we state the plaintext algorithm and its homomorphic evaluation at the level of ciphertexts. Throughout we write Enc(x) for a ciphertext encrypting x, i.e. shorthand for thFHE.Enc(pk, x). We use {0, 1, . . . , p − 1} to represent Z p . We write 1{c} for the bit 1 when a condition c holds and 0 otherwise, and (c ? a : b) for the value a if c holds and b otherwise. Homomorphic addition and multiplication by a public scalar need no bootstrapping (bts) and are evaluated directly. Everything else is built from the tables in Table 8, the gadgets shared across the four programs. Each table T takes one or two encrypted inputs, returns one encrypted output (or two for T sort ), and is evaluated by a single functional bootstrap. Using these gadgets, we describe the homomorphic realisations of the four programs below, with pseudocode listed in Algorithms 1 to 4. In each program, the highlighted comments indicate the number of bootstraps required for each step.

1. Sealed-Bid Auction (Algorithm 1). A first-price auction reveals only the winner and the price they pay. Assume the bids P are distinct; then one bidder i outbids all n − 1 others. To find that bidder, form the win count s i = j̸ = i T > (b i , b j ) for bids in [0, B). Computing all n of them costs n(n − 1) bootstraps. Bidder i wins exactly when s i = n − 1, so o i = T =c (s i ) at c = P n − 1 is a one-hot indicator of the P winner. The two outputs are linear in o i . The winner index is w = i i o i ; the clearing price is b w = i T sel (o i , b i ), where the multiplexer T sel keeps b i on the winning slot and zeroes the rest. Evaluation is n 2 + n bootstraps (Table 4), and each of w, b w is read by one Preproc. Correctness needs B 2 ≤ p for the two-input comparison T > on bids in [0, B), and n ≤ p to keep the win counts s i and the winner index w below p.

<!-- page 27 -->

Algorithm 2: Confidential ERC-20 transfers.

(ρ)

Input: sender balances s 0 , . . . , s n−1 , receiver balances r 0 , . . . , r n−1 , per-round transfer amounts a i Output: updated balances (s i , r i ) i

for ρ ← 1 to R do for i ← 0 to n − 1 do (ρ) if s i ≥ a i then (ρ) r i ← r i + a i (ρ) s i ← s i − a i

return (s i , r i ) i

(ρ)

// r i += T credit (s i , a i ): Rn bts (ρ) // s i ← T debit (s i , a i ): Rn bts

// queried accounts only. 1 Preproc each

Algorithm 3: Dark-pool order matching (stateful, R rounds).

Input: book of S resting asks (π s , ν s ) s (price, volume); requests (ℓ (ρ) , q (ρ) ) and pending orders (π̂ (ρ) , ν̂ (ρ) ), for ρ = 1, . . . , R Output: per-round fills f (1) , . . . , f (R)

for ρ ← 1 to R do for s ← 0 to S − 1 do κ s ← (π s ≤ ℓ (ρ) ) ? π s : P // κ s ← T ≤ℓ (ρ) ,P (π s ): RS bts β ← min s κ s // S−1 comparisons (β, ·) ← T sort (β, κ s ), then β ← T refresh (β): RS bts if β = P then f (ρ) ← 0 // nothing crosses (branchless) else s ⋆ ← first s with π s = β // ∀s (S slots): e s ← T = (π s , β), m s ← T scan (e s , g): 2RS bts f (ρ) ← min(q (ρ) P , ν s ⋆ ) // v ← T refresh s T sel (m s , ν s ) : S+1 bts, // (f (ρ) , ·) ← T sort (q (ρ) , v): +1 bt, total R(S+2) ν s ⋆ ← ν s ⋆ − f (ρ) // ∀s: ν s −= T sel (m s , f (ρ) ) (only s ⋆ changes): RS bts if ν s ⋆ = 0 then (π s ⋆ , ν s ⋆ ) ← (π̂ (ρ) , ν̂ (ρ) ) // d ← T =0 (ν s ⋆ ), ∀s: h s ← T ∧ (m s , d), // π s ← T sel (h s , π̂ (ρ) ) + T sel (1−h s , π s ), // ν s ← T sel (h s , ν̂ (ρ) ) + T sel (1−h s , ν s ): (5S+1)R bts

return (f (ρ) ) ρ

// book stays hidden. 1 Preproc per round

2. Confidential ERC-20 Transfer (Algorithm 2). Each account on a confidential ERC-20 ledger carries an encrypted balance, and a transfer moves tokens without exposing any balance or the amount sent. Account i holds a sender balance s i and a receiver balance r i as persistent state. A transfer (ρ) debits the sender only when its funds suffice. In round ρ, two two-input bootstraps on (s i , a i ) decide (ρ) (ρ) (ρ) account i’s transfer obliviously: T debit (s i , a i ) returns the new sender balance (s i − a i if s i ≥ a i , (ρ) (ρ) else s i ) and T credit (s i , a i ) the moved amount (a i if affordable, else 0). The receiver is credited by (ρ) (ρ) r i += T credit (s i , a i ), and T debit (s i , a i ) replaces s i , for 2Rn bootstraps in total. A balance is read with one Preproc. The encoding is correct while AB ≤ p for the two-input tables T debit , T credit on balances in [0, B) and amounts in [0, A), and every reachable balance stays below p as a receiver balance accumulates credits across rounds.

3. Dark-Pool DEX (Algorithm 3). The resting book of a dark pool consists of S orders (π s , ν s ), prices and volumes held encrypted state and never revealed; only the trades executed against it become public. Each round matches one buy request (ℓ (ρ) , q (ρ) ), a limit price and a quantity, against the cheapest ask it crosses, reports the fill f (ρ) , and updates the book, refilling an emptied slot from a pending order (π̂ (ρ) , ν̂ (ρ) ). To keep the matched slot secret, every step runs over all S slots and carries the match in a

<!-- page 28 -->

Algorithm 4: Median price oracle.

Input: price submissions x 0 , . . . , x n−1 ∈ {0, . . . , H − 1} Output: robust aggregate price

(y 0 , . . . , y n−1 ) ← sort(x 0 , . . . , x n−1 ) // Batcher network of T sort : (log 2 n) 2 − log 2 n + 4 n/4 − 1 bts 2 return y ⌊n/2⌋

// nondecreasing.

// median only. 1 Preproc

one-hot indicator m s . The round has three stages: cross prices the eligible asks and takes the lowest, β; locate marks the first slot at β as m s ; and fill and update computes the fill and writes the book back.

Cross. An ask crosses when π s ≤ ℓ (ρ) . The crossing key κ s = T ≤ℓ (ρ) ,P (π s ) keeps a crossing ask at its own price and lifts every other to a reserved value P above all prices (prices in [0, P )), so the lowest crossing price is β = min s κ s . This minimum is a tournament of S − 1 pairwise sorts T sort , then one T refresh .

Locate. The match is the first slot at price β, a one-hot m s . A per-slot equality e s = T = (π s , β) flags every slot at β, and a left-to-right prefix scan keeps the first. The scan carries a flag g, initially 0, that flips once a match has been passed: T scan sets m s = 1 exactly when e s = 1 and g = 0, then g += m s . The scan is sequential, slot s reading slot s − 1’s flag. P (ρ) Fill and update. The matched volume v = = s T sel (m s , ν s ) is cleaned by T refresh , and the fill f (ρ) (ρ) min(q , v) is one further T sort . The matched ask is drawn down by ν s −= T sel (m s , f ), and an emptied match is refilled: d = T =0 (ν s ⋆ ) tests emptiness, h s = T ∧ (m s , d) flags the slot, and every slot is rewritten as π s ← T sel (h s , π̂ (ρ) ) + T sel (1 − h s , π s ) (ν s analogously). All S slots are rewritten, so only the matched one changes. For volumes in [0, V ), the round is correct while P ≤ V , 2V ≤ p (the fill sorts the volumes q (ρ) and the matched volume, both < p/2), and P < p/2.

4. Median Price Oracle (Algorithm 4). A median price oracle aggregates n encrypted submissions into their median. The circuit sorts them obliviously and returns the middle element. The sorting algorithm is Batcher’s odd-even merge-sort. Each comparator is one two-input sort T sort , hence one bootstrap. For n a power of two the network has (log 2 n) 2 − log 2 n + 4 n/4 − 1 comparators (1471 at n = 128). Reading the median y ⌊n/2⌋ is one Preproc. Correctness needs every submission in [0, H) with H = p/2, the domain of the two-input sort.

Additional Preliminaries

B

We give some additional preliminaries beyond those in Section 3 that are used in the proofs of our main theorems.

We write ⊗ for the tensor (i.e. Kronecker) product of matrices. The matrix tensor product satisfies the mixed product property: For all matrices A, B, C and D of suitable dimensions, we have (A⊗B)(C⊗D) = AC ⊗ BD.

Supplementary lemmas. Below are lemmas on the ring expansion factors, subtractive sets, Gaussian norm bounds, and noise flooding. Lemma 1. If f is a power of two, then c 2 ≤ φ and c ∞ ≤ φ. If f is an odd prime, then c 2 ≤ f and c ∞ ≤ 2φ.

Proof. The claims about c ∞ follow by realising that the proof of [AL21, Proposition 2] not only applies to the ring of integers R of K but also to K in general. For the claims about c 2 , we use q Items (i) and

(ii) of [KLNO24a, Lemma 1], which state the following: For any x ∈ K, (i) ∥ψ(x)∥ 2 ≤ rad(f) · ∥σ(x)∥ 2 f and (ii) ∥σ(x)∥ 2 ≤ f̂ · ∥ψ(x)∥ 2 where rad(f) is the radical (i.e. product of all distinct prime factors)

of f and f̂ = f q if f is odd and f̂ = f/2 ∈ K. Substituting x = a · b, we have q if f is even. Consider a, b q

∥ψ(a · b)∥ 2 ≤ rad(f) · ∥σ(a · b)∥ 2 ≤ rad(f) · ∥σ(a)∥ 2 · ∥σ(b)∥ 2 ≤ rad(f) · f̂ · ∥ψ(a)∥ 2 · ∥ψ(b)∥ 2 . Observe f f f that rad(f) · f̂ = f if f is an odd prime and rad(f) · f̂ = f̂ = φ if f is a power of 2. f f

<!-- page 29 -->

Lemma 2. Let f be a power of two. Apply each component σ i , i ∈ Z × f , of the canonical embedding σ of K entrywise to vectors and matrices over K. Then for any matrix M ∈ K n×d ,

∥M∥ 2,2 = max ∥σ i (M)∥ 2,2 . ×

i∈Z f

i n×d Proof. Throughout, let i and j range over Z × f , let σ i be the embedding with σ i (ζ) = ζ , and M ∈ K × We assume f ≥ 2, since f = 1 and f = 2 give the same field K = Q. Then Z f is the set of odd residues modulo f, and φ = f/2. We will show that (1) Ψ (M) is unitarily equivalent to the block-diagonal matrix   σ 1 (M)   φn×φd .. D :=  ,  ∈ C

σ f−1 (M)

(2) the former implies ∥M∥ 2,2 = ∥D∥ 2,2 , and (3) ∥D∥ 2,2 = max i ∥σ i (M)∥ 2,2 . (1): First, let U ∈ C φ×φ be the matrix such that its (i, k)-th entry is ζ ik / φ, for all rows i and columns k ∈ {0, . . . , φ − 1}, so that σ(x) = φ · U · ψ(x) ∀x ∈ K.

That is, U is the conversion matrix between the coefficient P φ−1 and canonical embeddings of x ∈ K up to scaling. The inner product of rows i and j of U is φ 1 k=0 ω k where ω := ζ i−j . If i = j this equals 1. If i ̸ = j, then i − j is even and nonzero modulo f, so ω ̸ = 1 and ω φ = ζ f(i−j)/2 = 1, hence the sum is (ω φ − 1)/(ω − 1) = 0. Therefore U is unitary. Next, for a vector x ∈ K d , let σ̂(x) := (σ i (x)) i ∈ C φd

list the embeddings of x grouped by embedding rather than by entry. Also, let P d be the permutation matrix reordering coordinates from grouping by entry to grouping by embedding, so that we have

φ · W d · ψ(x)

where

σ̂(x) =

W d := P d · (I d ⊗ U).

Observe that the matrix W d is unitary, as it is a product of unitary matrices. Since each σ i is a ring homomorphism, σ i (Mx) = σ i (M) · σ i (x) for every i, implying σ̂(Mx) = D · σ̂(x). Together with ψ(Mx) = Ψ (M) · ψ(x) (Section 3), this gives

∀x ∈ K d .

W n · Ψ (M) · ψ(x) = D · W d · ψ(x)

As ψ(K d ) = Q φd contains a basis of C φd , it follows that the block diagonalisation of Ψ (M) is

Ψ (M) = W n ∗ · D · W d ,

that is, Ψ (M) is unitarily equivalent to D.

(2): Since Ψ (M) is real, its conjugate transpose is Ψ (M) T , and since W n is unitary, (1) gives

Ψ (M) T · Ψ (M) = W d ∗ · D ∗ · W n · W n ∗ · D · W d = W d ∗ · (D ∗ D) · W d .

Hence Ψ (M) T Ψ (M) and D ∗ D are unitarily similar and have the same eigenvalues, so s max (Ψ (M)) = s max (D). Since ∥M∥ 2,2 = s max (Ψ (M)) by [LSW25, Lemma 2] (Section 3), we get ∥M∥ 2,2 = ∥D∥ 2,2 .

(3): The matrix D ∗ D is block diagonal with diagonal blocks σ i (M) ∗ σ i (M) ∈ C d×d . The eigenvalues of a block-diagonal matrix are those of its diagonal blocks, so the largest eigenvalue of D ∗ D is the maximum over i of the largest eigenvalue of σ i (M) ∗ σ i (M). Taking square roots gives

∥D∥ 2,2 = s max (D) = max s max (σ i (M)) = max ∥σ i (M)∥ 2,2 .

i

i

Finally, combining (2) and (3), we get ∥M∥ 2,2 = ∥D∥ 2,2 = max i ∥σ i (M)∥ 2,2 .

<!-- page 30 -->

Lemma 3 (Adapted from [AL21, Theorems 1 and 2]). If f n is a power of two, then o 1, ζ, . . . , ζ f−1 P i−1 j is ξ-subtractive for ξ(t) = 2 ⌈log t⌉ . If f = p is a prime, then the set j=0 ζ : i ∈ [p − 1] is ξ-subtractive

for ξ(t) = 1.

The following lemma, adapted from [KLL + 26], provides bounds on the quality of the subtractive set we adopt in our implementation. Its proof is given in Appendix C.

Lemma 4 (Quality of Subtractive Sets. Adapted from [KLL + 26, Corollary 5.1]). Let f and K ≤ f be powers of two, η := ζ f/K a primitive K-th root of unity, and let Ξ ′ := η i : 0 ≤ i < K . For any 2 ≤ t ≤ K and ξ = ξ(t) = 2 ⌈log t⌉ , the set Ξ ′ and any subset thereof have the quality

⌊t/2⌋

Y

−(t−1)

ρ(t) ≤ ξ · 2

, sin (πk/K) k=1

θ(t) ≤ ξ · A, γ(t) ≤ ξ · (K − t + 1)(A 2 + (t − 1)B 2 ) + 1,

where

⌊(t−2)/2⌋

Y

Y

A := 2 t−1

cos 2 πk K ,

B :=

k=1

k=1

⌊(t−1)/2⌋

⌊(t−3)/2⌋

sin (πk/K)

Y

cos 2 πk K

k=1

Lemma 5 (Adapted from [Ban93, Lemma 1.5]). Let R = Z[ζ] with ring degree φ. For any m ∈ N, χ > 0, δ > 0, ≤ 2 −φm , Pr ∥e∥ 2 > χ φm e ← $ D R,χ i h Pr ∥e∥ ∞ > χ δ e ← $ D R,χ ≤ φm · 2 −δ .

The following lemma is standard and can be shown easily by bounding the KL divergence and then via Pinsker’s inequality.

∥c∥ 2

n n Lemma 6 (Noise Flooding). For any n ∈ N, χ > 0, c ∈ R n , it holds that KL(D R,χ , D R,χ +c) ≤ π· χ 2 2 ∥c∥ n n and SD(D R,χ , D R,χ + c) ≤ π 2 · χ 2 , where KL and SD denote the KL divergence and the statistical n n distance, respectively. In particular, if χ ≥ λ ω(1) · ∥c∥ 2 , one has D R,χ ≈ s D R,χ + c.

For our security proofs, we will need to apply noise flooding over Q many adaptive oracle queries. Naively making Q hybrid hops will lead to √ a factor Q blow-up in the advantage bound. The following lemma provides a tighter bound with only Q blow-up, it follows from bounding the KL divergence over all Q queries carefully and then applying Pinsker’s inequality.

Lemma 7. Let n ∈ N and χ, B > 0. For b ∈ {0, 1} and any (computationally unbounded) adversary A, let Flood b A be the game defined below:

Flood b A

return A O b ()

O b (c ∈ R n )

assert ∥c∥ 2 ≤ B

n e ← $ D R,χ

return a := b · c + e

For any (computationally unbounded) A that makes at most Q ∈ N queries to O b , it holds that Q · B Pr Flood 0 A = 1 − Pr Flood 1 A = 1 ≤ π 2 · χ

Proof. Fix any A. As A can be unbounded, we may assume it is deterministic – fixing its coins to the ones such that the LHS of the concerned inequality is maximised. The view of A is the tuple of all oracle answers (a 1 , . . . , a Q ). Below, denote by P and P̂ the joint distributions of these answers in Flood 1 A and Flood 0 A , respectively. The LHS quantity is thus at most SD(P, P̂ ), which we bound in the rest. We will use the chain-rule for KL divergence, for which we provide a proof below for completeness.

<!-- page 31 -->

Proposition 1. For any two distributions P, P̂ over tuples a = (a 1 , . . . , a Q ), the KL divergence between P and P̂ satisfies X X KL(P ∥ P̂ ) = P (a <i ) · KL P (a i | a <i ) P̂ (a i | a <i ) .

i∈[Q] a <i

Q

Proof. The probability chain rule gives P (a) = a <i = (a 1 , . . . , a i−1 ). Hence

P (a)

X

KL(P ∥ P̂ ) =

P (a) log

Q

i∈[Q] P (a i | a <i ) and P̂ (a) =

i∈[Q] P̂ (a i | a <i ), where

P̂ (a) X X P (a i | a <i ) = P (a) log P̂ (a i | a <i ) a i∈[Q]

a

X X

=

P (a) log

P (a i | a <i )

P̂ (a i | a <i ) X X X P (a i | a <i ) = P (a ≤i , a >i ) log P̂ (a i | a <i ) a >i i∈[Q] a ≤i

i∈[Q] a

X X

=

P (a ≤i ) log

i∈[Q] a ≤i

X

X X

=

P (a <i )

P (a i | a <i )

P̂ (a i | a <i )

P (a i | a <i )

P (a i | a <i ) log

P̂ (a i | a <i ) a i i∈[Q] a <i X X = P (a <i ) · KL P (a i | a <i ) P̂ (a i | a <i ) .

i∈[Q] a <i

In the above, the fourth line uses a = (a ≤i , a >i ) where we denote a ≤i P = (a 1 , . . . , a i ) and a >i = (a i+1 , . . . , a Q ). The fifth line holds by definition of marginal distribution, i.e. a >i P (a ≤i , a >i ) = P (a ≤i ). The sixth line uses P (a ≤i ) = P (a <i ) P (a i | a <i ), and the last line is by realising that the inner sum over P P (a i |a <i ) a i is the conditional KL divergence KL(P (a i | a <i ) ∥ P̂ (a i | a <i )) = a i P (a i | a <i ) log P̂ (a |a )

<i

i

With A deterministic, once the prefix a <i is fixed, the query c i is a fixed vector and the only fresh n randomness in a i is e i ← $ D R,χ , drawn independently of the prefix. The conditional distributions are n n therefore P (a i | a <i ) = c i + D R,χ and P̂ (a i | a <i ) = D R,χ By the KL divergence bound in Lemma 6 and the norm-check in the oracle O b , for every prefix a <i ,

π∥c i ∥ 22 πB 2 KL P (a i | a <i ) P̂ (a i | a <i ) ≤ ≤ χ 2 χ 2

Note that the above upper bound is a fixed value independent of the distribution of ∥c i ∥ (the latter may adaptively depend on the prefix a <i ). Plugging into Eq. (9), we get

X X

KL(P ∥ P̂ ) ≤

i∈[Q] a <i

P

where the last equality uses

πB 2 πQB 2 = , χ χ 2

P (a <i ) ·

a <i P (a <i ) = 1. Finally, using Pinsker’s inequality gives

r

Q · B χ

KL(P ∥ P̂ ) ≤ π 2 ·

SD(P, P̂ ) ≤

C

Proof of Lemma 4 (Quality of Subtractive Sets)

To prove Lemma 4, we will use the following Lemma 8 which provides more general bounds for a subtractive set that consists of roots of unity. It is adapted from [KLL + 26] to suit the norm convention in this work.

<!-- page 32 -->

Lemma from [KLL + 26, Theorem 4.3]). Let f be a power of two, so that φ = f/2, let 8 (Adapted f−1 , and let ξ = ξ(t) = 2 ⌈log t⌉ . For any 2 ≤ t ≤ f, the set Ξ and any subset thereof have Ξ = 1, ζ, . . . , ζ the quality

⌊t/2⌋

Y

ρ(t) ≤ ξ · 2 −(t−1)

, sin (πk/f) k=1

θ(t) ≤ ξ · A, γ(t) ≤ ξ · (f − t + 1)(A 2 + (t − 1)B 2 ) + 1,

where

⌊(t−2)/2⌋

Y

A := 2 t−1

cos 2 πk f ,

B :=

k=1

⌊(t−1)/2⌋

⌊(t−3)/2⌋

sin 2 (πk/f)

Y

Y

cos 2 πk f

k=1

k=1

Q := ν∈S\{µ} β−ν Proof. Throughout this proof, for a set S ⊆ {0}∪Ξ and an element β ∈ / S, we write λ S→β µ µ−ν for the Lagrange coefficient of the element µ ∈ S. 16 With this notation, the row vector ξ · v 0 T · V T −1 has its {0}∪T ∗ →α −1 µ-th entry being ξ · λ T µ →0 , and the matrix ξ · V Ξ\T ∗ · V {0}∪T , ∗ has its (α, µ)-th entry being ξ · λ µ where the row index α ranges over Ξ \ T ∗ and the column index µ over {0} ∪ T ∗ . By Lemma 3, all these elements lie in R. Since f is a power of two,

∥x∥ ≤ ∥σ(x)∥ ∞ = max |σ ℓ (x)|

ℓ

for any x ∈ K, so it suffices to bound the canonical embedding. Fix one embedding σ ℓ , sending ζ to a primitive f-th root of unity ω = exp(πir/φ) with r coprime to f. For exponents a, b we have |σ ℓ (ζ a )| = 1, |σ ℓ (ζ a − 0)| = 1, and σ ℓ (ζ a − ζ b ) = ω a−b − 1 = |exp(2πi r(a − b)/f) − 1| = 2 sin πr(a − b)/f .

As r is coprime to f, multiplication by r permutes the integers modulo f, so we may assume r = 1 without loss of generality.

Proposition 2 (Sine-product). For any m distinct non-zero integers d 1 , . . . , d m modulo f,

⌈m/2⌉ Y ≤ |sin(πd /f)| sin (πk/f) j j=1 k=1

Y

Proof. Indeed, |sin(πd/f)| depends only on d ¯ := min(d, f−d) ∈ {1, . . . , φ}, since sin(π(f−d)/f) = sin(πd/f), ¯ Each value of d ¯ is attained by at most two integers modulo f, namely d and is strictly increasing in d. and f − d. Hence the LHS in the proposition is the largest when the multiset d ¯ j takes the smallest possible values each repeated at most twice, that is, {1, 1, 2, 2, . . .} of size m, whose largest element is ⌈m/2⌉. When m is odd we enlarge the product by one factor sin −2 ≥ 1, which gives Eq. (11).

Proposition 3 (Cosine-product). For any m distinct non-zero integers d 1 , . . . , d m modulo f,

Y

Y

|sin(πd j /f)| ≤

j=1

k=1

⌊(m−1)/2⌋

cos 2 (πk/f).

Proof. Writing e := φ − d ¯ ∈ {0, . . . , φ − 1}, we have |sin(πd/f)| = sin(π(φ − e)/f) = cos(πe/f), which is the largest when e is the smallest. Each value e = k ≥ 1 is attained by at most two integers modulo f (those with d ¯ = φ − k), and e = 0 by one (the integer d = φ), so the LHS in the proposition is the largest for the multiset {0, 1, 1, 2, 2, . . .} of size m. For even m the largest element m/2 is unpaired, and bounding its single factor by cos(π(m/2)/f) ≤ 1 gives Eq. (12).

This is consistent with the notations in [KLL + 26].

<!-- page 33 -->

Bound on ρ. By definition ρ(t) = max T ⊆ t Ξ ξ · v 0 T · V T −1 = max T ⊆ t Ξ (ξ · λ T µ →0 ) µ∈T , that is, the maximum of ξ · λ T µ →0 over all µ ∈ T and all sets T ⊆ t Ξ. By Eq. (10), to bound ρ(t) it suffices to bound σ ℓ (ξ · λ T µ →0 ) for any µ,T and ℓ. Fix a size-t set T ⊆ t Ξ and µ ∈ T , and write each ν ∈ T as ζ c ν . Then |σ ℓ (ν)| = 1 and |σ ℓ (µ − ν)| = 2|sin(π(c µ − c ν )/f)|, so

|σ ℓ (ν)| = ξ · 2 −(t−1) |σ ℓ (µ − ν)|

Y

σ ℓ (ξ · λ T µ →0 ) = ξ

ν∈T \{µ}

|sin(π(c µ − c ν )/f)|

Y

ν∈T \{µ}

The t − 1 integers c µ − c ν are distinct and non-zero modulo f, so Eq. (11) with m = t − 1 and Q ⌊t/2⌋ ⌈(t − 1)/2⌉ = ⌊t/2⌋ upper-bounds this by ξ · 2 −(t−1) k=1 sin −2 (πk/f), which is the stated bound.

−1 Bound on γ. By definition γ(t) = max T ∗ ⊆ t−1 Ξ ξ · V Ξ · V {0}∪T ∗

. Fix any T ∗ ⊆ t−1 Ξ, define the

2,2

shorthand S := {0} ∪ T ∗ , and denote M := ξ · V Ξ\T ∗ · V S −1 . We bound separately the rows of ξ · V Ξ · V S −1 indexed by Ξ \ T ∗ , which form M, and those indexed by T ∗ , and then combine the two bounds. For any row α ∈ Ξ \ T ∗ and column µ ∈ S, the (α, µ)-th entry of M is

M α,µ = ξ · λ S→α = ξ µ

α − ν µ − ν

Y

ν∈S\{µ}

Write the evaluation point as α = ζ a and each node ν ∈ T ∗ as ν = ζ c ν . Relative to the bound on ρ(t), the main difference here is that the numerator is α − ν (instead of −ν) which is no longer a unit of R, and will yield a sine factor |σ ℓ (α − ν)| = 2|sin(π(a − c ν )/f)| as shown below. For a canonical embedding σ ℓ , extend σ ℓ entrywise to matrices and vectors of ring elements, so that σ ℓ (M) = σ ℓ (M α,µ ) α,µ ∈ C (f−t+1)×t . Since f is a power of two, Lemma 2 applies to M, and

sX

∥M∥ 2,2 = max ∥σ ℓ (M)∥ 2,2 ≤ max ∥σ ℓ (M)∥ F = max

ℓ

ℓ

|σ ℓ (M α,µ )| ,

ℓ

α,µ

where the inequality upper-bounds ∥·∥ 2,2 by the Frobenius norm ∥·∥ F . In the following we bound |σ ℓ (M α,µ )| for each index α, µ. We recall that M α,µ can be expressed as in Eq. (13). Fix any row α ∈ Ξ \ T ∗ . We Q consider two cases: the column index of M α,µ is µ = 0 or µ ∈ T ∗ . For µ = 0, the denominator ν∈T ∗ (0 − ν) in Eq. (13) is a product of units, so Y Y σ ℓ (ξ · λ S→α ) = ξ |σ ℓ (α − ν)| = ξ · 2 t−1 |sin(π(a − c ν )/f)|.

ν∈T ∗

ν∈T ∗

The t − 1 integers a − c ν are distinct and non-zero modulo f, so Eq. (12) with m = t − 1 upper-bounds this by

Y

σ ℓ (ξ · λ S→α ) ≤ ξ · 2 t−1

k=1

⌊(t−2)/2⌋

cos 2 (πk/f) = ξ · A.

For µ ∈ T ∗ , writing µ = ζ c for some c and factoring out the term with ν = 0,

|σ ℓ (α − 0)| |σ ℓ (µ − 0)|

Y

σ ℓ (ξ · λ S→α ) = ξ · µ

ν∈T ∗ \{µ}

|sin(π(a − c ν )/f)| , |sin(π(c − c ν )/f)|

|σ ℓ (α − ν)| = ξ |σ ℓ (µ − ν)|

Y

ν∈T ∗ \{µ}

where the last line is because both α and µ are units so |σ ℓ (α)| = |σ ℓ (µ)| = 1. Within each of the numerator and the denominator in Eq. (13), the t − 2 integers a − c ν (respectively c − c ν ) are distinct and non-zero modulo f. Hence, we can bound the numerator by Eq. (12) with m = t − 2, and the inverse of the denominator by Eq. (11) with m = t − 2 (using ⌈(t − 2)/2⌉ = ⌊(t − 1)/2⌋), obtaining

⌊(t−3)/2⌋

Y

σ ℓ (ξ · λ S→α ) µ

≤ ξ

cos (πk/f)

k=1

⌊(t−1)/2⌋

= ξ · B. sin 2 (πk/f)

Y

k=1

<!-- page 34 -->

For any α ∈ Ξ \ T ∗ , each row of σ ℓ (M) indexed by α has 1 entry with µ = 0 and t − 1 entries with µ ∈ T ∗ . Using the bounds from the above two cases, X |σ ℓ (M α,µ )| ≤ (ξ · A) 2 + (t − 1)(ξ · B) 2 = ξ 2 · (A 2 + (t − 1)B 2 ).

µ

Summing over the f − t + 1 rows, we get that X |σ ℓ (M α,µ )| ≤ ξ 2 · (f − t + 1)(A 2 + (t − 1)B 2 ).

α,µ

This bound is independent of ℓ, so taking square roots yields an upper-bound for ∥M∥ 2,2 by Eq. (14). It remains to account for the rows of ξ · V Ξ · V S −1 indexed by T ∗ . Each µ ∈ T ∗ indexes a row of V S , so row µ of V T ∗ · V S −1 is the unit row vector selecting the column µ. Hence, up to a permutation of rows, (t−1)×t ξ · V Ξ · V S −1 is M stacked on ξ · P, where P ∈ {0, 1} selects the entries of a vector indexed by T ∗ . t For any x ∈ K , since ξ is an integer and ∥Px∥ 2 ≤ ∥x∥ 2 ,

ξ · V Ξ · V S −1 · x 2 = ∥Mx∥ 2 + ξ 2 · ∥Px∥ 2 ≤ ∥M∥ 2,2 + ξ 2 · ∥x∥ 2

≤ ξ 2 · (f − t + 1)(A 2 + (t − 1)B 2 ) + 1 · ∥x∥ 2 .

Maximising over T ∗ yields the stated bound on γ(t).

−1 Bound on θ. This quantity concerns the same matrix M := ξ · V Ξ\T ∗ · V {0}∪T ∗ as above. In particular, θ(t) = max T ∗ ∥M · v 0 ∥ is the ℓ ∞ -norm of the column with µ = 0. We have

θ(t) ≤ max ∥M α,0 ∥ ≤ max ∥σ(M α,0 )∥ ∞ ≤ ξ · A,

α

α

where the second inequality is by Eq. (10). Maximising over T ∗ gives the bound on θ(t).

Selecting subtractive set elements that are evenly spread among the f monomials reduces the effective ring degree and can lead to better upper bounds. This is observed in [CLW25] and formalised in [KLL + 26, Section 5.1], and is also the choice in our implementation, captured by Lemma 4.

Proof (of Lemma 4). Since f is a power of two and K | f, the element η = ζ f/K is a primitive K-th root of unity with η K/2 = ζ f/2 = −1, so the subring R ′ := Z[η] ⊆ R is isomorphic to the K-th cyclotomic ring Z[Y ]/(Y K/2 + 1), of degree K/2. The set Ξ ′ = η i : 0 ≤ i < K is precisely the set of powers of η, which is a ξ-subtractive set over R ′ for the same slack ξ = 2 ⌈log t⌉ by Lemma 3 (as K is also a power of two). Applying Lemma 8 over R ′ gives the four bounds with conductor K and degree K/2. It remains to note that all the norms involved are unchanged when an element of R ′ is viewed in P K/2−1 P R. Any a = j=0 c j · η j ∈ R ′ equals j c j · ζ (f/K)j , whose exponents (f/K)j < φ are distinct, so the coefficient vector of a in the power basis of R is that of a in R ′ padded with zeros. Hence ∥a∥ p agrees in R and R ′ for every p, and the canonical-embedding magnitudes |σ ℓ (a)| used in the proof of Lemma 8 are those of R ′ , which give the trigonometric factors with argument πk/K. For γ, fix T ∗ ⊆ t−1 Ξ ′ , set S := {0} ∪ T ∗ , and let M := ξ · V Ξ ′ \T ∗ · V S −1 be the matrix with entries in R ′ , having K − t + 1 rows indexed by α ∈ Ξ ′ \ T ∗ and t columns indexed by µ ∈ S. Viewing M as a matrix over R, Eq. (14) bounds its ℓ 2 -induced operator norm by ∥M∥ 2,2 ≤ max ℓ ∥σ ℓ (M)∥ F , where ℓ ranges over the φ embeddings of R. By the previous paragraph, the magnitude |σ ℓ (M α,µ )| viewed in R equals the magnitude in R ′ , whose trigonometric factors carry the argument πk/K. Hence the bounds |σ ℓ (M α,0 )| ≤ ξA and |σ ℓ (M α,µ )| ≤ ξB for µ ∈ T ∗ , established in the proof of Lemma 8, hold with A and B evaluated at conductor K. As each of the K − t + 1 rows carries one entry of the first kind and t − 1 of the second, X ∥σ ℓ (M)∥ F = |σ ℓ (M α,µ )| ≤ ξ 2 · (K − t + 1) A 2 + (t − 1)B 2

α,µ

for every ℓ. Accounting for the t − 1 rows of ξ · V Ξ ′ · V S −1 indexed by T ∗ exactly as in the proof of Lemma 8 gives ξ · V Ξ ′ · V S −1 2,2 ≤ ∥M∥ 2,2 + ξ 2 ≤ ξ 2 · (K − t + 1)(A 2 + (t − 1)B 2 ) + 1 .

Taking square roots and maximising over T ∗ yields the stated bound for γ.

<!-- page 35 -->

D

Proof of Theorem 1 (FHE Leakage Security)

Theorem 1 (Leakage Security). Let K = Q(ζ) be a cyclotomic field of degree φ and expansion factor c ∞ w.r.t. the coefficient ℓ ∞ -norm. Let R = Z[ζ] be its ring of integers. Let L, D ∈ N and FHE be an FHE scheme with (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE . Then, for any PPT adversary A against the IND-CPA-with-(D, L, χ)-Leakage security of FHE that makes at most Q ∈ poly(λ) queries to the oracle LeakO, there exists a PPT adversary B against the IND-CPA security of FHE such that C · Q · φ · L · c ∞ · D · B Adv IND-CPA-wL (λ) ≤ · Q · ε + + Adv IND-CPA FHE FHE,A,(D,L,χ) FHE,B (λ) χ where C = π/2 is a constant. In particular, if χ > λ ω(1) · Q · φ · L · c ∞ · D · B, FHE has (R, n̂, p, q, ξ, B)linear-decryption and is IND-CPA secure, then it is also IND-CPA-with-(D, L, χ)-Leakage secure.

Proof. We consider the following sequence of hybrids.

Hyb b,0 : This is the IND-CPA-with-(D, L, χ)-Leakage security experiment for challenge bit b. To recall, the view of the adversary consists of

public key pk,

public parameters pp,

ciphertexts ctxt

from EncO, ChalO or EvalO, and their underlying plaintexts µ b ,

leakages u · ê + f

from LeakO on ciphertexts ctxt.

Hyb b,1 : We change the experiment as follows. For each query (id, u) to the oracle LeakO, compute j m L ê := ĉ 1 − sk T · ĉ 0 − ξ −2 p q µ mod q. If ∥ê∥ > B, then set L Leak [id] := f ← $ D R,χ and use this as the oracle answer. Otherwise, there is no change, i.e. set L Leak [id] := u · ê + f . L Hyb b,2 : We change the experiment as follows. For each (id, u) to the oracle LeakO, sample f ← $ D R,χ The leakage is computed as L Leak [id] := f .

For i = 0, 1, 2, let Adv i (A) denote the advantage of A in experiments (Hyb 0,i , Hyb 1,i ), that is

Adv i (A) := Pr Hyb 0,i,A (1 λ ) = 1 − Pr Hyb 1,i,A (1 λ ) = 1

By definition of Hyb b,0 , one has

Adv IND-CPA-wL FHE,A,(D,L,χ) (λ) = Adv 0 (A)

– By Lemma 9, if FHE has (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE , we have

Adv 0 (A) ≤ Adv 1 (A) + 2 · Q · ε FHE .

– By Lemma 10, we have

C ·

Adv 1 (A) ≤ Adv 2 (A) + 2 ·

Q · φ · L · c ∞ · D · B χ

– By Lemma 11, for every PPT A, there exists a PPT B such that

Adv 2 (A) ≤ Adv IND-CPA FHE,B (λ).

Putting everything together, one obtains C · Q · φ · L · c ∞ · D · B + Adv IND-CPA Adv IND-CPA-wL (λ) ≤ · Q · ε + FHE FHE,A,(D,L,χ) FHE,B (λ), χ

as claimed.

Lemma 9. Adopt the notations in Theorem 1. We have Adv 0 (A) ≤ Adv 1 (A) + 2 · Q · ε FHE .

<!-- page 36 -->

Proof. By the definition of (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE , the norm of each ê computed by the LeakO is bounded by B except with probability ε FHE . By a hybrid argument over the Q queries made by A to LeakO, it follows that, for each b ∈ {0, 1}, the statistical distance between Hyb b,0 and Hyb b,1 is at most Q · ε FHE . Thus, by the triangle inequality,

Adv 0 (A) = Pr Hyb 0,0,A (1 λ ) = 1 − Pr Hyb 1,0,A (1 λ ) = 1 Pr Hyb 0,0,A (1 λ ) = 1 − Pr Hyb 0,1,A (1 λ ) = 1 = + Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 + Pr Hyb 1,1,A (1 λ ) = 1 − Pr Hyb 1,0,A (1 λ ) = 1 ≤ Pr Hyb 0,0,A (1 λ ) = 1 − Pr Hyb 0,1,A (1 λ ) = 1 + Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 + Pr Hyb 1,1,A (1 λ ) = 1 − Pr Hyb 1,0,A (1 λ ) = 1

≤ Q · ε FHE + Adv 1 (A) + Q · ε FHE

= Adv 1 (A) + 2 · Q · ε FHE .

∞ ·D·B Lemma 10. Adopt the notations in Theorem 1. We have Adv 1 (A) ≤ Adv 2 (A) + 2 · C· Q·φ·L·c χ

Proof. The only difference between Hyb b,1 and Hyb b,2 is that whenever ∥ê∥ ≤ B, the answer from LeakO is changed from u · ê + f to f . For each such query u, it holds that ∥u · ê∥ 2 ≤ φ · L · ∥u · ê∥ ∞ ≤ φ · L · c ∞ · ∥u∥ ∞ · ∥ê∥ ∞ ≤ φ · L · c ∞ · D · B,

where we use that ∥u∥ ∞ ≤ D by the norm-check in leakO. For b ∈ {0, 1}, we invoke Lemma 7 with n = L and norm bound B ′ := φ · L · c ∞ · D · B. The (unbounded) reduction is trivial, so we only give a sketch. It simulates Hyb b,1 and Hyb b,2 as follows: on each leakO query it computes ê using sk, queries its oracle O b on c := u · ê if ∥ê∥ ≤ B and c := 0 otherwise (so ∥c∥ 2 ≤ B ′ in both cases), and answers the query with the oracle output. The remaining parts are identical in both hybrids, which are computed by the reduction itself. It is direct to see that it perfectly simulates either hybrid depending on the challenge bit in the experiment in Lemma 7. In particular, when ∥ê∥ > B, the reduction answers f as defined in Hyb b,1 . Since there are at most Q queries, Lemma 7 gives

Pr Hyb b,1,A (1 λ ) = 1 − Pr Hyb b,2,A (1 λ ) = 1 ≤ (C · Q · φ · L · c ∞ · D · B)/χ

for both b ∈ {0, 1}. Then by the triangle inequality, Adv 1 (A) = Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 0,2,A (1 λ ) = 1 = + Pr Hyb 0,2,A (1 λ ) = 1 − Pr Hyb 1,2,A (1 λ ) = 1 + Pr Hyb 1,2,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 ≤ Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 0,2,A (1 λ ) = 1 + Pr Hyb 0,2,A (1 λ ) = 1 − Pr Hyb 1,2,A (1 λ ) = 1 + Pr Hyb 1,2,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 ≤ (C · Q · φ · L · c ∞ · D · B)/χ + Adv 2 (A) + (C · Q · φ · L · c ∞ · D · B)/χ = Adv 2 (A) + 2 · (C · Q · φ · L · c ∞ · D · B)/χ.

Lemma 11. Adopt the notations in Theorem 1. We have Adv 2 (A) ≤ Adv IND-CPA FHE,B (λ).

Proof. Consider a PPT algorithm A distinguishing Hyb 0,2 and Hyb 1,2 with advantage Adv 2 (A). We construct a reduction B against the IND-CPA security of FHE, which proceeds as follows:

– It receives (pp, pk) from the IND-CPA challenger and sends them to A.

<!-- page 37 -->

– It internally maintains lists L Query , L leak , initially empty. It answers A’s queries to EncO, EvalO, LeakO by honestly performing the oracle computations (which are identical in Hyb 0,2 and Hyb 1,2 ) itself, and forwards the ChalO queries to its own ChalO oracle available from the IND-CPA challenger. In more detail, it answers the oracle queries as follows: • EncO(id, µ): If L Query [id] = ∅, it computes ctxt ← Enc(pk, µ) and sets L Query [id] := (ctxt, µ, µ). It returns L Query [id] to A. • ChalO(id, µ 0 , µ 1 ): If L Query [id] = ∅, it queries its own ChalO on (id, µ 0 , µ 1 ) to receive ctxt, and sets L Query [id] := (ctxt, µ 0 , µ 1 ). It returns L Query [id] to A. • EvalO(id, f, (id i ) i∈I ): If L Query [id] = ∅, it asserts L Query [id i ] ̸ = ∅ and parses (ctxt i , µ 0,i , µ 1,i ) ← L Query [id i ] for each i ∈ I, then computes ctxt ′ ← Eval(pk, f, (ctxt i ) i∈I ), and sets L Query [id] := (ctxt ′ , f ((µ 0,i ) i∈I ), f ((µ 1,i ) i∈I )). It returns L Query [id] to A. • LeakO(id, u ∈ R L ): If L leak [id] = ∅, it asserts ∥u∥ ≤ D and L Query [id] ̸ = ∅, parses (ctxt, µ 0 , µ 1 ) ← L , and sets L leak [id] := f . It returns L leak [id] to A. L Query [id] and asserts µ 0 = µ 1 , samples f ← $ D R,χ ′ ′ – Eventually, it receives b from A and returns b .

If B is interacting with the IND-CPA experiment 0, then queries to ChalO(id, µ 0 , µ 1 ) return ctxt ← Enc(pk, µ 0 ). Therefore, the view of A is identical to Hyb 0,2 . If B is interacting with the IND-CPA experiment 1, then queries to ChalO(id, µ 0 , µ 1 ) return ctxt ← Enc(pk, µ 1 ). Therefore, the view of A is identical to Hyb 1,2 . It follows that B perfectly simulates the view of either Hyb 0,2 or Hyb 1,2 to A, if it is interacting either with the IND-CPA experiment 0 or 1. Therefore Adv 2 (A) ≤ Adv IND-CPA FHE,B (λ) as claimed.

E

Proof of Theorem 2 (Tulva Correctness)

Theorem 2 (Correctness). If ξ ∈ Z, FHE has (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE and |q mod p| β z−1 ≥ + ξ · B + c ∞ · λ · m · ξ · χ̄ · + t · ρ · ( λ · χ + 2 ) . 2p

Then, thFHE in Fig. 3 has correctness error ε ≤ ε FHE +φ·(m+t)·2 −λ . In particular, if min{log(1/ε FHE ), λ− log φ − log(m + t)} ≥ ω(log λ), then thFHE is correct.

Proof. First observe that, for any thFHE ciphertext (ctxt FHE , t), the third and lines of ParDec fourth ĉ and Combine in Fig. 3 are identical, i.e. they compute the same x = G −1 , where (ĉ 0 , ĉ 1 ) ← β,q t Preproc(ctxt FHE ). The algorithm ParDec, on input (pk, sk k , ctxt), computes the following quantity pd k = s T k · c 0 + e k 2 z = s T k · A · x + e k + d k mod q,

where d k := ⌊y⌉ 2 z − y ∈ R is the rounding error, for y the representative of s T k · c 0 + e k mod q with coefficients in [−q/2, q/2). Writing y i for the coefficients of y, each coefficient of d k is 2 z · (⌊y i /2 z ⌉ − y i /2 z ), so ∥d k ∥ ≤ 2 z−1 . Below, for any recovery set T , denote by e T := (e k + d k ) k∈T the vertical concatenation of the errors e k + d k . The algorithm Combine, on input (pk, T, (pd k ) k∈T , ctxt), computes pd and c 1 which are

pd = ξ · v 0 T · V T −1 · (pd k ) k∈T mod q

= ξ · v 0 T · V T −1 · s T k · A · x + e k + d k k∈T mod q

// by Eq. (15)

= ξ · v 0 T · V T −1 · V T · R · A · x + ξ · v 0 T · V T −1 · e T mod q // (s k ) k∈T = ξ · V T · R mod q, (e k + d k ) k∈T = e T = ξ 2 · v 0 T · R · A · x + ξ · v 0 T · V T −1 · e T mod q = ξ 2 · r T · A · x + ξ · v 0 T · V T −1 · e T mod q // r T = v 0 T · R mod q

and

c 1 = ξ 2 · b T · x mod q

<!-- page 38 -->

= ξ 2 · (r T · A + e T + z T ) · x mod q

// b T = r T A + e T + z T mod q

= ξ 2 · (r T · A + e T + (ŝ T , 0 T h ) · G β,q ) · x mod q

// z T = ((ŝ T , 0 T h ) · G β,q mod q)

· ((ŝ , 0 T h ) · G β,q · x) mod q

= ξ · r · A · x + ξ · e · x + ξ

ĉ 0 mod q t

(ŝ , 0 T h ) · G β,q · G −1 β,q

= ξ · r · A · x + ξ · e · x + ξ ·

= ξ 2 · r T · A · x + ξ 2 · e T · x + ξ 2 · ŝ T · ĉ 0 mod q.

Putting Eqs. (16) and (17) together, we have

ĉ 0 t

// x = G −1 β,q

c 1 − pd = ξ 2 · r T · A · x + ξ 2 · e T · x + ξ 2 · ŝ T · ĉ 0 − ξ 2 · r T · A · x + ξ · v 0 T · V T −1 · e T mod q

= ξ 2 · ŝ T · ĉ 0 + ξ 2 · e T · x − ξ · v 0 T · V T −1 · e T mod q

= ξ 2 · ŝ T · ĉ 0 + f mod q,

where in the last line we use the shorthand

f := ξ 2 · e T · x − ξ · v 0 T · V T −1 · e T .

Using Eq. (18), we obtain

µ̂ = ξ 2 · ĉ 1 − (c 1 − pd) mod q

= ξ 2 · ĉ 1 − ξ 2 · ŝ T · ĉ 0 − f mod q · µ + ê − f mod q = ξ 2 · ξ −2 · = · µ + ξ 2 · ê − f mod q = · µ + ξ 2 · ê − f + q · h // for some h ∈ R

where the third equality follows from the (R, n̂, p, q, ξ, B)-linear-decryption property of FHE (Definition 4), which guarantees that ĉ 1 − ŝ T · ĉ 0 mod q = ξ −2 · ⌊q/p⌉ · µ + ê

except with probability at most ε FHE . Finally, the algorithm Combine returns ′ µ = · µ̂ mod p = · · µ + ξ · ê − f + q · h mod p // By Eq. (19) p 2 = · − · µ + · ξ · ê − · f + p · h mod p // = + p 2 = µ − · · µ + · ξ · ê − · f + p · h mod p = µ + − · · µ + · ξ 2 · ê − · f + p · h mod p = µ + − · · µ + · ξ 2 · ê − · f mod p.

Thus, the plaintext µ is correctly recovered as long as − · · µ + · ξ 2 · ê − · f = 0 ⇐⇒

⇐⇒

− · · µ + · ξ 2 · ê − · f ≤ − · µ + ξ 2 · ê − f ≤ , 2p

<!-- page 39 -->

which is implied by

· µ + ξ 2 · ê + ∥f ∥ ≤ 2p

In the rest, we show that Eq. (5) in the theorem statement implies Eq. (20) in the above except with probability at most ε FHE + φ · (m + t) · 2 −λ , which completes the proof. We have |q mod p| = · µ ≤ · ,

ξ 2 · ê = ξ 2 · ∥ê∥

// ξ ∈ Z

≤ ξ · B,

// By (R, n̂, p, q, ξ, B)-linear-decryption with error ε FHE

∥f ∥ = ξ 2 · e T · x − ξ · v 0 T · V T −1 · e T

≤ ξ 2 · e T · x + ξ · v 0 T · V T −1 · e T ≤ c ∞ · m · ξ 2 · ∥e∥ · ∥x∥

+ c ∞ · t · ξ · v 0 T · V T −1

// ξ ∈ Z, e T · x ≤ c ∞ · m · ∥e∥ · ∥x∥ · ∥e T ∥ // ξ · v 0 T · V T −1 · e T ≤ c ∞ · t · ξ · v 0 T · V T −1 · ∥e T ∥

β β // ∥e∥ ≤ χ̄ · λ by Eq. (8), ∥x∥ ≤ , ξ ∈ Z + c ∞ · t · ρ · (χ · λ + 2 z−1 ) // ∥e T ∥ ≤ χ · λ + 2 z−1 by Eq. (8), ∥d k ∥ ≤ 2 z−1 β z−1 = c ∞ · λ · m · ξ · χ̄ · + t · ρ · ( λ · χ + 2 ) ,

c ∞ · m · ξ 2 · χ̄ ·

λ ·

≤

where we recall that ρ in the above is a quality measurement of Ξ (Definition 1). Putting the above bounds together with Eq. (5) yields Eq. (20) as claimed. Indeed, if min{log(1/ε FHE ), λ − log φ − log(m + t)} ≥ ω(log λ), then the above bounds hold except with probability negligible in λ.

F

Proofs for Theorem 3 (Tulva Security)

This section provides the proof of Theorem 3 and is structured as follows. In Appendix F.1, we recall the theorem statement and state its proof which relies on several bridging lemmas. Then, in Appendix F.2, we state and prove these bridging lemmas Lemmas 12 to 15. One of the bridging lemmas (Lemma 12) will further rely on a separate utility lemma (Lemma 21), the latter being a generalisation of a lemma in [CLW25] and is to be provided in Appendix G.

F.1

Theorem Statement and Proof

Theorem 3 (Security). Let FHE be an FHE scheme with (R, n̂, p, q, ξ, B)-linear-decryption and Ξ be a ξ-subtractive set of cardinality K with quality measurements (ρ, γ, θ) (Definition 1). Let ϵ ∈ (0, p 1/2], Q ∈ poly(λ), q, ξ be coprime, χ ∗ 1 √ ≥ 2 · η ϵ (R t ) be such that there exists χ̂ > √ 0 with γ ≤ χ · (2η ϵ (R t ) 2 + (χ ∗ 1 ) 2 ) −1 − χ̂ −2 , and χ ∗ 2 ≥ 2 · η ϵ (R m ) be such that γ · φm · β/2 ≥ 1 and 2QK · φm · ∗ 2 −1 − χ̄ −2 , where c ⊗ := 1 if f is a power of two and c ⊗ := m 2 c 2 · c ⊗ t t · γ · β/2 ≤ χ · n (2η ϵ (R ) + (χ 2 ) ) t t o

otherwise. Let D t := t̃ : t ← $ R hq , t̃ := G −1 β,q (t) . Define the parameter sets:

– thFHE: par = (FHE, R, n, m, h, q, β, χ̄, χ, z, Ξ), – LWE: par 1 := (R, h log β q , poly(λ), q, χ ∗ 1 , D t ), – LWE: par 2 := (R, n, m, q, χ ∗ 2 ), – FHE: par 3 := (θ, K, χ).

<!-- page 40 -->

Consider the (t, K)-threshold FHE scheme thFHE par in Fig. 3. For all PPT A that requests partial decryptions on at most Q ciphertexts (i.e. in the Q-bounded IND-CPA experiment of Definition 7), there exist PPT B 1 , B 2 , B 3 such that Adv IND-CPA thFHE,A (λ) ≤ ε where

12·Q·ϵ LWE ε := 2·t· Adv LWE +Adv IND-CPA-wL par 1 ,B 1 (λ)+Adv par 2 ,B 2 (λ) + FHE,par 3 ,B 3 (λ) 1−ϵ +4·t· 2QK + ·ϵ. 1−ϵ

Proof. Let thFHE ′ denote the scheme in Fig. 3 with the step pd k ← ⌊pd k ⌉ 2 z of ParDec removed, i.e. the scheme without bit dropping. Since ⌊·⌉ 2 z is a deterministic public function applied only to the outputs of ParDec, any adversary A against thFHE yields an adversary A ′ against thFHE ′ that runs A, forwards all its oracle queries, and applies ⌊·⌉ 2 z to every partial decryption before passing it to A. The adversary A ′ is PPT, requests partial decryptions on the same ciphertexts as A, and perfectly simulates Exp b thFHE,A for IND-CPA IND-CPA both b ∈ {0, 1}, so Adv IND-CPA thFHE,A (λ) = Adv thFHE ′ ,A ′ (λ). It therefore suffices to show Adv thFHE ′ ,A (λ) ≤ ε for every PPT A against thFHE ′ that requests partial decryptions on at most Q ciphertexts, with ε as in Theorem 3. In the rest of this proof, A denotes such an adversary and partial decryptions are those in Exp b thFHE ′ ,A . Throughout this proof (and in Lemmas 12 to 15 and 21 which support this proof), we adopt the following notations:

– For any subset C ⊆ [K], denote by V C ∈ R |C|×t the submatrix of V whose rows are indexed by C. |C|×n Similarly, S C ∈ R q is the submatrix of S = V · R whose rows are indexed by C, i.e., S C = V C · R. – For any set C ⊂ [K] of corrupt parties with |C| < t, we define: • H := [K] \ C the set of honest (i.e. non-corrupt) parties, and • T C ∈ R t×t a matrix such that it holds ξ −1 · T C · V C ∗ = I t for some size-t set C ∗ satisfying ({0} ∪ C) ⊆ C ∗ ⊆ [0, K]. (T C is not unique given C and we may fix an arbitrary one.)

We consider the following sequence of hybrids.

Hyb b,0 : This is the thFHE ′ security experiment for challenge bit b. To recall, the view of the adversary consists of pk = (pk FHE , A, b) where

b T := r T A + e T + z T mod q,

z T = (ŝ T , 0 T h ) · G β,q mod q,

corrupt user keys (s k ) k∈C , ciphertexts ctxt = (ctxt FHE , t) from EncO, ChalO or EvalO, partial decrypĉ tions pd k = s T k Ax + e k mod q where x := G −1 0 and the vector ĉ 0 is obtained from running t (ĉ 0 , ĉ 1 ) ← FHE.Preproc(ctxt FHE ), which is possible because of the (R, n̂, p, q, ξ, B)-linear-decryption property of FHE. (We recall that Preproc is a public operation, thus the adversary can also compute the above and observe (ĉ 0 , ĉ 1 ).) Hyb b,1 : This experiment is identical to Hyb b,0 except for the following change. For each ctxt, sample a

t−|C|−1

K and an error e x ← $ D R,χ , its partial decryptions are computed as   (b − e − z) T x V H · T C   + e x mod q w x (pd k ) k∈[K] = ξI C S C Ax   (b − e − z) T x V H · (u 0 , U 1 , U 2 )   + e x mod q w x =: ξI C S C Ax ĉ where we recall x := G −1 0 and z T = (ŝ T , 0 T h ) · G β,q mod q. t In the last line, we define the shorthand

random vector w x ← $ R q

## T C = (u 0 , U 1 , U 2 ) ∈ R t×1 × R t×t−|C|−1 × R t×|C| ,

for the block columns of T C , which will be used in the subsequent hybrids.

<!-- page 41 -->

Hyb b,2 : This experiment is identical to Hyb b,1 except for the following change. For each ParDecO query (id, k), if L Query [id] = (ctxt, µ 0 , µ 1 ) is such that µ 0 ̸ = µ 1 and k ∈ / C, we change the partial decryption answer for k to a uniformly random R q element. For corrupt parties k ∈ C, the answer is kept as in Hyb b,1 . Hyb b,3 : This experiment is identical to Hyb b,2 except for the following change. For each ParDecO query id, if L Query [id] = (ctxt, µ 0 , µ 1 ) is such that µ 0 = µ 1 , we express its partial decryptions as h j m i V H u 0 (pd k ) k∈[K] = (b − e) T x − ĉ 1 − p q · ξ −2 · µ + ê V H (U 1 , U 2 ) w x + + e x mod q, ξI C S C Ax

where µ := µ 0 = µ 1 , and ê ∈ R is defined as

ê := ĉ 1 − ŝ · ĉ 0 − ξ

µ mod q

−2

ĉ 0 , and u 0 , U 1 , U 2 are defined in Hyb b,1 . t

We recall x := G −1

For i ∈ [0, 3], let Adv i (A) denote the advantage of A in experiments (Hyb 0,i , Hyb 1,i ), that is Adv i (A) := Pr Hyb 0,i,A (1 λ ) = 1 − Pr Hyb 1,i,A (1 λ ) = 1 . By definition of Hyb b,0 , one has Adv IND-CPA thFHE ′ ,A (λ) = Adv 0 (A). By Lemma 12, under the condition stated in Theorem 3, for any PPT A, there exist PPT B 1 , B 2 such that ! 6 · Q · ϵ 6 · ϵ LWE LWE Adv 0 (A) ≤ Adv 1 (A) + 2 · t · Adv par 1 ,B 1 (λ) + Adv par 2 ,B 2 (λ) + + 4 · QK · ϵ + t(1 − ϵ) 1 − ϵ

By Lemma 13, Adv 1 (A) = Adv 2 (A). By Lemma 14, Adv 2 (A) = Adv 3 (A). By Lemma 15, ∀ PPT A, ∃ PPT B 3 such that Adv 3 (A) ≤ Adv IND-CPA-wL FHE,B 3 ,par 3 (λ). Putting everything together, one obtains the claimed result. Lemmas 12 to 15 and their proofs are provided in Appendix F.2.

F.2

Proofs of Lemmas 12 to 15

Lemma 12. Adopt the notations in Theorem 3. Suppose q and ξ are coprime, 0 < ϵ ≤ 1/2, and the noise parameters χ ∗ 1 , χ ∗ 2 satisfy both of the following: −2 – χ ∗ 1 ≥ √ 2 · η ϵ (R t ) is such that there exists χ̂ > 0 satisfying γ ≤ χ · (2η ϵ (R t ) 2 + (χ ∗ 1 ) 2 ) −1 √ − χ̂ ; ⊗ ⊗ ∗ – χ 2 ≥ 2 · η ϵ (R ), γ · φm · β/2 ≥ 1, and, with c t := 1 if f is a power of two and c t := t otherwise, 2QK · φm · c 2 · c ⊗ (2η ϵ (R m ) 2 + (χ ∗ 2 ) 2 ) −1 − χ̄ −2 . t · γ · β/2 ≤ χ ·

Then, for any PPT A, there exist PPT B 1 , B 2 such that

(λ) Adv LWE (λ) + Adv LWE (R,n,m,q,χ ∗ (R,h ⌈ log q ⌉ ,poly(λ),q,χ ∗ ,D t ),B 1 2 ),B 2

Adv 0 (A) ≤ Adv 1 (A) + 2 · t ·

β

!

6 · Q · ϵ 6 · ϵ + 4 · QK · ϵ + t(1 − ϵ) 1 − ϵ

+

Proof. Let par = ((R, n, m, q, Q, χ̄, χ, D A , D t , β/2), (t, K, Ξ)), where n o D A := U(R n×m ), and D t := t̃ : t ← $ R hq , t̃ := G −1 β,q (t) .

We will show that for any PPT A, there exists a PPT B such that

Adv 0 (A) ≤ Adv 1 (A) + 2 · Adv RealIdeal (λ), par,B

where Adv RealIdeal (λ) is defined in Lemma 21. The claimed result will follow by plugging the upper-bound par,B RealIdeal for Adv par,B (λ) from Lemma 21, and by recalling that the parameter D A is omitted from the parameters of the LWE instance when D A is the uniform distribution (see Definition 2). Suppose A is a PPT distinguisher for (Hyb b,0 , Hyb b,1 ). We construct a reduction B distinguishing Real par,B and Ideal par,B . The reduction B works as follows:

<!-- page 42 -->

– It receives A ∈ R n×m from the challenger. It samples pp FHE ← FHE.Setup(1 λ ), sets pp := pp FHE , and passes pp to A, receiving from which C ⊂ <t [K]. – It samples (pk FHE , sk FHE ) ← FHE.KGen(p FHE ), parses sk FHE = ŝ ∈ R n̂ q , and sets z T := (ŝ T , 0 T h ) · G β,q mod q ∈ R m q . It forwards (C, z) to the challenger, receiving from which (b, S C = (sk k ) k∈C ). – It sets pk := (pk FHE , A, b) and (sk k ) k∈C := (s k ) k∈C , and sends (pk, (sk k ) k∈C ) to A. – It internally maintains lists L Query , L Share , L Party , initially empty. Define two subroutines Pre and Tag below, which will be used by the reduction to answer oracle queries, and where Tag invokes the experiment’s oracle GenO:

Pre(ctxt FHE )

(ĉ 0 , ĉ 1 ) ← Preproc(ctxt FHE )

return G −1 β,q (ĉ 0 )

Tag(id, ctxt FHE )

c̃ := Pre(ctxt FHE )

x ← GenO(id, c̃) c̃ parse ← x t̃

t := G β,q · t̃ mod q

return ctxt := (ctxt FHE , t)

The reduction answers the oracle queries of A as follows: • EncO(id, µ): If L Query [id] = ∅, it computes

ctxt FHE ← FHE.Enc(pk FHE , µ)

ctxt ← Tag(id, ctxt FHE ),

and

It returns L Query [id] to A. • ChalO(id, µ 0 , µ 1 ): If L Query [id] = ∅, it computes

ctxt FHE ← FHE.Enc(pk FHE , µ b )

and sets L Query [id] := (ctxt, µ, µ).

ctxt ← Tag(id, ctxt FHE ),

and

and sets L Query [id] := (ctxt, µ 0 , µ 1 ).

It returns L Query [id] to A. • EvalO(id, f, (id i ) i∈I ): If L Query [id] = ∅, then: ∗ For each i ∈ I, it returns ⊥ if L Query [id i ] = ∅, and otherwise parses (ctxt i , µ 0,i , µ 1,i ) ← L Query [id i ] and (ctxt FHE,i , t i ) ← ctxt i . ∗ It computes

ctxt ′ FHE ← Eval(pk, f, (ctxt FHE,i ) i∈I )

ctxt ← Tag(id, ctxt ′ FHE ), and sets L Query [id] := ctxt, f ((µ 0,i ) i∈I ), f ((µ 1,i ) i∈I ) .

and

It returns L Query [id] to A. • ParDecO(id, k): If L Query [id] = ∅, it returns ⊥. Otherwise: ∗ It adds {k} to L Party [id], and parses (ctxt, µ 0 , µ 1 ) ← L Query [id] and (ctxt FHE , t) ← ctxt. ∗ If µ 0 ̸ = µ 1 and |L Party [id] ∪ C| ≥ t, it returns ⊥. ∗ Otherwise, if L Share [id, k] = ∅, it queries

d k ← ShareO(id, k)

It returns L Share [id, k] to A. – Eventually receive b ′ from A, return b ′ .

and sets L Share [id, k] := d k .

Below, we show that B perfectly simulates the view of either Hyb b,0 or Hyb b,1 to A, if it is interacting either with the Real par,B or the Ideal par,B experiment. If B is interacting with the Real par,B experiment, then

b T = r T A + e T + z T mod q c̃ ĉ 0 and t̃ ← $ D t x = for c̃ = G −1 β,q t̃

d T = (pd k ) k∈[K] = ξ · VRAx + e x mod q

<!-- page 43 -->

n o K for e x ← $ D R,χ . Using that D t = t̃ : t ← $ R hq , t̃ := G −1 β,q (t) and that (s k ) k∈[K] = ξ · VR mod q, one obtains that (pd k ) k∈[K] = ξ · V · R · | A {z · x } + e x = s T k · c 0 + e k k∈[K] |{z} | {z }

c 0

(s k ) k∈[K]

(e k ) k∈[K]

Therefore, the view of A is identical to Hyb b,0 . If B is interacting with the Ideal par,B experiment, then

b ← $ R m c̃ x = t̃

for c̃ = G −1 β,q ĉ 0

and t̃ ← $ D t   (b − e − z) T x V · H C   + e x mod q w x d T = (pd k ) k∈[K] = ξI C S C Ax n o Using as above that D t = t̃ : t ← $ R hq , t̃ := G −1 β,q (t) , we conclude that the view of A is identical to Hyb b,1 . By the triangle inequality, it follows that Adv 0 (A) = Pr Hyb 0,0,A (1 λ ) = 1 − Pr Hyb 1,0,A (1 λ ) = 1 Pr Hyb 0,0,A (1 λ ) = 1 − Pr Hyb 0,1,A (1 λ ) = 1 = + Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 + Pr Hyb 1,1,A (1 λ ) = 1 − Pr Hyb 1,0,A (1 λ ) = 1 ≤ Pr Hyb 0,0,A (1 λ ) = 1 − Pr Hyb 0,1,A (1 λ ) = 1 + Pr Hyb 0,1,A (1 λ ) = 1 − Pr Hyb 1,1,A (1 λ ) = 1 + Pr Hyb 1,1,A (1 λ ) = 1 − Pr Hyb 1,0,A (1 λ ) = 1

≤ Adv RealIdeal (λ) + Adv 1 (A) + Adv RealIdeal (λ) par,B par,B

= Adv 1 (A) + 2 · Adv RealIdeal (λ), par,B

as wanted. As mentioned at the beginning of the proof, plugging the upper-bound for Adv RealIdeal par,A (λ) from Lemma 21 yields the claimed results.

Lemma 13. Adopt the notations in Theorem 3. We have Adv 1 (A) = Adv 2 (A).

Proof. Fix any id such that L Query [id] = (ctxt, µ 0 , µ 1 ) and µ 0 ̸ = µ 1 . Denote by H̄ ⊆ H = [K] \ C the set of honest parties for which an adversary has queried its partial decryptions. By design of the security experiment, it must hold that |H̄| < t − |C|. Now recall that, in Hyb b,1 , the set of partial decryptions for the parties H̄ is defined by Eq. (21), which is   (b − e − z) x  + e x mod q w x (pd k ) k∈H̄ = V H̄ · (u 0 , U 1 , U 2 )  S C Ax = V H̄ · u 0 · (b − e − z) T x + V H̄ · U 1 · w x + V H̄ · U 2 · S C Ax + e x mod q, −1 ĉ 0 where we recall w x is a random vector sampled by the experiment and x = G . By [CLW25, t

|H̄|

Lemma 9, Eprint], the columns of V H̄ · U 1 generate R q . Therefore, since w x is uniformly random, so is V H̄ · U 1 · w x mod q. That is,

## V H̄ · U 1 · w x mod q ∼ U(R | q H̄| ),

and therefore we get

## V H̄ · u 0 · (b − e − z) T x + U (R | q H̄| ) + V H̄ · U 2 · S C Ax + e x mod q

(pd k ) k∈H̄ ≡

<!-- page 44 -->

≡ U (R | q H̄| ).

In other words, the set of partial decryptions (pd k ) k∈H̄ for id is uniformly random, identical to that in Hyb b,2 . Therefore, Adv 1 (A) = Adv 2 (A).

Lemma 14. Adopt the notations in Theorem 3. We have Adv 2 (A) = Adv 3 (A).

Proof. Fix any id such that L Query [id] = (ctxt, µ 0 , µ 1 ), (ĉ 0 , ĉ 1 ) ← Preproc(ctxt FHE ), and µ 0 = µ 1 . Denote µ := µ 0 = µ 1 and let ê := ĉ 1 − ŝ T · ĉ 0 − ξ −2 µ mod q

Notice that

z x mod q = ((ŝ , 0 T h ) · G β,q ) · G −1 β,q

ĉ 0 mod q t

(ŝ T , 0 T h ) ·

=

ĉ 0 mod q t

= (ŝ T · ĉ 0 ) mod q · ξ −2 · µ + ê + q · h ′′ mod q = ĉ 1 − · ξ −2 · µ + ê mod q. = ĉ 1 −

Hence,

// By Eq. (25)

  (b − e) T x − z T x V H · (u 0 , U 1 , U 2 )   + e x mod q w x ξI C S C Ax  j m  (b − e) T x − ĉ 1 − q · ξ −2 · µ + ê V H · (u 0 , U 1 , U 2 )   =  + e x mod q w x ξI C  S C Ax j m i V (U , U ) w V H u 0 h H x −2 (b − e) x − ĉ 1 − p · ξ · µ + ê + + e x mod q, = ξI C S C Ax

that is, the partial decryptions for id in Hyb b,2 and Hyb b,3 are identical. Therefore, Adv 2 (A) = Adv 3 (A).

Lemma 15. Adopt the notations in Theorem 3. Then, for any PPT A there exists PPT B 3 such that Adv 3 (A) ≤ Adv IND-CPA-wL FHE,B 3 ,(θ,K,χ) (λ).

Proof. Suppose A is a PPT distinguisher for (Hyb 0,3 , Hyb 1,3 ). We construct a reduction B 3 against the IND-CPA under leakage security of FHE, which proceeds as follows:

– It receives (pp FHE , pk FHE ) from the IND-CPA-under-leakage challenger, parses pp = pp FHE , and passes pp to A, receiving from which C ⊂ <t [K]. – It samples A ← $ R n×m , R ← $ R t×n , b ← $ R m q , and e ← $ D R,χ̄ , sets (sk k ) k∈[K] := ξ · V · R mod q and pk := (pk FHE , A, b), and sends (pk, (sk k ) k∈C ) to A. – It internally maintains lists L Query , L Share , L Party , initially empty. It answers A’s queries to EncO, ChalO, EvalO by forwarding to its own EncO, ChalO, EvalO from the IND-CPA-under-leakage challenger, and appending a freshly sampled t itself. In more detail, it answers the oracle queries as follows: • EncO(id, µ): If L Query [id] = ∅, then

query (ctxt FHE , µ, µ) ← EncO(id, µ),

sample t ← $ R hq ,

set ctxt := (ctxt FHE , t)

and L Query [id] := (ctxt, µ, µ). It returns L Query [id] to A.

<!-- page 45 -->

• ChalO(id, µ 0 , µ 1 ): If L Query [id] = ∅, then

query (ctxt FHE , µ 0 , µ 1 ) ← ChalO(id, µ 0 , µ 1 ),

sample t ← $ R hq ,

set ctxt := (ctxt FHE , t)

and L Query [id] := (ctxt, µ 0 , µ 1 ). It returns L Query [id] to A. • EvalO(id, f, (id i ) i∈I ): If L Query [id] = ∅, it parses (ctxt i , µ 0,i , µ 1,i ) ← L Query [id i ] for each i ∈ I, then

query (ctxt ′ FHE , µ ′ 0 , µ ′ 1 ) ← EvalO(id, f, (id i ) i∈I ),

set ctxt ′ := (ctxt ′ FHE , t)

sample t ← $ R hq ,

and L Query [id] := (ctxt ′ , µ ′ 0 , µ ′ 1 ). It returns L Query [id] to A. – To answer A’s oracle queries to ParDecO(id, k): If L Query [id] = ∅, the reduction returns ⊥. Otherwise it adds {k} to L Party [id] and parses (ctxt, µ 0 , µ 1 ) ← L Query [id]. If µ 0 ̸ = µ 1 and |L Party [id] ∪ C| ≥ t, it returns ⊥. Otherwise, if L Share [id] = ∅, it computes (pd k ) k∈[K] by distinguishing two cases: • If µ 0 = µ 1 : It simulates (pd k ) k∈[K] using the leakO answer from the challenger. Specifically, V H · u 0 set u := , query leak ← LeakO(id, u),

where u 0 was defined in Eq. (22). Then, it parses (ctxt FHE , t) ← ctxt, computes (ĉ 0 , ĉ 1 ) ← ĉ 0 t−|C|−1 −1 Preproc(ctxt FHE ), samples w x ← $ R q , sets µ := µ 0 = µ 1 and x := G , and it sets t i j m V H (U 1 , U 2 ) w x V H u 0 h −2 mod q. (pd k ) k∈[K] := (b − e) x − ĉ 1 − p · ξ · µ + leak + ξI C S C Ax ĉ 0 −1 • If µ 0 ̸ = µ 1 : It parses (ctxt FHE , t) ← ctxt, computes (ĉ 0 , ĉ 1 ) ← Preproc(ctxt FHE ) and x := G , t

|C|

and samples e x ← $ D R,χ . It then samples the honest coordinates uniformly at random and computes the corrupt coordinates as real partial decryptions, that is

(pd k ) k∈H ← $ R |H|

and

(pd k ) k∈C := ξ · S C Ax + e x mod q.

In either case, it sets L Share [id] := (pd k ) k∈[K] . It returns pd k ← L Share [id] to A. – Eventually, it receives b ′ from A and returns b ′ .

Below we analyse the reduction’s simulation. Recall that C ∗ satisfies ({0} ∪ C) ⊆ C ∗ ⊆ [0, K]. Notice that V H · u 0 ∥u∥ = = V H · ξ · V C −1 ≤ θ(t), ∗ · v 0

where the second equality is by definition of u 0 = T C · v 0 = ξ · V C −1 ∗ · v 0 , θ(t) is one of the quality measurements of the subtractive set Ξ (Definition 1, Eq. (4)), and the inequality holds by taking T ∗ = C ∗ \ {0} in Eq. (4). Here V H carries more rows than V Ξ\T ∗ when |C| < t − 1, but the additional rows, indexed by the filler honest parties (C ∗ \ {0}) \ C, vanish on u 0 since V C ∗ · u 0 = ξ · v 0 , so the two give the same norm. Therefore, the queries made by B 3 to the oracle LeakO are valid. Below, we show that B 3 perfectly simulates the view of either Hyb 0,3 or Hyb 1,3 to A, if it is interacting either with the IND-CPA-with-(θ(t), K, χ)-leakage experiment 0 or 1. Consider the µ 0 = µ 1 case. By definition of the IND-CPA-with-(θ(t), K, χ)-leakage security experiment (Fig. 2), one has V H · u 0 leak = u · ê + f = · ê + f .

where

ê := ĉ 1 − ŝ T · ĉ 0 − ξ −2

µ mod q

as also defined in Eq. (24). It follows that h j m i V H (U 1 , U 2 ) V H u 0 w x (pd k ) k∈[K] = (b − e) T x − ĉ 1 − p q · ξ −2 · µ + leak + mod q ξI C S C Ax

<!-- page 46 -->

i j m V H u 0 h (b − e) T x − ĉ 1 − p q · ξ −2 · µ V H (U 1 , U 2 ) V H u 0 w x + · ê + f + mod q ξI C S C Ax i V (U , U ) w j m V H u 0 h H x = + f mod q (b − e) T x − ĉ 1 − p q · ξ −2 · µ − ê + ξI C S C Ax h i V (U , U ) j m w x V H u 0 H + + e x mod q = (b − e) T x − ĉ 1 − p q · ξ −2 · µ + ê ξI C S C Ax

=

where in the last line we have used that f and e x are identically distributed. This matches the distribution of (pd k ) k∈[K] defined in Eq. (23). For the µ 0 ̸ = µ 1 case, recall that the distribution of (pd k ) k∈[K] is identical in Hyb b,3 and Hyb b,2 , where in the latter (pd k ) k∈H are uniformly random and (pd k ) k∈C are real partial decryptions. This is exactly the distribution of (pd k ) k∈[K] sampled by the reduction. It follows that the ParDecO is correctly simulated in both cases. If B 3 is interacting with the IND-CPA-with-(θ(t), K, χ)-leakage experiment 0, then queries to ChalO(id, µ 0 , µ 1 ) return ctxt FHE ← FHE.Enc(pk FHE , µ 0 ) and therefore ctxt ← Enc(pk, µ 0 ). Therefore, the view of A is identical to Hyb 0,3 . If B 3 is interacting with the IND-CPA-with-(θ(t), K, χ)-leakage experiment 1, then queries to ChalO(id, µ 0 , µ 1 ) return ctxt FHE ← FHE.Enc(pk FHE , µ 1 ) and therefore ctxt ← Enc(pk, µ 1 ). Therefore, the view of A is identical to Hyb 1,3 . Therefore, Adv 3 (A) ≤ Adv IND-CPA-wL FHE,B 3 ,(θ,K,χ) (λ), as claimed.

G

## A Utility Lemma and Intermediate Assumption

In Appendix G.1, we state the Leaky LWE assumption and provide lemmas on reducing it from standard LWE. The Leaky LWE assumption serves as an intermediate interface which simplifies our proof steps. Using this, in Appendix G.2, we state and prove a utility lemma (Lemma 21), which concerns the computational indistinguishability of a pair of real and ideal experiments. This utility lemma is invoked in the proof of Theorem 3, specifically in Lemma 12, in Appendix F. Additional results assisting this utility lemma are in Appendices G.3 and G.4.

G.1

Intermediate lattice assumption

The Leaky LWE assumption [LSW25] supports leakages on the LWE errors, i.e. the adversary declares the set of leakage functions and sees the noisy evaluated LWE errors, conditioned on that the leakage functions are norm-bounded. We state both the semi- and fully-adaptive versions below.

Definition 8 (LLWE [LSW25], AdpLLWE). Let par = (R, n, m, Q, q, χ̄, χ, L, D A ) be parametrised by λ, where D A ∼ R n×m is a distribution. The semi-adaptive Leaky LWE assumption LLWE par (resp. adaptive Leaky LWE assumption AdpLLWE par ) states that for any PPT adversary A, for the experiments Exp-LLWE b given in Fig. 4, it holds that

LLWE , AdpLLWE

:= Pr Exp-LLWE 0 par,A (1 λ ) = 1 − Pr Exp-LLWE 1 par,A (1 λ ) = 1 ≤ negl(λ).

Adv par,A

The parameter D A is suppressed if it is the uniform distribution over R n×m

[LSW25], resp. [HKM + 26] 17 , showed that the semi-adaptive, resp. full-adaptive, Leaky LWE is implied by standard LWE under a polynomial-size modulus q. We recall both results below, with that of [HKM + 26] adapted to the formulation and norm convention in this work. For completeness, we also provide the adapted proof.

More specifically, [HKM + 26] showed that the Adaptive Hint-MLWE assumption is implied by Hint-MLWE [KLSS23], the latter further implied by LWE. Leaky LWE is a variant of Hint-MLWE, and the reduction of [HKM + 26] equally applies to Leaky LWE.

<!-- page 47 -->

Exp-LLWE b par,A (1 λ )

A ← D A

ē ← $ D R, χ̄

r ← $ R n q ;

if b = 0 then b := r A + ē mod q

if b = 1 then b ← $ R m

Z ← A(A)

assert Z ∈ L ⊆ R m×Q

Q e ← $ D R,χ ; l T := ē T · Z + e T

return A(b, l)

i := 0

return A LeakO (A, b)

LeakO(z)

assert i < Q

i := i + 1

assert z ∈ L ⊆ R m

e ← $ D R,χ ; ℓ := ē T · z + e

return ℓ

Fig. 4: Experiments for Leaky LWE (Definition 8), dashed box for semi-adaptive, solid box adaptive.

for

∗ Lemma 16 (Special case of [LSW25, Theorem 3]). Let R, n, m, Q, q, √ ϵ, α, χ̄, χ, m χ , L, D be parametrised n×m ∗ by λ, where R = Z[ζ], n, m, Q, q ∈ N, D ∼ R q , 0 < ϵ ≤ 1/2, χ ≥ 2 · η ϵ (R ), χ̄ > 0, χ > 0, and n o m×Q L = Z ∈R : ∥Z ∥ 2,2 ≤ α , where α = χ · (2η ϵ (R m ) 2 + (χ ∗ ) 2 ) −1 − χ̄ −2 . Denote par = (R, n, m, q, χ ∗ , D), par L = (R, n, m, Q, q, χ̄, χ, L, D).

∀ PPT A, ∃ PPT B such that

LWE Adv LLWE par L ,A (λ) ≤ Adv par,B (λ) + 6 · ϵ/(1 − ϵ).

In particular, if ϵ ∈ negl(λ) and the LWE par assumption holds, then the LLWE par L assumption holds.

The following is a special case of the Gaussian convolution lemma in [GMPW20], needed for Lemma 18.

Lemma 17 (Special case of [GMPW20, Theorem 3.1 (eprint)]). Let R = Z[ζ] have ring degree φ and coefficient embedding ψ, let m ∈ N, 0 < ϵ ≤ 1/2, and s, κ > 0 with s > η ϵ (R m ). Let z ∈ R m be arbitrary satisfying Ψ (z T ) 2,2 ≤ κ · 1 − η ϵ (R m ) 2 /s 2

and let Σ z := s 2 (κ 2 I φ − Ψ (z T )Ψ (z T ) T ). Then the statistical distance between z y + f y ← $ D R,s , f ← $ D R, √ Σ z and

is at most ϵ/(1 − ϵ) ≤ 2ϵ.

Proof. In this proof we use the shorthands

M := Ψ (z T ),

µ := ∥M∥ 2,2 ,

## D R,κs

η := η ϵ (R m ) = η ϵ (Z φm ).

Σ := Σ z ,

The bijection ψ preserves statistical distances and maps the distributions

## D R,s , D R, √ Σ , D R,κs , z T y

to

## D Z φm ,s , D Z φ , √ Σ , D Z φ ,κs , M · ψ(y)

respectively, so it suffices to bound the distance between D := {My + f | y ← $ D Z φm ,s , f ← $ D Z φ , √ Σ } and D Z φ ,κs . We apply [GMPW20, Theorem 3.1 (eprint)], for which we express √ the distribution D as a linear image of φm+φ one discrete Gaussian vector. Let Λ := Z , S := diag s · I φm , Σ and T := (M | I φ ) ∈ Z φ×(φm+φ) .

<!-- page 48 -->

y with independent f y ← $ D Z φm ,s and f ← $ D Z φ , √ Σ , and Tx = My + f . Hence T · D Λ,S is exactly the distribution of My + f in D, and it remains to check the requirements of [GMPW20, Theorem 3.1 (eprint)]:

Since SS T = diag s 2 I φm , Σ is block diagonal, a sample x ← $ D Λ,S is x =

– S has full column rank and Λ ⊆ span(S) = R φm+φ . – ker(T) = {(u, −Mu) : u ∈ R φm } is spanned by Λ ∩ ker(T) = {(u, −Mu) : u ∈ Z φm }, using M ∈ Z φ×φm , i.e. ker(T) is a Λ-subspace. ′ ′ ′ ′T ′ ′T for – η ϵ (Λ ∩ ker(T)) ≤ S. Recall that matrices S ≤ T means S S ⪯ T T [GMPW20]. Since I Λ ∩ ker(T) = CZ φm for C := φm , by [GMPW20, Definition 2.4 (eprint)] the condition is same as −M " s −1 I φm φm −1 √ −1 η ϵ (BZ ) ≤ 1 where B := S C = − Σ M

As η ϵ (Z φm ) = η, [GMPW20, Lemma 2.5 (eprint)] gives η ϵ (BZ φm ) ≤ ηB, so it suffices to show ηB ≤ I φm+φ , i.e. η 2 B T B ⪯ I φm . Write X := M T M, whose eigenvalues lie in [0, µ 2 ], with µ < κ by (26). Using Σ −1 = s −2 (κ 2 I φ − MM T ) −1 and M T (κ 2 I φ − MM T ) −1 = (κ 2 I φm − X) −1 M T (the “push-through identity”), B T B = s −2 I φm + M T Σ −1 M = s −2 I φm + (κ 2 I φm − X) −1 X

κ 2 κ 2 2 −1 (κ I − X) ⪯ I φm ⪯ η −2 I φm , φm s 2 s 2 (κ 2 − µ 2 )

=

where the last step is (26) squared and rearranged.

Therefore T · D Λ,S and D TΛ,TS are within relative error 2ϵ/(1 − ϵ), hence within statistical distance ϵ/(1 − ϵ) ≤ 2ϵ using ϵ ≤ 1/2. Finally TΛ = Z φ and (TS)(TS) T = s 2 MM T + Σ = κ 2 s 2 I φ , so D TΛ,TS = D Z φ ,κs .

The next lemma, adapted from [HKM + 26], shows that fully-adaptive Leaky LWE is implied by the semi-adaptive counterpart.

Lemma 18 (Adapted from proof of [HKM + 26, Theorem 1]). Let R, n, m, Q, q, ϵ, α, κ, χ̄, χ, D be parametrised by λ, where R = Z[ζ] has ring degree φ and field expansion factor c 2 w.r.t. the coefficient ℓ 2 -norm, and n, m, Q, q ∈ N, D ∼ R n×m , 0 < ϵ ≤ 1/2, and α ≥ 1, κ, χ̄, χ > 0 satisfy c 2 · α ≤ κ · 1 − κ 2 · η ϵ (R m ) 2 /χ 2 .

Define the parameters

par L = (R, n, m, mQ, q, χ̄, χ/κ, L L , D) and par A = (R, n, m, Q, q, χ̄, χ, L A , D) where L L = {Z ∈ R m×mQ : ∥Z T ∥ 2,2 ≤ Q} and L A = {z ∈ R m : ∥z∥ 2 ≤ α}. ∀ PPT A, ∃ PPT B such that

LLWE Adv AdpLLWE par A ,A (λ) ≤ Adv par L ,B (λ) + 4 · Q · ϵ.

In particular, if Q ∈ poly(λ), ϵ ∈ negl(λ), and the LLWE R,n,m,mQ,q,χ̄,χ/κ,L L ,D assumption holds for some κ satisfying Eq. (27), then the AdpLLWE R,n,m,Q,q,χ̄,χ,L A ,D assumption holds.

Proof. Consider the following hybrid experiments, where Σ z := (χ/κ) 2 (κ 2 I φ − Ψ (z T )Ψ (z T ) T ):

Hyb 0 : The fully-adaptive Leaky LWE experiment (Fig. 4, solid box) with challenge bit b = 0. Hyb 1 : Almost identical to Hyb 0 , except that the challenger additionally samples e 1 , . . . , e Q ← $ D R,χ/κ , and it answers the i-th oracle query LeakO(z) with (ē + e i ) · z + f , where f ← $ D R, Σ z is sampled freshly and dependent on the query z. Hyb 2 : Almost identical to Hyb 1 , except that the challenger samples the vector b ← $ R m q uniformly randomly.

<!-- page 49 -->

Hyb 3 : Almost identical to Hyb 2 , except that challenger undoes the change in Hyb 1 , i.e. each oracle query LeakO(z) is answered with ē T · z + e where e ← $ D R,χ is a fresh error, as in Hyb 0 .

We have the following:

– By Lemma 19, the advantage in distinguishing Hyb 0 and Hyb 1 is at most 2Qϵ. – By Lemma 20, the advantage in distinguishing Hyb 1 and Hyb 2 equals Adv LLWE par L ,B (λ) for some PPT B. – By the same argument as for Hyb 0 and Hyb 1 , the advantage in distinguishing Hyb 2 and Hyb 3 is again at most 2Qϵ.

The proof is completed by noting that Hyb 3 is identical to the fully-adaptive Leaky LWE experiment with challenge bit b = 1, and the claimed bound follows from the triangle inequality.

Lemma 19. For any (computationally unbounded) A, the advantage in distinguishing Hyb 0 and Hyb 1 is at most 2Qϵ.

Proof. For i ∈ {0, 1, . . . , Q}, let Hyb 0,i be identical to Hyb 0 except that the first i oracle queries are answered as in Hyb 1 , so that Hyb 0,0 = Hyb 0 and Hyb 0,Q = Hyb 1 . Fix any i ∈ [Q]. The answer to the i-th LeakO query z in Hyb 0,i is ê T i · z + f = ē T · z + e T i · z + f .

By Lemma 17, applied with y = e i and using κs = χ, the summand e T i · z + f is within statistical distance 2ϵ to D R,χ , which is the distribution of the corresponding error in Hyb 0,i−1 . As Hyb 0,i−1 and Hyb 0,i are otherwise identical, their statistical distance is at most 2ϵ. Summing over i ∈ [Q] yields the claim. In the rest we show that the requirements in Lemma 17 are satisfied, so that it can indeed be applied. Let z ∈ L A be any admissible query and write z = (z 1 , . . . , z m ). For any x = (x 1 , . . . , x m ) ∈ K m we have X z T x 2 ≤ c 2 · ∥z j ∥ 2 · ∥x j ∥ 2 ≤ c 2 · ∥z∥ 2 · ∥x∥ 2

j∈[m]

by the triangle inequality and Cauchy–Schwarz, hence

z T 2,2 = Ψ (z T ) 2,2 ≤ c 2 · ∥z∥ 2 ≤ c 2 · α.

The above together with Eq. (27) imply Eq. (26) for s = χ/κ, i.e. Ψ (z T ) 2,2 ≤ κ · 1 − κ 2 · η ϵ (R m ) 2 /χ 2

holds. Clearly Eq. (27) also implies the other requirement of κ · η ϵ (R m )/χ < 1.

Lemma 20. For any PPT A there exists a PPT B such that the advantage of A in distinguishing Hyb 1 and Hyb 2 is equal to Adv LLWE par L ,B (λ).

Proof. Given a PPT A distinguishing Hyb 1 and Hyb 2 , we construct a PPT reduction B against LLWE par L , as follows:

– Receive A from the LLWE challenger, reply with the leakage matrix Z := (I m | · · · |I m ) ∈ R m×mQ . – Receive (b, l) from the LLWE challenger, pass (A, b) to A. Also, write l T = (l T 1 , . . . , l T Q ) with each l i ∈ R m . – Maintain a counter i := 0. Answer A’s oracle queries LeakO(z) as follows: • Assert i < Q and z ∈ L A , and set i := i + 1. • Sample f ← $ D R, √ Σ z and answer with l T i · z + f . – Eventually receive a bit b ′ from A, return b ′ .

The reduction B is admissible as an LLWE par for any √ L adversary, since √ y ∈ K we have Z · y = T T mQ (y , . . . , y ) ∈ K , which implies ∥Z · y∥ 2 = Q · ∥y∥ 2 , so ∥Z ∥ 2,2 = Q and Z ∈ L L . The simulation is perfect: in the LLWE par L experiment with challenge bit b, the matrix A and the error ē ← $ D R, χ̄ are distributed as in Hyb 1 and Hyb 2 , the vector b is as in Hyb 1 if b = 0 and as in Hyb 2 if b = 1. In either game, by the choice of Z,

l T = ē T · Z + e T

mQ // e ← $ D R,χ/κ

<!-- page 50 -->

= ē T · (I m | · · · |I m ) + (e T 1 | . . . |e T Q )

= (ē T + e T 1 | . . . | ē T + e T Q )

l i = ē + e i ∀i ∈ [Q],

⇐⇒

// (e T 1 | . . . | e T Q ) := e T

// e i ← $ D R,χ/κ

hence each LeakO(z) query answer is (ē + e i ) T · z + f , as wanted. Overall, B’s answers are exactly those of Hyb 1 , resp. Hyb 2 .

By Lemmas 16 and 18, standard LWE thus implies fully-adaptive Leaky LWE, summarised below.

Corollary 2 (Adapted from [HKM + 26, Theorem 1]). Let R, n, m, Q, q, ϵ, α, κ, χ̄, χ, χ ∗ , D be parametrised by λ, where R = Z[ζ] has ring degree φ and √ field expansion factor c 2 w.r.t. the coeffi- ∗ cient ℓ 2 -norm, n, m, Q, q ∈ N, D ∼ R n×m , < ϵ ≤ 1/2, χ ≥ 2 · η ϵ (R m ), and α ≥ 1, κ, χ̄, χ > 0 satisfy both c 2 · α ≤ κ · 1 − κ 2 · η ϵ (R m ) 2 /χ 2 , χ p Q ≤ · (2η ϵ (R m ) 2 + (χ ∗ ) 2 ) −1 − χ̄ −2 . κ Denote par = (R, n, m, q, χ ∗ , D), par A = (R, n, m, Q, q, χ̄, χ, L A , D),

where L A = {z ∈ R m : ∥z∥ 2 ≤ α}. ∀ PPT A, ∃ PPT B such that

LWE Adv AdpLLWE par A ,A (λ) ≤ Adv par,B (λ) + 4 · Q · ϵ + 6 · ϵ/(1 − ϵ).

In particular, if Q ∈ poly(λ), ϵ ∈ negl(λ) and the LWE par assumption holds, then the AdpLLWE par A assumption holds.

Proof. Follows from putting Lemmas 16 and 18 together. In particular, we invoke Lemma 16 with LLWE parameters par ′ = (R, n, m, mQ, q, χ̄, χ/κ, L ′ , D), where L ′ = {Z ∈ R m×mQ : ∥Z T ∥ 2,2 ≤ α ′ } with α ′ = χκ · (2η ϵ (R m ) 2 + (χ ∗ ) 2 ) −1 − χ̄ −2 . Since L ′ ⊇ L L := {Z ∈ R m×mQ : ∥Z T ∥ 2,2 ≤ Q} by Eq. (29), LLWE with par ′ implies LLWE with par L = (R, n, m, mQ, q, χ̄, χ/κ, L L , D), the latter being the same as that used in Lemma 18. Eq. (28) is identical to Eq. (27) required by Lemma 18.

Remark 9 (On choosing κ for Lemma 18 and Corollary 2). Keeping everything else unchanged, a smaller κ in Lemma 18 and Corollary 2 is desired, since it leads to a larger error parameter χ/κ for LLWE in Lemma 18, i.e. a harder LLWE problem, and it makes Eq. (29) in Corollary 2 more easily satisfied. Writing η := η ϵ (R m ), a κ satisfying Eq. (28) exists if and only if

χ ≥ 2 · c 2 · α · η,

1 ± 1 − (2 · c 2 · α · η/χ) 2 . 18

χ in which case any κ such that κ 2 ∈ [κ 2 − , κ 2+ ] is admissible, where κ 2 ± := 2η For the minimum κ − , it holds that c 2 · α ≤ κ − ≤ 2 · c 2 · α, which follows from κ 2 − · (1 − κ 2 − · η 2 /χ 2 ) = c 22 · α 2 and from 1 − 1 − t ≤ t for t ∈ [0, 1], the latter giving

4·c 2 ·α 2 ·η 2

χ κ 2 − ≤ 2η 2 · χ 2 A sufficient condition for Eq. (29) at κ = κ − is thus 2Q · c 2 · α ≤ χ · (2η 2 + (χ ∗ ) 2 ) −1 − χ̄ −2 .

In the latter sections where we invoke Corollary 2, we will always directly require Eq. (31) instead of Eqs. (28) and (29). This is sufficient, since Eq. (31) and the condition χ ∗ ≥ 2 · η ϵ (R m ) jointly imply Eq. (30) 19 , and Eqs. (30) and (31) in turn imply that Eqs. (28) and (29) hold for the choice κ = κ − by the above.

Squaring Eq. (28) gives κ 4 · η 2 /χ 2 − κ 2 + c 22 · α 2 ≤ 0, a quadratic in κ 2 whose roots are the stated κ 2 ± . The latter are real √ if and only if 2 · c 2 · α · η/χ ≤ 1. Since χ ∗ ≥ 2 · η, the radicand in Eq. (31) is at most √ (2η 2 + 2η 2 ) −1 = (4η 2 ) −1 , so the right-hand side of Eq. (31) is at most χ/(2η). Hence Eq. (31) gives χ ≥ 2 · 2Q · c 2 · α · η, which implies Eq. (30) since Q ≥ 1.

<!-- page 51 -->

Real par,A (1 λ )

## L Share := ∅; L Query := ∅

A ← $ D A

(C, z) ← A (A) ; assert |C| < t

R ← $ R t×n

## S C := V C · R mod q ∈ R C×n

r := v 0 T · R mod q

e ← $ D R, χ̄

b T := r T A + e T + z T mod q

′

′

GenO,ShareO 0

(b, ξ · S C )

b ←A

assert |L Share | ≤ Q

// at most Q shared Ax

′

return b

// c̃ ∈ R (m−mt )

GenO(id, c̃)

if L Query [id] = ∅ then

assert ∥c̃∥ ≤ B c c̃ t̃ ← $ D t ; x := t̃

## L Query [id] := x

return x ← L Query [id]

ShareO b (id, k ∈ [K])

if L Share [id] = ∅ then

assert L Query [id] ̸ = ∅; parse x ← L Query [id]

if b = 0 then

K e x ← $ D R,χ ; d := ξ · VRAx + e x mod q

if b = 1 then

(d, st) ← S Share (x, st)

## L Share [id] := d

parse d ← L Share [id] ∈ R K

return d k

Ideal par,A (1 λ )

## L Share := ∅; L Query := ∅

A ← $ D A

(C, z) ← A (A) ; assert |C| < t

## S C ← $ R C×n

b ← $ R m

st ← S Init (A, b, S C , z)

// State of simulator S

GenO,ShareO 1

(b, ξ · S C )

b ←A

assert |L Share | ≤ Q

// at most Q shared Ax

′

return b

## S Init (A, b, S S , z)

e ← $ D R, χ̄ ; b̂ := b − e − z

return st := (A, b, S S , b̂)

## S Share (x, st)

K e x ← $ D R,χ

w x ← $ R t−|C|−1

 T  V H · T C  b̂ x  + e x mod q w x ξI C S C Ax

d :=

return (d, st)

Fig. 5: Real par,A and Ideal par,A with par = ((R, n, m, q, Q, χ̄, χ, D A , D t , B c ), (t, K, Ξ)).

Remark 10. The semi-adaptive Leaky LWE in [LSW25] more generally supports bounded-norm leakage also on the LWE secret r, and admits a reduction from LWE when r is distributed as Gaussian. The adaptive version can be generalised in an analogous way, where the oracle LeakO returns leakages of the form (r T , ē T ) · z + e. When r is Gaussian vector, Lemma 18 and Corollary 2 can be generalised analogously.

G.2

Utility Lemma

This subsection is devoted to proving that the two experiments Real and Ideal in Fig. 5 are computationally indistinguishable under two LWE assumptions, one with respect to the tag distribution D t and one with respect to the public matrix distribution D A . This is formally given in Lemma 21. The majority of its proof is a generalisation of [CLW25, Lemma 10, Eprint].

Lemma 21. Let par = ((R, n, m, q, Q, χ̄, χ, D A , D t , B c ), (t, K, Ξ)) be parametrised by λ, where R = Z[ζ] has ring degree φ and field expansion factor c p w.r.t. the coefficient ℓ p -norm, Ξ is a size-K ξ-subtractive

<!-- page 52 -->

set with quality measurements (ρ, γ, θ) = (ρ(t), γ(t), θ(t)) (Definition 1), D A and D t are distributions over R n×m and R m t respectively with m t < m, and B c > 0. Let B t > 0 be such that Pr( t̃ ≤ B t | t̃ ← $ D t ) = 1. Consider the experiments Real par,A and Ideal par,A in Fig. 5, and define the advantage bound

λ λ Adv RealIdeal par,A (λ) := Pr Real par,A (1 ) = 1 − Pr Ideal par,A (1 ) = 1 .

Suppose q and ξ are coprime, 0 < ϵ ≤ 1/2, and the noise parameters χ ∗ 1 , χ ∗ 2 satisfy both of the following: – χ ∗ 1 ≥ 2 · η ϵ (R t ) is such that there exists χ̂ > 0 satisfying

(2η ϵ (R t ) 2 + (χ ∗ 1 ) 2 ) −1 − χ̂ −2 ;

γ ≤ χ ·

⊗ – χ ∗ 2 ≥ 2 · η ϵ (R m ), γ · φm · max(B c , B t ) ≥ 1, and, with c ⊗ t t := 1 if f is a power of two and c t := otherwise, 2QK · φm · c 2 · c ⊗ · γ · max(B , B ) ≤ χ · (2η ϵ (R m ) 2 + (χ ∗ 2 ) 2 ) −1 − χ̄ −2 . c t t

Then, for any PPT A, there exist PPT B 1 , B 2 such that

LWE (λ) (λ) + Adv LWE · Adv RealIdeal (R,n,m,q,χ ∗ par,A (λ) ≤ Adv (R,m t ,poly(λ),q,χ ∗ 2 ,D A ),B 2 1 ,D t ),B 1 t 6 · Q · ϵ 6 · ϵ + + 4 · QK · ϵ + t(1 − ϵ) 1 − ϵ

In particular, if QK ∈ poly(λ), ϵ ∈ negl(λ), and the LWE R,m t ,poly(λ),q,χ ∗ 1 ,D t and LWE R,n,m,q,χ ∗ 2 ,D A assumptions hold, then the experiments Real par,A and Ideal par,A are computationally indistinguishable.

Proof. Let the experiment Real par,A be Hyb 0 , and we define experiments Hyb 1 , Hyb 2 , Hyb 3 and Hyb 4 in Fig. 6. Below we argue that Hyb i is indistinguishable from Hyb i+1 for each i ∈ {0, 1, 2, 3}. The proof is then completed by noting that Hyb 4 is identical to the experiment Ideal par,A .

V H by definition, thus the Hyb 1 . This is functionally equivalent to Hyb 0 = Real par,A . Notice that V = V C  T  r only differences in Hyb 1 are that we sample uniformly random  W  , and we swap S C

  v 0 T v 0 T R =  ξ · V H  R ξ · V ξ · V C

to

 T     T  r r M ·  W  =  V H · T C   W  . S C S C ξI C

We recall T C ∈ R t×t is such that it holds ξ −1 · T C · V C ∗ = I t for some size-t set C ∗ satisfying ({0} ∪ C) ⊆ C ∗ ⊆ [0, K]. To see that the two terms are functionally equivalent, we denote C ¯ := C ∗ \ ({0} ∪ C) and notice        T     T  v 0 T 1 · v 0 T v 0 r v 0 R =  ξ · V H  R =  ξ · ξ −1 · V H · T C · V C ∗  R =  V H · T C   V C̄  R ≡  V H · T C   W  mod q, ξ · V ξ · V C ξ · I C · V C V C S C ξI C ξI C | {z } | {z }

=V C∗

uniform

where the first = is by definition of V, the second = holds since ξ −1 · T C · V C ∗ = I t , and the last ≡ holds because ξ and q are coprime and thus V C −1 ∗ exists over R q .

t×t By definition of Ξ, ξ · V C −1 . Since ξ and q are coprime, there exists a ∈ R s.t. a · ξ = 1 + q · h for some ∗ ∈ R −1 t×t h ∈ Z. We have a · ξ · V C ∗ · V C ∗ = (1 + q · h) · I, and a · ξ · V C −1 . Therefore, a · ξ · V C −1 ∗ ∈ R ∗ mod q is the ∗ inverse of V C over R q .

<!-- page 53 -->

Hyb 1 (1 λ )

Hyb 2 (1 λ )

Hyb 3 (1 λ )

## L Share [·] := ∅

## L Share [·] := ∅

A ← $ D A

A ← $ D A

A ← $ D A

(C, z) ← A (A) ; assert |C| < t

(C, z) ← A (A) ; assert |C| < t  T  r  W  ← $ R t×n S C

## S C ← $ R C×n r m ← $ R (t−|C|)×m W m

e ← $ D R, χ̄

e ← $ D R, χ̄

:= r T m + e T + z T mod q

b := r A + e + z mod q

b

b

′

′

ShareO Hyb2

′

ShareO Hyb1

(b, ξ · S C )

b ←A

(b, ξ · S C )

b ←A

b ←A

assert |L Share | ≤ Q

assert |L Share | ≤ Q

return b ′

return b ′

return b ′

ShareO Hyb2 (id, k ∈ [K])

ShareO Hyb1 (id, k ∈ [K])

if L Share [id] = ∅ then

if L Share [id] = ∅ then

assert L Query [id] ̸ = ∅

assert L Query [id] ̸ = ∅

parse x ← L Query [id]

parse x ← L Query [id]

K e x ← $ D R,χ

K e x ← $ D R,χ

## V H · T C ξI C  T  r m d := M ·  W m  x + e x mod q S C A

## V H · T C ξI C  T  r d := M ·  W  Ax + e x mod q S C

M :=

M :=

M :=

## L Share [id] := d ∈ R K

## L Share [id] := d ∈ R K

parse d ← L Share [id]

parse d ← L Share [id]

return d k

return d k

return d k

Hyb 4 (1 λ )

## L Share [·] := ∅

## L Share [·] := ∅

A ← $ D A

(C, z) ← A (A) ; assert |C| < t

(C, z) ← A (A) ; assert |C| < t

## S C ← $ R C×n

## S C ← $ R C×n

r T m ← $ R 1×m

e ← $ D R, χ̄

e ← $ D R, χ̄

:= r T m + e T + z T mod q

b T ← $ R m

ShareO Hyb3

b ′ ← A ShareO Hyb4 (b, ξ · S C )

(b, ξ · S C )

assert |L Share | ≤ Q

assert |L Share | ≤ Q

return b ′

ShareO Hyb3 (id, k ∈ [K])

ShareO Hyb4 (id, k ∈ [K])

if L Share [id] = ∅ then

if L Share [id] = ∅ then

assert L Query [id] ̸ = ∅

assert L Query [id] ̸ = ∅

parse x ← L Query [id]

parse x ← L Query [id]

K e x ← $ D R,χ

K e x ← $ D R,χ

w x ← $ R t−|C|−1

w x ← $ R t−|C|−1 V H · T C M := ξI C   (b − e − z) T x   + e x mod q w x d := M · S C Ax

## V H · T C ξI C  T  r m x d := M ·  w x  + e x mod q S C Ax

## L Share [id] := d ∈ R K

## L Share [id] := d ∈ R K

parse d ← L Share [id]

parse d ← L Share [id]

return d k

Fig. 6: Hybrid distributions Hyb 1 to Hyb 4 for proof of Lemma 21. For each, the changes relative to the previous hybrid are marked in red. The oracle GenO is unchanged and omitted.

Hyb 2 . We swap the vector b T and each vector d from

r T A + e T + z T mod q

and

r T m + e T + z T mod q

and

to

 T  r M ·  W  Ax + e x mod q S C  T  r m M ·  W m  x + e x mod q S C A

respectively, where r m , W m are uniformly random. For this, we will invoke Theorem 5, instantiating its parameters (t, t 2 ) with (t − |C|, |C|) and its matrix with V H · T C M = (M 1 , M 2 ) := ∈ R K×((t−|C|)+|C|) , ξI C

r so that its secret matrices are S 1 = and S 2 = S C , and its unit vector u selects the row r T of S 1 , W c̃ whose noisy image is b. We bound the ℓ 2 -induced norm of M 1 and the norm of x := : t̃

∥M 1 ∥ 2,2 ≤ ∥V H · T C ∥ 2,2 = ξ · V H · V C −1 ≤ γ, ∗ 2,2

∥x∥ ∞ ≤ max(B c , B t ),

where the first inequality holds since M 1 consists of the first t − |C| columns of M, the block ξI C contributing to M 2 only, and where we recall γ is a quality measurement of Ξ (ref. Eq. (4)): the last inequality holds by taking T ∗ = C ∗ \ {0} in Eq. (4), since the rows of V H are a subset of the rows of V Ξ

<!-- page 54 -->

and removing rows does not increase the ℓ 2 -induced norm. The remaining requirements of Theorem 5 are satisfied by assumptions in this lemma: We set the noise parameter χ ∗ = χ ∗ 2 , the norm bound β = max(B c , B t ). The two constraints in Theorem 5, at its instantiated threshold t − |C|, follow from ⊗ γ · φm · max(B c , B t ) ≥ 1 and Eq. (32), since 1 ≤ c ⊗ t−|C| ≤ c t . Then, by Theorem 5, whose advantage bound carries the multiplicative factor t−|C| ≤ t, the advantage of any PPT algorithm B 2 in distinguishing Hyb 1 and Hyb 2 is upper-bounded by 6 · ϵ t · Adv LWE (λ) + · QK · ϵ + ∗ (R,n,m,q,χ 2 ,D A ),B 2 1 − ϵ

(To use Theorem 5, the trivial reduction forwards A to A, adds z T to the vector b T received from the experiment Exp2 b , passes ξS 2 in place of S 2 , and answers the first ShareO query on each id by querying O b once on the vector x recorded in L Query [id] and storing the answer under id, and every later query on the same id from that stored answer.)

Hyb 3 . We swap each vector d from  T  r m M ·  W m  x + e x mod q S C A

to



 r T m x M ·  w x  + e x mod q S C Ax

where w x is uniformly random. For this, we will invoke Theorem 4, for which we again write M = (M 0 , M 1 , M 2 ); here M 1 (width t 1 = t − |C| − 1) is the block swapped to uniform, while M 0 , M 2 (total width 1 + |C|) are left unchanged and together play the role of Theorem 4’s second block, so we instantiate Theorem 4 with t 1 = t − |C| − 1 and t 2 = 1 + |C|. We bound the norm of M 1 :

∥M 1 ∥ 2,2 ≤ ∥V H · T C ∥ 2,2 = ξ · V H · V C −1 ≤ γ, ∗ 2,2

where we recall γ is a quality measurement of Ξ (ref. Eq. (4)), and the last inequality holds for the same reason as in the Hyb 2 step. Then, by Theorem 4, whose advantage bound carries the multiplicative factor t 1 = t − |C| − 1 ≤ t, the advantage of any PPT algorithm B 1 in distinguishing Hyb 2 and Hyb 3 is upper-bounded by 6 · Q · ϵ tAdv LWE (λ) + , (R,m t ,poly(λ),q,χ ∗ 1 ,D t ),B 1 1 − ϵ where χ ∗ 1 ≥ 2 · η ϵ (R t ) is such that there exists χ̂ > 0 satisfying γ ≤ χ · (2η ϵ (R t ) 2 + (χ ∗ 1 ) 2 ) −1 − χ̂ −2 ,

as assumed in the statement of this lemma. (To use Theorem 4, the trivial reduction queries TagO from the experiments in Theorem 4 to obtain t̃ to answer GenO queries, simply forwards the ShareO queries to the oracle O, and generates the rest itself.)

Hyb 4 . This is functionally equivalent to Hyb 3 . We rewrite the vectors b = r m +e+z mod q and r m ← $ R m in Hyb 3 as b ← $ R m q and (b − e − z) in Hyb 4 . This is a simple change of variables of uniformly random vectors, and clearly the two hybrids are identically distributed.

We provide Theorems 4 and 5 involved in Lemma 21 in the remaining subsections.

G.3

Theorem 4 and proofs

Theorem 4. Let R, m, Q, q, m c , K, t 1 , t 2 , χ ∗ , χ, γ, D t and ϵ ∈ (0, 1) be parametrised by λ, where R = Z[ζ] ∗ has ring degree φ, m, Q, m c , K, t 1 , t 2 ∈ poly(λ) and D t is a distribution over R m q . Suppose χ , χ are such ∗ t 1 that χ ≥ 2 · η ϵ (R ), and there exists χ̂ > 0 such that γ ≤ χ · (2η ϵ (R t 1 ) 2 + (χ ∗ ) 2 ) −1 − χ̂ −2 . Denote

par = (R, m, Q, q, m c , K, t 1 , t 2 , χ, γ, D t ).

For any PPT A, define the following experiment Exp1 b par,A :

<!-- page 55 -->

Exp1 b par,A (1 λ )

L Query [·] := ∅; L t [·] := ∅ (M = (M 1 , M 2 ), S 2 ) ← A(1 λ ) t ×(m c +m) ∈ R K×(t 1 +t 2 ) × R q 2

assert ∥M 1 ∥ 2,2 ≤ γ

S 1 ← $ R t q 1 ×(m c +m)

b ′ ← A TagO,O b (1 λ )

return b ′

TagO()

i := |L t | + 1; t i ← $ D t

L t [i] := t i

return (i, t i )

O b (c ∈ R m c , i)

assert |L Query | < Q

if L Query [i] = ∅ then

assert L t [i] ̸ = ∅; parse t i ← L t [i] c K ; e ← $ D R,χ x := t i S 1 x + e if b = 0 then d := M · S 2

w + e S 2 x

if b = 1 then w ← $ R t q 1 ; d := M ·

## L Query [i] := d

return d ← L Query [i]

and denote the advantage of A in distinguishing the above experiments by λ λ Adv Exp1 par,A := Pr Exp1 par,A (1 ) = 1 − Pr Exp1 par,A (1 ) = 1 .

For any PPT A, there exists a PPT B such that

3ϵ 1 − ϵ

LWE Adv Exp1 par,A (λ) ≤ t 1 · Adv (R,m,poly(λ),q,χ ∗ ,D t ),B (λ) + 2Q ·

In particular, if the LWE R,m,poly(λ),q,χ ∗ ,D t assumption holds, then the experiments Exp1 0 par,A and Exp1 1 par,A are computationally indistinguishable.

Proof. Follows directly by putting Lemmas 23 and 24 together. (We rename χ̄ in Lemma 23 to χ̂.)

We will use the following statistical lemma from [LSW25] to prove Lemma 23. The proof of Lemma 23 is essentially an adaption of [LSW25, Thm.3].

Lemma 22 (Special case of [LSW25, Thm. 2]). Let m 1 , m 2 ∈ N and s 1 , s 2 , χ ∗ > 0. Fix any Z ∈ Z m 1 ×m 2 . Define the following matrices (dependent on s 1 , s 2 , Z):

m 1 ×m 2 Γ := s −2 , 2 · Z ∈ R

−2 m 1 ×m 1 Θ −1 := s −2 , 1 · I m 1 + s 2 · ZZ ∈ R

m 2 ×m 2 := s −2 2 · I m 2 − Γ · Θ · Γ ∈ R

−1

Φ

−1/2 −2 ∗ 2 ∗ −2 Let ϵ ∈ (0, 1) and υ −1 := √ s −2 + (υ − (χ ∗ ) 2 ) −1 ≥ 1 + s max (ZZ ) · s 2 . Suppose (χ ) < υ and (χ ) η ϵ (Z m 1 ), which implies υ ≥ η ϵ (Z m 1 ). Then, the statistical distance between the distributions   e ← $ D Z m 1 ,χ ∗ ; f 2 ← $ D Z m 2 , √ Φ   ( )     e 1 ← $ D Z m 1 ,s 1 c := Θ · Γ · f 2 e T 1 , e T 1 Z + e T 2 and e T + f 1 T , f 2 T   e 2 ← $ D Z m 2 ,s 2     f 1 ← $ D m 1 √ ∗ 2

is at most 3ϵ/(1 − ϵ).

,

Θ−(χ ) I m 1 ,c

Z

Lemma 23. Let R, m, Q, q, t 1 , K, χ̄, χ ∗ , χ, γ, D t and ϵ ∈ (0, 1) be parametrised by λ, √ where R = Z[ζ] ∗ has ring degree φ, m, Q, t 1 ∈ poly(λ) and D t is a distribution over R m 2 · η ϵ (R t 1 ), and q . Let χ ≥ −1 γ ≤ χ · (2η ϵ (R t 1 ) 2 + (χ ∗ ) 2 ) − χ̄ −2 . Denote

par = (R, m, Q, q, t 1 , K, χ̄, χ, γ, D t ).

For any PPT A, define the following experiment Exp b par,A :

<!-- page 56 -->

Exp b par,A (1 λ )

## L Query [·] := ∅; L t [·] := ∅

// initial lists

t 1 ×K

λ

Z ∈R

← A(1 ); assert Z

≤ γ

2,2

S ← $ R t q 1 ×m

b ′ ← A TagO,leakO b (·)

return b ′

TagO()

// t i ∈ R m

i := |L t | + 1; t i ← $ D t

L t [i] := t i

return (i, t i )

leakO b (i)

assert |L Query | < Q

if L Query [i] = ∅ then

assert L t [i] ̸ = ∅; parse t i ← L t [i]

t 1 K ē i ← $ D R, χ̄ ; e i ← $ D R,χ

if b = 0 then b i := S · t i + ē i mod q

if b = 1 then b i ← $ R t q 1

l T i := ē T i · Z + e T i mod q

## L Query [i] := (b i , l i )

return (b i , l i ) ← L Query [i]

and denote the advantage of A in distinguishing the above experiments by λ λ Adv Exp par,A := Pr Exp par,A (1 ) = 1 − Pr Exp par,A (1 ) = 1 .

For any PPT A, there exists a PPT B such that

3ϵ 1 − ϵ

LWE Adv Exp par,A (λ) ≤ t 1 · Adv (R,m,poly(λ),q,χ ∗ ,D t ),B (λ) + 2Q ·

In particular, if the LWE R,m,poly(λ),q,χ ∗ ,D t assumption holds, then the experiments Exp 0 par,A and Exp 1 par,A are computationally indistinguishable.

Proof. We will rely on that LWE with a uniformly random secret matrix S ← $ R q t 1 ×m is no easy than LWE with a uniformly random secret row vector. This is stated in the following proposition.

Proposition 4. Let R, m, q, t 1 , χ ∗ , D A , D t be parametrised by λ, where t 1 ∈ poly(λ) and D t is a distribution over R m q . For any PPT A, there exists a PPT B such that

LWE Adv LWE (R,m,poly(λ),t 1 ,q,χ ∗ ,D t ),A (λ) ≤ t 1 · Adv (R,m,poly(λ),q,χ ∗ ,D t ),B (λ),

The above follows directly from standard hybrid argument, its proof omitted. In the rest we show that, given a PPT A distinguishing Exp 0 and Exp 1 , we construct a PPT B against the LWE R,m,poly(λ),t 1 ,q,χ ∗ ,D t assumption. We will show that if A distinguishes the two experiments with advantage Adv Exp par,A (λ), then B breaks the LWE R,m,poly(λ),t 1 ,q,χ ∗ ,D t assumption with advantage at least

3ϵ 1 − ϵ

Adv Exp par,A (λ) − 2Q ·

The lemma then follows from combining with the proposition above. The PPT B works as follows:

– Receive for A the matrix Z, and assert ∥Z T ∥ 2,2 ≤ γ. – Internally maintain the lists L Query and L t . Also, let

Γ = χ −2 · Ψ (Z T ) T ,

−1

−1 Φ = χ −2 · I φK − Γ T Θ Γ ,

Θ = χ̄ −2 · I φt 1 + χ −2 · Ψ (Z T ) T Ψ (Z T )

,

where we recall that ψ : K → Z φ is the coefficient embedding w.r.t. the power basis (Section 3), and Ψ (M) is the matrix of x 7→ Mx in the coefficient embedding, so that ψ(Mx) = Ψ (M) · ψ(x). In particular ψ((ē T Z) T ) = ψ(Z T ē) = Ψ (Z T ) · ψ(ē), so the leakage ē T Z + e T is, in coefficients, ψ(ē) T · Ψ (Z T ) T + ψ(e) T , and Lemma 22 is applied with the integer matrix Ψ (Z T ) T ∈ Z φt 1 ×φK . – For any query to TagO, do the following: • Query the LWE challenger to obtain an LWE sample (t i , b̂ i ). • Store L t [i] := (t i , b̂ i ), i.e. including also the LWE sample b̂ i , and answer with t i . – For any query i to LeakO, do the following: • Assert |L Query | < Q, i.e. there has been fewer than Q distinct queries.

<!-- page 57 -->

• If L Query [i] = ∅, assert L t [i] ̸ = ∅ and parse (t i , b̂ i ) ← L t [i]. • Sample l i ← $ D R K , √ Φ , set c i := ψ −1 (Θ · Γ · ψ(l i )) 21 and F := Θ − (χ ∗ ) 2 I φt 1 , and sample f i ← $ D R t 1 , √ F,c i . Set b i := b̂ i + f i mod q and L Query [i] := (b i , l i ). • Answer with (b i , l i ) ← L Query [i]. – Eventually receive a bit b ′ from A, return b ′ .

We analyse the output of B.

If B interacts with the LWE experiment 0: In this case, each sample (t i , b̂ i ) from the LWE challenger is t 1 such that b̂ i = S · t i + ê i mod q, where ê i ← $ D R,χ ∗ . The simulated leakO answer is thus

(b i , l i ) = (S · t i + ê i + f i , l i ) ≈ s (S · t i + ē i , ē T i · Z + e T i ),

3ϵ where the last line follows from Lemma 22, with statistical distance at most 1−ϵ . Since there are at most 3ϵ Q many queries, the overall view of A is close to that from Exp with statistical distance at most Q · 1−ϵ

If B interacts with the LWE experiment 1: In this case, each sample (t i , b̂ i ) from the LWE challenger is such that b̂ i ← $ R t q 1 is uniformly random. The simulated leakO answer is thus

(b i , l i ) = ( b̂ + f i , l i ) = (U(R t q 1 ), l i ) ≈ s (U(R t q 1 ), ē T i · Z + e T i ),

3ϵ where the last line again follows from Lemma 22, with statistical distance at most 1−ϵ . Since there are at most Q many queries, the overall view of A is close to that from Exp with statistical distance at most 3ϵ Q · 1−ϵ Combining the two cases yields Eq. (35). It remains to see that Lemma 22 can indeed be invoked. Write υ −1 := χ̄ −2 + s max (Ψ (Z T ) T · Ψ (Z T )) · χ −2 . By the lemma condition,

s max (Ψ (Z T ) T · Ψ (Z T )) = Z T 2,2 ≤ γ 2 ≤ χ 2 (2η ϵ (R t 1 ) 2 + (χ ∗ ) 2 ) −1 − χ̄ −2 ,

which implies υ −1 ≤ (2η ϵ (R t 1 ) 2 + (χ ∗ ) 2 ) −1 , and therefore υ − (χ ∗ ) 2 ≥ 2η ϵ (R t 1 ) 2 . Together with the other −1/2 condition of (χ ∗ ) 2 ≥ 2η ϵ (R t 1 ) 2 , we have (χ ∗ ) 2 < υ and (χ ∗ ) −2 + (υ − (χ ∗ ) 2 ) −1 ≥ η ϵ (R t 1 ), hence the requirements of Lemma 22 are satisfied.

Lemma 24. Let R, m, Q, q, m c , K, t 1 , t 2 , χ̂, χ, γ, D t be parametrised by λ, where D t is a distribution over R m q . Denote

par = (R, m, Q, q, m c , K, t 1 , t 2 , χ, γ, D t ),

par E = (R, m, Q, q, t 1 , K, χ̂, χ, γ, D t ).

Consider the experiment Exp1 b par,A defined in Theorem 4 and the advantage Adv Exp1 par,A defined in Eq. (33), and let Exp denote the experiment of Lemma 23 with parameters par E . For any PPT A, there exists a PPT B such that Exp Adv Exp1 par,A (λ) = Adv par E ,B (λ).

Proof. Given a PPT A distinguishing Exp1 0 and Exp1 1 , we construct a PPT B distinguishing Exp 0 and Exp 1 in Lemma 23, as follows:

– Receive from A(1 λ ) the matrices (M = (M 1 , M 2 ), S 2 ), and assert ∥M 1 ∥ 2,2 ≤ γ. – Send Z := M T 1 ∈ R t 1 ×K to the Exp challenger. – Sample S 1,c ← $ R t q 1 ×m c . – Maintain a list L Query . Answer A’s oracle queries as follows: • TagO(): forward the query to the tag oracle of Exp, obtain (i, t i ), and answer with (i, t i ).

We abuse notation slightly, because Θ · Γ · ψ(l i ) may not lie in the image of ψ. This is not an issue, as we only operate on ψ(c).

<!-- page 58 -->

c , t i

• O b (c, i): if L Query [i] = ∅, query the leak oracle leakO b (i) of Exp to obtain (b i , l i ), set x :=

compute

d := M 1 · (S 1,c · c) + M 1 · b i − l i + M 2 · (S 2 · x) mod q,

and set L Query [i] := d. Answer with d ← L Query [i]. – Eventually receive a bit b ′ from A, return b ′ .

Below we show that B perfectly simulates the view of either Exp1 0 or Exp1 1 to A, if it interacts respectively with Exp 0 or Exp 1 , thus the lemma follows.

If B interacts with Exp 0 : By Lemma 23, for each fresh index i the leak oracle returns

b i = S · t i + ē i mod q,

l i = M 1 · ē i + e i ,

t 1 K where S ← $ R t q 1 ×m is the fixed secret of Exp, ē i ← $ D R, χ̂ , e i ← $ D R,χ , and we used Z = M 1 . Substituting,

d = M 1 · S 1,c · c + M 1 · (S · t i + ē i ) − (M 1 · ē i + e i ) + M 2 · S 2 · x

= M 1 · (S 1,c · c + S · t i ) − e i + M 2 · S 2 · x S = M 1 · S 1 · x − e i + M 2 · S 2 · x ≡ M · 1 · x + e i mod q, S 2

t ×(m +m)

c where S 1 := (S 1,c , S) ∈ R q 1 , so that S 1 · x = S 1,c · c + S · t i mod q, and the last ≡ holds since the discrete Gaussian over R is symmetric around zero. Since S 1,c and S are both uniform, S 1 is uniform t ×(m c +m) over R q 1 , exactly as in Exp1 0 . Thus d is distributed identically to the oracle answer in Exp1 0 , and B perfectly simulates Exp1 0 .

If B interacts with Exp 1 : In this case, b i ← $ R t q 1 is uniform and independent, while l i = M 1 ē i + e i as before. Substituting,

d = M 1 · S 1,c · c + M 1 · b i − (M 1 · ē i + e i ) + M 2 · S 2 · x

= M 1 · (S 1,c · c + b i − ē i ) − e i + M 2 · S 2 · x w = M 1 · w − e i + M 2 · S 2 · x ≡ M · + e i mod q, S 2 · x

where w := S 1,c c + b i − ē i mod q. Since b i is uniformly random and independent across queries, so is w, identically distributed as the freshly sampled w in Exp1 1 . Thus d is distributed identically to the oracle answer in Exp1 1 , and B perfectly simulates Exp1 1 .

Norm bound and query count: The matrix Z = M T 1 sent by B to the Exp challenger is admissible, because

Z T 2,2 = ∥M 1 ∥ 2,2 ≤ γ.

B simply forwards each TagO query, and it queries leakO exactly once per fresh index i, hence at most Q times by the assertion |L Query | < Q in O b of Exp b .

G.4

Theorem 5 and proofs

Theorem 5. Let R, n, m, Q, q, K, t, t 2 , ϵ, χ̄, χ, χ ∗ , γ, β, D A be parametrised by λ, where R = Z[ζ] has ring degree φ and field expansion factor c 2 w.r.t. the √ coefficient ℓ 2 -norm, n, m, Q, K, t, t 2 ∈ poly(λ), D A is a distribution over R n×m , 0 < ϵ ≤ 1/2 and χ ∗ ≥ 2 · η ϵ (R m ). Denote by u T := (1, 0, . . . , 0) ∈ R 1×t the first unit vector, and

par = (R, n, m, Q, q, K, t, t 2 , χ̄, χ, γ, β, D A ), par LWE = (R, n, m, q, χ ∗ , D A ). ⊗ Let c ⊗ t otherwise. Suppose that γ · φm · β ≥ 1 and t := 1 if f is a power of two and c t := 2QK · φm · c 2 · c ⊗ (2η ϵ (R m ) 2 + (χ ∗ ) 2 ) −1 − χ̄ −2 . t · γ · β ≤ χ ·

For any PPT A, define the following experiment Exp2 b par,A :

<!-- page 59 -->

Exp2 b par,A (1 λ )

i := 0

A ← $ D A

K×(t+t 2 )

M = (M 1 , M 2 ) ∈ R

← A(A)

assert ∥M 1 ∥ 2,2 ≤ γ

S 2 ← $ R t q 2 ×n ; ē ← $ D R, χ̄

if b = 0 then

S 1 ← $ R t×n

b T := u T S 1 A + ē T mod q

if b = 1 then

S̄ 1 ← $ R t×m

b T := u T S̄ 1 + ē T mod q

b ′ ← A O b (A, b, S 2 )

return b ′

O b (x ∈ R m )

assert i < Q

i := i + 1

assert ∥x∥ ∞ ≤ β

K e ← $ D R,χ

S 1 A x + e mod q S 2 A S̄ 1 if b = 1 then d := M · x + e mod q S 2 A

if b = 0 then d := M ·

return d

and denote the advantage of A in distinguishing the above experiments by λ λ Adv Exp2 par,A := Pr Exp2 par,A (1 ) = 1 − Pr Exp2 par,A (1 ) = 1 .

∀ PPT A, ∃ PPT B such that

LWE Adv Exp2 par,A (λ) ≤ t · Adv par LWE ,B (λ) + 4 · QK · ϵ + 6 · ϵ/(1 − ϵ) .

In particular, if QK ∈ poly(λ), ϵ ∈ negl(λ) and the LWE par LWE assumption holds, then the experiments Exp2 0 par,A and Exp2 1 par,A are computationally indistinguishable.

Proof. Follows from putting Corollary 2 and Lemmas 25 to 27 together. In particular:

– By Corollary 2, invoked with the query bound QK and with its leakage parameter α instantiated as ⊗ c ⊗ t ·γ· φm·β, so that its leakage set is L = {z ∈ R : ∥z∥ 2 ≤ c t ·γ· φm·β}, the LWE par LWE assumption implies AdpLLWE with par ∗ = (R, n, m, QK, q, χ̄, χ, L, D A ), at an additive loss √ of 4 · QK · ϵ + 6 · ϵ/(1 − ϵ). ∗ Its requirements hold: α ≥ 1 follows from γ · φm · β ≥ 1 as c ⊗ 2 · η ϵ (R m ) is assumed, t ≥ 1, χ ≥ and Eq. (36) is Eq. (31) with α instantiated and with Q replaced by QK, which suffices by Remark 9. – By Lemma 25, AdpLLWE with par ∗ implies AdpLLWE with par † = (R, nt, mt, QK, q, χ̄, χ, L † , I t ⊗ D A ), where L † = {z ∈ R mt : ∥z∥ 2 ≤ c ⊗ t · γ · φm · β} is the leakage set of Lemma 26, at a loss of a factor t. – By Lemma 26, AdpLLWE with par † implies the indistinguishability of the experiments Exp3 0 and Exp3 1 defined therein, and by Lemma 27 the latter implies the claimed indistinguishability. Both steps are tight.

Putting the advantage bounds in the above lemmas together yields the stated bound.

Lemma 25 below is a standard hybrid argument, reducing adaptive leaky LWE for matrix A to that for matrix I ⊗ A. It is a direct adaption of [CLW25, Proposition 1, Eprint].

Lemma 25. Let R, n, m, Q, q, χ̄, χ, D A be parametrised by λ, where D A is a distribution over R n×m . Let t ∈ poly(λ), L = {z ∈ R m : ∥z∥ 2 ≤ α} and L † = {z ∈ R mt : ∥z∥ 2 ≤ α} for some α > 0. Let

par ∗ = (R, n, m, Q, q, χ̄, χ, L, D A ),

For any PPT A, there exists a PPT B such that

par † = (R, nt, mt, Q, q, χ̄, χ, L † , I t ⊗ D A ).

Adv AdpLLWE (λ) ≤ t · Adv AdpLLWE par ∗ ,B (λ). par † ,A

In particular, if the AdpLLWE par ∗ assumption holds, then the AdpLLWE par † assumption holds.

Proof. For each i ∈ {0, 1, . . . , t}, define the following i-th hybrid experiment:

<!-- page 60 -->

Exp i (1 λ )

A ← D A ; j := 0

for k ∈ [t] do ē k ← $ D R, χ̄

for k ∈ [1, . . . , i] do b k ← $ R m

O(z)

assert j < Q

j := j + 1

assert z ∈ L †   z 1   parse  ...  ← z

for k ∈ [i + 1, . . . , t] do r k ← $ R n q ; b k := r k A + ē k mod q

b T := (b T 1 , . . . , b T t ); ē T := (ē T 1 , . . . , ē T t )

return A O (A, b)

// z k ∈ R m ∀k ∈ [t]

z t

X

ē T k · z k + e

e ← $ D R,χ ; ℓ :=

k∈[t]

return ℓ

It is direct to verify that the 0-th hybrid is identical to the AdpLLWE par † experiment 0, as

b T = (r T 1 A + ē T 1 , . . . , r T t A + ē T t ) = (r T 1 , . . . , r T t )(I t ⊗ A) + ē T mod q,

and each oracle answer is

X

ē T k · z k + e = ē T · z + e.

ℓ =

k∈[t]

Also, the t-th hybrid is identical to the AdpLLWE par † experiment 1. In the rest we show the (i − 1)-th and i-th hybrids are computationally indistinguishable under the AdpLLWE par ∗ assumption, for each i ∈ [t]. Fix any i ∈ [t]. Given any PPT A against distinguishing the (i − 1)-th and i-th hybrids, we construct a PPT B against AdpLLWE par ∗ . Let B proceed as follows:

– Receive (A, b i ) from the AdpLLWE par ∗ challenger. – For each k ∈ [1, . . . , t] \ {i}, sample ē k ← $ D R, χ̄ . – For each k ∈ [1, . . . , i − 1], sample random b k ← $ R m q . – For each k ∈ [i + 1, . . . , t], sample random r k ← $ R nq , set b T k := r T k A + ē T k mod q. – Set b T := (b T 1 , . . . , b T t ). Send (A, b) to A. – Internally maintain a counter j := 0. For each oracle query O(z) made by A, do the following: • Assert j < Q and set  j :=  j + 1. z 1  ..  † • Assert z ∈ L . Parse  .  ← z.

z t • For each k ∈ [1, . . . , t] \ {i}, let ℓ k := ē T k · z k . • Send z i to the oracle P LeakO available from the AdpLLWE par ∗ challenger, receive from which ℓ i . • Answer with ℓ := k∈[t] ℓ k . – Eventually receive a bit b ′ from A. Return b ′ .

It is direct to see that B perfectly simulates the view of the (i−1)-th and the i-th hybrid to A, if it interacts with the AdpLLWE par ∗ experiment 0 and 1, respectively. In particular, in either case, ℓ i = ē T i · z i + e for error e ← $ D R,χ , hence the simulated oracle answer is X X ℓ = ℓ k = ē T k · z k + e.

k∈[t]

k∈[t]

The vector z i sent from B to the AdpLLWE par ∗ challenger is admissible, i.e. z i ∈ L, since z ∈ L † implies ∥z∥ 2 ≤ α, and we have ∥z i ∥ 2 ≤ ∥z∥ 2 ≤ α.

Lemma 26 below restates AdpLLWE w.r.t. I ⊗ A in the matrix form used in the sequel, in which the secret is a matrix and the leakage on the error matrix is a noisy bilinear form.

Lemma 26. Let R, n, m, Q, q, K, t, χ̄, χ, γ, β, D A be parametrised by λ, where R = Z[ζ] has conductor f and ring degree φ, n, m, Q, K, t ∈ poly(λ) and D A is a distribution over R n×m . Denote

α := c ⊗ t · γ ·

φm · β,

<!-- page 61 -->

par E = (R, n, m, Q, q, K, t, χ̄, χ, γ, β, D A ), par † = (R, nt, mt, QK, q, χ̄, χ, L † , I t ⊗ D A ), ⊗ where c ⊗ t otherwise, and L † = {z ∈ R mt : ∥z∥ 2 ≤ α}. For any t := 1 if f is a power of two and c t := b PPT A, define the following experiment Exp3 par E ,A :

Exp3 b par E ,A (1 λ )

i := 0

t×m Ē ← $ D R, χ̄

A ← $ D A ;

if b = 0 then

S ← $ R t×n ;

B := SA + Ē mod q

if b = 1 then

B ← $ R t×m

LeakO

return A

(A, B)

LeakO(Y ∈ R K×t , x ∈ R m )

assert i < Q

i := i + 1

assert ∥Y∥ 2,2 ≤ γ ∧ ∥x∥ ∞ ≤ β

K e ← $ D R,χ

l := YĒx + e mod q

return l

and denote the advantage of A in distinguishing the above experiments by h i h i λ λ Adv Exp3 par E ,A := Pr Exp3 par E ,A (1 ) = 1 − Pr Exp3 par E ,A (1 ) = 1 .

For any PPT A, there exists a PPT B such that

AdpLLWE Adv Exp3 (λ). par E ,A (λ) = Adv par † ,B

In particular, if the AdpLLWE par † assumption holds, then the experiments Exp3 0 par E ,A and Exp3 1 par E ,A are computationally indistinguishable.

Proof. Given a PPT A distinguishing Exp3 0 and Exp3 1 , we construct a PPT B against AdpLLWE par † , as follows:

× R mt from the AdpLLWE challenger. Parse b̄ T = ( b̄ T 1 , . . . , b̄ T t ) with – Receive (I t ⊗ A, b̄) ∈ R nt×mt t×m b̄ j ∈ R q for j ∈ [t], set B ∈ R q to be the matrix whose j-th row is b̄ T j , and pass (A, B) to A. – For each query (Y, x) made by A: • Assert i < Q and set i := i + 1. Assert ∥Y∥ 2,2 ≤ γ and ∥x∥ ∞ ≤ β. • Let y k T denote the k-th row of Y and z k := y k ⊗ x ∈ R mt , i.e. z k consists of t blocks of length m, the j-th being y k,j · x. • For each k ∈ [K], query the oracle LeakO(z k ) available from the AdpLLWE challenger, and receive an answer ℓ k . Answer A with l := (ℓ 1 , . . . , ℓ K ) T . – Eventually receive b ′ from A, return b ′ .

Write ē T = (ē T 1 , . . . , ē T t ), where each ē j ∈ R m , for the error of LWE samples in the AdpLLWE experiment, and let Ē ∈ R t×m be the matrix whose j-th row is ē T j . In the AdpLLWE experiment 0, we have b̄ T = r T (I t ⊗ A) + ē T mod q for a uniform r ← $ R nt q . Writing r = (r T 1 , . . . , r T t ) where each r j ∈ R nq , then we have

b̄ T j = r T j A + ē T j mod q ∀j ∈ [t],

B = SA + Ē mod q

equivalently

where S ∈ R t×n is uniform, whose j-th row is r T j . In the AdpLLWE experiment 1, the matrix B is uniform. t×m In either case, Ē ← $ D R, χ̄ , as in Exp3. For an oracle query (Y, x), the answer is l = (ℓ 1 , . . . , ℓ K ) T where, for each k ∈ [K], X X ℓ k = ē T · z k + e k = ē T j · (y k,j · x) + e k = y k,j · (ē T j x) + e k = y k T Ēx + e k ,

j∈[t]

j∈[t]

with e k ← $ D R,χ . Vertically concatenating, we have l = YĒx + e as in Exp3. Hence, B perfectly simulates Exp3 0 , resp. Exp3 1 , when interacting with the AdpLLWE experiment 0, resp. experiment 1. Note that the K answers ℓ 1 , . . . , ℓ K have independent errors even if Y has two equal rows, since LeakO in Fig. 4 samples a fresh error on every query.

<!-- page 62 -->

Query count: B makes K queries to LeakO per query of A, hence at most QK in total by the assertion i < Q in LeakO of Exp3 b .

Norm bound: It remains to check that the queries of B satisfies the norm bound constraint. For each k ∈ [K], the entries of z k are y k,j · x i for (j, i) ∈ [t] × [m]. Regrouping them by the columns of Y, and writing u j ∈ R t for the j-th unit vector, X X X X X ∥z k ∥ 2 = ∥Y · (x i · u j )∥ 2 ≤ ∥Y∥ 2,2 · ∥x i ∥ 2 = t · ∥Y∥ 2,2 · ∥x∥ 2 ,

i∈[m] j∈[t]

k∈[K]

hence, for every k ∈ [K],

∥z k ∥ 2 ≤

i∈[m] j∈[t]

t · ∥Y∥ 2,2 · ∥x∥ 2 ≤ t · γ · φm · ∥x∥ ∞ ≤ t · γ · φm · β.

If f is a power of two, the factor t in the above bound can be dropped, as follows. The idea is to measure z k in the canonical embedding, where the product of two field elements has multiplicative norm, and then to relate the resulting bound back to ∥Y∥ 2,2 . We use the following three facts.

(i) Extend each canonical embedding σ ι of K (Section 3) entrywise to vectors and matrices over K (so that e.g. σ ι (Y) ∈ C K×t ). Since σ ι is a ring homomorphism, σ ι (Mv) = σ ι (M) · σ ι (v) and σ ι (a ⊗ w) = σ ι (a) ⊗ σ ι (w) for any matrix M and vectors v, a, w over K of compatible dimensions. (ii) As f is a power of two, σ is a scaled ℓ 2 -isometry, ∥σ(w)∥ 2 = φ · ∥w∥ 2 for any w ∈ K (Section 3), P hence ∥v∥ 2 = φ 1 ι ∥σ ι (v)∥ 2 for any vector v over K. (iii) By Lemma 2, max ι ∥σ ι (M)∥ 2,2 = ∥M∥ 2,2 for any matrix M over K.

Given these facts, for each k ∈ [K],

1 X ∥σ ι (z k )∥ 2 // by (ii) φ ι 1 X = ∥σ ι (y k )∥ 2 · ∥σ ι (x)∥ 2 // by (i) and ∥a ⊗ w∥ 2 = ∥a∥ 2 · ∥w∥ 2 φ ι 1 X ∥σ ι (x)∥ 2 ≤ max ∥σ ι (Y)∥ 2,2 · ι φ ι

∥z k ∥ 2 =

= max ∥σ ι (Y)∥ 2,2 · ∥x∥ 2

ι

≤ ∥Y∥ 2,2 · ∥x∥ 2

// by (iii)

// by (ii)

where the first inequality holds because σ ι (y k ) T is the k-th row of σ ι (Y) and the ℓ 2 -norm of a row of a complex matrix is at most its ℓ 2 -induced norm. Taking square roots and using ∥Y∥ 2,2 ≤ γ and ∥x∥ 2 ≤ φm · β as before yields ∥z k ∥ 2 ≤ ∥Y∥ 2,2 · ∥x∥ 2 ≤ γ · φm · β, i.e. the bound of the general case but without the factor t.

Lemma 27 below gives a reduction from Exp3 to the distinguishing problem defined in Theorem 5.

Lemma 27. Let R, n, m, Q, q, K, t, t 2 , χ̄, χ, γ, β, D A be parametrised by λ, where D A is a distribution over R n×m . Denote

par = (R, n, m, Q, q, K, t, t 2 , χ̄, χ, γ, β, D A ),

par E = (R, n, m, Q, q, K, t, χ̄, χ, γ, β, D A ).

Consider the experiment Exp2 b par,A defined in Theorem 5 and the advantage Adv Exp2 par,A defined in Eq. (37), and let Exp3 denote the experiment of Lemma 26 with parameters par E . For any PPT A, there exists a PPT B such that Exp3 Adv Exp2 par,A (λ) = Adv par E ,B (λ).

<!-- page 63 -->

Proof. Given a PPT A distinguishing Exp2 0 and Exp2 1 , we construct a PPT B distinguishing Exp3 0 and Exp3 1 , as follows:

– Receive (A, B) ∈ R n×m × R t×m from the Exp3 challenger. – Pass A to A, and receive from which M = (M 1 , M 2 ) ∈ R K×(t+t 2 ) . Assert ∥M 1 ∥ 2,2 ≤ γ. – Sample S 2 ← $ R t q 2 ×n , set b T := u T B mod q where u T := (1, 0, . . . , 0) ∈ R 1×t is the first unit vector, and pass (A, b, S 2 ) to A. – Maintain a counter i := 0. Answer each oracle query O b (x) of A as follows: assert i < Q, set i := i + 1, and assert ∥x∥ ∞ ≤ β. Then query LeakO(M 1 , x) of Exp3 to obtain l, compute

d := M 1 · Bx − l + M 2 · S 2 Ax mod q,

and answer with d. – Eventually receive a bit b ′ from A, return b ′ .

Below we show that B perfectly simulates the view of either Exp2 0 or Exp2 1 to A, if it interacts respectively with Exp3 0 or Exp3 1 , thus the lemma follows. t×m In both cases, write W := B − Ē mod q for the error matrix Ē ← $ D R, χ̄ of Exp3, and ē := u Ē for its first row, which follows D R,χ̄ . By definition of the LeakO answer in Exp3, we have l = M 1 · Ēx + e for K a fresh e ← $ D R,χ , hence for each query x the simulated oracle answer is

d = M 1 · Bx − (M 1 · Ēx + e) + M 2 · S 2 Ax W = M 1 · Wx − e + M 2 · S 2 Ax ≡ M · x + e mod q, S 2 A

where the last ≡ holds since the discrete Gaussian over R is symmetric around zero. Moreover, the vector simulated to A is b T = u T B = u T W + ē T mod q. It remains to identify W in the two cases.

If B interacts with Exp3 0 : Here B = SA+ Ē for a uniform S ← $ R t×n , so W = SA. Thus b T = u T SA+ ē T SA and d ≡ M · x + e, which is the view of Exp2 0 with S 1 := S. S 2 A

If B interacts with Exp3 1 : Here B ← $ R t×m is uniform and independent of Ē, so W = B − Ē is uniform W over R t×m and independent of Ē. Thus b = u W + ē and d ≡ M · x + e, which is the view of S 2 A Exp2 1 with S̄ 1 := W.

Norm bound and query count: The tuple (M 1 , x) sent by B to the Exp3 challenger is admissible, since ∥M 1 ∥ 2,2 ≤ γ and ∥x∥ ∞ ≤ β are exactly the assertions of Exp2 b . Finally, B queries LeakO exactly once per query of A, hence at most Q times by the assertion i < Q in O b of Exp2 b .