2.2.1 Introduction
The ring variant of learning with errors (Ring-LWE) based cryptography [
15,
16] is one of the most attractive research areas in cryptography. Ring-LWE has provided efficient and provably secure post-quantum cryptographic protocols, which include homomorphic encryption (HE) schemes [
4,
5,
9]. The development of the efficiency and security of both post-quantum cryptography and HE is strongly desirable. In fact, the standardization of post-quantum cryptography is under development by the National Institute of Standards and Technology. Moreover, HE schemes that enable us to execute the computation on encrypted data without decryption have many applications in cloud computing.
Ring-LWE is characterized by two probabilistic distributions, modulus parameters (integers) and number fields, as detailed in Sect.
2.2.2.4. Usually, cyclotomic fields are used as the underlying number fields to increase efficiency and security [
17]. However, especially in the case of HE schemes, improving the efficiency of the encryption/decryption procedures and homomorphic arithmetic operations on encrypted data while ensuring security remain important tasks.
To construct an HE scheme that can simultaneously encrypt many plaintexts efficiently, Arita and Handa proposed the use of a decomposition field, which is contained in a cyclotomic field with prime conductors, as an underlying number field for Ring-LWE [
1]. (Sect.
2.2.3 presents the details of decomposition fields and of Arita and Handa’s idea.) Arita and Handa’s HE scheme, which is called the subring HE scheme, is indistinguishably secure under a chosen-plaintext attack if the decision variant of Ring-LWE over the decomposition fields is computationally infeasible. Arita and Handa’s experiments [
1, Sect. 5] showed that the performance of the subring HE scheme is much better than that of the FV scheme based on Ring-LWE over
\(\ell \)th cyclotomic fields with prime numbers
\(\ell \), as implemented in HElib [
11].
As for the security of the subring HE scheme, Arita and Handa remarked that in the case of decomposition fields, some of the security properties of Ring-LWE in the case of cyclotomic fields are also satisfied. More concretely, there exists a quantum polynomial-time reduction from the approximate shortest vector problem on certain ideal lattices to Ring-LWE over decomposition fields, and the equivalence between the decision and search variants of Ring-LWE over decomposition fields is satisfied.
However, solving Ring-LWE is reduced to solving certain problems on lattices, such as the closest vector problem (CVP) and the shortest vector problem, and the difficulty of problems on lattices depends heavily on the structure and given bases of the underlying lattices. For example, if the shortest vector is much shorter than the second shortest vector in a certain lattice
\(\mathcal{L}\), then the shortest vector problem for lattice
\(\mathcal{L}\) would be easy. This means that the underlying number fields affect the difficulty of lattice problems arising in Ring-LWE. Hence, to ensure the security of the subring HE scheme, experimental or theoretical analyses of (lattice) attacks should be performed. However, [
1] does not provide any such analysis.
In this study, we provide an experimental analysis of the security of Ring-LWE over decomposition fields. More precisely, we compare the security of Ring-LWE over decomposition fields and of Ring-LWE over the
\(\ell \)th cyclotomic fields with some prime numbers
\(\ell \). In our experiments, we reduce the search Ring-LWE to the (approximate) CVP on certain lattices in the same way as Bonnoron et al.’s analysis [
3] because the target of Bonnoron et al.’s analysis is Ring-LWE optimized for HE. We use Babai’s nearest plane algorithm [
2] and Kannan’s embedding technique [
12] to solve the CVP. We then compare the running times, success rates, and Hermite root factors. (The root Hermite factor [
10] is usually used to evaluate the quality of lattice attacks.) We also compare the experimental results of lattice attacks against Ring-LWE over various decomposition fields to find those fields that provide weak Ring-LWE.
Our experimental results indicate that the success rates and Hermite root factors for the decomposition fields are almost the same as those for the cyclotomic fields. However, the running time for decomposition fields is longer than that for cyclotomic fields. Moreover, the difference in running time increases as the rank of the lattices increases.
Therefore, we believe that Ring-LWE over decomposition fields is more secure against the above lattice attacks than that over cyclotomic fields because the ranks of the lattices occurring in our experiments are much lower than the ranks of the lattices used in practice. This means that to construct HE schemes (or schemes of other types), fewer parameters are needed for Ring-LWE over decomposition fields than for Ring-LWE over cyclotomic fields. Therefore, as a result of our analysis, we believe that Ring-LWE over decomposition fields can be used to construct more efficient HE schemes.
2.2.2 Preliminaries
In this section, we briefly review the notation of lattices, Galois theory, number fields, and Ring-LWE. Throughout this study, \(\mathbb {Z}\), \(\mathbb {Q}\), \(\mathbb {R}\), and \(\mathbb {C}\) denote the ring of (rational) integers, field of rational numbers, field of real numbers, and field of complex numbers, respectively. For a positive integer \(m \in \mathbb {Z}\), we suppose that any element of \(\mathbb {Z}/m\mathbb {Z}\) is represented by an integer contained in the interval \(\left( -m/2, m/2 \right] \cap \mathbb {Z}\).
2.2.2.1 Lattices
An m-dimensional lattice is defined as a discrete additive subgroup of \(\mathbb {R}^m\). It is well known that for any lattice \(\mathcal{L}\subset \mathbb {R}^m\), there exist \(\mathbb {R}\)-linearly independent vectors \(\mathbf{b}_1, \ldots , and\,\mathbf{b}_n \in \mathbb {R}^m\) such that \(\mathcal{L}=\sum _{1 \le i \le n} \mathbb {Z}\mathbf{b}_i := \{ \sum _{1 \le i \le n}a_i\mathbf{b}_i \mid a_i \in \mathbb {Z}\ \}\). In other words, for a matrix \(\mathbf{B}= \left( \mathbf{b}_1, \ldots , \mathbf{b}_n \right) \) whose ith column vector is \(\mathbf{b}_j\), we have \(\mathcal{L}= \{ \mathbf{B}\mathbf{x} \mid \mathbf{x} \in \mathbb {Z}^n \}\). Then, we say that \(\{ \mathbf{b}_1, \ldots , \mathbf{b}_n \}\) is a lattice basis of \(\mathcal{L}\), and \(\mathbf{B}\) is the basis matrix of \(\mathcal{L}\) with respect to \(\{ \mathbf{b}_1, \ldots , \mathbf{b}_n \}\). The value n is called the rank of \(\mathcal{L}\), and it is denoted by \(\mathrm {rank}(\mathcal{L})\). There are infinite bases for a lattice. In fact, for any unimodular matrix \(\mathbf{U}\), all column vectors of \(\mathbf{U} \mathbf{B}\) also form a basis of \(\mathcal{L}\). An important invariant of \(\mathcal{L}\) is the determinant defined as \(\det (\mathcal{L}) := \sqrt{\det \left( \mathbf{B}\mathbf{B}^t \right) }\). This determinant is independent of basis.
There are various computationally hard problems on lattices. Here, we explain the CVP, which is a well-known problem on lattices. Given a lattice \(\mathcal{L}\) and target vector \(\mathbf{t} \in \mathbb {R}^m \smallsetminus \mathcal{L}\), the CVP on \((\mathcal{L}, \mathbf{t})\) is the problem of finding a vector \(\mathbf{x} \in \mathcal{L}\) such that for all vectors \(\mathbf{y} \in \mathcal{L}\), we have \(\Vert \mathbf{t} - \mathbf{x} \Vert \le \Vert \mathbf{t} - \mathbf{y} \Vert \). For a real number \(\gamma > 1\), the approximate CVP on \((\mathcal{L}, \mathbf{t}, \gamma )\) is the problem of finding a vector \(\mathbf{x} \in \mathcal{L}\) such that for all vectors \(\mathbf{y} \in \mathcal{L}\), we have \(\Vert \mathbf{t} - \mathbf{x} \Vert \le \gamma \Vert \mathbf{t} - \mathbf{y} \Vert \). Babai’s nearest plane algorithm and Kannan’s embedding technique are basic algorithms for solving the approximate CVP. Almost all known problems on lattices that are useful for constructing cryptographic protocols become more difficult as the ranks of the underlying lattices increase, and the quality of the two algorithms mentioned earlier depends on ranks of input lattices.
Breaking some cryptographic protocols can be reduced to solving certain computational problems on lattices, including the (approximate) CVP [
3,
8]. To solve such problems on lattices, we usually use lattice basis reduction algorithms, which transform a given basis of a lattice into a basis of the same lattice that consists of nearly orthogonal and relatively short vectors. In fact, an input of Babai’s nearest plane algorithm is an (LLL) reduced basis, and Kannan’s embedding technique outputs an appropriate vector from the reduced basis. In our experiments, to solve CVP using Babai’s nearest plane algorithm and Kannan’s embedding technique, we use the LLL algorithm [
13] and BKZ algorithm [
7,
19], which are well-known algorithms for computing such bases.
The quality of basis reduction algorithms is usually estimated by the root Hermite factor, which is defined as follows: Let \(\mathbf{b}\) be the shortest vector of a basis of a lattice \(\mathcal{L}\) with rank n, which has been reduced by a basis reduction algorithm \(\mathcal{A}\). Then, the root Hermite factor \(\delta _{\mathcal{A}, \mathcal{L}}\) is defined as a constant satisfying \( \delta ^n_{\mathcal{A}, \mathcal{L}} := \Vert \mathbf{b}\Vert /\det (\mathcal{L})^{1/n}. \) Better basis reduction algorithms provide smaller Hermite root factors.
2.2.2.2 Galois Theory
To describe decomposition fields, we need to describe Galois theory.
Let K be a field and L an extension field of K; we denote this situation by L/K. The field L is a K-vector space, and the degree of extension of L/K, denoted by [L : K], is defined as the dimension of L as K-vector space. If M is a subfield of L containing K as a subfield, i.e., \(K \subset M \subset L\), then we call M an intermediate field of L/K. If L/K satisfies \([L:K] < \infty \), then L/K is called a finite extension of K. If M is an intermediate field of L/K with \([L:K] < \infty \), then we have \([L:K]=[L:M][M:K]\). If for any \(\alpha \in L\), there exists a nonzero polynomial \(f(x) \in K[x]\) such that \(f(\alpha ) = 0\), then L/K is called an algebraic extension of K. It is known that all finite extensions are algebraic extensions.
From now on, we suppose that L/K is a finite algebraic extension. For any \(\alpha \in L\), the minimal polynomial over K of \(\alpha \) is defined as the monic polynomial \(f(x) \in K[x]\) with the lowest degree of all polynomials in K[x] that vanish at \(\alpha \). We denote \(\mathrm {Irr}(\alpha , K)(x)\) as the minimal polynomial over K of \(\alpha \). Note that the minimal polynomial over K of \(\alpha \) coincides with the monic irreducible polynomial over K that vanishes at \(\alpha \). For a subset \(S \subset L\), we denote K(S) as the smallest subfield of L among subfields containing K and S. We call K(S) the field generated by S over K. If L is generated by one element \(\theta \in L\) over K, i.e., \(L = K(\theta )\), then we have an isomorphism \(L \cong K[x]/\left( \mathrm {Irr}(\theta , K)(x) \right) \) by \(\theta \mapsto x\) (mod. \(\left( \mathrm {Irr}(\theta , K)(x) \right) \). This implies that \([K(\theta ):K] = \deg \mathrm {Irr}(\alpha , K)\).
Next, we describe separable, normal, and Galois extensions of fields. If
\(\mathrm {Irr}(\alpha , K)(x)\) for any
\(\alpha \) that has no multiple roots, then
L/
K is called a separable extension of
K. If
L contains all roots of
\(\mathrm {Irr}(\alpha , K)(x)\) for any
\(\alpha \in L\), then
L/
K is called a normal extension of
K. If all algebraic extensions of
K, including infinite algebraic extensions, are separable, then
K is called a perfect (field). It is known that fields with characteristic zero and any finite field are perfect, and that any finite separable extension field can be generated by one element. If
L/
K is a separable and normal extension of
K, then
L/
K is called a Galois extension of
K. Let
\(\Omega \) be a sufficiently large field containing
K such that any ring-homomorphism
\(\phi \) fixing
K, i.e.,
\(\phi (a) = a\) for any
\(a \in K\), to
L satisfies
\(\phi (L) \subset \Omega \). We define the set of all ring-homomorphisms by fixing
K to the range
L to
\(\Omega \) as follows:
$$ \mathrm {Hom}_K(L, \Omega ) := \left\{ \sigma : L \hookrightarrow \Omega \mid \sigma (a) = a, \forall a \in K \right\} . $$
(Note that any nonzero ring-homomorphism between fields is injective.) Let
L/
K be separable with
\([L:K] = n\) and
\(L = K(\theta )\). Let
\(\theta = \theta _1, \ldots , \theta _n\) be all roots of
\(\mathrm {Irr}(\theta , K)(x)\). For any
\(\sigma \in \mathrm {Hom}_K(L, \Omega )\), we have
\(\sigma \left( \mathrm {Irr}(\theta , K)(\theta ) \right) = \mathrm {Irr}(\theta , K) (\sigma (\theta )) = 0\). This means that
\(\sigma (\theta ) = \theta _i\) for some
\(i = 1, \ldots , n\). This then implies
\(\# \mathrm {Hom}_K(L) = n\). (Any
\(\tau \in \mathrm {Hom}_K(L, \Omega )\) is completely determined by the image of
\(\theta \) under
\(\tau \) because
\(\tau \) fixes
K.)
Moreover, if L/K is normal, then \(\sigma \) induces an isomorphism \(L \cong L\). Note that \(L = K(\theta ) \cong K(\theta _i)\) for any \(i = 1, \ldots , n\) because these fields are isomorphic to \(K[X]/\left( \mathrm {Irr}(\theta , K) \right) \). Therefore, we may take L as \(\Omega \) and can write \(\mathrm {Aut}_K(L)=\mathrm {Hom}_K(L, \Omega )\).
Now, we can describe the fundamental theorem of Galois theory (for finite field extensions). Let
L/
K be a finite Galois extension of
K. Then, we can write
\(\mathrm {Gal}(L/K) = \mathrm {Aut}_K(L)\). For any subgroup
\(H \subset \mathrm {Gal}(L/K)\) and an intermediate field
M of
L/
K, we define
$$\begin{aligned} L^H:= & {} \{ a \in L \mid \sigma (a) = a, \forall \sigma \in H \}, \\ G_M:= & {} \{ \sigma \in \mathrm {Gal}(L/K) \mid \sigma (a) = a, \forall a \in M \}. \end{aligned}$$
We note that
L/
M is a Galois extension with
\(\mathrm {Gal}(L/M) = G_M\). It is not difficult to see that
\(L^H\) is an intermediate field of
L/
K and that
\(G_M\) is a subgroup of
\(\mathrm {Gal}(L/K)\). We can define two maps with respect to
L/
K. One is a map
\(\Phi \) from
\(A := \{ M \subset L \mid \! M{ isanintermediatefieldof}L/K \}\) to
\(B := \{ H \subset \mathrm {Gal}(L/K)\! \mid H{ isasubgroupof}\mathrm {Gal}(L/K) \}\) by
\(M \mapsto G_M\). The other is a map
\(\Psi \) from
B to
A by
\(H \mapsto L^H\). The fundamental theorem of Galois theory is as follows:
For a proof of Theorem
2.2, see [
18] for example. (It is easy to prove (2) of Theorem
2.2 from the definitions of
\(\Phi \) and
\(\Psi \).)
2.2.2.3 Number Fields
To describe Ring-LWE and decomposition fields, which play central roles in this paper, we need some notations from algebraic number theory.
An (algebraic) number field is a finite extension field of \(\mathbb {Q}\). Let K be a number field with extension degree \([ K : \mathbb {Q}] = n\). An element \(a \in K\) is called an algebraic integer if there exists a monic polynomial \(f \in \mathbb {Z}[x]\) such that \(f(a) = 0\). The ring of integers \(O_K\) of K is defined as a subring of K consisting of all algebraic integers of K. The ring \(O_K\) has an integral basis (\(\mathbb {Z}\)-basis) \(\{ u_1, \ldots , u_n \}\), i.e., for any element \(u \in O_K\), there exist integers \(a_1, \ldots , a_n\) such that u is uniquely written as \(u = \sum _{1\le i \le n}a_iu_i\). It is well known that any (integral) ideal I of \(O_K\) is uniquely factored into products of some prime ideals, i.e., there exist prime ideals \(\mathcal{P}_1, \ldots , \mathcal{P}_m\) satisfying \(I = \mathcal{P}_1^{e_1} \cdots \mathcal{P}_m^{e_m}\) for \(e_i \ge 1\). If \(I = pO_K\) for a prime number p and K is a Galois extension of \(\mathbb {Q}\), then we have \(O_K/\mathcal{P}_i = \mathbb {F}_{p^{d}}\) for some \(d \in \mathbb {N}\) and all \(e_i\)’s are mutually equal. Moreover, we have \(med = n\), where \(e := e_i\), and if all \(e_i\)’s are equal to 1 (resp. all \(e_i\)’s and d are equal to 1), then we say that p is unramified (resp. splits completely) in K. Any prime ideal of \(O_K\) is a maximal ideal in \(O_K\), and thus we have \(P_i + P_j = O_K\) for any \(i \ne j\). This induces an isomorphism of rings \( O_K/\mathcal{P}_1 \cdots \mathcal{P}_m \cong O_K/\mathcal{P}_1 \times \cdots \times O_K/\mathcal{P}_m \).
2.2.2.4 Ring-LWE Problem
Let K and \(O_K\) be as above. Let \(\chi _{\mathrm {secret}}\) and \(\chi _{\mathrm {error}}\) be probabilistic distributions on \(O_K\) and let p be an integer. We denote by \(O_{K, p}\) the residue ring \(O_K/pO_K\). For a probabilistic distribution \(\chi \) on a set X, we write \(a \leftarrow \chi \) when \(a \in X\) is chosen according to \(\chi \). We denote U(X) as the uniform distribution on X. The Ring-LWE distribution on \(O_{K,p}\), denoted by \(\mathrm {RLWE}_{K, p, \chi _{\mathrm {error}}, \chi _{\mathrm {sec}}}\), is defined as a probabilistic distribution that takes elements of the form \((a, as + e)\) with \(a \leftarrow U(O_{K, p})\), \(s \leftarrow \chi _{\mathrm {secret}}\), and with \(e \leftarrow \chi _{\mathrm {error}}\). The Ring-LWE problem has two variants. One is the problem of distinguishing \(\mathrm {RLWE}_{K, p, \chi _{\mathrm {error}}, \chi _{\mathrm {sec}}}\) from \(U(O_{K, p} \times O_{K, p})\), which is called the decision Ring-LWE problem. The other is a problem of finding \(s \in O_{K, p}\), given arbitrarily many samples \((a_i, a_is + e_i) \in O_{K, p} \times O_{K, p}\) chosen according to \(\mathrm {RLWE}_{K, p, \chi _{\mathrm {error}}, \chi _{\mathrm {sec}}}\), which is called the search Ring-LWE problem.
The Ring-LWE problem is expected to be computationally difficult even with quantum computers. It is proved that the decision Ring-LWE problem is equivalent to the search problem if
K is a cyclotomic field and if
p is a prime number and (almost) splits completely in
K [
16]. In addition, this equivalence is generalized to the cases where
\(K/\mathbb {Q}\) is a Galois extension and where
p is unramified in
K [
6]. Moreover, there is a quantum polynomial-time reduction from the search Ring-LWE to the shortest vector problem on certain ideal lattices.
2.2.3 Ring-LWE over Cyclotomic and Decomposition Fields
In this section, we describe why Arita and Handa proposed the use of decomposition fields as the underlying number fields of Ring-LWE to construct efficient HE schemes.
2.2.3.1 Cyclotomic Fields and Decomposition Fields
First, we briefly review cyclotomic fields. For a positive integer m, let \(\zeta _m \in \mathbb {C}\) be a primitive mth root of unity and \(n = \varphi (m)\), where \(\varphi (\cdot )\) denotes Euler’s totient function. Then, \(K := \mathbb {Q}\left( \zeta _m \right) \) is called the mth cyclotomic field. The ring of integers of K coincides with \(R := \mathbb {Z}[\zeta _m]\). Any prime number p that does not divide m is unramified in K, and if \(p \equiv 1\) (mod. m), then p splits completely in K. Here, \(K/\mathbb {Q}\) is a Galois extension of degree \([K : \mathbb {Q}] = n\), and its Galois group \(\mathrm {Gal}(K/\mathbb {Q})\) is isomorphic to \(\left( \mathbb {Z}/m\mathbb {Z}\right) ^{*}\).
Next, we describe the decomposition fields of number fields. Let L be a number field, and suppose that \(L/\mathbb {Q}\) is a Galois extension and that its Galois group \(G := \mathrm {Gal}(L/\mathbb {Q})\) is a cyclic group. Let p be a prime number that is unramified in L and satisfies \(pO_L = \mathcal{P}_1 \cdots \mathcal{P}_g\), where the \(\mathcal{P}_i\)’s are the prime ideals of \(O_L\). Let \(G_Z\) be a subgroup of G that consists of all elements \(\rho \) fixing all \(\mathcal{P}_i\), i.e., \(\rho (\mathcal{P}_i) = \mathcal{P}_i\) for \(1\le i \le g\), and Z is the fixed field of \(G_Z\). Then, we call Z the decomposition field with respect to p. The field Z is a number field and the ring of integers of Z is \(O_Z = O_L \cap Z\). Suppose \(\mathrm {p}_i := O_Z \cap \mathcal{P}_i\). Then, we have \(pO_Z = \mathrm {p}_1 \cdots \mathrm {p}_g\). A generator \(\sigma \) of \(G_Z\) acts on \(O_L/\mathcal{P}_i \cong \mathbb {F}_{p^d}\) as the pth Frobenius map, i.e., \(\sigma (x) \equiv x^p\) (mod. \(\mathcal{P}_i\)) for all \(x \in O_L\) and for \(1 \le i \le g\). Therefore, we have \(O_Z/\mathrm {p}_i \cong \mathbb {F}_p\) and \([Z : \mathbb {Q}] = g\), i.e., p splits completely in Z.
2.2.3.2 Cyclotomic Fields Versus Decomposition Fields
Let
K,
L, and
Z be as above and
p be a prime number that is unramified in
K and splits completely in
Z. Assume that
L is the
\(\ell \)th cyclotomic field with a prime number
\(\ell \). As we mentioned in Sect.
2.2.1, cyclotomic fields are usually used as the underlying number fields of Ring-LWE. From the viewpoint of the efficiency of Ring-LWE based schemes, there are good
\(\mathbb {Z}\)-bases of the rings of integers of
K and
Z [
1,
17]. As for the security of the Ring-LWE, in the cases of
K and
Z, both the equivalence and the reduction mentioned in Sect.
2.2.2.4 are satisfied because both
\(K/\mathbb {Q}\) and
\(Z/\mathbb {Q}\) are Galois extensions.
The main difference between
K and
Z is the algebraic structures of their rings of integers modulo
p. Because
p is unramified in
K, we have
\(O_{K, p} \cong O_K/\mathcal{P}_1 \times \cdots \times O_K/\mathcal{P}_k\) and
\(O_K/\mathcal{P}_i \cong \mathbb {F}_{p^d}\) for
\(1 \le i \le k\) and for
\(d > 1\), where the
\(\mathcal{P}_i\)’s are prime ideals in
\(O_K\) lying over
p, i.e.,
\(pO_K = \mathcal{P}_1 \cdots \mathcal{P}_k\). The FV scheme [
9], which is an HE scheme based on Ring-LWE, uses
\(O_{K, p}\) as its plaintext space, and thus, the FV scheme (or any HE scheme with the same plaintext space) can encrypt and execute several additions of
\(dk = n = [K : \mathbb {Q}]\) plaintexts in
\(\mathbb {F}_p\) simultaneously. However, the FV scheme cannot execute the multiplication of the same number of plaintexts in
\(\mathbb {F}_p\) simultaneously. To execute the multiplication of plaintexts in
\(\mathbb {F}_p\), we can only use
\(\mathbb {F}_p \times \cdots \times \mathbb {F}_p\) (the direct product of
k finite fields) as the plaintext space.
In contrast, because p splits completely in Z, we have \(O_{Z, p} \cong O_Z/\mathrm {p}_1 \times \cdots \times O_Z/\mathrm {p}_g\) and \(O_Z/\mathrm {p}_i \cong \mathbb {F}_p\) for any \(1 \le i \le g\), where the \(\mathrm {p}_i\)’s are prime ideals in \(O_Z\) lying over p. This means that one can encrypt \(g = [Z : \mathbb {Q}]\) plaintexts simultaneously. Moreover, one can execute additions and multiplications of the same number of plaintexts in \(\mathbb {F}_p\) simultaneously. Because the extension degrees g and n are directly related to the ranks of the lattices occurring in known lattice attacks, we should set \(g \approx n\) to compare the security of Ring-LWE over these fields. Therefore, the HE scheme over Z can encrypt and operate d times as many plaintexts as the FV scheme over K simultaneously.