Seishiro Terada
In recent years, research has been conducted on quantum computers, which specialize in parallel computation on a scale that cannot be achieved with classical computers, and it is believed that quantum computers can be used to solve prime factorization and discrete logarithm problems in polynomial time. currently widely used public key cryptographic schemes such as RSA cryptography and elliptic curve cryptography Since cryptography is based on computational problems such as those described above, it can be deciphered in realistic time. Therefore, there is a growing demand for Post Quantum Cryptography (PQC) that can withstand decoding by quantum computers. Among them, lattice cryptography, which have been selected the most in the PQC standardization project of the National Institute of Standards and Technology (NIST), are attracting attention. In general, cryptosystems based on lattice cryptography use ideal lattices with the properties of ideals to speed up computation and reduce key size. In this study, we examine the shortest vector problem (SVP), which is the basis for the security of lattice cryptography. We analyze the computational difficulty of SVP by improving the Sieve algorithm, which is currently one of the fastest SVP decryption algorithms. In particular, we will exploit the property of ideal lattices that multiplication over lattice vectors is also a lattice vector on the same lattice, thereby reducing the space complexity, which is a problem of the Sieve algorithm.
Keyword: Lattice cryptography, shortest vector problem, ideal lattice, sieve algorithm
