Error-correcting pairs for a public-key cryptosystem

International Conference on Mathematics: Education, Theory and Application

数学;教育

Pellikaan, Ruud^1 ; Márquez-Corbella, Irene^2

Dept. of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, Eindhoven

5600 MB, Netherlands^1

Dept. of Mathematics, Statistics and O. Research, University of la Laguna, Spain^2

关键词: Algebraic geometry code;    Bounded distance decoding;    Lattice-based cryptography;    Multivariate cryptography;    Post quantum cryptography;    Public key cryptosystems;    Public-key encryption scheme;    Quantum fourier transforms;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/855/1/012032/pdf
DOI  :  10.1088/1742-6596/855/1/012032

学科分类：发展心理学和教育心理学

来源: IOP

【 摘 要 】

Code-based Cryptography (CBC) is a powerful and promising alternative for quantum resistant cryptography. Indeed, together with lattice-based cryptography, multivariate cryptography and hash-based cryptography are the principal available techniques for post-quantum cryptography. CBC was first introduced by McEliece where he designed one of the most efficient Public-Key encryption schemes with exceptionally strong security guarantees and other desirable properties that still resist to attacks based on Quantum Fourier Transform and Amplitude Amplification. The original proposal, which remains unbroken, was based on binary Goppa codes. Later, several families of codes have been proposed in order to reduce the key size. Some of these alternatives have already been broken. One of the main requirements of a code-based cryptosystem is having high performance t-bounded decoding algorithms which is achieved in the case the code has a t-error-correcting pair (ECP). Indeed, those McEliece schemes that use GRS codes, BCH, Goppa and algebraic geometry codes are in fact using an error-correcting pair as a secret key. That is, the security of these Public-Key Cryptosystems is not only based on the inherent intractability of bounded distance decoding but also on the assumption that it is difficult to retrieve efficiently an error-correcting pair. In this paper, the class of codes with a t-ECP is proposed for the McEliece cryptosystem. Moreover, we study the hardness of distinguishing arbitrary codes from those having a t-error correcting pair.