Abstract:
We consider the problem of constructing a cryptosystem with a public key based
on error-resistant coding. At present, this type of cryptosystems is believed to be able to
resist the advent of quantum computers and can be considered as a method of post-quantum
cryptography. The main drawback of a code-based cryptosystem is a great length of the public
key. Most papers devoted to reducing the cryptosystem key length consisted in replacing the
Goppa codes used in the original cryptosystem with some other codes with a requirement that
the system remains secure against attacks by a quantum computer. Here we propose another
approach to the key length reduction that is stated as a task of a simple description of an
error set which has either errors of weights greater than half the minimum distance or errors
that cannot be corrected without an additional secret knowledge. If a code structure allows
to give such a description of an error set, then the complexity of most attacks (for instance,
information-set decoding) significantly increases.
Fulltext:
PDF file (290 kB)