Non-commutative Ring Learning with Errors from Cyclic Algebras
Full text
This is a self-archived version of an original article. This version may differ from the original in pagination and typographic details. Author(s): Title: Year: Version: Copyright: Rights: Rights url: Please cite the original version: CC BY 4.0 https://creativecommons.org/licenses/by/4.0/ Non-commutative Ring Learning with Errors from Cyclic Algebras © The Author(s) 2022 Published version Grover, Charles; Mendelsohn, Andrew; Ling, Cong; Vehkalahti, Roope Grover, C., Mendelsohn, A., Ling, C., & Vehkalahti, R. (2022). Non-commutative Ring Learning with Errors from Cyclic Algebras. Journal of Cryptology, 35(3), Article 22. https://doi.org/10.1007/s00145-022-09430-6 2022
https://doi.org/10.1007/s00145-022-09430-6 J Cryptol (2022) 35:22 Research Article Non-commutative Ring Learning with Errors from Cyclic Algebras Charles Grover ·Andrew Mendelsohn ·Cong Ling Imperial College London, London, UK c.grov[email protected] andrew[email protected] [email protected] Roope Vehkalahti Department of Mathematics and Statistics, University of Jyväskylä, 40014 Jyväskylä, Finland [email protected] Communicated by Damien Stehlé Received 19 November 2020 / Revised 18 May 2022 / Accepted 19 May 2022 Abstract. The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice-based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of ‘structured’ LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well-chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a ring. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. We show that the security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem (under the condition of constant rank d). As a contribution of theoretic interest, we view CLWE as the first variant of Ring LWE which supports non-commutative multiplication operations. This ring structure compares favorably with Module LWE, and naturally allows a larger message space for error correction coding. Keywords. Algebraic number theory, Lattices, Learning with errors, Non-commutative algebra, Post-quantum cryptography. 1. Introduction With the predicted advent of quantum computers compromising the bulk of existent cryptographic constructions, lattice-based cryptography has emerged as a promising foundation for long term security. In particular, the Learning with Errors (henceforth © The Author(s) 2022 0123456789().: V,-vol
22 Page 2 of 67 C. Grover et al. LWE) problem introduced in [42], as well as its variants over rings (RLWE) [27] and modules (MLWE) [22], provides a natural intermediate step to base cryptographic hardness on lattice short vector problems in a post-quantum setting. Indeed, second round submissions to the NIST post-quantum standardization process such as NewHope [3] and KYBER [5] rely on the hardness of LWE variants. Cryptography based on the classical LWE problem is typically somewhat impractical, in part due to large key sizes. To solve this, the ring variant was introduced as a way to provide extra structure in LWE to trade a potential loss of security for an increase in efficiency. MLWE generalizes ring and classical LWE, providing a smoother transition between security and efficiency than the binary option presented by ring or classical LWE. The flexibility of MLWE is highly desirable in practice, as demonstrated by third-round NIST finalists KYBER and SABER, both based on MLWE [1]. Conceptually, one may view all these problems as variations on a single problem. The (search) LWE problem tasks a solver with recovering a secret vector s∈Zn qfrom a collection of pairs (ai,b=ai,s+ei), where ·,· denotes the inner product, each ai∈Zn qis uniformly random and the ei’s are small random errors. In practice, we view this collection of equations in matrix–vector form: As+e=b, where all operations and entries are over Zqand the challenge is to recover sfrom A,b. A popular ring variant replaces A,s,ewith elements a,s,efrom the ring Rq:= Zq[x] xn+1, requiring the solver to obtain sfrom samples ai·s+ei. For power-of-two nthis can be expressed in matrix–vector form by considering the matrix rot(a), the negacyclic matrix obtained from the coefficients of a. Explicitly, for a=a0+a1x+... +an−1xn−1and bold faced letters denoting coefficient vectors, a sample from the RLWE distribution takes the form: ⎛ ⎜ ⎜ ⎜ ⎝ a0−an−1... −a1 a1a0... −a2 . . .. . ..... . . an−1an−2... a0 ⎞ ⎟ ⎟ ⎟ ⎠ s+e=b where once again operations and entries are over Zq. This is exactly a structured version of the classical LWE problem, where the uniformly random matrix Ahas been replaced by the negacyclic matrix rot(a). Of course, this should be no harder to solve, yet no substantial progress has been made in using the structure of rot(a)to solve the problem efficiently. We can extend this matrix–vector view to MLWE as well. An MLWE instance takes place in a module Mof dimension dover Rq, such that a solver has to recover s∈Mfrom a collection of pairs (ai,ai,s+ei)where aiis a uniformly random element of Mand each eiis a small random element of Rq. A collection of such pairs can be viewed as As+e=b, where the ambient space Zqhas been replaced by Rq, e.g., with dsamples:
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 3 of 67 22 ⎛ ⎜ ⎜ ⎜ ⎝ a1,1a1,2... a1,d a2,1a2,2... a2,d . . .. . ..... . . ad,1ad,2...ad,d ⎞ ⎟ ⎟ ⎟ ⎠ s+e=b where all operations are over Rqand each ai,jis uniformly random. Of course, we could extend this to have operations over Zqby applying the rot(·)operation coordinatewise, to obtain a structured LWE instance in dimension nd. An advantage of these structured matrices is that they allow for streamlined storage and operations. For example, storing a uniformly random matrix Arequires one to store all n2of its entries, but rot(a)requires a factor nless memory since one need only store its first column. Equivalently, one RLWE sample generates nLWE samples while reducing the storage space and key sizes. Multiplication can also be speeded up by using the Chinese Remaindering Theorem (CRT) or other techniques. This concept of improving efficiency by adding structure motivates this work; can we perform an analog of the transformation taking an LWE matrix Ato an RLWE matrix rot(a)for the module M? We solve this by constructing a new variant of the LWE problem over a certain non-commutative space known as a cyclic algebra. In recent years, cyclic algebras have received significant attention in the field of coding theory (see, e.g., [25,32,44]) due to the particular nature of the matrix lattices they induce, and we view them as a suitable option for defining an LWE problem over a non-commutative ring. Though some efforts have been made to construct non-commutative LWE problems, for example [8,16], the majority of non-commutative cryptography has relied on group theoretic constructions, whose underlying hard problems are often less robust than those of lattice cryptography. Somewhat informally, for a cyclic algebra Aand well-chosen parameters there exists an automorphism θof Rqand a γ∈Rqsuch that an LWE style sample a·s+eover Acan be written in matrix–vector form ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ a0γθ(ad−1)γθ 2(ad−2)...γθ d−1(a1) a1θ(a0)γθ 2(ad−1)...γθ d−1(a2) a2θ(a1)θ 2(a0)...γθ d−1(a3) . . .. . .. . ..... . . ad−1θ(ad−2)θ 2(ad−3) ... θd−1(a0) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ s+e=b where all entries and operations are now over Rq. Though more complex than the transformation taking LWE to RLWE this fulfills our goal of providing a structured version of MLWE, since we have replaced the uniformly random matrix Aover Rqwith a structured matrix which we denote φ(a)that requires a factor of dless storage. Of course, by applying the rot(·)operation coordinatewise, one can extend this to a high-dimensional version of the LWE problem, now with two sets of structure lying on top of each other.
22 Page 4 of 67 C. Grover et al. 1.1. Contributions and Methodology The main novel contribution of this work is a definition of Cyclic Algebra LWE (CLWE), together with justifications for its construction and a polynomial time reduction from short vector problems over matrix lattices induced by two-sided ideals in the maximal order of a cyclic algebra to CLWE, establishing its security on the assumption that such problems are hard. As in [27], the algorithm bases the security of CLWE on short vector problems over two-sided ideal lattices in A; similarly to ideal lattices in K, these have some extra underlying structure that might make computational problems easier. However, we leave the relative complexity of these problems an open area of investigation. CLWE represents a middle ground between RLWE and MLWE. Cyclic algebras are equipped with a proper ring multiplication which preserves the dimension of the lattice. Specifically, we consider the following advantages of our CLWE construction: – Efficiency. CLWE can be seen a structured variant of MLWE. Assuming for simplicity that the public key in LWE-based schemes is a sample (A,b), a public key generated as A=rot(φ(a)) requires only as much storage as that of an equivalent dimension RLWE public key.1On the negative side, one should note that we do not know currently how to construct CLWE instances of arbitrary dimension, which might have an impact on concrete efficiency of the schemes. – Security. Recent works on quantum attacks on related ideal lattice problems (e.g., [10,14,17,18] amongst others) require that the underlying group, in this case the unit group of OK, is commutative, see, e.g., [20], which is untrue for a non-commutative algebra. We conjecture that the security level is higher than RLWE, but welcome further cryptanalysis. We actively avoid known attacks on previous attempts to create structured MLWE (see Sect. 3.2). We remark that solving ideal-SVP in a number field is not known to impact the security of RLWE. Moreover, there are currently no known algorithms solving RLWE faster than MLWE for similar parameter sets (either theoretically or practically). It is even known from [2] that for some specific choices of parameters, RLWE is asymptotically no easier than MLWE. – Decryption failure rates. The scalar multiplication of MLWE is dimension-lossy. In other words, the message space of MLWE is restricted in Rq, whose dimension is smaller than that of the module lattice. It leaves less room for error correction coding in MLWE-based schemes (e.g., a KYBER instance for a key size of 256 within Rqof dimension 256). In contrast, the dimension of the message space of CLWE is that of the (non-commutative) ring, which is higher by a factor of d. Thus, it accommodates better error correction coding (see Sect. 5.2), and low decryption failure rates are desired under chosen ciphertext attacks (CCA). Even trivial repetition coding can dramatically reduce decryption failure rates (e.g., NewHope)2 1In practice, a seed is often used to generate the matrix A, which, however, requires a pseudorandom generator under the random oracle model. By contrast, CLWE does not require the random oracle model. Moreover, certain applications do not permit the use of a seed, e.g., pseudorandom functions [7]. 2The same result could be obtained in MLWE by increasing the public key and ciphertext sizes by a factor 2: instead of considering an MLWE sample (A,b) with a vector b, one could consider a square matrix B, whose columns correspond to independent LWE samples using the same matrix A.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 5 of 67 22 Our search-to-decision reduction only holds for one choice of modulus q(once the algebra has been fixed) and structured modules of constant rank d. This issue needs to be remedied in the future. 1.2. Related Work and Organization This work is related to a number of different areas: lattice-based cryptography, information theory and number theory. In lattice-based cryptography, an alternative construction for structured module LWE, called multivariate-RLWE, was presented in [35,36], where they tensor product two (or more) number fields in order to provide a structured module matrix. However, an efficient implementation of [35] was attacked in [12], together with a warning about taking care when putting structure on a module. In short, [12] attacks certain instances of multivariate-RLWE by providing a homomorphism to some underlying subfield K, dramatically reducing the dimension of the lattice problem to be attacked. Fortunately for this work, a somewhat technical condition on the choice of γknown as the non-norm condition precludes such a homomorphism existing to reduce the dimension of CLWE (see Sect. 3.2). It is worth pointing out that that their problem has been addressed in [36], and in fact this fix looks somewhat like our non-norm condition (e.g., unlike the original version, full rank is maintained in [36]). This paper is inspired by the abundant literature of space-time coding based on cyclic division algebras (see the monographs [9,32] and references therein). On a high level, our construction is reminiscent of multiblock space-time codes [21,23], with the caveat of scaling up the number of blocks to make the codes practically undecodable. In the context of space-time coding, our construction generalizes [21] and offers greater flexibility in the code parameters (the number of blocks vs. the number of antennas). Multiblock spacetime codes have been used in [25] to achieve information-theoretic security over wiretap channels, as opposed to computational security in a classic cryptographic setting of this paper. There is a major difference between the roles of cyclic algebras in coding and cryptography, though: the primary concern for coding is the non-vanishing determinant (NVD), while the non-commutative ring structure becomes crucial for cryptography. For efficient multiplication of elements in a cyclic algebra, we heavily rely on the CRT technique of [33]. We present two approaches (subfields and compositum fields) to the construction of novel cyclic division algebras, which enlarge the pool of algebras and may find other applications. Specifically, our proof that the natural order of the family of cyclic division algebras constructed in Theorem 2(including those in [21]) is in fact maximal, is an original contribution. The rest of this paper is organized as follows. In Sect. 2we provide necessary background material on lattices, number fields, and cyclic algebras. In Sect. 3we provide a definition and discussion of CLWE, together with novel constructions of cyclic division algebras for the CLWE problem. In Sect. 4we provide a reduction from structured lattice problems to search CLWE, as well as a search-worst case decision reduction for CLWE. In Sect. 5we show a sample CLWE cryptosystem and provide an estimate of its asymptotic operation complexity. Finally, the paper is concluded in Sect. 6with a
22 Page 6 of 67 C. Grover et al. discussion of open problems. For a smooth flow of the main text, certain proofs, sideline discussions and technical details are deferred to appendices. 2. Preliminaries 2.1. Lattices A lattice is a discrete additive subgroup of a vector space V.IfVhas dimension n a lattice Lcan be viewed as the set of all integer linear combinations of a set of linearly independent vectors B={b1,...,bk}for some k≤n, written L=L(B)= {k i=1zibi:zi∈Z}.Ifk=nwe call the lattice full-rank, and we will only consider lattices of full-rank. We can extend this notion of lattices to matrix spaces by stacking the columns of a matrix. We recall two standard lattice definitions. Definition 1. Given a lattice Lin a space Vendowed with a metric ·, the minimum distance of Lis defined as λ1(L)=minv∈Λ/{0}v. Similarly, λn(L)is the minimum length of a set of nlinearly independent vectors, where the length of a set of vectors {x1,...,xn}is defined as maxi(xi). Definition 2. Given a lattice L⊂V, where Vis endowed with an inner product ·,·, the dual lattice L∗is defined L∗={v∈V:L,v⊂Z}. 2.2. Gaussian Distributions Definition 3. For a vector space Vwith norm ·and an r>0, we define the Gaussian function ρr:V→(0,1]by ρr(x)=exp(−πx/r2). We can use this function to define the spherical Gaussian distribution Drover V, which outputs vwith probability proportional to ρr(v). Similarly, we can sample an elliptical Gaussian Drin a basis b1,...,bnof V,forr=(r1,...,rn)a vector of positive reals, by sampling x1,...,xnindependently from the one-dimensional Gaussian distributions Driand outputting n i=1xibi. When sampling a Gaussian over a lattice L, we will use the discrete form of the Gaussian distribution. We define the distribution DΛ,rover Λby outputting xwith probability ρr(x) ρr(L)for each x∈L. This version of the discrete Gaussian is centered at 0, which in general need not be the case. An important lattice quantity, known as the smoothing parameter, was introduced in [31]. The motivation for the name is provided by Sect. 1following the definition. Definition 4. For a lattice Land ε>0, the smoothing parameter ηε(L)is defined as the smallest r>0 satisfying ρ1/r(L∗/{0})≤ε. The following is a special case of [31], Lemma 4.1.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 7 of 67 22 Lemma 1. For a lattice Lover Rn,ε>0,r≥ηε(L), and x∈Rn, the statistical distance between (Dr+x)mod Land the uniform distribution modulo Lis bounded above by ε/2. Equivalently, ρr(L+x)∈[1−ε 1+ε,1]·ρr(L). We introduce well-known lemmas used to relate the smoothing parameter to standard lattice properties. The first comes from [6], the second from [40]. Lemma 2. For a lattice Lof dimension n and c ≥1, it holds that c√n/λ1(L∗)≥ηε(L) for ε=exp(−c2n). Lemma 3. For a lattice Land ε∈(0,1), it holds that ηε(L)≤√log(1/ε)/π λ1(L∗). 2.3. Algebraic Number Theory Definition 5. A number field Kis a finite degree extension of the rationals Q. Typically, we define a number field by adjoining some algebraic element α∈Cand set K=Q(α). The degree of Krefers to its degree as a field extension. To define a cyclic algebra, we will need to take an additional extension of K. In particular, we will need the extension to be Galois over K, defined as follows. Definition 6. Let L/Kbe an extension of number fields of dimension d. The Galois group of Lover Kis the group Aut(L/K)of automorphisms of Lthat fix K.Wesay that the extension is Galois if the subfield of Lfixed by Aut(L/K)is exactly K. We define a cyclic Galois extension L/Kto be a Galois extension such that the Galois group of Lover Kis the cyclic group generated by some element θof degree d:= [L: K]. Finally, we require the ring of integers of a number field. Definition 7. Given a number field K, its ring of integers OKis the ring consisting of those elements of Kwhose minimal polynomial over Qlie in Z[x]. It is easy to check that if L/Kis an extension of number fields then OL∩K=OK. 2.3.1. The Canonical Embedding Let K=Q(α) be a number field of degree n. It is a well-known fact that there are exactly ndistinct ring embeddings σi:K→C. These embeddings correspond to the ndistinct injective ring homomorphisms mapping αto the roots of its minimum polynomial f. We split these embeddings and say that there are r1real embeddings (whose image lie in R) and r2conjugate pairs of complex embeddings (the complex embeddings come in pairs since complex roots of foccur in conjugate pairs), such that r1+2r2=n. The standard convention is to order the embeddings such that the r1real embeddings come first and the complex embeddings are arranged such that σr1+j=σr1+r2+jfor 1≤j≤r2.
22 Page 8 of 67 C. Grover et al. Definition 8. Let K=Q(α) be a number field of degree n=r1+2r2. The canonical embedding σis the ring homomorphism σ:K→Rr1×C2r2defined by σ(x)=(σ1(x), . . . , σn(x)). Formally, σmaps into the space H={(x1,...,xn)∈Rr1×C2r2|xr1+r2+j=xr1+j∀1≤j≤r2}⊂Cn, which is isomorphic to Rnas an inner product space. We can equip Hwith the orthonormal basis {hi}, where hi=eifor 1 ≤i≤r1 and hj=1 √2(ej+ej+r2), hj+r2=√−1 √2(ej−ej+r2)for r1<j≤r1+r2, and use the well-defined pnorm induced by viewing Has a subset of Cn. Observe that multiplication in Kmaps to coordinatewise multiplication in H.The2norm on H allows us to efficiently sample a Gaussian distribution Drover Kby sampling such a Gaussian coordinatewise over H, although technically this distribution is over the field tensor product KR=K⊗QR∼ =H. Furthermore, it satisfies the property that for any x∈KRwe have the equality of distributions x·Drand Dr, where r i=ri·|σi(x)|. When we have an extension of number fields L/K, we will denote their respective canonical embeddings σLand σKas maps into HLand HKto avoid confusion. 2.3.2. Relative Embeddings In the case of an extension Lof a number field Kit is sometimes more convenient to apply a different order on its embeddings induced by extending embeddings of Kto those of L. Given a tower L/K/Qwhere Khas degree nand Lhas degree dover K, there are precisely nembeddings σ1,...,σ nof Kinto C. Assuming L/Qis Galois, each of these can be extended to an embedding αi:L→Csuch that αi|K=σi. However, these extensions are not unique, and it is easy to see that there are [L:K]=d choices for each αi. In particular, in the case where L/Kis a cyclic extension with Galois group generated by θit holds that the composite automorphisms αi◦θj(·), 1≤ j≤d, run through the dchoices of αi. Hence, for a fixed choice of α1,...,α nthe nd automorphisms of Lcan each be uniquely represented by some αi◦θj(·), which we denote by αj i(·), 1≤i≤n,1≤j≤d. Given the usual ordering of embeddings of K, this induces two systematic orderings on the embeddings of Lby running through either the ior jcoordinates first. 2.4. Cyclic Algebras Definition 9. Let Kbe a number field with degree n, and let Lbe a Galois extension of Kof degree dsuch that the Galois group of Lover Kis cyclic of degree d,Gal(L/K)= θ. For nonzero γ∈Kwe define the resulting cyclic algebra A=(L/K,θ,γ):= L⊕uL ⊕... ⊕ud−1L
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 15 of 67 22 Definition 14. Let Abe a cyclic algebra, let Ibe some (possibly fractional) ideal of the natural order Λ. Then, for an approximation factor ξ≥1, the A-SVPξis to find a nonzero element a∈Isuch that |a|:=σA(a)2≤ξ·λ1(I), where as usual λ1(I) denotes the minimal length of nonzero elements of Iin the given norm. Remark 2. When we use these problems in our security reductions, we will assume that the ideals are in fact integral ideals (e.g., we exclude fractional ideals). Observe that this may be done without loss of generality, since solving the A-SVP problem on the fractional ideal Imay be done by solving it on the integral ideal cI(where c∈Kis the element such that cIis integral) and rescaling the solution. Essentially we have a specialized version of the SVP problem; we must find an element of Iwith minimal norm (up to approximation factor) in the ideal I. The extension of SIVP to A-SIVP is analogous, but since we consider our objects as Z-lattices we require the independent ‘vectors’ a1,...,arto be linearly independent over Z. For BDD, we need a suitable ambient space, and use the following definition. Definition 15. Let Abe a cyclic algebra, let Ibe some (possibly fractional) ideal of a maximal Z-order Λ, and let δ<λ 1(I)/2. Then the A-BDDI,δ problem, on input y=x+efor x∈Iand e∈d−1 i=0uiLRsatisfying |e|≤δ, is to compute x. 2.6. The Learning with Errors Problem We will briefly recall the initial Learning With Errors (LWE) problem here; in Sect. 3we will extend it to cyclic algebras. The problem comes in two forms; search and decision, both of which are based on the LWE distribution. Let nand qbe positive integers, and let α>0 be some error parameter. Define T:= R/Z, the unit torus. Definition 16. For a secret s∈Zn q,asample(a,b)←As,α is taken by sampling a uniformly random vector a∈Zn qand e←Dαand outputting (a,b)=(a,a,s/q+e mod Z). Given the above distribution, the LWE problem comes in two forms. Definition 17. The search LWE problem is to recover sfrom a collection of samples As,α. The decision LWE problem on input a collection of samples on Zn q×Tis to decide whether they are uniform samples or were taken from As,α for some secret s, where sis drawn uniformly at random from Zn q. Typically, the number of samples provided in each of these problems depends on the application. Since the decision problems has a probabilistic element, we will be interested in the advantage of the algorithms that solve it, which is defined as the difference between their acceptance probabilities on samples from an LWE distribution As,α and the uniform distribution. In practice, the decision problem is of more interest in cryptography.
22 Page 16 of 67 C. Grover et al. We will not define the popular extensions of these problems to number fields or modules, known as Ring-LWE and Module-LWE, but the unfamiliar reader may find details in [27] and [22], respectively, both of which we reference frequently in this work. 3. The CLWE Problem In this section we present the general definition of CLWE together with justifications for choices made in the definition, as well as constructions of specific algebras to use. We will save the security properties for Sect. 4.1. Definition 18. Let L/Kbe a Galois extension of number fields of dimension [L:K]= d,[K:Q]=nwith cyclic Galois group generated by θ(·).LetA:= (L/K,θ,γ)be the resulting cyclic algebra with center Kand invariant uwith ud=γ∈OK.LetΛbe an order of A. For an error distribution ψover d−1 i=0uiLR, an integer modulus q≥2, and a secret s∈Λ∨ q, a sample from the CLWE distribution Πq,s,ψ is obtained by sampling a←Λquniformly at random, e←ψ, and outputting (a,b)=(a,(a·s)/q+e mod Λ∨)∈(Λq,d−1 i=0uiLR)/Λ∨. Remark 3. Unlike in commutative spaces, the order of multiplication of aand sis important; our choice is (a·s), but similar security properties would hold if one took (s·a)instead. Also observe that our modulo reduction in the second coordinate of the pair is well defined, since (a·s)∈Λ∨ q. As usual, the associated CLWE problem will come in search and decision variants. Definition 19. Let Ψbe a family of error distributions over d−1 i=0uiLR. The search CLWE problem, which we denote by CLWEq,s,ψ , is to recover sfrom a collection of independent samples from Πq,s,ψ for arbitrary s∈Λ∨ qand ψ∈Ψ. We do not state the number of samples allowed for this (or the next) problem, as typically it depends on the application. Definition 20. Let Υbe some distribution on a family of error distributions over d−1 i=0uiLRand UΛdenote the uniform distribution on (Λq,( d−1 i=0uiLR)/Λ∨). Then, the decision CLWE problem, written D-CLWEq,Υ , is on input a collection of independent samples from either Πq,s,ψ for a random choice of (s,ψ)←U(Λ∨ q)×Υor from UΛ, to decide which is the case with non-negligible advantage. 3.1. Discussions 3.1.1. Relation to Module-LWE First, we explain why we choose the order of multiplication a·s. As discussed in the introduction, the transformation from a (primal) RLWE sample to nrelated LWE samples provides our motivation. Here, one RLWE sample a·s+e, where a,s,e∈Rq∼ =Zq[x] xn+1, generates nLWE samples by considering the multiplication operation as As+e, where A:=rot(a)is a negacyclic matrix. For appropriate choices of error distributions, this is
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 17 of 67 22 precisely nLWE samples with the exception that there is some structure in the matrix A. By ordering the multiplication a·s, we get a similar transform from CLWE to MLWE. Assuming for now that we have a discretized form of CLWE, and observing that for q∈Zwe have Λq∼ =d−1 i=0uiOL/qOL(see [33]), we transform a CLWE sample a·s+einto matrix–vector form to get φ(a)·s+e, where sand eare vectors of dimension dover OL/qOL. Setting A=φ(a), one can see that for appropriate choices of error distribution this is similar to dsamples from the MLWE distribution with some additional structure in the matrix A, as intended. 3.1.2. The Natural Order vs. Maximal Order In this work we consider the case where the natural order Λof Ais also a maximal order. The benefit of using the natural order is that it is simple to construct and represent, whereas finding a maximal order is computationally slow. Additionally, the natural order is somewhat orthogonal, in the sense that it has the same span in each uicoordinate independently of the other coordinates. This is advantageous when considering the relation to MLWE, where the module is always taken to be the full module Od K. As mentioned above, two-sided ideals in a maximal order form a free abelian group, which is not necessarily the case in the natural order. Further, as lattices, a maximal order gives denser (maximally so) sphere packing than the natural order, since the latter is a sublattice (of at least one maximal order). Fortunately, we will construct in Theorem 2 cyclic algebras whose natural order is also maximal, thus enjoying both the simplicity of the natural order and the convenience of a maximal order. Example 2. Quaternion algebra over Qis defined by H={x+jy :x,y∈Q(i)}, with the usual relations i2=j2=−1 and ij =−ji. It can be seen as a cyclic division algebra (Q(i)/Q,(·), −1)where (·)denotes the complex conjugate and −1 is a nonnorm element. A quaternion has matrix representation x−y yx. The Lipschitz integers L⊂Hform the (non-maximal) natural order L= {x+jy :x,y∈Z[i]}.The maximal Hurwitz order is given by H={a+bi +cj +d(−1+i+j+ij)/2:a,b,c,d∈Z}. It is easy to check that, as Z-lattices of dimension 4, the Lipschitz order is a sublattice of the Hurwitz order, of index 2. 3.1.3. A Pair of Number Fields In MLWE, we are free to choose the dimension of our module over the underlying number field K. However, in the cyclic algebra case we are restricted to cases where we can find L,K, and γsuch that A=(L/K,θ,γ)is well defined. From a theoretical standpoint it is not immediately clear whether we want to consider asymptotic security in terms of nor d, but following our motivation from MLWE we suggest that nis likely
22 Page 18 of 67 C. Grover et al. the suitable choice since the module dimension dis typically small in applications using MLWE, whereas the dimension of the underlying field Kis large. However, there seems to be no a priori reason why with the right techniques one could not consider both nand dasymptotically; the only case a cyclic algebra precludes is high-dimensional MLWE over a low dimension number field L, because the parameter doccurs in both the module and field dimension. 3.2. Evading BCV Style Attacks In our CLWE construction we have enforced that γis selected so that Ais a division algebra. We do this to avoid attacks in the style of [12]onthem-RLWE protocol. For m=2, the m-RLWE protocol of [35] can be considered as a structured variant of MLWE, where the matrix Ain the operation As+eis a negacyclic matrix over some ring Rq. More explicitly, 2-RLWE considers the tensor product of two fields K=K1⊗K2and runs the LWE assumption in the ring of integers Rq. The example use case given in [35] considers power-of-two cyclotomics K1,K2defined by the polynomials xk1+1 and yk2+1, respectively, claiming that the resulting problem in Rq=Zq[x,y] (xk1+1,yk2+1) effectively corresponds to an RLWE problem of dimension k1·k2due to an obvious homomorphism between Kand the two-power cyclotomic field Lof degree k1·k2.The problem also represents a structured MLWE instance over Zq[x] (xk1+1)of dimension k2. However, the observation of [12] is that there is a smaller field Kcontaining K1 such that there is a homomorphism from Kinto Kwith a well-defined image for y. This is because the roots of distinct two-power cyclotomic polynomials are algebraically related. For example, in the case k1=8,k2=4, it is clear that the map taking yto x2and fixing K1is a well-defined homomorphism from Kto K1. Using this homomorphism, [12] simplifies the problem of solving one 2-RLWE instance by considering it as four RLWE instances in dimension k1rather than one instance in dimension k1·k2, essentially removing the module dimension k2from the problem. We argue that the non-norm condition of γprecludes the existence of a homomorphism removing the module structure by taking a well-defined cyclic algebra A=(L/K,θ,γ) to a smaller subfield containing K. We restrict our search to maximal subfields of A, since any subfield is contained in at least one maximal subfield. It is a well-known result on division algebras that any maximal subfield Eof Acontains Kand satisfies [E:K]=d, and that in the case of a cyclic division algebra Athere is a choice of u∈Asuch that the cyclic algebra A:= jujEis isomorphic to A(see Sect. 15.1, Proposition a of [41]). Assume, for a contradiction, that we had such a homomorphism χ:A→L, where without loss of generality we assume the maximal subfield is L by the aforementioned proposition. Since Lis Galois, the restriction of χto Lis an automorphism of L. It is clear that χmust agree on conjugates, since χ(u)·χ() = χ(u·) =χ(θ()·u)=χ(u)·χ(θ()) for any ∈L. However, this contradicts χbeing injective on Land it follows that no such homomorphism exists. Hence, we conclude that the attack style of [12] does not threaten our algebraic structure.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 19 of 67 22 3.3. Concrete Algebras for CLWE In order to apply the CLWE assumption in a practical cryptosystem, one must choose a concrete algebra as an ambient space. More generally, we are interested in finding families of algebras suitable for CLWE that allow for asymptotic analysis and varied security levels. Our search for algebras is motivated by the restrictions and conditions discussed in the previous section. In particular, we are interested in cyclic division algebras satisfying the following properties: – The non-norm element γmust lie in OKto keep the natural order closed under multiplication, and should satisfy |γ|=1 in order to maintain both the coordinatewise independence and sub-multiplicative properties of the norm.3 – The dimension n:= [K:Q]of the division algebra should be large and the degree d:= [L:K]should be small. This is to maintain the analogy with structured MLWE (the degree corresponds to the module rank) and follows from the searchdecision reduction, which takes time polynomial in nbut not in d. – The base field Kshould be cyclotomic and qshould split completely in K.Thisis also a result of the methodology of the search-decision reduction, which uses the well-understood factorization of qin OK. In addition, since the bulk of latticebased cryptography is done over cyclotomic fields, we consider algebras which are small extensions of these as somewhat natural. We observe that an improved proof of decision security may allow this point to be dropped, whereas the other two points feel more integral. Although significant effort has been expended by coding theorists to construct cyclic division algebras satisfying a variety of conditions, such as in [44]or[21], we find ourselves with a fairly unique set of restrictions. In particular, for reasons relating to desired applications, the majority of algebras used in coding theory are either of small total dimension or have small [K:Q]and scale asymptotically in [L:K]. Since we are interested in scaling up Kasymptotically, we will have to build novel algebras satisfying the above requirements ourselves. We will, however, make heavy use of the following theorem as an intermediate step. Here ζmdenotes a primitive mth root of unity where ϕ(m)=nis the degree of the base field K=Q(ζm). Theorem 1. [21]Let m =pabe a prime power and let K =Q(ζm). Then, there exist infinitely many cyclic Galois extensions M/K of degree m such that ζi mis not a norm of M/Kfor0<i<m. We remark that the theorem is effective in the sense that it provides an explicit description of M, and we provide a summary of the recipe for constructing M. The crucial aspect of its construction is that Mis a subfield of some cyclotomic extension of K,K(ζq)for aprimeq, but we present its full description for completeness. 3We abbreviate the condition |σi(γ )|=1 for all iby |γ|=1, since in fact these are equivalent for algebraic γ.
22 Page 20 of 67 C. Grover et al. First, find some prime qsuch that q=1modpabut q= 1modpa+1, so that pais the highest power of pdividing q−1.4Set M=K(ζq)so that by coprimality M=Q(ζmq). Then Gal(M/K)is a cyclic group of order q−1 generated by some automorphism σ. Denote by Mthe subfield of Mfixed by σm. Then [M:K]=mby the fundamental theorem of Galois theory and the extension is both cyclic and Galois. Finally, localization theory is used to show that the powers of ζmare not norms in this extension. In this way, the theorem constructs Mexplicitly. The part of this theorem of our interest is that it allows us to scale Kasymptotically, but this comes with a drawback of very high degree M,i.e., it only permits a degree-m extension Mof a degree-ϕ(m)base field K. We present a new method that uses this theorem as a starting point to construct good algebras satisfying our restrictions. More precisely, our construction will begin with Theorem 1and then use elementary methods from Galois theory to build more favorable fields. 3.3.1. Constructions using Subfields We squash the field Mfrom Theorem 1to a subfield Lof small index over the base K satisfying the necessary properties to generate a cyclic algebra. Theorem 2. Let K =Q(ζm), where ϕ(m)=n, be a prime power cyclotomic with m=pafor some integer a and prime p. Then, there exists a cyclic Galois extension L/K of any index d dividing m within which ζmsatisfies the non-norm condition. Remark 4. Since the proof will provide an explicit description of L, the correct interpretation of this theorem is that we can construct cyclic division algebras A=(L/K,θ,γ) with θ=Gal(L/K), γ =ζm,K=Q(ζm), and [L:K]is any divisor of m=pa. Figure 2shows all possible cases of intermediate field Lbetween Kand M. Proof. Let K=Q(ζm)for a fixed m=pawith prime pand integer a. Following the construction of Theorem 1fix a cyclic Galois extension M/Kof degree msuch that ζi m is not a norm of an element of Minto Kfor any i=1,2,...,m−1. We will choose L as a suitable intermediate extension M/L/K.Letσdenote the generator of Gal(M/K), an automorphism of degree m.Forddividing m,σdfixes an extension Lof Kwith [M:L]=|Gal(M/L)|=m/dand it follows from the tower lemma that [L:K]=d. We will show that Lis a satisfactory extension of K. First, since Gal(M/L)is a normal subgroup of Gal(M/K)we see that L/Kis a normal, and hence Galois,5extension. It follows from standard Galois Theory that Gal(L/K)∼ =Gal(M/K)/Gal(M/L). Both groups in the quotient are cyclic, and so Gal(L/K)is cyclic with some generator θ. Furthermore, this isomorphism also allows us to deduce |Gal(L/K)|=d. 4It is easy to show that infinitely many primes satisfying this condition always exist by appealing to classical theorems of Chebotarev or Dirichlet. 5Since in this case all extensions are separable.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 21 of 67 22 Fig. 2. Cyclic subfields between Mand Kfrom Galois correspondence. σidenotes the group generated by σi,whereσis the generator of Gal(M/K). We’ve shown that L/Kis a cyclic Galois extension of degree d; we are left to show that ζi mis not a norm for i=1,...,d−1. Let Mdenote NM/K(M×)and Ldenote NL/K(L×). Say ζi m∈L, fixing x∈Lsuch that NL/K(x)=ζi m. Now by transitivity of the norm, NM/K(x)=NL/K(NM/L(x)) =NL/K(xm/d) =ζ(m/d)i m where the first equality follows from x∈Land the second since the norm is multiplicative. Mdoes not contain any power of ζmexcept ζm m=1 since ζmis a non-norm element in M/K,soitfollowsthatm|(m/d)iand so d|i. From this we conclude that ζm,ζ2 m,...,ζd−1 mdo not lie in Land so ζmsatisfies the non-norm condition. Remark 5. We presented the proof in the above form for ease of legibility, but it is straightforward to extend the argument in the final paragraph to show that ζjd+1 msatisfies the non-norm condition for any j=0,1,...,(m/d)−1. This is an effective construction that allows us to build cyclic division algebras of the form A=(L/K,θ,γ)where |γ|=1, Kis an arbitrary prime power cyclotomic, and L is an extension of Kwith degree divisible by the prime p. For cryptographically relevant examples, we can consider degree 2 or 4 extensions of a 2-power cyclotomic or degree 3 extensions of a 3-power cyclotomic. Given the impossibility result of Appendix Aand the restriction on the absolute value of γ, we view these algebras as essentially the best possible, at least for the case where Kis a prime-power cyclotomic.
22 Page 22 of 67 C. Grover et al. As discussed in Sect. 3.1, the natural order is not necessarily a maximal order. Nevertheless, the following theorem shows that the specific family of algebras we have constructed in Theorem 2represents a lucky case (its proof is given in Appendix B). Theorem 3. For the family of cyclic division algebras A=(L/K,θ,ζ m)constructed in Theorem 2, the natural order of Ais maximal. This makes our constructed family of algebras very attractive, as it enjoys both the simplicity of the natural order and the nice property of a maximal order. Remark 6. In the context of multiblock space-time coding [21], the construction of Theorem 1allows for a space-time code for mantennas and ϕ(m)blocks, i.e., a relatively small number of blocks. With our new construction Theorem 2, any number ϕ(mk), k∈Nsuch that mk is a power of p, of blocks becomes possible. Further, using a maximal order leads to optimum coding gains; it was not realized in [21] that the natural order from Theorem 1is actually maximal. 3.3.2. Constructions using Compositum Fields The algebras with prime-power cyclotomic centers of the previous subsection use the field construction technique of Theorem 2, and as such they are restricted to algebras whose dimension Nis in the form pk(p−1)for a prime pand integer k. We present another method of constructing algebras using compositum fields that allows us to target dimensions not achievable in this setting. This method starts from extensions which are nearly what we are looking for and applies field compositums (cf. [43, Chapter 30]). Say we have a Galois field extension L/Kwith non-norm element γ∈OKwhose Galois group is cyclic of degree d.LetF be some other Galois number field with F∩L=Q. Then Gal(LF/KF)∼ =Gal(L/K) and γis a non-norm element in LF/KF. Relabeling this extension as L/Kand letting θdenote the cyclic generator of the Galois group gives a cyclic field extension with non-norm γsuch that [L:K]=dand [K:Q]=[K:Q]·[F:Q]. The relations among these fields are illustrated in Fig. 3a. One can generalize this method to the case where the base field can not be written conveniently as a compositum of two fields. Let L/Kbe a cyclic Galois extension of degree dwith non-norm element γand let Kbe another Galois number field which contains K. Then KL/Kis a cyclic Galois extension of degree kfor some kdividing d, and in particular if K∩L=Kthen k=dsince the fields are linearly disjoint above K. See Fig. 3b for the relations among these fields. Similar to the subfield method, we also have the following theorem for the compositum field method (the proof is given in Appendix B). Theorem 4. Let K =Q(ζn)where n =prand p is prime, L/K be a finite cyclic extension of degree d with Gal(L/K)=θand Gal(L/Q)abelian, and F =Q(ζqt) where F ∩L=Q. Suppose the natural order Λ⊂A=(L/K,θ,ζ n)is maximal. Then, if [F:Q]and d are coprime, the natural order Λof the cyclic division algebra A=(LF/KF,θ,ζ n)is also maximal.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 23 of 67 22 Fig. 3. Constructions using field compositums: abase field Kis a compositum KF,bKcannot be written as a compositum. Table 1. Sample parameters of cyclic algebras. Method Center Kn=[K:Q]d=[L:K]Total dimension N=nd2of A Subfield Q(ζ81)54 3 486 Subfield Q(ζ256)128 2 512 Subfield Q(ζ64)32 4 512 Subfield Q(ζ512)256 2 1024 Subfield Q(ζ128)64 4 1024 Subfield Q(ζ243)162 3 1458 Compositum Q(ζ192)64 3 576 Compositum Q(ζ576)192 2 768 Compositum Q(ζ384)128 3 1152 The subfield method is given in Sect. 3.3, while the compositum method is given in Appendix 3.3.2 3.4. Sample Parameters Now that we have discussed our techniques for constructing suitable number fields we proceed to demonstrate that these methods are able to attain cryptographically relevant dimensions. In this section, we present a small selection of proof-of-concept dimensions in Table 1where we take our motivation for choices of dimension from KYBER and NewHope, since they are the successful second round NIST candidates whose methods are most similar to our own. Thus, we aim for dimensions in the region of between 512 and 1024, dimensions proposed for both NewHope and KYBER (which also achieves dimension 768). Of course, these schemes are restricted to having power-of-two ring dimension nand so their choices of dimension may not be optimal in general, but FrodoKEM [13], a plain LWE scheme, suggests dimensions in around the same range, specifically 640, 976, and 1344, so we consider dimensions in this region a sensible starting point. Corresponding to KYBER and other MLWE-based schemes we will set a small ‘module’ rank d:= [A:L]. We are constricted in our choice of fields by the fact that dappears as a square in the total dimension N=nd2, but for the most part we are able to work around this problem.
22 Page 24 of 67 C. Grover et al. 3.4.1. Subfields Two-Power Cyclotomic K We begin with straightforward cases where we can apply Theorem 2immediately to obtain fields in suitable dimensions. Let Kbe a two-power cyclotomic field, K=Q(ζ2k), with dimension n:= 2k−1. Since the rank d=[L: K]=[A:L]is a small power of two, the dimension nof Kwill be dictated by the choice of module rank d. We construct rank 2 and 4 examples as follows: –Ford=2wehave[A:K]=4, so for total dimension 1024 we set K=Q(ζ512). –Ford=4wehave[A:K]=16, so for total dimension 1024 we set K=Q(ζ128). To obtain algebras in dimension 512, simply pick Kwith dimension n/2 e.g., Q(ζ256) and Q(ζ64), respectively. In all cases, Theorem 2lets us pick the non-norm element γ as a root of unity. Three-Power Cyclotomic K Since 3 1024, one cannot achieve algebras in dimension 1024 with a 3-power cyclotomic center and instead we set about searching for algebras of nearby dimensions. Although we are unable to build fields in this case with dimension around 1024, we can get close to the more lightweight cryptographic dimension of 512 used in schemes targeting a lower security level. Recall that if K=Q(ζ3k)then Khas dimension n:= φ(3k)=2·3k−1. Again, the module rank is a power of 3 and the choice of module rank will define the choice of n. –Ford=3wehave[A:K]=9, so for total dimension 486 we set K=Q(ζ81). The next achievable dimension is 1458, for which K=Q(ζ243). –Ford=9wehave[A:K]=81. To achieve the same total dimensions we take small base fields K=Q(ζ9)and Q(ζ27), respectively. 3.4.2. Compositum Fields We give example algebras of dimensions 576, 768 and 1152 in Table 1with less restrictive dimension using field compositum techniques. We propose two alternate methods of applying field compositums in Fig. 3a: either use Theorem 2to make an algebra which already has large dimension by selecting large center Kand small extension L, then compose a small field Fonto Kand Lto tweak the total dimension. Alternatively, one can create algebras by selecting small fields Land Kusing Theorem 1and composing both with a large field F. We begin with an example of the first method that achieves dimension 768. Let Lbe a degree two extension of the field K=Q(ζ64)chosen by Theorem 2with non-norm root of unity γ, so that the corresponding algebra Ahas dimension 128. Compose both Land Kwith the field F=Q(ζ9), denoting the compositums by Land Krespectively. Then γis still a non-norm element in the extension L/K, a degree two extension that is cyclic and Galois, and the algebra A=(L/K,θ,γ)is a cyclic algebra of dimension 6×128 =768, as required. We observe that here the center Kcorresponds to the fields with fast operations used in [29]. Our final method of composing large degree fields onto small degree extensions is aimed at targeting odd module ranks. Begin by choosing the desired module rank das a (likely small) odd prime. Then set K=Q(ζd)and pick Las a cyclic Galois extension of Kin which the dth root of unity is a non-norm element using Theorem 1.Let F:= Q(ζ2k)and again let Land Kdenote its compositum with Land Krespectively.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 31 of 67 22 of distributions z·e+eis fixed. It follows that the extended αifunction maps the Ri−CLWEq,Σαproblem in Ato the same problem in A, and moreover that this map preserves Λ∨and the CRT style decomposition (Lemma 12)ofΛ∨ qby sending Rito some Rj, where jdepends on the choice of σi. We are now ready for the first step of our reduction. Lemma 13. There is a deterministic polynomial time reduction from CLWEq,Σαto RiCLWEq,Σα. Proof. Let Oibe an oracle for the Ri−CLWEq,Σαproblem. Since Lemma 12 defines an isomorphism, it is sufficient to use Oito solve the Rj−CLWEq,Σαfor each j.Letαj/i be an extension of the automorphism of Kmapping qjto qi, which exists by transitivity. Then, given a sample (a,b)←Πq,s,Σ , we construct the sample (αj/i(a), αj/i(b)). Since Λqand Λ∨ qare fixed by each αj/i, the resulting pair is a valid CLWE sample in A=(L/K,θ,αj/i(γ )); feeding these samples into Oioutputs a value tjmod Ri. We claim α−1 j/i(tj)=smod Rj. Since αj/iis an automorphism, each sample (a,b)is mapped to a new CLWE sample (α j/i(a), αj/i(a·s/q+e)mod Λ∨)in a new algebra A. We may write the second coordinate as αj/i(a)·αj/i(s)/q+αj/i(e)mod Λ∨. Since our automorphisms fix our family of error distributions Σαand map the uniform distribution to the uniform distribution, it follows that this is a valid CLWE instance with secret αj/i(s)and error distribution Σ∈Σα. Hence, Oioutputs t=αj/i(s)mod Ri, from which we recover α−1 j/i(t)=smod Rj, as required. 4.2.2. Hybrid CLWE and Search-Decision For this section we must introduce the cyclic algebra analog of the Hybrid LWE distribution used in [27]; we use the decomposition into the rings Rirather than the CRT. Definition 24. For a secret s∈Λ∨ q, distribution Σover jujLR, and i∈[n], we define a sample from the distribution Πi q,s,Σ over Λq×(d−1 i=0uiLR)/Λ∨by taking (a,b)←Πq,s,Σ and h∈Λ∨ qwhich is uniformly random and independent mod Rj,j≤iand 0 mod Rj,j>i, and outputting (a,b+h/q).Ifi=0, we define Π0 q,s,Σ =Πq,s,Σ . Using this distribution we define a worst-case decision problem relative to one Riand reduce it to the search problem Ri−CLWE. Definition 25. For i∈[n]and a family of distributions Σα,theW-D-CLWE i q,Σα problem is defined as the problem of finding jgiven access to Πj q,s,Σ for j∈{i−1,i} and valid CLWE secret sand error distribution Σ∈Σα. For a technical reason in the following proof, we restrict our secret sso that smod Ri lies in a set Giwith the property that g= h∈Giimplies g−his an invertible element. Applying this restriction for each iplaces s∈Gfor a set G=G1×···×Gnof size |G|=i|Gi|. We will call such a set Gapairwise different set. We need to guarantee
22 Page 32 of 67 C. Grover et al. that there exist sufficiently large choices of G. It is not difficult to see that the maximal set sizes |Gi|=qdand |G|=qnd, because any set of matrices in Md×d(Fq)of size at least qd+1 contains two matrices with the same first row, whose difference is therefore uninvertible. Constructions of such maximal sets Gare given in Appendix D. Lemma 14. Assuming constant d and s ∈G, there is a probabilistic polynomial-time reduction from Ri−CLWEq,s,Σαto W-D-CLWEi q,Σαfor any i ∈[n]. Proof. We follow the standard search-decision methodology of guessing the value of the secret mod Riand then modifying the samples so that the decision oracle tells us whether or not our guess was correct. Note that there are only |Gi|possible values of smod Ri, which is bounded above by qd2, polynomial in n, and so we may efficiently enumerate over the possible values. We define the transform which takes a value g∈Λ∨ qand maps Πq,s,Σ to Πi−1 q,s,Σ if g=smod Rior Πi q,s,Σ otherwise as follows. On input a CLWE sample (a,b)← Πq,s,Σ , output the pair (a,b)=(a+v,b+(h+vg)/q)∈Λq×( d−1 i=0 uiLR)/Λ∨, where v∈Λqis uniformly random mod Riand 0 mod Rjfor j= iand h∈Λ∨ qis uniformly random and independent mod Rj,j<iand 0 on the other Rj. It is clear that ais still uniformly distributed on Λq,sowearelefttoshowbis correctly distributed. For a fixed value of a, we write b=b+(h+vg)/q =(as +h+vg)/q+e =(as+h+v(g−s))/q+e, where eis still drawn from Σ.Ifg=smod Ri, then v(g−s)=0modRi, and so the distribution of the pair (a,b)is precisely Πi−1 q,s,Σ . Otherwise, v(g−s)is uniformly random mod Riby assumption on Gand 0 mod the other Rj, and so letting h= h+v(g−s)we see that the distribution of (a,b)is precisely Πi q,s,Σ . Remark 7. This is the only stage of the proof which enforces that the asymptotic complexity scales only with nand not with d, since we are forced to guess all of smod Ri at once. Since the above reduction is secret preserving, the required decision oracle for W-DCLWEi q,Σαhas the additional restriction that s∈G, but for the purposes of the rest of our proof it will be more convenient to have access to an oracle solving the at least as hard problem where sis arbitrary. Additionally, in practical applications we will use the decision problem for arbitrary s, so we see no benefit of the tighter reduction where sis restricted.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 33 of 67 22 4.2.3. Worst-Case to Average-Case Decision Reduction Now that we have removed the restriction that s∈G, we are able to follow the skeleton of the RLWE search-decision reduction of [27] more liberally. Definition 26. The error distribution Υαon the family of possible error distributions is sampled from by choosing an error distribution Σ←Σαand adding it to Dr, where each ri:= α((n·d2)1/4·√yi)for y1,...,yn·d2sampled from Γ(2,1). Definition 27. For i∈[n]and a distribution Υαover possible error distributions, an algorithm solves the D-CLWEi q,Υαproblem if with a non-negligible probability over the choice pairs (s,Σ) ←U(Λ∨ q)×Υαit has a non-negligible difference in acceptance probability on inputs from Πi q,s,Σ and Πi−1 q,s,Σ . This is the average case decision problem relative to Ri; in our worst-case to averagecase reduction we will need to randomize the choice of error distribution, which we do by sampling from Υα. Lemma 15. For any α>0and i ∈[n]there is a randomized polynomial-time reduction from W-D-CLWEi q,Σαto D-CLWEi q,Υα. Proof. Since the definition of Υαis a distribution over the family of distributions obtained by sampling from Σαand adding an elliptical Gaussian, the proof is the same as Lemma 5.12 of [27], except we replace each instance of mod qiR∨with mod Riand each instance of Rqwith Λq. Remark 8. This choice of Υαmeans that the error covariance matrix in our decision problem is closer to diagonal than that in the corresponding search problem! In fact, if one increased the elliptical error in the decision problem, one could ‘flood out’ the non-diagonal entries of the covariance matrix, leading to elliptical error which is easier to handle in practice. Finally, we use a hybrid argument. We must first show that Πn q,s,Σ is uniformly random given Σsampled from Υα, but again this follows the same method as the ring case, except we must replace their use of Lemma 1by [37, Lemma 2.4]. Lemma 16. Let Υαbe as above and let s ∈Λ∨ q. Then given an oracle Owhich solves the D-CLWEq,Υαproblem there exists an efficient algorithm that solves D-CLWEi q,Υα for some i ∈[n]using O. Proof. The proof is identical to the ring case, Lemma 5.14 of [27], except that the indexing set Z∗ mis replaced by [n]. Denote by CLWEq,Σα,Gthe search CLWE problem where s∈Gfor arbitrary fixed G⊂Λ∨ q. To sum up, we have obtained the main result of this section:
22 Page 34 of 67 C. Grover et al. Theorem 7. Let Λbe the natural order of a cyclic algebra A=(L/K,θ,γ),d constant, q ∈poly(n)and assume that α·q≥ηε(Λ∨)for a negligible ε=ε(n). Then, there is a probabilistic reduction from CLWEq,Σα,Gfor any pairwise different G ⊂Λ∨ q to D-CLWEq,Υαwhich runs in time polynomial in n. 4.3. Summary and a Remedy for Secret Space There are certain technicalities and subtleties in our security proof, which we briefly summarize as follows. The hardness of Search CLWE in Sect. 4.1 requires a natural order Λthat is maximal. Nonetheless, Lemma 10 (due to Lemmas 6and 7) is the only stage of the proof that assumes such a natural, maximal order. An improved proof technique may be able to drop this assumption (e.g., to use the natural order). The search to decision reduction in Sect. 4.2 requires a natural order Λ, due to the CRT decomposition of Lemma 12. A better version of CRT may extend the reduction to a maximal order. Fortunately, the orders we take from Theorem 2are both natural and maximal, thereby meeting these requirements. The requirement of unramified qin Theorem 6(due to Lemma 6) is minimal: for the algebras of Theorem 2, the only unsuitable primes are the pand q used in the construction (cf. Sect. 3.3). Lemma 14 enforces that slies in a pairwise different set G. It is the only stage of the proof which requires such a set. We emphasize that our reduction takes the search CLWE problem where s∈Gfor arbitrary fixed G to the decision CLWE problem for arbitrary secret s. In other words, we claim hardness for the full decision problem, based on hardness of a restricted search problem. Also, our reduction implies that the decision problem is as hard as the search problem for the hardest choice of G. See Appendix D for more details. Remark 9. The so-called normal form is used de facto in LWE-based cryptography. We note that the normal form reduction is agnostic to the secret space G. More precisely, starting with a secret s∈Ggets cancelled in the transformation and replaced by a new secret sderived from the error distribution (see Lemma 18 in Sect. 5.1). Therefore, the secret space in the normal form of CLWE is the expected space in relation to other LWE normal forms. Even if our secret space is still exponentially large in n, it may be a concern with security of CLWE if the above reductions were best possible (e.g., decision CLWE is polynomial-time equivalent to restricted search, rather than at least as hard). Fortunately, it is possible to remedy the loss of secret space by using a prime modulus qthat totally ramifies in relative extension L/K. The proofs of the following theorems are given in Appendix E. Theorem 8. Let Abe a cyclic division algebra over a number field L with center K and natural, maximal order Λwith |γ|=1. Let α=α(n)∈(0,1)and q =q(n)≥2,
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 35 of 67 22 completely split in K , and the ideals above q in K totally ramify in L, be parameters such that α·q≥ω(√log N). Then, there is a polynomial-time quantum reduction from A-DGSI,ξ to search CLWEq,Σαfor any ξ=r·√dω(log (d·n))/αq, where d is constant, r >√2q·ηε(I)and Iand qΛare coprime. Note the DGS to search CLWE reduction requires a restriction on the ideal lattice problems that it holds for, but the search to decision part does not depend on any chosen ideal: Theorem 9. Let Λbe the natural order of a cyclic division algebra A=(L/K,θ,γ), d is constant, q ∈poly(n)such that the ideals above q in OKare maximally ramified in OL, and assume that α·q≥ηε(Λ∨)for a negligible ε=ε(n). Then, there is a probabilistic reduction from CLWEq,Σαto D-CLWEq,Υαwhich runs in time polynomial in n. 4.3.1. Explicit Primes for the Reduction Which primes is the reduction valid for? We need q∈Zsuch that qsplits completely in K, say as qOK=q1...qg, and that these primes are maximally ramified in L, i.e., qiOL=Q[L:K] i. To find such primes, we need to review how the algebras used are constructed. We set K=Q(ζm)and M=Q(ζmq), where q=1modmis a prime, and gcd(m,q)=1. For a degree dextension of K, fix an intermediate field K⊂L⊂Mof the correct degree, via the generator of the Galois group of M/K. Recall that we impose gcd(d,m)>1. From [45], the ramified primes of Qin Mare the primes dividing mq, and the ramified primes of Kin Mare the primes dividing q. Since qis prime, there is only one prime qdividing it, which is itself. To see that q=qhas the correct ramification, observe the following: By our choice of q, it is completely split in K. If we label the ramification index e, the inertial degree f, and the number of primes qsplits into by g, using the identity [K:Q]=eq K/Qfq K/Qgq K/Q, we know that gq K/Q=[K:Q], and fq K/Q=eq K/Q=1. Moreover, qis ramified in Q(ζmq), and qdoes not divide m. This (with the condition on q)impliesthat fq M/Q=1. Also, eq M/Q=φ(q)=q−1=[M:K]and gq M/Q=[K:Q] . Multiplicativity of the ramification index and inertial degree then gives eq L/K=[L:K], fq L/K=1 and gq L/K=1, for any intermediate field L. This means that once an algebra is fixed, there is only one prime that the above reduction is valid for. This might seem like a significant issue; but, to construct an algebra of fixed size, there are infinitely many primes qthat can be used to construct M, and thus L. This means that if we know the kind of prime we want to use before the algebra is constructed, there are in effect infinitely many primes to choose from. For example, we can consider K=Q(ζ128), and construct a degree 4 extension of Kto generate an algebra of dimension 1024 over Qusing the prime q=3457, and the above reduction holds for those parameters.
22 Page 36 of 67 C. Grover et al. 5. CLWE in Cryptography In this section we present a proof-of-concept cryptosystem using CLWE. To demonstrate our comparison against MLWE our scheme will closely resemble the typical ‘compact’ LWE cryptography schemes over modules, in particular KYBER (see [5]), although it is likely that an adaptation of Regev style encryption from [42] would suit CLWE as well. 5.1. Making CLWE Suitable for Cryptography: Normal Form We implicitly use some standard LWE facts: firstly, we discretize our error distribution eto Λ∨ q; discretizing does not reduce security since an attacker may always discretize the samples themselves. Secondly, we can ‘tweak’ the problem so that e,s∈Λq. Fortunately, in the case where γis a unit, Λ∨=iuiO∨ Land so this tweak is precisely multiplying on the right by the tweak factor taking O∨ Lto OL(see, e.g., [38]). Finally, we require hardness of a ‘normal’ form for the CLWE distribution, where sis sampled from the same distribution as the noise e. We require two facts for our proof: firstly, given that qsplits completely in Kthe ring Λqis isomorphic to the direct product of nfull matrix algebras over Md×d(Fq), which can be seen by appealing to the CRT-style decomposition of Lemma 12 and Wedderburn’s Theorem as in [33, Propositions 1 and 4]. Secondly, we require that a non-negligible fraction in nof elements of Λqare invertible, which follows for fixed, small, dand q∈poly(n)from this direct product decomposition. Otherwise, our proof follows the outline for that of plain LWE from [4]. Given these two facts, we proceed with showing that the normal form of the CLWE distribution is as hard as the case of taking the secret uniformly at random. Lemma 17. For a fixed d and q ≥(n+1), a non-negligible proportion of elements of Λqare invertible. Proof. Following the decomposition of Lemma 12 and Wedderburn’s Theorem, it is sufficient to show that a non-negligible proportion of elements of Md×d(Fq)×···×Md×d(Fq) are invertible, where there are ncopies of Md×d(Fq). The proportion of invertible elements of Md×d(Fq)is precisely (qd−1)(qd−q)...(qd−qd−1) qd2 =qd−1 qd...qd−qd−1 qd =1−1 qd...1−1 q ≥1−1 qd ,
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 37 of 67 22 from which it follows that the total fraction of invertible elements in Λqis at least ((1−1 q)d)n. By assumption, q≥n+1, and so (1−1 q)nd ≥((1−1 n+1)n)d≥(e−1)d= e−d, as required. Remark 10. This lower bound of e−dmeans that the normal form reduction will be asymptotic in nbut only valid for fixed d. However, as dincreases the number of invertible matrices in Λqis bounded above by (1−1 q)nd, and so the reduction would be efficient in din the case where one enforced a relation on qand d, such as q≥nd +1, or more succinctly q≥N. Lemma 18. There is a probabilistic polynomial time reduction from the CLWE problem with uniformly random secret s, possibly over a limited secret space G, and error distribution χto the CLWE problem with secret s←χ. Proof. It is sufficient to show that there is an efficient transformation taking samples with secret sto samples with some new secret staken from χ. Sample pairs (a,b)← Πq,s,χ until a pair (a1,b1:= a1·s+e1)such that a1is invertible in Λqis obtained. Since a non-negligible fraction of elements of Λqare invertible by Lemma 17,thisstep takes only polynomial time. Now, given a pair (ai,bi)←Πq,s,χ , we obtain a sample from the CLWE distribution Πq,e1,χ by outputting (ai,bi)=(aia−1 1,aia−1 1b1−bi). Since a−1 1is invertible, aiis uniform. Similarly, aia−1 1b1−bi=(aia−1 1(a1·s+e1)) −ai·s+ei =aia−1 1e1−ei, and so (ai,bi)is a valid CLWE sample with secret e1and error distribution χ. Relabeling e1as scompletes the proof. 5.2. Sample Cryptosystem Our scheme is parameterized by an algebra A:= (L/K,θ,γ), where Ais as in Sect. 3.3, an error distribution Σ, and a prime modulus q≡1modm(recall K=Q(ζm)) which is completely split in L. We will denote with bold faced letters the vector form of an element of Λq, e.g., if a=a0+ua1+... +ud−1ad−1then a=(a0,a1,...,ad−1). We note that OL/qOLhas a polynomial representation of dimension n·d, and so we encode our message ∈{0,1}n·d2as an entry of Λqas a vector mof d{0,1}polynomials. The scheme proceeds as follows: – Alice generates a CLWE sample (a,b:= a·s+e), where a∈Λqis uniformly random and s,e←Σ, and outputs public key a,b. – To encrypt m∈{0,1}n·d2,Bobsamplest,e1,e2←Σand outputs u:= φ(a)Tt+ e1,v:= φ(b)Tt+e2+q 2·m. – To decrypt, Alice computes c=v−φ(s)Tuand recovers each coordinate of mby rounding the corresponding entry of cto 0 or q 2and outputting 0 or 1 respectively.
22 Page 38 of 67 C. Grover et al. Remark 11. There are two benefits of instantiating this scheme in the cyclic algebra setting rather than over modules as in [5], both following from the matrix embedding φ. Firstly, in the module setting Alice must publish a matrix Arather than the vector ain her key, since φ(a)lets us generate a matrix; this saves a factor of din the size of the public key. Secondly, by extending bto φ(b)we are able to increase the dimension of v, and correspondingly increase the size of the message by a factor of d. Example 3. Recall our explicit algebras from Sect. 3.3. Without considering streamlined implementation for specific NIST submissions, we will pick toy comparison parameters for equivalent module-based systems and ring-based schemes, e.g., KYBER and NewHope. For the module case, consider a module of dimension 4 over a ring Lof dimension 256, with 2-power cyclotomic base field [K:Q]=64. Our public key (a,b) requires storing only 8 elements of Rq=OL/q·OLrather than 20 in the form (A,b). Our message consists of 1024 bits, corresponding to the total dimension of the algebra rather than the module versions 256 which corresponds to the field dimension; if the private key size is 256, our CLWE scheme allows a rate-1/4 binary error correction code, while KYBER does not. Our ciphertext sizes are the same. As far as the modulus qis concerned, we find q=3329 splits completely in a quartic cyclic extension Lof K, which matches with the modulus qused in KYBER;7meanwhile, q=3457 splits completely in Kbut ramifies totally in another relative extension of K. Overall this represents a noteworthy gain in key and message size without loss in efficiency. For the ring case, consider an instantiation of NewHope in dimension 1024. Both public keys are in the form (a,s)and so require equivalent levels of storage (8 elements of a field of dimension 256 or 2 in dimension 1024), and the same phenomenon is true of ciphertext sizes and message length. However, a larger modulus q=12289 is used in NewHope. Hence, we hope to gain in security without losing much efficiency. A limitation of our current method is that we cannot achieve rank d=3, similar to the RLWE limitation over power-of-2 rings. Before considering security and correctness we need a somewhat technical lemma allowing the use of the matrix transpose operation. Essentially, it states that if the CLWE problem is hard in an algebra A, then for a,s,e∈Λq, the equation φ(a)Ts+eis a valid CLWE instance in some other algebra Afor which the CLWE problem is still hard. Lemma 19. Let A=(L/K,θ,γ), where γis a unit, be a cyclic division algebra with matrix embedding φ(a)and natural order Λ. Then there exists another cyclic algebra A=(L/K,θ,γ−1)with matrix embedding φ(a)and natural order Λsuch that for a∈Athere exists a∈Λsatisfying φ(a)T=φ(a). Moreover, Astill satisfies the division algebra condition, and Λ qand Λqcanonically isomorphic as additive groups. Proof. The fact that Ais still a division algebra follows from the non-norm property on γand the fact that NL/K(L×)is a multiplicative group. Λ qand Λqare additive isomor7The initial version of KYBER uses q=7681, but it has been reduced to 3329 later which does not split completely in L=Q(ζ512). It is noteworthy that, with a similar technique, further reduction of qin CLWE may also be possible.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 39 of 67 22 phic because both algebras share the same underlying fields and γ,γ−1are both units of OL. Since the first row of φ(a)is precisely (x0,γθ(xd−1), γ θ2(xd−2),...,γθd−1(x1)), by setting a=x0+uγθ(xd−1)+···+ud−1γθd−1(x1)and observing that θdis the identity it is easy to check that φ(a)T=φ(a). The proofs of correctness and security are similar in spirit to those of other compact LWE schemes such as, e.g., NewHope [3] or KYBER [5]. We proceed with a somewhat informal security argument. Lemma 20. The defined scheme is IND-CPA secure under the assumption that the decision CLWEq,Υ problem is hard. Proof. The goal of an IND-CPA adversary is to distinguish, with non-negligible advantage, between encryptions of two plaintexts m1,m2. The challenger chooses i∈{0,1} uniformly at random and encrypts mias u,v. By the assumption that the decision CLWE problem is hard, the adversary cannot distinguish between the case where b=as +e and the case where it is replaced by a uniform random b, so we replace bin the public key given to the adversary by band also use bto compute the challenge ciphertext v. Setting v := v−q 2·mi, it follows by Lemma 19 that u,v represent two samples from a valid CLWE distribution with secret t, and so the adversary cannot distinguish them from uniform with non-negligible advantage. Hence, the challenger cannot distinguish vand hence vfrom uniform with non-negligible advantage and so cannot guess iwith non-negligible advantage. Finally, we demonstrate conditions on the error term for the scheme to be correct. Lemma 21. The defined scheme is correct as long as the ∞norm of e=(φ(e)Tt+ e2−φ(s)Te1)is less than q 4, where the ∞norm is over the vector of all polynomial coefficients of each uientry of eof dimension n ·d2. Proof. To decrypt, Alice computes v−φ(s)Tuand computes mby rounding. Since φ(·)is a homomorphism, we have v−φ(s)Tu=φ(b)Tt+e2+q 2·m−φ(s)T(φ(a)Tt+e1) =φ(e)Tt+e2−φ(s)Te1+q 2·m =e+q 2·m. from which the result follows immediately. We note that the error term ewill be unsurprising to those familiar with LWE-based cryptography. Although we do not provide concrete correctness estimations, the error parameters for our decision reduction are equivalent to those of MLWE up to some small covariance terms. We do not expect this covariance to greatly affect the distribution of the
22 Page 40 of 67 C. Grover et al. error and thus for equivalent parameter choices we expect a similarly small probability of decryption failure. 5.3. Operational Complexity in Cyclic Algebras In the previous subsection we showed that the CLWE problem can be used to construct a standard LWE-based cryptosystem. Assuming that parameters across all variants of the LWE assumption are roughly equivalent, the CLWE problem supports key and message sizes as advantageous as those of the RLWE problem, and better than those of the module case. Along with storage considerations, another important facet of the ambient space in LWE cryptography is the efficiency of operations. Here, we will consider the asymptotic complexity of multiplication in a cyclic algebra in order to compare it to the ring and module variants. Since in practice we consider operations modulo some prime q, addition in rings, modules, and cyclic algebras can be considered as addition in vector spaces over Zq, which has complexity dominated by that of multiplication. Consequently, we only concern ourselves with a comparison of the cost of computing the multiplication operation Asin the three cases. In order to keep our comparison consistent, we let Ndenote the total dimension of the underlying LWE instance. In the ring case, Ndenotes the ring dimension; in the module case, N=nd, where ndenotes the ring dimension and dthe module rank; in the cyclic algebra case N=nd2, where the ring dimension is nd and the algebra has ‘module’ rank d. However, since it will be important later we remark here that the cyclotomic part of the ring will be of dimension nrather than nd. The three cases can be considered as follows: – In the ring case, the operation Asover Zqis a representation of the ring operation a·sin Rq∼ =Zq[X]/(XN+1). Using the CRT decomposition in dimension Nof [28], this operation is decomposed into coordinatewise multiplication in a vector of dimension Nover Zq, following which the decomposition is reversed to recover a·s. The complexity of this technique is dominated by that of the CRT decomposition, which takes time O(Nlog N), although the coordinatewise multiplication also requires time O(N). – In the module case, Ais a d×dmatrix over Rq. In this case, one can compute Asby applying the CRT in dimension ncoordinatewise on Aand s. This requires d2+d applications of the CRT, for a total asymptotic complexity of O(d2nlog n)= O(Ndlog(N/d)). Again, this hides a coordinatewise multiplication step which takes time O(Nd)in this setting. – In the cyclic algebra case, Ais a matrix in the shape φ(a), where φ(a)is the left regular representation of a∈Λq. We estimate the complexity of the operation φ(a)·sin Appendix F. Explicitly, our algorithm has complexity O(Nlog(N/d2))+ ˜ O(Ndω−2)in the case where qsplits completely in L, with ω∈[2,2.373]denoting the exponent of matrix multiplication. The latter term corresponds to the cost of multiplication in our analog of the finite fields used in the CRT method for RLWE. We see that, in the case of completely splitting q, cyclic algebras compare favorably with modules for multiplication in the same dimension Nand when dgrows to infinity, depending on the exact relationship between log d2and dω−2. Recall that for our reduction to hold, we require dto be constant, in which case all three complexities discussed
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 47 of 67 22 drawback since it can be done efficiently on computational software such as SAGE or PARI. Remark 12. In fact, this quartic method can be applied to other instances where we do not have an explicit description of the subfields of K(ζq)whichhavedegreedover K: define the families of qwhich split completely in K, then check whether those qsplit completely in Lusing computational software. Since q=1modmand mis relatively large, there will not be many qto check of appropriate size for lattice cryptography, and so we conclude that this method is sufficient for fixed choices of fields L,Kfor which a satisfactory qexists. Compositum Fields Since a prime qis completely split in a compositum field K1K2 if and only if it is completely split in both K1and K2, it is ready to extend the above method to compositum fields. For the case of Fig. 3a, suppose we have found primes qcompletely split in Kand Lusing the above method. Then we choose qthat is also completely split in F, which ensures it is completely split in compositum field K=KF, hence in L=LF. For the case of Fig. 3b, we choose qthat is also completely split in K, which ensures it is completely split in compositum field L=KL. D. Restricting the Secret Space In Lemma 14 we need to use a fact that is implicit in the search-decision reduction of [27]: for uniformly random v∈Riand an incorrect guess gof the secret smodulo Ri, the distribution of v(g−s)is uniformly random. In the ring and module cases, the secret space is decomposed into a direct product of finite fields, so it is clear that v(g−s)is uniformly random in each finite field for g= s. In our case, an appeal to Wedderburn’s theorem demonstrates that, since for our parameter choices each Riis a central simple algebra over OK∨/qiOK∨∼ =Fq, each Riis isomorphic to the full matrix ring Md×d(Fq), for which it is not true in general that v(g−s)is uniformly random for g= s; in fact, it is uniformly random if and only if g−sis invertible. Thus, we restrict our secret sso that smod Rilies in a set Gi with the property that g= h∈Giimplies g−his an invertible matrix. Applying this restriction for each iplaces s∈Gfor a set G=G1×···×Gnof size |G|=i|Gi|. Now, an incorrect guess g∈Giof smod Riresults in a distribution of v(g−s)which is uniformly random mod Ri. We will call such a set Ga pairwise difference set. We also need to guarantee that there exist sufficiently large choices of G.Asimple method for constructing a valid Giis by fixing some arbitrary embedding βof Fqdinto Mn×n(Fq)and letting Giequal the image of this embedding, such that |Gi|=qdand |G|=qnd. Indeed, a Giconstructed in this way is maximal because any set of matrices in Md×d(Fq)of size at least qd+1 contains two matrices with the same first row, whose difference is therefore uninvertible. There are a number of choices of embedding β, and thus set Gi, equal to the number of irreducible polynomials of degree din Fq[x], which can be calculated by the Necklace polynomial and in general will vastly exceed q. We make clear that our
22 Page 48 of 67 C. Grover et al. reduction will take the decision CLWE problem for arbitrary secret s to the search CLWE problem where s∈Gfor arbitrary fixed G, which we denote by CLWEq,Σα,G. Thus, our reduction states that the decision problem is as hard as the search problem for the hardest choice of G, precluding obvious attacks on the unique case where G=OLq∨ and the CLWE problem with s∈Gcorresponds to dparallel copies in Lof the RLWE problem.8For a general set G,s∈Gwill not provide parallelization since they need not have the property of Lthat they are entirely contained in one ucoordinate of A. Additionally, even though elements of Gconstructed this way co-commute, they do not lie in the center of Λand the multiplication a·sin the CLWE instance will not be a commutative operation. Of course, fixing a Gof size qnd restricts the size of the secret space by a factor of qnd qnd2, a substantial loss in size even for fixed, small d. For concrete parameter settings, this may result in a much easier problem, but asymptotically it is still exponential in n and thus establishes a suitable hardness property for decision CLWE. Of course, attacks based on exhaustive search are unlikely to represent the best attacks on the CLWE problem, so this may or may not substantially aid an attacker in practice. In fact, there is no a priori reason why Gishould be a field, or even closed under multiplication. For example, fixing a pair of invertible matrices M1,M2and replacing Giwith M1·Gi·M2={M1XM 2|X∈Gi}results in a new set of size qdwhose pairwise differences are all invertible but is not multiplicatively closed in general. Although the field embedding technique is perhaps the most elegant way of building Gi, and certainly the most constructive, it may transpire that taking sfrom some set with less algebraic structure is advantageous in terms of the hardness of the resulting search problem. One can also construct the valid set Gi+Xby adding a fixed matrix Xto each element of Gi, but this technique is somewhat constrained by the fact that LWE samples are additive in the secret s(e.g., one could just add a·Xinto the second coordinate of the resulting samples). Although this restriction is not ideal, we have a remark about the implications on the security of the CLWE problem. Restricting the secret space in (R)LWE problems is not an uncommon idea: tertiary secrets, where each coordinate of s∈{−1,0,1},are used in the NIST candidate LAC [24] amongst others, and security whilst restricting the secret to orders or subfields is discussed in [11], and to other K-lattices in [39]. Overall, we suspect that the decision CLWE problem is polynomial time equivalent to the search CLWE problem without restriction on s, in particular when the number of samples is small as in our applications in Sect. 5, and that the restriction is a function of our reduction technique rather than some causal property of the CLWE distribution. For the purposes of constructing a cryptosystem, we assume that this reduction implies that the decision CLWE problem is hard. 8Although this case exists only when each qiOLis a prime ideal in OL.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 49 of 67 22 E. The Case where qTotally Ramifies in Relative Extension L/K Here, we apply a decomposition in terms of Λideals: Λq=Λ/qΛ=Λ/Pe1 1...Peg g,(4) where the Piare maximal two-sided ideals in Λand the eiare some positive integers. Moreover, the following holds (see [30]): Λ/Pi∼ =Mfi(Fqei), where fiei=d. When ei=d,wehaveΛ/Pi∼ =M1(Fqd)=Fqd, a finite field. We reduce CLWE to CLWE modulo Pd iusing a similar proof as above, and from there reduce to CLWE modulo Pi. The secret then lies in some finite field, so the difference of any two elements will invert and the size of the secret space will be unrestricted. However, in order to achieve this we will have to consider the reduction for ideal lattice problems where the ideal is coprime to the ideal generated by the modulus q. This is still an infinite set of ideal lattices. Before proceeding with the reduction, we first remove the restriction on the ramification of the modulus present in the statements of the technical lemmas. In [34], Propositions 1 and 4 state that for pi⊂OKunramified, and inert or split in OL,piΛ=d−1 j=0ujpiOL, and the piΛare the largest two-sided ideals containing qΛ. In our case, we are dealing with piramified and not split in OL. Let p∈Zbe a prime such that pOK=p1...p[K:Q]. Moreover, let piOL= (P1...Pg)e, where eg =[L:K]and e>1; importantly, this means that fPi= [OL/Pi:OK/pi]=1. Set I=P1...Pg⊕uP1...Pg⊕... ⊕ud−1P1...Pgin Λ= OL⊕uOL⊕... ⊕ud−1OL. It can be verified that Iis a two-sided ideal. Background on the following definitions can be found in [43]. Definition 28. The order ideal ordOK(X)of a finitely generated OK-module Xis defined as follows: 1. If X=0,ordOK(X)=OK; 2. If Xis not an OK-torsion module, ordOK(X)=0; 3. If Xis a nonzero OK-torsion module, then Xhas an OK-composition series, whose composition factors are {OK/pi},with piranging over some set of maximal ideals of OK.Set ordOK(X)=ipi,where the number of factors equals the number of composition factors of X. Definition 29. Let Mbe an integral ideal of Λ. Define its norm by NA/K(M)=ordOKΛ/M Lemma 23. (24.6 of [43]) Let Jbe a prime ideal of Λ, and let J∩OK=p. Set f=[Λ/J:OK/p]. Then NA/K(J)=pf.
22 Page 50 of 67 C. Grover et al. Lemma 24. (Theorem 24.13 of [43]) For any maximal integral ideal M, Nrd(M)=p for M lying above p,ifOK/pis a finite field. To prove the desired result we use a norm argument, considering the norm of I,NA/K(I), defined in Definition 29 to be ordOK(Λ/I). What is ordOK(Λ/I)? Since Λ/Iis nonzero, ordOK(Λ/I)= OK. Furthermore, Λ/Ihas OK-torsion: observe that (OK∩ I)(x+I)⊂I(x+I)∈I, for all x∈Λ,so(OK∩I)(Λ/I)=0 and Λ/Iis an OK-torsion module. Thus, ordOK(Λ/I)= 0. This leaves 3. Composition series can be hard to figure out explicitly, but in fact our calculation of ordOK(Λ/I)will reduce to figuring out ordOK(OL/J), for some ideal Jof OL. This has an easy description when Jis a product of prime ideals: ordOK(OL/P)=pfL/K, where P∩OK=pand fL/K=[OL/P:OK/p], the inertial degree. So ordOK(OL/P)=NL/K(P)(see [43], 4.33). Proposition 2. Let pOL=(P1...Pg)e, where eg =[L:K]and e >1. Set I= P1...Pg⊕uP1...Pg⊕... ⊕ud−1P1...Pg. Then Iis a maximal ideal in Λ. Proof. We consider two related norms, the norm from Ato K, denoted NA/K, and the reduced norm, denoted Nrd. They are related as follows: NA/K=Nd rd, where [L:K]=d. In our case the inertial degree fL/K=1, so OL/Pj∼ =OK/p∼ =Fp, and [OL/Pj:OK/p]=1. Moreover, we have Λ/I=(OL⊕uOL⊕... ⊕ud−1OL)/(P1...Pg⊕uP1...Pg⊕... ⊕ud−1P1...Pg) ∼ =OL/P1...Pg⊕uOL/uP1...Pg⊕... ⊕ud−1OL/ud−1P1...Pg ∼ =(OL/P1...Pg)d∼ =(OK/p)g·d, so f=gd. Thus, if Iis prime, by Lemma 23 above, NA/K(I)=pgd.Wehave: NA/K(I)=ordOK(Λ/I)=ordOK((OL/P1...Pg)d)=ordOK(OL/Pd 1...Pd g) =NL/K(Pd 1...Pd g)=NL/K(Pd 1)...NL/K(Pd g)=NL/K(P1)d...NL/K(Pg)d =ordOK(OL/P1)d...ordOK(OL/Pg)d=pd...pd=pgd, as required. So Ihas the same norm as a prime ideal. We finally show that if Iwere not a maximal two-sided ideal (so prime), then we obtain a contradiction. Suppose we have IJΛ, where Jis a maximal twosided ideal of Λ. Then |Λ/J|<|Λ/I|, and so [Λ/J:OK/p]<[Λ/I:OK/p],or equivalently fJ<fIfor fas defined previously. Then NA/K(I)=pfIpfJ= NA/K(J); using the relation between the norms gives Nrd(I)Nrd(J), which are both ideals of OK-butNrd(I)is maximal in OK,soNrd(J)cannot be a proper ideal containing it. This is a contradiction, and the result follows. Corollary 2. Let pi⊂OKbe a prime ideal above prime q ∈Z, such that piOL=Pe i, for some positive integer e ≤[L:K]=d. Then I=Pi+uPi+... +ud−1Piis the maximal ideal of Λlying above pi.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 51 of 67 22 Proof. We have three statements to prove: that Iis a two-sided ideal, that it is maximal, and that it lies above pi. The latter statement is clear: I∩OK=Pi∩OK=pi. Moreover, maximality follows from Proposition 2. To see that it is an ideal, first note that it is additively closed. In addition, for any element of Gal(L/K),sayθ,wehaveθ(Pi)=Pi, because the automorphism permutes the primes above pi, and there is only one that can be permuted. We now drop the subscript and write P.Leta∈Iand b∈Λ. Then 1. a·b=(a1+ua2+... +ud−1ad−1)·(b1+ub2+... +ud−1bd−1) =d−1 j=0ujγαijk d−1 i+k≡jmod dθk(ai)bk⊂d−1 j=0ujγαijk d−1 i+k≡jmod dθk(P)bk ⊂d−1 j=0ujγαijk d−1 i+k≡jmod dP⊂P⊕uP⊕... ⊕ud−1P=I, 2. and b·a=(b1+ub2+... +ud−1bd−1)·(a1+ua2+... +ud−1ad−1) =d−1 j=0ujγαijk d−1 i+k≡jmod dθk(bi)ak⊂d−1 j=0ujγαijk d−1 i+k≡jmod dθk(bi)P ⊂d−1 j=0ujγαijk d−1 i+k≡jmod dP⊂P⊕uP⊕... ⊕ud−1P=I, where αijk =1,i+k= j 0,i+k=j.Thus, Iis closed by multiplication on both sides. We can use our result on maximal ideals to say the following: Lemma 25. Assume q ∈Zis prime such that q is completely split in OK,f q L/Q=1, and eq L/K>1. Let I⊂Λbe an ideal not contained in the same maximal ideal as qΛ, and let J=q·Λ=q·Λ, where q is a prime integer and q=r i=1qiis a decomposition into prime ideals in OK. Assume γ/∈qifor each i.Then, there exists an element t ∈I∩OKsuch that t ·I−1⊂Λis coprime to J,and we can compute such a t efficiently given Iand the prime factorization of J. Proof. For an ideal Idenote by Iits intersection with K,which is a non-trivial ideal of OK. As usual, we obtain t∈Isuch that t·I−1and Jare coprime as ideals of OKand t∈I\r i=1qi·I.Assume, for a contradiction, that t·I−1+J= Λ, i.e., the ideals are not coprime. Then, there is some maximal ideal Mof Λcontaining t·I−1and J. Write qiOL=(P1...Pg)e.Since qis has inertial degree equal to 1 in OLand γ/∈qi,by the theorem in the previous section, this ideal must be one of the form P1...Pg⊕uP1...Pg⊕ud−1P1...Pgsince it contains J. Then t·I−1⊂ P1...Pg⊕uP1...Pg⊕ud−1P1...Pgand consequentially t∈(P1...Pg⊕uP1...Pg⊕ ud−1P1...Pg)·Ibecause I·I−1=Λin a maximal order. Since tis central it follows that t∈((P1...Pg⊕uP1...Pg⊕ud−1P1...Pg)·I)∩OK. Thus, we have t∈qi and t∈I, i.e., t∈qi∩I. Since Iis not contained in any of the maximal ideals above q,Ilies above an integer mwhere gcd(q,m)=1. Bezout’s theorem tells us that there exist a,b∈Zsuch that aq +bm =1. Thus, qiand Iare coprime, and t∈qi∩I=qiI—which is a contradiction.
22 Page 52 of 67 C. Grover et al. Note here we have had to impose an extra condition—that Idoes not share a maximal ideal with q. This means that the relevant intersections with OKare coprime ideals, and the proof goes through. This is not a particularly strong restriction, as there are many such ideals I. Lemma 26. Let Λ,γ, and q be given in Lemma 3.Let I,Jbe ideals of Λas above, with t ∈I∩OKchosen as above such that t ·I−1and Jare coprime as ideals, and let Pdenote an arbitrary fractional ideal of Λ. Then, the function χt:A→Adefined as χt(x)=t·x induces a module isomorphism from P/J·P→I·P/I·J·P. Furthermore, in the case J=qfor a prime integer q we can efficiently compute the inverse. Proof. The proof only relies on the ramification of qinsofar as the above lemma does, so the proof holds under the conditions of the previous lemma. The above results mean that, subject to the weak condition in Lemma 25, the reduction to search CLWE in the main body of the paper holds for primes qsuch that qis split completely in OK, and has fq L/Q=1, using an ideal I∈Λthat doesn’t share a maximal ideal with the prime q. This removes the restrictions on q, and we have traded qunramified in OLwith arbitrary ideal I,forqhaving fq L/Q=1 with Icontaining any integer which is coprime to q. There has been a tradeoff between the number of valid primes and the number of valid ideals. The following is the first step in the reduction using ramified primes. Reducing CLWE to CLWE modulo Pd iAs above, we use the extended embeddings of Kto A. Since any embedding of Kcan be extended to an embedding of L,weuse those extended embeddings to send A=(L/K,θ,γ)to A=(L/K,θ,γ), where γ is the image of γunder a chosen embedding. These maps preserve the decomposition of Λ∨ qby sending Pito some Pj—we below show that these embeddings permute the primes Pimodulo qΛ. We will abuse notation and denote the action of αon the cosets Λ/qΛalso by α. Lemma 27. Let αbe an isomorphism from A→Aas above. Fix a prime q ∈Zsuch that qOK=p1...pg. Let Pibe a prime ideal of Λlying above the prime ideal pi⊂OK. Then, considering αas acting on the cosets of Λ/qΛ,α(Pi+qΛ) =Pj+qΛ,for some i = j. Proof. First observe that αpermutes the primes of OK, since it was induced by an element of Gal(K/Q). Thus, α(pi)=pj, and so α(pi+qΛ) =pj+qΛ, where we have used that αfixes Λq. Moreover, since pi⊂Pi,wehavepj+qΛ=α(pi+ qΛ) ⊂α(Pi+qΛ) =α(Pi)+qΛ. Since αfixes Λ/qΛ, we in fact have that α(Pi)+ qΛ⊂Λ/qΛ. Note that α(Pi)is a prime (and hence maximal) α(Λ) ideal. Thus, α(Pi)+α(qΛ) =α(Pi)+qΛis a prime ideal of α(Λ)/α(qΛ) =α(Λ/qΛ) =Λ/qΛ. So we find that α(Pi+qΛ) corresponds to a maximal ideal of Λ/qΛlying above pj; thus, α(Pi+qΛ) =Pj+qΛ.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 53 of 67 22 Lemma 28. (Reduction from CLWE to Pd i-CLWE) There is a deterministic polynomial time reduction from CLWEq,Σαto Pd i-CLWEq,Σα. Proof. Let Oidenote an oracle for the Pd i-CLWEq,Σ problem. Equation (4) defines an isomorphism, so we can use the oracle Oito solve the Pd j-CLWEq,Σ problem for each j.Let αj/ibe an extension of the automorphism of Kthat maps qjto qi. Given sample (a,b)←Πq,s,Σα, construct a sample of the form αj/i(a), αj/i(b). Since Λqand Λ∨ qare fixed by each αj/i, the sample is a valid CLWE sample in A= (L/K,θ,αj/i(γ ). Feeding this sample into Oioutputs a value tjmod Pd i. We show that α−1 j/itj=smod Pd j.Since αj/iis an automorphism, each (a,b)is mapped to CLWE sample αj/i(a), αj/i(a·s/q+e)mod Λ∨in the algebra A,and we can write αj/i(a)·αj/i(s)/q+αj/i(e)mod Λ∨. As stated above, our automorphisms fix our family of error distributions, and map the uniform distribution to the uniform distribution, so this is a valid CLWE instance with secret αj/i(s)∈αj/i(Λ∨ q)=Λ∨ qand error distribution Σ∈Σα.SoOioutputs t=αj/i(s)mod Pd i,which yields α−1 j/i(t)= smod Pd j,since the embeddings permute the Pi, and thus the Pd i, as required. CLWE Modulo PiWe now show that it suffices to solve the problem modulo Pi, rather than modulo Pd i. Since sis not zero in Λ/qΛ,sis not in Pd 1...Pd g, so there exists a k:s∈ Pd k. We will first show that the corresponding problem for RLWE can be solved; we will then show that the problem for CLWE can be solved using the method for RLWE. First, we need some lemmas and definitions. RLWE Let R=Z[x]/Φn(x), where Φn(x)is the nth cyclotomic polynomial. Then Ris the ring of integers of the nth cyclotomic field, denoted K.LetRp=R/pR, and R∨={x∈K:Tr(xR)⊂Z}be the dual lattice. An RLWE sample has the form (a,b)=(a,(a·s)/p+emod R∨)∈Rp×T, where a←Rpuniformly at random, s←R∨ p, and esampled according to some error distribution; finally, Tis the unit torus. Let pOK=r i=0pe i,fore>1. Let pi,j-RLWE be the problem of finding smod pj i,givenRLWEsample(a,b). We show that we can solve this problem, given access to a pi,1-RLWE oracle. Note that knowing smod pe iis sufficient to find s,by using automorphisms and the CRT. Lemma 29. Given RLWE sample (a,b)and an oracle for pi,1-RLWE oracle, we can solve pi,e-RLWE. Proof. Let (a,b)be an RLWE sample, and submit (a,b)to the oracle to obtain an element xsuch that x≡smod pi. Then x−s∈pi. We can write x−s=α·p+β·fi(ζn), where α, β ∈OK, since OK=Z[ζn]for cyclotomic fields, and p=(p,fi(ζn)), where Φn(x)=i=0fj(x)mod p, and the fjare irreducible modulo p.Sox−s−βfi(ζn)= α·p⊂pOK, and s≡x−βfi(ζn)mod pOK. We proceed to construct an element congruent to smodulo peOK, since peOK⊂pe iOK. Replace sby (x−s−βfi(ζn))/p. Then (a,b)=(a,(a·(1 p(x−s−βfi(ζn)))/p+ emod R∨)is a valid RLWE sample. Submit it to the oracle to obtain ysuch that
22 Page 54 of 67 C. Grover et al. y≡x−s−βfi(ζn) pmod pi. As before, write this in terms of the generators of p, and subtract the fi(ζn)term to obtain an element in pOK, resulting in y−d·fi(ζn)−x−s−βfi(ζn) p=p·e for some dand e∈Ok. Replace x−s−βfi(ζn) pby y−d·fi(ζn) p−x−s−βfi(ζn) p2. Continue in this manner until we have v−w·fi(ζn) p−... −y−d·fi(ζn) pe−1−x−s−βfi(ζn) pe=z∈OK. Rearrange for s=pez−pe−1(v −w·fi(ζn)) +... +p(y−d·fi(ζn)) +x−βfi(ζn). Clearly s≡pez−pe−1(v −w·fi(ζn)) +... +p(y−d·fi(ζn)) +x−βfi(ζn)≡xmod pi. Moreover by construction we have found an element in the same coset modulo peas s, namely pe−1(v −w·fi(ζn)) −... −p(y−d·fi(ζn)) −x+βfi(ζn). Reducing modulo pe i, we obtain an element of OKcongruent to s, which is a solution to pi,e-RLWE. Solving Pi,d-CLWE Lemma 30. Let q ∈Zbe prime such qOK=pi,piOL=Pd iand qΛ=Pd 1...Pd g. Given C LW E sample (a,b)and an oracle for the CLWE mod Piproblem, we can solve the CLWE modPd i-problem. Proof. Submit (a,b)to the oracle for x∈Λ∨ q:x≡smod Pi. By Proposition 2, I=Pi+uPi+... +ud−1Piis the maximal ideal of Λlying above pi.Sowecantake Pi=Pi+uPi+... +ud−1Pi. Then x−s∈Pi,and hence xi−si∈Pifor each i, where xiand siare the ith coefficient of xand srespectively. The prime ideals of the ring of integers of an algebraic number field lying above the prime qhave the form Pi=(q,fi(α)), for some polynomial fiand α∈OL. Thus, proceeding as in the RLWE case, we can express xi−siin terms of qand fi(α), subtract the fi(α) term, and have an element divisible by q. We replace the siwith the resulting element, xi−si−bi·fj(α) q, for each i, to obtain a new valid CLWE sample with new secret x, and then query the oracle for a value congruent to xmodulo Pi. We can iterate the procedure as before, until we have an element yisuch that yi≡simod Pd i. We can then obtain an element ysuch that yi−siis divisible by qdfor each i, and hence y−sis divisible by qd,soy−s∈Pd i. This lemma means that if we can solve search CLWE modulo Pi, we can construct a solution to search CLWE modulo Pd i; we can then use the argument of the preceding section (using the embeddings and the CRT) to find the secret sand solve CLWE. In the following section, in a series of steps mirroring the standard methods, adapted largely from [26], we establish the hardness of the decision problem. Hybrid CLWE and Search to Decision Definition 30. For s∈Λ∨ q,distribution Σover ⊕jujLR,and i∈[n],define a sample from distribution Πi q,s,Σ over Λq×⊕d−1 j=0ujLR/Λ∨by taking (a,b)←Πq,s,Σ and h∈Λ∨ qwhich is uniformly random and independent mod Pj,for j≤iand 0 mod Pj, for j>i,and outputting (a,b+h/q). If i=0,define Π0 q,s,Σ =Πq,s,Σ . Then for
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 55 of 67 22 i∈[n]and a family of distributions Σα,the WD-CLWEi q,Σαproblem is to find jgiven access to Πj q,s,Σ for j∈{i−1,i}and CLWE secret and error distribution s,Σ. Lemma 31. For any i ∈[n]there is a probabilistic polynomial-time reduction from Pi-CLWEq,s,Σα,Gto WD-CLWEi q,s,Σα. Proof. We proceed as usual. There are |Λ/Pi|possible values of smod Pi,which is bounded above by |Λ/Pi|=qd,so we may efficiently enumerate over the possible values. We want a transform which takes g∈Λ/Piand maps Πq,s,Σ to Πi−1 q,s,Σ if g=smod Pior to Πi q,s,Σ otherwise. Take CLWE sample (a,b)←Πq,s,Σ ,and output a,b=(a+v,b+(h+vg)/q)∈Λq×d−1 i=0 uiLR/Λ∨, with v∈Λquniformly random mod Piand 0 mod Pjfor j= i, and h∈Λ∨ quniformly random and independent mod Pjfor j<iand 0 on the other Pj.Then ais uniformly distributed on Λq,so it remains to prove bis distributed correctly. Fix a,then b=b+(h+vg)/q =(as +h+vg)/q+e =as+h+v(g−s)/q+e where eis drawn from Σ.Ifg=smod Pi,then v(g−s)=0modPiso the distribution of a,bis Πi−1 q,s,Σ .Otherwise, v(g−s)is uniformly random mod Pi(since Λ/Piis a field) and 0 modulo the other Pj.Setting h=h+v(g−s), one can see that the distribution of a,bis Πi q,s,Σ , as required. Worst-Case to Average-Case Decision Reduction This stage of the reduction holds identically to that of the main body of the paper, replacing Riwith Pi. F. Estimating the Multiplication Complexity The overall flow to compute the multiplication is depicted in Fig. 5, which is explained in detail in the sequel. F.1. Algorithm for Multiplication in Cyclic Algebras We recall some details necessary to understand our multiplication algorithm. Recall that in the explicit constructions of Theorem 2the base field Kis cyclotomic and qis a prime integer chosen so that qsplits completely in OKas q=q1...qn, where nis the dimension of Kas an extension of Q. Furthermore, the degree of Lover Kis a typically
22 Page 56 of 67 C. Grover et al. Fig. 5. Depiction of the multiplication algorithm for cyclic algebras. [CLB17] is referred to as [15]. small d. Then, following the CRT-like decomposition of Lemma 12 we write Λq∼ =R1×···×Rn for Ri=d−1 j=0ujOL/qiOL. We will show that each Riis a skew polynomial ring over Zq, and in particular a skew polynomial ring for which we can apply the algorithms of [15] to compute multiplication independently in each Riin ˜ O(dω)operations in Zq, which output elements whose ucoordinates are in the form iikifor ki∈OKqand {i}some arbitrary normal basis for OLqover OKq. We remark that the representation as a skew polynomial ring need not contradict the fact that we viewed the rings Rias matrix rings in Sect. 4.2, since computing matrix multiplication can be reduced to the problem of computing multiplication of skew polynomials (see [15]). Since ω≤2.373, this leads to a complexity of approximately ˜ O(Nd0.373)and it is possible to compute the multiplication in each Riin parallel. However, we must also compute the complexity of the splitting isomorphism. F.2. The Rings Ri In order to apply the algorithm of [15], we must confirm that each Risatisfies the following conditions: –Riis the quotient of a skew polynomial ring with center OK/qiby a polynomial in the form Xd−γ. –γis a norm from OL/qiOLinto OK/qi.9 –OL/qiOLis a field extension of OK/qior an étale-OK/qialgebra. The first of the conditions follows immediately from the definitions of a skew polynomial ring and a cyclic algebra. The veracity of the latter conditions will depend on how the prime ideal qiof OKsplits in OLas qiOL. Since qiis prime in Kand L/Kis Galois, 9Due to the modulo reduction this does not contradict the assumption that γis not a global norm.
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 63 of 67 22 case we constructed each iin this manner. Armed with this knowledge, we adapt the multiplication algorithm as follows. Choose an arbitrary integral OK-basis 1,..., dof OL. As a precomputation phase, compute and store the images jmod qiOLfor each iand j. The CRT-like decomposition of Lemma 12 splits each of the ucoordinates of an element of Λq,an element of OLq, into its mod qiOLparts. Once again, we suggest an algorithm where elements of OLqare stored in the form =d j=1jkjfor kj∈OKq, e.g., on elements stored as K-combinations of this basis. We split ∈OLqinto its OL/qicomponents in time O(d·nlog n), since d j=1 jkjmod qiOL= d j=1 (jmod qiOL)·(kjmod qiOL), where each kjmod qican be computed in time O(nlog n)by the K-CRT and each j mod qimod OLwas computed in the precomputation phase. Consequentially, we can perform the CRT style decomposition of an element in Λqwhose ucoordinates are all stored in this manner in time O(d2·nlog n), since we must split d2elements of OK.This decomposing complexity is the same as in the previous case where qsplits completely. Following this, each ring Rican be plugged in to the algorithm of [15] to compute the multiplication in time ˜ O(Ndω−2). However, since the ido not correspond to a standard orthonormal basis we incur an extra cost when reversing this transformation. Namely, each of the ucoordinates of each ring Riis output by the algorithm of [15]as an element ∈OLmod qiOLexpressed in an arbitrary normal basis. Before reversing the decomposition we must allow for the complexity of expressing each element of the output in the bases obtained by the images of 1,..., dmod qiOL, as this basis was not necessarily normal. Since OLmod qiOLis a vector space of dimension dover Fqthis can be done via a precomputed change of basis matrix over Fqin time ˜ O(dω), and since there are nrings with dcoordinates each the complexity of computing this on every coordinate is ˜ O(ndω+1). The resulting multiplication algorithm has total complexity O(Nlog(N/d2)) +˜ O(Ndω−1). While this represents only a minor asymptotic loss, especially since we expect the first term to dominate the complexity, it is likely in practice that the extra step required to recover the basis representation would cause a tangible slowdown. An unfortunate issue with this technique is that by replacing the orthonormal basis with an arbitrary basis we have lost Theorem 11 and thus the efficient method for sampling a discrete Gaussian in the representation =jjkj. However, this generalization allows for the use of an arbitrary basis 1,..., d, unlike in the split case in which we chose a specific basis. Since we require that elements of Λqare input into the algorithm with ucoordinates in the form jjkjthis algorithm can be combined with the cryptosystem of Sect. 5.2 in the case where there is a basis g1,...,gdof OLqover OKqin which one can compute the representation =jgjkjparticularly efficiently. This is because one can just sample from the usual Gaussian distribution over the polynomial basis of OLq, compute its representation as =jgjkj, and then apply the multiplication algorithm in this form. More generally, the flexible choice of basis allows for both non-split qand for a user to choose their favorite OLbasis properties,
22 Page 64 of 67 C. Grover et al. such as a normal basis or a basis consisting of small elements. We remark that it is likely possible to construct a pair of fields L/Kthat allow for a basis 1,..., dpermitting a fast algorithm transforming from the polynomial representation of OLto the representation iikiwith each kiin polynomial representation, which would allow one to bypass the complications of sampling Gaussian distributions by just sampling in OL directly. F.6. Generalizing to Other Centers In the exposition of the previous section we required that qsplits completely in the center K. This corresponds to the requirement in the ring and module cases that qsplits completely in the field K, which allows the use of the NTT to compute multiplications over a direct product of finite fields. However, there has been recent progress in loosening this requirement for the NTT and allowing the modulus qtobe1modnrather than 1 mod m, where as usual Kis the mth cyclotomic field of degree n. For example, in the second round specification of KYBER [5]qis set as 3329 and n=256, yet they still support efficient NTT-based multiplication. In such cases, qis ‘well’ split but not completely split, and the fast NTT operations use the method of [29], where qsplits into some product of prime ideals qiwhose norms can be small powers of q. We observe that our methods can be partially generalized to this case in the following manner. Say q=iqiis a decomposition into prime ideals in OKand there exists an efficient algorithm for fast multiplication in OKq. We can replace our condition that q splits completely in OLwith the condition that each ideal qiin the OK-factorization of q splits completely into a product of dprime ideals qiOL=d j=1qi,jin OLof the same norm. Then, we can replicate the method of Appendix F.4 to find a cyclic, orthonormal basis e1,...,edof OL/qiOLover OK/qiand concatenate together the bases for each i to make the cyclic, orthonormal, basis 1,..., dof OLqover OKq. Since the basis is orthonormal, if =iikiand g=iigiwith each ki,gi∈OKq, then ·g= d i=1 i(gi·ki). Since the basis is cyclic, θ() = i θ(i)ki = i iki−1 where we define k0:= kd. Now we are able to use existing fast multiplication algorithms in OKqto compute operations in OLqby expressing elements in this basis. Represent each x=d−1 i=0uixi∈ Λqby expressing each xi∈OLqin the jbasis. Then, to multiply xand yin Λqone only has to compute multiplications in OKq, since the operations required are just computing the non-commutative relation u=uθ(), which merely permutes the iusing θ,
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 65 of 67 22 and computing multiplication and addition, which can be done coordinatewise in the orthonormal ibasis. Each Lmultiplication requires dmultiplications in K, and each u coordinate of Λrequires dmultiplications in L. Consequentially, naive multiplication in Λqtakes d3instances of the efficient OKq-multiplication algorithm we have access to. For specific K-multiplication algorithms it is likely that this process can be streamlined; the intention of this section is merely to demonstrate that one can build efficient Λq operations from more general efficient operations over the center in the same manner that the techniques of Appendix F.4 used the CRT method. References [1] G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson, D. Smith-Tone, Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. rep., NIST (2020), https://nvlpubs.nist.gov/ nistpubs/ir/2020/NIST.IR.8309.pdf [2] M.R. Albrecht, A. Deo, Large modulus Ring-LWE ≥Module-LWE, in Takagi, T., Peyrin, T. (eds.) Advances in Cryptology – ASIACRYPT 2017. pp. 267–296. Springer, Cham (2017) [3] E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, Post-quantum key exchange: a new hope, in 25th USENIX Security Symposium (USENIX Security 16). pp. 327–343 (2016) [4] B. Applebaum, D. Cash, C. Peikert, A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems, in Advances in Cryptology-CRYPTO 2009, pp. 595–618. Springer (2009) [5] R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J.M. Schanck, P. Schwabe, G. Seiler, D. Stehlé, CRYSTALS-Kyber algorithm specifications and supporting documentation (version 2.0). https://pq-crystals.org/kyber/data/kyber-specification-round2.pdf (2019) [6] W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers. Math. Annalen 296(1), 625–635 (1993) [7] A. Banerjee, C. Peikert, New and improved key-homomorphic pseudorandom functions. in Garay, J.A., Gennaro,R.(eds.)Advances in Cryptology – CRYPTO 2014. pp. 353–370. Springer, Berlin, Heidelberg (2014) [8] G. Baumslag, N. Fazio, A.R. Nicolosi, V. Shpilrain, W.E. Skeith III, Generalized learning problems and applications to non-commutative cryptography, in Provable Security, pp. 324–339. Springer (2011) [9] G. Berhuy, F. Oggier, An Introduction to Central Simple Algebras and Their Applications to Wireless Communication. American Mathematical Society (2013) [10] J.F. Biasse, F. Song, On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q (ζn p). Tech. rep. (2015) [11] M. Bolboceanu, Z. Brakerski, R. Perlman, D. Sharma, Order–LWE and the hardness of Ring–LWE with entropic secrets. Cryptology ePrint Archive, Report 2018/494 (2018), https://eprint.iacr.org/2018/494 [12] C. Bootland, W. Castryck, F. Vercauteren, On the Security of the Multivariate Ring Learning with Errors Problem (2018), published: Cryptology ePrint Archive, Report 2018/966 [13] J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, D. Stebila, Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE (2016), published: Cryptology ePrint Archive, Report 2016/659 [14] P. Campbell, M. Groves, D. Shepherd, Soliloquy: A cautionary tale (2015) [15] X. Caruso, J. Le Borgne, Fast multiplication for skew polynomials, in Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pp. 77–84. ACM (2017) [16] Q. Cheng, J. Zhuang, LWE from Non-commutative Group Rings. arXiv preprint arXiv:1612.06670 (2016) [17] R. Cramer, L. Ducas, C. Peikert, O. Regev, Recovering short generators of principal ideals in cyclotomic rings, in Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 559–585. Springer (2016)
22 Page 66 of 67 C. Grover et al. [18] R. Cramer, L. Ducas, B. Wesolowski, Short Stickelberger class relations and application to Ideal-SVP. in Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 324–348. Springer (2017) [19] E. Crockett, C. Peikert, Challenges for Ring-LWE. IACR Cryptology ePrint Archive (2016) [20] R. Jozsa, Quantum factoring, discrete logarithms, and the hidden subgroup problem. Comput. Sci. Eng. 3(2), 34–43 (2001) [21] J. Lahtonen, N. Markin, G. McGuire, Construction of multiblock space–time codes from division algebras with roots of unity as nonnorm elements. IEEE Trans. Inf. Theory 54(11), 5231–5235 (2008) [22] A. Langlois, D. Stehlé, Worst-case to average-case reductions for module lattices. Designs Codes Cryptogr. 75(3), 565–599 (2015) [23] H. Lu, Constructions of multiblock space–time coding schemes that achieve the diversity-multiplexing tradeoff. IEEE Trans. Inf. Theory 54(8), 3790–3796 (2008) [24] X. Lu, X. Liu, Z. Zhang, D. Jia, H. Xue, J. He, B. Li, K. Wang, Z. Liu, H. Yang, LAC: Practical Ring– LWE based public-key encryption with byte-level modulus (2018), https://eprint.iacr.org/2018/1009. pdf [25] L. Luzzi, R. Vehkalahti, C. Ling, Almost universal codes for MIMO wiretap channels. IEEE Trans. Inf. Theory 64(11), 7218–7241 (2018) [26] V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in Gilbert, H. (Ed.) Advances in Cryptology – EUROCRYPT 2010, (Springer, Berlin, Heidelberg, 2010), pp. 1–23. [27] V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings. in Annual International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2010), pp. 1–23. [28] V. Lyubashevsky, C. Peikert, O. Regev, A toolkit for Ring-LWE cryptography. in Annual International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2013), pp. 35–54. [29] V. Lyubashevsky, G. Seiler, NTTRU: truly fast NTRU using NTT. IACR Trans. Cryptogr. Hardware Embed. Syst. 2019(3), 180–201 (2019) [30] C. Maire, F. Oggier, Maximal order codes over number fields. J. Pure Appl. Algebra 222(7), 1827 – 1858 (2018) [31] D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007) [32] F. Oggier, J.C. Belfiore, E. Viterbo, Cyclic Division Algebras: A Tool for Space-time Coding,(Now Publishers Inc, 2007) [33] F. Oggier, B.A. Sethuraman, Quotients of orders in cyclic algebras and space-time codes. Adv. Math. Commun.,7(2012) [34] F. Oggier, B. Sethuraman, Quotients of orders in cyclic algebras and space-time codes. arXiv preprint arXiv:1210.7044 (2012) [35] A. Pedrouzo-Ulloa, J.R. Troncoso-Pastoriza, F. Pérez-González, On Ring Learning with Errors over the Tensor Product of Number Fields. arXiv preprint arXiv:1607.05244 (2016) [36] A. Pedrouzo-Ulloa, J.R. Troncoso-Pastoriza, N. Gama, M. Georgieva, F. Pérez-González, Revisiting multivariate ring learning with errors and its applications on lattice-based cryptography. Cryptology ePrint Archive, Report 2019/1109 (2019), https://eprint.iacr.org/2019/1109 [37] C. Peikert, An efficient and parallel Gaussian sampler for lattices. in: Annual Cryptology Conference, (Springer, 2010), pp. 80–97 [38] C. Peikert, How (not) to instantiate ring-LWE. in International Conference on Security and Cryptography for Networks, (Springer, 2016), pp. 411–430 [39] C. Peikert, Z. Pepin, Algebraically structured LWE, revisited. Cryptology ePrint Archive, Report 2019/878 (2019), https://eprint.iacr.org/2019/878 [40] C. Peikert, O. Regev, Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing,(ACM, 2017), pp. 461–473 [41] R.S. Pierce, Associative algebras. Graduate Texts in Mathematics, (Springer, New York, NY 1982) [42] O. Regev, On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM) 56(6), 34 (2009) [43] I. Reiner, Maximal Orders. L.M.S. Monographs. Academic Press (1975)
Non-commutative Ring Learning with Errors from Cyclic Algebras Page 67 of 67 22 [44] R. Vehkalahti, C. Hollanti, J. Lahtonen, K. Ranto, On the densest MIMO lattices from cyclic division algebras. IEEE Trans. Inf. Theory 55(8), 3751–3780 (2009) [45] L.C. Washington, Introduction to Cyclotomic Fields. Graduate Texts in Mathematics, (Springer, New York, 2012) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.