Cryptanalysis of the Randomized Version of a
Lattice-Based Signature Scheme from PKC’08
Haoyu LiRenzhang Liu1 , Abderrahmane Nitaj2 , and Yanbin Pan1 ?
1
Key Laboratory of Mathematics Mechanization, NCMIS,
Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Beijing 100190, China
2
Laboratoire de Mathématiques Nicolas Oresme
Université de Caen Basse Normandie, France

Abstract. In PKC’08, Plantard, Susilo and Win proposed a latticebased signature scheme, whose security is based on the hardness of theclosest vector problem with the infinity norm (CVP∞ ). This signaturescheme was proposed as a countermeasure against the Nguyen-Regev
attack, which improves the security and the efficiency of the Goldreich,Goldwasser and Halevi scheme (GGH). Furthermore, to resist potential
side channel attacks, the authors suggested modifying the deterministic signing algorithm to be randomized. In this paper, we propose achosen message attack against the randomized version. Note that the
randomized signing algorithm will generate different signature vectors ina relatively small cube for the same message, so the difference of any two
signature vectors will be relatively short lattice vector. Once collecting
enough such short difference vectors, we can recover the whole or thepartial secret key by lattice reduction algorithms, which implies that the
randomized version is insecure under the chosen message attack.
Keywords: Lattice-based cryptography, Signature schemes, Lattice reduction

1

Introduction

It is well known that classical cryptography is vulnerable to quantum
computers since Shor’s algorithm [19] will solve the integer factorization and the logarithm discrete problems efficiently. This has motivatedthe development of post-quantum cryptography, especially lattice-based
cryptosystems. In general, the security of lattice-based cryptosystems isalways related to some hard computational problems in lattices, suchas the Shortest Vector Problem (SVP) and the Closest Vector Problem(CVP).
?

This work was supported in part by the NNSF of China (No. 11201458, No. 11471314
and No. 61572490), and in part by the National Center for Mathematics and Interdisciplinary Sciences, CAS.

2

Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan

As important cryptographic primitives, several lattice-based digital
signature schemes have been proposed in recent years, such as [8, 9, 17,
7, 5]. In 1997, Goldreich, Goldwasser and Halevi [8] proposed the GGH
signature scheme based on lattices, whose security is related to the hardness of approximate CVP. In fact, GGH is not only a concrete signaturescheme, but also a general framework to construct lattice-based digital
signature schemes. The GGH framework consists of a good lattice basis
G, a bad basis B for the same lattice and a reduction algorithm as thesigning algorithm. Usually, the good basis is used as the secret key, withwhich the reduction algorithm can efficiently output an approximation
for the closest vector of a target vector corresponding to the message.
Such approximation is the signature of the message. The bad basis is
published as the public key, with which one can check if the signature isin the lattice and close enough to the target vector. In GGH scheme, theyused a nearly orthogonal basis G as the good basis, a random basis as
the bad basis B, and Babai’s rounding-off algorithm [2] as the reduction
algorithm.
Based on GGH framework, Hoffstein, Howgrave-Graham, Pipher, Silverman, and Whyte [10] presented the NTRUSign as a more efficientlattice-based signature scheme. They used some special short basis as agood basis, a “random” basis as the bad basis B, and Babai’s rounding-off
algorithm as the reduction algorithm.
However, Nguyen and Regev [16] proposed a clever method to recover
the secret key of the GGH signature scheme and NTRUSign by studying the parallelepiped of the lattice. More precisely, by collecting enoughmessage-signature pairs, they can obtain many samples uniformly distributed in the parallelepiped due to Babai’s rounding-off algorithm employed as reduction algorithm in this two signature schemes. Then withthese samples, they can finally recover the parallelepiped which leaks thegood basis. They also pointed out that even taking Babai’s nearest planealgorithm [2] as the signing algorithm, these two schemes are still insecure. Later, Ducas and Nguyen [6] proposed some method to analyze
some countermeasures against the Nguyen-Regev attack.
By the Nguyen-Regev attack, it seems that the security of GGH typesignature schemes depends heavily on the reduction algorithms. To resist
such attack, at least two different reduction algorithms have been proposed. In 2008, Gentry, Peikert and Vaikuntanathan [7] presented a Gaussian sample algorithm similar to [11]. Based on such a random vectorsampling algorithm, Gentry, Peikert and Vaikuntanathan constructed asignature scheme, with a short trap-door basis as the private key and a3long basis as the public key. Since the lattice vectors outputted by the
new sampling algorithm do not reveal the trap-door, the signature schemeof Gentry, Peikert and Vaikuntanathan can be proved to be secure under
the chosen message attack (CMA).
In 2008, Plantard, Susilo, and Win [17] proposed another signaturescheme at PKC’08 to resist the Nguyen-Regev attack. They employed aspecial type of lattices as the good basis which has a basis that can be
written into the sum of a diagonal matrix and a ternary random matrix.
With such a basis, they proposed a reduction algorithm to reduce any
vector into a small cube. Since the cube is public and it seems hard to
recover the private basis from the cube, the authors claimed that theirscheme can resist the Nguyen-Regev attack well.
As pointed out by Plantard, Susilo, and Win, since their reduction
algorithm is deterministic, the scheme may suffer some potential sidechannel attacks. To make the scheme more secure, they modified their
reduction algorithm to be randomized.
In this paper, we show that the randomized version of the PSW signature scheme is insecure under the CMA model. Simply speaking, notethat when we query the signing oracle with the single message m for manytimes, we will usually obtain different signature vectors w1 , w2 , · · · , wk
with k ≥ 2. Denote by H(m) the hash vector of the message m. Note
that, in the PSW scheme, the difference wi − H(m), 1 ≤ i ≤ k are all in
the given lattice. It is easy to see that wi − wj , 1 ≤ i < j ≤ k are all in
the lattice. Note that each signature wi is contained in a relatively small
cube, then their difference vectors wi − wj are relatively short. Once weobtain many such difference vectors, the Z-linear combinations of these
vectors will span the given lattice with high probability. By using thelattice reduction algorithms such as LLL [12] and BKZ [18, 4] to theseshort difference vectors, we could obtain a much shorter basis, which may
leak the good basis in this signature scheme. In fact, we find that for
dimension less than 400, BKZ-20 will recover all or partial rows of thegood basis in our experiments.
To fix the randomized version of the PSW signature scheme, we will
give two methods as presented in [7]. The first method is to store themessage-signature pairs locally. When signing a message, we first check
whether the message is in storage or not. If the message is in storage, we
output the stored corresponding signature, otherwise, we apply the randomized reduction algorithm to generate a signature. The second method
is using the randomized reduction algorithm to generate the signature for4Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan

the hash value of a message and some additional random number insteadof the hash value of just the message.
Roadmap. The remainder of the paper is organized as follows. First we
present some notations and preliminaries on lattices and hard problems
in Section 2. Then we describe the Plantard, Susilo, and Win signaturescheme in Section 3. Finally we describe our attacks and some experimental results in detail in Section 4, and some strategies to fix the randomized
version of PSW signature scheme are discussed in Section 5.

2

Preliminaries

Denote by R, Z the real number field and the integer ring respectively.
For a vector v = (v1 , p
v2 , · · · , vn ) ∈ Rn , denote by vi its i-th component
and denote by kvk = v12 + v22 + · · · + vn2 its length.
2.1

Lattices

A lattice Λ is a discrete subgroup of Rn . Equivalently, a lattice is a Zlinear combinations of m linearly independent vectors in Rn . The set ofthese linearly independent vectors is called a basis of Λ. Given a matrix
B ∈ Zm×n , we denote by Λ(B) the lattice spanned by the row vectors of
B. That is,mnXoΛ(B) =
xi bi |xi ∈ Z, 1 ≤ i ≤ m ,i=1

where bi is the i-th row of B. If the rows of B are linearly independent,
we call B a basis of Λ(B). For a basis
p B, we denote by det (Λ(B)) thedeterminant of the lattice Λ(B) as det (BB T ).
A lattice Λ(B) may have many bases. If B is a nonsingular squarematrix with all entries in Z, then Λ(B) has a special basis in Hermite
Normal Form. In general, a nonsingular square matrix H = (hij ) ∈ Zn×n
is in Hermite Normal Form if1) hij = 0 for 1 ≤ j < i ≤ n;2) hii > 0 for 1 ≤ i ≤ n;3) 0 ≤ hij < hjj for 1 ≤ i < j ≤ n.
Hermite Normal Form of any integer matrix can be computed in polynomial time, and Micciancio [14] suggested publishing the Hermite Normal
Form as the public key which will improve the security of some latticebased cryptosystems.

5

2.2

Lattice problems and algorithms

In lattice theory, the Shortest Vector Problem (SVP) and the Closest
Vector Problem (CVP) are two famous computational problems whichhave been proved to be NP-hard [3, 1]. Given a lattice basis B ∈ Zm×n ,the shortest vector problem aims to find a nonzero shortest vector in
Λ(B), and the closest vector problem aims to find the closest vector to atarget vector t ∈ Zn . We denote by λ1 (Λ(B)) the length of the shortest
nonzero lattice vectors in the lattice Λ(B).
The approximation versions of SVP and CVP are usually used toevaluate the security for lattice-based schemes. For the approximation of
SVP, we need to find a lattice vector v such that kvk ≤ γλ1 , and for theapproximation of CVP, our aim is to find a lattice vector w satisfying
kw − tk ≤ γ minv∈Λ(B) kv − tk with γ ≥ 1.
Some polynomial-time algorithms have been presented to solve approximate SVP and approximate CVP with exponentially large factorγ, such as LLL [12], BKZ [18, 4] for the approximate SVP and Babai’s
nearest plane algorithm [2] for approximate CVP.
LLL algorithm is a polynomial-time lattice reduction algorithm which
was presented in [12]. An important property of this algorithm is theoutput vectors are relatively short. Furthermore, in practice, the output
of LLL algorithm is much better than the theoretical analysis.
Blockwise Korkine-Zolotarev (BKZ) algorithm [18, 4] is also a widelyused lattice reduction algorithm in the analysis for lattice-based cryptosystems. In general, BKZ algorithm has an additional parameter β ≥ 2
as the block size. In the process of BKZ algorithm, a subalgorithm whichfinds the shortest vector of the projective lattice with dimension β is calledat each iteration. Generally speaking, BKZ algorithm will cost more timethan LLL, but the output will be much shorter than that of LLL when β
becomes larger.

3

The PSW digital signature scheme

In PKC’08, Plantard, Susilo, and Win [17] proposed a new digital signature based on CVP∞ , which was claimed to be a countermeasure against
the Nguyen-Regev attack.
3.1

The original signature scheme

The original PSW signature scheme consists of three main steps as thefollowing:6

Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan

Setup
1. Choose an integer n.
2. Compute a random matrix M ∈ {−1, 0, 1}n×n .
3. Compute d = b2ρ(M ) + 1c and D = dIn , where ρ(M ) is the maximum of the absolute value of the eigenvalues of M .
4. Compute the Hermite Normal Form H of the basis D − M .
5. The public key is (D, H), and the secret key is M .
To sign a message m ∈ {0, 1}∗ , one does the following.
Sign
1. Compute the vector v = H(m) ∈ Zn where H is a hash function
which maps m to {x ∈ Zn ||xi | < d2 , 1 ≤ i ≤ n}.
2. By Algorithm 1, compute w as the signature of m.
Algorithm 1 Signing algorithm
Input: A vector v ∈ Zn , the matrix D and M obtained in the Setup step.
Output: A vector w ∈ Zn such that w ≡ v (mod Λ(D − M )) and |wi | < d for alli = 1, 2, · · · , n.
1: w ← v
2: i ← 1
3: k ← 0
4: while k < n do
5:
k←0
6:
q ← d wdi c;7:
wi ← wi − qd8:
for j ← 1 to n do
9:wi+j mod n ← wi+j mod n + qMi,i+j mod n
10:|wi+j mod n | < d11:k ←k+1
12:
end for13:i ← i + 1 mod n
14: end while
15: return w

To verify a message-signature pair (m, w), one does the following.
Verify1. Check if |wi | < d, 1 ≤ i ≤ n.
2. Compute the vector H(m) ∈ Zn .
3. Check if the vector H(m) − w is in the lattice of basis H.

7

3.2

The randomized version of PSW signature scheme

As pointed out by Plantard, Susilo, and Win, since the reduction algorithm is deterministic, the original PSW scheme may suffer some potential side channel attacks. To resist the potential side channel attacks, theysuggest using the following randomized algorithm (Algorithm 2) as thesigning algorithm.
Algorithm 2 Randomized signing algorithm
Input: A vector v ∈ Zn , the matrix D and M obtained in the Setup step.
Output: A vector w ∈ Zn such that w ≡ v (mod Λ(D − M )) and |wi | < d for alli = 1, 2, · · · , n.
1: w ← v$
2: i ←− {1, 2, · · · , n}
3: k ← 0
4: while k < n do
5:
k←0
6:
q ← d wdi c;7:
wi ← wi − qd8:
for j ← 1 to n do
9:wi+j mod n ← wi+j mod n + qMi,i+j mod n
10:|wi+j mod n | < d11:k ←k+1
12:
end for13:i ← i + 1 mod n
14: end while
15: return w

4
4.1

The chosen message attack against the randomized
version of PSW scheme
Key idea of our chosen message attack

As we can see, in the randomized version of the PSW signature scheme,
the signature vectors for the same message may not be unique. Therefore,
in the CMA model, if we query the randomized signing oracle with thesame message m, we may obtain different signature vectors w1 , w2 , · · · , wk
where k ≥ 2. Note that wi − H(m), 1 ≤ i ≤ k are all in the lattice, andso are their difference vectors(wi − H(m)) − (wj − H(m)) = wi − wj ,where 1 ≤ i ≤ j ≤ k.

8Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan

Since each component of wi is in (−d, d), we know that each compo√
nent of wi − wj is in (−2d, 2d). Since d ∈ Θ( n) as stated in [17], thelattice vectors wi − wj ’s are very short.
Once we obtain many such short difference vectors, the Z-linear combinations of these vectors will span the lattice Λ(D − M ). By using thelattice reduction algorithms such as LLL and BKZ to the set of short
generators, we expect to obtain a much shorter basis, which may leak theprivate key.
We present the framework of our attack as the following:
1. Generate some messages m1 , m2 , · · · randomly;
2. For any message mj ∈ {m1 , m2 , · · · }, querying the signing oracle forseveral times to obtain many different signatures {wj1 , wj2 , · · · , wjk }with k ≥ 2;
3. Collect enough difference vectors wji − wj1 ’s such that they can span
the lattice Λ(D − M ). Denote by L the set of these wji − wj1 ’s;
4. Use lattice basis reduction algorithm to L to output a square matrix
LL, and expect to obtain some information about the private key.
4.2

Our strategy to collect the difference vectors

To collect the difference vectors, we have to decide how many messages
we will choose in Step 1 and how many signatures for one message we willquery with the oracle in Step 2. Below we give a very simple but efficient
strategy, that is, for one message we query as many different signatures
as possible and we choose as few messages as possible to satisfy Step 3.
Note that for every message, the signing algorithm (Algorithm 2) will
generate at most n different signatures since there are n choices for theindex i. Assume there were exactly n different signatures, then it is natural
to ask how many times we query the signing oracle to collect all thesesignatures. Since every signature is uniformly randomly returned by theoracle, by the classical result for Coupon Collector’s Problem [15], it canbe easily concluded that the expectation of this number is
n(1 +

1
1
1
1
+ · · · + ) = n ln n + γn + + O( ),2n2nwhere γ ≈ 0.5772156649 is the Euler’s constant. Hence, we can query
one message for dn log ne times, and then we know that the probability
1of collecting all the n signatures is greater than 1 − n− ln 2 +1 [15]. Whenn ≥ 100, this value is greater than 0.85, which is acceptable.

9

Therefore, in our attack we query dn log ne signatures for each message, and choose random messages until we collect enough difference vectors, then applying LLL and BKZ to obtain a short basis for the lattice.
We present the attack as Algorithm 3.

Algorithm 3 Chosen message attack against the randomized version of
PSW scheme
Input: The public key H, the randomized signing oracle O and a message generator
G to generate the messages randomly.
Output: A set of short basis for Λ(H).
1: Let LL be a zero matrix of n × n
2: while det LL/ det H ! = 1 and det LL/ det H ! = −1 do
3:
W = {}
4:m←G
5:
for i ← 1 to dn log ne do6:w ← O(m)7:
If w is not in W, append w to W
8:
end for9:Collect all w1 − wi , 1 ≤ i ≤ |W | to append to the matrix LL
10:
LL ← the last n rows of LLL(LL) (since LLL algorithm puts linearly independent vectors in the last rows)
11: end while
12: B ← LatticeReduction(LL)
13: Check whether B leaks the private key or not.

4.3

Experimental Results

In our experiments, we used SageMath 7.5.1 [21] to implement our attacks, and the LLL’s parameter is set to the default value. For BKZ
algorithm, we set the parameter “algorithm” as “NTL” to call the NTL
library [20] to implement this algorithm. All experiments were run on amachine with Intel(R) Xeon(R) CPU E5-2620 v4 @2.1GHz.
We chose the dimension n to be 200, 300, 400, and for any dimension we chose 5 randomized generated instances. For the lattice reduction
algorithms, we used LLL algorithm, BKZ-10, and BKZ-20 respectively.
The results are listed in Table 1.

10Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan
Table 1. Experimental Results for Our Attack

dim
200
300
400
num 3 2 3 2 3 3 2 22
2 3 4 3 2 3
LLL A P(22) A A P(32) N N N N
N N N NNN
BKZ-10 A A A A A N N P(3) N
N N N NNN
BKZ-20 A A A A A A N A P(4) P(22) N P(2) N N N
1 dim: The dimension of the lattice Λ(D − M );2 num: The number of messages we need to span the latticeΛ(D − M );3 N: The lattice reduction algorithm can not recover any rowsof the matrix D − M ;4 A: The lattice reduction algorithm can recover all rows of

the matrix D − M ;5 P: The lattice reduction algorithm can recover partial rowsof the matrix D − M , and the number in the bracket is thenumber of rows we recovered.
We would like to point out a natural attempt to recover the rows of
D − M is by applying lattice basis reduction algorithm on the public key
H directly, since every row of D − M is very short. However, for justdimension n = 165 in our experiments, we could not recover any row of
D − M when we even applied BKZ-20 on the public key H directly.
In contrast, with our attack, for the dimension n = 200, LLL algorithm
could recover all (or partial) rows of D − M , and BKZ-10 could recover
all the rows of D − M for our instances. For the dimension n = 300,
we could recover all rows of D − M in 2 instances and partial rows in 2
instances when BKZ-20 was used.
For the dimension n = 400, we just obtain partial rows in D − M
for only one instance with BKZ-20 algorithm. Employing BKZ algorithmwith bigger blocksize, we may obtain more rows.
However, we would like to point out that even only partial rows arerecovered, the randomized version of the PSW signature scheme is notsecure. Since the messages are all generated randomly, we may expect torecover all the rows of the matrix D − M by repeating our attack several
times.
Remark 1. Once obtaining a short basis, we can also recover the matrix
M by finding some lattice vector close to (0, · · · , d, · · · , 0). Using somestrategies in [13] to solve the Bounded Distance Decoding (BDD) problem
may improve our results.

11Remark 2. We would like to point out that the strategy to collect thedifference vectors also plays an important role in our attack. Anothernatural strategy is to query the signing oracle just twice for each message
and collect enough difference vectors to mount the attack. However, the
new stategy did not work so well as Algorithm 3. For dimension n = 200
and larger dimensions, we could never recover any rows of the matrix
D − M by using this strategy in our experiments.

5

Possible ways to fix the randomized version

There are two possible ways to fix the randomized version similar to thestrategies in [7].
The first way is to store the message-signature pairs locally, which
seems a bit impractical. In detail, once given a message m, we will modify
the Sign step as the following:
Sign
1. Check whether m has been signed or not.
2. If m is stored locally, return the locally stored signature w corresponding to m.
3. Otherwise, use Algorithm 2 to output a signature w and store (m, w)
locally.
The second way is to add some random number to the hash function.
This strategy is usually used in the hash-then-sign schemes. Since theoriginal PSW scheme has no security proof and we do not know the exact
hardness of CVP∞ over the PSW instances, we can not present someformal security proof for this fixed version, but just present it as thefollowing:
Sign
1. Choose r ← {0, 1}n at random.
2. Compute the vector v = H(m||r), where H maps (m||r) to the area(−d2 , d2 )n .
3. Applying Algorithm 2, compute the signature w.
Once given the signature (m, r, w), we will modify the Verify step as
below.
Verify1. Check if |wi | < d for 1 ≤ i ≤ n.
2. Compute the vector H(m||r).
3. Check whether the vector H(m||r) − w ∈ Λ(H) or not.

12

6

Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan

Conclusions

In this paper, we show that the randomized PSW signature scheme is
not secure under the chosen message attack at least for dimension lessthan or equal to 400. However, for the scheme with bigger dimension
which becomes less efficient apparently, it seems that we need the BKZ
algorithm with bigger blocksize to recover the private key. In fact, ourattack reveals that the storage of previous signature or the use of random
nonce employed in the randomized signature scheme is crucial.

References
1. Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions(extended abstract). In: Proceedings of the Thirtieth Annual ACM Symposium on
Theory of Computing. pp. 10–19. STOC ’98, ACM, New York, NY, USA (1998),
http://doi.acm.org/10.1145/276698.276705
2. Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem.
Combinatorica 6(1), 1–13 (Mar 1986), https://doi.org/10.1007/BF02579403
3. Boas, P.V.E.: Another NP-complete problem and the complexity of computing
short vectors in lattices. Math. Dept. Report 81-04. Univ. of Amsterdam (1981)
4. Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates. In: Lee, D.H.,
Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011: 17th International
Conference on the Theory and Application of Cryptology and Information Security,
Seoul, South Korea, December 4-8, 2011. Lecture Notes in Computer Science,
vol. 7073, pp. 1–20. Springer Berlin Heidelberg, Berlin, Heidelberg (2011), https://doi.org/10.1007/978-3-642-25385-0_1
5. Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures andbimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology –CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA,
August 18-22, 2013. Proceedings, Part I. Lecture Notes in Computer Science, vol.
8042, pp. 40–56. Springer, Berlin, Heidelberg (Aug 2013), https://doi.org/10.
1007/978-3-642-40041-4_3
6. Ducas, L., Nguyen, P.Q.: Learning a zonotope and more: Cryptanalysis of
NTRUSign countermeasures. In: Wang, X., Sako, K. (eds.) Advances in Cryptology– ASIACRYPT 2012: 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012.
Proceedings. Lecture Notes in Computer Science, vol. 7658, pp. 433–450. Springer,
Berlin, Heidelberg (2012), https://doi.org/10.1007/978-3-642-34961-4_27
7. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new
cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. pp. 197–206. STOC ’08, ACM, New York, NY,
USA (2008), http://doi.acm.org/10.1145/1374376.1374407
8. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice
reduction problems. In: Kaliski, B.S. (ed.) Advances in Cryptology - CRYPTO’97: 17th Annual International Cryptology Conference, Santa Barbara, California,
USA, August 17-21, 1997. Proceedings. Lecture Notes in Computer Science, vol.
1294, pp. 112–131. Springer Berlin Heidelberg, Berlin, Heidelberg (1997), https://doi.org/10.1007/BFb0052231

13
9. Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.:
NTRUSign: Digital signatures using the NTRU lattice. In: Joye, M. (ed.) Topics
in Cryptology - CT-RSA 2003: The Cryptographers’ Track at the RSA Conference 2003 San Francisco, CA, USA, April 13–17, 2003 Proceedings. Lecture Notes
in Computer Science, vol. 2612, pp. 122–140. Springer Berlin Heidelberg, Berlin,
Heidelberg (2003), https://doi.org/10.1007/3-540-36563-X_9
10. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) Algorithmic Number Theory: Third International
Symposiun, ANTS-III Portland, Oregon, USA, June 21-25, 1998 Proceedings. Lecture Notes in Computer Science, vol. 1423, pp. 267–288. Springer Berlin Heidelberg,
Berlin, Heidelberg (1998), https://doi.org/10.1007/BFb0054868
11. Klein, P.: Finding the closest lattice vector when it’s unusually close. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. pp.
937–941. SODA ’00, Society for Industrial and Applied Mathematics, Philadelphia,
PA, USA (2000), http://dl.acm.org/citation.cfm?id=338219.338661
12. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rationalcoefficients. Mathematische Annalen 261(4), 515–534 (Dec 1982), https://doi.
org/10.1007/BF01457454
13. Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: An update. In: Dawson,
E. (ed.) Topics in Cryptology – CT-RSA 2013: The Cryptographers’ Track at
the RSA Conference 2013, San Francisco,CA, USA, February 25-March 1, 2013.
Proceedings. Lecture Notes in Computer Science, vol. 7779, pp. 293–309. Springer,
Berlin, Heidelberg (2013), https://doi.org/10.1007/978-3-642-36095-4_19
14. Micciancio, D.: Improving lattice based cryptosystems using the hermite normal
form. In: Silverman, J.H. (ed.) Cryptography and Lattices: International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers. Lecture
Notes in Computer Science, vol. 2146, pp. 126–145. Springer Berlin Heidelberg,
Berlin, Heidelberg (Mar 2001), https://doi.org/10.1007/3-540-44670-2_11
15. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press,
Cambridge (Sep 1995), http://doi.acm.org/10.1145/211542.606546
16. Nguyen, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of GGH and
NTRU signatures. In: Vaudenay, S. (ed.) Advances in Cryptology - EUROCRYPT
2006: 24th Annual International Conference on the Theory and Applications of
Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006. Proceedings. Lecture Notes in Computer Science, vol. 4004, pp. 271–288. Springer Berlin
Heidelberg, Berlin, Heidelberg (2006), https://doi.org/10.1007/11761679_17
17. Plantard, T., Susilo, W., Win, K.T.: A digital signature scheme based on CVP∞ .
In: Cramer, R. (ed.) Public Key Cryptography - PKC 2008: 11th International
Workshop on Practice and Theory in Public-Key Cryptography, Barcelona, Spain,
March 9-12, 2008. Proceedings. Lecture Notes in Computer Science, vol. 4939, pp.
288–307. Springer Berlin Heidelberg, Berlin, Heidelberg (2008), https://doi.org/
10.1007/978-3-540-78440-1_17
18. Schnorr, C.P., Euchner, M.: Lattice basis reduction: Improved practical algorithms
and solving subset sum problems. Mathematical Programming 66(1-3), 181–199(Aug 1994), https://doi.org/10.1007/BF01581144
19. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science.
pp. 124–134. IEEE, Santa Fe, NM, USA (Nov 1994)
20. Shoup, V.: NTL: A library for doing number theory (2001), http://www.shoup.
net/ntl

14

Haoyu LiRenzhang Liu, Abderrahmane Nitaj, and Yanbin Pan

21. Stein, W., et al.: Sage Mathematics Software Version 7.5.1. The Sage Development
Team (2017), http://www.sagemath.org