Some Mathematical Problems Behind Lattice-Based Cryptography

Chuanming Zong

doi:10.3390/cryptography10010010

Return

Some Mathematical Problems Behind Lattice-Based Cryptography

2026-02-12

Chuanming Zong *

DOI：10.3390/cryptography10010010

Original

Save

View PDF

Abstract

En 中文

In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, D-Wave demonstrated the first quantum computer. These events and further developments have brought a crisis to secret communication. In 2016, the National Institute of Standards and Technology (NIST) launched a global project to solicit and select a handful of encryption algorithms with the ability to resist quantum computer attacks. In 2022, it announced four candidates, CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+, for post-quantum cryptography standards. The first three are based on lattice theory and the last on a hash function. The security of lattice-based cryptosystems relies on the computational complexity of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. As we will explain, the SVP is a ball-packing problem, and the CVP is a ball-covering problem. Furthermore, both the SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. This paper will briefly describe the mathematical problems on which lattice-based cryptography is built so that cryptographers can extend their views and learn something useful.

Keywords:

lattice

shortest vector problem

closest vector problem

lattice ball packing

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.