Keyword Search Result

[Keyword] random sampling reduction(1hit)

1-1hit
  • Random Sampling Reduction with Precomputation

    Masayuki YOSHINO  Noboru KUNIHIRO  

     
    PAPER-Foundations

      Vol:
    E96-A No:1
      Page(s):
    150-157

    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.

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