格子簡約アルゴリズムを用いたナップサック暗号への攻撃についての考察

Lattice Reduction Attack on the Knapsack Type Cryptosystem
大庭 翔介 †

Shosuke Oba
Abstract
The subset-sum problem is, for given positive
integers a0 , . . . , an−1 , and M , to find a subsetof the ai that sums up to M. There are known
low-density attacks enabling us to solve almost
all subset-sum problems of density d < 0.9408 in
polynomial time. In this paper, we review thesemethods and perform computer experiments tocompare algorithms to solve subset-sum problems using the L3 -algorithm.

1. Introduction

ツォイクマン トーマス †Thomas Zeugmann
2.1. Subset-Sum Problems
Definition 1. The subset-sum problem is the problem, given a0 , . . . , an−1 ∈ N and M ∈ N as inputs, to∑n−1find x0 , . . . , xn−1 ∈ {0, 1} such that i=0 xi ai = M.
We call a0 , . . . , an−1 in Definition 1 weights. The
subset-sum problem is known to be NP-complete.
Definition 2. For a subset-sum problem with weights
a0 , . . . , an−1 , its density d is defined byd := n/ log2 (max ai ).
iKnapsack cryptosystems are cryptosystems whosesecurity is based on the diﬃculty of the subset-sumproblem. Merkle–Hellman knapsack cryptosystem is
one of the first practical public key cryptosystems. It
is not used anymore, because it has been broken.
Lagarias and Odlyzko [2] proposed an attack for
the Merkle–Hellman knapsack cryptosystem in 1985.
They showed that almost all subset-sum problemsof density d < 0.645 are eﬃciently solvable. Later,
Coster et al. [1] improved this method.
They reduced subset-sum problems to the problem
to find a shortest vector in a lattice (SVP). Here, lattices are sets of all integral combinations of linearly
independent vectors. SVP is NP-hard, but by using
the L3 -algorithm, proposed by Lenstra et al. [3], SVP
can be approximated in polynomial time.
In [2], the authors confirmed that their method behaves well using the L3 -algorithm. However, in theirexperiments the dimension was at most 50 because
the performance of computers at that time was notas high as current. In this paper, we compare thesealgorithm with L3 -algorithm in higher dimensions.
In Section 2, we recall some basic knowledge ofsubset-sum problems and lattices. In Section 3, werecall previous results by Lagarias and Odlyzko[2] andby Coster et al. [1]. In Section 4, a computer experiment is done to compare these algorithms, where weuse the L3 -algorithm to compute a reduced basis.

2. Preliminaries
We recall some basic knowledge about the subsetsum problem and lattices.
† 北海道大学 大学院 情報科学研究科

Graduate School of Information Science and Technology,
Hokkaido University

Regarding the density, it is known that if ai arechosen at random, when density is significantly larger
than 1 then the subset-sum problem has many solutions in general, and when the density is approximately 1 then the most diﬃcult problem arise.

2.2. Lattices
Definition 3. Let b1 , . . . , bn ∈ Rm be n linearly independent vectors. Then, a lattice generated from thesevectors is defined as}{ n∑mxi bi | xi ∈ Z.
L(b1 , . . . , bn ) :=i=1

In Definition 3, the vectors b1 , . . . , bn are called abasis of the lattice.
The L3 -algorithm is a polynomial time algorithm
to transform the input basis to a basis called LLL
reduced basis. These input and output bases generate
the same lattice. Regarding LLL reduced bases, thefollowing theorem is important:
Theorem 1. If b1 , . . . , bn is a LLL reduced basis ofa lattice L with parameter 1/4 < δ < 1, then√∥b1 ∥ ≤ (2/ 4δ − 1)n−1 min ∥x∥.
x∈L\{0}This theorem states that the first basis vector in an
LLL reduced basis is an approximation the shortestvector in the lattice up to an exponential factor.

3. Previous Results
3.1. Lagarias and Odlyzko’s Method
Lagarias and Odlyzko [2] proposed an algorithm
to solve low-density subset-sum problems. Their approach was as follows: For given a0 , . . . , an−1 , and M ,we form the lattice with the basis:
 1 0 ··· 0 bN a0 0N a1 
 0 1 ··· 0 b1  . ..
..
 ..  :=  , (1).
.

0 0 · · · 1 N an−1bn−10 0 ··· 0NMbn√where N is an integer such that N > n/2. If thesubset-sum problem has a solution x0 , . . . , xn−1 , thelattice has a vectorn−1∑x :=xi bi + bn = (x0 , . . . , xn−1 , 0).

random, and generated x0 , . . . , xn−1 ∈ {0, 1} at random such that xi = 1 for exactly n/2 of the xi ’s. For
generated subset-sum problems, we constructed lattice bases, and then we permuted the order of vectors
in the bases. After that, we ran L3 -algorithm on thebases. By permuting the order of vectors in bases,
the L3 -algorithm outputs diﬀerent reduced bases. If
we found a desired form vector in the basis, the run
was a success and halted. If we could not find a solution, repeat these steps at most 10 times.

i=0

Theorem 2. Given subset-sum problem instance, ifa0 , . . . , an−1 are randomly chosen and the densityd < 0.645, above lattice has a vector x as a shortest nonzero vector with suﬃciently high probability.

0.7

solvable density

Furthermore, it is considerably short. Lagarias andOdlyzko [2] proved the following theorem:

LOCJLOSS

0.6
0.5
0.4
0.3
0.2
0.1
0050

We can use L -algorithm to find a shortest nonzero
vector in a lattice. We can find the solution of subsetsum problems by finding the vector x in the LLL reduced basis.

3.2. CJLOSS Method
Coster et al. [1] improved Lagarias and Odlyzko’s [2]method. They made important changes to the latticebasis shown in (1). The vector bn is replaced bybn = (1/2, 1/2, . . . , 1/2, N M ) ,√where N is an integer such that N > n/2. If asubset-sum problem has a solution x0 , . . . , xn−1 , thelattice has the vectorn−1∑x̂ :=xi bi + bn = (x0 − 1/2, . . . , xn−1 − 1/2, 0) .
i=0√
The length of the vector is n/2. It is also considerably short. They proved the following theorem:
Theorem 3. Given subset-sum problem instance, ifa0 , . . . , an−1 are randomly chosen and the densityd < 0.9408, above lattice has a vector x̂ as a shortest
nonzero vector with suﬃciently high probability.

4. Computer Experiments
We performed a computational test to compare
algorithms in Section 3: Lagarias–Odlyzko algorithm, and the CJLOSS algorithm. We used an Intel(R) CoreT M i7-2620M CPU @ 2.70GHz and NTL
10.3.0 [4] for the L3 -algorithm.
In the tests we fixed the dimension n of subsetsum problems and the bit length b of weights. Thenwe generated a0 , . . . , an−1 ∈ {1, . . . , 2b } uniformly at

100150200250300

n3Figure1 Comparing the LO and CJLOSS algorithms

The results are in Fig. 1. As the dimension washigher, the density of solved subset-sum problems decreased in both of algorithms. This is mentioned in[2], and they conjectured the density of solved subsetsum problems goes to 0 as n goes to infinity. This
result also suggests it. Success rates of the CJLOSS
algorithm are higher than of the Lagarias-Odlyzko algorithm, as well in high dimensions.
In all results, the density of solved subset-sum problems fall much below the theoretical bound in highdimensions. The density of almost all of subset-sum
problems are solved seems to be in inverse proportion
to dimension. It is considered that the L3 -algorithm
can find much short vectors in low dimensions, but its
performance degrades as the dimension goes higher.
To find a shortest vector, further devising may beneeded.

References[1] M. J. Coster, A. Joux, B. A. LaMacchia, A. M.
Odlyzko, C.-P. Schnorr, and J. Stern. Improved
low-density subset sum algorithms. computational
complexity, 2(2):111–128, 1992.
[2] J. C. Lagarias and A. M. Odlyzko. Solving lowdensity subset sum problems. Journal of the Association for Computing Machinery, 32(1):229–246,Jan. 1985.
[3] A. Lenstra, H. Lenstra, and L. Lászlo. Factoringpolynomials with rational coeﬃcients. Mathematische Annalen, 261:515–534, 1982.
[4] V. Shoup. A library for doing number theory. version 10.3.0. http://www.shoup.net/ntl.