# Cryptanalysis of Compact-LWE and Related Lightweight Public Key Encryption

Authors: Dianyan Xiao; Yang Yu
Journal: Security and Communication Networks
 (2018)

---

## Abstract

In the emerging Internet of Things (IoT), lightweight public key cryptography plays an essential role in security and privacy protection. With the approach of quantum computing era, it is important to design and evaluate lightweight quantum-resistant cryptographic algorithms applicable to IoT. LWE-based cryptography is a widely used and well-studied family of postquantum cryptographic constructions whose hardness is based on worst-case lattice problems. To make LWE friendly to resource-constrained IoT devices, a variant of LWE, named Compact-LWE, was proposed and used to design lightweight cryptographic schemes. In this paper, we study the so-called Compact-LWE problem and clarify that under certain parameter settings it can be solved in polynomial time. As a consequence, our result leads to a practical attack against an instantiated scheme based on Compact-LWE proposed by Liu et al. in 2017.


---

## Body

## 1. Introduction

The Internet is changing from a network of conventional computers to a network of smart objects, that is, “things,” including vehicles, electronics, implantable medical devices, and sensors. The trend of Internet of Things (IoT) makes the Internet more ubiquitous, but it simultaneously brings a series of challenges, such as monitoring [1], communication [2], and management [3]. Among all these challenges, security [4–6] is currently listed as a top concern. As the theoretical basis, cryptographic algorithms play a key role in achieving data confidentiality and integrity, authentication, and other security needs in IoT.Currently, RSA and ECC cryptosystems have been implemented efficiently on resource-constrained devices [7, 8], which provides desirable security for IoT applications. However, these public key schemes are based on integer factorization or discrete logarithms, which are fragile under quantum cryptanalysis. To defense quantum attacks, NIST has launched the postquantum cryptography standardization. Lattice-based cryptography is viewed as a very promising postquantum alternative to classical cryptography due to its strong security guarantee, great performance and powerful functionality. It is becoming increasingly important to design and evaluate practical schemes based on well-studied lattice problems.TheLearning With Errors (LWE) problem, introduced by Regev [9], is one of the most popular lattice problems for cryptographic applications [10–13]. An LWE instance consists of a random matrix A∈Zqm×n and a vector b=As+emod⁡q, where the secret s∈Zqn and the error e∈Zm are sampled from a certain distribution. The decision LWE problem is to distinguish the distribution of LWE instances from the uniform distribution over Zqm×n×Zqm, while the search version is to recover the secret s from LWE instances. In [9], the average-case LWE is proved as hard as certain worst-case lattice problems, which provides a solid theoretical grounding for LWE-based schemes.However, LWE-based schemes are usually not efficient in practice. It seems infeasible to apply regular LWE-based cryptographic constructions to IoT directly, due to the constrained computing environments of smart devices. Thus it is critical to refine existing algorithms or develop new LWE-based cryptographic schemes for security protection using limited resources. So far, there are mainly two optimization strategies: (1) introducing extra algebraic structures and (2) reducing the sizes of matrix or vector elements. Following the first one, some LWE variants, such as Ring-LWE [14] and Module-LWE [15], were developed and led to many practical schemes [16–18] and efficient implementations [19, 20]. Following the second strategy, some variants were proposed as well, including LWE with short secret or error [21–23] and LWE with compact matrix [24, 25]. Then, related cryptanalyses [26–29] provided concrete security estimations for the schemes based on these variants.A recent instantiation of LWE-based encryption scheme with particularly aggressive parameter was proposed by Liu et al. [25] and presented as an invited talk at ACISP 2017 conference. The scheme is based on the so-called Compact-LWE and designed especially for resource-constrained IoT devices. As shown by experimental results, the scheme indeed achieves an excellent performance on small IoT devices. Subsequently, Bootle and Tibouchi gave a cryptanalysis of this scheme [29] by recovering the nonce in the encryption process with the help of lattice embedding technique. They pointed out that the security level was much lower than [25] claimed.We took an insight into the Compact-LWE problem, an LWE variant with the randomA selected from a small range, and discovered that two q-ary lattices defined by A have reduced bases of special patterns. We proved that the Compact-LWE problem can be solved in polynomial time under certain parameters, which is applied to analyze two concrete lightweight public key schemes proposed in [24, 25], respectively. We failed to attack the scheme of [24] due to its moderate parameters and successfully recovered plaintexts with 100% probability and within a very short time for the encryption scheme in [25]. Compared with the attack against the scheme of [25] in [29], our attack follows a different method and can be used to analyze general cryptographic constructions based on this kind of LWE variant.The article is organized as follows. In Section2, we recall some notations and basic facts used in our discussion. In Section 3, we introduce Compact-LWE and present our analysis. We describe a concrete attack against related Compact-LWE-based schemes in Section 4 and conclude in Section 5.


## 2. Preliminaries

### 2.1. Notations

For any positive integerq, we identify Zq with the set {0,…,q-1}. We denote by xq the remainder of x divided by q in Zq and by xq the remainder in -q/2,…,q-1-q/2. Let ·,· and · be the Euclidean inner product and norm, respectively. The elements of Rm are viewed as column vectors. For any point t∈Rm and r>0, we denote by Bmt,r the m-dimensional ball of radius r centered at t.


### 2.2. Probability and Statistics

Letχ be a distribution over a discrete domain E. We write X↩χ to represent the random variable X that is sampled from the distribution χ. For a finite domain E, we denote by U(E) the uniform distribution over E.A functionf(n) isnegligible, if f(n)=o(n-c) for every fixed constant c. We generally denote by negl(n) as a negligible function with respect to n. We say that a probability isoverwhelming if it is 1-negl(n), and a probability isnonnegligible if it is ω(n-c) for some constant c.Definition 1.
Given a distributionχ over Qm, we say that χ is α,β-confidence with respect to λ, if Pr[X≥α]≤negl(λ) and Pr[X≤β]≥1/poly(λ) for X↩χ.The parameterα describes an overwhelming confidence interval for χ with respect to λ, while β describes a nonnegligible confidence interval.


### 2.3. Lattices

AlatticeL is a discrete additive subgroup of Rm and generated by a set of linearly independent vectors b1,…,bn, that is, L=∑i=1n‍xibi∣xi∈Zfor  anyi. We call B=b1,…,bn∈Rm×n abasis of L and write L as L(b1,…,bn) or L(B). The integer n is called therank of L. For any unimodular matrix U∈Zn×n, BU is also a basis of L. Thespan of L, denoted by span(L), is the linear space spanned by its basis. The first minimum of a lattice L is defined as λ1(L)≔minv∈L∖0v.We denote byB∗=(b1∗,…,bn∗) theGram-Schmidt orthogonalization of B where bi∗=bi-∑j=1i-1‍μi,jbj∗ and μi,j=bi,bj∗/bj∗,bj∗. Thevolume of L is defined as volL=∏i=1nbi∗ that is an invariant of L and independent of the choice of the basis.Thedual lattice of L is L∗≔{y∈span(L)∣〈x,y〉∈Z,∀x∈L}. If B is a basis of L, it is known that D=BBTB-T is a basis of L∗. Furthermore, we have the following relation between the Gram-Schmidt orthogonalization of a basis and its dual.Lemma 2.
Let(b1,…,bn) be an ordered basis of lattice L and d1,…,dn be its dual basis in reverse order (i.e., di,bj=δi,n+1-j where δi,j denotes Kronecker delta). Then di∗=bn+1-i∗/bn+1-i∗2 for i=1,…,n.Given a latticeL and a “reasonable” subset K of span(L),Gaussian heuristic says that the number of points in K∩L is approximately vol(K)/vol(L). From Gaussian heuristic, we would expect that λ1(L)≈vol(L)1/n·GH(n) where GH(n)=vol(Bn(0,1))-1/n≈n/2πe.Lattice reduction is a powerful tool for cryptanalysis. LLL, invented by Lenstra et al. [30], is the first polynomial time lattice reduction algorithm. We now recall this classical reduction. For a detailed introduction, we refer to [31].Definition 3 (LLL reduced basis).
A basisB=(b1,…,bn) is a δ-LLL reduced basis with δ∈(1/2,1) if the following conditions hold: (1)
Size Reduced:μi,j≤1/2 for 1≤j<i≤n.(2)
Lovász Condition:δbi∗≤bi+1∗+μi+1,ibi∗ for 1≤i<n.Then we immediately get the following property of LLL reduced bases.Lemma 4.
Let(b1,…,bn) be a δ-LLL reduced basis. For any 1≤j<i≤n, then (1)bi∗≥γj-ibj∗,where γ=1/δ2-1/4.


## 2.1. Notations

For any positive integerq, we identify Zq with the set {0,…,q-1}. We denote by xq the remainder of x divided by q in Zq and by xq the remainder in -q/2,…,q-1-q/2. Let ·,· and · be the Euclidean inner product and norm, respectively. The elements of Rm are viewed as column vectors. For any point t∈Rm and r>0, we denote by Bmt,r the m-dimensional ball of radius r centered at t.


## 2.2. Probability and Statistics

Letχ be a distribution over a discrete domain E. We write X↩χ to represent the random variable X that is sampled from the distribution χ. For a finite domain E, we denote by U(E) the uniform distribution over E.A functionf(n) isnegligible, if f(n)=o(n-c) for every fixed constant c. We generally denote by negl(n) as a negligible function with respect to n. We say that a probability isoverwhelming if it is 1-negl(n), and a probability isnonnegligible if it is ω(n-c) for some constant c.Definition 1.
Given a distributionχ over Qm, we say that χ is α,β-confidence with respect to λ, if Pr[X≥α]≤negl(λ) and Pr[X≤β]≥1/poly(λ) for X↩χ.The parameterα describes an overwhelming confidence interval for χ with respect to λ, while β describes a nonnegligible confidence interval.


## 2.3. Lattices

AlatticeL is a discrete additive subgroup of Rm and generated by a set of linearly independent vectors b1,…,bn, that is, L=∑i=1n‍xibi∣xi∈Zfor  anyi. We call B=b1,…,bn∈Rm×n abasis of L and write L as L(b1,…,bn) or L(B). The integer n is called therank of L. For any unimodular matrix U∈Zn×n, BU is also a basis of L. Thespan of L, denoted by span(L), is the linear space spanned by its basis. The first minimum of a lattice L is defined as λ1(L)≔minv∈L∖0v.We denote byB∗=(b1∗,…,bn∗) theGram-Schmidt orthogonalization of B where bi∗=bi-∑j=1i-1‍μi,jbj∗ and μi,j=bi,bj∗/bj∗,bj∗. Thevolume of L is defined as volL=∏i=1nbi∗ that is an invariant of L and independent of the choice of the basis.Thedual lattice of L is L∗≔{y∈span(L)∣〈x,y〉∈Z,∀x∈L}. If B is a basis of L, it is known that D=BBTB-T is a basis of L∗. Furthermore, we have the following relation between the Gram-Schmidt orthogonalization of a basis and its dual.Lemma 2.
Let(b1,…,bn) be an ordered basis of lattice L and d1,…,dn be its dual basis in reverse order (i.e., di,bj=δi,n+1-j where δi,j denotes Kronecker delta). Then di∗=bn+1-i∗/bn+1-i∗2 for i=1,…,n.Given a latticeL and a “reasonable” subset K of span(L),Gaussian heuristic says that the number of points in K∩L is approximately vol(K)/vol(L). From Gaussian heuristic, we would expect that λ1(L)≈vol(L)1/n·GH(n) where GH(n)=vol(Bn(0,1))-1/n≈n/2πe.Lattice reduction is a powerful tool for cryptanalysis. LLL, invented by Lenstra et al. [30], is the first polynomial time lattice reduction algorithm. We now recall this classical reduction. For a detailed introduction, we refer to [31].Definition 3 (LLL reduced basis).
A basisB=(b1,…,bn) is a δ-LLL reduced basis with δ∈(1/2,1) if the following conditions hold: (1)
Size Reduced:μi,j≤1/2 for 1≤j<i≤n.(2)
Lovász Condition:δbi∗≤bi+1∗+μi+1,ibi∗ for 1≤i<n.Then we immediately get the following property of LLL reduced bases.Lemma 4.
Let(b1,…,bn) be a δ-LLL reduced basis. For any 1≤j<i≤n, then (1)bi∗≥γj-ibj∗,where γ=1/δ2-1/4.


## 3. Compact-LWE and Its Weak Instances

In this section, we will introduce an LWE variant named Compact-LWE and report on an attack against certain Compact-LWE instances. A formal definition of Compact-LWE is given as follows.Definition 5.
Letq,m,n,b be positive integers and χ be a distribution over Zm. Given s↩U(Zqn), the Compact-LWEq,m,n,b,χ problem is to recover s from (A,b=As+emod⁡q) where A↩U(Zbm×n) and e↩χ.Compared with classical LWE, the sizes of elements ofA, namely b, can be less than the modulus q. Thanks to this modification, Compact-LWE-based schemes are of smaller public key sizes and better efficiency than original LWE-based schemes. Thus Compact-LWE seems friendly to lightweight cryptography and constrained devices.


### 3.1. Structures ofq-Ary Lattices in Compact-LWE

We introduce twom-dimensional q-ary lattices which are widely used in the cryptanalysis of LWE. The first lattice, denoted by LqA, is generated by the columns of A and q·Im and defined as (2)LqA≔x∈Zm∣x=Aymod⁡qforsomey∈Zn,The second lattice Lq⊥A is formed by all integer vectors “orthogonal” (modulo q) to the columns of A, which is (3)Lq⊥A≔x∈Zm∣ATx=0mod⁡q.As shown in [10], these two lattices are duals scaled by a factor: (4)Lq⊥A=q·LqA∗.By running LLL algorithm with inputA∣q·Im, one can obtain a basis of Lq(A). For A in the compact setting, the LLL reduced basis is of a special structure.Lemma 6.
LetA∈Zbm×n where m≥n+2πe and b≤qm-n/m/m. Let B=b1,…,bm be the basis of Lq(A) obtained by running LLL with parameter δ on A∣q·Im. Under Gaussian heuristic, then, for γ=1/δ2-1/4, (1)
Lb1,…,bn=L(A) and bi∗≤bm  for 1≤i≤n;(2)
bi∗>qγn-i+1(bm)-n/m-n for n+1≤i≤m.Proof.
Letϕ:Zm/Lq⊥(A)→Zqn be the homomorphism mapping v+Lq⊥A to ATvmod⁡q. It can be verified that ϕ is injective, then we have (5)volLq⊥A≤qn.Together with (4), it follows that (6)volLqA≥qm-n.
LetπA· denote the projection to the orthogonal complement of spanA. Considering the projected lattice L′ generated by πA(q·Im), the dimension of L′ is m-n. Combined with (6), we have (7)volL′≥volLqAvolLA≥qm-nvolLA.Since volLA=∏i=1n‍ai∗≤∏i=1n‍ai≤bmn, it follows that (8)volL′≥qm-nbmn.By Gaussian heuristic, we have that (9)λ1L′≈m-n2πe·volL′1/m-n≥q·bm-n/m-n.A straightforward computation leads to that λ1L′≥bm≥maxi=1nai∗. It is known that the maximum of the Gram-Schmidt norms would never increase in LLL algorithm. Thus, Lovász condition always holds for the nth and n+1th vectors during LLL, which means that these two vectors would never be swapped. In other words, running LLL on A∣q·Im is equivalent to running LLL on A and πAq·Im, respectively. Consequently, we have Lb1,…,bn=LA and bi∗≤maxi=1nai∗≤bm for 1≤i≤n.
For the second inequality, Lemma4 yields that (10)bn+i∗≥bn+1∗γ1-i>qγ1-ibm-n/m-n,because bn+1∗≥λ1L′. We now complete the proof.Remark 7.
Experimental results coincide with Lemma6. Under parameter settings (q,m,n)=220,300,120, we generated 20 instances for each b ranging from 2 to 218. Figure 1 illustrates the average profile of B, where the first nbi∗’s are relatively short when b is small. We notice that the slope of log2bi∗i=n+1m is less than the theoretical bound log2γ≈0.2172, which can be explained by the better performance of LLL in practice than the theoretical prediction. Figure 2 shows the gap between bn+1∗ and bn∗, which is narrowing as b increases. It is worth noting that when b<qm/m-n/m (the bound in Lemma 6 marked by the dashed line), the gap is quite significant.Figure 1
Experimental measure oflog2bi∗i=1m for different b.Figure 2
Experimental measure of the gap betweenlog2bn∗ and log2bn+1∗.Lemma 8.
Letm≥n+2πe and b≤qm-n/m/m. Let A∈Zbm×n and δ∈(1/2,1). There exists a basis of Lq⊥(A), denoted by D=d1,…,dm, satisfying the following conditions under Gaussian heuristic: (1)
L(d1,…,dm-n)=x∈Zm∣xTA=0,(2)
di≤i+3/4·γm-n(bm)n/m-n for 1≤i≤m-n,(3)
di≥n/2πeq/bm for m-n+1≤i≤m,
whereγ=1/δ2-1/4. This basis can be obtained in polynomial time.Proof.
LetB=B1∣B2 be the LLL reduced basis of Lq(A) defined in Lemma 6 where L(B1)=L(A). Let U be a matrix such that UTB=qIm. Then, from (4), U is a basis of Lq⊥(A). Let U=U1∣U2=um,…,u1 where U1∈Zm×n.
LetL⊥(A)=x∈Zm∣xTA=0. We claim that L(U2)=L⊥(A). It is easy to observe that L⊥(A)=L⊥(B1) where L⊥(B1)=x∈Zm∣xTB1=0. On one hand, we have L(U2)⊆L⊥(B1) since U2TB1=0. On the other hand, for arbitrary v∈L⊥(B1)⊆Lq⊥(A), there exists a unique vector pair (z1,z2) such that v=U1z1+U2z2. Since U1TB1=qIn, we have vTB1=qz1T=0 and then v∈L(U2). Therefore, it holds that L(U2)=L⊥(A).
We run size reduction algorithm on(u1,…,um) (vectors of U in reverse order) and obtain a new basis of Lq⊥(A), denoted by D=(d1,…,dm). Size reduction can be done within polynomial time; thus it suffices to prove the last two conditions hold for D. From Lemmas 2 and 6, we have that, for i=1,…,m-n, (11)di∗=ui∗=qbm+1-i∗≤γm-n-ibmn/m-n,and then (12)di≤di∗2+14∑j=1i-1dj∗2≤i+34γm-nbmn/m-n.
LetL′′=Lπm-ndm-n+1,…,πm-ndm where πm-n· is the projection to the orthogonal complement of span(d1,…,dm-n). Observing that volLqAvolLq⊥A=qm and di∗=q/bm+1-i∗ for i≤m-n, together with Lemma 6, we have (13)volL′′=volLq⊥A∏i=1m-ndi∗=qn∏i=1nbi∗≥qnbmn.On the basis of Gaussian heuristic, we conclude that, for m-n+1≤i≤m, (14)di≥πm-ndi≥λ1L′′≥n2πeqbm.We now complete the proof.Remark 9.
We ran experiments under parametersq,m,n=220,300,120 and tested 20 instances for each b ranging from 2 to 218. Figure 3 provides a geometric intuition of D. There also exists a large gap between dm-n and dm-n+1 when b is small. As illustrated in Figure 4, the gap between dm-n and dm-n+1 is shrinking as b grows. However, when b<qm-n/m/m (marked by the dashed line), the length of dm-n is far less than q.Figure 3
Experimental measure oflog2dii=1m for different b.Figure 4
Experimental measure of the gap betweenlog2dm-n and log2dm-n+1.


### 3.2. Attack Against Weak Compact-LWE Instances

Figure1 illustrates a staircase-shaped profile of the basis of Lq(A). Exploiting this feature, we can prove that it is possible to efficiently recover a candidate error whose norm is close to that of the original error for certain parameters. The following lemma will be used in the later discussion.Lemma 10.
LetL⊆Rm be a lattice of rank n and B be a basis of L. Let t∈Rm and dist⁡(t,L)=minv∈Lt-v. If dist⁡(t,L)≤r<1/2mini=1nbi∗, then there exists a unique vector in Bt,r∩L.Proof.
We denote byv=∑i=1nvibi the vector output by Babai’s nearest plane algorithm [32] on the lattice L and target vector t. Assume, by contradiction, that v′≠v is another vector in B(t,r)∩L and v′=∑i=1nvi′bi. Let k be the largest index such that vk≠vk′. According to the process of Babai’s algorithm, we conclude that (15)v′-t≥12bk∗>r,which implies a contradiction.Next we demonstrate a class of provably weak instances of Compact-LWE and also an attack aiming at them.Theorem 11.
Letq,m,n,b,r be positive integers satisfying b≤qm-n/m/m and mn/2b<r≤q/2γn-m+1bm-n/m-n where γ=1/δ2-1/4 for δ∈1/2,1 and a constant c>0. Let χ be a r,1/24r2-mnb2-confidence distribution. Under Gaussian heuristic, there exists a probabilistic polynomial time algorithm solving Compact-LWEq,m,n,b,χ.Proof.
Given a random sampleA,b=As+emod⁡q, we can obtain a basis of Lq(A), denoted by B, by applying LLL algorithm with parameter δ on A∣qIm. Exploiting Babai’s algorithm on Lq(A) and target vector b, we get a pair of solution s′,e′. We are to prove that s′,e′ is legal for Compact-LWE, that is, e′≤r, with nonnegligible probability.
From Lemma6, we get that r<1/2bi∗ for n+1≤i≤m. We denote by πn(·) the projection to the orthogonal complement of spanb1,…,bn. Let L′=πnL and b′=πn(b). Lemma 10 shows that there exists a unique vector in Bb′,r∩L′, namely, πn(e)=πne′. Then we have (16)e′2=e′-πne′2+πne′2≤14∑i=1nbi∗2+e2≤mnb24+e2.Since χ is r,1/24r2-mnb2-confidence, it implies that e≤1/24r2-mnb2 with nonnegligible probability. Thus the probability of e′≤r is nonnegligible.Remark 12.
In such weak instances, it can be verified that(17)q>n·γm-n-1bmm/m-n,and thus parameters are overstretched [33, 34]. The inequalities given in Lemma 6 follow the worst-case result of LLL, but LLL behaves much better in practice. Hence our attack may apply to more Compact-LWE instances. Moreover, note that, for usual LWE distribution χ such as discrete Gaussian, it is easy to set α,β such that χ is α,β-confidence.


## 3.1. Structures ofq-Ary Lattices in Compact-LWE

We introduce twom-dimensional q-ary lattices which are widely used in the cryptanalysis of LWE. The first lattice, denoted by LqA, is generated by the columns of A and q·Im and defined as (2)LqA≔x∈Zm∣x=Aymod⁡qforsomey∈Zn,The second lattice Lq⊥A is formed by all integer vectors “orthogonal” (modulo q) to the columns of A, which is (3)Lq⊥A≔x∈Zm∣ATx=0mod⁡q.As shown in [10], these two lattices are duals scaled by a factor: (4)Lq⊥A=q·LqA∗.By running LLL algorithm with inputA∣q·Im, one can obtain a basis of Lq(A). For A in the compact setting, the LLL reduced basis is of a special structure.Lemma 6.
LetA∈Zbm×n where m≥n+2πe and b≤qm-n/m/m. Let B=b1,…,bm be the basis of Lq(A) obtained by running LLL with parameter δ on A∣q·Im. Under Gaussian heuristic, then, for γ=1/δ2-1/4, (1)
Lb1,…,bn=L(A) and bi∗≤bm  for 1≤i≤n;(2)
bi∗>qγn-i+1(bm)-n/m-n for n+1≤i≤m.Proof.
Letϕ:Zm/Lq⊥(A)→Zqn be the homomorphism mapping v+Lq⊥A to ATvmod⁡q. It can be verified that ϕ is injective, then we have (5)volLq⊥A≤qn.Together with (4), it follows that (6)volLqA≥qm-n.
LetπA· denote the projection to the orthogonal complement of spanA. Considering the projected lattice L′ generated by πA(q·Im), the dimension of L′ is m-n. Combined with (6), we have (7)volL′≥volLqAvolLA≥qm-nvolLA.Since volLA=∏i=1n‍ai∗≤∏i=1n‍ai≤bmn, it follows that (8)volL′≥qm-nbmn.By Gaussian heuristic, we have that (9)λ1L′≈m-n2πe·volL′1/m-n≥q·bm-n/m-n.A straightforward computation leads to that λ1L′≥bm≥maxi=1nai∗. It is known that the maximum of the Gram-Schmidt norms would never increase in LLL algorithm. Thus, Lovász condition always holds for the nth and n+1th vectors during LLL, which means that these two vectors would never be swapped. In other words, running LLL on A∣q·Im is equivalent to running LLL on A and πAq·Im, respectively. Consequently, we have Lb1,…,bn=LA and bi∗≤maxi=1nai∗≤bm for 1≤i≤n.
For the second inequality, Lemma4 yields that (10)bn+i∗≥bn+1∗γ1-i>qγ1-ibm-n/m-n,because bn+1∗≥λ1L′. We now complete the proof.Remark 7.
Experimental results coincide with Lemma6. Under parameter settings (q,m,n)=220,300,120, we generated 20 instances for each b ranging from 2 to 218. Figure 1 illustrates the average profile of B, where the first nbi∗’s are relatively short when b is small. We notice that the slope of log2bi∗i=n+1m is less than the theoretical bound log2γ≈0.2172, which can be explained by the better performance of LLL in practice than the theoretical prediction. Figure 2 shows the gap between bn+1∗ and bn∗, which is narrowing as b increases. It is worth noting that when b<qm/m-n/m (the bound in Lemma 6 marked by the dashed line), the gap is quite significant.Figure 1
Experimental measure oflog2bi∗i=1m for different b.Figure 2
Experimental measure of the gap betweenlog2bn∗ and log2bn+1∗.Lemma 8.
Letm≥n+2πe and b≤qm-n/m/m. Let A∈Zbm×n and δ∈(1/2,1). There exists a basis of Lq⊥(A), denoted by D=d1,…,dm, satisfying the following conditions under Gaussian heuristic: (1)
L(d1,…,dm-n)=x∈Zm∣xTA=0,(2)
di≤i+3/4·γm-n(bm)n/m-n for 1≤i≤m-n,(3)
di≥n/2πeq/bm for m-n+1≤i≤m,
whereγ=1/δ2-1/4. This basis can be obtained in polynomial time.Proof.
LetB=B1∣B2 be the LLL reduced basis of Lq(A) defined in Lemma 6 where L(B1)=L(A). Let U be a matrix such that UTB=qIm. Then, from (4), U is a basis of Lq⊥(A). Let U=U1∣U2=um,…,u1 where U1∈Zm×n.
LetL⊥(A)=x∈Zm∣xTA=0. We claim that L(U2)=L⊥(A). It is easy to observe that L⊥(A)=L⊥(B1) where L⊥(B1)=x∈Zm∣xTB1=0. On one hand, we have L(U2)⊆L⊥(B1) since U2TB1=0. On the other hand, for arbitrary v∈L⊥(B1)⊆Lq⊥(A), there exists a unique vector pair (z1,z2) such that v=U1z1+U2z2. Since U1TB1=qIn, we have vTB1=qz1T=0 and then v∈L(U2). Therefore, it holds that L(U2)=L⊥(A).
We run size reduction algorithm on(u1,…,um) (vectors of U in reverse order) and obtain a new basis of Lq⊥(A), denoted by D=(d1,…,dm). Size reduction can be done within polynomial time; thus it suffices to prove the last two conditions hold for D. From Lemmas 2 and 6, we have that, for i=1,…,m-n, (11)di∗=ui∗=qbm+1-i∗≤γm-n-ibmn/m-n,and then (12)di≤di∗2+14∑j=1i-1dj∗2≤i+34γm-nbmn/m-n.
LetL′′=Lπm-ndm-n+1,…,πm-ndm where πm-n· is the projection to the orthogonal complement of span(d1,…,dm-n). Observing that volLqAvolLq⊥A=qm and di∗=q/bm+1-i∗ for i≤m-n, together with Lemma 6, we have (13)volL′′=volLq⊥A∏i=1m-ndi∗=qn∏i=1nbi∗≥qnbmn.On the basis of Gaussian heuristic, we conclude that, for m-n+1≤i≤m, (14)di≥πm-ndi≥λ1L′′≥n2πeqbm.We now complete the proof.Remark 9.
We ran experiments under parametersq,m,n=220,300,120 and tested 20 instances for each b ranging from 2 to 218. Figure 3 provides a geometric intuition of D. There also exists a large gap between dm-n and dm-n+1 when b is small. As illustrated in Figure 4, the gap between dm-n and dm-n+1 is shrinking as b grows. However, when b<qm-n/m/m (marked by the dashed line), the length of dm-n is far less than q.Figure 3
Experimental measure oflog2dii=1m for different b.Figure 4
Experimental measure of the gap betweenlog2dm-n and log2dm-n+1.


## 3.2. Attack Against Weak Compact-LWE Instances

Figure1 illustrates a staircase-shaped profile of the basis of Lq(A). Exploiting this feature, we can prove that it is possible to efficiently recover a candidate error whose norm is close to that of the original error for certain parameters. The following lemma will be used in the later discussion.Lemma 10.
LetL⊆Rm be a lattice of rank n and B be a basis of L. Let t∈Rm and dist⁡(t,L)=minv∈Lt-v. If dist⁡(t,L)≤r<1/2mini=1nbi∗, then there exists a unique vector in Bt,r∩L.Proof.
We denote byv=∑i=1nvibi the vector output by Babai’s nearest plane algorithm [32] on the lattice L and target vector t. Assume, by contradiction, that v′≠v is another vector in B(t,r)∩L and v′=∑i=1nvi′bi. Let k be the largest index such that vk≠vk′. According to the process of Babai’s algorithm, we conclude that (15)v′-t≥12bk∗>r,which implies a contradiction.Next we demonstrate a class of provably weak instances of Compact-LWE and also an attack aiming at them.Theorem 11.
Letq,m,n,b,r be positive integers satisfying b≤qm-n/m/m and mn/2b<r≤q/2γn-m+1bm-n/m-n where γ=1/δ2-1/4 for δ∈1/2,1 and a constant c>0. Let χ be a r,1/24r2-mnb2-confidence distribution. Under Gaussian heuristic, there exists a probabilistic polynomial time algorithm solving Compact-LWEq,m,n,b,χ.Proof.
Given a random sampleA,b=As+emod⁡q, we can obtain a basis of Lq(A), denoted by B, by applying LLL algorithm with parameter δ on A∣qIm. Exploiting Babai’s algorithm on Lq(A) and target vector b, we get a pair of solution s′,e′. We are to prove that s′,e′ is legal for Compact-LWE, that is, e′≤r, with nonnegligible probability.
From Lemma6, we get that r<1/2bi∗ for n+1≤i≤m. We denote by πn(·) the projection to the orthogonal complement of spanb1,…,bn. Let L′=πnL and b′=πn(b). Lemma 10 shows that there exists a unique vector in Bb′,r∩L′, namely, πn(e)=πne′. Then we have (16)e′2=e′-πne′2+πne′2≤14∑i=1nbi∗2+e2≤mnb24+e2.Since χ is r,1/24r2-mnb2-confidence, it implies that e≤1/24r2-mnb2 with nonnegligible probability. Thus the probability of e′≤r is nonnegligible.Remark 12.
In such weak instances, it can be verified that(17)q>n·γm-n-1bmm/m-n,and thus parameters are overstretched [33, 34]. The inequalities given in Lemma 6 follow the worst-case result of LLL, but LLL behaves much better in practice. Hence our attack may apply to more Compact-LWE instances. Moreover, note that, for usual LWE distribution χ such as discrete Gaussian, it is easy to set α,β such that χ is α,β-confidence.


## 4. Attack against Compact-LWE-Based Schemes

In this section, our analysis of Section3 is applied to attack concrete Compact-LWE-based lightweight encryption schemes. We successfully recover the plaintexts in IoT-oriented public key encryption proposed by Liu et al. in [25] following a totally different way with [29]. However, we fail to give an effective cryptanalysis of the binary LWE-based lightweight encryption in [24].


### 4.1. Liu et al.’s Compact-LWE-Based Scheme

Firstly, we briefly recall the public key encryption in [25]. The scheme is specified by a tuple of public parameters (q,n,m,t,w,b) satisfying (18)n+1<m<n2,2log2⁡b<n<b,2blog2⁡b+2·b<q.We list below three main algorithms: key generation Gen, encryption Enc(·), and decryption Dec(·). (i)
Gen: sample s↩U(Zqn), and choose sk,r,p from Zq satisfying (19)t≤p,b<r,skt-1+wrp<q,and sk,p,q are pairwise coprime. Sample A↩U(Zbm×n) and e↩U(Zrm). Let skq-1∈Zq such that sk·skq-1=1mod⁡q. Output SK=(s,sk,r,p) as the secret key and PK=(A,pk=As-skq-1·p·emod⁡q) as the public key.(ii)
Enc(v∈Zt,PK): uniformly and independently sample i1,…,iw↩U(Zm), and calculate c′=∑j=1w‍aij,pkijmod⁡q where (ai,pki) is the ith row of PK. Let c′=(a,pk), output c=(a,v-pkmod⁡q) as the ciphertext.(iii)
Dec(c=(a,x),SK): calculate c=a,s+xmod⁡q and then calculate skv=sk·cmod⁡q. Let skp-1 be the multiplicative inverse of sk modulo p. Output the plaintext v=skp-1·skvp.In [25], the authors also proposed concrete parameters to instantiate the scheme. The parameters are listed as follows:(i)
Public parameters:(q,n,m,t,w,b)=(232,13,74,216,86,16)(ii)
Secret parameters:(sk,p,r)=2x+1,t+2y+1,≤q-1-sk·t-1/w·p where (x,y)∈[0,50]×[0,500] or [0,500]×[0,50].


### 4.2. Attack against Liu et al.’s Scheme

According to the average profile of bases shown in Lemmas6 and 8 under the parameters (q,m,n,b)=(232,74,13,16) (see Figures 5 and 6) as suggested in [25], it seems that Liu et al.’s scheme is fragile. We propose a new attack against Liu et al.’s scheme with the help of our analysis towards Compact-LWE in Section 3.Figure 5
Experimental measure oflog2bi∗i=1m.Figure 6
Experimental measure oflog2dii=1m.Our attack consists of two steps:guessing the mask coefficient(sk,p) andrecovering the plaintext. In the first step, one can almost determine the pair (sk,p) (sometimes together with several possible candidate pairs) by enumerating and checking. In the second step, combined with (sk,p), one can calculate a pair of legal solution s′,e′ to the Compact-LWE problem and recover the plaintext as well. Now we are to show the details of our attack.Step 1 (guessing the mask coefficientsk,p).
Firstly, we prove that it is possible to recover efficiently the secret parameterssk and p only from the public key PK=(A,pk).
LetD=(d1,…,dn) be a basis of Lq⊥(A) as described in Lemma 4 with δ=0.99. Let pq-1∈Z such that pq-1·p=1mod⁡q; then we have that (20)sk·pq-1·di,pk=-di,emod⁡q.Since e≤rm≤q-1-sk·t-1/w·pm and di is also small when 1≤i≤m-n, a routine computation yields that di,e≤di·e<q/2 under the parameter setting suggested in [25]. Then it holds that (21)sk·pq-1·di,pkq=di,e≤q-1-sk·t-1w·pm·di,for i=1,…,m-n. We try all possible pairs sk,p∈2x+1∣x∈0,50∩Z×t+2y+1∣y∈[0,500]∩Z and check inequality (21) for d1,…,dm-n, respectively; then (sk,p) is viewed as a candidate when it holds for all i=1,…,m-n.
Experiments indicate that this step can indeed determine the unique correct(sk,p) at most times, and output a few candidates (including the correct pair) of the form (λ·sk,p) for small factor λ at other times. Therefore, by guessing sk and p, we can actually remove the secret scaling factor and transform PK into a standard Compact-LWE sample.Step 2 (recovering the plaintext).
After the previous step, we obtain one or more(sk,p) pairs. Next, we are to show how to recover the plaintext combined with the ciphertext.
LetB=(b1,…,bm) be the basis of Lq(A) described in Lemma 6. Given a candidate pair of the mask coefficient sk′,p′=(λ·sk,p) where λ is small, let pk′=sk′·pq-1·pkmod⁡q. Running Babai’s algorithm on Lq(A) and target vector pk′, we obtain v′∈Lq(A) and let e′=v′-pk′. We observe that the distance from pk′ to Lq(A) is at most λ·e, and λ·e≤λ·rm<1/2bi∗ for n+1≤i≤m. Following a similar argument of (16) in Theorem 11, we know that (22)e′2≤λ·e2+n4max1≤i≤nbi∗2≤λ2r2+n4b2m.Let s′∈Zqm such that v′=sk′·pq-1As′mod⁡q, then pk=As′-skq′-1·p′·e′mod⁡q where skq′-1·skq′=1mod⁡q. Exploiting the substitute secret key sk′,p′,s′,e′, we can decrypt the ciphertext c=(a,x) as follows: (1)
Calculatec′=a,s′+xq.(2)
Calculateskv′=sk′·c′q.(3)
Returnv′=skp′-1·skv′p where skp′-1·sk′=1mod⁡p.We now explain why the ciphertext can be decrypted correctly by above algorithm. It can be checked thatsk′·c′=sk′·v+p′∑j=1weij′mod⁡q. Noticing that e′ is well-bounded and some coordinates ei′ of e′ could be negative, we may assert that sk′·v+p′∑j=1weij′∈-q/2,q/2 with a high probability. Thus the term sk′·v+p′∑j=1weij′ can be recovered (as skv′) correctly, which implies that v′ is the plaintext.Experiments show that the plaintext can indeed be recovered, even ifsk′,p′=(λ·sk,p) for some λ≠1. When λ is large, the norm of e′ may exceed the upper bound rm, which implies that (sk′,p′) is a wrong guess. Therefore, we may eliminate some wrong guesses of sk′,p′ further in this step. Moreover, one may also try more middle terms such as skv′=sk′·c′q,sk′·c′q±q during the “decryption” to ensure that the correct value of sk′·v+p′∑j=1weij′ is not missed. However, from our experimental results, we observe that trying only one skv′=sk′·c′q is enough to recover the plaintext in practice.Experimental Results. We implemented our attack using the NTL library [35]. All experiments were run on a single core of a 3.40 GHz Core i7-4930K PC.We follow the parameter setting suggested in [25]: the public parameters (q,n,m,t,w,b)=(232,13,74,216,86,16) and the secret parameters (sk,p)=(2x+1,t+2y+1). We denote the cases (x,y)∈[0,50]×[0,500] and [0,500]×[0,50] by ParaA and ParaB, respectively. For ParaA and ParaB, we respectively generated 100 random instances and calculated the ciphertexts of 100 random messages for each instance. Then we ran the attack on these 10000 ciphertexts. Experimental results are given in Table 1.Table 1
Experimental results.
Parameter Time for Step1 Time for Step2 Time for attack Determining uniquesk,p Success rate ParaA 0.61 s 1.94 s 2.55 s 67% 100% ParaB 0.60 s 1.86 s 2.46 s 71% 100%As mentioned before, we may obtain severalsk′,p′ pairs in Step 1. In fact, it suffices to take use of the pair with the minimal sk′ to recover the plaintext. This observation leads to an optimization of the attack: one may search sk′,p′ in increasing (dictionary) order and move to Step 2 once a candidate is found. Experimental results for optimized attack are given in Table 2.Table 2
Experimental results for optimized attack.
Parameter Time for Step1 Time for Step2 Time for attack Success rate ParaA 0.57 s 1.14 s 1.71 s 100% ParaB 0.57 s 1.14 s 1.71 s 100%Comparison with Bootle and Tibouchi’s Attack. We note that Bootle and Tibouchi also proposed a practical attack [29] against Liu et al.’s encryption scheme. They deployed the technique of embedding lattices to compute the nonce sequence i1,…,iw in encryption processEnc(·), while we start from a different angle and recover a substitutable tuple of private keys sk′,p′,s′,e′. We hold the view that the insecurity of Liu et al.’s scheme is not only a result of the small value of n as claimed in [29], but also the overstretched magnitude relation between the modulus q and parameters b, m, and n, which is clarified in Theorem 11.


### 4.3. Attack against Galbraith’s Scheme

In [24], Galbraith proposed a class of LWE-based encryption for constrained devices with more compact parameters; that is, the public matrix A is binary. We tried to attack Galbraith’s scheme exploiting short vectors of Lq⊥(A) as described before, but it was ineffective even for the parameters totally broken in [27]. That is because the modulus q in Galbraith’s scheme is not so overstretched. However, the binary public matrix and encryption nonce may still be problematic as suggested in [27].


## 4.1. Liu et al.’s Compact-LWE-Based Scheme

Firstly, we briefly recall the public key encryption in [25]. The scheme is specified by a tuple of public parameters (q,n,m,t,w,b) satisfying (18)n+1<m<n2,2log2⁡b<n<b,2blog2⁡b+2·b<q.We list below three main algorithms: key generation Gen, encryption Enc(·), and decryption Dec(·). (i)
Gen: sample s↩U(Zqn), and choose sk,r,p from Zq satisfying (19)t≤p,b<r,skt-1+wrp<q,and sk,p,q are pairwise coprime. Sample A↩U(Zbm×n) and e↩U(Zrm). Let skq-1∈Zq such that sk·skq-1=1mod⁡q. Output SK=(s,sk,r,p) as the secret key and PK=(A,pk=As-skq-1·p·emod⁡q) as the public key.(ii)
Enc(v∈Zt,PK): uniformly and independently sample i1,…,iw↩U(Zm), and calculate c′=∑j=1w‍aij,pkijmod⁡q where (ai,pki) is the ith row of PK. Let c′=(a,pk), output c=(a,v-pkmod⁡q) as the ciphertext.(iii)
Dec(c=(a,x),SK): calculate c=a,s+xmod⁡q and then calculate skv=sk·cmod⁡q. Let skp-1 be the multiplicative inverse of sk modulo p. Output the plaintext v=skp-1·skvp.In [25], the authors also proposed concrete parameters to instantiate the scheme. The parameters are listed as follows:(i)
Public parameters:(q,n,m,t,w,b)=(232,13,74,216,86,16)(ii)
Secret parameters:(sk,p,r)=2x+1,t+2y+1,≤q-1-sk·t-1/w·p where (x,y)∈[0,50]×[0,500] or [0,500]×[0,50].


## 4.2. Attack against Liu et al.’s Scheme

According to the average profile of bases shown in Lemmas6 and 8 under the parameters (q,m,n,b)=(232,74,13,16) (see Figures 5 and 6) as suggested in [25], it seems that Liu et al.’s scheme is fragile. We propose a new attack against Liu et al.’s scheme with the help of our analysis towards Compact-LWE in Section 3.Figure 5
Experimental measure oflog2bi∗i=1m.Figure 6
Experimental measure oflog2dii=1m.Our attack consists of two steps:guessing the mask coefficient(sk,p) andrecovering the plaintext. In the first step, one can almost determine the pair (sk,p) (sometimes together with several possible candidate pairs) by enumerating and checking. In the second step, combined with (sk,p), one can calculate a pair of legal solution s′,e′ to the Compact-LWE problem and recover the plaintext as well. Now we are to show the details of our attack.Step 1 (guessing the mask coefficientsk,p).
Firstly, we prove that it is possible to recover efficiently the secret parameterssk and p only from the public key PK=(A,pk).
LetD=(d1,…,dn) be a basis of Lq⊥(A) as described in Lemma 4 with δ=0.99. Let pq-1∈Z such that pq-1·p=1mod⁡q; then we have that (20)sk·pq-1·di,pk=-di,emod⁡q.Since e≤rm≤q-1-sk·t-1/w·pm and di is also small when 1≤i≤m-n, a routine computation yields that di,e≤di·e<q/2 under the parameter setting suggested in [25]. Then it holds that (21)sk·pq-1·di,pkq=di,e≤q-1-sk·t-1w·pm·di,for i=1,…,m-n. We try all possible pairs sk,p∈2x+1∣x∈0,50∩Z×t+2y+1∣y∈[0,500]∩Z and check inequality (21) for d1,…,dm-n, respectively; then (sk,p) is viewed as a candidate when it holds for all i=1,…,m-n.
Experiments indicate that this step can indeed determine the unique correct(sk,p) at most times, and output a few candidates (including the correct pair) of the form (λ·sk,p) for small factor λ at other times. Therefore, by guessing sk and p, we can actually remove the secret scaling factor and transform PK into a standard Compact-LWE sample.Step 2 (recovering the plaintext).
After the previous step, we obtain one or more(sk,p) pairs. Next, we are to show how to recover the plaintext combined with the ciphertext.
LetB=(b1,…,bm) be the basis of Lq(A) described in Lemma 6. Given a candidate pair of the mask coefficient sk′,p′=(λ·sk,p) where λ is small, let pk′=sk′·pq-1·pkmod⁡q. Running Babai’s algorithm on Lq(A) and target vector pk′, we obtain v′∈Lq(A) and let e′=v′-pk′. We observe that the distance from pk′ to Lq(A) is at most λ·e, and λ·e≤λ·rm<1/2bi∗ for n+1≤i≤m. Following a similar argument of (16) in Theorem 11, we know that (22)e′2≤λ·e2+n4max1≤i≤nbi∗2≤λ2r2+n4b2m.Let s′∈Zqm such that v′=sk′·pq-1As′mod⁡q, then pk=As′-skq′-1·p′·e′mod⁡q where skq′-1·skq′=1mod⁡q. Exploiting the substitute secret key sk′,p′,s′,e′, we can decrypt the ciphertext c=(a,x) as follows: (1)
Calculatec′=a,s′+xq.(2)
Calculateskv′=sk′·c′q.(3)
Returnv′=skp′-1·skv′p where skp′-1·sk′=1mod⁡p.We now explain why the ciphertext can be decrypted correctly by above algorithm. It can be checked thatsk′·c′=sk′·v+p′∑j=1weij′mod⁡q. Noticing that e′ is well-bounded and some coordinates ei′ of e′ could be negative, we may assert that sk′·v+p′∑j=1weij′∈-q/2,q/2 with a high probability. Thus the term sk′·v+p′∑j=1weij′ can be recovered (as skv′) correctly, which implies that v′ is the plaintext.Experiments show that the plaintext can indeed be recovered, even ifsk′,p′=(λ·sk,p) for some λ≠1. When λ is large, the norm of e′ may exceed the upper bound rm, which implies that (sk′,p′) is a wrong guess. Therefore, we may eliminate some wrong guesses of sk′,p′ further in this step. Moreover, one may also try more middle terms such as skv′=sk′·c′q,sk′·c′q±q during the “decryption” to ensure that the correct value of sk′·v+p′∑j=1weij′ is not missed. However, from our experimental results, we observe that trying only one skv′=sk′·c′q is enough to recover the plaintext in practice.Experimental Results. We implemented our attack using the NTL library [35]. All experiments were run on a single core of a 3.40 GHz Core i7-4930K PC.We follow the parameter setting suggested in [25]: the public parameters (q,n,m,t,w,b)=(232,13,74,216,86,16) and the secret parameters (sk,p)=(2x+1,t+2y+1). We denote the cases (x,y)∈[0,50]×[0,500] and [0,500]×[0,50] by ParaA and ParaB, respectively. For ParaA and ParaB, we respectively generated 100 random instances and calculated the ciphertexts of 100 random messages for each instance. Then we ran the attack on these 10000 ciphertexts. Experimental results are given in Table 1.Table 1
Experimental results.
Parameter Time for Step1 Time for Step2 Time for attack Determining uniquesk,p Success rate ParaA 0.61 s 1.94 s 2.55 s 67% 100% ParaB 0.60 s 1.86 s 2.46 s 71% 100%As mentioned before, we may obtain severalsk′,p′ pairs in Step 1. In fact, it suffices to take use of the pair with the minimal sk′ to recover the plaintext. This observation leads to an optimization of the attack: one may search sk′,p′ in increasing (dictionary) order and move to Step 2 once a candidate is found. Experimental results for optimized attack are given in Table 2.Table 2
Experimental results for optimized attack.
Parameter Time for Step1 Time for Step2 Time for attack Success rate ParaA 0.57 s 1.14 s 1.71 s 100% ParaB 0.57 s 1.14 s 1.71 s 100%Comparison with Bootle and Tibouchi’s Attack. We note that Bootle and Tibouchi also proposed a practical attack [29] against Liu et al.’s encryption scheme. They deployed the technique of embedding lattices to compute the nonce sequence i1,…,iw in encryption processEnc(·), while we start from a different angle and recover a substitutable tuple of private keys sk′,p′,s′,e′. We hold the view that the insecurity of Liu et al.’s scheme is not only a result of the small value of n as claimed in [29], but also the overstretched magnitude relation between the modulus q and parameters b, m, and n, which is clarified in Theorem 11.


## 4.3. Attack against Galbraith’s Scheme

In [24], Galbraith proposed a class of LWE-based encryption for constrained devices with more compact parameters; that is, the public matrix A is binary. We tried to attack Galbraith’s scheme exploiting short vectors of Lq⊥(A) as described before, but it was ineffective even for the parameters totally broken in [27]. That is because the modulus q in Galbraith’s scheme is not so overstretched. However, the binary public matrix and encryption nonce may still be problematic as suggested in [27].


## 5. Conclusion

In this paper, we target the variant of LWE called Compact-LWE which may be applied to design IoT-oriented lightweight cryptography. We give an explicit analysis of Compact-LWE and point out some weak instances with extreme compactness and overstretched moduli. As an application of our results, we propose a practical attack against the lightweight public key scheme in [25]. Consequently, we claim that the security estimation in [25] is incorrect.The fragility of the scheme in [25] comes not only from its small parameters but also from the weak hardness of Compact-LWE. It would be interesting to generally figure out a theoretical hardness relation between Compact-LWE and other lattice problems.Compact-LWE may be still of some interest under refined parameters. We leave to future work the issues of tradeoff between efficiency and security, in particular the practical parameter selections achieving given security levels for IoT devices.



---

*Source: 4957045-2018-03-11.xml*