request@qapp.tech
RU
Lattice-based cryptography

Summary

A robust family of quantum-resistant cryptographic algorithms based on the assumed computational complexity of certain integer lattice-related mathematical problems. Such problems underpin most NIST post-quantum competition finalists, such as CRYSTALS-KYBER, NTRU, SABER, CRYSTALS-DILITHIUM, FALCON, as well as certain NIST post-quantum competition alternate finalists, such as FrodoKEM, NTRUprime, and the vast majority of CACR post-quantum competition participants.

Cryptographic algorithms from this family are relatively efficient and generate medium-length keys. However, some of the encryption schemes and key-agreement protocols could potentially make errors, i.e. incorrectly decrypt data. Cryptanalysts aim at finding the optimal set of parameters, which would allow the algorithms to achieve a balance between robustness and performance, simultaneously minimizing the possibility of errors.
    More on the topic

    A lattice is a subset of vectors in a multidimensional Euclidean space, which form a discrete subgroup with respect to the addition operation. Many algebraic problems eventually come down to lattice-based problems; for example, lattice-based algorithmic techniques are widely used for cryptanalyzing classical public-key systems (RSA, DSA). Active research in this area has helped discover a number of complex problems that could become the foundation for quantum-resistant cryptographic algorithms.

    Complex lattice problems include the NP-hard shortest vector (SVP) and closest vector (CVP) problems, the Learning with Errors problem (LWE) and its versions (RLWE), as well as the short integer solution problem (SIS).
      The first design of a lattice-based cryptographic scheme was proposed in 1996 by M. Ajtai and C. Dwork. In 1998 a group of researchers introduces the NTRU scheme, well-working in practice, but lacking a theoretical foundation (its robustness was, however, theoretically proven later). In 2005, O. Regev proposed the LWE problem and based several efficient cryptographic schemes on it; the schemes turned out to be robust both in theory and practice.

      Lattice-based cryptography has experienced notable failures as well, for example, the GGH encryption scheme (Goldreich – Goldwasser – Halevi, 1997) was compromised in 1999 by Ph. Nguyen (Nguyen, 1999).
      Note that the lattice theory could also be applied to homomorphic encryption schemes.

      The advantages of lattice-based cryptographic schemes include a wide variety of research works on the topic, efficiency (the NTRU system has the same level of robustness as classical systems, such as RSA, and is almost just as fast) and a relatively low entry barrier for researchers. However, it is not always possible to get an acceptable parameter size.
        How to implement lattice-based cryptography for business data protection?

        The QApp team attaches great significance to studying lattice-based cryptographic algorithms. Our PQLR SDK library already includes the SABER key encapsulation algorithm and the FALCON cryptographic signature algorithm.