IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

173

PAPER

Special Section on Cryptography and Information Security

On the Complexity of the LWR-Solving BKW Algorithm∗
Hiroki OKADA†a) , Atsushi TAKAYASU†† , Nonmembers, Kazuhide FUKUSHIMA† , Shinsaku KIYOMOTO† ,and Tsuyoshi TAKAGI†† , Members

SUMMARY
The Blum-Kalai-Wasserman algorithm (BKW) is analgorithm for solving the learning parity with noise problem, which wasthen adapted for solving the learning with errors problem (LWE) by
Albrecht et al. Duc et al. applied BKW also to the learning withrounding problem (LWR). The number of blocks is a parameter of BKW.
By optimizing the number of blocks, we can minimize the time complexityof BKW. However, Duc et al. did not derive the optimal number ofblocks theoretically, but they searched for it numerically. Duc et al. also
showed that the required number of samples for BKW for solving LWE
can be dramatically decreased using Lyubashevsky’s idea. However, it
is not shown that his idea is also applicable to LWR. In this paper, wetheoretically derive the asymptotically optimal number of blocks, and thenanalyze the minimum asymptotic time complexity of the algorithm. We
also show that Lyubashevsky’s idea can be applied to LWR-solving BKW,
under a heuristic assumption that is regularly used in the analysis of LPNsolving BKW. Furthermore, we derive an equation that relates the Gaussian
parameter σ of LWE and the modulus p of LWR. When σ and p satisfy theequation, the asymptotic time complexity of BKW to solve LWE and LWR
are the same.
key words: lattice, learning with errors, learning with rounding, BlumKalai-Wasserman algorithm

1.

Introduction

Background.
The National Institute of Standards and Technology(NIST) initiated post-quantum cryptography (PQC) standardization [2] in December 2016. In the list of first-roundcandidates, there are several learning with errors problem(LWE) based schemes such as [3]–[7], and learning withrounding problem (LWR) based schemes such as [8]–[11].
Subsequently, NIST announced 26 second-round candidates
selected from the 69 first-round candidates in January 2019.
LWE-based [3]–[5] and LWR-based [10], [12] schemes still
remain on the second-round candidate list. Therefore,studies on the algorithms for solving LWE and LWR are
important for design and security analysis of post-quantum
cryptosystems.
LWE, which is an extension of the learning parity with
Manuscript received March 18, 2019.
Manuscript revised July 1, 2019.
†
The authors are with KDDI Research, Inc., Fujimino-shi, 3568502 Japan.
††
The authors are with The University of Tokyo, Tokyo, 1138654 Japan.
∗
A preliminary version of this paper was presented in [1] at
ICISC 2018. This full version provides a technical contribution
over [1] in Sect. 4.
a) E-mail: ir-okada@kddi-research.jp
DOI: 10.1587/transfun.2019CIP0022

noise problem (LPN), is introduced by Regev [13]. An
adversary of LWE receives samples (a j , ha j , si + e j ) ∈ Znq ×
Zq ( j = 1, 2, . . . ) from the oracle of LWE, where a j is a
uniformly random vector in Znq , s is a fixed secret vector
in Znq , and e j ∈ Zq is a noise (usually, a discrete Gaussian
noise). The goal of the adversary is to recover secret vector
s. LPN has a fixed modulus q = 2 and the noise follows the
Bernoulli distribution. Regev [13] presents a reduction fromworst-case lattice problems to the average-case LWE.
We can classify algorithms for solving LWE into two
families. The first family uses lattice reduction techniques,
which have been extensively studied [14]–[16]. The
expected complexity of these algorithms is often consideredwhen parameters for LWE-based schemes are discussed,
such as in [17]. The second family is tailor-made for
LPN and LWE without lattice reduction, which includes
the main subject of this paper: the Blum-Kalai-Wasserman
algorithm (BKW) [18]. BKW can be described as a “blockwise” and addition-only variant of the standard Gaussianelimination. First, we separate the vector a j ∈ Znq into
a blocks: We can write a j = (a j,1 ||a j,2 || . . . ||a j,a ), wherena j,1 , . . . , a j,a ∈ Zqa , and then, by adding the samples together
like the Gaussian elimination, we obtain “reduced” samples
a0j = (a0j,1 ||0|| . . . ||0). As reported in [19], improved variantsof BKW such as [20], [21] are some of the asymptoticallyfastest algorithms. Although some algorithms [22] based on
lattice reduction outperform these BKW-like algorithms forsome parameter-sets (q, σ), it allows a heuristic [19].
LWR is proposed by Banerjee et al. [23] with
its reduction from LWE. We can consider LWR as adeterministic variant of LWE in which the noise additions
are replaced with deterministic rounding operations. An
adversary of LWR receives samples (a j , d qp ha j , sic) ∈ Znq ×
Z p ( j = 1, 2, . . . ) from the LWR oracle, where p is arounding modulus such that p < q. Compared with LWEbased cryptographic schemes, LWR-based schemes can be
simply implemented because they replace the rich Gaussian
error sampling process of the LWE-based schemes withthe rounding operations (which can be simply implemented
by rounding off the lower-order bits). LWR was initiallyapplied to low-depth pseudorandom functions [23], [24],and there have been a number of applications, e.g., lossy
trapdoor functions [25], public-key cryptosystems [10], [12]and key exchange protocol [9].
However, few studies have examined the complexity of

Copyright c 2020 The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

174

LWR, while the complexity of LWE has been extensively
studied. The complexity of LWR is often estimated byadopting the LWE-solving algorithms to LWR. Albrecht

et al. [17] estimate the cost of running primal anddual lattice attacks, which is based on lattice reduction
techniques, against lattice-based schemes including LWEbased and LWR-based schemes in the list of the first-roundsubmissions for the NIST PQC. They consider that the costof lattice attacks for LWE and LWR are the same when theequation σ = 2 √q3p holds, as considered in [8], [10]. Thisequation is simply derived by comparing the variance of theGaussian noise of LWE and the “rounding error” of LWR.
Note that the equation, which relates the hardness of LWR
and LWE, is limited to attacks based on lattice reduction
techniques, and it is not shown that the conversion equation
can be applied for BKW.
Previous Works. BKW initially targeted LPN, and its
time complexity is sub-exponential in 2O(n/ log n) . Albrecht
et al. [26] expanded it to solve LWE whose time complexity
is qO(n/ log n) . Duc et al. [27] improved Albrecht et al.’s BKW
and also introduced its variant for LWR, which was the firstalgorithmic analysis of LWR. They showed that the timecomplexity of the LWR-solving algorithm is qO(n/ log n) when
the number of blocks is a = O(log n). However, they did
not show that this choice of a is optimal; thus the minimum
time complexity of the algorithm is not shown.
Furthermore, Duc et al. applied Lyubashevsky’s idea[28] to LWE and showed that the minimum required numberof samples using his method is n1+(log q+1)/ log n , at theexpense of increasing the size of the noise. However, they
did not show that Lyubashevsky’s idea can also be applied
to LWR.
After BKW proposed by Albrecht et al., new variantsof BKW [20], [21], [29], [30] for solving the small-secret
LWE, whose secret vector s is extremely small (e.g. s ∈{0, 1}n ), have been proposed. These algorithms can beapplied to the general LWE, whose secret vector s is uniform
in Znq , by transforming the general LWE to small-secret LWE
problem with a technique called secret-error switching, and
it is shown that some of these algorithms [20], [21] solve thegeneral LWE problem faster. However, it is not shown thatthese new types of BKW can be applied to LWR. In order toapply the secret-error switching technique to LWR, we needto convert LWR samples into LWE samples with uniform
error by substituting the LWR samples (a j , d qp ha j , sic) with(a j , qp d qp ha j , sic), and solving this converted LWR with theiralgorithm is out of reach, as mentioned in [21]. On theother hand, Duc et al.’s LWR-solving BKW does not needto convert LWR samples into LWE samples; the algorithm istailor-made for solving LWR.
Our Contribution. Our work mainly targets the asymptotic
complexity for solving the LWR problem, rather than for
specific LWR instances with the parameters used in NISTPQC candidates.
In Sect. 3, we first review Duc et al.’s LWR-solving
BKW, and then derive the time complexity in a simpler

form. Subsequently, we theoretically derive the optimal
choice of the number of blocks a that asymptoticallyminimize the time complexity, while Duc et al. searchednumerically for the optimal a in [27]]. Thus, an entirely
theoretical analysis of the time complexity of the algorithm
is shown in this paper: We show that the minimum timecomplexity of BKW is t = qO(n/ log n) and the required
number of samples is m = qO(n/ log n) . We also confirm thatthe derived parameter is accurately optimal by showing theresults of some concrete instances of LWR, and that they fit
the results given by Duc et al.
In Sect. 3.4, we derive a conversion equation between
the Gaussian parameter σ in LWE and the rounding modulus
p in LWR, by comparing the time complexity of BKW for
LWE and LWR: We show that the time complexity of BKW
to solve LWE and that to solve LWR are the same when σ
and p satisfy equation σ = 2 √q3p . This equation coincides
with the equation derived from the complexity analysis of
the attacks based on lattice reduction techniques. Thus,
our result means that the equation is applicable also forcomplexity analysis based on BKW.
In Sect. 4, we apply Lyubashevsky’s idea (hereinafter
called sample amplification) to the LWR problem, and showthat the minimum required number of samples for LWRsolving BKW with sample amplification is m = O(n log q),
while it is shown that the LWR-solving BKW requiresm = qO(n/ log n) samples in Sect. 3. This result meansthat the LWR-solving BKW algorithm is also applicablein a practical situation where we can obtain only apolynomial-size number of LWR samples, using the sample
amplification technique.
2.

Preliminaries

Notations.
We denote the logarithm of base 2 and the natural
logarithm as log(·) and ln(·), respectively. We denote theimaginary unit as i, and a real part of x ∈ C as Re(x). We
let d·c : R → Z be the rounding function that rounds to theclosest integer (in the case of equality, we take the floor).
2πi
2πi
We define θq := e q and also θ p := e p . We write vectors inbold. By a j we denote the j-th vector of the list of vectors.
We denote a partial vector of a vector a = (a1 , a2 , . . . , an ) bya(k,l) := (ak , ak+1 , . . . , al ), where 1 ≤ k ≤ l ≤ n. By (a||b) wedenote the concatenation of two vectors a and b. We denotethe Hamming weight of the vector x by Hw(x). We denoteby h·, ·i the usual dot product of two vectors, and we defineh·, ·iq := h·, ·i (mod q). We denote the empty set by ∅. We
U

write s ←− S to denote the process of sampling s uniformly
at random over S, and we write e ← χ to denote the processof sampling e according to a probability distribution χ.
2.1

LWE and LWR

LWE oracle and LWE are defined as follows.

Definition 1 (LWE oracle). Let n, q be positive integers.

OKADA et al.: ON THE COMPLEXITY OF THE LWR-SOLVING BKW ALGORITHM

175

Learning with Error (LWE) oracle LWE s,χ for a fixed vectors ∈ Znq and probability distribution χ over Zq is an oracleU
returning (a, c) c = ha, si + e mod q, a ←− Znq , e ← χ .
For the distribution of noise χ, variants of the Gaussian
distribution that is discretized into Zq are used. In thispaper, we consider two types of Gaussian distributions thatare considered in [27]; the rounded Gaussian distribution
Ψ̄σ,q and the discrete Gaussian distribution Dσ,q . The
probability mass function of Ψ̄σ,q for integer x in the interval
R x+ 1] − q2 , q2 ], is given by Pr[x ← Ψ̄σ,q ] = x− 12 g(θ; q, σ)dθ,2
i q qi−(θ+lq)2P
1
2σ2 , for θ ∈√where g(θ; q, σ) := ∞e−2, 2 .
l=−∞ σ 2π
The probability mass function of Dσ,q is, for x an integery2x2
Pin ] − 2q , q2 ], Pr[x ← Dσ,q ] = e− 2σ2 / y∈]− 2q , q2 ] e− 2σ2 .
Definition 2 (LWE problem). LWE is the problem ofrecovering the hidden secret s given m samples (a j , c j ) ∈Znq × Zq ( j = 1, 2, . . . , m) received from LWE s,χ .
LWE oracle and LWE, which are the main focus of thispaper, are defined as follows.

Definition 3 (LWR oracle). Let n, q be natural numbers.
Learning with Rounding (LWR) oracle LWR s,p for a hidden
vector s ∈ Znq and rounding modulus p is an oracle returning


l
k
U
(a, c) c = qp ha, siq , a ←− Znq .
Definition 4 (LWR problem). LWR is the problem ofrecovering the hidden secret s given m samples (a j , c j ) ∈Zkq × Zq ( j = 1, 2, . . . , m) received from LWR s,p .
The rounding calculation in the LWR sample generates
a “rounding error,” which is similar to the Gaussian noise
added in the LWE sample. Duc et al. proved that “rounding
error” follows a uniform distribution, in Lemma 19 in [27].
Lemma 5 (Lemma 19. in [27]). Let n and p ≥ 2 be positive
integers, q > p be prime. Let (a, c) be a random sample
from an LWR oracle LWR s,p . Then, the “rounding error,”given byξ=pha, siq − c,q(1)follows the uniform distribution in a discrete subset of[− 21 , 12 ] with mean zero. Furthermore, the characteristic
function of ξ, for t ∈ R,0 , isφξ (t) := E[e±itξ ] =sin( 2t )q sin( 2qt ).

(2)Banerjee et al., showed a reduction from LWE to
LWR, in the paper [23] in which they first introduced LWR.
Alwen et al. [25] also showed a reduction without the superpolynomial parameters, but it limits the number of samples
that the LWR oracle allows the adversary to receive.

2.2

Duc et al.’s BKW for LWR

We recall Duc et al.’s BKW to solve LWR. BKW consistsof three stages: 1) Sample reduction, 2) Hypothesis testing,and 3) Back substitution. For simplicity, we consider only
the case that the number of blocks a and the block length b
satisfy ab = n.
Stage 1: Sample reduction. We receive m samples{(a j , c j )}mj=1 from LWR oracle LWR s,p , and represent the setof samples as S := {(a j , c j )}mj=1 . We separate the vectora j ∈ Znq into a blocks whose length are b: We can write
a j = (a j (1,b) ||a j (b+1,2b) || . . . ||a j ((a−1)b+1,ab) ). In Stage 1, ourgoal is to produce samples whose elements are all zero
except for the first block, with the addition or subtractionof pairs of samples. For l = 0, we extract a sample(a, c) from S, and search another sample (a0 , c0 ) such that(a±a0 )((a−1)b+1,ab) = 0, then we store the sample (a±a0 , c±c0 )in the temporary set S0 . If a sample (a, c) already holdsa((a−1)b+1,ab) = 0, we directly store it in S0 . If we cannot
find the sample (a0 , c0 ) such that (a ± a0 )((a−1)b+1,ab) = 0,
we store the sample (a, c) in T0 . After we finish extracting
samples and empty the set S, we renew S ← S0 and moveon to the next step for l = 1. In this manner, we recursively
generate the sets Tl for 0 ≤ l ≤ a − 2, and then we set
Ta−1 ← S in the end. Note that the samples (a, c) in Tl
hold a((a−l)b+1,ab) = 0 (except for l = 0). In particular, thesamples (a, c) in Ta−1 hold a(b+1,ab) = 0. We may thinkof the reduced samples in T a−1 as the set of samples of theb-dimensional LWR, although the variance of their noise islarger than those of the original samples. Hereinafter, thesamples in Tl are termed “reduced samples,” and representlTl = {(alj , clj )}mj=1, where ml := #Tl . Note that the maximum
number of samples whose (a − l)-th block cannot vanish is
qb −1
2 , and the minimum (worst) number of reduced samples
in Ta−1 (i.e. minimum value of ma−1 ) is
m0 = m − (a − 1)

qb − 1.
2(3)

Stage 2: Hypothesis testing. For simplicity, we explain
Stage 2 and Stage 3 only for l = a − 1† . For simplicity ofnotation, we define a b-dimensional vector a j := (aa−1
j )(1,b) ,and denote c j := ca−1
j . The goal of this stage is to estimate
the first b elements of s, denoted as s(1,b) . We define the
2πi
P 0
c
function f (y) := mj=1 1{a j =y} θ pj , where y ∈ Zbq , θ p := e p ,and 1{a j =y} is 1 when a j = y is true and 0 otherwise. The
discrete Fourier transform of f isfˆ(z) :=

Xy∈Zbq

f (y)θq−hy,zi =m0X−( p ha j ,zi−c j )
.
θp q

(4)

j=1

Then, we search the max Re( fˆ(z)), and output s(1,b) =†In Sect. 3.1, we consider only the time complexity to recovers(1,b) because the whole time complexity of the algorithm is at mosta positive constant multiple of it.

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020176

argmax z Re( fˆ(z)). We explain how the output estimates thesecret vector. We define the “rounding error” of the reduced0samples {(a j , c j )}mj=1 by ξ j := qp ha j , s(1,b) i − c j , as like (1).
Recall that the a j is produced by a − 1 times of the “treelike” addition of the original samples in the process of Stage
1, i.e. a j is the sum of the 2a−1 original samples, thus we canwrite a j = (a j,1 ± a j,2 ±· · ·± a j,2a−1 )(1,b) , where a j,1 , . . . , a j,2a−1
are the original samples. Similarly, we can write c j = c j,1 ±c j,2 ±· · ·±c j,2a−1 , and obtain ξ j = qp ha j,1 ±a j,2 ±· · ·±a j,2a−1 , si−
P a−1
P a−1
(c j,1 ± c j,2 ± · · · ± c j,2a−1 ) = 2k=1 qp ha j,k , si − c j,k = 2k=1 ξ j,k ,where the ξ j,k are independent rounding errors from original
samples. From the above equation and (4), when z = s(1,b) ,P 0 −(P2a−1 ξ )we obtain fˆ(s(1,b) ) = mj=1 θ p k=1 j,k . On the other hand,when z , s(1,b) , qp ha j , zi − c j distribute uniformly in ]0, p].
Thus, when we select an appropriate value of parameter
P a−1
a such that the sum of the rounding errors 2k=1 ξ j,k does not
grow too large, Re( fˆ(s)) is so much larger than Re( fˆ(z)) thatthe hypothesis test succeeds with high probability.
Stage 3: Back substitution. Using the obtained s(1,b) ,update the sets Tl by zeroing-out b elements in each sample:
Replace all (a, c) ∈ Tl0 for 0 ≤ l0 < a − 1 with (a0 , c0 ), wherea0 = (0||a(b+1,n) ) ∈ Znq , c0 = c − qp ha(1,b) , s(1,b) iq ∈ Z p . Thenback to Stage 2 to obtain s(b+1,2b) .
Repeating a rounds of Stages 2 to 3, we estimate s(1,b) , s(b+1,2b) , . . . , s(a(b−1)+1,ab) , and obtain s =(s(1,b) ||s(b+1,2b) || . . . ||s((a−1)b+1,ab) ).
3.

Our Analysis of BKWof samples to solve LWR. We asymptotically analyze thetime complexity and make it in a simple form so that we
can theoretically derive the optimal number of blocks a in
Sect. 3.2. We first refer to Lemma 6 (Theorem 23. in [27]),
which is the analysis of the minimum number of samples
needed to solve LWR.
Lemma 6 (Theorem 23. in [27]). We define the probability
thath the algorithm
recoverthe correct answer  :=
 cannotiˆ
Pr argmax z Re f (z) , s(1,b) . Then, the number of samples
required to solve LWR with oracle LWR s,p is8n  q  a−1
a−1 −2mLWR =
ln(Rq,p )2 − (3/p)2anqa − 1+ (a − 1),(5)2
where Rq,p := 
sin πp .
πq sin pq

Note that Rq,p is derived based on the characteristic
function of the “rounding error” given in (2): Rq,p = φξ ( 2πp)
LWRholds. As discussed later, this min (5) is the main termof the time complexity of the algorithm.
In the following Lemma 7, we analyze the asymptotic
behavior of the complicated part of the mLWR . We describe
it in a simpler form in order to enable the analysis of theminimum time complexity, which is given later in Sect. 3.2.
Note
q that we use the error rate of the LWR sample αlwr :=1pπ
6 [8] to describe the time complexity for simplicity ofnotation.
We derive the minimum time complexity and the minimum
number of required samples, by optimizing the number ofblocks a which is a parameter of BKW. As with Duc et al.,we consider only the case that the block length b satisfy
n = ab, for simplicity. Therefore, the block length b isdetermined by the number of blocks a, as b = na . Notethat the complexity of BKW for the general case, wheren = (a − 1) · b + n0 and n0 < b, is asymptotically the samewith that for the case where ab = n. We always consider q
to be a prime, and q > p > 4 because we need the condition
to prove Lemma 7.
In Sect. 3.1, we analyze the time complexity of BKW
for solving LWR, using a as a parameter. Then, we derive
the optimal value of a that asymptotically minimizes theasymptotic time complexity in Sect. 3.2. We confirm thatthe optimal value of a minimizes the time complexityof the algorithm in Sect. 3.3, by calculating the concrete
time complexity of BKW for several LWR instances.
Furthermore, in Sect. 3.4, we derive an equation that relates
σ of LWE and p of LWR. When σ and p satisfy the equation,
the asymptotic time complexity of BKW to solve LWE and
LWR are the same.
3.1

Complexity

We analyze the time complexity and the required number

Lemma 7. Let αlwr := 1p

2a−1(Rq,p )qπ
6 . When q > p > 4, we have

2a−1 −2− (3/p)

πα2lwr 2a=e!
1+O 2 2 .
p q
p

(6)

 
sin π

Proof. When q > p > 4, we obtain Rq,p = pqπ  pπ  ≥π sin pq
 
 
p
p
π
π
increasing when
π sin p . Since π sin p is monotonically 4πp > 4, we obtain Rq,p > π sin 4 ' 0.9003, and
a−1

a−1

Rq,p > 3/p. Let x = (Rq,p )2 and y = (3/p)2 ,then we have yx < 1. Using Taylor expansion, we
obtain (x − y)−2 = x12 1 + O( yx ) . Therefore, we obtain
a−1 −2a−1
a(Rq,p )2 − (3/p)2= (Rq,p )−2 + O 21a−1 . Using
p


π2
1
Taylor expansion, we obtain Rq,p = 1 − 6p
+
O
= 1−
2
2 q2
p




1
1
2
−πα2lwr
παlwr + O p2 q2 , and Rq,p − e= O p2 q2 . Consequently,

−2a


2
a
= eπαlwr 2 + O p21q2 .
from this equation, we obtain Rq,pThus, we have (6).
We can now derive the number of required samples andthe time complexity of the algorithm.
Theorem 8. Let n and p > 4 be positive integers, q > p
be a prime, and a be a natural number. Fix  ∈ (0, 1).

OKADA et al.: ON THE COMPLEXITY OF THE LWR-SOLVING BKW ALGORITHM

177

When at least mLWR = poly(eπαlwr 2 , q a ) samples are given
by LWR oracle LWR s,p , the time complexity of BKW torecover secret s with a probability of qat least 1 −  is
2

tLWR = poly(eπα2lwr 2a

,q

n
a

a

n

), where αlwr = 1pπ6.

Proof. From Lemma 6 and Lemma 7, the number ofrequired samples to solve LWR is!!
8n  q  πα2 2a1mLWR =
lne lwr + O 2 2
a

pq
n

+ (a − 1)

qa − 1.
2(7)

Recall that the number of the “reduced” samples wenaobtain after Stage 1 is m0 = mLWR − (a − 1) q 2−1 =q  2 a8neπαlwr 2 + O p21q2 , which is defined in (3).
a ln 
In Stage 1, since we apply the addition for O(mLWR )samples in Znq for a − 1 times, the time complexity is
t1 = O(anmLWR ). In Stage 2, we first calculate f (y) :=Pm0
cjb
j=1 1{a j =y} θ p , for all y ∈ Zq . Since we need only tom0
calculate f (y) for y ∈ {a j } j=1 , the time complexity forcalculating f (y) is O(m0 ) = O(eπαlwr 2 ( an ) ln q). After that,
we compute the DFT of f , the complexity of which isnO(q a ( na ) ln q). Finally, we search max fˆ(z) defined in (4) for
2

n

a

n

all z ∈ Zqa , the time complexity of which is O(q a na ). Thus,2athe time complexity of Stage 2 is t2 = O(eπαlwr 2 ( an ) ln q) +n n
O(q a ( a ) ln q). In Stage 3, since we update all samples stored
in Tl0 (the total number of these samples is mLWR − m0 ) withn
inner product calculation of the vectors in Zqa , and the timencomplexity is t3 = O((mLWR − m0 ) an ) = O(q a na ). Therefore,
the time complexity of BKW is tLWR = t1 + t2 + t3 =
n
n
2
a
2
a
O(eπαlwr 2 ( na ) ln q) + O(q a ( na ) ln q) = poly(eπαlwr 2 , q a ).

3.2

asymptotically minimized† when a satisfies
eπαlwr 2 = q a .
2

Theorem 9 (Optimal choice of a). The optimal parametera that asymptotically minimizes the asymptotic timecomplexity of the algorithm to solve LWR is



 1
 n ln q ln 2 
a = 
W 
(8)
ln 2
πα2lwrwhere W is Lambert W function [31].
Proof. From Theorem 8, we obtain the time complexity
n
2
a
2
a
t = O(eπαlwr 2 ( na ) ln q) + O(q a ( an ) ln q). Note that eπαlwr 2nmonotonically increases and q a monotonically decreases,
as a increases.
Therefore, the time complexity isn(9)From (9), by simple arithmetic, we obtain (ln 2)ae(ln 2)a =n ln q ln 2
. To solve this equation in terms of a, we use the
πα2lwrLambert W function, which satisfies W(zez ) = z. We obtain
W((ln 2)ae(ln 2)a ) = (ln 2)a, and (8).
Since the Lambert function W(x) has an asymptotic
form as W(x)+o(1), we can evaluate = ln(x) − ln(ln(x))
a = ln12 ln n lnπαq2ln 2 − ln ln n lnπαq2ln 2 + o(1). Furthermore,
lwr
lwr
when we consider q to be at most exponential of n (thisrange of q includes most of q used in LWE cryptosystems),
we obtain log q = O(n), and a = O(log n). Using this value,(9), and Theorem 8, we obtain the corollary below.
Corollary 10 (Minimum time complexity).
 Let nand q >p > 4 be prime numbers. Let a = ln12 W n lnπαq2ln 2 , wherelwr
q
αlwr = 1p π6 . Fix  ∈ (0, 1). When at least qO(n/ log n) samples
are given by LWR oracle LWR s,p , the time complexity of
BKW to recover secret s with a probability of at least 1 − is qO(n/ log n) .
3.3

Concrete Analysis

Table 1 shows the concrete time complexity of BKW. We
denote the time complexity of the LWR-solving BKW by
CLWR . Then, similar to Theorem 17 in [27], we obtain!
n
12n
CLWR = (a − 2)(a − 1)
+ 1 (q a − 1)4an+nq a log(q)!
a−1
X0LWR a − 1 − j+
m j,
(n + 2) + 2 ,2
j=0

Optimization

We analyze the optimal choice for input parameter a toasymptotically minimize the asymptotic time complexity of
BKW to solve LWR. Furthermore, we analyze the minimum
time complexity.

a

(10)

 q   a−1− j
a−1− j −2
where m0j,LWR := 8n. We use
R2q,p − (3/p)2
a ln 
the same parameters n, q and p as in Table 2 in [27]: For√
type (a), q = nextprime(d(2σn)3 e), p = nextprime(d 3 qe)and for type (b), p = 13, q = nextprime(d2σnpe), wheren2
σ = √2πn(log(n)). These parameters are selected based on
2
Corollary 4.2 in [25]. Type (a) parameters maximize theefficiency, and type (b) parameters minimize the modulus toerror ratio (q/σ). Note that we also ignored the constraint
on them as Duc et al. did. We set
 number of samples
a = ln12 W n lnπαq2ln 2 and calculate mLWR and CLWR in (5)lwr
and (10), respectively. We also set  = 0.01 in Table 1,

Let ã satisfies eπαlwr 2 = qn/ã , and Let tã be the time complexity
2ãwith a = ã, namely tã = O(eπαlwr 2 ( na ) ln q). If we set a > ã, then we
2
a
2
a
2
ã
obtain ta = O(eπαlwr 2 ( na ) ln q), and ta > tã since eπαlwr 2 > eπαlwr 2 .
n n
If we set a < ã, then we obtain t = O(q a ( a ) ln q), and ta > tã sincenq a > qn/ã . Therefore, ã is asymptotically optimal.
†

2

ã

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

178
Table 1Time and sample complexity for the LWR-solving BKW.

LWR instance: type (a)

n
32
40
64
80
96
112
128

q
6318667
23166277
383056211
1492443083
4587061889
11942217841
27498355153

p
191
293
733
1151
1663
2287
3023

a
19∗
20∗
24† (23)
25∗
26∗
28∗
29∗

log(CLWR )
51.00
60.66
92.70† (92.10)
110.82132.17148.00167.44

LWR instance: type (b)log(mLWR )
42.70
52.18
83.08† (82.80)
101.11
122.15
137.68156.88

q
2411
3709
9461
14867
21611
29717
39241

p
13
13
13
13
13
13
13

a
11∗
11∗
12∗
12∗
12∗
13∗
13∗

log(CLWR )
44.53
53.24
81.48
103.76126.83140.08162.50log(mLWR )
37.00
45.44
72.92
94.86
117.66130.63152.84∗ : optimal value. † : not optimal value. The optimal values are shown in parenthesis.

in accordance with the setting given in Table 2 of [27]. In
Table 1, we can observe that our choice of the number ofblocks a asymptotically (but almost exactly) minimizes thetime complexity of the algorithm.
3.4

Relation between LWE and LWR

We compare the time complexity of BKW to solve LWE
and LWR, and then derive a relation between p in LWR
and σ in LWE. We showed that the time complexity ofn2a
BKW to solve LWR is poly(eπαlwr 2 , q a ) in Theorem 8. On
the other hand, based on Theorem 16 in [27], Kaminakaya
et al. [32] analyzed the time complexity of BKW to solven2a
LWE, and showed√that the complexity is poly(eπαlwe 2 , q a ),2πσwhere αlwe :=We describe the result later inq .
Lemma 12 and refer to the proof given in [32]. As a
preparation, we refer to Theorem 16 in [27], which shows
the number of samples required to solve LWE:hLemma 11 (Theorem 16. in [27]). Let  := Pr argmax zi
Re fˆ(z) , s(1,b) be the probability that the algorithm does
not recover the correct answer. Then, the number of samples
required to solve LWE with oracle LWE s,χ is mLWE =
n
q
a
8n
−2a
+ (a − 1) q 2−1 , wherea ln  (Rq,σ,χ ) qπ−2π2 σ2 /q2
when χ = Ψ̄q,σ , π sin q e
Rq,σ,χ = 1 − 2π22σ2
when χ = Dq,σ .
q
We can show the time complexity of BKW for LWE
based on this Lemma:
Lemma 12 ([32]). Let a and b be natural numbers such thatab = n. There is an algorithm to solve LWE whose oracle isn2a
LWE s,χ , with the number of samples m = poly(eπαlwe 2 , q a ),
n
a
2
and
the time complexity t = poly(eπαlwe 2 , q a ), where αlwe :=√2πσq , both when χ = Dσ,q and χ = Ψ̄σ,q .
Proof. Here, we refer the proof given in [32]. Similar to theproof of Theorem 8, using Lemma 11, we can prove that
there is an algorithm to solve LWE whose oracle is LWE s,χ ,−2a nwith number of samples m = poly( Rq,σ,χ
, q a ), and time−2a ncomplexity t = poly( Rq,σ,χ
, q a ). Thus, we need only2

prove that Rq,σ,χ = O(e−παlwe ) holds, both when χ = Ψ̄σ,qand when χ = Dσ,q . When χ = Ψ̄σ,q , since sin πq < πq , weobtain Rq,σ,χ < e−2π σ /q = e−παlwe , which means Rq,σ,χ =2O(e−παlwe ). When χ = Dσ,q , using Taylor expansion, we
2

2

2

2

2

2

α4

6
obtain Rq,σ,χ − e−παlwe = 1 − πα2lwe − e−παlwe = − lwe
2 + O(αlwe ),2thus we obtain Rq,σ,χ = e−παlwe + O(α4lwe ).

We can now derive the relation between the parametersof LWE and LWR.
Corollary 13. The time complexity of BKW to solve LWE
over Znq with Gaussian parameter σ and that to solve LWR
over Znq with rounding modulus p are asymptotically thesame, when q, p and σ satisfy
σ=

q
√ .
2 3p

(11)

Proof. The time complexity of BKW to solve LWE and
LWR are given in Theorem 8 and Lemma 12, respectively.
Solving the equation παlwe = παlwr for σ, we obtain
(11).
3.5

Application to Variants of LWR

Most of LWE-based [3], [5] or LWR-based [10], [12]schemes are based on the ring variants of LWE or
LWR, which are Ring-LWE (RLWE) [33], Module-LWE(MLWE) [34], Ring-LWR (RLWR) [23] and Module-LWR(MLWR) [10], [12]. In RLWE, polynomials s, ai , and ei
are sampled from a ring Rq := Zq /φ for some polynomial
φ of degree n, e.g. φ = X n + 1. Given a list of RLWE
samples (ai , ai · s + ei )mi=1 , Search-RLWE is to recover s
and Decision-RLWE is to distinguish the list of samples
from a list uniformly sampled from Rq × Rq . MLWE is aproblem which generalizes RLWE. In MLWE, polynomial
vectors ai , s, and polynomials ei are drawn from Rqk and Rq
respectively. Search-MLWE is to recover s from a list of
MLWE samples (ai , < hai , si + ei )mi=1 . Decision-MLWE is todistinguish the list of samples from a list uniformly sampledfrom Rqk × Rq . In Search-RLWR and Decision-RLWR, amlist of RLWR samples (ai , d qp ai · sc + ei ) ∈ Rq × R p is
i=1
given, where d·c is the function that rounds the coefficientsof an input polynomial to the nearest integer. In SearchMLWR and Decision-MLWR, a list of MLWR samplesm(ai , d qp hai · sic + ei ) ∈ Rqk × R p ,i=1
The complexity of RLWE, MLWE, RLWR and MLWR

OKADA et al.: ON THE COMPLEXITY OF THE LWR-SOLVING BKW ALGORITHM

179

are evaluated by interpreting those ring elements as integer
vectors, in [17]: They convert those variants to LWE or
LWR. Specifically, let us consider the case when we are
given RLWE sample (a, b = a · s + e) ∈ Rq × Rq with
Pn−1
φ = X n + 1, as an example. Let us denote a := i=0
ai X i ,
Pn−1
P
P
n−1
n−1
i
−i
i
b := i=0 bi X , s := i=0 si X , e := i=0 ei X , a =(a0 , . . . , an−1 ), and s = (s0 , . . . , sn−1 ). Then, we notice thatb0 = ha, si + e0 , and (a, b0 ) ∈ Znq × Zq is an LWE sample.
Using this simple conversion, the bit security of all the LWE,
LWR and NTRU based schemes is estimated. In the same
way as this, using the conversion, the BKW algorithm is also
simply applicable to the ring variants. Thus, our analysisof the BKW algorithm can also be applied to RLWR and
MLWR if we can obtain sufficiently many samples.
4.

Using Fewer Samples

We apply the sample amplification idea introduced by
Lyubashevsky [28] to the LWR-solving BKW, and we showthat the required number of samples of BKW can be
decreased to polynomial size, increasing the size of therounding error in LWR samples,
4.1

Sample Amplification Technique

We show how to apply the sample amplification idea
to LWR-solving BKW. We define a variant LWR oracle
LWR0s,p,χ , which regards the rounding error as a stochastic
variable. And then, we obtain Corollary 15.
Definition 14. Let n, q be natural numbers. LWR oracle
LWR0s,p,χ for a fixed vector s ∈ Znq is an oracle returning




U
(a, c) = a, qp ha j , siq + ξ a ←− Znq , ξ ← χ , where χ isdefined by its characteristic function 
h i
sin 2t .
φχ (t) = E eitξ =q sin 2qt

(12)

Corollary 15. An algorithm that can solve LWR withthe oracle LWR0s,p,χ , can also solve LWR with the oracle
LWR s,p .
 lkProof. Suppose we received samples (a, c) = a, qp ha j , siqlkfrom LWR s,p . Let us define ξ = qp ha, siq − qp ha, siq , anddenote the distribution of ξ by χ. From Lemma 19 in [27],we can show that the characteristic function of χ is the sameas (12).
In the rest of this section, we consider the algorithm forsolving a variant of LWR with LWR0s,p,χ .
Theorem 16 (Sample amplification). Let w ∈ N, andβ ∈ R (β > 1). When we obtain m = wqβn/w samples
from LWR0s,p,χ , we can generate an arbitrary number ofsamples of LWR0s,p,χw , where χw is the distribution whose!w
h isin( 2t )itξcharacteristic function is φχw (t) = E e =.
tq sin 2q

Proof. We show that the amplified samples obtainedwith sample amplification and the original samples are
statistically indistinguishable, in a way similar to Lemma
17 in [32]. For m samples (a j , c j ) obtained from LWR s,p , wedefineP(mod q)hA (x) =j∈{ j|x j =1} a j
(13)
P


hc (x) =
c
(mod
p).
j
j∈{ j|x j =1}
U

For j = 1, . . . , M, we sample x j ←− {x ∈{0, 1}m | Hw(x) = w}, and generate an amplified sample( â j , ĉ j ) = (hA (x j ), hc (x j )). We define the set of m original
samples as S := {(a j , c j )}mj=1 , and the set of M amplified
samples as Ŝ := {( â j , ĉ j )} M
Let us define predicate
j=1 .
g, which outputs 1 when BKW solves LWR correctlywith a given set of samples and outputs 0 otherwise.
Then, in a way similar to Lemma 17 in [32], we obtain(β−1)nPr[g(Ŝ) = 1] − Pr[g(S) = 1] ≤ Mq− 2 . Thus, when we(β−1)ndefine the value of β such that limn→∞ Mq− 2 = 0 (at leastβ > 1), we obtain limn→∞ Pr[g(Ŝ) = 1] − Pr[g(S) = 1] =0.
Next, we derive the characteristic
function of χw . FromP(13), we obtain ĉ j = j∈{ j|x j =1} qp ha j , siq + ξ j = qp h â j , siq +PP:=j∈{ j|x j =1} ξ j (mod p). We define ξ̂ jj∈{ j|x j =1} ξ j .
Because ξ j and ξ j0 ( j , j0 ) are i.i.d, from (12),! we obtain
w
h i
h i Q
sin( 2t ) .
φχw (t) := E eitξ̂ = j∈{ j|x j =1} E eitξ j =t
q sin 2q

Independence Heuristic. In order to use the amplified
samples as input of LWR-solving BKW, we assume aheuristic, which is often used in the analysis of BKWtype algorithms for solving LPN [35]–[37]. While BKW
needs original samples to be statistically independent ofeach other, sums of samples (e.g. amplified samples) are
obviously stochastically dependent of each other. However,in [38], it has been shown that the dependence between sumsof 2 LPN samples, which are the counterpart of simplified
samples with w = 2, merely affect the asymptotic timecomplexity of the LPN solving algorithm. Moreover, theauthors of [39] proposed a variant of LPN-solving BKWwith improved memory complexity under the heuristicthat sums of w(> 2) LPN samples also merely affects
the asymptotic time complexity of the LPN-solving BKW
algorithm. They has also presented precise experimental
results that verify the heuristic in the paper. Similar to their
heuristic, we assume that the dependency of the amplified
LWR samples for w ≥ 2 merely affects the asymptotic timecomplexity of the LWR-solving BKW.
4.2

Complexity

We analyze the time complexity and the required numberof original samples for solving LWR with the sample
amplification, in a way similar to Theorem 8.
Theorem 17. Let a and b be natural numbers such that

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

180
Table 2
n
32
40
64
80
96
112
128

q
6318667
23166277
383056211
1492443083
4587061889
11942217841
27498355153

Time and sample complexity for the LWR-solving BKW with sample amplification.

p
191
293
733
1151
1663
2287
3023

without sample amplification (from Table 1)alog(CLWR )log(mLWR )
19∗
51.00
42.70
20∗
60.66
52.18
24† (23)92.70† (92.10)
83.08† (82.80)
25∗110.82101.11
26∗
132.17122.1528∗
148.00137.6829∗
167.44156.88

a
10∗
11∗
13∗
14∗
15∗
16∗
17∗

with sample amplificationlog(CLWR−amp )log(mLWR−amp )
83.60
7.91
99.51
8.21
151.948.84
186.209.13
217.889.36
247.16
9.56
274.27
9.72∗ : optimal value. † : not optimal value. The optimal values are shown in parentheses.

ab = n. Let w ∈ N, and β(> 1) ∈ R. Fix  ∈ (0, 1).
Then, under the Independence Heuristic, when at leastm = wqβn/w samples are given by LWR oracle LWR s,p ,the time complexity of BKW with sample amplification torecover secret s with a probability of atq least 1 −  isnt = poly(q a , exp(α2lwr w2a )) where αlwr = 1pπ6.

Proof. We derive the required number of amplified samples
which we denote by M̂ for solving LWR with sample
amplification, under the Independence Heuristic. This can
be derived by replacing Rq,p in (5) with Rq,p,w := φχw 2π
p .
q 

2a−1 −22a−1(3/p)
Thus, we obtain M̂ = 8n
ln
(R
)
+
−
q,p,w
a

n
a

(a − 1) q 2−1 , Similarly to Lemma 7, we can show that
n
q 


2
a
a
M̂ = 8neπwαlwr 2 + O p21q2 + (a − 1) q 2−1 . The rest ofa ln 
the proof follows that of Theorem 8, by replacing mLWR in(7) with this M̂, and we can show that the time complexity of2a
BKW with sample amplification is t = O(eπwαlwr 2 ( an ) ln q) +
n n
n
2
a
O(q a ( a ) ln q) = poly(eπwαlwr 2 , q a ).
4.3

ab = n. Fix  ∈ (0, 1), and β ≥ 2. Then, underthe Independence Heuristic, when at least m = m̃ =eβn ln q samples are given by LWR oracle LWR s,p , the timecomplexity of BKW with sample amplification to recoversecret s with a q
probability of at least 1 −  is t = qO(n/ã) ,where αlwr = 1p
4.4

Concrete Analysis

Table 2 shows the concrete time complexity of the LWRsolving BKW algorithm with our sample amplification
technique, in the case where we use a minimum numberm̃ = eβn ln q of the LWR samples. We set β = 2 forthis table. We denote the time and the sample complexityof the LWR-solving BKW by CLWR−amp and mLWR−amp ,respectively. Similar to Sect. 3.3, we can obtain!
n12n
CLWR−amp = (a − 2)(a − 1)
+ 1 (q a − 1)4an+nq a log(q)!
a−1
X
0LWR−amp a − 1 − j
m j,
+(n + 2) + 2 ,2
j=0

Optimization

As in Sect. 3.2, we derive the optimal value of the parametera that minimizes the asymptotic time complexity of the
BKW algorithm with sample amplification. In a similar
way to derive (8), we can show that the optimal value ofa to minimize the time complexity of BKW with sample
amplification is



 1
 n ln q ln 2 a = 
W
(14)
 .
ln 2
πwα2lwr
Next, we minimize the required number of samples,regarding w as a parameter. Since m = wqβn/w , and ∂m∂w =qβn/w (w−βn log q), when choose ww= w̃ := βn ln q, we obtainm = m̃ := eβn ln q, whichistheInserting w = w̃ minimum.
ln 2
into (14), we obtain ã = ln12 W πβα. When α2lwr is small2
lwr
enough, we can evaluate

 



 1   ln 2 
ln
2
0
ln  − ln ln  .
ã ' 
(15)
2
2
ln 2
βαlwr
βαlwr

To summarize, we obtain the following corollary:
Corollary 18. Let a and b be natural numbers such thatπ
0
6 , and ã is defined as in (15).

(16)




a−1− j −2
a−1− j0LWR−ampqwhere m j,
R2q,p,w − (3/p)2. This:= 8n
a ln 
can be derived by replacing the Rq,p in m0j,LWR = q   a−1− j
a−1− j −28n
R2q,p − (3/p)2
with Rq,p,w . We use the typea ln 
(a) parameters which are also used in Table 1. We also set = 0.01, in accordance with the setting given in the table.
In Table 2 we reproduce the optimal parameter a, the timeand sample complexity of the LWR solving BKW withoutsample amplification from Table 1, for readability purposes.
From Table 2 we can observe that our choice of the numberof blocks a for BKW with sample amplification, which
is derived in (14), minimizes the time complexity of thealgorithm. We can observe that, at the expense of increasing
the time complexity, the sample amplification techniquesignificantly reduces sample complexity to polynomial size(m̃ = 2en ln q).
5.

Conclusion

We analyzed the time complexity of BKW for LWR

OKADA et al.: ON THE COMPLEXITY OF THE LWR-SOLVING BKW ALGORITHM

181

and theoretically derived the optimal number of blocks athat asymptotically (but almost completely) minimizes thetime complexity of the algorithm, while Duc et al. [27]numerically searched for the optimal value of a. We
derived the relation between the parameters of LWE and
LWR with the same time complexity of BKW, which isσ = 2 √q3p . This equation coincides with the equation
derived by the complexity analysis of the lattice attacks:
We showed that the conversion equation also holds on thecomplexity analysis of BKW. We also showed that the
sample amplification method is applicable to LWR-solving
BKW under the Independence Heuristic, and analyzed thatthe minimum required number of samples for LWR-solving
BKW with sample amplification is O(n log q).
References[1] H. Okada, A. Takayasu, K. Fukushima, S. Kiyomoto, and T. Takagi,“On the complexity of the LWR-solving BKW algorithm,” ICISC
2018, pp.196–214, 2019.
[2] National Institute of Standards and Technology, “Post-quantum
cryptography,” https://csrc.nist.gov/Projects/Post-Quantum-Cryptog
raphy. Accessed: Feb. 27, 2019.
[3] J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J.M.
Schanck, P. Schwabe, G. Seiler, and D. Stehle, “CRYSTALS —Kyber: A CCA-secure module-lattice-based KEM,” EuroS&P 2018,
pp.353–367, 2018.
[4] J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig,
V. Nikolaenko, A. Raghunathan, and D. Stebila, “Frodo: Take off
the ring! practical, quantum-secure key exchange from LWE,” CCS
2016, pp.1006–1018, 2016.
[5] E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe, “Post-quantum
key exchange — A new hope,” USENIX Security Symposium,
pp.327–343, 2016.
[6] R.E. Bansarkhani, “LARA — A design concept for lattice-based
encryption,” Cryptology ePrint Archive, Report 2017/049, 2017.
[7] M.R. Albrecht, E. Orsini, K.G. Paterson, G. Peer, and N.P. Smart,“Tightly secure Ring-LWE based key encapsulation with shortciphertexts,” ESORICS 2017, pp.29–46, 2017.
[8] J.H. Cheon, D. Kim, J. Lee, and Y. Song, “Lizard: Cut off the tail! apractical post-quantum public-key encryption from LWE and LWR,”
SCN 2018, pp.160–177, 2018.
[9] Z. Jin and Y. Zhao, “Optimal key consensus in presence of noise,”
CoRR, vol.abs/1611.06150, 2016.
[10] J.P. D’Anvers, A. Karmakar, S.S. Roy, and F. Vercauteren, “Saber:
Module-LWR based key exchange, CPA-secure encryption and
CCA-secure KEM,” AFRICACRYPT 2018, pp.282–305, 2018.
[11] H. Baan, S. Bhattacharya, O. Garcia-Morchon, R. Rietman,
L. Tolhuizen, J.L. Torre-Arce, and Z. Zhang, “Round2: KEM
and PKE based on GLWR,” Cryptology ePrint Archive, Report
2017/1183, 2017.
[12] H. Baan, S. Bhattacharya, S. Fluhrer, O. Garcia-Morchon,
T. Laarhoven, R. Rietman, M.J.O. Saarinen, L. Tolhuizen, andZ. Zhang, “Round5: Compact and fast post-quantum public-key
encryption,” Cryptology ePrint Archive, Report 2019/090, 2019.
[13] O. Regev, “On lattices, learning with errors, random linear codes,
and cryptography,” J. ACM, vol.56, no.6, pp.34:1–34:40, 2009.
[14] A. Becker, N. Gama, and A. Joux, “A sieve algorithm based on
overlattices,” LMS J. Comput. Math., vol.17, no.A, pp.49–70, 2014.
[15] Y. Chen and P.Q. Nguyen, “BKZ 2.0: Better lattice security
estimates,” ASIACRYPT 2011, pp.1–20, 2011.
[16] N. Gama, P.Q. Nguyen, and O. Regev, “Lattice enumeration using
extreme pruning,” EUROCRYPT 2010, pp.257–278, 2010.
[17] M.R. Albrecht, B.R. Curtis, A. Deo, A. Davidson, R. Player, E.W.

Postlethwaite, F. Virdia, and T. Wunderer, “Estimate all the {LWE,
NTRU} schemes!,” SCN 2018, pp.351–367, 2018.
[18] A. Blum, A. Kalai, and H. Wasserman, “Noise-tolerant learning, theparity problem, and the statistical query model,” J. ACM, vol.50,
no.4, pp.506–519, 2003.
[19] G. Herold, E. Kirshanova, and A. May, “On the asymptotic
complexity of solving LWE,” Des. Codes Cryptogr., vol.86, no.1,
pp.55–83, 2018.
[20] Q. Guo, T. Johansson, and P. Stankovski, “Coded-BKW: Solving
LWE using lattice codes,” CRYPTO 2015, pp.23–42, 2015.
[21] P. Kirchner and P.A. Fouque, “An improved BKW algorithm for
LWE with applications to cryptography and lattices,” CRYPTO
2015, pp.43–62, 2015.
[22] T. Laarhoven, “Sieving for shortest vectors in lattices using angular
locality-sensitive hashing,” CRYPTO 2015, pp.3–22, 2015.
[23] A. Banerjee, C. Peikert, and A. Rosen, “Pseudorandom functions
and lattices,” EUROCRYPT 2012, pp.719–737, 2012.
[24] D. Boneh, K. Lewi, H. Montgomery, and A. Raghunathan,“Key homomorphic PRFs and their applications,” CRYPTO 2013,
pp.410–428, 2013.
[25] J. Alwen, S. Krenn, K. Pietrzak, and D. Wichs, “Learning withrounding, revisited,” CRYPTO 2013, pp.57–74, 2013.
[26] M.R. Albrecht, C. Cid, J.C. Faugère, R. Fitzpatrick, and L. Perret,“On the complexity of the BKW algorithm on LWE,” Des. Codes
Cryptogr., vol.74, no.2, pp.325–354, 2015.
[27] A. Duc, F. Tramèr, and S. Vaudenay, “Better algorithms for LWE
and LWR,” EUROCRYPT 2015, pp.173–202, 2015.
[28] V. Lyubashevsky, “The parity problem in the presence of noise,
decoding random linear codes, and the subset sum problem,”Approximation, Randomization and Combinatorial Optimization.
Algorithms and Techniques, pp.378–389, 2005.
[29] Q. Guo, T. Johansson, E. Mårtensson, and P. Stankovski, “CodedBKW with sieving,” ASIACRYPT 2017, pp.323–346, 2017.
[30] M.R. Albrecht, J.C. Faugère, R. Fitzpatrick, and L. Perret, “Lazymodulus switching for the BKW algorithm on LWE,” PKC 2014,
pp.429–445, 2014.
[31] R.M. Corless, G.H. Gonnet, D.E. Hare, D.J. Jeffrey, and D.E. Knuth,“On the Lambert W function,” Adv. Comput. Math., vol.5, no.1,
pp.329–359, 1996.
[32] K. Kaminakaya, N. Kunihiro, and A. Takayasu, “BKW algorithm
for solving LWE problem,” Symposium on Cryptography andInformation Security, SCIS 2016, IEICE, 2016 (in Japanese).
[33] V. Lyubashevsky, C. Peikert, and O. Regev, “On ideal lattices
and learning with errors over rings,” EUROCRYPT 2010, pp.1–23,
2010.
[34] A. Langlois and D. Stehlé, “Worst-case to average-case reductions
for module lattices,” Des. Codes Cryptogr., vol.75, no.3, pp.565–
599, June 2015.
[35] S. Bogos, F. Tramér, and S. Vaudenay, “On solving LPN using BKW
and variants,” Cryptogr. Commun., vol.8, no.3, pp.331–369, 2016.
[36] S. Bogos and S. Vaudenay, “Optimization of LPN solving
algorithms,” ASIACRYPT 2016, pp.703–728, 2016.
[37] B. Zhang, L. Jiao, and M. Wang, “Faster algorithms for solving
LPN,” EUROCRYPT 2016, pp.168–195, 2016.
[38] S. Devadas, L. Ren, and H. Xiao, “On iterative collision search for
LPN and subset sum,” Theory of Cryptography, pp.729–746, 2017.
[39] A. Esser, F. Heuer, R. Kübler, A. May, and C. Sohler, “DissectionBKW,” CRYPTO 2018, pp.638–666, 2018.

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

182

Hiroki Okada
received his B.E. and
M.E. in applied mathematics and physics from
Kyoto University, Japan, in 2014 and 2016,
respectively. He joined KDDI in 2016 andhas been engaged in research on lattice-based
cryptography and homomorphic encryption. He
is currently an associate research engineer at
the Information Security Laboratory of KDDI
Research, Inc.

Atsushi Takayasu
received his B.E.
in mathematical engineering and information
physics from the University of Tokyo in 2012,
M.S. and Ph.D. in complexity science andengineering from the University of Tokyo in2014 and 2017. He was a JSPS Research Fellow(DC1) during his Ph.D. course. He is currently
an assistant professor in the Graduate Schoolof Information Science and Technology at the
University of Tokyo, a Collaborative Researcher
in National Institute of Advanced Industrial
Science and Technology. He received Best Student Paper Award in ACISP
2016. His research interest includes cryptography and information security.

Kazuhide Fukushimareceived his
M.E. in Information Engineering from Kyushu
University, Japan, in 2004. He joined KDDIand has been engaged in the research on postquantum cryptography, cryptographic protocols,and identification technologies. He is currently
a research manager at the Information Security
Laboratory of KDDI Research, Inc. He received
his Doctorate in Engineering from Kyushu
University in 2009. He received the IEICE
Young Engineer Award in 2012. He is a memberof the Information Processing Society of Japan.

Shinsaku Kiyomoto
received his B.E. inengineering sciences and his M.E. in Material
Science from Tsukuba University, Japan, in
1998 and 2000, respectively.
He joined
KDD (now KDDI) and has been engaged
in research on stream ciphers, cryptographic
protocols, and mobile security. He is currently
a senior researcher at the Information Security
Laboratory of KDDI Research, Inc. He was avisiting researcher of the Information Security
Group, Royal Holloway University of London
from 2008 to 2009. He received his doctorate in engineering from Kyushu
University in 2006. He received the IEICE Young Engineer Award in 2004
and Distinguished Contributions Awards in 2011. He is a member of IEICE
and JPS.

Tsuyoshi Takagi
received the B.Sc. and
M.Sc. degrees in mathematics from Nagoya
University in 1993 and 1995, respectively. He
was engaged in research on network security
at NTT Laboratories from 1995 to 2001. Hereceived the PhD from the Technical Universityof Darmstadt in 2001. He was an AssistantProfessor in the Department of Science at
Technical University of Darmstadt until 2005.
He is currently a Professor in the Graduate
School of Information Science and Technology
at University of Tokyo and in the Institute of Mathematics for Industry at
Kyushu University. His current research interests are information security
and cryptography. He received DOCOMO Mobile Science Award in 2013,
IEICE Achievement Award in 2013, and JSPS Prize in 2014. Dr. Takagi
was a Program Chair of the 7th International Conference on Post-Quantum
Cryptography, PQCrypto 2016.