Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method

In this paper we study closest vector problem (CVP) and bounded distance decoding problem (BDD) which arise in cryptanalysis of lattice-based cryptosystems. We propose an algorithm for solving bounded distance decoding (BDD) problem using quantum annealing. We provide estimates for the number of qubits required to run this algorithm for lattices that have Hermite normal form with a single pivot element not equal to 1, and for lattices defined by the public keys of NTRUEncrypt cryptosystem.