Fast polynomial arithmetic in homomorphic encryption with cyclo-multiquadratic fields

Cryptography and Communications (2025) 17:741–775 https://doi.org/10.1007/s12095-024-00771-6 RESEARCH Fast polynomial arithmetic in homomorphic encryption with cyclo-multiquadratic fields Iván Blanco-Chacón1,3 ·Alberto Pedrouzo-Ulloa2·Rahinatou Y. Njah Nchiwo3· Beatriz Barbero-Lucas4 Received: 23 April 2024 / Accepted: 22 December 2024 / Published online: 30 January 2025 © The Author(s) 2025 Abstract We discuss the advantages and limitations of cyclotomic fields to have fast polynomial arithmetic within homomorphic encryption, and show how these limitations can be overcome by replacing cyclotomic fields by a family that we refer to as cyclo-multiquadratic. This family is of particular interest due to its arithmetic efficiency properties and to the fact that the Polynomial Learning with Errors (PLWE) and Ring Learning with Errors (RLWE) problems are equivalent for it. Likewise, we provide exact expressions for the condition number for any cyclotomic field, but under what we call the twisted power basis. As a tool for our result, we obtain refined polynomial upper bounds for the condition number of cyclotomic fields with up to 6 different primes dividing the conductor. From a more practical side, we also show that for this family, swapping between NTT (Number Theoretic Transform) and coefficient representations can be achieved at least twice faster than for the usual cyclotomic family. Keywords Ring Learning with Errors ·Polynomial Learning with Errors · Condition Number ·Cyclotomic polynomials ·Homomorphic Encryption · Number Theoretic Transforms Mathematics Subject Classification (2010) 11T71 ·94A60 ·11Y16 Iván Blanco-Chacón and Alberto Pedrouzo-Ulloa contributed equally to this work. BIván Blanco-Chacón iv[email protected] BAlberto Pedrouzo-Ulloa [email protected] BRahinatou Y. Njah Nchiwo [email protected] BBeatriz Barbero-Lucas [email protected] 1Departament of Physics and Mathematics, University of Alcalá, Alcalá, Spain 2atlanTTic, Universidade de Vigo, Vigo 36310, Galicia, Spain 3Department of Mathematics and Systems Analysis, Aalto University, Espoo, Finland 4School of Mathematics and Statistics, University College Dublin, Dublin, Ireland 123 742 Cryptography and Communications (2025) 17:741–775 1 Introduction and motivation Lattices have become a fundamental tool for the construction of modern and efficient cryptographic primitives. Notably, they bring about several relevant properties; firstly, from a theoretical perspective, lattice-based cryptographic primitives admit quantum polynomial reductions from worst-case to average-case supposedly hard lattice problems, which typically correspond to approximating within polynomial factors the Shortest Vector Problem (SVP) or Closest Vector Problem (CVP) over general lattices, or even over the more structured class of ideal lattices. Despite the fact that the precise theoretical hardness of all these worst-case assumptions is not well established yet, confidence on its difficulty has been gained during the last years by the fact that there are already numerous works studying their concrete bit security [1], and there are also related theoretical results proving that SVP for general lattices and with small approximation factors is NP-hard [2,3]. Secondly, latticebased primitives are easier to implement and require, in general, much smaller key sizes than other post-quantum proposals. At this point, it is worth mentioning that comparing to more traditional quantum-vulnerable cryptographic assumptions (e.g., hardness of integer factorisation for RSA and the discrete logarithm problem for Diffie-Hellman), lattice-based primitives introduce a non-negligible size overhead on both the encrypted data and the keys. Even so, in return they are usually simple, efficient and highly parallelizable, while also comparing favourably with the use of post-quantum assumptions. Actually, the success caused by their benefits is confirmed by the fact that, out of the four proposals selected in the NIST Post-Quantum Cryptography Standardization Process, three are lattice-based (see [4]). Moreover, this category has been keeping the largest number of surviving candidates along all the previous rounds. For instance, in the third round, 5 out of 7 finalists were based on structured lattice assumptions; being also the only hardness assumption keeping surviving representatives for digital signatures, Public-Key Cryptography (PKE) and Key Encapsulation Mechanisms (KEM). Finally, not only they appear as a strong substitute for conventional cryptographic primitives, but also they have shown to be very flexible, having been used to construct a wide variety of new exciting applications, e.g., Fully Homomorphic Encryption (FHE), Functional Encryption (FE), Attribute-based Encryption (ABE), etc. In particular, if we pay attention to the state-of-the-art of FHE, lattice-related assumptions are nowadays the main building block backing up its security; e.g., in the Homomorphic Encryption (HE) standardization process all included designs rely on the use of lattices. (see [5]). 1.1 The family of Learning with Errors and its equivalence between variants While the aim in lattice-based cryptography is to ground security in the hardness of the previously mentioned worst-case lattice problems, alternative average-case assumptions are often considered to build cryptographic primitives. In this case, the objective is to make use of the assumptions which better fit the needs of practical cryptographic constructions. Among them, the most prominent example is the Learning with Errors problem (LWE [6]). It has become the preferred one due to its versatility and strong security guarantees by possessing a reduction from approximate SVP over general lattices. However, applications based on LWE present a quadratic overhead with respect to the considered security parameter [7]. As a means to effectively address this limitation, Lyubashevsky et al. [7] introduced a variant called Ring Learning with Errors (RLWE) which, contrarily to LWE, is based on the 123 Cryptography and Communications (2025) 17:741–775 743 hardness of worst-case problems over ideal lattices. RLWE has proven to be more practical than LWE, removing its quadratic overhead and, consequently, enabling a noteworthy reduction in the size of public keys and the ciphertext-to-plaintext size ratio. Alternatively, the Module-LWE problem (MLWE [8,9]) was introduced as a bridge between LWE and RLWE, enabling for more (resp. less) efficient constructions than LWE (resp. RLWE), but having a reduction from problems over less structured lattices (i.e., module lattices) than ideal lattices. In general, the wide variety of structured and unstructured lattice assumptions, together with their dependency on many interrelated parameters, makes the analysis of the concrete security of lattice constructions a very relevant topic (see [10]and [1]). 1.2 PLWE and conditions for polynomial equivalence with RLWE To make the present work self-contained, we recall next the definitions of the RLWE and the PLWE problems we will work with, as well as the notion of both problems being equivalent. For a number field K, let us denote by OKits ring of integers. Let qbe a rational prime and let f(x)∈Z[x]be a monic irreducible polynomial. Denote further Of=Z[x]/( f(x)). If the polynomial f(x)is understood or not entirely relevant for the discussion, we will just write Oinstead of Of. Definition 1.1 (The RLWE/PLWE problem) Let χbe a discrete random variable with values in OK/qOK(resp. in O/qO). The RLWE (resp. PLWE) problem for χis defined as follows: For an element s∈OK/qOK(resp. O/qO) chosen uniformly at random,1aRLWEsample (resp. a PLWE sample) is a pair (a,as +e)where ais sampled uniformly at random from OK/qOK(resp. from O/qO)andeis sampled from the distribution χ. The RLWE (resp. PLWE) distribution is the probability distribution whose support is the set of all possible RLWE (resp. PLWE samples) and its probability function is that induced from the uniform and from the χdistributions in their respective sets. The RLWE (resp. PLWE) problem consists in giving an adversary access to arbitrarily many samples of the RLWE (resp. PLWE) distribution and asking the adversary to recover swith non-negligible advantage. Remark 1.2 First, it is worthy to mention that the random variables χused to define both problems are discretized versions of multivariate centred Gaussian distributions (for details see [13, Section 2]). Second, Definition 1.1 is the definition of RLWE/PLWE in search version. Moreover, the original definition for the RLWE distribution in [13] is built upon the image by the canonical embedding of O∨ K, the dual of the ring of integers OK.However,as provedin[14], this dual-based definition is equivalent to the non-dual one we provide here. We are using this version as starting point, as, being equivalent to the dual one, it is more suitable for our arguments. Moreover, we refer the reader to [13]forthedecisional version of the problem. In [15], a polynomial time reduction is given from worst case SVP over ideal lattices to the PLWE problem for power-of-two cyclotomic fields. Later, in [13] ideal-SVP polynomial 1Note that several different choices for the distribution of s(i.e., the secret key distribution) are commonly used in practice, particularly in homomorphic encryption. These choices include the error distribution χ itself, ternary and binary distributions over OK/qOK(resp. O/qO), as well as distributions that produce sparse elements from OK/qOK(resp. O/qO). For more details on the distributions typically used for sin homomorphic encryption, we refer the reader to [11,12]. 123 744 Cryptography and Communications (2025) 17:741–775 time reduction was established for RLWE over cyclotomic fields under flexible conditions on the security parameters and further, in [16] the polynomial reduction was extended to noncyclotomic Galois number fields building on the same number-theoretical kind of arguments as in [13]. While the RLWE problem is formulated in terms of the ring of integers OKof an algebraic number field K, the use of more concrete ring structures is usually more suitable for cryptographic implementations. In particular, the PLWE problem provides a very convenient choice supporting efficient arithmetic [15,17]. A natural and important question which arises with PLWE is to understand under which conditions it is equivalent to RLWE, in particular in the case where Kis the splitting field of f(x)and hence OKis isomorphic (by evaluation at a root) to a sub-order in the ring Z[x]/( f(x)). More formally, following [14], [18]and[19] we recall the notion of equivalence: Definition 1.3 (Equivalence) For a monic irreducible polynomial f(x)∈Z[x],denotebyK its splitting field. We say that the RLWE and PLWE problems are equivalent if there exists an algorithm which takes any RLWE sample into a PLWE sample and viceversa in probabilistic polynomial time in the degree of K, incurring in a noise increase which is also polynomial in the degree of K. Following [14], the noise increase caused by the change of embeddings (coefficient embedding in the quotient ring and evaluation followed by canonical embedding in the ring of integers) is measured by the condition number of the corresponding matrix. We will develop this in more detail in Subsection 3.1. Notice that even if the quotient rings Z[x]/( f(x)) and OKwere isomorphic (i.e., when Kis monogenic), the problems might not be equivalent. Indeed, evaluation at a root of f(x) followed by the canonical embedding takes PLWE samples to RLWE samples in polynomial time using, for instance, Horner’s polynomial evaluation and as for the reverse algorithm, solving the corresponding Vandermonde system by Gaussian elimination takes about n3 operations where nis the degree of K. However, the noise distribution on the canonical embedding size might be so twisted after evaluation that an admissible PLWE sample might be taken into a non-admissible RLWE sample if the noise gets amplified beyond a certain threshold. The term admissible refers here to the fact that decryption reverses encryption. Hence, this algorithm must cause a distortion into the error distribution which is, at most, also polynomial in the degree of the underlying number field. For those PLWE instantiations where there is an affirmative answer for this equivalence, RLWE hardness results straightforwardly apply to the corresponding PLWE-based implementation. Although it is known [20] that this equivalence holds for the widely used case of PLWE under Z[x]/(xm+1)(with ma power-of-two) and RLWE under power-of-two cyclotomic fields,2it has been recently shown that the same relation does not hold in general for arbitrary cyclotomic number fields [21]. Additionally, a series of works [14,18–20,22]have explored in detail this relation for different types of number fields and quotient polynomial rings: (1) In [14] the authors show their equivalence for an ad hoc family of polynomials, (2) for the cyclotomic scenario there are some positive results showing the equivalence if 2The transformation between RLWE and PLWE samples is a scaled isometry for power-of-two cyclotomic number fields. 123 Cryptography and Communications (2025) 17:741–775 745 the number of distinct primes dividing the conductor3is kept uniformly bounded [18], and finally, (3) there are also positive results for a family of finite abelian Q-extensions [19,23]. Main objectives Consequently, a better understanding of the required conditions for the equivalence between PLWE and RLWE is not only an interesting research topic by itself, but also turns out to be fundamental to provide a wider catalogue of PLWE instantiations for the designers of cryptographic implementations. This corresponds to the first objective of this work. Our second goal addresses the study of the polynomial multiplication, a building block affecting the speed of cryptographic primitives based on RLWE and, specifically, its use in homomorphic encryption. In particular, we discuss to what extent the broadly used Residue Number System representation (definition given in the next Section 2) interferes with the RLWE-PLWE equivalence for most of families of number fields used to back homomorphic encryption primitives. As a way to overcome this tradeoff, we propose the use of a new family of number fields which we have baptised as cyclo-multiquadratic. It is worth remarking that, while cyclo-multiquadratics can enhance the performance of this underlying building block, it also comes with limitations. We elaborate more on the possible tradeoffs in following sections. 1.3 Our contributions First, we give refined polynomial upper bounds for the condition number of the Vandermonde matrix corresponding to the RLWE-to-PLWE transformation for cyclotomic number fields with up to 6 primes dividing the conductor. These bounds are much sharper than the general one given in [18, Thm. 3.10] and extend the results of Section 4therein. The proof of these bounds has been postponed to the appendix, to ease the reading of our work. Second, in Thm. 3.16 we give an exact formula for the condition number of the RLWEto-PLWE transformation for any cyclotomic number field, but where the usual power basis is replaced by the twisted power basis,4and justify why this basis is preferable to the usual one in homomorphic encryption applications. Furthermore, we compare the condition number for different cyclotomic fields with our predicted bounds. We consider conductors up to 106, divisible by up to 6 different primes and with general conductors of that magnitude (Fig. 2). Third, we introduce cyclo-multiquadratic number fields and justify why they are interesting as a tool to grant RLWE/PLWE equivalence, while also providing arithmetic efficiency when applying the Residue Number System representation. In particular, we prove in Prop. 4.4 and Cor. 4.5 that, under very general assumptions on the parameters set, RLWE and PLWE are equivalent for this family with at most a sub-quadratic noise increase under the twisted power basis embedding. We note that, despite this efficiency improvement, the noise increase remains slightly higher than that of the widely considered case of power-of-two cyclotomics. We elaborate further on this comparison in Section 2. Finally, in Subsection 4.1 we introduce and justify a hybrid embedding (usual power basis on the multiquadratic part twisted by the usual power basis in the cyclotomic side), and 3The conductor of the n-th cyclotomic field is n. In the present work we will not use this notion for other number fields. 4The formal definition of the twisted basis can be found in Definition 3.10. It is worth noting that it is also referred to as the powerful basis in the literature [7]. 123 746 Cryptography and Communications (2025) 17:741–775 likewise we prove RLWE/PLWE equivalence in Thm. 4.6 by using the sharper bounds for the condition number mentioned in the first paragraph. 1.4 Organisation of our work In Section 2we revise the Residue Number System (RNS) representation and how this tool serves to speed up the arithmetic in relevant polynomial rings. Likewise, we also discuss the need for modern HE schemes to swap between representations, and how this causes a logarithmic increase in the computational complexity. A natural question which arises is whether there exists a more efficient representation, a question answered in [24,25]bythe second author in the affirmative for the family of the so called multiquadratic number fields. We recall that, however, for this family the RLWE and PLWE problems are not equivalent, being this the reason for which we introduce a new family: the cyclo-multiquadratric number fields. In Section 3we recall some algebraic number theoretical tools to make the paper selfcontained. In particular, we discuss the Kronecker product in some detail, as we will make use of it in a decisive manner. We also introduce the twisted power basis, discuss several results on the equivalence on cyclotomic number fields and show, with the help of the Kronecker product, that if we replace the usual power basis by the twisted power basis, the cyclotomic ring of integers admits a lattice structure for which RLWE and PLWE become equivalent for arbitrary degree. In Section 4we study the arithmetic of cyclo-multiquadratic number fields and show the equivalence of the RLWE and PLWE problems for this family, as well as we discuss how it keeps the computational efficiency. Finally, in the Appendix we give the proof of several sharp bounds for the condition number of cyclotomic fields whose conductor is divisible by at most six different primes, a result which we use in Section 4. 2 Homomorphic encryption and cyclo-multiquadratic fields The majority of the efficiency improvements that PLWE brings about are strongly related to the algebraic structure of the used quotient polynomial ring R=Z[x]/( f(x)).Themost common choice is to have f(x)=n(x),then-th cyclotomic polynomial. For the sake of exposition, we will simplify here things a little bit and consider that PLWE-based ciphertexts are composed of an unknown number of polynomial elements belonging to the ring Rq= Fq[x]/n(x). Instead of making use of the coefficient representation, an adequate selection of the ciphertext modulus qmakes n(x)to split into linear factors,5which enables us to use the Chinese Remainder Theorem (CRT) as a means to efficiently operate with polynomials. While polynomial multiplication with the coefficient representation presents an asymptotic cost of O(φ(n)log φ(n)), this cost is reduced to O(φ(n)) under a CRT representation; hence being linear in the degree of the involved polynomials [7]. Consequently, as PLWE-based primitives usually require to deal with a relatively high degree of the underlying number field, this alternative representation is widely used because it reduces the effect of the logarithmic factor in each polynomial multiplication. This CRT tool is useful to speed up any type of PLWE-based primitive and, in particular, it results to be fundamental to accelerate homomorphic encryption. In this scenario, the CRT 5In particular, n(x)decomposes into φ(n)distinct linear factors over Fq[x]if and only if q≡1(mod n). 123 Cryptography and Communications (2025) 17:741–775 747 is not only applied at the “ciphertext” layer by choosing an adequate modulo q, but also at the “plaintext” layer where an adequate plaintext modulo allows to batch several integers (usually refered as “slots”) in only one encryption (as many as φ(n)slots per ciphertext). In addition to reducing cipher expansion with respect to plaintext size, this CRT isomorphism enables Single Instruction, Multiple Data (SIMD) operations directly over encrypted integer vectors [26]. Many of the most recent libraries dealing with homomorphic cryptography, such as TFHE-rs 6 and TFHE [27], HElib [28], Lattigo [29], NFLlib [30], PALISADE 7(currently updated and included inside the OpenFHE library [31]) and SEAL [32] take advantage of different variants of this tool to optimize polynomial operations. Specifically, the BFV implementation of HElib and PALISADE uses a double-CRT representation and works over general cyclotomic number fields. This representation applies a first CRT to split the cyclotomic polynomial, and a second CRT over Fqto factor the coefficients of the polynomials depending on the prime-power-decomposition of the modulus q. The rest of implementations are specialized for power-of-two cyclotomic fields: (1) Libraries implementing the FHEW/TFHE [33,34] scheme usually make use of a Discrete Fourier Transform (DFT) representation by means of efficient Fast Fourier Transform (FFT) computations over complex numbers. (2) BFV and CKKS implementations [35,36] with f(x)=xm+1 make use of a CRT–NTT representation (where NTT stands for Number Theoretic Transform), in which a CRT is applied over all coefficients in Fq, while a negacyclic NTT is applied to split f(x)in linear factors. See Fig. 1 for a toy example of this representation.8 Hence we see that the quotient polynomial ring Zq[x]/(xm+1)is the preferred choice by current libraries, as it enables efficient implementations of polynomial operations through previously computing fast radix9algorithms of the DFT and NTT [30,39]. Also important, polynomial operations over the plaintext ring naturally correspond to basic blocks in practical signal processing applications [40–42], comprising, among others, linear convolutions, filtering, and linear transforms. 2.1 Non-polynomial operations and RNS representation In the community of computer arithmetic, the CRT representation described above is also referred to as Residue Number System (RNS). The benefits of staying in the CRT-NTT representation are not only asymptotic. The factorization into several terms produced by the CRT over Fqenables to fit the computation flow into the underlying machine word, with the consequent improvement on practical performance. Unfortunately, the current state-of-the-art in HE, represented by schemes as CKKS and BFV, also makes an intensive use of other non-polynomial operations which are not entirely compatible with the CRT–NTT representation. One clear example is the case of coefficient rounding/rescaling, which is usually performed at the end of each ciphertext multiplication. While there are several strategies to apply this rounding while staying in the first CRT decomposition [35,36], currently there are no equivalent results for its negacyclic NTT counterpart. This means that whenever we execute a non-polynomial operation over each 6TFHE-rs: Pure Rust implementation of the TFHE scheme for boolean and integers FHE arithmetics, https:// github.com/zama-ai/tfhe-rs. 7PALISADE Homomorphic Encryption Software Library, https://palisade-crypto.org/. 8In Fig. 1, the Hadamard product between vectors aand bis denoted as a◦b. Example extracted from [37]. 9For a DFT/NTT of composite size, radix-type algorithms recursively express the transform in terms of a series of DFTs/NTTs of smaller size. The term radix here usually refers to the smallest factor considered in the recursive decompositions [38]. 123 748 Cryptography and Communications (2025) 17:741–775 Fig. 1 Toy example of the CRT-NTT representation polynomial coefficient, we have to swap between NTT and coefficient-wise representations, which presents an asymptotic cost of O(mlog m)elementary multiplications and O(mlog m) elementary additions by means of efficient FFT-type algorithms. 2.2 Efficient conversion between coefficient and CRT–NTT representation The inherent logarithm increase in computational cost which appears when swapping between CRT-NTT (or double-CRT) and coefficient representations is already contemplated in [43], where the authors pose the question of whether there is a more compact representation that can be converted to double-CRT in linear time. Interestingly, this question can be answered in the affirmative for a concrete family of noncyclotomic number fields, coined in [24,25] as multiquadratic number fields. Those works show how the convolution property displayed by these rings is compatible with a particular NTT transform, whose shape is related to a number theoretic version of the Walsh-Hadamard Transform (WHT). This transform can be very efficiently computed with a variant of the Fast Walsh-Hadamard transform algorithm (FWHT), which requires a total of O(mlog m)elementary additions but only O(m)elementary multiplications. Consequently, by substituting the polynomial ring R=Z[x]/(xm+1)by the ring R=Z[x1, ..., xr]/(x2 1+d1,...,x2 r+dr) in the PLWE formulation (with m=2r), we can now take advantage of the different algebraic structure introduced by these multiquadratic rings. In practice, this means that we can swap between NTT and coefficient representations in linear time with respect to the number of elementary multiplications. The benefits of this structure do not only amount to providing more efficient polynomial arithmetic [24], but it also introduces interesting improvements for homomorphic slot manipulation by adding new strategies and storage/computation tradeoffs for relinearization and linear matrix operations. All these benefits build on the natural hypercube structure of its group of automorphisms, which is the direct product (Z2,+)×···×(Z2,+)   r ,wherem=2r is the dimension of the corresponding multivariate number field. Contrarily, the hypercube structure considered in other works dealing with cyclotomic number fields [44–46] relies on the group Z∗ m/(p), where extra homomorphic operations are required to address “bad” dimensions [28]. These are dimensions where more than one automorphism is needed to rotate their slots.10 10 HElib distinguishes between two types of “bad” dimensions: those referred to as “bad” and those called “very bad.” The difference lies in the degree of perturbation that the application of automorphisms causes to the slots of the dimension. We refer the reader to [28] for further details. 123 Cryptography and Communications (2025) 17:741–775 749 2.3 Another non-cyclotomic family: Cyclo-multiquadratic fields The reduction from worst-case ideal lattice problems to RLWE [16] also applies to multiquadratic number fields, namely, those of the form Q(√d1,...,√dr), whenever an adequate choice of {d1,...,dr}parameters is made [25]. Hence, we can efficiently swap between polynomial coefficients and CRT–NTT representations with linear multiplicative complexity, while still backing up security on the hardness of RLWE, and consequently, answering in the affirmative the question posed in [43] regarding swapping “double-CRT” representations in linear time. Delving now into its RLWE-PLWE relation, here we observe how the RLWE and PLWE problems defined, respectively, over multivariate number fields Q(√d1,...,√dr)and multivariate quotient polynomial rings R=Z[x1, ..., xr]/(x2 1+d1,...,x2 r+dr)are not equivalent in the sense we informally stated previously. Actually, the algorithm transforming RLWE samples into PLWE samples and vice versa does not cause a polynomial distortion in the error distribution, but instead quasi-polynomial. In view of this, one last objective of this work is to explore related number field families where (1) the RLWE-PLWE equivalence still holds, and (2) the swapping between CRT–NTT representations is still more efficient than in the widespread cyclotomic case. To this aim, we explore a non-cyclotomic family of number fields defined as the compositum of cyclotomic and multiquadratic fields [25] (see Section 4), which we refer to as cyclo-multiquadratic number fields in the present work. We find particular instantiations of this family which satisfy the RLWE/PLWE equivalence while still providing better concrete efficiency than cyclotomics when swapping between double-CRT representations. Unfortunately, it does seem to be the case that, to have “polynomial” RLWE/PLWE equivalence, we have to resign to have asymptotic linear complexity in the double-CRT transformation.We elaborate more on these tradeoffs next. Tradeoff for hybrid cyclo-multiquadratic rings Our work suggests the existence of different concrete practical tradeoffs between the (1) “polynomial/quasi-polynomial” RLWEPLWE equivalence and (2) “quasi-linear/linear” complexity for the double-CRT transform applied to all polynomial elements in cyclo-multiquadratic rings. For example, some simple parameters’ choices already give more efficient double-CRT transforms than cyclotomic rings. This is done by decomposing m, the total field dimension, in terms of both its multiquadratic and cyclotomic subfields11 as m=mcyclommult =m1/lm1−1/l,wherethe parameter lcontrols the relative dimensions provided by each subfield. It can be seen that, in the above expression, for l=log mwe have linear multiplicative complexity O(m), while for l=√log m,wehaveO(m√log m)multiplicative complexity (see Appendix B.1 for further details). This complexity is obtained by combining the use of FFT-type and FWHT-type algorithms for, respectively, the cyclotomic and multiquadratic subfield dimensions. Unfortunately, only a quasi-polynomial RLWE/PLWE equivalence remains in both cases. We refer the reader to Appendix B.1 for a detailed explanation of the complexity of this algorithm and the PLWE-RLWE equivalence for this choice of parameters. On the contrary, Section 4shows that, by means of Prop. 4.4, sub-quadratic RLWE–PLWE equivalence can be achieved for cyclo-multiquadratic rings if mcyclo =2uand mmult =2r with u=r1+1/lfor fixedl≥2. Also, by allowing a more generic conductor on the cyclotomic 11 Here mcyclo is the dimension of the cyclotomic subfield, and mmult is the dimension of the multiquadratic subfield. 123 756 Cryptography and Communications (2025) 17:741–775 b) If n =plqsrtwith l,s,t≥0, denoting by εthe number of primes diving n with positive power, then Cond(Vn)≤4φ(rad(n))ε−1m2. c) If n =paqbrcsd,then Cond(Vn)≤4φ(rad(n))4m2. d) If n =paqbrcsdteand m =φ(n),then Cond(Vn)≤4φ(rad(n))7m2. e) If n =paqbrcsdteuf,then Cond(Vn)≤4φ(rad(n))11m2. The results provided in Prop. 3.15 are particularly useful for defining secure parameters in practical applications, such as those relying on the HElib library [44,51], which operates with quotient cyclotomic rings under the power basis and where nis the product of several prime powers. For example, HElib is used in several practical applications that work with ncomposed of up to three primes, including homomorphic building of logistic regression models [52] and the homomorphic execution of AES encryption/decryption circuits [53]. Any improvement in the bounds provided in Prop. 3.15 would have immediate implications for the choice of tighter cyclotomic PLWE-based cryptosystem parameters. However, things are much easier if we replace the usual power basis by the twisted basis. In this case, we are changing, first, the usual coordinate embedding by the twisted coordinate embedding and second, even if the image of the transformation is again the canonical embedding of the ring of integers, the basis is again different. Even so, as we pointed out, for many applications it is preferable to work under the twisted canonical embedding instead of the usual canonical embedding. In particular, we have: Theorem 3.16 For n =pk1 1...pkr rwe have Cond(TV Kn)=φ(n)√2r    r  i=11−1 pi. Proof Since the Kpki i are linearly disjoint, from (3.4)wehave TV Kn=Vpk1 1⊗···⊗Vpkr r, From Corollary 3.9 we have Cond(TV Kn)=Cond(Vpk1 1 )···Cond(Vpkr r). The result now follows from Theorem 3.13. Contrariwise to the case of Theorem 3.14, where we needed to impose a constant number of primes dividing the conductor, we can see by Theorem 3.16 that, if we work with PLWE under the twisted basis, the condition number grows polynomially even for the case of conductors divisible by a growing number of primes. Consequently, choices of nwhere r=O(log n) give still the equivalence of RLWE/PLWE under the twisted basis. Nevertheless, even though we can obtain an exact expression for the condition number of cyclotomics under the twisted basis, many applications still utilize the power basis and/or both [28]. This highlights the 123 Cryptography and Communications (2025) 17:741–775 757 importance of obtaining sufficiently tight upper bounds for the condition number under both the power and twisted bases, not only in cyclotomics but also in the more general cases discussed in Section 4for the proposed cyclo-multiquadratics (see Cor. 4.5 and Thm. 4.6). As far as we currently know, we could only find in [28] some related numerical bounds for both cyclotomic power and twisted basis. Their results focus on the infinity norm of the linear transformation from RLWE to PLWE, for which they provide some empirical results for the power basis with up to 5 primes dividing n. For the aim of exposition of our results, we have compared in several figures all the expressions and upper bounds for the condition number from Thm 3.14, Prop. 3.15 and Thm 3.16.13 Figures 2a, 2c, 2d, 2e, 2f, 2g compare all provided expressions,14 but each figure specifically considers a different number of primes dividing the conductor: Fig. 2a considers 1 prime, Fig. 2c considers 2 primes, Fig. 2d considers 3 primes, Fig. 2e considers 4 primes, Fig. 2f considers 5 primes and Fig. 2g considers 6 primes. Then, Fig. 2b represents the particular case of n=2lpd by comparing the expressions from Thm. 3.14, Prop. 3.15 and Thm. 3.16 with the closed formula from Theorem 3.13. Finally, Fig. 2h compares the condition number without any restriction for n, by considering the expressions for power (from Thm. 3.14) and twisted basis (from Thm. 3.16). Note that all figures are log-log plots, so polynomial functions appear approximately as linear functions in which the slope is equal to the maximum degree of the polynomial. Then, it is easy to see how, for Figures 2a, 2b2c, 2d, 2e, 2f, 2g, in which the number of primes dividing nis keep constant, the refined upper bounds from Prop. 3.15 grow much slower than the ones from Thm. 3.14. In all these cases, the analogous expression for the twisted basis giveninThm.3.16 is the slowest, by growing approximately linear in n. In general, this difference among expressions increases when we have a higher number of different primes dividing n, and finally, it becomes more evident in Fig. 2h, where we do not fix the number of primes. For this more general case, the upper bound for the usual power basis from Thm. 3.14 presents a double exponential in the number of primes, and hence, it grows considerably faster than the expression for the twisted basis given in Thm. 3.16. 4 Cyclo-multiquadratic fields A multiquadratic field is a number field of the form Q(√d1, ..., √dr)with di∈Zsquarefree. In this section we will deal with totally real multiquadratic fields, namely, di≥2 for 1 ≤i≤r. We are interested in the interplay between cyclotomic and totally real multiquadratic fields. In particular, let n≥2befixedandletustakerdifferent primes p1,p2, ..., prsuch that pinfor each i. Denote K:= Kn(√p1, ..., √pr). Proposition 4.1 For the extensions Kn/Qand K /Q,wehave Gal(K/Q)∼ =Gal(Kn/Q)×Gal(Q(√p1)/Q)×...×Gal(Q(√pr)/Q). Proof First, we observe that the extensions Kn/Qand Q(√p1)/Qare linearly disjoint: otherwise it would be Kn∩Q(√p1)=Q(√p1)hence Q(√p1)⊆Kn. In that case, the prime p1, which ramifies in Q(√p1),wouldramifyinKn, which is a contradiction since p1n.The 13 Note that, for Thm. 3.14, we represent the upper bound for Cond(Vn)divided by A(n),i.e., Cond(Vn)/A(n). It is actually a lower bound of the expression given for Cond(Vn)in that theorem. 14 The used code is publicly available at https://github.com/apedrouzoulloa/cyclomultiquadratic. 123 758 Cryptography and Communications (2025) 17:741–775 Fig. 2 Condition number of cyclotomic fields in terms of (1) different forms for n, and (2) use of conventional power basis or twisted basis 123 Cryptography and Communications (2025) 17:741–775 759 same argument applies to the extensions KnQ(√p1)/Q(√p1)and Q(√p1,√p2)/Q(√p1) to show that they are linearly disjoint, and the statement for arbitrary r>1 follows by induction. Finally, by using (3.1) the result holds.  Double-CRT with cyclo-multiquadratic rings Our focus in this section is to discuss the conditions for the equivalence between RLWE and PLWE for this family of fields. This equivalence is described in terms of zero characteristic rings, which is why arithmetic modulo qis not explicitly considered in the main results of this section (Cor. 4.5 and Thm. 4.6). However, returning to our discussion in Section 2about efficient polynomial arithmetic, double-CRT is always possible for cyclo-multiquadratic rings. In general, we need a chain of prime moduli q 1,...,q Lsuch that q=iq i, although for simplicity, we first assume that qis prime in our explanation. Unlike the cyclotomic rings discussed in Section 2, where we work with polynomial rings of the form Zq[x]/n(x), in the case of cyclo-multiquadratics, we consider a multivariate polynomial quotient ring of the form Rq=Zq[x0,x1,...,xr]/(n(x0), x2 1−p1,...,x2 r− pr). In addition to the coefficient representation, cyclo-multiquadratic rings also support a CRT representation [25] if the prime modulus qmakes each factor n(x0), x2 1−p1,...,x2 r− prsplit into linear factors. Specifically, qmust satisfy several simultaneous conditions: •n(x0)splits if q≡1(mod n). •For all i,x2 i−pisplits if piis a quadratic residue modulo q. To verify the latter condition, we can use the Legendre symbol, which is defined for an odd prime qas pi q!=p q−1 2 imod q. In summary, besides q≡1(mod n)(asisrequired for cyclotomic rings), the double-CRT representation for cyclo-multiquadratic rings also requires pi q!=1foralli. Finally, in the more general case where qis the product of several primes qj,werequirethat,foralliand j,n≡1(mod qj)and pi qj!=1. Condition number for cyclo-multiquadratics To alleviate notation, from now on, and unless stated otherwise, by the notation ⊗we will understand the usual tensor product ⊗Z. Denote, as in the previous section, On=Z[x]/(n(x)) and set O√pi:= Z[x]/(qi(x)), where qi(x)is the minimal polynomial of √pi, namely, qi(x)=x2−piif pi≡2,3 (mod 4)and qi(x)=x2−x+1−pi 4, the minimal polynomial of 1+√pi 2otherwise. Recall that for a quadratic number field Q(√d),wheredis square-free, its ring of integers is given by Z[εd]. Here, εd=√dwhen d= 1(mod 4),andεd=1+√d 2otherwise, as shown in [49, Thm. 3.3]. Since we need to distinguish between these two cases in the computation of condition numbers below, let us instead denote εi=⎧ ⎨ ⎩ √piif pi≡2,3(mod 4) 1+√pi 2if pi≡1(mod 4). Setting O:= Z[x]/(n(x)) ⊗Z[x]/(q1(x)) ⊗···⊗Z[x]/(qr(x)),wehave: Lemma 4.2 Succesive evaluations at ζn,ε1,...εryield an isomorphism O∼ =OK. Proof Denote by OKnthe ring of integers of Knand notice that O√piisomorphic to the ring of integers of Q(√pi). Since the respective evaluation maps are isomorphisms between the 123 760 Cryptography and Communications (2025) 17:741–775 quotient rings and the corresponding ring of integers and since all these are free Z-modules, succesive evaluations at ζn,ε1,...εrgive an isomorphism O∼ =OKn⊗O√pi⊗···⊗O√pr. Moreover, since the extensions are linearly disjoint and the gcd of all the discriminants is 1, by [54, Thm. 4.26] we have OKn⊗O√pi⊗···⊗O√pr∼ =OK.  Hence, by Prop. 4.1 the twisted coordinate embedding reads as: σT,K:O→σ1(OK)×···×σ2rm(OK) 2rm−1  i=0 aixi→ TV K⎛ ⎜ ⎜ ⎜ ⎝ a0 a1 . . . a2rm−1 ⎞ ⎟ ⎟ ⎟ ⎠ ,(4.1) where, as in the previous section TV K:= TV Kn⊗Vp1⊗... ⊗Vpr, with Vpi=⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1√pi 1−√piif pi≡2,3(mod 4) #11+√pi 2 11−√pi 2$if pi≡1(mod 4). Hence, we have: Cond(Vpi)=⎧ ⎪ ⎨ ⎪ ⎩ √pi+1 √piif pi≡2,3(mod 4) 5 2√pi+√pi 2if pi≡1(mod 4). (4.2) The following upper bound follows directly from (4.2): Corollary 4.3 For each prime number p ≥2, it holds Cond(Vp)≤2+√p. Hence, as a direct consequence of Corollary 3.9 and Theorem 3.13,wehave: Proposition 4.4 With notation as above: Cond(TV K)≤φ(n)2ω(n) 2 r  i=1 2+√pi!. We can hence conclude that Corollary 4.5 For n ≥eewe have Cond(TV K)≤φ(n)nα r  i=1 2+√pi!with α=0.2076. 123 Cryptography and Communications (2025) 17:741–775 761 Proof In [55, Thm. 11 pag. 369], it is proved that for n≥3 it holds ω(n)≤1.3841 log(n) log log(n). The result follows from this upper bound and from Proposition 4.4. Now, the idea is to choose nand the primes p1,...,prin such a way that Cond(TV K)=O((m2r)k), with m=φ(n), (4.3) and with uniformly upper bounded (and small)k,say0≤k≤4, so that for suitable large enough choices of nand rwe can grant that the distortion caused by the RLWE-PLWE correspondence is polynomial in the degree of the number field, which is a sort of balance between noise and security. We need to recall, first, the straightforward inequality n≤2φ(n)2,for each n≥1. Actually, if n=2amwith a= 1, then n≤φ(n)2. For (4.3) to hold, it is enough that we can grant that in the large (1+2α)log(m)+ r  i=1 log 2+√pi!∼ =k(log(m)+rlog(2)), or equivalently k=lim m,r→∞ (1+2α)log(m)+r i=1log 2+√pi! log(m)+rlog(2),(4.4) whenever this limit exists. If, for instance, we take the popular choice n=2u+1and pi=the i-th prime (with i>1), the right hand side of (4.4), before taking limit, can be upper bounded by (1+2α)ulog(2)+rlog 2+√pr! ulog(2)+rlog(2)(4.5) Since, by the Prime Number Theorem, a reasonable approximation for the r-th prime is pr∼ =rlog(r),foruand rlarge enough, (4.5) can be fairly approximated by (1+2α)ulog(2)+rlog(2+%rlog(r)) ulog(2)+rlog(2). Moreover, if in addition ulog(2)rlog(2+%rlog(r)), namely, if lim u,r→∞ ulog(2) rlog(2+%rlog(r)) =∞, then we have: k≤1+2α=1.4152. For instance, if u∼r1+1/lfor fixed l≥2, then we obtain a sub-quadratic upper-bound for the condition number. Some extra remarks on the condition number and double-CRT To obtain the upper bounds in Cor. 4.5 (and also in Thm. 4.6 for Subsection 4.1) for the condition number of cyclo-multiquadratics, we consider its ring of integers OK(see Lemma 4.2). However, it is 123 762 Cryptography and Communications (2025) 17:741–775 important to mention that OKdoes not, in general, have the same form as the one used for the existence of the double-CRT in Rq=Zq[x0,x1,...,xr]/(n(x0), x2 1−p1,...,x2 r−pr). Some quotients qi(xi)of OKtake the form qi(xi)=x2 i−xi+1−pi 4if pi≡1(mod 4). Following [25], in this situation, we must simply apply a map from OKto Rq, where for all xisuch that pi≡1(mod 4): •Substitute xi→xi+1 2in the two polynomial elements of the PLWE sample (a,b= as +e)∈O2 K. •Multiply both polynomial elements of the PLWE sample by 2. As a result, we obtain transformed PLWE samples (˜a,˜ b)∈R2 q. The transformation applied to each xisuch that pi≡1(mod 4)can also be seen as a multiplication by the matrix M=21 01 , with Cond(M)=3. Thus, we have Cond(M−1Vpi)≤35 2√pi+√pi 2.The use of the double-CRT when the number field has primes pi≡1(mod 4)implies that the term √piin the upper bound given in Cor. 4.3 is multiplied by 3 2. Since this increase in the upper bound does not affect the results obtained in Cor. 4.5 and Thm. 4.6, which still hold in this case, we have preferred not to account for this constant factor in the exposition for simplicity. 4.1 A hybrid embedding Setting as before K=KnQ(√p1)···Q(√pr), observe that, in the previous subsection, we have evaluated the elements of the multivariate quotient ring at the powerful basis on the cyclotomic side, at the generators of the quadratic fields on the multiquadratic side and then, we have applied the canonical embedding. We recall that this approach allows us to obtain a sub-quadratic condition number. However, if the conductor nof the cyclotomic part is divisible by several primes, the ring of integers of the cyclotomic field is isomorphic to the quotient ring Z[x]/(n(x)) but also to a multivariate quotient polynomial ring (Lemma 3.11 together with (3.2)). Hence, if the coordinates of the samples are given with respect to the usual power basis instead of the powerful basis, it is the Vandermonde matrix VKnthe one whose condition number we must upper bound, as the transformation between PLWE and RLWE is, in this case, evaluation at the usual power basis on the cyclotomic side, evaluation at the generators of the quadratic fields on the multiquadratic side and followed by the canonical embedding. Namely, the corresponding embedding for the whole cyclo-multiquadratic field would be σ T,K:O→σ1(OK)×···×σ2rm(OK) 2rm−1  i=0 aixi→ TV K⎛ ⎜ ⎜ ⎜ ⎝ a0 a1 . . . a2rm−1 ⎞ ⎟ ⎟ ⎟ ⎠ ,(4.6) where now TV K=VKn⊗Vp1⊗... ⊗Vpr. In the context of cyclotomic rings where the conductor nis divisible by several primes, PLWE samples under the powerful basis (see Thm. 3.16) typically exhibit a significantly smaller condition number compared to PLWE samples under the power basis (see Prop. 3.15). This raises the question of the relevance and utility of providing in this section upper bounds 123 Cryptography and Communications (2025) 17:741–775 763 and conducting analyses under the cyclotomic power basis, as opposed to exclusively using the powerful basis. While some works, such as [56], which focuses on an implementation of CKKS with a conductor composed of two primes, consider only the cyclotomic powerful basis, it is important to recognize that certain HE libraries make use of both basis depending on the specific algorithm being executed. For instance, in the BGV implementation of HElib [28], the power basis is employed during modulus switching, key switching, and encryption, whereas the powerful basis is used in other operations such as decryption. Thus, in practice, it may also be valuable to consider the power basis when working with the cyclotomic part Knof the proposed cyclo-multiquadratic rings in K. Denoting by c(n)the condition number of Kn,wehavethat Cond(TV K)≤c(n) r  i=1 2+√pi! As in the previous subsection, we will choose pi=the i-th prime number, where we do not explicitly exclude the ω(n)primes pithat divide nbecause this does not significantly affect the approximation used for the size of the primes. In this case, if we want Cond(TV K)=O((m2r)k), (4.7) we need to have k=lim sup m,r→∞ log(c(n)) +r i=1log 2+√pi! log(m)+rlog(2),(4.8) As we have pointed out in the previous section, in [21] it is shown that c(n)is not polynomial for general n≥2. However, if we stick to a conductor divisible by a bounded number of primes, we can grant that c(n)essentially grows polynomially with rad(n). Next, we will assume that ω(n)≤6 and will use Proposition 3.15 to give an explicit formula for (4.8)togrant(4.7). First, assume that ω(n)≤3. Then, the right hand side of the equality (4.8), before taking limit, is upper bounded by log(4)+2log(m)+(ω(n)−1)log(φ(rad(n))) log(m)+rlog(2)+ rlog 2+%rlog(r) log(m)+rlog(2).(4.9) As in the previous subsection, we impose that rlog(%rlog(r)) log(m), namely, that limr,m→∞ rlog(√rlog(r)) log(m)=0. If ω(n)=1, the upper limit of (4.9) is indeed the limit and we have k=lim r,m→∞ log(4)+2log(m) log(m)+rlog(2)+ (ω(n)−1)log(φ(rad(n))) +rlog 2+%rlog(r) log(m)+rlog(2)=2. If 1 <ω(n)≤3, we observe that log(φ(rad(n)) log(m)≤1, but the limit of this expression may not exist in general. However, it is still true that lim supn→∞ log(φ(rad(n)) log(m)=1. Hence k=lim sup r,m→∞ log(4)+2log(m) log(m)+rlog(2)+ (ω(n)−1)log(φ(rad(n))) +rlog 2+%rlog(r) log(m)+rlog(2)≤4. 123 764 Cryptography and Communications (2025) 17:741–775 For ω(n)=4, we have k=lim sup r,m→∞ log(4)+2log(m)+4log(φ(rad(n))) log(m)+rlog(2)+ rlog %2+rlog(r) log(m)+rlog(2)≤6, and for ω(n)=5 we obtain k=lim sup r,m→∞ log(4)+2log(m)+7log(φ(rad(n))) log(m)+rlog(2)+ rlog %2+rlog(r) log(m)+rlog(2)≤9. Finally, for ω(n)=6 we obtain k=lim sup r,m→∞ log(4)+2log(m)+11 log(φ(rad(n))) log(m)+rlog(2)+ rlog %2+rlog(r) log(m)+rlog(2)≤13. Altogether, we have proved the following: Theorem 4.6 Let K =KnQ(√p1,···,√pr)with pr=the r-th prime and m =φ(n). Assume that we choose n and r such that limr,m→∞ rlog(√rlog(r)) log(m)=0. Then, we have: •If ω(n)≤3,then Cond(TV K)=O((2rm)2+ω(n)−1). •If ω(n)=4,then Cond(TV K)=O((2rm)6). •If ω(n)=5,then Cond(TV K)=O((2rm)9). •If ω(n)=6,then Cond(TV K)=O((2rm)13). The results from Thm. 4.6 and Prop. 3.15 enable a fair comparison of the condition numbers obtained for cyclotomics and cyclo-multiquadratics that follow our parameters’ indications. By fixing the same equivalent field dimension for both cases, we observe that the incorporation of the multiquadratic part does not substantially increase the condition number. Moreover, although at first glance the results provided in Cor. 4.5 and Thm. 4.6 seem to indicate that it is always better to work under the twisted basis for the cyclotomic part of cyclomultiquadratic rings, we remind the reader that several practical applications in homomorphic encryption (HE) based on PLWE with cyclotomics utilize both the cyclotomic power and powerful basis [52,53]. Both applications are implemented in the HElib library [44,51], which employs either basis depending on the specific step executed within the HE primitive. We note, however, that HElib [43] employs a more general notion of the basis, considering nth cyclotomic fields where ndecomposes into pairwise coprime integers. In contrast, our work with the twisted basis focuses on decomposing ninto different prime powers, enabling a more detailed analysis of the condition number. Still, it is worth mentioning that Definition 3.10 provides a formulation of the twisted basis that accommodates this more general context, bridging the gap between these two approaches. Some discussions on the impact of cyclo-multiquadratics Once we have introduced our two main results on the condition number for cyclo-multiquadratics in Cor. 4.5 and Thm. 4.6, 123 Cryptography and Communications (2025) 17:741–775 765 we return to the discussion in Section 2regarding the practical efficiency improvements introduced by cyclo-multiquadratics. In general, we observe that these rings can provide a constant improvement in the multiplicative computational cost when swapping between NTT and coefficient representations. Nevertheless, as noted in Cor. 4.5, these rings also produce a slight increase in noise distortion compared to the cyclotomic counterparts with the same field dimension. Due to this increase, maintaining RLWE worst-case hardness, according to the invulnerability condition stated in [57], requires adding extra noise to the PLWE samples. In practice, this implies selecting a larger modulus q, which could reduce the efficiency gains discussed in Section 2. As previously discussed in the comparison between the cyclotomic power and powerful basis, the HElib library makes use of both in different steps of the BGV implementation [28]. Moreover, several practical applications implemented with the BGV scheme of HElib consider cyclotomics with an order nthat is the product of three distinct primes [52,53], for which Prop. 3.15 shows that the condition number grows as a polynomial of degree 4. In contrast, as demonstrated in Cor. 4.5 and Thm. 4.6, the inclusion of the multiquadratic part in cyclo-multiquadratics results in a much smaller increase in the condition number, even remaining sub-quadratic in the total field dimension for the case discussed in Cor. 4.5. Thus, although the required modulus qwould be slightly larger than in the ideal scenario with power-of-two cyclotomics, the noise distortion remains significantly smaller than that produced in the general cyclotomic rings currently implemented in practical applications. This high-level analysis seems to indicate that, despite the need for a larger modulus q, the benefits of cyclo-multiquadratics would remain. Nevertheless, we emphasize that this analysis is qualitative, and a more detailed study is needed, as many factors can influence its practical efficiency (see Subsection 2.3), which is beyond the scope of this work. For more concrete examples of the increase in qcaused by only multiquadratics, we refer to [24], where an additive homomorphic scheme based on RLWE is instantiated. Despite requiring larger ciphertexts compared to RLWE with power-of-2 cyclotomics, the scheme still achieved improved efficiency for its primitives. The solutions proposed in Cor. 4.5 and Thm. 4.6 aim precisely to find a middle ground, producing smaller ciphertexts than in the multiquadratic case while still improving the efficiency of the basic building blocks. 5 Conclusions We have started discussing in Sections 1and 2why the CRT is useful to speed up homomorphic encryption. In most applications, CRT is applied both on plaintexts and ciphertexts, hence enabling SIMD operations directly over encrypted integer vectors. We have also pointed out how several widely used homomorphic schemes, such as CKKS and BFV, use other nonpolynomial operations, like coefficient rounding/rescaling, which are not entirely compatible with the CRT–NTT representation. Because of this, when running a non-polynomial operation, one has to swap between NTT and coefficient-wise representations, which presents an asymptotic cost of O(mlog m)elementary multiplications. This led us to address the question whether or not there is a more compact representation that can be converted to double-CRT in linear time. We recall previous investigation of the second author, where the multiquadratic family was introduced, answering that question in an affirmative manner. However, a new difficulty appears in this setting since the RLWE and PLWE problems for multiquadratic fields are not 123 772 Cryptography and Communications (2025) 17:741–775 B.2.1 General expression for MultCostRatio(mcyclo,mmult) In the previous section, we made use of several assumptions regarding the relation between r and l. However, we can obtain an exact lower bound for MultCostRatio(mcyclo,mmult)without the need to work in the range of intermediate values for rwhere r1/l≈1. To do this, we again resort to the fact that x x+1≥x−1 xfor x≥1, and define d=1/lfor simplicity in notation, yielding the following lower bound: MultCostRatio(mcyclo,mmult)=A·(u+cr) 1+A·u =A·(r1+d+cr) 1+A·r1+d =A·c·r 1+A·r1+d+A·r1+d 1+A·r1+d =A·r 1+A·r1+d+A·(c−1)·r 1+A·r1+d+A·r1+d 1+A·r1+d ≥A·r−1 A·r1+d+A·(c−1)·r 1+A·r1+d+A·r1+d 1+A·r1+d ≥A·r A·r1+d−1 A·r1+d+A·(c−1)·r 1+A·r1+d+A·r1+d 1+A·r1+d ≥1 rd−1 A·r1+d+A·(c−1)·r 1+A·r1+d+A·r1+d 1+A·r1+d ≥c rd−c A·r1+d+A·r1+d−1 A·r1+d ≥c rd−c A·r1+d+1−1 A·r1+d ≥1+c rd−c+1 A·r1+d. This expression provides a much better understanding of the adequate values for c,l= 1/d,andrwhich maximize MultCostRatio(mcyclo,mmult). Generally, we need rvalues small enough compared to l, but larger than cto minimize the effect of the term being subtracted. Acknowledgements I. Blanco-Chacón is partially supported by the grants MTM2016-79400-P (Spanish Ministry of Science and Innovation), CCG20/IA-057 (University of Alcalá), and PID2019-104855RBI00/AEI/10. 13039/501100011033 (Spanish Ministry of Science and Innovation). Part of the work has been completed as a visiting professor at Aalto University School of Science. A. Pedrouzo-Ulloa is partially supported by the European Union’s Horizon Europe Framework Programme for Research and Innovation Action under project TRUMPET (proj. no. 101070038), by the European Regional Development Fund (FEDER) and Xunta de Galicia under project “Grupos de Referencia Competitiva” (ED431C 2021/47), and by FEDER and MCIN/AEI under project FELDSPAR (TED2021-130624B-C21). Part of the work has been completed as a visiting researcher at CEA-List, Université Paris-Saclay, and at the Universitat Politècnica de Catalunya (UPC), being funded by the European Union “NextGenerationEU/PRTR” under TRUFFLES and by means of a Margarita Salas grant of the Universidade de Vigo. R. Y. Njah Nchiwo is supported in part by a PhD scholarship by the Magnus Ehrnrooth Foundation, Finland, in part by Academy of Finland, grant 351271 (P.I. Camilla Hollanti) and in part by MATINE, Finnish Ministry of Defence, grant #2500M-0147 (P.I. PI Camilla Hollanti). B. Barbero-Lucas is partially supported by the grant CCG20/IA-057. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Funded by the European Union. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them. The authors would like to thank Camilla Hollanti and Raúl Durán-Díaz for helpful 123 Cryptography and Communications (2025) 17:741–775 773 discussion and thorough reading of several versions of our work. Likewise, I. Blanco-Chacón would like to thank Aalto SCI for inviting him as a visiting professor for the year 2023–2024. Finally, we would like to thank the anonymous reviewers and the editor for their valuable feedback, which greatly contributed to improving the quality of this manuscript. Data Availability The data and code used to generate the figures in this paper are publicly available in the following GitHub repository: https://github.com/apedrouzoulloa/cyclomultiquadratic. This repository contains the code used for the analysis and figure generation. The repository is publicly accessible for review and use. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015) 2. Micciancio, D.: The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput. 30(6), 2008–2035 (2000) 3. Khot, S.: Hardness of approximating the shortest vector problem in lattices. J. ACM. 52(5), 789–808 (2005) 4. NIST Post-Quantum Cryptography Standardization, Round 3 Submissions. https://csrc.nist.gov/Projects/ post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions 5. Homomorphic Encryption Standardization. https://homomorphicencryption.org/ 6. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM. 56(6), 34–13440 (2009) 7. Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-lwe cryptography. In: Advances in Cryptology - EUROCRYPT 2013. Lecture Notes in Computer Science, vol. 7881, pp. 35–54. Springer, Berlin, Heidelberg (2013) 8. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory. 6(3), 13–11336 (2014) 9. Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565–599 (2015) 10. Bolboceanu, M., Brakerski, Z., Sharma, D.: On algebraic embedding for unstructured lattices. IACR Cryptol. ePrint Arch., 53 (2021) 11. Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., Vaikuntanathan, V.: Homomorphic Encryption Standard. Cryptology ePrint Archive, Paper 2019/939 (2019). https://eprint. iacr.org/2019/939 12. Bossuat, J.-P., Cammarota, R., Chillotti, I., Curtis, B.R., Dai, W., Gong, H., Hales, E., Kim, D., Kumara, B., Lee, C., Lu, X., Maple, C., Pedrouzo-Ulloa, A., Player, R., Polyakov, Y., Lopez, L.A.R., Song, Y., Yhee, D.: Security Guidelines for Implementing Homomorphic Encryption. Cryptology ePrint Archive, Paper 2024/463 (2024). https://eprint.iacr.org/2024/463 13. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Advances in Cryptology - EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 1–23. Springer, Berlin, Heidelberg (2010) 14. Rosca, M., Stehlé, D., Wallet, A.: On the ring-lwe and polynomial-lwe problems. In: Advances in Cryptology - EUROCRYPT 2018–37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Lecture Notes in Computer Science, vol. 10820, pp. 146–173. Springer, Cham (2018) 15. Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Advances in Cryptology - ASIACRYPT. Lecture Notes in Computer Science, vol. 5912, pp. 617–635. Springer, Berlin, Heidelberg (2009) 123 774 Cryptography and Communications (2025) 17:741–775 16. Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-lwe for any ring and modulus. In: ACM SIGACT Symposium on Theory of Computing. STOC 2017, pp. 461–473. ACM, New York, NY, USA (2017) 17. Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-lwe and security for key dependent messages. In: Advances in Cryptology - CRYPTO. Lecture Notes in Computer Science, vol. 6841, pp. 505–524. Springer, Berlin, Heidelberg (2011) 18. Blanco-Chacón, I.: On the RLWE/PLWE equivalence for cyclotomic number fields. Appl. Algebra Eng. Commun. Comput. 33(1), 53–71 (2022) 19. Blanco-Chacón, I.: RLWE/PLWE equivalence for totally real cyclotomic subextensions via quasiVandermonde matrices. J. Algebra Appli. 21(11), 2250218 (2022) 20. Ducas, L., Durmus, A.: Ring-lwe in polynomial rings. In: Public Key Cryptography - PKC 2012–15th International Conference on Practice and Theory in Public Key Cryptography. Lecture Notes in Computer Science, vol. 7293, pp. 34–51. Springer, Berlin, Heidelberg (2012) 21. Scala, A.J.D., Sanna, C., Signorini, E.: Rlwe and plwe over cyclotomic fields are not equivalent. Applicable Algebra in Engineering, Communication and Computing (2022) 22. Bolboceanu, M.: Relating different polynomial-lwe problems. In: SecITC 2018. Lecture Notes in Computer Science, vol. 11359, pp. 492–503. Springer, Cham (2018) 23. Blanco-Chacón, I., López-Hernanz, L.: RLWE/PLWE equivalence for the maximal totally real subextension of the 2rpq-th cyclotomic field. Adv. Math. Commun. (2022) 24. Pedrouzo-Ulloa, A., Troncoso-Pastoriza, J.R., Gama, N., Georgieva, M., Perez-Gonzalez, F.: Multiquadratic rings and walsh-hadamard transforms for oblivious linear function evaluation. 2020 IEEE International Workshop on Information Forensics and Security, WIFS 2020. (2020) 25. Pedrouzo-Ulloa, A., Troncoso-Pastoriza, J.R., Gama, N., Georgieva, M., Pérez-González, F.: Revisiting multivariate ring learning with errors and its applications on lattice-based cryptography. Math. 9(8) (2021) 26. Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71(1), 57–81 (2014) 27. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: Fast Fully Homomorphic Encryption Library. https://tfhe.github.io/tfhe/ (2016) 28. Halevi, S., Shoup, V.: Design and implementation of helib: a homomorphic encryption library. IACR Cryptol. ePrint Arch., 1481 (2020) 29. Mouchet, C., Bossuat, J.-P., Troncoso-Pastoriza, J., Hubaux, J.: Lattigo: a multiparty homomorphic encryption library in go. In: WAHC (2020) 30. Aguilar-Melchor, C., Barrier, J., Guelton, S., Guinet, A., Killijian, M.-O., Lepoint, T.: NFLlib: NTT-Based Fast Lattice Library, pp. 341–356. Springer, Cham (2016) 31. Badawi, A.A., Bates, J., Bergamaschi, F., Cousins, D.B., Erabelli, S., Genise, N., Halevi, S., Hunt, H., Kim, A., Lee, Y., Liu, Z., Micciancio, D., Quah, I., Polyakov, Y., Saraswathy, R.V., Rohloff, K., Saylor, J., Suponitsky, D., Triplett, M., Vaikuntanathan, V., Zucca, V.: Openfhe: Open-source fully homomorphic encryption library. In: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Los Angeles, CA, USA, 7 November 2022, pp. 53–63. ACM, New York, NY, USA (2022) 32. Microsoft SEAL (release 4.1). https://github.com/Microsoft/SEAL. Microsoft Research, Redmond, WA. (2023) 33. Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Advances in Cryptology - EUROCRYPT 2015. Lecture Notes in Computer Science, vol. 9056, pp. 617– 640. Springer, Berlin, Heidelberg (2015) 34. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption over the torus. J. Cryptol. 33(1), 34–91 (2020) 35. Bajard, J., Eynard, J., Hasan, M.A., Zucca, V.: A full RNS variant of FV like somewhat homomorphic encryption schemes. In: Selected Areas in Cryptography - SAC. Lecture Notes in Computer Science, vol. 10532, pp. 423–442. Springer, Cham (2016) 36. Halevi, S., Polyakov, Y., Shoup, V.: An improved RNS variant of the BFV homomorphic encryption scheme. In: Topics in Cryptology - CT-RSA 2019. Lecture Notes in Computer Science, vol. 11405, pp. 83–105. Springer, Cham (2019) 37. Pedrouzo-Ulloa, A.: Multiquadratic rings and oblivious linear function evaluation. TEMat monográficos. 2, 83–86 (2021) 38. Duhamel, P., Vetterli, M.: Fast fourier transforms: A tutorial review and a state of the art. Signal Process. 19(4), 259–299 (1990) 39. Harvey, D.: Faster arithmetic for number-theoretic transforms. J. Symb. Comput. 60, 113–119 (2014) 40. Nussbaumer, H.J.: Fast Fourier Transform and Convolution Algorithms. Springer, Berlin, Heidelberg (1982) 123 Cryptography and Communications (2025) 17:741–775 775 41. Bianchi, T., Piva, A., Barni, M.: Composite Signal Representation for Fast and Storage-Efficient Processing of Encrypted Signals. IEEE Trans. Inf. Forensic. Secur. 5(1), 180–187 (2010) 42. Pedrouzo-Ulloa, A., Troncoso-Pastoriza, J.R., Pérez-González, F.: Number theoretic transforms for secure signal processing. IEEE Trans. Inf. Forensic. Secur. 12(5), 1125–1140 (2017) 43. Halevi, S., Shoup, V.: Bootstrapping for helib. J. Cryptol. 34(1), 7 (2021) 44. Halevi, S., Shoup, V.: Faster homomorphic linear transformations in helib. In: Advances in Cryptology - CRYPTO 2018. Lecture Notes in Computer Science, vol. 10991, pp. 93–120. Springer, Cham (2018) 45. Cheon, J.H., Choe, H., Lee, D., Son, Y.: Faster linear transformations in HElib, revisited. IEEE Access. 7, 50595–50604 (2019) 46. Han, K., Hhan, M., Cheon, J.H.: Improved homomorphic discrete fourier transforms and FHE bootstrapping. IEEE Access. 7, 57361–57370 (2019) 47. Chiu, S., Parhi, K.K.: Long polynomial modular multiplication using low-complexity number theoretic transform [lecture notes]. IEEE Signal Process. Mag. 41(1), 92–102 (2024) 48. Heideman, M.T., Burrus, C.S.: On the number of multiplications necessary to compute a length-2ndft. IEEE Trans. Acoust. Speech Signal Process. 34(1), 91–95 (1986) 49. Stewart, I.N., Tall., D.O.: Algebraic Number Theory (Second Edition). Chapman and Hall/CRC Press, New York (1987) 50. Scala, A.J.D., Sanna, C., Signorini, E.: On the condition number of the vandermonde matrix of the nth cyclotomic polynomial. J. Math. Cryptol. 15(1), 174–178 (2021) 51. Halevi, S., Shoup, V.: Algorithms in helib. In: Advances in Cryptology - CRYPTO 2014. Lecture Notes in Computer Science, vol. 8616, pp. 554–571. Springer, Berlin, Heidelberg (2014) 52. Crawford, J.L.H., Gentry, C., Halevi, S., Platt, D., Shoup, V.: Doing real work with FHE: the case of logistic regression. In: Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2018, Toronto, ON, Canada, October 19, pp. 1–12. ACM (2018) 53. Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7417, pp. 850–867. Springer, Berlin, Heidelberg (2012) 54. Narkiewicz, W.: Elementary and Analytic Theory of Algebraic Numbers. Springer, Berlin, Heidelberg (2004) 55. Robin, G.: Estimation de la fonction de tchebychef θsur le k-iéme nombre premier et grandes valeurs de la fonction ω(n)nombre de diviseurs premiers de n. Acta Arithmetica. 42(4), 367–389 (1983) 56. Jang, J., Lee, Y., Kim, A., Na, B., Yhee, D., Lee, B., Cheon, J.H., Yoon, S.: Privacy-preserving deep sequential model with matrix homomorphic encryption. In: ASIA CCS ’22: ACM Asia Conference on Computer and Communications Security, Nagasaki, Japan, 30 May 2022 - 3 June 2022, pp. 377–391. ACM, New York, NY, USA (2022) 57. Peikert, C.: How (not) to instantiate ring-lwe. In: Security and Cryptography for Networks - 10th International Conference, SCN 2016, Amalfi, Italy, August 31 - September 2, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9841, pp. 411–430. Springer, Cham (2016) 58. Washington, L.C.: Introduction to Cyclotomic Fields. Springer, New York, NY (1997) 59. Bzdega, B.: On the height of cyclotomic polynomials. Acta Arithmetica. 152, 349–359 (2010) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123