Criptossistema de McEliece

Na criptografia, o criptossistema de McEliece é um algoritmo de criptografia assimétrica desenvolvido em 1978 por Robert McEliece. Foi o primeiro esquema desse tipo a usar aleatorização no processo de criptografia. O algoritmo nunca ganhou muita aceitação na comunidade criptográfica, mas é um candidato para a "criptografia pós-quântica", pois é imune a ataques usando o Algoritmo de Shor e – de forma mais geral – à medição de estados de classes laterais (cosets) usando amostragem de Fourier. O algoritmo baseia-se na dificuldade de decodificar um código linear genérico (problema que se sabe ser NP-difícil). Para a descrição da chave privada, um código de correção de erros é selecionado, para o qual se conhece um algoritmo de decodificação eficiente, e que seja capaz de corrigir t {\displaystyle t} erros. O algoritmo original usa códigos de Goppa binários (códigos de subcorpos de códigos de geometria algébrica de uma curva de gênero 0 sobre corpos finitos de característica 2); esses códigos podem ser decodificados eficientemente, graças a um algoritmo de autoria de Patterson. A chave pública é derivada da chave privada disfarçando o código selecionado como um código linear genérico. Para isso, a matriz geradora G {\displaystyle G} do código é perturbada por duas matrizes invertíveis selecionadas aleatoriamente, S {\displaystyle S} e P {\displaystyle P} (veja abaixo). Existem variantes deste criptossistema que utilizam diferentes tipos de códigos. A maioria deles provou ser menos segura; foram quebrados por decodificação estrutural. O McEliece com códigos de Goppa tem resistido à criptoanálise até o momento. Os ataques mais eficazes conhecidos usam algoritmos de decodificação de conjunto de informações. Um artigo de 2008 descreve tanto um ataque quanto uma correção. Outro artigo mostra que, para a computação quântica, os tamanhos de chave devem ser aumentados por um fator de quatro devido a melhorias na decodificação de conjunto...