Header

UZH-Logo

Maintenance Infos

Considerations on computational lattice problems


Wagner, Urs. Considerations on computational lattice problems. 2013, University of Zurich, Faculty of Science.

Abstract

Lattices are discrete subgroups of the Euclidean space. While they are highly structured objects and their elements can easily be described by means of
integer linear combinations of their basis vectors, it is possible to define NP-hard problems on them. Due to the existence of a class of lattices with favorable worst-case to average-case connection, these problems are well suited as basis for provable secure cryptosystems. The problems appearing in this thesis are the shortest vector problem (SVP), the closest vector problem (CVP) and their approximate versions respectively. All known algorithms that solve these problems exactly run in exponential time, while there are polynomial-time algorithms that solve these problems approximately. The latter ones either perform or are based on basis reduction. Any improvement on these algorithms has direct impact on the security parameters of various cryptographic functions proposed. This thesis contains results on the algorithmic side as well as theoretical considerations. Concerning approximation
of SVP, a polynomial time improvement of LLL |probably the most famous lattice basis reduction algorithm| is presented. Further, improvements on both, an algorithm to solve the SVP exactly and an algorithm to solve the CVP exactly, are given. The first extends the AKS sieve algorithm while the second is a closest point search algorithm based on HKZ bases. The more theoretical results are two-fold: on the one hand, we prove new inequalities on the harmonic, geometric and arithmetic means inequalities if two of the means are known. This leads to new inequalities between the orthogonality defect and the Seysen measure of a lattice basis, both quantifying the reducedness of a basis. On the other hand, the natural density of rectangular unimodular matrices is computed, giving partial answers on the probability that randomly chosen lattice vectors can be completed into a basis or generate the lattice respectively.

Abstract

Lattices are discrete subgroups of the Euclidean space. While they are highly structured objects and their elements can easily be described by means of
integer linear combinations of their basis vectors, it is possible to define NP-hard problems on them. Due to the existence of a class of lattices with favorable worst-case to average-case connection, these problems are well suited as basis for provable secure cryptosystems. The problems appearing in this thesis are the shortest vector problem (SVP), the closest vector problem (CVP) and their approximate versions respectively. All known algorithms that solve these problems exactly run in exponential time, while there are polynomial-time algorithms that solve these problems approximately. The latter ones either perform or are based on basis reduction. Any improvement on these algorithms has direct impact on the security parameters of various cryptographic functions proposed. This thesis contains results on the algorithmic side as well as theoretical considerations. Concerning approximation
of SVP, a polynomial time improvement of LLL |probably the most famous lattice basis reduction algorithm| is presented. Further, improvements on both, an algorithm to solve the SVP exactly and an algorithm to solve the CVP exactly, are given. The first extends the AKS sieve algorithm while the second is a closest point search algorithm based on HKZ bases. The more theoretical results are two-fold: on the one hand, we prove new inequalities on the harmonic, geometric and arithmetic means inequalities if two of the means are known. This leads to new inequalities between the orthogonality defect and the Seysen measure of a lattice basis, both quantifying the reducedness of a basis. On the other hand, the natural density of rectangular unimodular matrices is computed, giving partial answers on the probability that randomly chosen lattice vectors can be completed into a basis or generate the lattice respectively.

Statistics

Downloads

79 downloads since deposited on 12 Mar 2014
8 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation (monographical)
Referees:Rosenthal Joachim, Maze G, Monico C, Climent J
Communities & Collections:07 Faculty of Science > Institute of Mathematics
UZH Dissertations
Dewey Decimal Classification:510 Mathematics
Language:English
Place of Publication:Zürich
Date:2013
Deposited On:12 Mar 2014 09:43
Last Modified:07 Apr 2020 06:44
Number of Pages:95
OA Status:Green
Related URLs:https://www.recherche-portal.ch/permalink/f/5u2s2l/ebi01_prod009989125 (Library Catalogue)

Download

Green Open Access

Download PDF  'Considerations on computational lattice problems'.
Preview
Content: Published Version
Language: English
Filetype: PDF
Size: 834kB