REPUBLIC OF SERBIA

MINISTRY OF DEFENCE

www.mod.gov.rs

MINISTRY OF DEFENCE

Material Resources Sector

Defensive Technologies Department

Military Technical Institute

www.vti.mod.gov.rs

A Study of Lattice-based Cryptography

Nikolai Stoianov

Defense Institute, Sofia, Bulgaria, n.stoianov@di.mod.bg

Maya Bozhilova

Defense Institute, Sofia, Bulgaria, m.bozhilova@di.mod.bg

Abstract: Cryptography is one of the most important parts of information security. Most of the asymmetric cryptographic algorithms are based on hard solved mathematical problems. With growing of computer operation speed and with availability of huge amount of computer memory some of these problems look to be solved in near time. In addition exploring physics and in particular developing of quantum computer will dramatically change world of cryptography. So called quantum algorithms of Shor and Grover are facts. These algorithms will break widely used asymmetric algorithm – RSA. Beside this some groups of new algorithms are developed and they seem to be harder to solve with quantum algorithms. This paper presents a study of one group of algorithms based on so called “lattice problems”. Basic mathematical definition are given, explanation of lattice problems (shortest vector problem and closest vector problem) and related cryptographic issue are shown. The most popular cryptographic schemes are explained and a small numeric example for NTRU with public parameters (13, 2 , 31, 2) is given.

Key words: post-quantum cryptography, lattice-based cryptography, NTRU cryptosystem.