Random Sampling Reduction with Precomputation

Masayuki YOSHINO  Noboru KUNIHIRO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.1   pp.150-157
Publication Date: 2013/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.150
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Foundations
random sampling reduction,  precomputation,  lattice reduction,  size reduction,  lattice-based cryptography,  

Full Text: PDF(734.4KB)>>
Buy this Article

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.