Name
Abstract | ||
|---|---|---|
Given, an integer n-dimensional lattice basis, the random sampling reduction was proven to find a short vector in O(n(2)(k/6)(k/4)) arithmetic steps with an integer k, which is freely chosen by users. This paper introduces new random sampling reduction using precomputation techniques. The computation cost O(k(2) log(2) k(k/6)(k/4) + nk log k) is almost independent of the lattice dimension number. The new method is therefore especially advantageous to find a short lattice vector in higher dimensions. The arithmetic operation number of our new method is about 20% of the random sampling reduction with 200 dimensions, and with 1000 dimensions it is less than 1% (similar or equal to 1/130) of that of the random sampling reduction with representative parameter settings under reasonable assumptions. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1587/transfun.E96.A.150 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
random sampling reduction, precomputation, lattice reduction, size reduction, lattice-based cryptography | Precomputation,Algorithm,Theoretical computer science,Size reduction,Sampling (statistics),Lattice-based cryptography,Mathematics,Lattice reduction | Journal |
Volume | Issue | ISSN |
E96A | 1 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masayuki Yoshino | 1 | 21 | 7.43 |
| Noboru Kunihiro | 2 | 425 | 45.72 |