Criptosistema de McEliece

Abstract

El criptosistema de McEliece es un criptosistema de clave pública basado en codificar un mensaje secreto utilizando como clave pública una matriz generadora de un código corrector de errores y añadiendo un error aleatorio. Dicha matriz generadora se construye multiplicando por una matriz S invertible por la izquierda y una matriz P de permutación por la derecha a otra matriz generadora de estructura conocida. Las matrices S y P se escogen al azar y constituyen la clave privada. Sin ellas, la estructura del código es difícil de adivinar (el código parece escogido al azar), por lo que corregir el error es difícil para un observador no deseado. Con la clave privada, podemos obtener la matriz generadora original, la cual descubre la estructura del código y para la cual se conoce un algoritmo eficiente de corrección de errores. Mediante dicho algoritmo corrector, podemos obtener el mensaje original. Este criptosistema no se utiliza en la actualidad debido al gran tamaño de sus claves. Sin embargo, se ha demostrado que puede resistir ataques que utilizan computación cuántica, en contraste con los criptosistemas actuales, por lo que es un buen candidato para la criptografía post-cuántica.

McEliece’s cryptosystem is a public key cryptosystem based on encoding a secret message using a generator matrix of an error-correcting code as public key and adding a random error. This generator matrix is constructed by multiplying an invertible matrix S on the left and a permutation matrix P on the right to another generator matrix of known structure. The matrixes S and P are chosen randomly and they constitute the private key. Without them, the code structure is difficult to guess (the code seems randomly chosen), so correcting the error is difficult for an unwanted observer. With the private key, we can obtain the original generator matrix, which discovers the code structure and for which an efficient error correcting algorithm is known. Using the said correction algorithm, we can get the original message. This cryptosystem is not currently been used due to the large size of its keys. However, it has been shown to withstand attacks using quantum computing, in contrast to current cryptosystems, making it a good candidate to post-quantum cryptography.