Random Sampling Reduction with Precomputation

Masayuki YOSHINO, Noboru KUNIHIRO

  • Full Text Views

    0

  • Cite this

Summary :

Given an integer n-dimensional lattice basis, the random sampling reduction was proven to find a short vector in 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 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% ( 1/130) of that of the random sampling reduction with representative parameter settings under reasonable assumptions.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.1 pp.150-157
Publication Date
2013/01/01
Publicized
Online ISSN
1745-1337
DOI
10.1587/transfun.E96.A.150
Type of Manuscript
Special Section PAPER (Special Section on Cryptography and Information Security)
Category
Foundations

Authors

Keyword

FlyerIEICE has prepared a flyer regarding multilingual services. Please use the one in your native language.