--- title: "Amortized Bootstrapping Revisited: Simpler, Asymptotically-faster, Implemented" authors: "Antonio Guimarães, Hilder V. L. Pereira, Barry van Leeuwen" venue: "Advances in Cryptology – ASIACRYPT 2023, Guangzhou" source: "IACR ePrint 2023/014 (author copy)" source_version: 2023-11-23 canonical: https://antonioguimaraes.org/publications/amortized-bootstrapping-revisited/ pdf: https://eprint.iacr.org/2023/014.pdf generator: scripts/fulltext.py (pdftotext) --- # Amortized Bootstrapping Revisited: Simpler, Asymptotically-faster, Implemented *Antonio Guimarães, Hilder V. L. Pereira, Barry van Leeuwen*. Advances in Cryptology – ASIACRYPT 2023, Guangzhou. > 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://eprint.iacr.org/2023/014.pdf Amortized bootstrapping revisited: Simpler, asymptotically-faster, implemented Antonio Guimarães 1 , Hilder V. L. Pereira 1 , and Barry van Leeuwen 2 Institute of Computing – University of Campinas, Brazil ⋆ ⋆ ⋆ , COSIC, KU Leuven, Leuven, Belgium. † Abstract. Micciancio and Sorrel (ICALP 2018) proposed a bootstrapping algorithm that can refresh many messages at once with sublinearly many homomorphic operations per message. However, despite the attractive asymptotic cost, it is unclear if their algorithm could ever be practical, which reduces the impact of their results. In this work, we follow their general framework, but propose an amortized bootstrapping procedure that is conceptually simpler and asymptotically cheaper. We reduce the number of homomorphic multiplications per refreshed message from O(3 ρ · n 1/ρ · log n) to O(ρ · n 1/ρ ), and the noise e 2+3·ρ ) to O(n e 1+ρ ), where n is the security level and ρ ≥ 1 is a free parameter. We overhead from O(n also make it more general, by handling non-binary messages and applying programmable bootstrapping. To obtain a concrete instantiation of our bootstrapping algorithm, we describe a double-CRT (aka RNS) version of the GSW scheme, including a new operation, called shrinking, used to speed-up homomorphic operations by reducing the dimension and ciphertext modulus of the ciphertexts. We also provide a C++ implementation of our algorithm, thus showing for the first time the practicability of the amortized bootstrapping. Moreover, it is competitive with existing bootstrapping algorithms, being even around 3.4 times faster than an equivalent non-amortized version of our bootstrapping. Introduction Since the introduction of the first Fully Homomorphic Encryption (FHE) scheme, by Gentry [16], there has been a quest to improve the efficiency and the security of FHE. The main efficiency bottleneck of any FHE scheme is the bootstrapping operation that refreshes the ciphertexts after being involved in a few homomorphic operations, allowing us to perform further operations on them. Hence, most works aiming to make FHE more efficient direct their efforts towards designing faster bootstrapping. For this goal, there are two main strategies: Heavy-packed bootstrapping tries to pack several messages into a “large” ciphertext. This makes bootstrapping complex and very costly, but refreshes several messages at once, with the aim for the amortized cost per message to be low. This type of bootstrapping was proposed for many schemes, [11,15,10,17], obtaining good amortized costs, however these schemes generally were not very efficient regarding noise management, thus, their bootstrapping algorithms often incur quasipolynomial noise growth. This implies that their security is based on worst-case lattice problems with superpolynomial approximation factors. Ideally, we would like to have FHE with assumptions identical to general lattice-based public-key encryption, which assumes worst-case lattice problems with polynomial approximation factors only. ⋆⋆⋆ This paper was mainly written while Hilder V. L. Pereira was in COSIC, KU Leuven. Please, notice that van Leeuwen is the family name of the third author, thus, instead of [GPL23], the correct acronym for citing this paper would be [GPV23] or maybe [GPvL23]. † Table 1: Comparison of number of homomorphic operations and noise growth of bootstrapping algorithms of different schemes based on worst-case lattice problems with polynomial approximation factor. The notation Õ hides polylogarithmic factors in n. Messages Scheme Total cost Õ(n) [14] O(n) [12] 1+1/ρ ρ Õ(3 · n ) O(n) [29] 1+1/ρ O(ρ · n ) O(n) This work Amortized cost Noise overhead Õ(n 1.5 ) Õ(n) O(n) Õ(n) 1/ρ Õ(n 2+3·ρ ) ρ Õ(3 · n ) 1/ρ Õ(n 1+ρ ) O(ρ · n ) On the other front, fast single message bootstrapping encrypts a single message into a “small” ciphertext, hugely simplifying the bootstrapping. The aim here is to execute it much faster, in many cases in a few milliseconds on a common commercial computer [14,12,32,8]. The downside now is the need for one bootstrapping per gate of the circuit being evaluated homomorphically and, since each bootstrapping refreshes a single message, the amortized cost is still high. However, this bootstrapping strategy does attain a polynomial noise overhead, achieving the ideal assumption base: worst-case lattice problems with polynomial approximation factors. Then, in [29], Micciancio and Sorrell try to obtain the advantages of these two approaches, by proposing a bootstrapping algorithm that follows the blueprint of [14], but packs several messages into a single ciphertext to amortize the cost of the bootstrapping. Therewith, they obtain the first FHE scheme whose security is based on the hardness of worst-case lattice problems with polynomial approximation factors that at the same time is bootstrappable with amortized sublinearly many homomorphic operations. Their main idea is to describe the bootstrapping as a polynomial multiplication, then to evaluate it homomorphically using some fast polynomial multiplication algorithm. Due to the limitations of the functions one can evaluate homomorphically, they cannot simply evaluate a Fast Fourier Transform, thus, they adapt the Nussbaumer Transform [31] to work over power-of-three cyclotomic rings, then use it in their algorithm to bootstrap O(n) messages in time Õ(3 ρ · n 1+1/ρ ), where ρ is a free parameter. Note that the Õ-notation hides polylogarithmic factors on n. Therefore, their amortized cost is only Õ(3 ρ · n 1/ρ ) homomorphic operations per message. Following the blueprint of [29], we propose a simpler and more efficient amortized bootstrapping. Our first contribution is to remove the Nussbaumer Transform, replacing it by a standard (homomorphic) Number Theoretic Transform (NTT). By doing so we make the whole bootstrapping algorithm more straightforward and gain important asymptotic factors decreasing the number of homomorphic operations per message from O(3 ρ · n 1/ρ · log n) to O(ρ · n 1/ρ ), and the noise introduced by the bootstrapping from Õ(n 2+3ρ ) to Õ(n 1+ρ ). Moreover, instead of just bits, we can handle n messages in Z t , for small t. This also means that we support programmable bootstrapping, reducing the noise and simultaneously applying any function f : Z t → Z t to the message. In Table 1, we present a comparison of our work with previous ones. Although [29] obtains a significant asymptotic improvement over previous works, it is unclear how (in)efficient it would be in practice, since the hidden constants are hard to estimate. Thus, as a second contribution, we present a concrete instantiation of our method. For this, we formalize a double-CRT (RNS) variant of the GSW scheme [18], including a new operation, called shrinking, that allows to efficiently reduce the ciphertext size, and thus, the cost of the homomorphic operations, as the noise grows. This also allows us to present a concrete cost analysis, in terms of polynomial multiplications (or NTTs), which gives us a much better idea of the practical cost of the amortized bootstrapping and makes it easier to compare with other works, since the number of times that the NTT is executed is already used to estimate the cost of several previous schemes, such as [14,12,8]. Finally, we also implemented our bootstrapping in C++ and made it publicly available, 3 thus, presenting the first implementation of amortized and providing baseline running times and memory usage for this type of bootstrapping, showing that such a scheme is feasible in practice with running times comparable to some existing schemes. Overview of the amortized bootstrapping from [29] The bootstrapping strategy of [3], improved and made practical in [14], works as follows: the whole FHE scheme is organized in two layers, each one composed by one homomorphic scheme. The base scheme is an LWE-based scheme that can perform very limited number of homomorphic operations, then has to be bootstrapped. Then the second scheme, called the accumulator, is used to evaluate the decryption of the base scheme homomorphically, i.e., to bootstrap it. For the accumulator, one uses the GSW scheme [18] instantiated with the RLWE problem, so that it can encrypt polynomials. Because of the slow noise growth of GSW, the noise overhead of the bootstrapping is just polynomial in the security parameter. Essentially, to decrypt an LWE ciphertext c, one has to multiply it by the secret key s. Thus, starting with GSW encryptions of powers of X with the key in the Q n secret c i ·s s i exponent, i.e., X , the GSW homomorphic multiplications are used to compute i=0 X i = X c·s . Finally, there is an extraction procedure that maps this power of X to the message encrypted by c. Notice that the bootstrapping costs Õ(n) homomorphic operations, more specifically, GSW multiplications. The main idea of [29] is to combine O(n) LWE ciphertexts into one single RLWE ciphertext c ∈ R 2 encrypting O(n) messages. Then, because the secret is a polynomial s instead of a vector, decrypting c now boils down to performing a polynomial multiplication on R, which can be done in time O(n · log n) via standard techniques, such as the Fast Fourier Transform (FFT). Thus, if one could use the accumulator to evaluate an FFT, the amortized cost of such bootstrapping would be only O(log n) homomorphic operations per message. However, due to limitations in the noise growth of this bootstrapping strategy, it is not possible to evaluate all the O(log n) recursive levels of the FFT. Thus, [29] sets the recursion level as a parameter ρ. Moreover, since the GSW scheme is instantiated over the ring R := Z[X]/⟨X N +1⟩ and working only with powers of X, whose order is 2N in R, there is a limited set linear operations over Z 2N available as homomorphic operations. So, for example, we cannot take an encryption of (X to the power of) m and produce an encryption of −m or of m −1 . Therefore, [29] cannot evaluate an FFT. To overcome this limitation, they pack the LWE ciphertexts into an RLWE ciphertext defined over a power-of-three cyclotomic ring, i.e., defined modulo Φ 3 k (X) = 2 · 3 k−1 + 3 k−1 + 1, and adapt the Nussbaumer transform to replace the FFT and perform polynomial multiplications modulo Φ 3 k (X). The radix-r Nussbaumer transform works as the FFT, by dividing the input by r in each recursive level. However, in their adapted algorithm, there is an expansion by 3, i.e., they obtain r inputs of length 3n/r instead of length n/r. Since this expansion happens in all recursive levels, the factor 3 accumulates exponentially and, at the end, their bootstrapping costs Õ(3 ρ · n 1+1/ρ ) homomorphic operations and the noise introduced by the bootstrapping is Õ(n 2+3·ρ ). GitHub repository: https://github.com/antoniocgj/Amortized-Bootstrapping Overview of our contributions and techniques Simpler and more efficient amortized bootstrapping Micciancio and Sorrell accepted that the accumulator constructed with GSW just provides a limited set of operations over Z 2N , where N is a power of two, and tried to adapt the fast polynomial multiplication algorithms to work with that instruction set. We diverge from this by trying to adapt the accumulator to the algorithm we want to evaluate, instead of vice versa. As the Number Theoretic Transform (NTT) is the algorithm of choice to perform multiplications modulo X N + 1 our goal is to obtain an accumulator that can evaluate NTTs. To obtain that, we use the results from [7] to instantiate the GSW scheme modulo X p − 1, where p is a prime number, but with security based on the RLWE problem. This gives us an equivalent instruction set of [29], but over Z p . Then, we set p ≡ 1 (mod 2N ), so that we have a 2N -root of unity in Z p and the NTT of dimension N is well-defined. Then, we extend recent results about using automorphisms on bootstrapping algorithms [7,24] to the GSW scheme, which expands the instruction set of our accumulator. In Table 2, we compare both accumulators. Putting it all together we obtain a GSW-based accumulator that allows us to homomorphically evaluate a standard NTT. The only limitation that remains is that the noise overhead of the bootstrapping is still exponential in the number of recursive levels of the NTT, hence restricting to ρ recursive levels as in [29], guarantees that the noise overhead remains polynomial in N . With a more powerful accumulator, the bootstrapping algorithm becomes much simpler, as its main step is essentially the same as a well-known NTT. Moreover, there is no longer the expansion by 3 within the recursions, which allows us to save a factor of 3 ρ in the time complexity and to reduce the noise overhead from Õ(n 2+3·ρ ) to Õ(n 1+ρ ). Additionally, our accumulator also allows us to replace the algorithm used in [29] to perform the entry-wise vector multiplication in the FFT domain, called SlowMult, by a cheaper and simpler procedure, which yields an additional gain of a log n factor. Therefore, we reduce the number of homomorphic operations from O(3 ρ · n 1+1/ρ · log n) in [29] to O(ρ · n 1+1/ρ ). In Figure 1, we present the main steps of our bootstrapping. [m 1 ] X m 1 +e 1 [f 1 (m 1 )] Homomorphic inverse NTT .. . .. . Packing i P m i · X [m n ] High noise .. . .. . .. . Message .. extraction . .. . m n +e n [f n (m n )] X Low noise Fig. 1: Main building blocks of our amortized bootstrapping. First we pack high-noise ciphertexts into a single ciphertext encrypting a polynomial with original messages as the coefficients. Then we evaluate the NTT homomorphically, obtaining encryptions of powers of X having the messages plus restricted noise in the exponent. Finally, we execute a message extraction procedure, removing the noise terms and applying any set of desired functions to the messages. Table 2: Comparison of the accumulator proposed in [29] and ours. The notation [a] means encryption of (X to the power of ) a. Negation is not natively supported by [29], thus, for any message m, they actually encrypt (m, −m), which requires two ciphertexts. Negation is then implemented by swapping the ciphertexts so that they encrypt (−m, m). However this doubles the memory and time of all their operations. Variable Size of enc. type message Available operations Key [a], [b] 7→ [a + b] [a] 7→ [−a] [a], w 7→ [a · w] switch- Shrinking ing ## 2 GSW ciphertexts * [29] Z 2 k ## 1 GSW Z p , cipherprime p text Ours Double-CRT version of GSW FHE schemes implementing single-message bootstrapping, such as [14,12,8], can use very small parameters when compared to other FHE schemes thanks to the almost linear noise overhead of the bootstrapping. In particular, the ciphertext modulus, Q, is typically an integer between 2 32 and 2 64 . Since all homomorphic operations are defined modulo Q, these schemes can be implemented using native integer types of most CPUs. For other schemes the ciphertext modulus, Q, is much larger, normally with more than one thousand bits. Thus, implementing the operations modulo Q requires more care: one represents Q as a product of small primes q i ’s, e.g., with 32 bits, then uses the Chinese Remainder Theorem (CRT) to express operations modulo Q as independent operations modulo each q i , allowing the use of native integer types again. As all the polynomials composing ciphertexts are stored in the FFT domain and the FFT can be seen as a type of CRT, this representation is often called Double- CRT [21] or, alternatively, RNS representation [20]. Since the amortized bootstrapping has at least quadratic noise overhead, it also typically requires Q with more bits than native types of CPUs. Therefore, to obtain a practical implementation, we formally describe a double-CRT version of the accumulator, i.e. the GSW scheme 4 , including all common operations already existing for GSW, such as homomorphic multiplication and external product, and new operations, like Galois automorphisms and key switchings. One optimization that is commonly used for GSW is to ignore least significant bits of the ciphertexts during the multiplications, as they correspond to the noise of the RLWE samples, i.e., approximate deomposition in the TFHE scheme [12]. However, in the double-CRT representation, as there is no notion of least significant bits, this technique no longer applies. Thus, we propose a ciphertext shrinking, which introduces the implementation of approximate gadget decompositions over the double-CRT representation. It takes a GSW ciphertext, which is a 2d × 2 matrix where each entry is a polynomial modulo Q, and outputs another GSW ciphertext as a 2d ′ × 2 matrix and defined modulo Q ′ , where d ′ < d and Q ′ < Q, with basically the same relative noise. Reduc- A double-CRT version of GSW is implemented in the Lattigo library, but there is no formal description and analysis of the scheme. Moreover, it only includes external products. ing simultaneously d and Q enables a cubic performance improvement in all core homomorphic operations. We notice that any protocol or scheme that uses GSW can benefit from our new homomorphic operations, thus, this contribution is of independent interest. Thanks to this low-level description of the GSW scheme, we estimate the cost of our amortized bootstrapping concretely in terms of NTTs and integer (modular) multiplications. This simplifies the comparison with other bootstrapping strategies and also clarifies the practicability of the amortized bootstrapping. Proof-of-concept implementation in C++ We provide the first implementation of a bootstrapping algorithm for FHE based on the worst-case hardness of lattice problems and with polynomial approximation factors with amortized sublinearly many homomorphic operations. We show that our construction is practical, being up to 3.4 times faster than the non-packed approach we tested. Our source code is publicly available, since we believe that this can help the academic community to understand our techniques and also simplify comparisons in future works. We stress that the description of [29] is very high level and also that any implementation of their bootstrapping must be far from practical, even if our double-CRT GSW scheme is used, due to all the hidden constants in the asymptotic costs. Thus, one could reasonably wonder if the amortized bootstrapping would ever be practically feasible, and our algorithms together with our implementation provide a positive answer. Preliminaries For a 1 , ..., a k , m 1 , ..., m k ∈ Z, with m i ’s being pairwise coprime, let M = ki=1 m i and define CRT m 1 ,...,m k (a 1 , ..., a k ) as the unique a ∈ Z M such that a i = a mod m i . Also, for any a ∈ Z M , −1 define CRT m (a) = (a mod m 1 , ..., a mod m k ). For an element a(X) of any polynomial ring of 1 ,...,m k the form Z[X]/⟨f (X)⟩, we extend CRT and CRT −1 by applying it coefficient wise. For any vector u, we denote the infinity norm by ∥u∥ and the Euclidean norm by ∥u∥ 2 . For P any polynomial a = di=0 a i · X i , we define the norm of a as the norm of the coefficient vector (a 0 , ..., a d ). If a is an element of a polynomial ring like Z[X]/⟨f (X)⟩, we consider a ′ ∈ Z[X] as the unique canonical representation of a, and thus the norm of a is simply the norm of a ′ . Rings We use power-of-two cyclotomic rings of the form Z[X]/⟨X N + 1⟩, where N = 2 k for some k ∈ N, which we denote by R̂, and circulant rings of the form Z[X]/⟨X p − 1⟩, for some prime number p, which we denote by R̃. For any positive integer Q, we define R̂ Q := R̂/(Q R̂) and R̃ Q := R̃/(Q R̃), i.e., the same rings as before but with coefficients of the elements reduced modulo Q. Plain, ring and circulant LWE In the well-known learning with errors problem (LWE) [33] with parameters n, q, and σ, an attacker has to find a secret vector s ∈ Z n given many samples of the form (a i , b i ), where a i is uniformly sampled from Z nq and b i := a i · s + e i mod q, with e i following a discrete Gaussian distribution with parameter σ. The ring version of LWE, known as RLWE [27], is used to obtain more efficient cryptographic schemes, since it typically allows us to encrypt larger messages when compared to similar schemes instantiated with LWE. In the RLWE we fix the ring R = Z[X]/⟨Φ m (X)⟩, where Φ m (X) is the m-th cyclotomic ring, and we are given samples of the form (a i , b i ), where a i is uniformly sampled from R q and b i := a i · s + e i mod q, for some small noise term e i , and we have to find the secret polynomial s. Most schemes are constructed on top of the RLWE problem with a power-of-two cyclotomic polynomial, Φ 2N (X) = X N + 1, where N = 2 k for some k ∈ N ∗ . In this work, we also use a variant of the LWE called circulant-LWE (CLWE), which was introduced in [7] and was proved to be as hard as the RLWE on prime-order cyclotomic polynomials. Hence, we restrict ourselves to prime p. Instead of using the ring R = Z[X]/⟨Φ p (X)⟩ we use the “circulant ring” R̃ = Z[X]/⟨X p − 1⟩. Then CLWE samples are obtained essentially by projecting RLWE samples from R to R̃. This is done by fixing some integer Q prime with p and by defining the map L Q : R Q → R̃ Q as p−1 X p−1 X −1 i i a i · X 7→ a i · X − p ## L Q : p−1 X p−1 X ! X i mod Q · · a i Finally, given an RLWE sample (a ′ , b ′ = a ′ · s ′ + e ′ ) ∈ R 2 Q , we define the corresponding CLWE sample as (a, b) := (L Q (a ′ ), L Q ((1 − X) · b ′ )) ∈ R̃ 2 Q . Thanks to the homomorphic properties of L Q , we have b = a · s + e mod Q, where e = L Q ((1 − X) · e ′ ) is a small noise term and s = L Q ((1 − X) · s ′ ) is the CLWE secret. Then, using the CLWE problem, the GSW instantiated over the circulant ring R̃ is CPA-secure if the message space is restricted to powers of X, that is, if one just encrypts X k ∈ R̃ for k ∈ Z [7]. In Section 3.5, we extend the results [7] so that we can also encrypt non-powers of X (under some conditions), as this is needed in our bootstrapping algorithm, especially, to use Galois automorphisms on GSW ciphertexts. Subgaussian distributions and independence heuristic A random variable X is subgaussian with parameter σ > 0, in short σ-subgaussian, if for all t ∈ R it holds that E[exp(2πtX)] ≤ exp(πσ 2 t 2 ). If X is σ-subgaussian, then ∀t ∈ R, Pr[|X| ≥ t] ≤ 2 exp(−πt 2 /σ 2 ). This allows p one to bound the absolute value of X with overwhelming probability. Namely, by setting t = σ λ/π, p p −λ we see that Pr[|X| ≥ σ λ/π] ≤ 2 exp(−π(s λ/π) /s ) = 2 exp(−λ) < 2 . Linear combinations of independently distributed subgaussians are again subgaussians, i.e., given independent P n n , it holds that Y := σ i -subgaussian distributions X ’s, then for any c = (c , ..., c ) ∈ R i n i=1 c i X i q P n 2 2 is i=1 c i σ i -subgaussian. We say that a polynomial a is σ-subgaussian if its coefficients are independent σ i -subgaussian, with σ i ≤ σ. For any n ∈ N ∗ , given f equal to X n ±1 and a, b ∈ Z[X]/⟨f ⟩ following subgaussians with parameters σ a and σ b , we assume the independence heuristic, i.e. the coefficients of the noise terms of the LWE, RLWE, and CLWE samples appearing in the linear combinations we consider are independent and concentrated, to say that a·b is ( n · σ a · σ b )-subgaussian. Double-CRT (RNS) representation for polynomial arithmetic Homomorphic operations of commonly used FHE schemes are composed of some operations over polynomial rings R Q = Z Q [X]/⟨f (X)⟩, where f (X) is a degree-N polynomial over Z Q [X]. Here, we suppose that f (X) = X N + 1 or f (X) = X N − 1. Because Q generally has much more than 64 bits, working with elements of R Q requires libraries that implement arbitrary precision integers, which is inefficient. To overcome this the residual number system (RNS), aka double-CRT, is typically used. It exploits the decomposition of Q to work with several polynomials modulo each q i , which then fit in the 32- or 64-bit native integer types of current processors. In more detail, because Q = ℓi=1 q i , by using the Chinese remainder theorem coefficient-wise we have ℓ Y R Q = Z Q [X]/⟨f (X)⟩ = Z q i [X]/⟨f (X)⟩ Thus, additions and multiplications over R Q can be implemented with ℓ independent operations over R q i . Moreover, since efficiently multiplying polynomials modulo f (X) requires fast Fourier transforms or number-theoretic transforms (NTT), one goes one step forward and represents elements of R q i in the “NTT form”, i.e., given a(X) ∈ R Q , one stores the matrix Mat(a) ∈ Z ℓ×N defined as row i (Mat(a)) := NTT q i (a(X)). Notice that we need to choose q i such that a suitable primitive root of unity ω i ∈ Z q i exists. So, given a(X) ∈ R Q , we store the matrix    NTT q i (a mod q i ) a 1,0 . . . a 1,N −1    .. . . .. ..  ∈ Z ℓ×N Mat(a) :=   =  . . . .   NTT q ℓ (a mod q ℓ ) a ℓ,0 . . . a ℓ,N −1 With this representation each addition and multiplication over R Q is implemented with pointwise operations of the corresponding matrices. For example, a · b ∈ R Q is   a 1,0 · b 1,0 . . . a 1,N −1 · b 1,N −1   .. .. ℓ×N .. Mat(a) ⊙ Mat(b) =   ∈ Z . . . a ℓ,0 · b ℓ,0 . . . a ℓ,N −1 · b ℓ,N −1 where the operations in the i-th row are performed modulo q i . Cost of operations in double-CRT representation: We estimate the cost of our algorithms by the number of NTTs and multiplications performed modulo the small primes q i ’s. We assume that all those primes have about the same bit length, thus, operations modulo any of them cost essentially the same. Moreover, we assume that a forward and a backward NTT modulo q i have the same cost, thus, we do not distinguish them in our cost estimations. Base extension In some situations, we may want to operate on polynomials defined modulo different values Q and D. To do this we need to represent both operands on a common modulus with an operation called base extension. Q w For Q v simplicity, let’s assume that D = i=1 d i divides Q so that we have Q = P · D for some P = i=1 p i . Then, given a ∈ R Q and b ∈ R D , both in double-CRT form, we want to lift b to R Q . This is done by reconstructing each coefficient of b modulo D, then reducing them modulo each p i . However, to avoid arbitrary precision integers we try to reconstruct b i ∈ Z D already performing all the operations modulo the p i ’s. This means that the conversion is not exact and we obtain [b i ] D + u i · D in base P with |u i | ≤ 1/2 instead of exactly [b i ] D . So, overall we have the residues of [b(X)] D + u(X) · D in the basis P · D, with ∥u(X)∥ ∞ ≤ 1/2 [23]. For completeness, we show this operation in detail in Appendix C. It costs v + w NTTs and O(v · w · N ) modular multiplications, and it is defined as follows:   v w X FastBaseExtension(b, D, P ) :=  b · (D/d j ) −1 · (D/d j ) mod p i  j=1 d j Gadget matrix Consider three positive integers Q, B, and d such that d ∈ O(log Q). Let g be a d-dimensional column vector, I 2 be the 2 × 2 identity matrix, and ⊗ denote the Kronecker tensor product. We say that G = I 2 ⊗ g ∈ Z 2d×2 is a gadget matrix for the base g with quality B if there is an efficient decomposition algorithm G −1 : Z 2 Q → Z 2×2d such that, if A = G −1 (a, b), then ∥A∥ ∞ ≤ B and A · G = (a, b) mod Q. We naturally extend G −1 to a polynomial ring of the form R Q = Z Q [X]/⟨f (X)⟩ by applying G −1 coefficientwise. That is, given (a, b) ∈ R 2 Q , we define P f −1 −1 G −1 (a, b) = deg G (a i , b i ) · X i . We also extend G −1 to matrices C ∈ R 2d×2 by applying it to 2d×2 each row. Thus, for C ∈ R Q , we have G −1 (C) ∈ R 2d×2d . The main example of a gadget matrix is the one defined by some base B ∈ Z, which corresponds to d = ⌈log B (Q)⌉, g = (B 0 , B 1 , ..., B d−1 ) T , and quality B. For instance, if B = 2, then G −1 (a, b) = (a 0 , ..., a d−1 , b 0 , ..., b d−1 ), where a i ’s and b i ’s are the bits of a and b, respectively. The CRT-gadget decomposition is of central importance in our double-CRT GSW Q scheme, presented in Section 3, and it is defined as follows. Let q 1 , ..., q ℓ be prime numbers and Q := ℓi=1 q i . Let d ∈ N be the “number of digits”. For simplicity, assume Q that d|ℓ and define k := ℓ/d ∈ Z. Then, i·k q i , that is, a product of k for 1 ≤ i ≤ d, define the i-th “CRT digit” as D i := j=(i−1)·k+1 consecutive primes. Finally, define Q i := Q/D i and Q̂ i := (Q/D i ) −1 mod D i . Then the gadget matrix is G = I 2 ⊗ g ∈ Z 2d×2 where g := (Q 1 · Q̂ 1 , ..., Q d · Q̂ d ). More explicitly,   Q 1 · Q̂ 1 ..   ..  . .     Q d · Q̂ d 0   ∈ Z 2d×2 . G =   0  · Q̂ 1    . ..   .. .  Q d · Q̂ d −1 −1 Then we define G −1 (a, b) := (CRT −1 D 1 ,...,D d (a), CRT D 1 ,...,D d (b)). It follows that G (a, b) · G = −1 (a, b) mod Q. Moreover, since each entry of G (a, b) is of the form a mod D i or b mod D i , we see that the quality of this gadget matrix is D := max (D 1 , ..., D d ). Because of the ciphertext shrinking that we present in Section 3, we need a more general definition of gadget matrices, which includes an integer scaling factor. Namely, we say that G α is a scaled gadget matrix with factor α if G −1 (α −1 · a, α −1 · b) · G α = (a, b), in other words, we have to multiply the input (a, b) by the inverse of α modulo Q before decomposing it. Basic encryption schemes based on LWE, RLWE, and CLWE We define the set of LWE encryptions of a message m ∈ Z t , where t ≥ 2, under a secret key s ∈ Z n , with E-subgaussian noise and scaling factor ∆ ∈ Z as n+1 LWE Q : b = [a · s + e + ∆ · m] Q where e is E-subgaussian }. s (∆ · m, E) := {(a, b) ∈ Z Q For a power-of-two cyclotomic polynomial R̂, the set of RLWE ciphertexts encrypting a message m ∈ R̂, with scaling factor ∆ ∈ N, under a secret key s, and with E-subgaussian noise is R̂ Q LWE s (∆ · m, E) := {(a, b) ∈ R̂ 2 Q : b = [a · s + e + ∆ · m] Q where e is E-subgaussian }. Basically the same definition applies to CLWE ciphertexts: R̃ Q LWE s (∆ · m, E) := {(a, b) ∈ R̃ 2 Q : b = [a · s + e + ∆ · m] Q where e is E-subgaussian }. In any of the three types of ciphertexts, the decryption is done by multiplying the term a (or a) by the secret key and subtracting it from b modulo Q, which produces e ′ = e + ∆ · m mod Q, then we output ⌊e ′ /∆⌉ mod t. If ∥e ′ − ∆ · m∥ < Q/(2t), then the decryption correctly outputs m mod t. Common homomorphic operations Generally, FHE schemes allow us to add and multiply ciphertexts homomorphically. In this section we briefly show a list of other common homomorphic operations that apply to RLWE and that will be used here on both RLWE and CLWE ciphertexts. Readers not familiar with them can read Appendix D for a detailed description. Q ℓ−1 – Modulus switching: takes a ciphertext c = (a, b) ∈ RLWE s,Q (m, E), where Q = i=0 q i , ′ ∈ RLWE ′ ), where Q ′ = Q/q and E ′ ≤ and prime q diving Q, and outputs c (m, E s,Q q (E/q) 2 + ∥s∥ 22 /2. Moreover, it costs 2ℓ NTTs and O(kℓN ) multiplications on Z q i . – Key switching: takes as input a ciphertext c = (a, b) ∈ R̃ Q LWE z (∆ · m, E) and a key-switching key K ∈ q R̃ Q KS ds (z, E k ), both in double-CRT form. It outputs c ′ ∈ R̃ Q LWE s (∆ · m, E ′ ), where E ′ ≤ O( E 2 + dp · D 2 · E k 2 ), with D = max(D 1 , ..., D d ). Moreover, it costs d · ℓ NTTs and O(ℓ 2 · p) products on Z q i . – Automorphism: it takes c = (a, b) ∈ R̃ Q LWE s (∆ · m, E), u ∈ Z p , and K ∈ R̃ Q KS ds (s(X u ), E k ) as input. It outputs c ′ ∈ R̃ Q LWE s (∆ · m(X u ), E ′ ). The noise growth and the cost are the same as the ones of the key switching. Ring Packing In [29], Micciancio and Sorrell present a ring packing method to transform a set into a single RLWE ciphertext encrypting of N LWE samples (a i , b i := a i · s + e i + ∆µ i ) ∈ Z n+1 P N −1 i µ = i=0 µ i · X . To do so, they define a “packing key” composed of n · L RLWE ciphertexts as n·L×2 K := (a, b := a · z + e + G · s) ∈ R̂ Q where L := ⌈log B (Q)⌉ and G = I n ⊗ (B 0 , ..., B ℓ−1 ) T ∈ Z n·L×n is a gadget matrix such that g −1 (u)G = u for any u ∈ Z nQ . We show this packing procedure in detail in Appendix E. Note that it requires O(n · L) multiplications on R̂ Q . Double-CRT GSW encryption scheme In this section, we formalize a double-CRT version of the GSW scheme supporting all the standard operations, like the external product and homomorphic multiplication. We also present two key switching algorithms for GSW, making it possible to evaluate automorphisms on GSW ciphertexts. Moreover, we also include a new operation, which we call shrinking. We present our scheme over the circulant ring R̃ := Z[X]/⟨X p − 1⟩, where p is prime, and base its security on the circulant-LWE problem. Moreover, since our main goal is to use the GSW scheme to run the amortized bootstrapping, we just define the encryption function to powers of X and do not present the decryption. We stress that is trivial to adapt our scheme to the usual RLWE problem using power-of-two cyclotomic rings and encrypting other types of messages. We define the GSW ciphertexts in a more general way, by including a correction factor α ∈ Z, which is introduced by the shrinking operation. In more detail, the set of GSW encryptions m with a scaling factor α is denoted by R̃ Q GSW ds (α · m). Any element of this set has the form C = [a | a · s + e] + m · G α ∈ R̃ 2d×2 , where s ∈ R̃ is the secret key, e ∈ R̃ 2d is the noise term, and G α is the scaled gadget matrix, as described in Section 2. We can write R̃ Q GSW ds (α · m, E) to specify that e is E-subgaussian. Saying that C is in double-CRT form means that each entry c i,j ∈ R̃ Q is stored as Mat(c i,j ), as described in Section 2. λ ): Choose a prime number p, standard deviations σ , σ ∈ R, and an integer – GSW.ParamGen(1 err sk Q ℓ Q := i=1 q i , where q 1 , ..., q ℓ are small primes (say, with 32 bits), such that the (p, Q, σ err , σ sk )- RLWE problem offers us λ bits of security. Moreover, p and Q must be coprime. Let d ∈ N be the “number of CRT digits”. For simplicity, Q assume that d|ℓ and let u := ℓ/d ∈ Z. Then, for 1 ≤ i ≤ d, define each “CRT digit” as D i := i·u j=(i−1)·u+1 q i , that is, a product of u consecutive primes. Output params = (p, Q, σ err , σ sk , d, {q i } ℓi=1 , {D i } di=1 ). – GSW.KeyGen(params): Sample s̄ 0 , ..., s̄ p−1 following a discrete Gaussian over Z with parameter P i σ sk . Let s̄ = p−1 i=0 s̄ i · X then project s̄ as s := L((1 − X)s̄) ∈ R̃. Output sk := (s, s̄). where each row is a sample – GSW.Enc(µ, sk): To encrypt µ ∈ Z p , generate a matrix V ∈ R̃ 2d×2 from the Circulant-LWE distribution with secret s and noise terms following a discrete Gaussian with parameter σ err . Output V + X µ · G ∈ R̃ Q GSW ds (1 · X µ ). Lemma 1 (Security of GSW). If the decisional (p, Q, σ err , σ sk )-RLWE problem is hard, then the GSW scheme over the circulant ring R̃ is CPA-secure for messages of the form X k . Proof. Lemma 4 of [7]. We now present the homomorphic operations that can be performed with GSW. Shrinking gadget matrices We begin by defining a new operation called shrinking, whose main purpose is to reduce the size of ciphertexts. Let Q, Q i , Q̂ i , and D be as in Section 2. Also, let α ∈ Z Q and α i := α mod D i . Then, the scaled gadget matrix is   Q 1 · Q̂ 1 · α 1 ..     .     Q d · Q̂ d · α d  ∈ Z 2d×2 .  G α =   · Q̂ · α     .. ..   . . Q d · Q̂ d · α d Notice that each CRT digit D i defines two rows of G α . Ideally, we would choose k digits, say, D 1 , ..., D k , remove the two 2k rows corresponding to them, and obtain a new gadget matrix with respect to the digits D k+1 , ..., D d . However, by doing so, we obtain a scaled gadget matrix G β with respect to a new scaling factor β. 2(d−k)×2 For this shrinking operation, we define the projection π k : R 2d×2 → R Q as the function that takes a matrix C and outputs C such that for 1 ≤ i ≤ d − k, row i (C ) := row i+k (C) and row d−k+i (C ′ ) := row i+d+k (C). Then we divide the result by D (k) := D 1 · ... · D k , and compute the new scaling factor β. This procedure is shown in detail in Algorithm 1. In Lemma 2, we prove its correctness. Algorithm 1: Shrink matrix Input: C ∈ R 2d×2 , CRT digits D 1 , ..., D d , a scaling factor α, and k ∈ Z such that 1 ≤ k < d. 2(d−k)×2 Output: C ′ ∈ R Q ′ and α ′ ∈ Z. (k) 1 D := D 1 · ... · D k (k) 2 Q := Q/D 3 C̄ := π k (C) (k) 4 C := C̄/D mod Q ′ (k) −1 5 α := α · CRT D k+1 ,...,D d (D ) mod Q ′ . 6 return C , α Lemma 2. Let Q := di=1 D i for coprime D i ’s and k be an integer such that 1 ≤ k < d. Define Q ′ := Q/(D 1 · ... · D k ). Then, given a scaled gadget matrix G α with respect to the CRT basis D 1 , ..., D d , Algorithm 1 outputs G ′ ∈ Z 2(d−k)×2 and α ′ ∈ Z such that CRT −1 (a, b) · G ′ = α ′ · (a, b) mod Q ′ , for any (a, b) ∈ R 2 Q ′ , where CRT −1 is the decomposition with respect to D k+1 , ..., D d . Proof. Presented in Appendix F.1. Shrinking a ciphertext Let C = [a | a · s + e] + m · G α ∈ R̃ 2d×2 be an encryption of m with scaling factor α. We define the operation GSW.Shrink(C, k) essentially by applying Algorithm 1 to C, except that dividing 2(d−k)×2 C̄ ∈ R̃ Q by D (k) is done by applying the modulus switching to every row of C̄. This is necessary because we are assuming that C is stored in double-CRT form. We show this procedure in detail in Algorithm 2 and prove its correctness in Lemma 3. Lemma 3 (Correctness and cost of ciphertext shrinking). Let C ∈ R̃ Q GSW ds (α · m, E), k ∈ N ∗ such that k < d, and C ′ , α ′ be the output of Algorithm 2. Assume that s is S-subgaussian for some S. Then, C ′ ∈ R̃ Q GSW ds (α ′ · m, E ′ ) with E ′ ≤ O(E/D (k) + p · S). Moreover, assuming that each CRT digit D i is a product of ℓ/d primes, the cost of Algorithm 2 is 4 · (d − k) · ℓ NTTs and O(k · ℓ 2 · p) multiplications on Z q i . Proof. Firstly notice that C̄ = π k (C) = π k ([a | a · s + e]) + m · π k (G α ) = [ā | ā · s + ē] + m · D (k) · G α ′ , where ā = π k (a) and ē = π k (e). Thus, each row of C̄ can be seen as an RLWE sample encrypting ∆ · µ, where µ ∈ {m, −s} and ∆ = D (k) · Q ′ i · Q̂ ′ i · α i ′ for some i. Thus, ModSwt Q→Q ′ (row i ( C̄)) Algorithm 2: Shrink ciphertext Input: C ∈ R̃ 2d×2 in double-CRT form, scaling factor α, CRT digits D 1 , ..., D d , and k ∈ Z such that 1 ≤ k < d. 2(d−k)×2 Output: C ′ ∈ R̃ Q ′ and new correction factor α ′ ∈ Z. Complexity: 4 · (d − k) · ℓ NTTs and O(k · ℓ 2 · p) multiplications on Z q i . Noise growth: E 7→ O(E/D (k) + p · S) (k) 1 D := D 1 · ... · D k (k) 2 Q := Q/D 2(d−k)×2 3 C̄ := π k (C) ∈ R̃ Q ′ 4 for 1 ≤ i ≤ 2 · (d − k) do c i := ModSwt Q→Q ′ (row i ( C̄)) Define C ′ such that row i (C ′ ) = c i . (k) , ..., D (k) ) −1 mod Q ′ . 7 β := CRT D k+1 ,...,D d (D 8 α := α · β mod Q 9 return C , α outputs an RLWE sample encrypting ∆ · µ/D (k) = Q ′ i · Q̂ ′ i · α i ′ · µ. Grouping these rows to define C ′ gives us C ′ = [a ′ | a ′ · s + e ′ ] + m · G α ′ . To analyze the error growth, first, notice that π k does not increase the noise, thus, ē is E-subgaussian. Then, the final noise e ′ is just provenient from the modulus switching over RLWE samples with E-subgaussian noise, thus, we have E ′ = O(E/D (k) + p · S). Over the ring R̃ Q , one modulus switching to remove u primes out of ℓ costs 2ℓ NTTs and O(u·ℓ·p) products modulo q i . Since we are removing D (k) , which is a product of kℓ/d primes, and we execute modulus switching 2(d − k) times, in total we need 4(d − k)ℓ NTTs and O(2(d − k) · k · ℓ 2 · p/d) = O(k · ℓ 2 · p) multiplications on Z q i . External product in RNS representation The external product is a homomorphic multiplication between a CLWE ciphertext and a GSW ciphertext. In our case, there is a little difference because we have to take care of the scaling factor α. Namely, firstly we multiply the CLWE ciphertext by α −1 mod Q before decomposing it with respect to the scaled gadget matrix G α , so that the result CLWE ciphertext does not depend on α. We now present this operation in detail in Algorithm 3 and prove its correctness in Lemma 4. Lemma 4 (Correctness and cost of external product). On input c ∈ R̃ Q LWE s (∆ · m 0 , E 0 ) and √ C ∈ R̃ Q GSW ds (α · m 1 , E 1 ), Algorithm 3 outputs c ′ ∈ √ R̃ Q LWE s (∆ · √ m 0 · m 1 , E ) where E = O( dp · D · E 1 + E 0 ) if m 1 is a power of X and E = O( dp · D · E 1 + p · E 0 · ∥m 1 ∥) otherwise. Moreover, it requires 2 · d · ℓ NTTs and O(ℓ 2 · p) products on Z q i . 2d×2 Proof. Remember that we can write C = [a | a · s + e] + m · G α ∈ R̃ Q for some a ∈ R̃ 2d Q and E-subgaussian e. Let u = (u 1 , ..., u 2d ) be the vector defined by the first loop. It is easy to see that u = G −1 (α −1 · c). Therefore, it holds that u · G α = c mod Q. Applying the fast base extension to u i outputs v i = u i + w i where ∥w i ∥ ≤ D i /2. Thus, by defining D := max(D 1 , ..., D d ), we have v = u + w where ∥w∥ ≤ D/2. Firstly, we claim that w · G α = (0, 0) mod Q. Indeed, remember that Q i := Q/D i , Q̂ i := T (0 g) T ) ∈ Z 2d×2 , thus, Q −1 i mod D i , g = (Q 1 · Q̂ 1 · [α] D 1 , ..., Q d · Q̂ d · [α] D d ) and G α = ( (g 0) Algorithm 3: RNS-friendly External product Input: c ∈ R̃ Q LWE s (∆ · m 0 , E 0 ) and C ∈ R̃ Q GSW ds (α · m 1 , E 1 ) both in double-CRT form. Output: c ′ ∈ R̃ Q LWE s (∆ · m 0 · m 1 , E ′ ) Complexity: 2 · d · ℓ NTTs √ and O(ℓ · p) products on u Z q i . Noise growth: E ∈ O( √ dp · D · E 1 + E 0 ) if m 1 = X for some u and E ′ ∈ O( dp · D · E 1 + p · E 0 · ∥m 1 ∥) otherwise 1 Denote c = (a, b) ▷ Almost for free in double-CRT form. Just group entries corresponding to prime factors of each D i and multiply them by α −1 2 for 1 ≤ i ≤ d do Let u i := α −1 · a mod D i Let u i+d := α −1 · b mod D i for 1 ≤ i ≤ d do Let v i := FastBaseExtension(u i , D i , Q/D i ) ∈ R̃ Q Let v i+d := FastBaseExtension(u i+d , D i , Q/D i ) ∈ R̃ Q Let v := (v 1 , ..., v 2d ) ∈ R̃ 2d Q ▷ it is already in double-CRT format 9 c = v · C ∈ R̃ Q 10 return c by writing w = (w 1 , w 2 ) we can see that (w 1 , w 2 ) · G α = (w 1 · g, w 2 · g). But for both i = 1, 2, we have d d X X (w i,j · D j ) · (Q j · Q̂ j · [α] D i ) = w i,j · Q · Q̂ j · [α] D i = 0 mod Q. w i · g = j=1 Therefore, modulo Q, it holds that j=1 c ′ := v · C = [v · a, v · a · s + v · e] + u · G α · m 1 = [v · a, v · a · s + v · e] + [a, a · s + e + ∆ · m 0 ] · m 1 = [v · a + a · m 1 , a ′ · s + v · e + e · m 1 +∆ · m 0 · m 1 ]. {z } | {z } | a ′ e ′ Hence, c is indeed an RLWE encryption of m 0 · m 1 . Moreover, since ∥v∥ ≤ D, we have that v · e is ( dp · D · E 1 )-subgaussian. If m 1 = X z for some p z, the product do not change the distribution, √ e·m 1 mod X −1 just rotates the coefficients of e, but thus, √ e is ( dp · D · E 1 + E 0 )-subgaussian. In general, e · m 1 is ( p · E 0 · ∥m 1 ∥)-subgaussian, and e ′ is ( dp · D · E 1 + p · E 0 · ∥m 1 ∥)-subgaussian. It remains to analyze the cost of the algorithm. The first loop costs only 2ℓ modular multiplications. Since each CRT digit D i has ℓ/d prime factors, each base extension costs ℓ NTTs and O((ℓ/d) · (ℓ − ℓ/d) · p) modular multiplications. Thus, the second loop costs 2 · d · ℓ NTTs and O(ℓ 2 · (1 − 1/d) · p) = O(ℓ 2 · p) modular multiplications. Since the output of FastBaseExtension is already in double-CRT format, the product v · C does not require any NTT and is performed via pointwise multiplication, thus, it costs 4dℓp modular multiplications. Therefore, the total cost is 2 · d · ℓ NTTs and O(ℓ 2 · p) products on Z q i . Homomorphic multiplication This operation 5 takes GSW encryptions of two messages and outputs a GSW encryption of their product. This is done by performing one external product for each row of one of the ciphertexts, therefore, the cost is exactly 2·d times the cost of one external product. Since each row is multiplied independently, the noise growth is the same as in the external product. We show it in detail in Algorithm 4. The only caveat is the scaling factor of the output. Both input ciphertexts have scaling factors, say α 0 and α 1 , so one could expect that the output would be scaled by α 0 · α 1 . However, since external products output CLWE encryptions that do not depend on the scaling factor of the GSW ciphertext, the output of the GSW multiplication is scaled only by, say, α 0 . Algorithm 4: RNS-friendly GSW homomorphic multiplication Input: C 0 ∈ R̃ Q GSW ds (α 0 · m 0 , E 0 ) and C 1 ∈ R̃ Q GSW ds (α 1 · m 1 , E 1 ) both in double-CRT form. Output: C ∈ R̃ Q GSW ds ((α 0 ) · m 0 · m 1 , E) Complexity: 4 · d 2 · ℓ NTTs and O(d · ℓ 2 · p) products on Z q i . Noise growth: E ∈ O( √ dp · D · E 1 + E 0 ) if m 1 = X u for some u and E ′ ∈ O( dp · D · E 1 + p · E 0 · ∥m 1 ∥) otherwise ▷ Consider ∆ i := Q i · Q̂ i · α 0 mod D i 1 for 1 ≤ i ≤ d do Let c i := row i (C 0 ) ∈ R̃ Q LWE s (∆ i · m 0 , E 0 ) c ′ i = c i ⊡ C 1 ∈ R̃ Q LWE s (∆ i · m 0 · m 1 , E) ▷ External product 4 for d + 1 ≤ i ≤ 2 · d do Let c i := row i (C 0 ) ∈ R̃ Q LWE s (−∆ i · m 0 · s, E 0 ) c ′ i = c i ⊡ C 1 ∈ R̃ Q LWE s (−∆ i · m 0 · m 1 · s, E) 2d×2 such that row i (C ′ ) = c ′ i 7 Let C ′ ∈ R̃ Q 8 return C ′ Key switching for GSW ▷ External product If one instantiates the double-CRT GSW scheme over the usual power-of-two cyclotomic ring, i.e. modulo X N + 1, then one can freely choose the keys that will be switched with no issue regarding security. However, we are using the circular ring, X p − 1, and so have to be more careful. In [7], it is shown that GSW over circulant rings is secure if one just encrypts powers of X. The main problem was that in a circular ring an attacker can interpret an element a ∈ R as a polynomial a ′ ∈ Z[X]. In this case, it holds that a ′ = a+u·(X p −1) for some u ∈ Z[X], and so a ′ (1) = a(1) ∈ Z. Thus, a ciphertext evaluated at one would produce the pair (a(1), b(1) = a(1)·s(1)+∆m+e(1)) ∈ Z 2 , which could leak information about s or the message. To solve this Bonnoron, Ducas, and Fillinger [7] apply a function to the RLWE samples that fixes the values of the polynomials when they are evaluated at one, such that (a(1), b(1)) = (0, ∆), thus are independent of the secret key and leak no information on the message. However, to key switch from a secret key s ∈ R̃ to another secret key z ∈ R̃, we have to encrypt z, which is not a power of X. Thus, we extend the results of [7] to show that it is also safe to In [13], a homomorphic multiplication between two GSW ciphertexts is called internal product. Algorithm 5: GSW key switching Input: C ∈ R̃ Q GSW dz (α · m, E), K ∈ R̃ Q KS ds (z, E k ), K s ∈ R̃ Q GSW ds (1 · (−s), E s ), all in double-CRT form. Output: C ′ ∈ R̃ Q GSW ds (α · m, E ′ ), Complexity: 3 · d 2 · ℓ NTTs ℓ 2 · p) products on √ Z q i . √ and O(d · √ Noise growth: E ∈ O( dp · D · E s + p · ∥s∥ · E + p · d · D · E k · ∥s∥) 1 for 1 ≤ i ≤ d do c i = KeySwt(row i (C), K) ∈ R̃ Q LWE s (∆ i · m) c d+i = c i ⊡ K s ∈ R̃ Q LWE s (−∆ i · m · s) Let C ′ ∈ R̃ 2d×2 such that row i (C ′ ) = c i 5 return C encrypt z. The crucial property here is: In the case of key-switching keys, we are only encrypting the secret polynomials of the CLWE problem, which are always of the form s = L((1 − X) · s ′ ), and so always result in zero when they are evaluated at one. Therefore, as m(1) = 0, it is secure to encrypt them under the CLWE problem. We prove this formally for any constant c such that m(1) = c in Appendix B. GSW key switching via two-layer reconstruction Given C ∈ R̃ Q GSW dz (α · m), remember that for 1 ≤ i ≤ d, row i (C) ∈ R̃ Q LWE z (∆ i · m), where ∆ i := Q i · Q̂ i · α i . Also, for d + 1 ≤ i ≤ 2 · d, row i (C) ∈ R̃ Q LWE z (−∆ i · m · z). Thus, to switch C to a key s, we just need to use the first d rows. Namely, we use the RLWE/CLWE key switching to obtain CLWE encryptions of ∆ i · m under s, then we multiply these ciphertexts by −s to construct the last d rows. This procedure is shown in detail in Algorithm 5. From the costs of the external product and of the key switching, we see that we need 3 · d 2 · ℓ NTTs and O(d · ℓ 2 · p) products on Z q i . From the noise growth presented in these √ algorithms, we see that after key switching, the noise is Ê-subgaussian, where Ê ∈ O(E + dp · D · E k ) and D = ). Thus, after the we have an √ E -subgaussian, where √ max(D 1 , ..., D √ external products, √ d E ∈ O( dp · D · E s + p · Ê · ∥s∥) = O( dp · D · E s + p · ∥s∥ · E + p · d · D · E k · ∥s∥) Noise-reduced GSW key switching via parallel reconstruction When we key switching the first d rows from z to s, we generate CLWE samples with a larger noise. Then, when we use these samples to reconstruct the other d rows, we accumulate more noise over them, generating thus samples with even larger noise, proportional to p. The key switching that we present in this section avoids that “double accumulation” by producing independent CLWE samples that can be subtracted to reconstruct the remaining rows. Because subtraction increases the noise linearly, we accumulate less noise in the last d rows of the GSW ciphertext. In the end, we save a factor p in the final noise. For this, we need an extra key encrypting the s · z and we replace the GSW encryption of s by a key-switching key from s to s itself. We present this procedure in detail in Algorithm 6, but defer the proof of its correctness to Appendix F.3. GSW automorphism Given C ∈ R̃ Q GSW ds (α · m, E) and η : X 7→ X u , for some u ∈ Z, we just have to apply η to each row of C, then apply one of the GSW key switching algorithms described in Section 3.5. Algorithm 6: NoiseReducedGSWKeySwt Input: C ∈ R̃ Q GSW dz (α · m, E), K z ∈ R̃ Q KS ds (z, E z ), K s ∈ R̃ Q KS ds (s, E s ), and K sz ∈ R̃ Q KS ds (s · z, E sz ), all in double-CRT form. Output: C ′ ∈ R̃ Q GSW ds (α · m, E ′ ), Complexity: 3 · d 2 · ℓ NTTs √ and O(d · ℓ √ · p)) products √ on Z q i . Noise growth: E ∈ O( dp · D · E sz + dp · D · E s + p · ∥s∥ · E) ▷ Construct the first d rows of the GSW ciphertext 1 for 1 ≤ i ≤ d do c i = KeySwt(row i (C), K z ) ∈ R̃ Q LWE s (∆ i · m) ▷ Now construct the last d rows for 1 ≤ i ≤ d do Let (a, b) = row i (C) ∈ R̃ Q LWE z (∆ i · m) for 1 ≤ i ≤ d do ▷ Each base extension costs ℓ NTTs and O(p · ℓ 2 /d) multiplications on Z q i h i = FastBaseExtension(a mod D i , D i , Q/D i ) ∈ R̃ Q y i = FastBaseExtension(b mod D i , D i , Q/D i ) ∈ R̃ Q h := (h 1 , ..., h d ) y := (y 1 , ..., y d ) a ′ := h · col 1 (K sz ) − y · col 1 (K s ) b ′ := h · col 2 (K sz ) − y · col 2 (K s ) c d+i := (a ′ , b ′ ) ∈ R̃ Q LWE s (−∆ i · m · s) Let C ′ ∈ R̃ 2d×2 such that row i (C ′ ) = c i 14 return C Notice that the first d rows of C are regular CLWE encryptions, thus, automorphisms work as usual producing new CLWE encryptions under the key η(s). The other d rows can be seen as CLWE encryptions of the −∆ i · m · s, therefore, the automorphism generates CLWE encryptions of −∆ i · η(m) · η(s), which correspond to the last d rows of a GSW encryption of ∆ i · η(m) under the key η(s). Moreover, η does not change the distribution of the noise. In summary, η(C) ∈ R̃ Q GSW dη(s) (α · η(m), E). Then, applying GSW key switching on η(C) gives us C ′ ∈ R̃ Q GSW ds (α · η(m), E ′ ). Hence, the noise growth and the cost are the same as the ones of the chosen key switching. GSW evaluation of scalar products on the exponent In this section we consider the problem of evaluating a scalar product between two vectors u, v ∈ Z kp , when u is known in clear and each entry of v is encrypted as X v i into a GSW sample. The output is a GSW encryption of X u·v mod p . The straightforward way of implementing this scalar product is the following: apply the automorphism X 7→ X u i to obtain GSW encryptions of X u i ·v i mod p , then use the GSW multiplication k Q k u ·v i i times to obtain a GSW encryption of i=1 X = X u·v mod p . However, each GSW multiplication costs 2d external products, so this naı̈ve implementation needs 2kd external products. We want to reduce that to around k · d, thus, halving the cost. Moreover, instead of using k automorphisms on GSW ciphertexts, which cost essentially 2 · d · k CLWE key switchings, we want to use automorphisms on the CLWE samples so that the cost of k automorphisms also drops to k · d, that is, halving the cost compared to GSW automorphisms. Algorithm 7: EvalScalarProd: Evaluate scalar product in the exponent of X Input: K s ∈ R̃ Q GSW ds (1 · (−s), E s ), K v ∈ R̃ Q KS ds (s(X v ), E k ) for all v ∈ Z p , and for 1 ≤ i ≤ k, C i ∈ R̃ Q GSW ds (α · X m i , E i ) and u i ∈ Z p . P All K v and C i in double-CRT form. Output: C ′ ∈ R̃ Q GSW ds (α · X y , E ′ ) where y = ki=1 u i · m i mod p. Complexity: 3 · k · d 2 · ℓ NTTs and O(k · d · ℓ 2 · p) products on Z q i . P k Noise growth: E 7→ O dDp · ∥s∥ · E i + dp · D · E s + Ē + Ê , where Ē = p · ∥s∥ · E 1 and Ê = p · ∥s∥ · k + 1 · E KS with E KS ∈ O( dp · D · E k ). ▷ Consider that ∆ i := Q i · Q̂ i · α i , where α i = α mod D i 1 Define u k+1 = 1 2 for 1 ≤ i ≤ d do Let c i := row i (C 1 ) ∈ R̃ Q LWE s (∆ i · X m 1 , E 1 ) −1 m 1 ·u 1 ·u 2 c i = Auth(c i , u 1 · u −1 , E 1 + E KS ) 2 mod p) ∈ R̃ Q LWE s (∆ i · X P j −1 (j) ▷ Let S := u j+1 · i=1 m i · u i mod p for 2 ≤ j ≤ k do (j−1) +m j P j c i = c i ⊡ C j ∈ R̃ Q LWE s (∆ i · X S , i=2 dp · D · E i + (E 1 + E KS )) v = u j · u −1 j+1 mod p (j) P dp · D · E i + E 1 + j + 1 · E KS ) c i = Auth(c i , v, K v ) ∈ R̃ Q LWE s (∆ i · X S , ji=1 ▷ Now, construct the other d rows of the GSW sample for 1 ≤ i ≤ d do (k) Let c d+i := c i ⊡ K s ∈ R̃ Q LWE s (−∆ i · X S · s, E) (k) , E) such that row i (C ′ ) = c i Define C ′ ∈ R̃ Q GSW ds (α · X S 12 return C Hence, given C i ∈ R̃ Q GSW ds (α · X v i ), we define C ′ 1 = C 1 , and for 2 ≤ i ≤ k, we want to compute C ′ i = Auth(C i , u i ) · C ′ i−1 . The main idea is to extract the d rows of C ′ i that correspond to the CLWE samples encrypting m X for some message m and ignore the other d rows. So, let c j ∈ R̃ Q LWE s (∆ j ·X m ) be the j-th row of C ′ i . Instead of applying the automorphism u i to C ′ i , we can use a technique from [7] and apply u −1 i mod p to c j , then multiply it with C i−1 via external product, and apply the automorphism u i in the end. This gives us −1 u i ·m ) 1. c ′ j = Auth(c i , u −1 i ) (encrypts X −1 2. c ′′ j = c ′ j · C i (encrypts X u i ·m+v i ) ′′ m+u i ·v i ) 3. c ′′′ j = Auth(c i , u i ) (encrypts X P u i v i ), as desired. Notice that Repeating this k times, at the end, we have c ′′′ j ∈ R̃ Q LWE s (∆ j · X for each i, the first and the third step are automorphisms, so can compose them and run a single key switching instead of two. Finally, repeating this d times, we obtain all the d first rows of the GSW ciphertext encrypting the X u·v , and it remains to construct the other d rows essentially by multiplying by −s, as it was done in the GSW key switching in Algorithm 5. Since the whole algorithm uses k · d external products and k · d CLWE automorphisms, the total cost is 3 · k · d 2 · ℓ NTTs. Notice that k GSW multiplications plus k GSW automorphisms would cost 7 · k · d 2 · ℓ NTTs, therefore we are gaining a factor of around 2.33. We show this procedure in detail in Algorithm 7. Bootstrapping In this section, we show how we can use our circulant GSW scheme to evaluate a bootstrapping algorithm with polynomial noise overhead and sublinear number of homomorphic operations per refreshed message. Homomorphic Number Theoretic Transform With a more expressive accumulator in hand we can finally replace the homomorphic Nussbaumer transform and the SlowMult algorithm used in [29] by the Number Theoretic Transform (NTT) and a simpler point-wise multiplication. It is well known that over “cyclic polynomial rings” of the form R p := Z p [X]/⟨X N − 1⟩, where N is a power of two, we can multiply two elements a, z ∈ R p in time O(N log N ) by using the NTT. For this, assume that p ≡ 1 (mod N ), then there exists a primitive N -root of unity ω ∈ Z p . The NTT is an algorithm that takes a ∈ R p , interprets it as a polynomial in Z p [X], and, in time N → Z N be the O(N log N ), outputs the vector (a(ω 0 ), a(ω 1 ), ..., a(ω N −1 )) ∈ Z N p . Now let ⊙ : Z entrywise multiplication. Then it holds that NTT −1 (NTT(a) ⊙ NTT(z)) ≡ N · a · z mod ⟨X N − 1, p⟩. However, over “negacyclic polynomial rings” of the form R̂ p := Z p [X]/⟨X N + 1⟩, to perform this multiplication, we first have to multiply the coefficients of a and z by powers of some primitive 2N -root of unity ψ ∈ Z p , then apply the NTT and inverse NTT as usual, and finally multiply by powers of ψ −1 . In more detail, let ψ := (ψ 0 , ψ, ..., ψ N −1 ) and ψ −1 := (ψ 0 , ψ −1 , ..., ψ −(N −1) ), where ψ is a 2N ’th root of unity as defined above, then ψ −1 ⊙ NTT −1 (NTT(ψ ⊙ a) ⊙ NTT(ψ ⊙ z)) ≡ N · a · z mod ⟨X N + 1, p⟩ Because we now need a 2N -root of unity modulo p, we need p ≡ 1 (mod 2N ). Notice that the NTT is of dimension N , not 2N . Also, given ψ, the N -th root of unity used by the NTT can be defined as ω = ψ 2 mod p. This radix-m version of the NTT algorithm recursively splits the N -dimensional input into m vectors of dimension N m . Then, after ρ recursive levels, we reach the base case of the recursion and we apply a quadratic algorithm to compute the NTT of inputs of size m N ρ . Typically, one sets ρ = log m (N ), such that the quadratic step is executed over inputs of size one and are actually void, obtaining the complexity O(N · log N ). However, because the noise overhead of the homomorphic NTT is proportional to N ρ , we restrict ourselves to instantiating the algorithm with small values of ρ only. We show the radix-m inverse NTT in detail in Algorithm 8, where the multiplication by ψ −1 and also by the inverse of N modulo p is already included in the last step, so that the output already corresponds to the product of the two polynomials. We denote a k-th root of unity in Z p by w k . At the beginning of the algorithm, we start with w N , then all the others roots of unity that appear in all the recursive calls are just powers of w N . Number of operations of homomorphic inverse NTT The time complexity of a radix-m NTT is standard: the number of operations of lines 7 and 15 can be represented by T (N ) = 1+ ρ 1 Algorithm 8: NTT −1 - Inverse NTT in time O ρ · N m + + + Input: (f 0 , . . . , f N −1 ) ∈ Z N s.t. m | N p , ρ ∈ Z , ρ̃ ∈ Z , where ρ̃ starts at 1, m ∈ Z −1 Output: NTT (f ) 1 if ρ = 1 then u = ψ −1 N −1 mod p else u = (1, 1, ..., 1) ∈ Z N if ρ̃ = ρ then ▷ Trivial quadratic algorithm, time O N 2 for 0 ≤ j < N do P −i·j mod p a j = n−1 i=0 f i · u j · w N else ▷ General case with recursive calls for 0 ≤ i < m do g = f i , f m+i , ..., f m(N/m−1)+i h (i) = NTT −1 m (g, ρ̃ + 1) N for 0 ≤ k 1 < m do for 0 ≤ k 2 < m do N j = k 1 + m · k 2 P m−1 (i) −i·k 1 −i·k 2 a j = i=0 h k 1 · u j · w N · w m mod p return (a 0 , ..., a N −1 ) m · T (N/m) + m · N . Iterating it ρ times gives us T (N ) = m ρ · T (N/m ρ ) + ρ · m · N . Finally, we reach the end of the recursion and use the quadratic algorithm, thus, replacing T (N/m ρ ) by (N/m ρ ) 2 , we have T (N ) = N 2 /m ρ + ρ · m · N . By choosing m = N 1/ρ , we obtain the optimal complexity: N 2 1+ 1 O ρ · N · m + ρ = O ρ · N ρ m (1) With this, it is now easy to prove the complexity and noise overhead of the homomorphic evaluations of this algorithm. Lemma 5 (Time complexity in terms of homomorphic operations). The homomorphic 1+ 1 evaluation of the inverse NTT, Algorithm 8, of dimension N , can be executed with O N ρ · ρ homomorphic operations (GSW multiplications and automorphisms). Proof. The input of the algorithm is a vector of (circulant) GSW ciphertexts encrypting X f i . To add each term of the sums shown in lines 7, we just have to apply an automorphism, obtaining −i·j an encryption of X f i ·u j ·w n mod p , and one homomorphic multiplication, to accumulate the term in the partial sum. For the sum of line 15, we proceed in the same way, by applying the automorphism X 7→ X w , −i·k 2 , then one multiplication. where w = u j · w n −i·k 1 · w m 1+ 1 Thus, in total, we have O N ρ · ρ homomorphic operations. Since each GSW multiplication and automorphism can be implemented with O(d 2 · ℓ) NTTs and O(d · ℓ 2 · p) products on Z q i using our double-CRT instantiation of GSW, we have the following result. Corollary Q ℓ 1 (Time complexity in terms of NTTs and modular multiplications). Let Q = i=1 q i be the ciphertext modulus. Let d be the number of CRT digits used in the GSW ciphertexts. Then the homomorphic evaluation of the inverse NTT, Algorithm 8, of dimension N , 1+ ρ 1 1+ ρ 1 can be executed with O N · ρ · d · ℓ NTTs and O N · ρ · d · ℓ · p multiplications modulo q i . Finally, by assuming that each sum in lines 7 and 15 is implemented with Algorithm 7, we can have a concrete instead of asymptotic estimation of the number of NTTs. Lemma 6 (Number of NTTs used the homomorphic inverse NTT). Let Q = ℓi=1 q i be the ciphertext modulus. Let d be the number of CRT digits used in the GSW ciphertexts. Consider the Algorithm 8 with recursive level ρ, dimension N , and with lines 7 and 15 implemented with the EvalDotProduct, Algorithm 7. If no ciphertext shrinking is used, then the total number of NTTs is N 3 · N · d 2 · ℓ · + ρ · m . (2) m ρ If we use shrinking at the end of each recursive call, then the total number of NTTs is ρ−1 X 3 · N 2 · d 2 ρ · ℓ ρ +3 · N · m · m ρ ρ−1 X ! ! d 2 i · ℓ i +4 · N · d i · ℓ i+1 (3) where d ρ and ℓ ρ define the dimension of the input ciphertexts (thus, d = d ρ > d ρ−1 > ... > d 0 and ℓ = ℓ ρ > ℓ ρ−1 > ... > ℓ 0 ). Proof. The proof follows trivially by defining a recursive formula for the amount of NTTs per recursive call, then applying the number of NTTs already given in Algorithm 7. A detailed proof is provided in Appendix G. Error growth of the homomorphic inverse NTT Assuming again that the sums in Algorithm 8 are implemented with the EvalScalarProd (Algorithm 7), we have the following result. Lemma 7. Consider the homomorphic evaluation of Algorithm 8 on input C i ∈ R̃ Q GSW ds (α · X f i , E), where 0 ≤ i < n. Let K s ∈ R̃ Q GSW ds (1 · (−s), E s ) and K v ∈ R̃ Q KS ds (s(X v ), E k ) be the keys to compute the sums with Algorithm 7. Moreover, assume that E s is constant. Then, the noise of the output ciphertexts is bounded by O ( d · D · p · ∥s∥) ρ · N · (E + E k ) where ρ is the chosen recursive depth. Proof. We present the proof in Appendix F.4. Partial decryption using NTT −1 m Remember that to decrypt (a, b) ∈ R̂ p LWE z (m, E), we have to compute b ⋆ := b − a · z mod p, then it holds that b ⋆ = e + ∆ · m, where ∆ = ⌊p/t⌉. Then we can recover each coefficient m i by taking the log t most significant bits. This last step is message extraction and we present it in Section 4.3. In this section, we present an algorithm that uses the homomorphic inverse NTT to compute b ⋆ . The first part of the algorithm computes the forward NTT of a and of b, to obtain a := NTT(ψ ⊙ a), b := NTT(ψ ⊙ b), and the bootstrapping key encrypting z̄ := NTT(−ψ ⊙ z), we use GSW automorphisms to compute the entrywise product ā ⊙ z̄ = (ā 0 · z̄ 0 , ..., ā N −1 · z̄ N −1 ). At this point, we also add NTT(ψ ⊙ b). Finally, we apply the inverse NTT homomorphically to obtain GSW ciphertexts encrypting b ⋆ . Algorithm 9: NTTDec, the homomorphic partial decryption Input: Encryption c ∈ R̂ p LWE z (m, E (in) ). Bootstrapping keys K i ∈ R̃ Q GSW ds (1 · X −z̄ i , E), where (z̄ 0 , . . . , z̄ N −1 ) := NTT(ψ ⊙ z) ∈ Z N p , and key-switching keys for all the Galois automorphisms η a : X 7→ X a . Vectors with powers of 2N -th root of unity ψ in Z p , i.e., ψ = (ψ 0 , . . . , ψ N −1 ) and ψ −1 = (ψ 0 , . . . , ψ −(N −1) ) ′′ i Output: C̄ i ∈ R̃ Q GSW ds (α · X e i +∆·m , E ) for 0 ≤ i In lines 5 and 6, we compute K̄ i via GSW automorphism. Since this is done for each i, it contributes a total of 3 · N · d 2 · ℓ NTTs and O(N · d · ℓ 2 · p) modular multiplications. Then, we perform N plaintext-ciphertext multiplications to add b̄ i to the exponent. This costs zero NTTs and O(N · p · d · ℓ) modular multiplications, thus, it is already dominated by the cost of the automorphisms. 1+ 1 Finally, we apply the homomorphic inverse NTT, which, by Lemma 5, costs O N ρ · ρ · d 2 · ℓ 1+ 1 NTTs and O N ρ · ρ · d · ℓ 2 · p multiplications modulo q i . Thus, it is clear that this step dominates the total cost. As for the noise overhead, assuming that the ciphertexts defined in line 6 are obtained by applying the GSW Galois automorphisms defined in Algorithm 6, we have p p E ′ = O( dp · D · E s + p · ∥s∥ · E + dp · D · E k ). Then, multiplying by X b̄ i modulo X p − 1 only rotates the coefficients of the noise terms, but does not increase them. Thus, the ciphertexts K̃ i also have E ′ -subgaussian noise. by Lemma 7, the homomorphic inverse NTT increases the noise from E ′ to Finally, O ( d · D · p · ∥s∥) ρ · N · (E ′ + E k ) . Therefore, using the definition of E ′ and simplifying the expression by ignoring lower terms, we obtain p E ′′ = O ( d · D · p · ∥s∥) ρ · N · p · (E · ∥s∥ + E k · d · D) . Message Extraction After executing Algorithm 9, we obtain ciphertexts of the form C̃ ∈ R̃ Q GSW ds (α · X ∆·m+e ), and we want to extract the message m from the exponent, X ∆·m+e 7→ m. This message extraction procedure was introduced in [14] and adapted to different settings in subsequent works [12,32,8]. Usually, it is assumed to work with negacyclic rings, however in Algorithm 10 we provide a version of the message extraction algorithm adapted to the cyclic ring. Here we assume messages in Z t instead of in {0, 1}, and apply a programmable bootstrapping, i.e., mapping X ∆·m+e to f (m) for any given function f : Z t → Z t . Moreover, our algorithm also takes care of the scaling factor α in the gadget matrix. We prove its correctness and time complexity Appendix F.2. The Bootstrapping Algorithm With all the sub-constructions in place, we can now fully define the bootstrapping algorithm and analyze both the complexity and the error growth. p+1 , then packs them into The algorithm takes in N LWE samples c i ∈ LWE Q s (∆ · m i ) P ∈ Z one RLWE ciphertext c ∈ R̂ Q LWE z (∆ · m(X)), where m(X) = m i X i . It proceeds by modulo switching c from Q to p and running NTTDec, the partial decryption via homomorphic NTT, which generates GSW encryptions of X ∆ m i +e i . Finally, the messages m i are extracted back into LWE ciphertexts. The bootstrapping is shown in detail in Algorithm 11. Algorithm 10: MsgExtract Input: C ∈ R̃ Q GSW ds (α · X ∆·m+e , E), where ∆ = ⌊p/t⌉ and |e| < ∆/2. A function f : Z t → Z t p+1 Output: c̄ ∈ LWE Q s (⌊Q/t⌉ · f (m), E ) ∈ Z Q Complexity: d · ℓ NTTs √ and O(ℓ · p) products on Z q i . Noise growth: E P 7→ O( P dp · D · E) ∆−1 p−i∆−j ∆/2 mod X p − 1 1 Let t(X) = X · t−1 j=0 f (i)X 2 Let c̄ = (0, ⌊Q/t⌉ · t(X)) ∈ R̃ Q be a trivial and noiseless encryption of t(X) ′ ′ 3 c := (a , b ) = c ⊡ C ; ▷ c ′ ∈ R̃ Q LWE s (⌊Q/t⌉ · t(X) · X ∆·m+e , E ′ ) p×p 4 Let A ∈ Z be the circulant matrix of a ′ p 5 Let b ∈ Z be the coefficient vector of b p 6 Let u := (1, 0, ..., 0) ∈ {0, 1} 7 return c̄ = [u · A, u · b] ; ▷ c̄ ∈ LWE Q s (⌊Q/t⌉ · f (m), E ) Algorithm 11: Bootstrap — for plaintext space Z t (in) Input: c i ∈ LWE Q ) ∈ Z p+1 for 0 ≤ i < N , where ∆ = ⌊Q/t⌉. All the bootstrapping and s (∆ · m i , E key-switching keys used in Algorithm 9. Arbitrary functions f i : Z t → Z t , for 0 ≤ i < N . p+1 Output: c ′ i ∈ LWE Q for 0 ≤ i < N . s (∆ · f i (m i )) ∈ Z 1+ ρ 1+ 1 Complexity: O(N · ρ · d 2 · ℓ) NTTs and O(N ρ · ρ · d · ℓ 2 · p) multiplication in Z q i . ρ (in) ρ+1 Noise growth: E 7→ O (p · d · D) · ∥s∥ · N · (E · ∥s∥ + E k · d · D) (a (1) , b (1) ) = PackLWE (c 0 , ..., c N −1 ) ; (2) (2) 2 (a , b ) = ModSwitch Q→p (a (1) , b (1) ) ; (2) (2) 3 (C 0 , . . . , C N −1 ) = NTTDec(a ,b ) ; 4 for 0 ≤ i < N do c ′ i = MsgExtract(C i , f i ) ; return c ′ 0 , ..., c ′ N −1 ▷ (a (1) , b (1) ) ∈ R̂ Q LWE z (∆ · m(X), E (1) ) ▷ (a (2) , b (2) ) ∈ R̂ p LWE z (∆ ′ · m(X), E (2) ) ▷ C i ∈ R̃ Q GSW ds (α · X e i +∆ ·m i , Ē) ▷ c ′ i ∈ LWE Q s (f i (m i ), E ) Lemma 9. Given at most N LWE ciphertexts and the keys described in Lemma 8, Algorithm 11 outputs LWE ciphertexts with E ′ -subgaussian noise, where E ′ = O (p · d · D) ρ+1 · ∥s∥ ρ · N · (E · ∥s∥ + E k · d · D) . 1+ 1 1+ 1 Moreover, it costs O N ρ · ρ · d 2 · ℓ NTTs and O N ρ · ρ · d · ℓ 2 · p multiplication in Z q i . Proof. The cost of Algorithm 11 is asymptotically dominated by the NTTDec, thus, it follows directly from Lemma 8. Again from noise of the GSW ciphertexts √ Lemma 8, the √ C i output by NTTDec satρ isfy Ē = O ( d · D · p · ∥s∥) · N · p · (E · ∥s∥ + E k · d · D) , where E and E k are the parameters of the noises from the bootstrapping keys √ and the key-switching keys, respectively. From 11, the final noise is then E ′ = O( dp · D · Ē). Hence, it holds that E ′ = Lemma O (p · d · D) ρ+1 · ∥s∥ ρ · N · (E · ∥s∥ + E k · d · D) Corollary 2. The bootstrapping algorithm presented in Algorithm 11 has noise overhead of Õ(λ 1.5+ρ ), where λ is the security parameter. Proof. For a security level of λ bits based on the RLWE problem, we can choose p, N ∈ Θ(λ) and E, E k , ∥s∥ ∈ O(1). Since d = O(log Q) = O(log λ) and D is constant, we have E ′ = O λ ρ+1.5 · (log λ) (ρ+2)/2 · D ρ+2 · ∥s∥ ρ+1 = Õ(λ 1.5+ρ ). Theorem 1 (Correctness of bootstrapping). For a security parameter λ, let Q = Õ(λ 2.5+ρ ) (in) ) ∈ Z p+1 satisfy E (in) = O(Q/λ). and consider that the input ciphertexts c i ∈ LWE Q s (∆ · m i , E −λ Then, with probability 1 − 2 , the output of Algorithm 11 is correct, i.e., it outputs valid LWE encryptions of f (m i ), with E ′ -subgaussian noise, where Õ(λ 1.5+ρ ) = Õ(Q/λ), thus, it is composable. Proof. From the description of the ring packing √ algorithm presented in Section √ 2, the parameter E (1) shown in Algorithm 11 satisfy E (1) = E (in) · N + nN log Q·E R = O(E (in) · λ) = O(Q/ λ), where we used n, N, log Q ∈ O(λ) and E R = O(1). Thus, switching, √ after modulus √ √ by using p = O(λ) and ∥s∥ = O(1), it holds that E (2) = O(E (1) p/Q + N · ∥s∥) = O(p/ λ + N · ∥s∥) = O(p/ λ). Therefore, from the noise bound of the subgaussian distributions, as discussed in Section 2, the noise of the packed RLWE ciphertext is O(E (2) λ) = O(p) with probability 1 − 2 −λ , which means it is decryptable. In other words, with overwhelming probability, the correctness condition of MsgExtract is satisfied, i.e., the restriction ∥e∥ < ∆/2 described in Lemma 11, since there ∆ = ⌊p/t⌉ = O(p). Hence, the output indeed encrypts f (m i ). Moreover, by Corollary 2, the final noise is E ′ -subgaussian with E ′ = Õ(λ 1.5+ρ ), which is O(Q/λ), therefore, satisfies the same bound as the input, and thus, the bootstrapping is composable. Remark 1. One can trivially gain a factor λ in the noise presented in Corollary 2 by partially merging MsgExtract with the homomorphic inverse NTT, Algorithm 8, by starting with encryptions of ⌊Q/t⌉ · t(X) instead of encryptions of one. This does not change the noise growth of the inverse NTT and we just needs to execute lines 4 to 7 of MsgExtract, which also do not change the noise. With this, the final noise in Corollary 2 is improved to Õ(λ 1+ρ ). This optimization is applied in our implementation. Practical Results Amortized bootstrapping algorithms introduce significant asymptotic gains compared to nonamortized versions. However, they also introduce some performance overhead by requiring significantly larger parameters. As parameters grow, the asymptotic gains start to materialize, but, at the same time, memory requirements increase sharply to a point in which the implementation might become prohibitive. This is the problem preventing the [29] method from being practical, and, to a lesser extent, is also an issue in our method. As such, our primary goal when developing a proof-of-concept practical implementation was to find the smallest parameter set in which our amortized bootstrapping starts to present practical gains. We implemented our scheme mostly from scratch using Intel HEXL Library [6] as the arithmetic backend to provide fast polynomial multiplications. We benchmarked our implementation in a m6i.metal instance on AWS (Intel Xeon 8375C at 3.5GHz with 512 GB of RAM at 3200 MHz). We use Ubuntu 22.04 and G++ 11.3.0. Compiling options and further details are available in our repository. All parameter sets presented in this section consider the 128-bit security level estimated using the Lattice Estimator [2] with the default (MATZOV [28]) cost model. Parameter selection In general, bootstrapping capabilities are defined by three parameters: The output dimension p, the input error σ in , and the output error σ out a bootstrapping. Specifically, a k-bit message is of k+1 p/2 correctly bootstrapped with probability erf σ √ 2 , where erf is the Gauss error function. Let in p ∗ be the modulus of the bootstrapping output, and N be the RLWE input dimension, Equation 4 estimates the value of σ in for the amortized bootstrapping considering a composed circuit (i.e., when we bootstrap the result of a previous bootstrapping). The first term represents noise introduced by the previous bootstrapping and arithmetic operations. The second term estimates the noise introduced by the key switching from dimensions p to N and the ring packing. These first two terms are scaled down by p p ∗ by the modulus switching procedure, which, in turn, introduces some rounding noise, represented by the third term in the equation. Compared to a typical bootstrapping, our amortized method has the additional restriction that there must exist a 2N -th root of unity modulo p. Therefore, we select p = 12289 for bootstrapping RLWE samples of dimension N = 1024. As the rounding noise is the only one to be introduced directly over modulus p, it is the main limiting factor for our bootstrapping capabilities, and we minimize it by working with sparse ternary keys of Hamming Weight 256. ∥s∥ 22 p p ∗ σ in ≤ σ out + (p + N 2 ) log 2 (p ∗ )σ ks Performance of Amortized Bootstrapping (4) + INTT Performance The homomorphic evaluation of the INTT, Algorithm 8, is the core and most expensive procedure in our amortized bootstrapping. Table 3 shows its execution time for ℓ = d = 4 and ρ = 2, with and without shrinking. We choose these parameters only for benchmarking the INTT implementation and shrinking technique. They are not optimized √ for message bootstrapping. We note that increasing ρ would multiply the output noise by at least dpD ∥s∥ (Lemma 7), which, in turn, would cubically deteriorate performance on the basic arithmetic. While our estimates and Table 3: Execution time, in milliseconds, for the INTT for ℓ = 4 and ρ = 2. Without shrinking With shrinking Shrinking Exec. Time Amortized Time Exec. Time Amortized Time Speedup 12289 512 1,078,033 2,106 695,761 1,359 12289 1024 3,546,423 3,463 2,132,504 2,083 n p Table 4: Execution time, in milliseconds, for the amortized bootstrapping. ℓ = d Total Time Amortized Time 871,827 12289 1024 1,540,075 1,504 n p experimental data suggest the asymptotic improvements of ρ = 2 are greater than the arithmetic overhead, this does not seem to be the case for larger values of ρ. Bootstrapping Performance As we move to the complete bootstrapping, we introduce the overhead of calculating several key switchings, but we also can further optimize the INTT evaluation. As we defined, it outputs GSW ciphertexts, from which we extract CLWE samples in the message extraction phase. A more efficient way of implementing it is to run the last recombination step (Lines 12 to 15 in Algorithm 8) already using a CLWE as the accumulator for the summations, replacing GSW multiplications with external products. Further, we can also initialize the accumulator with the test vector at the beginning of this last recombination (similarly as introduced in [12]), which simplifies the message extraction and reduces the output error, as explained in Remark 1. This also allows us to use a smaller modulus, with ℓ = 3. Table 4 shows the results for complete bootstrapping, including key switchings, with ρ = 2 and p ∗ = 2 24 . The failure probabilities for 7 and 8-bit messages are 2 −62.4 and 2 −17.2 , respectively. The parameters ℓ = 4 and ℓ = 3 are similar in terms of bootstrapping capabilities, but using ℓ = 4 reduces σ out significantly (in up 2 49 times for our parameters), enabling variations of our bootstrapping as we exemplify in Section 5.3. Comparison with other bootstrapping methods As the output of the bootstrapping is a set of LWE ciphertexts defined modulo Q, one can classify the bootstrapping algorithms in two categories depending on the size of Q as follows: (1) when Q is small enough to fit into native integer types; (2) when Q is large and double-CRT techniques are needed. The first scenario yields the fastest bootstrapping algorithms known until now, as the ones implemented in TFHE-RS [1], but it is less general, since the output ciphertexts have little noise budget and all the subsequent homomorphic evaluation is done via programmable bootstrapping. The second scenario is more versatile, since we can increase Q to obtain refreshed ciphertexts with more noise budget so that we can compute on them without using programmable bootstrapping. In particular, some constructions require large Q. For example, if one uses scheme switchings, such as Chimera [9], where the slots of a BGV ciphertext are extracted into individual LWE ciphertexts, then functional bootstrapping is applied on each of them, then one needs the output to be defined modulo a large Q so that it is possible to pack the LWE ciphertexts again into a BGV ciphertext. As another example, the high-precision CKKS bootstrapping presented in [22] also requires large Q. Thus, we divide our comparison in those two cases. Comparison with small-Q bootstrapping algorithms Our amortized bootstrapping produces ciphertexts with large Q, hence this comparison is complicated, since these two types of bootstrapping offer different capabilities, and unfair, since using small Q allows one to implement the bootstrapping using native integer types, which represents a much faster arithmetic back end compared to double-CRT. Nonetheless, this section contains some discussion about this comparison. The state-of-the art implementation of programmable bootstrapping is TFHE-RS [1]. To achieve their impressive performance, they rely on binary secrets, on an FFT library specially tailored for negacyclic rings used in RLWE, and on small (word-sized) modulus. These are all particularities not shared by our scheme. Furthermore, we must note that the performance of such library is the result of several years of extensive research on techniques, parameters, and implementation optimizations [4]. Whereas, the goal of our implementation is just to provide a the first proof of concept of an entirely novel bootstrapping method, and further research on optimal choice of parameters or implementation optimizations are out of our scope. All that said, we notice that TFHE-RS bootstraps 8-bit messages in 828.1 ms [1], which is only 3% faster than our amortized time in the same machine. Comparison with large-Q bootstrapping algorithms To have a comparable non-amortized version of our bootstrapping, we implemented, using double-CRT, the algorithm defined in [24], which is the latest bootstrapping method for TFHE-like schemes. We start with the implementation of the accumulator using the double-CRT CLWE variant of the GSW scheme described in Section 3. We estimate noise using Equation 4, but consider N = 0 as we do not have the ring packing in this version. We choose parameters that enable similar bootstrapping capabilities for both methods and optimize performance by minimizing the dimension n. The main restriction for this process is the security level of the input. Specifically, we work with sparse ternary keys to minimize the noise, and we need to perform a key switching from dimensions p = 12289 to n, which requires an output modulus of at least p ∗ ≈ 2 21 to accommodate the noise. Considering this, n = 896 is the smallest dimension for which the input ring is secure. We could lower n by using Gaussian keys with a larger distribution σ s , but it is advantageous to avoid the quadratic impact of σ s compared to the linear impact of n in the square norm of s (third term of Equation 4). Thus, considering n = 896, ℓ = d = 2, and p = 12289, the running time we obtained was around 2.9 seconds, which is 3.4 times slower than our best amortized running times presented in Table 4. The failure probabilities for 7 and 8-bit messages are 2 −58.5 and 2 −16.3 , respectively. Further Improvements Since our results are comparable with the state-of-the-art programmable bootstrapping with small ciphertext modulus Q (even though our amortized bootstrapping uses large Q, and thus, needs double-CRT), and faster than non-amortized bootstrapping with large Q, we believe that we achieved the goal of showing that efficient amortized bootstrapping is possible and can be practical. Nonetheless, our implementation is a proof of concept and there are many promising techniques that could be applied to further improve performance. For example, using parameters from Table 4, our implementation requires 76.5 GiB of memory (for ℓ = 3). However, considering only already existing techniques from the literature (e.g., decomposed automorphisms [24]), we could reduce it to less than 10 GiB of memory. We discuss more about possible further improvements in Appendix H. ## Acknowledgments This work has been supported in part by Cyber Security Research Flanders with reference number VR20192203, by the Defence Advanced Research Projects Agency (DARPA) under contract No. HR0011-21-C-0034 DARPA DPRIVE BASALISC, and by the FWO under an Odysseus project GOH9718N. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA, the US Government, or Cyber Security Research Flanders. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. This work was done while A. Guimarães was visiting the Department of Computer Science of Aarhus University. He is supported by the São Paulo Research Foundation under grants 2013/08293- 7, 2019/12783-6, and 2021/09849-5. ## References 1. zama-ai/tfhe-rs (May 2023), https://github.com/zama-ai/tfhe-rs, original-date: 2022-10-13T09:20:07Z 2. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. Cryptology ePrint Archive, Report 2015/046 (2015), https://eprint.iacr.org/2015/046 3. Alperin-Sheriff, J., Peikert, C.: Faster bootstrapping with polynomial error. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 297–314. Springer, Heidelberg (Aug 2014). https://doi.org/10. 1007/978-3-662-44371-2_17 4. Bergerat, L., Boudi, A., Bourgerie, Q., Chillotti, I., Ligier, D., Orfila, J.B., Tap, S.: Parameter optimization & larger precision for (T)FHE. Cryptology ePrint Archive, Report 2022/704 (2022), https://eprint.iacr.org/ 2022/704 5. Bluestein, L.: A linear filtering approach to the computation of discrete fourier transform. IEEE Transactions on Audio and Electroacoustics 18(4), 451–455 (1970). https://doi.org/10.1109/TAU.1970.1162132 6. Boemer, F., Kim, S., Seifu, G., de Souza, F.D., Gopal, V.: Intel HEXL: Accelerating homomorphic encryption with intel AVX512-IFMA52. Cryptology ePrint Archive, Report 2021/420 (2021), https://eprint.iacr.org/ 2021/420 7. Bonnoron, G., Ducas, L., Fillinger, M.: Large FHE gates from tensored homomorphic accumulator. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 18. LNCS, vol. 10831, pp. 217–251. Springer, Heidelberg (May 2018). https://doi.org/10.1007/978-3-319-89339-6_13 8. Bonte, C., Iliashenko, I., Park, J., Pereira, H.V.L., Smart, N.P.: Final: Faster fhe instantiated with ntru and lwe. In: Advances in Cryptology – ASIACRYPT 2022. Springer International Publishing, Cham (2022) 9. Boura, C., Gama, N., Georgieva, M., Jetchev, D.: Chimera: Combining ring-lwe-based fully homomorphic encryption schemes. Journal of Mathematical Cryptology 14(1), 316–338 (2020). https://doi.org/doi:10.1515/ jmc-2019-0026, https://doi.org/10.1515/jmc-2019-0026 10. Brakerski, Z., Gentry, C., Halevi, S.: Packed ciphertexts in LWE-based homomorphic encryption. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 1–13. Springer, Heidelberg (Feb / Mar 2013). https: //doi.org/10.1007/978-3-642-36362-7_1 11. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012. pp. 309–325. ACM (Jan 2012). https://doi.org/10.1145/2090236.2090262 12. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (Dec 2016). https://doi.org/10.1007/978-3-662-53887-6_1 13. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: Fast fully homomorphic encryption over the torus. Journal of Cryptology 33(1), 34–91 (Jan 2020). https://doi.org/10.1007/s00145-019-09319-x 14. Ducas, L., Micciancio, D.: FHEW: Bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 617–640. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/978-3-662-46800-5_24 15. Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012), https://eprint.iacr.org/2012/144 16. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC. pp. 169–178. ACM Press (May / Jun 2009). https://doi.org/10.1145/1536414.1536440 17. Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (Apr 2012). https: //doi.org/10.1007/978-3-642-29011-4_28 18. Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (Aug 2013). https://doi.org/10.1007/978-3-642-40041-4_5 19. Guimarães, A., Pereira, H.V.L., Leeuwen, B.v.: Amortized Bootstrapping Revisited: Simpler, Asymptoticallyfaster, Implemented (2023), https://eprint.iacr.org/2023/014, report Number: 014 20. Halevi, S., Polyakov, Y., Shoup, V.: An improved RNS variant of the BFV homomorphic encryption scheme. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 83–105. Springer, Heidelberg (Mar 2019). https: //doi.org/10.1007/978-3-030-12612-4_5 21. Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 641–670. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/ 978-3-662-46800-5_25 22. Kim, A., Deryabin, M., Eom, J., Choi, R., Lee, Y., Ghang, W., Yoo, D.: General bootstrapping approach for RLWE-based homomorphic encryption. Cryptology ePrint Archive, Report 2021/691 (2021), https://eprint. iacr.org/2021/691 23. Kim, A., Polyakov, Y., Zucca, V.: Revisiting homomorphic encryption schemes for finite fields. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part III. LNCS, vol. 13092, pp. 608–639. Springer, Heidelberg (Dec 2021). https://doi.org/10.1007/978-3-030-92078-4_21 24. Lee, Y., Micciancio, D., Kim, A., Choi, R., Deryabin, M., Eom, J., Yoo, D.: Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption. Cryptology ePrint Archive, Report 2022/198 (2022), https://eprint.iacr.org/2022/198 25. Liu, F.H., Wang, H.: Batch bootstrapping i: A new framework for simd bootstrapping in polynomial modulus. In: Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III. p. 321–352. Springer-Verlag, Berlin, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30620-4_11, https://doi. org/10.1007/978-3-031-30620-4_11 26. Liu, F.H., Wang, H.: Batch bootstrapping ii: Bootstrapping polynomial modulus only requires Õ(1) fhe multiplications amortization. In: Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III. p. 353–384. Springer-Verlag, Berlin, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30620-4_12, https://doi.org/10.1007/978-3-031-30620-4_12 27. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (May / Jun 2010). https://doi. org/10.1007/978-3-642-13190-5_1 28. MATZOV: Report on the Security of LWE: Improved Dual Lattice Attack (Apr 2022). https://doi.org/10. 5281/zenodo.6412487, https://doi.org/10.5281/zenodo.6412487 29. Micciancio, D., Sorrell, J.: Ring packing and amortized FHEW bootstrapping. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) ICALP 2018. LIPIcs, vol. 107, pp. 100:1–100:14. Schloss Dagstuhl (Jul 2018). https://doi.org/10.4230/LIPIcs.ICALP.2018.100 30. Micheli, G.D., Kim, D., Micciancio, D., Suhl, A.: Faster Amortized FHEW bootstrapping using Ring Automorphisms (2023), https://eprint.iacr.org/2023/112, report Number: 112 31. Nussbaumer, H.: Fast polynomial transform algorithms for digital convolution. IEEE Transactions on Acoustics, Speech, and Signal Processing 28(2), 205–215 (1980). https://doi.org/10.1109/TASSP.1980.1163372, https: //ieeexplore.ieee.org/document/1163372 32. Pereira, H.V.L.: Bootstrapping fully homomorphic encryption over the integers in less than one second. In: Garay, J. (ed.) PKC 2021, Part I. LNCS, vol. 12710, pp. 331–359. Springer, Heidelberg (May 2021). https: //doi.org/10.1007/978-3-030-75245-3_13 33. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC. pp. 84–93. ACM Press (May 2005). https://doi.org/10.1145/1060590.1060603 A Glossary of parameters used in this work Parameter λ n N p ρ q i ℓ t d D i D Description Size Security level – Dimension of LWE samples O(λ) Degree of RLWE samples (X N + 1). Power of two. O(λ) Degree of CLWE samples (X p − 1). Prime. O(λ) Recursive depth of the bootstrapping algorithm – Prime factor of ciphertext modulus Q < 2 50 Õ(λ 1.5+ρ ) Ciphertext modulus defined as ℓ 1=1 q i Number of prime factors of Q O(ρ · log λ) Plaintext modulus O(1) Dimension of GSW ciphertexts. Number of CRT digits O(ℓ) Each CRT digit. Product of approx. ℓ/d primes. O(q i · ℓ/d) Upper-bound on the size of the CRT digits max(D 1 , ..., D d ) B Generalization of circulant-LWE encryption In [7], it was proved that we can use the circulant-RLWE problem to encrypt messages of the form X k , that is, powers of X. We now show that by slightly modifying their proof, we can prove that a scheme that encrypts polynomials m(X) whose sum of coefficients is equal to 0 is also CPA-secure under the RLWE assumption. Lemma 10. If the decisional Ring-LWE problem is hard for the prime-order cyclotomic polynomial Φ p (X), a modulus Q ∈ Z, and standard deviation σ, then the Circulant-LWE scheme is cpa-secure P i for messages of the form m(X) = p−1 i=0 m i · X where m(1) = 0. P P p−1 i Proof. Let S Q,p := { p−1 i=0 a i X : i=0 a i = 0 mod Q}. By Lemma 11 of [7], if the Ring-LWE problem is hard, then the Circulant-LWE distribution is indistinguishable from the uniform distribution 2 . Now, notice that for any ∆ ∈ Z and b ∈ S over S Q,p Q,p , if we define c = b + ∆ · m, then we have p−1 X p−1 X p−1 X b i + ∆ c i = m i = 0 mod Q. Thus, S Q,p + ∆m = S Q,p . Therefore, the circulant-LWE encryption of m is indistinguishable from 2 . a uniformly random sample from S Q,p × (S Q,p + ∆m) = S Q,p Now, notice that the secret key of the Circulant-LWE scheme is obtained by projecting the secret s̄ from the RLWE to s = L((1 − X)s̄) ∈ S Q,p , therefore, it satisfies s(1) = 0. Moreover, applying automorphisms to s modulo X p − 1 only reorder the coefficients, so, if s (k) (X) := s(X k ), we also have s (k) (1) = 0, therefore, encrypting s (k) (X) for any k is secure and we conclude that it is safe to publish the key-switching keys from s to s (k) . Finally, in Algorithm 6, we also need to encrypt a product s · z, but both keys are also CLWE secrets, thus, we still have s(1) · z(1) = 0. C Algorithm to perform fast base extension Algorithm 12: FastBaseExtension Q v Input: D = w i=1 d i , P = i=1 p i , a ∈ R D in double-CRT form. Output: a ′ = a + u · D ∈ R P D in double-CRT form, where ∥u∥ ≤ 1/2. Complexity: v + w NTTs and O(v · w · N ) modular multiplications // Assume that D̂ j := (D/d j ) −1 mod d j are precomputed 1 for 1 ≤ j ≤ w do Let a (j) := row j (Mat(a)) ∈ Z N (j) a (j) := NTT −1 d j (a ) ∈ R d j 4 for 1 ≤ i ≤ v do a (w+i) := 0 ∈ R p i for 1 ≤ j ≤ w do tmp := a (j) · D̂ j mod d j tmp := tmp · (D/d j ) mod p i a (w+i) = (a (w+i) + tmp) mod p i 10 for 1 ≤ i ≤ v do a (w+i) := NTT p i (a (w+i) ) ∈ Z N p i 12 Return (a (1) , ..., a (w+v) ) ∈ Z (w+v)×N . Common homomorphic operations D Modulus switching Here, we just consider the case where we want to switch the ciphertext Q ℓ−1 q i . q to a smaller Q ′ by removing some primes, say, q 0 , ..., q k−1 . Thus, Q ′ = i=k modulus Q = ℓ−1 i It is possible to switch to a larger modulus Q ′ by adding new primes to the moduli chain, but since we do not use this in our work, we do not discuss it here. Let q := Q/Q ′ = q 0 ·...·q k−1 . Given c := (a, b := a·s+e+∆m) ∈ RLWE s,Q (m) where ∆ = ⌊Q/t⌉ for some t, the modulus switching from Q to Q ′ consists in computing c ′ := c · Q ′ /Q Q ′ = ([⌊a/q⌉] Q ′ , [⌊b/q⌉] Q ′ ). Generally, c ′ is an RLWE encryption of the same message m, but with ciphertext modulus Q ′ and noise close to e/q. Because rounding is not compatible with double-CRT representation we avoid it by first subtracting [c] q from c, so that the result is a multiple of q, then we can divide by q and no rounding is needed. In more detail, we define δ a := a mod q and δ b := b mod q, then compute ĉ = (a − δ a , b − δ b ). Notice that all the coefficients of ĉ belong to qZ. Finally, we output c ′ := [ĉ/q] Q ′ = ((a − δ a ) · q −1 , (b − δ b ) · q −1 ) mod Q ′ . To subtract δ a from a we first need to use FastBaseExtension from q to Q ′ to obtain δ a in base Q. The same is needed for b. Each FastBaseExtension costs ℓ NTTs and O(kℓN ) modular multiplications, where N is the degree of the modulus polynomial. Multiplying by q −1 modulo Q ′ means that we have to multiply each residue of c ′ modulo q i , for k ≤ i ≤ ℓ − 1 by the inverse of q modulo q i . This step just costs O(N · (ℓ − k)) integer modular multiplications. Thus, the overall number of operations 2ℓ NTTs and O(kℓN ) multiplications on Z q i . Algorithm 13: ModSwitch Algorithm Input: c = (a, b) ∈ RLWE s,Q (m), Q ′ such that Q ′ |Q Output: c ′ ∈ RLWE s,Q ′ (m) Complexity: 2ℓ NTT, O(kℓN ) √ multiplications on Z q i Noise growth: E → O(E/q + N · S) 1 δ a = FastBaseExtension Q ′ ,q (a mod q) 2 δ b = FastBaseExtension Q ′ ,q (b mod q) 3 ĉ = (a − δ a , b − δ b ) −1 4 c = [ĉ/q] Q ′ = (a − δ a ) · q , (b − δ b ) · q −1 mod Q ′ After modulus switching, there is a ϵ such that ∥ϵ∥ ∞ ≤ 1 and the noise changes from e to e ′ = (e + δ a · s − δ b )/q + m · ϵ. Because both a and b are (indistinguishable from) uniform modulo Q, both δ a and δ b are uniform modulo q, thus, they are (q · √ 2π)-subgaussians. √ Therefore, if e is E-subgaussian and s is S-subgaussian, we have e ′ is (E/q + N · S · 2π + 2 2π)-subgaussian. Simplifying, the modulus switching changes the noise from an E-subgaussian to a O(E/q + N · S)-subgaussian. Key switching The key-switching procedure can be divided into two steps, where the first step uses the secret key to generate a public key-switching key, and the second step consists of using the key-switching key to actually perform the key switching. We denote by R̃ Q KS ds (z, E) the set of key-switching keys from a key z to a key s, having E- subgaussian noise. Given s and z, we generate K ∈ R̃ Q KS ds (z, E) as K = [a k | b k := a k · s + e k + z · g] ∈ R q d×2 , where g = (Q 1 · Q̂ 1 , . . . , Q d · Q̂ d ) is the CRT gadget vector, that is, for 1 ≤ i ≤ d, row i (K) ∈ R̃ Q LWE s (∆ i · z, E), where ∆ i := Q i · Q̂ i . To key switch a ciphertext, c = (a, b) ∈ R̃ Q LWE z (∆ · m), we basically have to compute the CRT decomposition of a and multiply it by both columns of K. This is shown in detail in Algorithm 14. Algorithm 14: Key switching Input: c = (a, b) ∈ R̃ Q LWE z (∆ · m, E) and K ∈ R̃ Q KS ds (z, E k ), both in double-CRT form. Output: c ′ ∈ R̃ Q LWE s (∆ · m, E ′ ) Complexity: d · ℓ NTTs and √ O(ℓ 2 · p) products on Z q i Noise growth: E ′ = O(E Q + dp · D · E k ), where D = max(D 1 , ..., D d ) ▷ Consider that Q = ℓi=1 q i and D i is a product of k primes, with ℓ = k · d 1 for 1 ≤ i ≤ d do ā i := a mod D i ▷ Each base extension costs ℓ NTTs and O(k · ℓ · p) multiplications on Z q i ã i = FastBaseExtension(ā i , D i , Q/D i ) ∈ R̃ Q ▷ The following lines cost zero NTTs and O(2 · d · p) modular products a := (ã 1 , ..., ã d ) ∈ R̃ dQ 5 â = a · col 1 (K) 6 b̂ = a · col 2 (K) ▷ Noise: O( dp · D · E k )-subgaussian 7 c = (−â, b − b̂) ∈ R̃ Q 8 return c Automorphism D.1 Given a ciphertext c = (a, b) ∈ R̂ Q LWE s (∆ · m) and an integer u ∈ Z ∗ p , we apply the Galois automorphism X 7→ X u to both a and b. This operation maps c to another RLWE ciphertext encrypting m(X u ) mod X p − 1. It also has the side effect of changing the key to s(X u ), thus, a key switching is needed to go back to the original key s(X). Applying the automorphism itself is done by simply rotations of coefficients, which is essentially for free, thus, the cost and the noise growth are only due to the key-switching step. We show it in detail in Algorithm 15. We are most interested in the particular case where we encrypt an integer v as X v , since the automorphism allows us to obtain an encryption of u · v mod p as X u·v . Algorithm 15: Automorphism Input: c = (a, b) ∈ R̃ Q LWE s (∆ · m, E), u ∈ Z p , and K ∈ R̃ Q KS ds (s(X u ), E k ). Both c and K in double-CRT form. Output: c ′ ∈ R̃ Q LWE s (∆ · m(X u ), E ′ ) Complexity: d · ℓ NTTs and √ O(ℓ 2 · p) products on Z q i Noise growth: E ′ = O(E + dp · D · E k ), where D = max(D 1 , ..., D d ) u mod p 1 Let η be the mapping X 7→ X u 2 (â, b̂) = (η(a), η(b)) ∈ R̃ Q LWE s(X u ) (∆ · m(X ), E) u 3 c = KeySwt(â, b̂, K) ∈ R̃ Q LWE s (∆ · m(X ), E ) 4 return c Detailed algorithm for ring packing E Algorithm 16: PackLWE Algorithm from [29] nℓ×2 with Input: [(a (i) , b (i) )] i First, notice that   Q k+1 · Q̂ k+1 · α k+1 ..     .     · Q̂ · α d d d  ∈ Z 2(d−k)×2 . Ḡ := π k (G) =    · Q̂ · α k+1 k+1 k+1     .. ..   . . Q d · Q̂ d · α d But we see that for k + 1 ≤ i ≤ d, Q i = Q/D i = (Q ′ /D i ) · D (k) = Q ′ i · D (k) , thus all entries are divisible by D (k) . Also, Q̂ i = [(Q/D i ) −1 ] D i = [(Q ′ /D i ) −1 · (D (k) ) −1 ] D i = Q̂ ′ i · (D (k) ) −1 mod D i . Therefore, by defining α i ′ := α i · (D (k) ) −1 mod D i , we have   ′ Q k+1 · Q̂ ′ k+1 · α k+1 ..     .     π k (G)  Q d · Q̂ d · α d  ∈ Z 2(d−k)×2 . = G :=   · Q̂ · α D (k) k+1  k+1  k+1   .. ..   . . Q ′ d · Q̂ d · α d ′ Now, let y := CRT −1 (a, b). To show that y · G ′ = α ′ · (a, b) mod Q ′ , notice that the product by the first column of G ′ , modulo Q ′ , gives us d X (Q ′ i · Q̂ ′ i ) · α i ′ · [a] D i y · col 1 (G ) = i=k+1 = CRT([α ′ · a] D k+1 , ..., [α ′ · a] D d ) = CRT([(D (k) ) −1 · α] D k+1 , ..., [(D (k) ) −1 · α] D d ) · CRT([a] D k+1 , ..., [a] D d ) = α ′ · a The same argument shows that y · col 2 (G ′ ) = α ′ · b mod Q ′ . F.2 Lemma and proof of correctness of MsgExtract Lemma 11 (Correctness of MsgExtract). Let the input ciphertext be C̃ ∈ R̃ Q GSW ds (α · X ∆·m+e , E), with ∥e∥ < ∆/2. Let the plaintext space be Z t for some t ≥ 2. Let s ∈ Z N be the coefficient vector of s. For any function f : Z t → Z t , define the “test polynomial” t(X) ∈ R̃ as   ∆−1 2∆−1 t∆−1 X X X t(X) = X ∆/2 ·  f (0) · X p−i + f (1) · X p−i + ... + f (t − 1) · X p−i  . i=∆ i=(t−1)·∆ Then, Algorithm 10, MsgExtract, outputs an LWE ciphertext LWE p s (⌊Q/t⌉ · f (m), E ′ ) ∈ Z p+1 Q , where E = O( dp · D · E). Proof. The correctness follows from the standard observation that the constant term of g(X) := t(X) · X ∆·m+e is equal to f (m). This is essentially the same argument used in the extraction algorithms of [13,8]. Thus, by the correctness of the external product, c ′ encrypts g(X) such that g 0 = f (m). The rest of the procedure just extracts from c ′ an LWE sample corresponding to the first coefficient, hence, encrypting g 0 . The cost and noise growth are simply given by the external product, Algorithm 3, but with the number of NTTs divided by two, since the first polynomial in the external product is zero. F.3 Lemma about GSW key switching with less noise growth Lemma 12 (Correctness and cost of GSW key switching with parallel reconstruction). On input C ∈ R̃ Q GSW dz (α·m, E), K z ∈ R̃ Q KS ds (z, E k ), K s ∈ R̃ Q KS ds (s, E z ), and K sz ∈ R̃ Q KS ds (s· z, E s ), Algorithm 3 outputs C ′ ∈ R̃ Q GSW ds (α · m, E ′ ) where p · ( d · D · E sz + d · D · E s + ∥s∥ · E) . E ′ = O Moreover, it requires 3 · d 2 · ℓ NTTs and O(d · ℓ 2 · p) products on Z q i . Proof. The correctness of the first d rows of the output C ′ follows from the correctness of the key switching for R/CLWE samples, Algorithm 14. For the last d rows, consider the following. d×2 Write K s := [a s | b s := a s ·s+e s +s·g] ∈ R̃ d×2 Q and K sz := [a k | b k := a k ·s+e k +s·z·g] ∈ R̃ Q , where g ∈ Z d is the CRT gadget vector. Also, write (a, b) = row i (C) with b = a · z + e + ∆ i · m. Then y · col 2 (K s ) = y · a s · s + y · e s + s(az + e + ∆ i · m) = y · a s · s + y · e s + a · s · z + e · s + ∆ i · m · s and h · col 2 (K sz ) = h · a k · s + he k + a · s · z. Hence, b ′ := h · col 2 (K sz ) − y · col 2 (K s ) = (h · a k − ya s ) ·s + h · e k − y · e s − e · s −∆ i · m · s. | {z } | {z } a ′ e ′ By defining D = max(D 1 , ..., D d ), we have that e ′ is E ′ -subgaussian, where p p E ′ ∈ O( dp · D · E sz + dp · D · E s + p · ∥s∥ · E). Thus, (a ′ , b ′ ) ∈ R̃ Q LWE s (−∆ i · m · s, E ′ ). Now, it remains to analyze the cost. The d RLWE key switchings executed in line 2 cost, in total, d 2 · ℓ NTTs and O(d · ℓ 2 · p) products on Z q i . All the fast base extensions cost in total 2 · d 2 · ℓ NTTs and O(d · ℓ 2 · p) modular products. The remaining operations just cost 4 · d · p modular products. Therefore, the algorithm requires 3 · d 2 · ℓ NTTs and O(d · ℓ 2 · p) products on Z q i . F.4 Proof of Lemma 7, about noise growth of Algorithm 8 Proof. Algorithm 8 can be divided into three distinct steps: – The splitting step, where the vectors g passed to the recursive calls are defined. This does not introduce any additional error. – The base case of the recursion, where the NTT is computed with a quadratic algorithm. – The recombination step, lines 12 to 15. First consider the base case, where the quadratic step is applied to vectors of dimension N/m ρ . In this step, each a k is defined as the output of Algorithm 7 on ciphertexts C i ∈ R̃ Q GSW ds (α · X f i , E). Thus, by the noise analysis done in Algorithm 7, at the end of the base case, we have GSW ciphertexts with E (ρ) -subgaussian noise, where ! ! r r p N N · d · p · D · ∥s∥ · E + dp · D · E s + · p · ∥s∥ · E KS E (ρ) = O m ρ m ρ where E KS = O( dp · D · E k ). Now, for 2 ≤ i ≤ ρ, let E (i) be the subgaussian parameter of the noise of the ciphertexts used in the recombination step of the i-th recursive level. At this stage, each a j is computed as an inner product with m coefficients, hence the noise in the output of the i-th recursive level is E (i−1) -subgaussian, where E (i−1) is obtained by applying the noise growth formula of Algorithm 7 with input noise E (i) and vector dimension equal to m, that is, E (i−1) = O α · E (i) + β , where α = m · d · D · p · ∥s∥ and β := dp · D · E s + p · ∥s∥ · E 1 + p · ∥s∥ · m · E KS . Iterating this formula gives us ρ−2 X ! E (1) = O(α · E (2) + β) = · · · = O α ρ−1 · E (ρ) + β By the definition of E (ρ) , we have N · ( d · D · p · ∥s∥) ρ · E + α ρ−1 p E (1) = O α i . ρ−2 X ! ! r N √ · p · ∥s∥ · E KS m ρ α i dp · D · E s + + β . Finally, by absorbing the √ lowest terms in the big-Oh notation, assuming that E s is constant, and recalling that E KS = O( dp · D · E k ), we obtain !! r N √ (1) ρ ρ−1 · d · D · p · ∥s∥ · E k E = O N · ( d · D · p · ∥s∥) · E + α m ρ = O N · ( d · D · p · ∥s∥) ρ · (E + E k ) G Number of NTTs in homomorphic inverse NTT Let T (N ) be the number of NTTs over Z q i that are executed during the homomorphic evaluation of the inverse NTT, Algorithm 8. Firstly, let’s consider that no ciphertext shrinking is used, so d and ℓ are constant in all the recursive levels. We can see that T (N ) = m · T (N/m) + R(N ) where m·T (N/m) accounts for the m recursive calls on vectors of dimension N/m and R(N ) is the number of NTTs of the recombination step. Assuming that the sums are implemented with EvalScalarProd, Algorithm 7, which cost 3 · m · d 2 · ℓ NTTs, we have R(N ) = N · (3 · m · d 2 · ℓ) = 3 · N · m · d 2 · ℓ. Therefore, T (N ) = m · T (N/m) + 3 · N · m · d 2 · ℓ. Iterating this up to ρ recursive levels, we have T (N ) = m · T (N/m) + 3 · N · m · d 2 · ℓ = m · (m · T (N/m 2 ) + 3 · (N/m) · m · d 2 · ℓ) + 3 · N · m · d 2 · ℓ = m 2 · T (N/m 2 ) + 3 · 2 · N · m · d 2 · ℓ . = .. = m ρ · T (N/m ρ ) + 3 · ρ · N · m · d 2 · ℓ Then, we run the homomorphic quadratic inverse NTT on dimension N/m ρ . Since on dimension k, this algorithm executes k times the homomorphic scalar product of dimension k, its cost is k · (3 · k · d 2 · ℓ). Therefore, using k = N/m ρ , the total number of NTTs is N ρ ρ 2 + ρ · m . T (N ) = m · 3 · (N/m ) · d · ℓ + 3 · ρ · N · m · d · ℓ = 3 · N · d · ℓ · m ρ To generalize this analysis to the case where shrinking is used, let’s assume that we shrink the ciphertexts at the end of each recursive call. Thus, considering that we have recursive depth ρ, we have different dimensions and number of primes, d i and ℓ i for 0 ≤ i ≤ ρ, where ℓ ρ is the number of primes that we have in the very beginning (thus, d ρ > d ρ−1 > ... > d 0 and ℓ ρ > ℓ ρ−1 > ... > ℓ 0 ). Now, the formula for the number of NTTs becomes T (N, i) = m · T (N/m, i + 1) + 3 · N · m · d 2 i · ℓ i + 4 · N · d i · ℓ i+1 where the last term, 4 · N · d i · ℓ i+1 , accounts for the number of NTTs executed by the shrinking algorithm to switch from dimension (d i+1 , ℓ i+1 ) to (d i , ℓ i ) the n ciphertexts output by the m recursive calls. By starting with i = 0 and iterating ρ times again, we have T (N, 0) = m · T (N/m, 1) + 3 · N · m · d 20 · ℓ 0 + 4 · N · d 0 · ℓ 1 = m 2 · T (N/m 2 , 2) + 3 · N · m · d 21 · ℓ 1 + 4 · N · d 1 · ℓ 2 + 3 · N · m · d 20 · ℓ 0 + 4 · N · d 0 · ℓ 1 = m 2 · T (N/m 2 , 2) + 3 · N · m · d 21 · ℓ 1 + d 20 · ℓ 0 + 4 · N · (d 1 · ℓ 2 + d 0 · ℓ 1 ) . = .. ! ! ρ−1 ρ−1 X X = m ρ · T (N/m ρ , ρ) + 3 · N · m · d 2 i · ℓ i + 4 · N · d i · ℓ i+1 Now, using 3·(N/m ρ ) 2 ·d 2 ρ ·ℓ ρ for the number of NTTs of the quadratic step, i.e., T (N/m ρ , ρ), the total number of NTTs used in the homomorphic inverse bootstrapping with one layer of shrinking after each recursive level is ! ! ρ−1 ρ−1 X X 3 · N 2 · d 2 ρ · ℓ ρ +3 · N · m · d 2 i · ℓ i + 4 · N · d i · ℓ i+1 T (N, 0) = m ρ Further Improvements H In this section, we discuss some of the techniques that could be used to improve our construction or implementation. We note that, although we estimate the impact for some of them using experimental data, we do not present these techniques in our implementation. Their implementation is left as future work. Optimal Parameter Selection We choose parameters in Section 5.3 based on a manual search. However, optimizing parameters is generally a complex task, requiring extensive parameter search, application considerations, and testing [4]. As such, a more extensive and formal parameter optimization could likely improve our results both for the amortized and non-amortized versions. Memory usage The high memory requirements are certainly the main drawback of our construction, but there already are several ways of mitigating it. Table 5 shows the detailed memory requirements for our parameters. Compressed (Compr.) values consider different techniques that we can use to reduce memory requirements, but that might affect performance. Performance Optimal (Perf. Opt.) values do not consider any compression techniques, focusing solely on improving performance. Our implementation and, hence, all execution times we present in this section do not consider the compression techniques. LWE and Packing key switching keys are not included in this comparison. The table considers the following techniques: – Temporary buffer. Our algorithm needs a temporary buffer because it does not calculate the INTT in place. Instead of having a different buffer for each recursive call to the INTT, we can have a single one shared among them. This restricts parallelization and does not allow memory from shrunk ciphertexts to be freed. – State buffer. This is the array of accumulators. To save memory, we can evaluate the INTT directly over the bootstrapping key. This comes at the cost of having to load the bootstrapping key before each bootstrapping. – Automorphism key switching keys. We can use decomposed automorphism calculations, as we further discuss in the next subsection. Table 5: Memory requirements for p = 12289. N = 512 N = 1024 ℓ =3 ℓ =4 ℓ =3 ℓ =4 Perf. Opt. Compr. Perf. Opt. Compr. Perf. Opt. Compr. Perf. Opt. Compr. Bootstrapping Key 4.5 GiB 4.5 GiB 8.0 GiB 8.0 GiB 9.0GiB 9.0 GiB 16.0 GiB 16.0 GiB Automorphism key 54.0 GiB 63.0 MiB 96.0 GiB 112.0 MiB 54.0GiB 63.0 MiB 96.0 GiB 112.0MiB Temporary buffer 2.2 GiB 72.0 MiB 4.0 GiB 128.0 MiB 4.5GiB 72.0 MiB 8.0 GiB 128.0MiB State buffer 4.5 GiB 8.0 GiB 9.0GiB 16.0 GiB Total 65.3 GiB 4.6 GiB 116.0GiB 8.2 GiB 76.5GiB 9.1 GiB 136.0 GiB 16.2 GiB Decomposed Automorphisms In [24], they introduce an efficient way of reducing the number of automorphism keys by representing the automorphism generators as a product of the powers of the ring multiplicative generator. In their case, automorphism generators are in Z ∗ 2N , and they need to map them to Z N/2 × Z 2 to obtain a multiplicative generator. In ours, automorphism generators are in Z ∗ p for some prime p, so we always have a multiplicative generator of order p − 1. This technique can reduce the number of automorphism key switching from p down to just ⌈log 2 (p)⌉, which would reduce the total size of the automorphism keys 877 times for our parameters. It is hard to estimate the impact on the performance. In one hand, this technique could bring a slowdown of around 2 to 3 times, on the other, reducing drastically the memory usage reduces data movement, which speeds up the running times in practice. In [24], they also introduce the concept of window size, which defines the number of automorphism keys they actually use. In this way, they are able to provide intermediary solutions, which require larger keys but introduce less performance overhead. Reducing the size of NTTs When defining the accumulator for the non-amortized version, we are able to select values for p that are very close to the next power of two. The same cannot be done when defining p for the amortized method, as we are further limited by the necessity of a 2n-th root of unity modulo p. If the goal is just to reduce memory usage, we can use the Bluestein NTT [5], which allows evaluating multiplications directly in R̃. However, Bluestein essentially turns the transform in a convolution of size 2N , thus not improving itself. In fact, it might introduce additional overheads to the transform computation. It also requires the existence of p-th roots of unity modulo the primes Q i , which further limits our parameter selection. Nonetheless, it would reduce our memory requirements by around two times.