The weight-one error channel and its application in code-based cryptography
Loading...
Date
2023-09-11
Authors
Thiers, Johann-Philipp
Journal Title
Journal ISSN
Volume Title
Publication Type
Dissertation
Published in
Abstract
Public-key cryptographic algorithms are an essential part of todays cyber security, since
those are required for key exchange protocols, digital signatures, and authentication. But
large scale quantum computers threaten the security of the most widely used public-key
cryptosystems. Hence, the National Institute of Standards and Technology ( NIST ) is currently
in a standardization process for post-quantum secure public-key cryptography. One type of
such systems is based on the NP-complete problem of decoding random linear codes and
therefore called code-based cryptography.
The best-known code-based cryptographic system is the McEliece system proposed in 1978
by Robert McEliece. It uses a scrambled generator matrix as a public key and the original
generator matrix as well as the scrambling as private key. When encrypting a message it is
encoded in the public code and a random but correctable error vector is added. Only the
legitimate receiver can correct the errors and decrypt the message using the knowledge of the
private key generator matrix.
The original proposal of the McEliece system was based on binary Goppa codes, which are
also considered for standardization. While those codes seem to be a secure choice, the public
keys are extremely large, limiting the practicality of those systems. Many different code
families were proposed for the McEliece system, but many of them are considered insecure
since attacks exist, which use the known code structure to recover the private key.
The security of code-based cryptosystems mainly depends on the number of errors added by
the sender, which is limited by the error correction capability of the code. Hence, in order to
obtain a high security for relatively short codes one needs a high error correction capability.
Therefore maximum distance separable ( MDS ) codes were proposed for those systems, since
those are optimal for the Hamming distance.
In order to increase the error correction capability we propose q -ary codes over different
metrics. There are many code families that have a higher minimum distance in some other
metric than in the Hamming metric, leading to increased error correction capability over this
metric. To make use of this one needs to restrict not only the number of errors but also their
value.
In this work, we propose the weight-one error channel, which restricts the error values to
weight one and can be applied for different metrics. In addition we propose some concatenated
code constructions, which make use of this restriction of error values. For each of these
constructions we discuss the usability in code-based cryptography and compare them to other
state-of-the-art code-based cryptosystems.
The proposed code constructions show that restricting the error values allows for significantly
lower public key sizes for code-based cryptographic systems. Furthermore, the use of
concatenated code constructions allows for low complexity decoding and therefore an efficient
cryptosystem.
Description
Faculties
Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
Institutions
Institut für Nachrichtentechnik
Citation
DFG Project uulm
EU Project THU
Other projects THU
License
CC BY 4.0 International
Is version of
Has version
Supplement to
Supplemented by
Has erratum
Erratum to
Has Part
Part of
DOI external
DOI external
Institutions
Periodical
Degree Program
DFG Project THU
item.page.thu.projectEU
item.page.thu.projectOther
Series
Keywords
McEliece cryptosystem, Code-based cryptography, Generalized concatenated codes, Post-quantum public-key cryptography, Post-Quantum-Kryptografie, Public-Key-Kryptosystem, Public key cryptography, DDC 620 / Engineering & allied operations