The aim of this thesis is to identify the characteristics of lattice-based cryptosystems.
The use of encryption and signature schemes can be insecure considering attacks by a quantum computer and inefficient in the computation time. An alternative cryptography is proposed, which is based on worst-case lattice problems. The security and the hardness of the underlying computational problems will be analyzed by providing collaboration between the linear-algebra, complexity-theory and the public-key cryptography.
Table of Contents
1 Introduction
1.1 Outline
2 Mathematical Background
2.1 Lattices and Lattice Reduction Problems
2.1.1 Definitions and Properties
2.1.2 Lattice Problems
2.1.3 Lattice-Reduction
2.2 Asymmetric Cryptosystems and Digital Signatures
2.2.1 Asymmetric Cryptography
2.2.2 Digital Signatures
3 Lattice-based Cryptosystems
3.1 GGH-Cryptosystem
3.1.1 Construction
3.1.2 Attacks
3.2 Comparison to other cryptosystems
4 Conclusion and Future Work
Objectives and Research Themes
This thesis aims to explore the characteristics of lattice-based cryptosystems as a robust alternative to traditional asymmetric encryption methods, which face potential security risks from quantum computing and computational inefficiencies. The research focuses on the mathematical foundations of lattices and analyzes the hardness of underlying computational problems to evaluate the security of specific lattice-based constructions.
- Mathematical properties of lattices and lattice basis reduction algorithms (LLL-algorithm).
- Analysis of computational hardness in lattice problems such as the Shortest Vector Problem (SVP) and Closest Vector Problem (CVP).
- Construction and security analysis of the Goldreich-Goldwasser-Halevi (GGH) cryptosystem.
- Comparative study of lattice-based schemes versus traditional public-key systems like RSA and NTRU.
- Evaluation of potential security attacks and their impact on system performance.
Excerpt from the Book
3.1.1 Construction
We need a basis B and a reduced basis R of the same lattice such that R has a low dual orthogonality-defect and B has a high dual-othogonality-defect. We first create the reduced basis and then generate the lattice.
There exist two ways to choose R. The simplest way is to choose the entries of the matrix uniformly at random from {−l, ..., l}n×n for some integer bound l (e.g. l = 4). The other way is to generate an almost rectangular lattice, starting from k · l ∈ n and adding noise to each of the vectors. We generate R = R + k · l where R is an uniformly distributed matrix in {−l, ..., l}n×n. The best k is suggested to be about √n · l.
After creating the private basis R we have to generate the public key B from R. By Theorem 2.1.1.4 we know that two bases A and B can generate the same lattice if and only if A = BU for a unimodular matrix U. So we multiply the private basis R by unimodular matrices Ui = Li · Ti, where Li and Ti are upper and lower triangular matrices with diagonal entries in [−1, 1]. This leads to vectors which are larger than the entries of the private basis. At least 4 unimodular matrices are required to prevent recovering the private basis R.
To get a public basis B, we can also transform R by taking one vector of the basis and adding to it a random integer linear combination of the other vectors.
Summary of Chapters
1 Introduction: Provides an overview of the necessity for secure communication and the role of public-key cryptography, introducing lattices as a secure alternative.
2 Mathematical Background: Explains the foundational theory of lattices, including definitions, properties, and the complexity of lattice problems, alongside an overview of existing asymmetric systems.
3 Lattice-based Cryptosystems: Details the construction and security analysis of the GGH-cryptosystem and compares it with other approaches like NTRU and Ajtai-Dwork.
4 Conclusion and Future Work: Summarizes the findings regarding the security and efficiency of lattice-based systems and suggests areas for future improvement.
Keywords
Lattices, Cryptography, Public-key, GGH-cryptosystem, Lattice reduction, LLL-algorithm, Shortest Vector Problem, Closest Vector Problem, Security, Complexity, Asymmetric encryption, Digital signatures, NTRU, Computational hardness, Lattice basis
Frequently Asked Questions
What is the core subject of this thesis?
The thesis examines the application of mathematical lattice theory to modern cryptography, specifically focusing on developing and analyzing public-key systems based on the hardness of lattice problems.
What are the central thematic areas?
The work covers lattice mathematics, basis reduction algorithms, the construction of the GGH cryptosystem, and a security comparison between lattice-based schemes and traditional systems like RSA.
What is the primary research goal?
The primary goal is to determine if lattice-based systems offer a viable, secure, and efficient alternative to classical public-key cryptography in the face of evolving computational threats.
Which scientific methods are employed?
The thesis utilizes theoretical proofs and mathematical derivations, specifically applying complexity theory, linear algebra, and algorithmic analysis to evaluate lattice problems and cryptographic security.
What is covered in the main body of the work?
The main body systematically explores lattice foundations, introduces the LLL-reduction algorithm, details the GGH construction, and performs an attack-oriented security analysis against various dimensions.
Which keywords best characterize this work?
Key terms include Lattices, Cryptography, GGH-cryptosystem, LLL-algorithm, SVP, CVP, Public-key infrastructure, and Computational hardness.
How does the GGH cryptosystem ensure its security?
GGH relies on a trapdoor function where the private key is a "good" (reduced) basis that allows solving the CVP, while the public key is a "bad" basis that makes the CVP computationally infeasible for attackers.
What are the primary findings regarding the security of GGH?
The study concludes that GGH security is dependent on lattice dimensions; specifically, attacks become largely infeasible for dimensions exceeding 150, though key size remains a noted limitation.
- Citation du texte
- Merve Cakir (Auteur), 2014, Lattices and their application in Cryptography, Munich, GRIN Verlag, https://www.grin.com/document/351869
