Header

UZH-Logo

Maintenance Infos

A study of cryptographic systems based on Rank metric codes


Marshall, Kyle Daniel. A study of cryptographic systems based on Rank metric codes. 2016, University of Zurich, Faculty of Science.

Abstract

The ubiquity, dependability, and extensiveness of internet access has seen a migration of local services to cloud services where the advantages of scalability can be efficiently exploited. In doing so, the exposure of sensitive data to eavesdropping is a principal concern. Asymmetric cryptosystems attempt to solve this problem by basing access on the knowledge of a solution to mathematically difficult problems. Shor demonstrated that on a quantum computer, cryptosystems based on the difficulty of factoring integers or solving discrete logarithms were efficiently solvable. As the most ubiquitous asymmetric cryptosystems in modern use are based on these problems, new cryptosystems had to be considered for post-quantum cryptography. In 1978, McEliece proposed a cryptosystem based on the difficulty of decoding random linear codes but the key sizes were too large for practical consideration. These systems, though, do appear to resist Shor’s algorithm and other quantum attacks. More recently, Gabidulin proposed using codes in the rank metric to design secure cryptosystems because they could be designed with smaller parameters. In this direction, many proposals for cryptosystems based on rank metric codes were designed. Overbeck managed to cryptanalyze many of these systems, but there remain several which resist all known structural attacks.
In this work, we investigate the use of rank metric codes for cryptographic purposes. Firstly, we investigate the construction of MRD codes and propose some new constructions based on combinatorial methods. We then generalize Overbeck’s attack and show how our generalized attack can be used to cryptanalyze some of the cryptosystems which were designed to resist the attack of Overbeck. Our attack is based on a new approach of exploiting the structure of low weight elements in the code. Our approach also allows us to extend a result of Gaborit to obtain a polynomial time decoding algorithm for codes with certain parameters. Lastly, we consider the use of codes in the subspace metric– which are based on rank metric codes–in order to create an alternative instance of Juels’ and Sudan’s fuzzy vault primitive.

Abstract

The ubiquity, dependability, and extensiveness of internet access has seen a migration of local services to cloud services where the advantages of scalability can be efficiently exploited. In doing so, the exposure of sensitive data to eavesdropping is a principal concern. Asymmetric cryptosystems attempt to solve this problem by basing access on the knowledge of a solution to mathematically difficult problems. Shor demonstrated that on a quantum computer, cryptosystems based on the difficulty of factoring integers or solving discrete logarithms were efficiently solvable. As the most ubiquitous asymmetric cryptosystems in modern use are based on these problems, new cryptosystems had to be considered for post-quantum cryptography. In 1978, McEliece proposed a cryptosystem based on the difficulty of decoding random linear codes but the key sizes were too large for practical consideration. These systems, though, do appear to resist Shor’s algorithm and other quantum attacks. More recently, Gabidulin proposed using codes in the rank metric to design secure cryptosystems because they could be designed with smaller parameters. In this direction, many proposals for cryptosystems based on rank metric codes were designed. Overbeck managed to cryptanalyze many of these systems, but there remain several which resist all known structural attacks.
In this work, we investigate the use of rank metric codes for cryptographic purposes. Firstly, we investigate the construction of MRD codes and propose some new constructions based on combinatorial methods. We then generalize Overbeck’s attack and show how our generalized attack can be used to cryptanalyze some of the cryptosystems which were designed to resist the attack of Overbeck. Our attack is based on a new approach of exploiting the structure of low weight elements in the code. Our approach also allows us to extend a result of Gaborit to obtain a polynomial time decoding algorithm for codes with certain parameters. Lastly, we consider the use of codes in the subspace metric– which are based on rank metric codes–in order to create an alternative instance of Juels’ and Sudan’s fuzzy vault primitive.

Statistics

Downloads

2 downloads since deposited on 02 Feb 2017
2 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation
Referees:Horlemann-Trautmann Anna-Lena, Kresch Andrew, Rosenthal Joachim
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2016
Deposited On:02 Feb 2017 07:19
Last Modified:28 Feb 2017 04:09
Number of Pages:91
Related URLs:http://www.recherche-portal.ch/ZAD:default_scope:ebi01_prod010745199 (Library Catalogue)

Download

Preview Icon on Download
Content: Accepted Version
Language: English
Filetype: PDF - Registered users only
Size: 728kB

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations