1104

Transcript

1 Efficient provable-secure NTRUEncrypt over any cyclotomic field ∗ Yang Wang, Mingqiang Wang School of Mathematics, Shandong University , [email protected] [email protected] Abstract NTRUEncrypt is a fast lattice-based cryptosystem and a probable alternative of the existing public key schemes. The existing provable-secure NTRUEncrypts are limited by the cyclotomic field it works on - the prime-power cyclotomic field. This is worth worrying, due to the subfield attack methods proposed in 2016. Also, the module used in computation and security parameters rely heavily on the choice of plaintext space. These disadvantages restrict the applications of NTRUEncrypt. In this paper, we give a new provable secure NTRUEncrypt in standard model under canonical embedding over any cyclotomic field. We give an reduction from a simple variant of RLWE - an error distribution discretized version of RLWE, hence from worst-case ideal lattice problems, to our NTRUEncrypt. In particular, we get a union bound for reduction parameters and module for all choices of plaintext space, so that our NTRUEncrypt can send more encrypted bits in one encrypt process with higher efficiency and stronger security. √ log n n ) ω ( n Furthermore, our scheme’s decryption algorithm succeeds with probability 1 − − ω (1) comparing with the previous works’ 1 − n , making our scheme more practical in theory. Keywords : NTRU, Ideal lattice, Canonical embedding, Cyclotomic fields, RLWE 1 Introduction The NTRU encryption scheme, devised by Hoffstein, Pipher and Silverman in [19], was first presented in Crypto’96. It is one of the fastest known lattice-based cryptosystems as testified by its inclusion in the IEEE P1363 standard and regarded as an alternative to RSA and ECC due to its potential of countering attacks by quantum computer. Based ∗ Corresponding author 1

2 on the underlying problem of NTRU, various cryptographic primitives are designed, such as ideuntity-based encryption [11], fully homomorphic encryption [4 26], digital signatures , , [10 18] and multi-linear maps [14]. Meanwhile, a batch of cryptanalysis works were proposed , 6 , 7 , 12 , 13 , 15 , 17 , 20 , 22 , aiming at NTRU family [1 34]. Althought its description ( early version ) relies on arithmetic over polynomial ring for small parameters, it is generally believed that NTRU problem is hard and NTRUEncrypt is secure in practice. However, the security of the first NTRUEncrypt in [19] is heuristic and lack of solid mathematical proof. This leads to a break-and-repair development history of NTRUEncrypt. The first provable secure NTRUEncrypt variant is proposed by Stehl ́ e and Steinfeld in [35]. They gave a reduction from RLWE problem to the IND-CPA security of their NTRUEncrypt. e But the modified scheme is restricted to power-of-2 cyclotomic rings. Although Stehl ́ and Steinfeld’s scheme maybe less practical compared with classical NTRUEncrypt [8], it showed an important connection between NTRUEncrypt and RLWE, hence between problems over NTRUEncrypt and worst-case problems over ideal lattices. Recently, Yu, Xu and Wang modified Stehl ́ e and Steinfeld’s scheme to make it work over prime cyclotomic rings in [38]. Though the results of Yu allows more flexibility of parameter selections, the size requirements for parameters are more limited, making Yu’s scheme less efficiency. Both of the above works are based on coefficient embedding. The first NTRUEncrypt scheme using canonical embedding is discussed in [39] which shows that given approximate parameters, provably secure NTRUEncrypt can work on prime-power cyclotomic rings. Yu’s two papers gave a reduction from a variant of RLWE problem proposed in [9] to their NTRUEncrypts. With the recent calls of post-quantum cryptography by NIST ( Dec. 2016 ), a better understanding of these problems is necessary and the study of NTRUEncrypt is of theoretical value as stated in [39]. Considering the subfield attack proposed in [1 , 6 , 22], designing practical NTRUEncrypt with more flexible choices of parameters over more general rings ( algebraic fields ) is worth to do and this is also the main motivation of our paper. Moveover, different choices of the plaintext spaces influence the efficiency of the previous NTRUEncrypts greatly. That is to say, in order to reach the best efficiency in applications, the existing NTRUEncrypts’ plaintext space are all limited - only encrypt one bit in each encrypt process. Try to improve the efficiency of NTRU scheme is also a big motivation of our research. 1.1 Our Contributions In this paper, we give a IND-CPA secure NTRUEncrypt by using canonical embedding over any cyclotomic field and give a reduction from a variant of RLWE problem discussed in [24] to our NTRUEncrypt. Thanks to the RLWE problem we used and the powerful basis and decoding basis discussed in [24], the reduction parameters are much tighter than all the previous results. Moreover, our scheme allows a more flexible choice of parameters. Also, √ ω ( ) n log n comparing with n our scheme’s decryption algorithm succeeds with probability 1 − − ω (1) the previous works’ 1 − n , making our scheme more practical in theory. Our results enrich the provably secure NTRU family. We also give an improved regularity result for 2

3 all cyclotomic rings by-products. We exploit some ideals shown in [36 38 39], and many , , technical differences need to be treated carefully. Our main contributions are summarized as follows. We design a new variant of NTRUEncrypt by using canonical embedding over any cyclo- ∨ tomic field. We put our scheme to work on the fractional ideal , the codefferent ideal of R any cyclotomic field while the previous works are restricted in prime-power cyclotomic rings. The RLWE problems we used is a simple variant of the original RLWE problem proposed in [23] - an error distribution discretized version of RLWE. Comparing with the RLWE in polynomial rings, the version we used has less reduction loss and tighter reduction parame- ters. We observe that the decryption process is not necessary to consider the so-called coef- ficient embedding. We only need to consider the coefficients of element represented under ∨ R , and different basis effects the results heavily. So we consider a kind of the basis of basis-coefficient embedding and drop the traditional coefficient embedding completely. ∨ R proposed in [24] and subgaussian distribution to analysis We use decoding basis of the error distribution, which give us a looser bound for estimating the decryption algorithm. These mathematical tools also make our decryption algorithm succeed with an exception √ ω ( − n log n (1) ω − ) n of a negligible probability in n , much better than the previous works’ applications. Our main result is as following: , be a positive integer, n = φ ( l Theorem 1.1. ≥ 6 Let q ≥ 8 n , q = 1 mod l be a prime of l ) poly ( n ) , K = Q ( ζ be the ring of algebraic integers of ) be a cyclotomic field and R size K . l √ 1 nk 4 Assume that ≥ 2 satisfies αq ≥ ω ( α α ( n ) = ) ξ · ( . Let log , (1) ) α n with k = O = ) nk log ( 1 × × qR ε ) and p ∈ R (0 . Moreover, with R ∈ ) the set of invertible elements of R , = R/ ( q q q 2 √ √ 3 1 3 + ε 2 2 2 2 2 2 n ( ω · and ln (8 nq ) · q n log n log log n · α let · q σ ) · σ · || p || ≥ . Then if < q ∞ there exists an IND-CPA attack against NTRUEncrypt ) proposed in Section 5 ( n,q, p,σ,ξ 1 1 , there exists a and has success probability ( that runs in time + ) poly time − ) n poly ( n ) n ( 2 poly √ n ̃ K with γ = ( O algorithm solving γ − Ideal-SIVP on any ideal lattice of ) . Moreover, α √ ) n log n − ω ( over the choice of the − n the decryption algorithm succeeds with probability 1 encryption randomness. √ √ 3 1 1 − ε ε + 2 2 2 n = To have a overview, we take σ nq , α · q = ω ) · log n ), then q q · ( ln (8 = 2 3 2 R ω n ·|| p || log , our result is not ). Although when p is a “constant” in n , i.e. p ∈ Z ( ∞ as good as [35 , 39], when p is a “non-constant polynomial”, our results maybe better. In particular, when p is an element whose coefficients are all non-zero with respect to the usual power basis of R , our result is even better than [35], the case of cyclotomic field K = Q ( ζ ) k 2 - the most commonly used cyclotomic fields. More precisely, in this case, the magnitude of 5 . 8 5 . 11 11 in [35] becomes ̃ ω n ), in [38] becomes ̃ n ( ) and in [39] becomes ̃ ω ( n ω ( q ), while ours is 6 ̃ ω ( n ). Moreover, in applications, our construction gets rid of the restriction of cyclotomic fields and has potentialities to send more encrypted bits in one encrypt process - about 3

4 O ( , 38 , 39] when their schemes set p to be a small “polynomial” to n ) times more than [35 and . Further, our decryption algorithm succeeds with a approximate the best bound of q γ √ − ω ( log n (1) n ) − ω − n n − . More details probability of 1 comparing with the previous work’s 1 are discussed in Section 6. 1.2 Technique Overview In this section, we give a technique overview about our constructions. Although the e and Steinfeld’s route, many main thoughts of our NTRUEncrypt constructions follow Stehl ́ differences exist. We design our modified NTRUEncrypt in any cyclotomic field by using canonical em- bedding and give a reduction from a simple variant of RLWE problem proposed in [24] to our scheme. This is quite different from the existing provable-secure NTRUEncrypts, which work in the ring of algebraic integers ( or equivalently the cyclotomic polynomial ring ) in theory. The error distribution of the modified RLWE proposed in [24] is a discretization of a ∨ K R . It is a kind of subgaussian distribution as discussed gaussian distribution on to in [28]. The properties of subgaussian distribution, together with a simple computation 1 ) give us a nice estimation of the infinite norm of elements represented by ( Lemma 5 . ∨ . These technical treatment, with the addition of savings by using the R decoding basis in simple variant of RLWE problem, can tighten up the bound of q and make our scheme more efficient in theory. We regard the element as an usual algebraic number and put all computations in cyclo- tomic fields. More preciously, our scheme is not restricted in the domain ( or equivalent, R the polynomial ring ) - the ring of algebraic integers of a cyclotomic field. We put it to work ∨ on the fractional ideal R , the codefferent ideal of cyclotomic field. Hence, we can get a q and security parameter γ , making our schemes have potentiali- union bound for module ties to send more encrypted bits in each encrypt process with higher efficiency and stronger security. The key generation algorithm is as follows: × : n,q ∈ Z , p ∈ R Input . , σ ∈ R q × × sk, pk ) ∈ R × : A key pair R ( Output . q q ′ ′ × 1 . Sample f let f = p · f , resample. + 1; if ( f mod qR ) / ∈ R from D ; R,σ q × ) ; if ( g mod qR . Sample g from D / ∈ R 2 , resample. R,σ q × . Return secret key sk = f and public key pk = h = pg/f ∈ R 3 . q This is almost the same comparing with the previous works. We use standard method to prove that the algorithm would terminate in expected time. Furthermore, the Gaussian distribution ensures that the secret key is ‘short’. The analysis of public key distribution needs to deal with some kinds of q -ary lattices, defined in Section 3 . 1. By accurate analysis 4

5 of the relationship between different fractional ideals, also inspired by [39] as we remarked in Section 3 λ . with respect to l 2, we give a lower bound of norm in a kind of q -ary lattice. ∞ 1 In this section, we consider the problem absolutely in , hence get a better result comparing K with [39]. We also get an improved regularity result, which is discussed by Micciancio in [27], for any cyclotomic ring by-products. The NTRUEncrypt is as following: × = f ∈ R Key generation : Use the algorithm describe above, return sk q ∨ − 1 × f = pg · with f = 1 , and pk ∈ R = h . mod pR q : Given message m ∈P , set s,e ← ↩ χ and return c = hs + pe Encryption ∨ m ∈ + . R q Decryption Given ciphertext c and secret key f, compute c = fc. Then : 1 ∨ ∨ qR c ) mod pR = ( . return m mod 1 ∨ ∨ ( / R ) with p an invertible element in R pR = R/ ( qR ). The plaintext of our scheme is q ∨ ∨ , not restricted in Our computations are in R . By using the decoding basis of R R and ∨ basis-coefficient embedding of element in R , we give a tight connection between canonical norms and basis-coefficient norms, which is helpful for us to analyze the decryption algorithm. These operations also enable us to get rid of the limitations of cyclotomic fields in theory. Therefore, we get an uniform result for all cyclotomic field. Moveover, by using Lemma 5 1, . √ ) n log n ω − ( n we also prove that the failure probability of our decryption process is negligible - (1) − ω n comparing with the existing schemes’ 3, we . Furthermore, as we remark in Remark 5 . . Hence, in applications, our R can put all computations and storages in an integral ideal of constructions maybe more practical. 1 . 5 To sum up, though the best bounds of q in [36] is about times smaller than ours, n the biggest advantage of our scheme is that our constructions do not limited by the choice of plaintext space and the cyclotomic fields they work on in theory. Hence, our NTRUEncrypt can send more encrypted bits in one encrypt process with higher efficiency and stronger √ n log − ω ( ) n n security. Further, our decryption algorithm succeeds with a probability of 1 − − ω (1) comparing with the previous work’s 1 − n . Therefore, we believe, in applications, our scheme would have more advantages. 2 Preliminaries In this section, we introduce some background results and notations. 2.1 Notations l ˆ ˆ l l = l when Throughout this paper, is odd and l,n l = are positive integers. l is when 2 even. Functions φ ( n ) and μ ( n ) stand for the Euler function and the M ̈ o bius function. We use 5

6 [ ] to denote the set 1 , 2 , ··· ,n } . For p = 1 , 2 , ··· , ∞ , we use || x || n to represent it’s l { norm p p || x || to represent p corresponding to the canonical embedding. When = 2, we usually use k × k s norm. For any matrix ∈ C , we use λ it’s ( M ) stand for it’s eigenvalues and M l ( M ) i 2 i stand for it’s singular values for i ∈ [ n ]. We arrange eigenvalues and singular values by their s ( M ) ≥···≥ λ magnitude, i.e. ( M ) and s ). For two random variables ( M ) ≥···≥ λ M ( n n 1 1 rad represent the radical of a , ∆( ) stands for their statistic distance. Function X,Y X,Y ∏ k α α k 1 rad p . , p ( n ) = ··· with different primes p n , i.e. for n = p positive integer i i 1 =1 i k H and Geometry 2.2 Cyclotomic Number Fields, Space = ( ζ ) for Through out this paper, we consider the cyclotomic number fields. Let Q K ∏ l i μ ( ) i ( ) = = -th primitive unit root, which has minimal polynomial Φ l ζ be the x ζ − 1) ( x l l l | i ∼ = φ ( l ). Hence [ K : Q ] = n = φ ( l ), and K x of degree Q [ x ] / Φ ] ( n ). We set R = O ζ = Z [ = K l ∈ Z be a prime, then the factorization of the ideal 〈 ’s ring of integers. Let 〉 = qR K q be q d d 0 be the largest integer such that q l , let e = φ ( q divides ) and let is as follows. Let ≥ d ∏ g d e 〉 . Then 〈 q f = ≥ 1 be the multiplicative order of q modulo l/q ) q q where are n/ ( ef i i i =1 f different prime ideals, each of norm q . = 1 mod l , we have e = f = 1, the ideal 〈 q 〉 In particular, for an integer prime q 〉 〈 ∏ i 〉 = with splits into is a ω , where n q distinct prime ideals as 〈 q ω = q q,ζ − ∗ i i Z i ∈ l ∏ i q primitive root in is q . We have Φ Z ( x ) = . The norm of ω . Note ( x − q ) mod ∗ q i l ∈ Z i l ∼ x = Z that [ R ] / Φ R ( x ), the Chinese Remainder Theorem gives us a isomorphism = l q q q ∏ ∏ i ), where the represents the direct product. We will use this property Z ω [ x ] / ( x − ∗ q Z ∈ i l q is a prime such that q = 1 mod l . frequently, so from now on, we assume + K/Q is a Galois extension and [ K : Q ] = n = 2 s , s ∈ Z Since , there are n embeddings from K C . In fact, they are automorphisms of K , all of them are complex embeddings to , K { σ K/Q : i = 1 ) = ··· ,n } and use the canonical and form ’s Galois group. We set Gal( i on K , who maps x ∈ K to ( σ ,σ ( x ) , ··· embedding σ ( x )) ∈ H , where H is a kind of 1 n l i l ) = ζ Minkowski space in algebraic number theory. Here we identity ( with σ ζ the l − th i i ∗ n ] s [ ∈ i , , } x ∀ x , ··· ,x element of ) ∈ C ( : x Z , order the σ and define = { H = i 1 − +1 i n n i l n is isomorphic to as an inner product space via the orthonormal basis h H defined as R n ] i ∈ [ n j C e be the vector with 1 in its ∈ -th coordinate and 0 elsewhere, i be the follows: assume j 1 i √ √ complex unit, we set h = s + e ≤ j e ≤ ) and h ) for 1 . − e = ( e ( j j − − +1 n +1 − j n j +1 n j j 2 2 ∼ Moveover, K ) ⊆ H σ ( := K ⊗ R . K = R Q For any element x ∈ K , we can define the ` and norm of x by || x || ∞ = || σ ( x ) || p < for p p p ) | || . Because multiplication of embedded elements is component-wise, | || x σ = max ( x ∞ i ] n [ ∈ i ∈ K , we have || x · y || ≤|| for any a || x,y ·|| y || . The Trace and Norm for p ∈{ 1 , ··· , ∞} p p ∞ ∑ n ) = x x σ ) := N ( x ) and N( ( ∈ K is defined as usual, i.e. Tr( x ) := Tr of x ( x ) = i Q K/ Q K/ =1 i ∏ n − σ Q ( linear: ). The Norm is multiplicative: N( x · y ) = N( x ) · N( y ). The Trace is x i =1 i x + y ) = Tr( x ) + Tr( y ) and Tr( c · x ) = Tr( · Tr( x ) for all x,y ∈ K and c ∈ Q . Also note that c ∑ n ( x ( x ) σ σ y ) = < σ ( ) , x y · · ) = x y Tr( ) is a symmetric bilinear form akin σ ( y ) > , so Tr( i i =1 i to the inner product of embeddings of x and y . 6

7 The absolute discriminant ∆ K is a measure of the geometry sparsity of its ring of in- of K 2 ( ,α represent the Z basis of R , then we can define ∆ = | ··· σ ( α )) | α , tegers. Let , 1 ≤ i,j ≤ n i 1 K j n l represents the determinant of matrix. The discriminant of the th cyclotomic |·| where − number field is ( ) n l n ∆ = . ≤ n K ∏ 1 1 − p p prime p l | R is the usual ideal defined in a ring and a fractional ideal J ⊆ K is a set ⊆ I An integral ideal ⊆ R is a integral ideal for some d ∈ R . It is well known that both I such that J admit dJ and -basis and we can require ∈ Z . The norm of an integral ideal is its index as an additive Z d ) dI N( ) N( dI = is defined as N( R subgroup of I J ) = and the norm of a fractional ideal ) N( | N( d ) | d ∈ where such that dI ⊆ R . One can regard integral ideal as a special fractional ideal. R For any two fractional ideals and J , the sum I + J is the set of all a + b for a ∈ I and I ∈ J I · J is the set of all finite sums of terms ab for a ∈ I and b , and the product ideal J ∈ . Multiplication extends to fractional ideals in the obvious way and the set of fractional b ideals forms a group under multiplication. Every fractional ideal can be represented as the − 1 − 1 · quotient of two integral ideals and has an inverse ideal, written I , such that = R . I I Lattice and Discretization 2.3 H and we only deal with full-rank We define a lattice as a discrete additive subgroup of B ··· { b = , lattices. Assume , b ) = } is the set of basis of a lattice Λ, we have Λ = L ( B n 1 ∑ n { | z ) b L : z B ∈ Z } . The determinant of a lattice , which is ( B ) is defined as | det( i i i i =1 independent of the choice of basis . The minimum distance λ (Λ) of a lattice is the length of B 1 a shortest nonzero lattice vector. We usually use the l . norm, hence λ || (Λ) = min x || = x Λ 6 0 1 2 ∈ ∑ n ∨ = { y ∈ H : ∀ x ∈ Λ , < x , H is defined as Λ ⊆ The dual lattice of Λ = y . x > y Z ∈ } i i =1 i n This is actually the complex conjugate of the dual lattice as usually defined in C . All of the properties of the dual lattice that we use also hold for the conjugate dual. It is easy to ∨ ∨ see that (Λ = Λ. If B = { b is a set of independent vector of a lattice, its dual } ⊆ H ) i basis = { d D } is characterized by < b is the Kronecker delta. It is , d δ > = δ , where ij ij i j j ∨ ( D ) = L ( B ) obvious that . L + I K For any fractional ideal I as Z β , + ··· of Z β K for some β ∈ , we can represent i n 1 i = 1 , ··· ,n . Then σ ( I ) is a lattice of H , and we call σ ( I ) an ideal lattice and identify I I with this lattice and associate with = all the usual lattice quantities. We have ∆ K 2 R )) det( , the squared determinant of the lattice σ ( R ). For any fractional norm I , we also σ ( √ ∆ . The following lemma from [23] gives upper and lower bounds ( ) · σ have det( )) = N( I I k l norm. on the minimum distance of an ideal lattice in 2 For any fractional ideal I in a number field K of degree n , Lemma 2.1. 1 √ √ 1 1 n 2 n n ≤ λ · ( N ) ≤ I n · N n ( ( I ) · ∆ I ) . 1 K ∨ I in K , its dual is defined as I ⊆ = { a ∈ K : Tr ( aI ) For any fractional ideal Z } . It is ∨ ∨ ∨ ∨ I = I , I ) is a fractional ideal and I easy to verify ( embeds under σ as the dual lattice 7

8 of I J ∈ K with J = Z β as defined before. For any fractional ideal + ··· Z β , the for β J ∈ i n 1 ∨ ∨ ∨ ∨ . In fact, an ideal δ ) = where Tr( ··· Z β = J Z β β β can be represented as J + dual of ij i n 1 j ∨ 1 ∨ − ∨ I . I : R · R and its inverse are related by multiplication with the dual ideal K of = ∨ ∨ − 1 The factor ) the different, which is R is often called the codifferent, and its inverse ( R . For more details, one can refer to [5]. R in fact an ideal in We now consider the discretization. As in [24] and [25], the goal is to convert a continuous ( B ), a point x Gaussian into a Gaussian-like distribution. Given a lattice Λ = H and a L ∈ c H representing a lattice coset Λ + c , the goal is to discretize x ∈ y ∈ Λ + c , point to a point y = b x e written is not too large. To do this, we . We want to make the length of y − x c Λ+ f from Λ + ( c − x ), and output y = f + x . We require can sample a relatively short vector f be efficient and depend only on the desired coset Λ + ( − x ). the method used to choose c We call such a procedure valid. Three easy methods are described in [24]. We describe the formal definition as in [28], a modified version of [24]. If Bern denotes the Bernoulli distribution, then the univariate Reduction Definition 2.2. ( a ) = Bern ( d distribution e− a ) − ( d a e− a ) is the discrete probability distribution defined Red a a ∈ R as taking the values for parameter 1 + −d 1. a e with probability d a e− a , a a e− a e with probability 1 − ( d a 2. a ) . −d n ) R ∼ , ··· ,R R A random variable ∈ R R has a multivariate Reduction distribution = ( n 1 n ( a ) on R = ( for parameter a Red a = , ··· ,a j ) if its components R for ∼ Red ( a ) j n 1 j ··· ,n are independent univariate Reduction random variables. , 1 Some useful lemmas are stated in [28], we only state the results. Red ∼ Lemma 2.3. ( a ) is a univariate Reduction random variable for parameter (1) If R 0 1 , then R ( satisfies a i ∈ | R | ≤ 1 , ( ii ) E ( R ) = 0 , ( iii ) V ar ( R ) ≤ R ) R ∈ iv a and ( − ) 0 0 0 0 0 4 c a d a e}⊆ Z . {b , Λ has ( column ) basis matrix B with s and ( B ) (2) Suppose that the lattice R is a Reduction 1 2 2 2 ( random variable of approximate dimension, then ≤ n · s B R || B ) and E ( || B R || || ) ≤ 1 1 2 · s ( B ) . n 1 4 We now describe the coordinate-wise rounding discretisation which is easy to use for our application. One can check the following definition defines a valid discretisation, more details are in [28]. n n L ( B ) is a n Definition 2.4. dimensional lattice in R Suppose . For c ∈ R Λ = , the − n B x e b to the lattice of the point x ∈ R coordinate-wise randomized rounding discretisation c Λ+ Λ + c with respect to the basis B can then be defined in terms of the multivariate coset Reduction random variable by the random variable Q x , c 1 − B Red x = x + BQ , where Q )) ∼ . ( B − c ( b x e , x , c c x Λ+ c 8

9 n B The coordinate-wise randomized rounding e of the point x ∈ R b has the properties x Λ+ c B B 2 2 B ) = x and E ( ||b x e ( 3, it follows that . − x || x ) E n · s . Also, by Lemma 2 ( b ) e ≤ 1 Λ+ Λ+ c c √ B s || ≤ || x || + n ||b · x e ( B ). For lattices in space H , the definition of discretisation is 1 c Λ+ similar. , Λ = ) is a n − dimensional lattice in space H . For c ∈ H B Suppose Definition 2.5. ( L B e X of random variable X to b the coordinate-wise randomized rounding discretisation Λ+ c with respect to the basis is then defined by the conditional random c B Λ + the lattice coset variable B 1 − B . | X = x ) = b x e X )) x = x + BQ , where Q e ∼ Red ( B − b ( c ( x , x , c c c Λ+ Λ+ c √ B ), just as the case defined n · s ( B H ||≤|| x || + , we also have ||b x e x ∈ For a vector 1 c Λ+ n . R in ∨ R R Tensors and Basis for and 2.4 and L be two field extensions of Let , the field tensor product K ⊗ K L is defined Q Q Q − linear combinations of pure tensors a ⊗ b for a ∈ K and b ∈ L , where as the set of all is − bilinear and satisfies the mixed-product property, i.e. for all e ∈ Q , one have Q ⊗ a ⊗ b )+( a ⊗ b ) = ( a + a ) ⊗ b , ( a ⊗ b )+( ) ⊗ b ) = ( a ⊗ ( b ( + b )), e ( a ⊗ b ) = ( ea ) ⊗ b = a ⊗ ( eb a 1 2 2 1 2 1 2 1 and ( a ⊗ b ). These properties define addition and multiplication )( a b ⊗ b b ) = ( a ( a ⊗ ) 2 1 1 2 2 1 1 2 ⊗ , and though the result is not always a field, it will always be one whenever we take K L in Q the tensor product of two cyclotomic fields in this work. A key fact from algebraic number theory is the following. ∏ ∏ α k Proposition 2.6. Let l = have prime-power factorization p l = l , i.e. l are powers k k k K = Q ( ζ of distinct primes. Then ) is isomorphic to the tensor product ⊗ of the field K k l k ∏ = Q ( ζ K , via the correspondence ) a → ( ⊗ a ) , where on the left we implicitly embed l k k k k k k a . ∈ K K each into k k ∼ K ⊗ K When taking , it follows directly from the definitions that the canonical em- = k k k σ of K is the tensor product of the canonical embeddings σ bedding of K ) = , i.e. σ ( ⊗ a k k k k a ). This decomposition of σ σ ) ( ( ⊗ ⊗ a in turn implies that the trace decomposes as Tr k k k k Q K/ ∏ = a ). Tr ( k Q K / k k In our application, we hope that the matrices whose columns are consisted of the basis ∨ and R and larger has smaller s R of s . So, we introduce the powerful basis and decoding n 1 − 1 1 l − ζ , under the to ζ basis as in [25]. We set τ be the automorphism of = ζ K that maps l l l ). Note that for a ( σ )) = ( τ canonical embedding it corresponds to complex conjugation σ ( a l l − ′ ′ ′ 1 − l l ′ = . to ζ ζ any = ζ l dividing ζ τ also maps l , ′ l l l l 9

10 Definition 2.7. of = Q ( ζ ~p ) and R = Z [ ζ The Powerful basis ] is defined as follows: K l l j to be the power basis ( ζ , define For a prime power ) (1) , treated as a vector ~p l 0 , 1 , ··· ,n − 1 } ) ( j ∈{ l ⊆ . K over R ∏ ∏ α k having prime-power factorization (2) = = l p l l , define ~p = ⊗ For ~p , the tensor k k k k ζ of each K product of the power bases = Q ( ~p . ) k k l k ∨ ∨ ~ τ ( ~p ) is d ~p . The Decoding basis of = R , the dual of the conjugate of the powerful basis ∨ ) is a Z − basis of R . Different basis of R Also note that R τ ) are connected by ( ~p ( or unimodular matrix, hence the spectral norm ( i.e. the ) may have different magnitude. s 1 ( ( ( ~p s s σ σ ( ~p )). The following lemma comes from [25], which shows the estimate of )) and n 1 25]. , We remark that more details one can refer to [24 √ √ l ˆ ( ~p )) = We have s Lemma 2.8. , s ( σ ( ~p )) = . ( σ l n 1 l ) rad ( ~ ~ d d )) and s ( σ ( σ ( )). Assume that σ ( ~p ) = T , the lemma s We also need the estimate of ( n 1 √ √ l ˆ ~ s l and s and dual ideal, through ( T ) = T ) = d shows that . By the definition of ( n 1 ) l ( rad 1 1 − ∗ ~ ~ ~ √ , )) = d ( σ ( s ) d )) = σ d T ) = ( ( . Hence we have s an easy computation, one have ( σ ( 1 n ˆ l √ √ l ) rad ) l ( rad ( ~ , . ||≤ d ( σ || . Moreover, one can similarly deduce that ,n for all i = 1 ) 2 , ··· i l l c We define the symbol ||·|| the basis-coefficient embedding norm. Given a basis B of B + a fractional ideal J , written x = x , for any b x + ··· ∈ x coefficient b − , then the B J n n 1 1 is the vector ( x embedding of , ··· ,x x ) and the B − cofficient embedding norm of x is n 1 ∑ 1 n ∨ c 2 2 R R ∈ ) with respect to the (or . Hence, if we represent = ( x ) || x || x defined as i B =1 i powerful basis (decoding basis ), we have √ √ l c c ˆ x || ) for x (1) || x || ≤|| σ ( x R, ||≤ ∈ || l ~ ~ ) ( σ ( p ) σ p ) l ( rad and √ 1 ( ) rad l ∨ c c √ . for x || ≤|| σ ( x ) ||≤ x || ∈ (2) R || || x ~ ~ σ ) d ( ) ( σ d l ˆ l ∨ ∨ + , we use the representative element of the coset x When we write qR x mod qR ∑ n q q ~ ) for computation. Similarly, for element x ∈ by x , , we write R [ − x with x d ∈ i i i =1 i 2 2 ∑ n q q − [ ∈ ). , x with x ~p , we use the representative element of the coset by qR + x mod qR i i i i =1 2 2 ∨ ∨ . Notice that R ⊆ For our applications, we need to do computations in R , any element R R Z − linear combination of the decoding basis. From now of can also be represented as a ∨ R and the powerful basis of R . We will omit the on, we only use the decoding basis of ∨ ~ ~ ( d ) when we use the σ subscribe σ d ) − cofficient embedding of elements in R ( . 2.5 Gaussian and Subgaussian Random Variables 2 || || x − π 2 s . By , 1] as ρ For ( s > ) = e 0, define the Gaussian function ρ x : H → (0 s s normalizing this function we obtain the continuous Gaussian probability distribution D of s 10

11 n − n + parameter · ρ , whose density is given by ( x ). Let r = ( r be a , ··· ,r s ) ∈ ( R s ) n 1 s ∈ for j r [ s ], we can define the elliptical Gaussian distributions r = vector such that j j n +1 − ∑ are } in the basis { x as follows: a sample from D , where is given by h h x r i i n i ≤ i i i ∈ ] [ n chosen independently from the Gaussian distribution D over R . Note that, if we define r i ∑ n map R φ by : ( H → is also a ( elliptical ) Gaussian D ), then ,x x φ h ··· ) = ( x , 1 i r n i n ] ∈ i [ n distribution over . The map φ ◦ σ builds a relation of Gaussian distribution between H R n R . and ⊆ H , σ > 0 and c ∈ H , we define the lattice Gaussian distribution of For a lattice Λ ( b ) ρ σ, c n . We usually omit R ∈ b , for any σ by c ( b ) = D support Λ, deviation and center c ,σ, Λ (Λ) ρ c σ, c when it is 0 . For δ > 0, we define the smoothing parameter η the subscript (Λ) as the δ ∨ 1 ρ smallest σ > 0 such that needs to be for (Λ ≤ δ . It quantifies how large σ ) D \ 0 c L,σ, σ to behave like a continuous Gaussian. We will use following lemmas from [29], [31], [3] and [16]. √ 1 ln (2 n (1+ )) ε · (Λ) ≤ Λ and positive real ε > Lemma 2.9. , we have η For any full-rank lattice 0 ε π λ (Λ) . n Lemma 2.10. For any full-rank lattice Λ , c ∈ H , ε ∈ (0 , 1) and σ ≥ η , we have ( L ) ε √ ε 1+ n − · . Pr ≤ ] n 2 [ σ − b || ||≥ c ← ↩D b c ,σ, Λ ε − 1 Λ and any positive real ε > 0 , we have η Lemma 2.11. (Λ) ≤ For any full-rank lattice ε √ 1 ln (2 (1+ n )) 1 ε . · ∞ ∨ (Λ π ) λ 1 σ > Let denote the Euclidean unit ball. Then for any lattice Λ and any B 0 , Lemma 2.12. n √ √ 2 − n ) nσB )) < 2 ( / (Λ · ρ ρ ( λ is the set of lattice points of norm greater , where Λ / ( ) nσB n σ n r √ √ 2 n − Pr than ( || x || > . nσ ) < 2 . Hence, nσ x ← ↩D ,σ Λ ′ ′ , ⊆ Λ be full-rank lattices. For any c ∈ H , ε ∈ (0 Let 1 / 2) and σ ≥ η , Lemma 2.13. Λ ) (Λ ε ′ ′ / ε 2 mod Λ ∆( ,U we have D Λ . )) ≤ (Λ c ,σ, Λ It is convenient for us to use the notion of subguassian random variables in our application. We only introduce the definition and some lemmas we need, more details can be found in [24], [28], [30] and [37]. We describe the definitions as in [28]. Definition 2.14. ≥ 0 , a real-valued random variable X δ δ − subgaussian with standard For is b ≥ 0 if parameter 2 2 1 t b tX δ 2 . R ∈ for all t e e e ( E ≤ ) is δ − subgaussian random variable with scaled parameter A real-valued random variable X ≥ 0 if s 2 2 2 πtX δ πs t e e e E ( ) ≤ for all t ∈ R . 11

12 2 Notice that if N (0 ,b X ), then X is a δ − subgaussian random variable with standard ∼ 2 2 1 b t 2 b parameter term is exactly the moment-generating function of the one-dimension , the e over Gaussian distribution of parameter δ − subgaussian R b . A real-valued random variable is √ πb subgaussian with scaled parameter δ 2 if and only if it is . b with standard parameter − n or space H R One can extend the definitions to . n ≥ 0 , a multivariate random variable X on R For any is δ − subgaussian Definition 2.15. δ b ≥ 0 if with standard parameter 2 2 1 < X > , t δ || n || b t 2 e e ) ( E ≤ e ∈ R for all . t b Z δ − subgaussian with standard parameter is a ≥ 0 H on A multivariate random variable if 2 2 1 || t || b δ < t , Z > 2 H. ∈ t for all e ( ≤ e E e ) X δ − subgaus This definition is equivalent to say that a random vector or its distribution is n if for all unit vector t ∈ R sian with standard parameter , the random variable b X , t > < 2 x 2 , it can . Using the inequality cosh ( x δ ≤ e is − subgaussian with standard parameter b ) be shown that any B − bounded centered univariate random variable X (i.e. E [ X ] = 0 and | B ) is 0 − subguassian with standard parameter B ( 0 − subgaussian with scaled X | ≤ √ 2 π ). parameter B n Z A random variable R or H is a noncentral subgaussian random Definition 2.16. on || E ( Z ) || ≥ 0 and deviation parameter d ≥ 0 if the variable with noncentrality parameter 0 Z = Z − E ( Z ) is a centered random variable − subgaussian random variable with standard 0 parameter d . We regard a central subgaussian random variable as a special case of a noncentral sub- gaussian random variable. A fact showed in [28] Theorem 3 states that the coordinate-wise B H ∈ c and H is a ⊆ ) for Λ = L ( B z b to z randomized rounding discretisation of e c Λ+ || || and deviation z noncentral subgaussian random variable with noncentrality parameter 1 parameter s )). Moveover, [28] proposed the following useful lemma. ( σ ( B 1 2 Suppose that B is a column basis matrix for a lattice in H with largest Lemma 2.17. singular value ( B ) and Z is an independent noncentral subgaussian random variable with s 1 deviation parameter d to . The coordinate-wise randomized rounding discretisation of Z Z B Z b Z is a noncentral subgaussian random variable with noncentrality parameter || E ( e ) || c Λ+ 1 1 2 2 2 2 B ) s ) ( ) . + ( ( and deviation parameter d 1 Z 2 2.6 RLWE Problem We first state a definition of RLWE with a slight different comparing with [23] by scaling the b component by a factor of q and describe the worst-case result shown in [23]. 12

13 ∨ Definition 2.18. ∈ R For a secret s and a distribution ψ over K , a sample from RLWE R q ∨ over R A × ( K , choosing / ( qR distribution )) is generated by choosing a ← ↩ U ( R ) q q s,ψ R ∨ , and outputting ( a,b = a · s + e mod qR e ) . ← ↩ ψ R The average-case decision version of the RLWE problem, denoted Definition 2.19. − DLWE , is to distinguish with non-negligible advantage between independent samples from q,ψ ∨ s ← ↩ U ( R A where ) , and the same number of uniformly random and independent samples s,ψ q ∨ ( ( K R from × qR / )) . R q Let K be the l -th cyclotomic number field having dimension n = φ ( l ) and Theorem 2.20. R = O be its ring of integers. Let α = α ( n ) > 0 , and let q = q ( n ) ≥ 2 , q = 1 mod l K √ ) -bounded prime such that αq ≥ ω ( n be a poly ( ) . Then there is a polynomial-time n log √ n ̃ ( ) -approximate SIVP on ideal lattices in K to the problem of O quantum reduction from α R − DLWE k given only solving samples, where ψ is the Gaussian distribution D with · ξ q,ψ q 1 nk 4 . ) · ( = α ξ ) log ( nk ∨ R We will use a variant of RLWE whose support set is R , which is discussed in × q q ∨ χ be a discrete error distribution over R 19 by letting , we modify Definition 2 . [24]. Let R − A DLWE and uniform samples from be the problem of distinguishing between q,χ s,χ ∨ . The following lemma shows that for a wide family of discrete error distributions, × R R q q the hardness of the discrete version follows from that of the continuous one. p and q be positive coprime integers, and b·e be a valid discretization Lemma 2.21. Let ∨ ∨ ω ∈ R and a . There exists an efficient transformation that on input pR to cosets of p ′ ′ ′ ∨ ∨ with the following ∈ R ( × ( K a / ( qR ,b )) , outputs a pair ( a = pa pair ,b ) ∈ R ) × R q q R q guarantees: if the input pair is uniformly distributed then so is the output pair; and if the input ∨ for some pair is distributed according to the RLWE distribution ∈ R A and distribution s s,ψ ∨ K , then the output pair is distributed according to A where χ = b p · ψ e ψ . over ω + s,χ pR R ∨ The distribution of s , we need to change it to above is uniform distribution over R error distribution. This modification makes the secret short, which is very useful in some applications. The following lemma shows this variant of RLWE is as hard as the original one by using the technique proposed in [2]. and q be positive coprime integers, Let be a valid discretization to cosets p Lemma 2.22. b·e ∨ ∨ pR be an arbitrary element in R of , and . If R − DLWE samples is hard given some k ω q,χ p ∨ p DLWE in which the secret is sampled from χ := b − · ψ e then so is the variant of R , + pR q,χ ω given 1 sapmles. − k ∨ = 1, ω = 0 and χ = b D In our applications, we will set . Here we use the p e R q · ξ B ∨ coordinate-wise randomized discretisation the decoding basis with Λ = σ ( R b·e ) and B Λ ∨ for R . Hence, a vector x sampled from χ is a noncentral subgaussian random variable with 13

14 1 s ( σ ( B )) and has the property noncentrality parameter x and deviation parameter || || 1 2 √ √ √ √ √ rad ) l ( || ||≤ x nqξ + B n · ( nqξ σ ( )) + ns ≤ (3) 1 l with overwhelming probability. In fact, we can give a elaborate estimate by using Lemma 2 17. One can see the elaborate . × estimate in Section 5. One should also note that when we restrict a to , the problem R q × × ∨ A remains hard as stated in [35]. From now on we denote × R R the distribution on q q s,ψ × ∨ × − DLWE and denote R R × ( R U the problem of distinguishing distributions of ) and q q q,ψ × A . s,ψ 3 Some New Results on q -Ary Lattices We first describe an isomorphism theorem which is helpful for us to analyse the q-ary lattices we need. In some textbooks, it is called the fourth isomorphism theorem or lattice isomorphism theorem. We only describe it’s ring’s version. When come to groups or modules, the results are almost the same. Proposition 3.1. Let R be a ring, and B an ideal of R. Then every subring of R/B is of ⊆ A the form A/B, for some subring A of R such that R , the corresponding relation is B ⊆ − 1 . In particular, every ideal of R/B is of the form A/B, for some ideal A of R such that 1 ⊆ A ⊆ R . B ) and R We know that [ x ] / Φ is a ( x Z Z R [ x ] is a principal ideal domain, hence = q q l q q ∗ i . ω is the i -th element in Z = φ as in Section 2 i 2, then , where principal ideal ring. If we set i l ∏ ∏ n n 1 − x − φ ( ) = x ( Φ ) = ∈ ( x − φ . For any proper ideal R I ) mod q , we can write l i q i =1 i i =1 ∏ 〈 f ( x ) 〉 R x , where f ( I ) contains at least one monomials of x − φ = , i.e. f ( x ) = ( x − φ ) i q i i ∈ S ∏ for some , 2 , ··· ,n } . We will use I S represents the ideal ⊆{ 1 ) R x − φ . ( R of S q q i ∈ i S m ∈ ( R , we know there is an ideal ) Let , I ba an proper ideal of R such a J of R q q qR ⊆ J ⊆ R and I = J/qR . In fact, if we set I = 〈 f ( x ) that R 〉 , then J = 〈 f ( x ) ,q 〉 R . q ∨ ∨ ∨ ∨ ⊆ J ⊆ R , We get R ⊆ ⊆ J Considering the relation ⊆ ( qR ) qJ ⊆ ( qJ ) qR , which 1 1 ∨ ∨ ∨ ∨ ∨ J ⊆ R ( ( ) ) ⊆ . Thus we get the R module inclusion relations qR J implies ⊆ ⊆ R q q ∨ ∨ ∨ ∨ ∨ ∨ ∨ submodule of . Moveover, qJ ⊆ J is a R R J ⊆ /qJ R . /qJ 3.1 q -Ary Lattices q With the relations describe above in mind, we define the -ary lattice we need for our analysis of public key distribution in Section 4. The definitions are as followings: m ∑ ⊥ m , t } = 0 mod a qR ··· ,t ∀ ) ∈ R ( : I i, ( t ) = mod qR ) ∈ I and { ( t a , i i i m 1 =1 i 14

15 ∨ m ∨ ∨ L t a , ··· ,t ,I ) ∈ ( J ( ) ) = : ∃ s ∈ R { , ∀ i, t . = a } · s mod qJ ( i i m 1 ∑ m ⊥ m qR t a , ··· ,t ( ) ∈ J ) = : { ( , ··· t , a In fact, = 0 mod I } and L ( a ,I ) = { ( t 1 i 1 i m i =1 ∨ m ∨ ∨ ∨ ∨ ∨ : ∃ s ∈ R ) , ∀ i, t . It is = ∈ ( · s mod qJ R } , since qJ t ⊆ R ) and a R · a ∈ s i i m i ⊥ easy to see that both ) and L ( a ,I ) are well-defined and are q modules, hence the value ( a I ∨ ⊥ ⊥ ( and L R a ) as a a ( . We also define s ) and L ( a ,R can take over all elements in ). R q q ⊥ a I ) and L ( a ,I ). The following lemma shows the dual relations between ( ⊥ ⊥ ∨ I ) and L ( a ,I ) be defined above, then we have a Let a I ) = q ( L ( a ,I )) ( Lemma 3.2. ( ⊥ ∨ a ,I ) = q ( a and ( I )) L . ( ∨ ⊥ ∨ ⊥ ⊥ ( ( L ( a ,I )) We first show and L ( a ,I ) ⊆ q ( a I ( I )) ) . ∀ t ∈ a ⊆ ( I ) and q Proof. a ∑ ′ m ,I ), we only need to show z ∈ L ( Tr( t a · z z ) = 0 mod q Z . Note that z · = a q · s + i i i i i i =1 ′ ∨ z for some ∈ , we have J i m m m ∑ ∑ ∑ ′ z s ) = Tr( . · Tr( t z · t t · a Tr( ) + q · ) · i i i i i i i =1 i =1 =1 i ∑ ∑ m m By the definition, = q · t for some r ∈ R . Thus · a r Z . z ∈ ) Tr( t q · i i i i i =1 =1 i ∨ ⊥ ∨ ( a ,I )) ( ⊆ a To complete the proof, we will show q I ). ∀ x ∈ ( L ( a ,I )) ( , we need to L ∑ m m ∨ J ∈ show for all i ∈ [ m ] and q · x ) ( qR . Note that q ( J · ∈ qx ⊆ L a ,I ), we can a i i i i =1 ′ ′ ) i ∨ ( ,I ) such that the i -th coordinate is q · s take with s v ∈ J be the vectors in and 0 L ( a ′ ′ ) i ( ) = Tr( x · · q · v s ) ∈ Z , hence q · x elsewhere. We have Tr( ∈ J , since s x can take over i i ∨ . J all elements of ∑ ′ ′ m ∨ ∈ , then J t a ,I ), t with ∀ ∈ ( L · . We write as a · s + q t t ∈ ) t · x Tr( Z i i i i i i i =1 m m m ∑ ∑ ∑ ′ · qx Tr( t , ) · ) + a x · t ) = Tr( Tr( x s · i i i i i i =1 i i =1 =1 i ∑ ∑ m m , hence Tr( s the latter sum is in Z · ) · x and we get a ∈ Z x . Therefore R ∈ a · i i i i =1 i =1 i ⊥ ∨ ( ( I ) = q ( L we have proved a ,I )) a , by taking dual in both side, we finish the proof. ∞ 3.2 Lower Bound of λ L ( in ) a,I 1 ∏ ∏ = Let ). φ − ( x − φ x ) R ( ⊆ R I and J ) = = 〈 f x ( x ) ,q 〉 R ∈ R where f ( S q q i S i S S ∈ ∈ S i S i ∏ n q and ⊆ R We have I qR = J ⊆ /qR . The factorization of ideal 〈 q 〉 R is J i S S S i =1 ∗ q is a = 〈 q,x − φ R 〉 , here we still use i to represent the i -th element in Z with . Since i i l q i,j is a maximal ideal, hence q ], and q n is coprime for any Dedekind domain, each ∈ [ j i i ∏ ∏ 1 − 1 − q q ∩ q q = 〈 q, ( x − φ . Further, )( x − φ = ) · . Therefore, J q = 〉 = J , q j i i S j j i i i S i i ∈ ∈ S S ∏ 1 − ∨ ∨ J we have R . The following lemma is an analogue of Chinese Remainder q = S i S ∈ i Theorem. 15

16 ∨ Lemma 3.3. and J J = I be a fractional ideal of · R Let ⊆ J for i ∈ [ n ] , where I K ⊆ R i i i ∏ ba ideals and are pairwise coprime. Then we have a isomorphism between J/ and J i n i ] ∈ [ J/J the direct sum . ⊕···⊕ J/J n 1 : J −→ J/J J/J ⊕···⊕ Proof. We define the map by mapping x ∈J to ( x mod J φ , ··· ,x 1 1 n ∨ ). Note that J ∩ J is = I φ I ], we have the kernel of R · = J n mod J J for any i,j ∈ [ i j i j i n j ∏ . So we only need to prove φ is a surjective. J i [ n ] i ∈ ∏ n 6 ) J = + J J J , we have M = ( ⊆ J M for j ··· = i and M J + Set = M j 2 n 2 1 j i 3 1 i i = 6 ,j =1 j ∨ ∨ ∨ ∨ J . + J J = ( I R + I = ) R J = R · R ··· = R , since . Hence M M + M + + ··· 2 1 n j i j i n 3 ∨ = 1 ∈ M = 0 such that e e + e satisfy + ··· + e } We can take ∈ R ⊆ R e . These { e i i 1 i i n 2 ) for 6 = i and e J = 1 mod J mod . ∀ ( x ]. , ··· ,x n j ∈ J/J [ ⊕···⊕ J/J ∈ , x i ∈ J for i n 1 n 1 i i j = e x If we take ). We + x + e ,x x ··· ∈ J , we have x mod J , = x x , i.e. φ ( x ) = ( ··· i i n n n 1 1 1 have finished the proof. × m ), the lattice Now we can give a lemma which shows that for a ↩ U ) (( ← L ( a ,I ) is R S q extremely unlikely to contain unusually short vectors for the infinity norm. β q ∞ )) ] , m ≥ 2 and ε > 0 , we have λ For any S ( L ( a ,I Lemma 3.4. ⊆ ≥ B , with B = [ n , S 1 n | S | 1 (3 m +1) n − εmn over the uniformly ) − ε , except with probability p ≤ 2 where )(1 − β q = (1 − n m m × ) . ∈ ( R a random choice of q Let p denote the probability, over the randomness of a , that L ( a ,I Proof. ) contains a non- S β q ≤ B = of infinity norm t zero vector . We upper bound p by the union bound, summing n ∨ a ]. Since the ’s are independent, we ,s ) = Pr s [ ∀ i, t the probabilities = a p · ( mod qJ t i i i a S ∏ ∨ ,s p ( t ]. In other words, we have ) = t p ,s ), where p qJ ( t ) = Pr ,s ( mod s [ t · = a i i i a i i i i S m ≤ i have m ∏ ∑ ∑ ∨ . = Pr t a qJ mod s ] · [ ≤ p i a i S i ∨ ∨ ∨ m i =1 /qJ R ∈ s ∈ ) J ( t ∀ || i, < B 0 < || t ∞ i ∏ ∏ ∏ ′ 1 − − 1 ∨ ∨ ∨ ∨ ′ qJ q = Note that · R q = q q · R · R = = S , where R · q i S i i S ∈ i i ∈ S ∈ i S ∨ ∨ ∨ ∨ / ( q and J R ) ⊕···⊕ /qJ . 3, we get an isomorphisms between J [ n ] \ S . Using Lemma 3 i 1 S S S ′ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∼ R / ( q R R . Also we have R q /qJ ( / R / i q ). ∈ S R ⊕···⊕ ), where ( ) J = i i i j ′ ′ 1 S S S S ∏ ′′ ′ ∨ ∨ ′′ such that s,t We claim that there must be a set ∈ ⊆ S S ∈ and s,t / R q R q i i i j S i ∈ ′ ′′ ′ ∨ ∈ = 0 mod . Otherwise, there are some j ∈ S \ such that either s j q for all R S S j ∨ ∨ ∨ R t , or s 6 = 0 mod q and R = 0 mod and t = 0 mod q R q . In both cases, we have 6 j j i i j ′′ × ∨ ∈ ) = 0, since a ∈ R , we have p . Therefore, for j ( S a ,s t = a · s = 0 mod q R t i i i j i q i ′′ ′ × ∨ R regardless of the value of a . For any j ∈ S ∈ = 0 mod \ t S = a , · s 6 , we have q R i j i i q ′ ∨ × s 6 = 0 mod q , the value of the value of a and a R ∈ R is unique, since S . For j ∈ [ n ] \ i j i q ′ ′′ | S −| d a | S can be arbitrary. Hence, overall, if we set , we get p ( ,s ) = ( q − 1) t d = | . By i i i ∨ ∈ R s , all the element of the coset s + qJ s satisfy the equation t = a · noting that for any i q i ∨ mod qJ for the same t , we can rewrite the sum’s conditions by 16

17 m ∑ ∑ ∑ ∏ ∑ ′ | −| S d p ≤ . ( q 1) − ′ ′′ ′ ∨ ∨ ∨ m i =1 ( ) s R / ∈ qJ ) J ( t ∈ | ≤ ≤| S 0 d ⊆ S S ′′ ∀ < B || i, 0 < || t h ∈ s ∞ i = d S | | ∏ ∈ t h ∨ i = h q R ′′ i S i ∈ ∏ ′′ ′ ′′ ∨ ∨ ′′ ∈ R | , with S Set ∈ S h and J S = | = d . Let q ( B,d ) denote the number of t N i ∈ S i || such that < B and t ∈ h . We consider two cases for N ( B,d ) depending on d . || t ∞ ∏ ∨ ∨ ′′ = ∈ h β ≥ d · n . Since t Suppose that tR R t , h is fraction ideal, we have 〈 ⊆ q = 〉 i ∈ S i ∏ ∨ ′′ is a full-rank R -submodule of h . Hence, N( t ) = N( 〈 t 〉 ) ≥ N( h ) ≥ N( and 〈 t 〉 h ) = q · R i ∈ i S ∏ d q 1 − 1 d ∨ √ ′′ || t ≥ || || ≥ . We conclude that || t ( N( ) ≥ q ))N( · ∆ R q ) = . Thus N( t n ∞ i K ∈ S i n n d β 1 n q q n = ≥ N . B t ) ( ≥ n n · n . Define B ( l, c ) = { x ∈ H Suppose now that || x − c || d < β < l } . Note : ∞ ( h ) is a lattice of H , we get N ( B,d ) is at most the number of points of σ ( h ) in σ that ∞ λ ( h ) 1 B, 0). Let λ = ( B the region , then for any two elements v , we have and v h ∈ 2 1 2 λ, v B ) ∩ B ( λ, v ( ) = φ . For any v ∈ B ( B, 0), we also have B ( λ, v ) ⊆ B ( B + λ, 0). 2 1 d 0)) λ, B vol ( B ( + B 2 d − nβ n n n β − n . 2 + 1) ≤ q q (2 + 1) = ( ≤ B,d ≤ ) N ( Therefore, λ λ, ( B ( vol 0)) ′ ∨ | S |− d ∨ s ) and s ∈ h is q ∈ R We claim that the number of / ( . In fact, if s satisfies the qJ ∨ s ∈ h / ( qJ ). Using a kind of isomorphism theorem which states that for above conditions, ∼ a , b and c with a ⊆ b , ac / bc any fractional ideals , we have a / b = ∏ ∏ ∏ ∏ ∏ ∨ ∨ ∨ ∼ ∼ ∼ h R / ( q ) ) q q qJ R . ) / q R/ ( ( q ) / ( = = = i i i i i ′ ′ ′ ′′ ′′ ′′ S ∈ S i ∈ ( S ∈ \ S i ) S ∈ i S i ∈ i ′ ∏ ∨ d |− S | ′ ′′ / qJ | | ) Hence, we have ( h = | R/ ( q = | ) . Using the above B -bound and the q i i \ S ∈ ) ( S ′ ∏ ′ m d | S −| d P = ≤ of cardinality d is fact that the number of subsets of 2 S , setting 1) ( , − q =1 i we can rewrite the inequality of as p   ∑ ∑ ∑ ∑ ∑   + p ≤ P ′′ ′ ′ ∨ ∨ ∨ m ≤ 0 n · d<β ) ( ∈ t R ) s ∈ J / ( qJ n · β ≤| S d | ≤ ⊆ S S ′′ h || t < B || < s 0 ∈ ∀ i, ∞ i d | S | = ∏ ∈ t h ∨ i q R h = ′′ i i ∈ S ∑ ∑ ∑ ∑ ≤ P ′ ′′ m ∨ ∨ ∨ · d<β 0 n ≤ J ( ( t / R ) ) qJ s ∈ ∈ S S ⊆ ′′ ∈ s h t || || < 0 i, ∀ < B ∞ i | d = | S ∏ t ∈ h ∨ i q = h R ′′ i ∈ i S ′ |− m | S d ′ ( ) q B,d N | | S 2 max ≤ ′ d m ( | S ) |− n · d<β ( 1) − q m ′ ′ ) ( 1 B,d N m | ( S S |− d ) | | = 2 ) (1 + max ′ S | ) d |− 1)( ( m − · d<β n q − 1 1) q ( − ′ ′ ′ ′ 1 m |− |− S S | + mnβ d ) d |− | m ( | S +2 | mn S | ) q ≤ max (1 + 2 n · d<β − q 1 ′ ′ ′ | S | (1+ m )+2 mn ) m mnβ + | S εmn |− m | S − | (1+3 n 2 ≤ 2 ≤ q · · q . 17

18 We finish the proof. The estimate of ( B,d ) in the case d < β · n is inspired by [39]. Remark: N 3.3 Improved Results on Regularity . 13, 3 . 2 and 3 . 4. The following result is a direct consequence of Lemmata 2 10, 2 . 1 m ∈ q ≥ 2 , δ l (0 , = 1 mod Let Lemma 3.5. be a prime, m ε > 0 , S ⊆ [ n ] , c ∈ R ) , and 2 √ 1 | S | | S | 1 mn (1+ ln(2 )) − + ε + δ mn n m m · . Then for all exception a fraction q , where ← n ≥ σ ↩ D t c ,σ, R π m (3 m +1) n × − εmn of of R q ∈ ) 2 , we have a ( q ( ) ⊥ m ⊥ a ); t ( R ( / mod I ( I ∆ )) a ≤ 2 δ. U S S be a distribution over R and denote Let D χ the distribution of such tuple ( a , , ··· ,a m χ q 1 ∑ m m × × . The , ↩ χ ,m ← i for all t ) and , = 1 ··· 2 ( R ↩ U ← a where R × ) ( R t a ) ∈ i q i i i q q i =1 ∑ m ,t regularity of the generalized knapsack function ( ) → t , ··· is the statistical t a m 1 i i =1 i × m ). In [27], Micciancio discussed the regularity over and U (( R distance between R ) D × q χ q general rings and used it to design one-way functions. Some improved regularity results are given in [35], [38] and [39]. Here, we can also give an improved result of regularity, by taking and c = 0 in Lemma 3 . 5. S = φ 1 × for ) m ≥ 2 , δ ∈ (0 , ( Theorem 3.6. ) , ε > 0 and a Let ← ↩ U q R = 1 mod l be a prime, i q 2 √ 1 1 mn (1+ )) ln(2 ε + δ m m ≥ all ∈ [ n ] . Assume t ← ↩ D n i , where σ q · . Then we have R ,σ π ( ) m ∑ m εmn × − (3 m +1) n a ); U (( R , ··· ) ,a × R , ) ∆ ≤ 2 δ + 2 ( . a t q i 1 i q m q =1 i 4 Analysis of Key Generation Algorithm With the results in Section 3, we can derive a key generation algorithm for NTRUEncrypt as in [35]. Further, by choosing appropriate parameters, we can show that the key generation algorithm terminates in limited time and the key distributions are very closed to the uniform distribution. The key generation algorithm is as follows: × n,q ∈ Z , p ∈ R R Input , σ ∈ : . q × × : sk, pk ∈ R A key pair ) × R ( . Output q q ′ ′ × from D , resample. ; let f = 1 · f . Sample f + 1; if ( f mod qR ) / ∈ R p R,σ q × , resample. ; if ( g 2 qR ) / ∈ R . Sample g from D mod R,σ q × pg/f = f and public key pk = h = . Return secret key sk ∈ R 3 . q 18

19 The following lemma shows that the key generation algorithm can terminate with exe- cuting only several times. Let Lemma 4.1. q be a prime such that q = 1 mod l . Let l be a positive integer and √ 1 1 n )) (1+ ln (2 1 × ε n , for an arbitrary ε ∈ (0 , q · ) . Let a ∈ R and p ∈ R · σ > n . Then q 2 π 1 × ′ ≤ [( p · f + a mod ( ) / ∈ R n ] qR Pr . ) ε + 2 q ↩D f ← R,σ q Proof. Thanks to the Chinese Remainder Theorem, we only need to bound the probability ′ 1 i + 2 ε , for any i ≤ n . Here we set to represent the + that ∈ q p · f a is no more than i q √ √ 1 1 1 ∗ n n n ( q . By Lemma 2 ) = λ . ( q 1, we have ) Z -th element in nN ( q ) ) λ ≤ ∆ i ( ≤ nq . K i i 1 n i m ′ . 13, we know that p · f ε mod q . is within distance 2 By Lemma 2 to uniformity on 9 and 2 i ′ 1 q q = − a/p mod , as we need. ε with probability ≤ R/ f + 2 , so we have i i q Next, we show that the generated secret key by the key generation algorithm is small. This lemma is very useful for us to analyze the probability of success in the decryption algorithm in Section 5. √ 1 2 ln (6 n ) n ≥ 8 n , q = 1 mod l be a prime and σ ≥ Lemma 4.2. Let n ≥ 6 , q · · n q . Then π √ √ n − 3 ≥ 1 , the secret key f,g satisfy || f − 2 2 with probability ||≤ || || . and || g p nσ nσ ||≤ ∞ √ √ 1 1 n . . By Lemma 2 n n 9, ( ∆ = ) · ( R ) ≤ ε λ = ( Set R ) = λ Proof. . Note that K n 1 − 1 n 3 √ √ n 2 ln (6 ) 3 n n − 2 σ n . Hence, Pr . Meanwhile, ) ( · R η we have nσ ) ≤ ≤ || x || ≥ ( ↩D ← x ε c R,σ, 2 π − n 3 1, so we get . satisfies the condition in Lemma 4 √ × ) Pr ∈ R nσ and g ||≥ g || ( √ g ← ↩D q R,σ × ||≥ ( g Pr || g ∈ R nσ | ) = ↩D ← g q R,σ × ) Pr R ∈ ( g q ↩D g ← R,σ √ ) nσ Pr || ||≥ ( g ← ↩D g R,σ ≤ × Pr R ( g ∈ ) q ↩D ← g R,σ 1 3 n n − 3 − n . 2 ≤ 2 · · ≤ 1 3 n 2 − ) n ( 1 + 2 ε − q √ ′ n − 3 f g || ≤ Hence, we have || , || || − 2 1 with probability nσ . Then we can estimate ≥ √ ′ . nσ || p || 2 f || ||≤ 1 + || p || f ·|| ||≤ ∞ ∞ The last lemma of this section estimates the statistic distance between the distribution × R . The proof is almost the same with of public key and the uniform distribution on q × Thm 3] or [38 , restricted to D [35 , the discrete Gaussian D Thm 2]. We denote by R,σ σ,z × R + z . q 19

20 √ 3 1 1 × ε +2 2 2 n ≥ σ and Lemma 4.3. ) · q Let 0 < ε < ln (8 . Let p ∈ R nq and , y R ∈ i q q 2 − 1 1 p mod qR for = ∈{ − , 2 } . Then y z i i i ] [ × 5 n · p + D y 2 1 σ,z 1 × . ∆ mod q,U ( R ≤ ) q × b c εn q · D p y + σ,z 2 2 × × a For , we define Pr = Pr R . [( y + pf ∈ / ( y + pf ) = a ], where f Proof. ← ↩ D ) f a 1 ,f 2 i 1 2 σ,z q 1 2 i ′ n 2 n +5 − εn − n c −b q − q 1) Pr | · It is suffice to show that q − 1) − |≤ =: ε 2 except a fraction ( ( a n − 2 nε 7 × of q ∈ R 2 a . Note that a ≤ f + + a y f ( = a / z ) + a pf z + is equivalent to ( y 2 1 2 1 1 1 2 2 2 1 1 q × × 2 × ( /a a in R pf [ and − a := Pr /a , we get Pr ← ↩ R + ) = when a ← ↩ − R a ) f 1 a 2 f 1 2 1 1 2 ,f q q q 2 1 2 × = a . z f + a ) z a ] = Pr R ( ∈ a for 1 2 2 1 2 2 − a /a q 2 1 2 × z ) ∈ R The set of solutions ( , f a ← ↩ D f + f , to the equation a a ,f = + a f z 2 1 1 1 1 1 2 i 2 2 2 σ,z i ⊥× ⊥× ⊥ × 2 = z = ( z is ,z z ) and a + qR a a ∩ ( R mod . Therefore + qR ) , where 2 1 q ⊥× 2 D a + ) ( z ,σ R = Pr . a × × R D + ( z ) ( D qR z + + R · + qR ) q q 1 R,σ R,σ 2 a 2 ⊥ × 1 t and t , so are in the same ideal ) ∈ , t t = − t , we know for any a Note that R ( a ∈ 1 2 2 1 q a 2 ⊥× ⊥ ⊥ ⊥ ⊥ a = a ). Similarly, \ ( I ) I ( . It follows that a a ( I ) ) = R of \ ( ∪ a ∪ q R ⊆ S I = φ [ ⊆ n ] ,S 6 S q × R ( )). Using the inclusion-exclusion principal, we + qR = R \ we have ∪ qR + I ( S ] n [ = ⊆ S ,S 6 φ q get ∑ | ⊥× | S ⊥ 2 2 z (4) , )) I D − 1) + a ( · D ( ) = ( ( z + a S ,σ R ,σ R ] n [ ⊆ S ∑ × | S | (5) ∀ ( z i + R 1 , + qR ) = ∈{ . ) qR + I ( − 1) 2 } , D · D + ( z i i S R,σ R,σ q ⊆ [ ] S n 2 7 − 2 nε × n ) : 2 ∈ ( of q a In the rest of the proof, we show that, except for a fraction R ≤ q n − 1) ( q ⊥× 2 ) = (1 + δ ( ) · z + D a , 0 ,σ R n 2 q n 1) ( q − × , qR z 1 + R , 2 + ∈{ ) = (1 + δ } ) · , D ∀ ( i i i R,σ q n q ′ 2 n +2 −b εn c − n } q for i ∈{ 0 , 1 , 2 |≤ . These imply that | Pr where − ( q − 1) 2 δ |≤ ε | . a i c εn −b n − Handling , we apply Lemma 3 m = 2 and δ = q εn | ≤ S | (4): When . Note . 5 with 2 2 / | R ( qR ) | ⊥ ⊥ 2 2 2 2 2 / a that ( I ) | = ( I qR ) ⊆ R . Meanwhile, , we have | = | ) ⊆ qR ( / a R | R S S 2 ⊥ / ) | I ( ) a | qR ( S ⊥ 2 2 n −| S | | S | n ( qR and ) | = | I . Therefore for all | = q | a = ( , since | R I | / | I q | ) | R / /I q | = S S q S S q 7 n 2 2 × ∈ ( R except a fraction a ) ≤ , of 2 nε q q ∣ ∣ ∣ ∣ ⊥ − n −| S | | n S ⊥ −| − 2 2 z + a D ( I − )) ( q I D 2 |≤ ( a = ( δ. | )) − q ∣ ∣ S S R ,σ z ,σ, R − ′ ′ ⊥ | , we can choose S S | When > εn with | S a | = b εn c . Then we have ⊆ S ( I ⊆ ) S ⊥ ⊥ ⊥ ′ ′ 2 2 )). Using the result proven before, ( I I a ( ( a ) and hence ( D D )) ≤ a ( I S − z z R ,σ, R − ,σ, S S 20

21 ⊥ − n −b εn c 2 )) ≤ 2 ( + q a we conclude that ( I D . Overall, we get δ S R ,σ, − z ∣ ∣ ∣ ∣ n ∣ ∣ n ∑ ∣ ∣ ( ) q − ( 1) ∣ ∣ n ⊥× − k n − k ⊥× ∣ ∣ 2 2 D − z + a ) ( q − = 1) ( + D ( z − ) a ∣ ∣ ,σ R R ,σ k ∣ ∣ 2 n ∣ ∣ q k =0 n ∑ ( ) n +1 n c εn −b n − + 2 δ 2 ≤ q k e εn d k = n +1 εn −b c − n q δ ( 2 ) ≤ + 7 n 2 × 2 n ≤ for all except a fraction a ∈ ( R choices of . The ) satisfies , since the are 2 δ of S nε 2 0 q q 2 n q q +2 +1 n −b εn c n n n − b− εn c 2 n +2 b− εn c 2 2 δ · q |≤ ( δ ≤ 2 ) = ( + | q as required. q · ) n 0 − 1) q − 1 ( q | S | S ∈ [ n ], det | I R/J + qR | = | Handling is the | = q (5 ) : Note that for any , where J S S S λ such that R / ( qR ) = I ideal of . By Minkowski’s Theorem, we have J ) = ( I qR + S 1 S S √ | S | n n 9 gives that · q ( qR ) ≤ . Lemma 2 . + σ > η I ( I + qR ) for any | S | ≤ n λ with δ S S n 2 n − | −| S 2 . Therefore, Lemma 2 . 13 shows that q D . For the δ 2 | ≤ ( I | + qR ) − q δ = S z − R,σ, i ′ n n | ≤ S S ⊆ S with | S > | case . Using the same argument above, we get , we can choose | 2 2 ′ n − 2 ≤ δ + qR ) q D + 2 ≤ ) ( I qR + D I ( . Therefore, S z − R,σ, z R,σ, − i i S ∣ ∣ ∣ ∣ n ∣ ∣ n ∑ ∣ ∣ ) ( ( q − 1) ∣ ∣ n k × k − × ∣ ∣ ( + qR ) ( + q R − − D z 1) + qR ) − = + z ( D R ∣ ∣ i R,σ i R,σ q q k ∣ ∣ n ∣ ∣ q k =0 n ∑ ( ) n +1 n k − + 2 δ 2 ≤ q k n k = 2 n n +1 − 2 q δ ≤ 2 ( + ) , which leads to the desired bound on i = 1 , 2. δ i 5 NTRUEncrypt Scheme and Security Analysis In this section, we describe the NTRUEncrypt. We set the plaintext message space 1 nk ∨ ∨ 4 ∨ is a positive integer. where k = R D /pR e P . Denote with ξ = α · ( χ = b ) R q · ξ ) log ( nk ∨ ∈ R ⊆ R We will use decoding basis for element . One should note that f = 1 mod pR x ∨ f = 1 mod pR implies . Key generation : 4 , return sk = f Use the algorithm describe in Section × ∨ − 1 × pg R ∈ = h = . · f with f = 1 ∈ R mod pR , and pk q q Encryption : Given message m ∈P , set s,e ← ↩ χ and return c = hs + pe ∨ + ∈ R . m q Decryption : Given ciphertext c and secret key f, compute c fc. Then = 1 ∨ ∨ c . mod return m qR ) mod pR = ( 1 21

22 We first give an accurate estimate of the infinite norm of elements sampled from the discertisation of a Gaussian distribution. 1 ) ( √ 4 nk ∨ . (1) , χ = b D k and ) e n O , α · q ≥ ω ( = log Assume that ξ = Lemma 5.1. α · ξ R q log nk √ 2 2 ∨ log n · α Set · q ω ) = B the decoding basis for R ( , then for any t ∈ H , we have δ n and √ 2 t ·|| ) n log n − ( ω || 2 || Pr ≤ n || > δ | ) x , t ( | ( t ) . x ↩χ ← q · ξ √ Note that a gaussian random variable has mean 0 and deviation ← ↩ D Proof. x , the ξ q · π 2 e is a noncentral subgaussian random variable with noncentrality parameter discretisation b x 2 2 1 ξ q 1 2 2 + s ) ) ( B , by Lemma 2 . 17. Hence, we have 0 and deviation parameter ( 1 4 2 π ( ) 2 2 ξ q 2 2 1 1 + B ) ( · s ·|| t || 1 x b , ) e ( t 2 4 π 2 e ≤ ( E e ) . ← , by taking the Chernoff bound, we get x For any ↩ D q · ξ 2 t , ( x e ) | δ ·|| t || | 2 b | ( t , b x e ) | > e > δ ·|| t || e ) ) = Pr( Pr( ) ( 2 2 ξ q 2 2 2 1 1 δ − + || ·|| s · || ( B ) t ·|| t 1 2 2 4 π . 2 · ≤ e √ ( ) 2 2 l ( rad ) ξ q 1 1 2 2 s ·|| t || ( . Since s ≤ 1, we have B ) = ( B · ) + Now, we estimate the value of 1 1 l 2 π 2 4 ( ) 1 ( ( ) ) 2 2 2 2 √ 1 2 ( l ) rad − q ξ q α 1 1 1 nk 1 2 2 2 2 2 2 n · α · ·|| t || · = Ω( + + · q s · n log B ( = || t ·|| ) 1 π 2 4 log( 4 l π 2 2 2 nk ) 2 || || t ). Therefore, √ √ 2 2 2 n 2 q ( ω · 1) − n (log · −|| t || α ) 2 ( ·|| || − ω t n log n ) n log e | || ≤ Pr( t ·|| > δ ( ) e x b , t ) | . n ≤ . 1, we can get a useful estimate for || x || By using Lemma 5 with x ← ↩ χ = b D . e ξ · ∞ q 1 1 i i 0 , ··· , 0 , t = ( ) and t = ( , ), we get , 0 Choose ··· , 0 , − , 2 2 2 2 √ √ 1 2 ) n log n 2 − ω ( √ ( | Re( ω ( σ n log n · α Pr · q ( ) ≤ n x )) | > ↩χ ← x 1 2 and √ √ 1 2 n ) log n 2 − ω ( √ > ω Pr ( | ( Im( n log n · α σ · q . ) ≤ n ( x )) | 1 ← x ↩χ 2 √ 2 2 − ω ( n log n ) n n log nα ( q | )) ≤ σ ( x ) | > ω ( . Similarly, one can prove Hence we have Pr 1 x ↩χ ← √ 2 2 − ω ( n log n ) | > ω ( . Therefore, we n log nα ,n q σ )) ≤ n ( | that Pr ··· ( x ) for any k = 1 , 2 k ← x ↩χ conclude √ √ √ ) ( 2 − ω n log n 2 − ω ( n log n ) n α n · q ≤ n log )) ≤ n · n · . (6) ( x Pr ) || > ω σ ( ( || ↩χ ∞ x ← In order to show that the decryption algorithm succeeds with high probability, we need c || x | and || x || some relations between for any x ∈ K , i.e. we need the parameters C C and 1 2 1 c c √ x || C ≤ || x || ≤ C such that || X || C . Recall that for decoding basis, we have and || = 1 1 2 ˆ l √ rad ( l ) = C . 2 l 22

23 √ √ 1 2 ln (6 n ) ˆ n Lemma 5.2. , q = 1 mod l , σ ≥ Let ≥ 6 , n · n · q q ≥ , C = 8 n l and C = 2 π √ √ √ 3 ( ) l rad ω ) 2 2 − 2 ( n log n 2 q log · σ ·|| p ( n . If < q n 1 − n log log n ) ω · α || · , , then with probability ∞ l the decryption algorithm of NTRUEncrtpt recovers m . ∨ ∨ ∨ · s = p · g · s Proof. qR Notice that , we have fc = pgs + pfe + fm mod qR f ∈ R · . If h mod q c + fm || pgs || < pfe + , then we have fc has the representation pgs + pfe + fm when compute ∞ 2 ∨ ∨ ∨ = ( fc mod qR mod qR pR . Hence, we have , since f = 1 mod pR = 1 m ) mod q ∨ c || mod . It thus suffices to give an upper bound on the probability that fc ≥ pR || . ∞ 2 c c || || Note that ≤|| fc || || ≤ C fc fc || = C || pgs + pfe + fm ||≤ C ( || pgs || + || pfe || + || fm || ). ∞ √ 3 − n nσ ≥ − 2 , || f ||≤ 2 2, with probability 1 || p || . By the choice of parameters and Lemma 4 ∞ √ and || g ||≤ nσ . Hence, combining with (6), we get √ √ 2 pfe ||≤ 2 || nσ || p || + || ·|| s || || + pgs nσ || p || ) ·|| e || ∞ ∞ ∞ ∞ √ 2 2 2 log n · α ω · q ( ) σ || n || ≤ p ∞ √ ∨ − ω ( n log n ) ∨ . Since m ∈ R − / ( pR with probability 1 n ⊆ K , by reducing modulo the ) ∑ n 1 1 ~ ~ m ( pσ d ) , ]. Hence ’s, we can write into pσ ( ε d ) − with ε ( ∈ i i i i =1 i 2 2 √ n n ∑ ∑ n ~ ~ ( σ ||≤ ε ) d || || p ||≤|| d ( pσ ε ) || C || , || || m || = p i i ∞ i i ∞ 2 2 =1 i i =1 by using √ n n n ∑ ∑ ∑ n c ~ ~ ~ ( ε ( ε · d d C ) ||≤ C || σ ε ) ( ≤ = d ) || || ·|| || . i i 2 i 2 i i i 2 =1 i i =1 =1 i n − 3 2 − 2 1 ≥ with probability C . Therefore, ||·|| || || || nσ || ≤ So, we have m p f || ≤ || fm 2 ∞ putting these results together, we have √ 2 2 2 2 ( n ω ( C ||≤ fc || ·|| · q log ) · σ ·|| p || n ) + n · σ · p || α C · 2 ∞ ∞ √ 3 2 2 2 2 · log log n · α ( · q log ≤ n σ ·|| p || n ω ) ∞ √ n log n ) − ω ( C = , where we have used the fact that C 1 and ≤ n with probability 1 − 2 √ log log n ). We get the results we need. ( n O ˆ = We remark that we can put all computations in an integral ideal l · Remark 5.3. I ∨ ˆ . The only by multiplying an integer ⊆ l without changing the conditions on q and α R R ˆ a to represent change is a slight modification on the decryption algorithm. We use symbol ∨ ∨ ˆ R the corresponding element of , i.e. ˆ a = a l · a . Note that f = 1 mod pR = 1 mod pR ∈ , 1 ˆ ˆ ˆ ) = we have l mod pI . Therefore, ˆ m = l . ) ( · l ( f · ˆ c mod qI ) mod pI f with ˆ m ∈ I/ ( pI ˆ l × , − DLWE The security of the scheme follows by an elementary reduction from R q,D qξ × R exploiting the uniformity of the public key in . It’s proof and the invertibility of p ∈ R q q is almost the same as in [35] or [38]. 23

24 √ 3 1 1 + ε 2 2 . ) Lemma 5.4. l , σ ≥ Let ln (8 nq ) · n 6 , · q q ≥ 8 n , δ > 0 and ε ∈ (0 , , n q = 1 mod ≥ 2 T and has success If there exists an IND-CPA attack against NTRUEncrypt that runs in time 1 × probability + with parameters δ and qξ , then there exists an algorithm solving R-DLWE q 2 ′ ′ − Ω( n ) q δ = = δ − ( T n ) and has success probability . O + T that runs in time be the given IND-CPA attack algorithm, we construct an algorithm B against Proof. Let A × × × ∨ O that samples from either U ( DLWE as follows. Given oracle R × R − ) or A R q q s,D q,D qξ qξ ′ ′ × ∨ calls O to get a sample ( h ← ,c , s R ↩ χ for some × R B with public , then runs A ) from q q ′ × p · h key ∈ R h = . When A outputs challenge messages m 1), , m , ∈P , B picks b ← ↩ U (0 1 0 q ′ ′ ∨ A + m p ∈ R c computes and give it to · . When a returns its guess b = , B returns 1 c b q ′ b b and 0 otherwise. when = ′ × R h Note that , so is the public key h given to A is uniformly random in . Thus, it q − Ω( n ) is within statistical distance q of the public key distribution in the genuine attack. ′ hs = Moreover, when + e with s, e ← ↩ χ , the ciphertext c given to A has the right c × O A distribution as in the IND-CPA attack. Therefore, if outputs samples from , A s,D qξ 1 n Ω( ) − + q . δ − B succeeds an ≥ returns 1 with probability 2 ∨ × and ), then c is uniformly random in R R × ( R Now, if O outputs samples from U q q q 1 b . Hence, B outputs 1 with probability independent of B . The claimed advantage of 2 follows. In a summary, we have the following results. q n = φ ( l ) ≥ 6 , l ≥ 8 n , q = 1 mod l be a prime of Theorem 5.5. Let be a positive integer, √ n ) and K = Q size ζ poly ) . Assume that α = α ( n ) ≥ 2 satisfies αq ≥ ω ( ( log n ) . Let ξ = α · ( l √ 3 1 1 nk 1 × ε + 4 2 2 . Moreover, let σ ≥ n q ) ( ) and p ∈ R with and k = O (1) , ε · ∈ ln (8 nq ) · (0 , q ) nk 2 log ( √ 3 2 2 2 2 < q . Then if there exists an IND-CPA attack against · · α log · q n ) n σ ·|| p || ( ω log log n ∞ 1 1 n,q, p,σ,ξ ) that runs in time poly ( n ) and has success probability NTRUEncrypt ( + , ( n ) 2 poly Ideal-SIVP on any ideal lattice of poly ) − time algorithm solving γ − n K with ( there exists a √ √ n ω ) n ( log − n ̃ 1 . Moreover, the decryption algorithm succeeds with probability ) n ( O − = γ α over the choice of the encryption randomness. 6 Comparison with Previous Works q as small as possible and α ( hence γ ), as big as In applications, we hope we can take , 38 , 39], the results of q and γ depend possible ( as small as possible ). In previous works [35 heavily on the choice of p , i.e. p is a ‘constant’ or p is an ‘usual polynomial’. Therefore, in applications, the number of encrypted bit in each encrypt process depends heavily on the choice of p . We can take a comparison for an overview. (1) is a ‘constant’. p 3 4 In this case, by taking qα = Ω(log γ = n ), one have the approximate parameter √ 1 n . 1 5 75 . 3 2 ε − ̃ 2 39]. The magnitude of q and γ are q · q ) in [38 , ω = l O || log p ( ( l ·|| ) 0 . 75 log n 24

25 2 . 25 1 5 1 . . 8 5 2 4 − ε 0 2 and ω ( d l ) with l l be a prime in [38] and q = ̃ log ·|| p || l ·|| p || = ) and γ ω ( √ 5 4 v n || ( ) with l = d ·|| , d is a prime in [39]. In [35], one can set α · q = ω ( ω p log n ), = ̃ γ dl 1 2 2 . 5 2 − 5 . 5 4 ε 2 n ·|| p || ( ) and γ = ̃ ω ( n n then q ·|| p || = ). In [36], they improved the result log ω 4 . 5 = ̃ n ω ). ( q to is an ‘usual polynomial’. p (2) 3 4 = n ), one have the approximate parameter γ = Ω(log In this case, by taking qα √ 1 n 5 1 . 2 75 . 4 ε − ̃ 2 39]. The magnitude of γ are q , q ) in [38 q O ( and · l l = log ) ω || ( ·|| p 0 . 75 log n 25 . 3 1 5 1 . 0 ε 4 . 10 5 − 2 2 ( = ω ( d ) with l be a prime in [38] and l ω = ̃ γ log q ·|| p l ·|| p || || ) and l and √ 7 4 v γ ·|| p || = ̃ ) with l = d ω , d is a prime in [39]. In [35], one can set α · q = ω ( n ( log n ), dl 1 2 ε 3 . 5 − 4 2 7 . 5 2 log = n · deg ω p ) ·|| p || ( ) and γ = ̃ ω ( n n then q · deg ( p ) ·|| p || ( ). (3) Our results. p ∈ In our scheme, we regard ‘constant’, i.e. Z , and ‘usual polynomial’ as an element of ∨ R . In both cases, they have the same status. Hence, our results do not algebraic number in 3 4 n ), one have the approximate parameter qα depend on the choice of = Ω(log . By by taking p √ 1 n 3 2 − ε 3 ̃ 2 ( O γ = · || ) and q = ω ( n ), as in [38] and [39]. Then, one can take log q n ·|| p 75 . 0 ∞ n log 6 . 5 4 = ̃ ω ( ·|| p || γ ). In particular, our results eliminate the limitation of cyclotomic fields. n ∞ p In order to reach the best bounds, the previous results must set ∈ Z , which limits the = 2 to encrypt one bit each time. If one p number of encrypted bits. The usual case is set n bits each time, which means that every coefficient of the power basis ( or wants to encrypt would become very bad, see case (2). Note that monomial ) must be used. The bound of q √ √ √ ∏ p ( − 1) rad ( l ) l ( ) rad p c ||≤ p || when represented under decoding bases, ·|| , where || . = p n l l If we want to make the best of the number of encrypted bits, for example, take every coefficient’s value in [0 ··· ], the results of previous work would become pretty bad, since , ,n p || || || p || . More precisely, the previous results also depend on while ours only depend on ∞ 11 ( ( q in [35] becomes ̃ ω ) bits each time, the magnitude of n O ), when we want to encrypt n 6 5 . 11 . 5 8 ω ω n ) and in [39] becomes ̃ n ( ) comparing with ours ̃ ( ( n ω ), when we in [38] becomes ̃ 15 O ( n log( n )) bits each time, the magnitude of q in [35] becomes ̃ ω ( n want to encrypt ), in 15 13 10 ). ) and in [39] becomes ̃ ω ( n n ) comparing with ours ̃ ω ( n [38] becomes ̃ ( ω That is to say, if we consider to encrypt many bits in each encryption process, one can see our construction has potentialities to do much better than [35 38 , 39], since our scheme , p . has no limits on the choice of 7 Conclusion 1 . 5 n To sum up, though the best bounds of q is about times smaller than ours, our scheme do not limited by the choice of and the cyclotomic fields it works on. Hence, our scheme get p rid of the dependence of the plaintext space, so that our NTRUEncrypt has potentialities to send more encrypted bits in each encrypt process with higher efficiency and stronger security. √ ( ω − n log n ) n − Further, our decryption algorithm succeeds with a probability of 1 comparing 25

26 − ω (1) with the previous work’s 1 − . Therefore, we believe, in applications, our scheme may n have more advantages. Acknowledgement The authors would like to express their gratitude to Bin Guan and Yang Yu for helpful discussions. References [1] M. Albrecht, S. Bai, L. Ducas: A subfield lattice attack on overstretched NTRU as- sumptions: Cryptanalysis of some FHE and graded encoding schemes . CRYPTO 2016, LNCS, vol. 9814, 153-178, (2016). Fast cryptographic primitives and circular [2] B. Applebaum, D. Cash, C. Peikert, A. Sahai: secure encryption based on hard learning problems . CRYPTO 2009, LNCS, vol. 5677, 595-618, (2009). [3] W. Banaszczyk: . New bounds in some transference theorems in the geometry of numbers 296 Math. Ann., (4), 625-635, (1993). [4] J. W. Bos, K. Lauter, J. Loftus, M. Naehrig: Improved security for a ring based fully homomorphic encryption scheme . IMACC 2013, LNCS, vol. 8308, 45-64, (2013). [5] K. Conrad: The different ideal . Available at Http://www.math.uconn.edu/ ∼ kconrad/blurbs/ . [6] J. H. Cheon, J. Jeong, C. Lee: An algorithm for NTRU problems and cryptanalysis . LMS J. COMPUT. of the GGH multilinear map without a low-level encoding of zero 19 (A), 255-266, (2016). MATH., [7] D. Coppersmith, A. Shamir: Lattice attacks on NTRU . EUROCRYPT 1997, LNCS, vol. 1233, 52-61, (1997). On the efficiency of provably secure NTRU . [8] D. Cabarcas, P. Weiden, J. A. Buchmann: PQCrypto 2014, LNCS, vol. 8772, 22-39, (2014). [9] L. Ducas, A. Durmus: Ring-LWE in polynomial rings . PKC 2012, LNCS, vol. 7293, 34-51, (2012). [10] L. Ducas, A. Durmus, T. Lepoint, V. Lyubashevsky: Lattice signatures and bimodal gaussians . CRYPTO 2013, LNCS, vol. 8042, 40-56, (2013). [11] L. Ducas, V. Lyubashevsky, T. Prest: Efficient identity-based encryption over NTRU lattices . ASIACRYPT 2014, LNCS, vol. 8874, 22-41, (2014). [12] L. Ducus, P. Q. Nguyen: Learning a zonotope and more : Cryptanalysis of NTRUSign countermeasures . ASIACRYPT 2012, LNCS, vol. 7658, 433-450, (2012). [13] C. Gentry: Key recovery and message attacks on NTRU-composite . EUROCRYPT 2001, LNCS, vol. 2045, 182-194, (2001). 26

27 [14] S. Garg, C. Gentry, S. Halevi: Candidate multilinear maps from ideal lattices . EURO- CRYPT 2013, LNCS, vol. 7881, 1-17, (2013). [15] N. Gama, P. Q. Nguyen: New chosen-ciphertext attacks on NTRU . PKC 2007, LNCS, vol. 4450, 89-106, (2007). Trapdoors for hard lattices and new crypto- [16] C. Gentry, C. Peikert, V. Vaikuntanathan: . Proc. of STOC, ACM, New York, 197-206, (2008). graphic constructions [17] N. Howgrave-Graham: A hybird lattice-reduction and meet-in-the-middle attack against NTRU . CRYPTO 2007, LNCS, vol. 4622, 150-169, (2007). NTRUSign: [18] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte: Digital signatures using the NTRU lattice . CT-RSA 2003, LNCS, vol. 2612, 122-140, (2003). NTRU: A ring-based public key cryptosystem [19] J. Hoffstein, J. Pipher, J. H. Silverman: . ANTS 1998, LNCS, vol. 1423, 267-288, (1998). A chosen-ciphertext attack against NTRU [20] E. Jaulmes, A. Joux: . CRYPTO 2000, LNCS, vol. 1880, 20-35, (2000). Basic algebra . Birkh ̃ a user Boston, (2006). [21] A. W. Knapp: Revisting lattice attacks on overstretched NTRU parameters . [22] P. Kirchner, P. A. Fouque: EUROCRYPT 2017, LNCS, vol. 10210, 3-26, (2017). [23] V. Lyubashevsky, C. Peikert, O. Regev: On ideal lattices and learning with errors over rings . EUROCRYPT 2010, LNCS, vol. 6110, 1-23, (2010). [24] V. Lyubashevsky, C. Peikert, O. Regev: A Toolkit for Ring-LWE Cryptography . Crypto. ePrint Archive, 2013:293, (2013). [25] V. Lyubashevsky, C. Peikert, O. Regev: . EURO- A Toolkit for Ring-LWE Cryptography CRYPT 2013, LNCS, vol. 7881, 35-54, (2013). [26] A. L ́ pez-Alt, E. Tromer, V. Vaikuntanathan: On-the-fly multiparty computation on o . Proc. of STOC, ACM, New York, the cloud via multikey fully homomorphic encryption 1219-1234, (2012). Generalized compact knapsacks, cyclic lattices, and efficient oneway [27] D. Micciancio: functions . Comput. Complex. 16 (4), 365-411, (2007). [28] S. Murphy, R. Player: Noise Distributions in Homomorphic Ring-LWE . Crypto. ePrint Archive, 2017:698, (2017). Worst-case to average-case reductions based on gaussian mea- [29] D. Micciancio, O. Regev: sures . SIAM J. Comput., 37 (1), 267-302, (2007). [30] D. Micciancio and O. Regev: Trapdoor for lattices: Simpler, tighter, faster, smaller . EUROCRYPT 2012, LNCS, vol. 7237, 700-718, (2012). [31] C. Peikert: Limits on the hardness of lattice problems in ` nroms . Comput. Complexity, p 2 (17), 300-351, (2008). 27

28 [32] C. Perkert: An efficient and parallel Gaussian sampler for lattices . CRYPTO 2010, LNCS, vol. 6223, 80-97, (2010). [33] O. Regev: . J. On lattices, learning with errors, random linear codes, and cryptography ACM, 56 (6), 1-40, (2009). NTRUCCA: how to strengthen [34] R. Steinfeld, S. Ling, J. Pieprzyk, C. Tartary, H. Wang: . PKC 2012, LNCS, NTRUEncrypt to chosen-ciphertext security in the standard model vol. 7293, 353-371, (2012). [35] D. Stehl ́ e , R. Steinfeld: Making NTRU as secure as worst-case problems over ideal lattices . EUROCRYPT 2011, LNCS, vol. 6632, 27-47 (2011). [36] D. Stehl ́ , R. Steinfeld: Making NTRUEncrypt and NTRUSign as secure as worst-case e problems over ideal lattices . Crypto. ePrint Archive, 2013:004, (2013). [37] R. Vershynin: Introduction to the non-asymptotic analysis of random matrices . Available at http://www-personal.umich.edu/ romanv/papers/non-asymptotic-rmt- plain.pdf. [38] Y. Yu, G. W. Xu, X. Y. Wang: Provably Secure NTRU Instances over Prime Cyclotomic Rings . PKC 2017, LNCS, vol. 10174, 409-434, (2017). [39] Y. Yu, G. W. Xu, X. Y. Wang: Provably Secure NTRUEncrypt over More General Cyclotomic Rings . Crypto. ePrint Archive, 2017: 304, (2017). 28

Related documents

Position Classification Standard for Property Disposal Series, GS 1104

Position Classification Standard for Property Disposal Series, GS 1104

Property Disposal Series, GS-1104 TS-119 September 1992 Position Classification Standard for Property Disposal Series, GS-1104 Table of Contents ... 2 SERIES DEFINITION ... ... ... 2 EXCLUSIONS OCCUPA...

More info »
ACCESSORIES PL

ACCESSORIES PL

Accessories North America Price List – April 2019

More info »
HQ1

HQ1

Case: 17-3244 Document: 003113227172 Page: 1 Date Filed: 05/02/2019 PRECEDENTIAL UNITED STATES COURT OF APPEALS FOR THE THIRD CIRCUIT ______ 3244 - No. 17 ______ JENNIFER SWEDA; BENJAMIN A. WIGGINS; R...

More info »
ppacacon

ppacacon

111 TH C ONGRESS " ! LEGISLATIVE COUNSEL P RINT 111–1 2d Session COMPILATION OF PATIENT PROTECTION AND AFFORDABLE CARE ACT [As Amended Through May 1, 2010] INCLUDING P ATIENT P ROTECTION AND A FFORDAB...

More info »
2017 Without Dependents BAH Rates

2017 Without Dependents BAH Rates

2017 BAH Rates - WITHOUT DEPENDENTS O07 O06 W04 W05 O02E O03E W03 O02 O03 O04 O05 O01E O01 E07 E08 E09 W01 W02 E03 E05 E06 E04 E02 E01 MHA_NAME MHA 1155 KETCHIKAN, AK 1521 1527 1587 1659 1788 1530 163...

More info »
Compendium II: Compendium of Copyright Office Practices

Compendium II: Compendium of Copyright Office Practices

COMPENDIUM II L COMPENDIUM OF OFFICE PRACTICES COPYRIGHT the Copyright Under Which Law Became Fully Effective on January 1, 1978, Including Title of the United States 17 Code and Amendments Thereto CO...

More info »
Untitled

Untitled

Harmoniz ed vision 4 hedule of the United States (2019) Re Tariff Sc Annotated f poses ting Pur or Statistical Repor GN p .1 GENERAL R ATION ULES OF INTERPRET inciples: wing pr ollo y the f verned b i...

More info »
CityNT2019TentRoll 1

CityNT2019TentRoll 1

STATE OF NEW YORK 2 0 1 9 T E N T A T I V E A S S E S S M E N T R O L L PAGE 1 VALUATION DATE-JUL 01, 2018 COUNTY - Niagara T A X A B L E SECTION OF THE ROLL - 1 CITY - North Tonawanda TAX MAP NUMBER ...

More info »
The Post Trial Handbook: A Guide for Military Justice Practitioners

The Post Trial Handbook: A Guide for Military Justice Practitioners

2009 EDITION O F F I C E O F T H E C L E R K O F C O U RT THE POST-TRIAL HANDBOOK A Guide for Military Justice Practitioners OFFICE OF THE CLERK OF COURT 901 North Stuart Street ARLINGTON, VIRGINIA Ar...

More info »
OperatorHoursReport

OperatorHoursReport

John Bel Edwards Rebekah E. Gee MD, MPH SECRETARY GOVERNOR State of Louisiana Louisiana Department of Health Office of Public Health Certified Water and Wastewater Operators 2018 - 2019 Hours Hours li...

More info »
SAS/GRAPH 9.2 Reference, Second Edition

SAS/GRAPH 9.2 Reference, Second Edition

® SAS/GRAPH 9.2 Reference Second Edition TW12141_ColorTitlePage.indd 1 3/4/10 3:20:52 PM

More info »
u7112 connectplus directories 2019

u7112 connectplus directories 2019

UCare Connect + Medicare Provider and Pharmacy Directory Introduction This Provider and Pharmacy Directory includes information about the provider and pharmacy types in UCare Connect + Medicare and li...

More info »
U7112 UCARE CONNECT + MEDICARE PROVIDERDIR MAY 2019 DATA.sv

U7112 UCARE CONNECT + MEDICARE PROVIDERDIR MAY 2019 DATA.sv

UCare Connect + Medicare Provider and Pharmacy Directory Introduction This Provider and Pharmacy Directory includes information about the provider and pharmacy types in UCare Connect + Medicare and li...

More info »
LawReferenceBook2018

LawReferenceBook2018

California Contractors License Law & Reference Book 2018 Edition With Rules and Regulations Contractors State License Board State of California Edmund G. Brown, Jr., Governor

More info »
doj final opinion

doj final opinion

UNITED STAT ES DIS TRICT COURT IC F OR THE D ISTR T OF CO LU M BIA UNITED STAT F AMERICA, : ES O : : la in t if f, P 99 No. on cti l A vi Ci : 96 (GK) -24 : and : TOBACCO-F UND, : REE KIDS ACTION F : ...

More info »
NCDOT Current STIP

NCDOT Current STIP

May 2019 NCDOT Current STIP

More info »
C:\Users\aholmes4\AppData\Roaming\SoftQuad\XMetaL\7.0\gen\c\H5515 ~1.XML

C:\Users\aholmes4\AppData\Roaming\SoftQuad\XMetaL\7.0\gen\c\H5515 ~1.XML

H. R. 5515 One Hundred Fifteenth Congress of the United States of America AT THE SECOND SESSION Begun and held at the City of Washington on Wednesday, the third day of January, two thousand and eighte...

More info »
Vaginal Birth After Cesarean: New Insights. Evidence Report/Technology Assessment, No. 191

Vaginal Birth After Cesarean: New Insights. Evidence Report/Technology Assessment, No. 191

Evidence Report/Technology Assessment Number 191 Vaginal Birth After Cesarean: New Insights Prepared for: Agency for Healthcare Research and Quality U.S. Department of Health and Human Services 540 Ga...

More info »