Lattices and their application in Cryptography

Abstract

The aim of this thesis is to identify the characteristics of lattice-based cryptosys-tems. 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.

Contents

1 Introduction . . 1

1.1 Outline . . 2

2 Mathematical Background 3

2.1 Lattices and Lattice Reduction Problems . . 3

2.1.1 Definitions and Properties . . 3

2.1.2 Lattice Problems . . 11

2.1.3 Lattice-Reduction . . 14

2.2 Asymmetric Cryptosystems and Digital Signatures . . 17

2.2.1 Asymmetric Cryptography . . 17

2.2.2 Digital Signatures . . 18

3 Lattice-based Cryptosystems 19

3.1 GGH-Cryptosystem . . 19

3.1.1 Construction . . 19

3.1.2 Attacks . . 23

3.2 Comparison to other cryptosystems . . 26

44 Conclusion and Future Work . . 29

1 Introduction

The Internet has become an indispensable part in the work and private life. Thus, the necessity for secure communication continues to increase and became one of the most important tasks.

The public-key cryptography was published in 1976 and had awakened much interest. Cryptosystems could be developed based on mathematically hard problems and other applications such as digital signatures were worked out. The RSA is the most popular public-key encryption scheme, which provides convenience with respect to key exchange. It also gives the possibility of authentication.

However, a major risk of asymmetric cryptosystems is the security, which depends on computational problems such as factoring large numbers and discrete logarithm problem. Thus at a point, these systems are insecure.

IIn contrast, the use of lattices introduces problems, which are at least NP-complete and therefore also suitable for the cryptography. This thesis provides an exciting opportunity to advance our knowledge of lattices and some lattice-problems, which are described by working out proofs step-by-step, to present the construction of new cryptosystems and analyze them. Examples are provided to make the material more comprehensible.

1.1 Outline

This thesis is categorized into two parts, which are as follows:

In the second chapter the fundamentals of the lattice-theory will be presented. We introduce lattice basis reduction with the corresponding LLL-algorithm and define latticeproblems that have been proved to be hard. We also provide a brief overview of public-key cryptography and digital signatures.

The third chapter describes the application of lattices in cryptography. We describe the construction of the lattice-based cryptosystem Goldreich-Goldwasser-Halevi and analyze the security in which we present the most effective attacks against it. We will conclude with a comparison to other cryptosystems like RSA.

2 Mathematical Background

In this chapter, the mathematical foundations will be explained, on which the lattice-based cryptography is constructed. In the first section, lattices and some lattice-based problems will be presented. We will also be concerned with the reduction of lattices. The second section provides a brief overview of public-key systems and digital signatures.

2.1 Lattices and Lattice Reduction Problems

The most definitions and theorems are based on the lecture notes of Claus-Peter Schnorr [1] and the lecture notes of Daniele Micciancio [2].

[...]

[1] CLAUS-PETER SCHNORR: Gittertheorie und algorithmische Geometrie, Reduktion von Gitterbasen und Polynomidealen . Johann-Wolfgang-Goethe University, Frankfurt/Main, 1994

[2] DANIELE MICCIANCIO: CSE 206A: Lattice Algorithms and Applications. University of California, San Diego, 2014