%% ------------------------------------------------------------------------- %%
%!TEX root = quali.tex

\chapter{Proposta}
\label{cap:introducao}

\section{Introdução}
O esquema de chave pública de McEliece \cite{mceliece1978} foi o primeiro baseado em códigos corretores de erros,
e também o primeiro a usar um procedimento aleatório para a encriptação \cite{menezes1996handbook}.
Tanto a encriptação quanto a decriptação são computacionalmente mais eficientes que as respectivas
de outros esquemas baseados no problema do logaritmo discreto. Além disso, o esquema é baseado no problema
\cNP-difícil da decodificação por síndrome \cite{berlekamp1978inherent}, que é conjecturado tipicamente difícil, e é teoricamente
mais difícil que o problema do logaritmo discreto. Porém, os 2 fatores a seguir foram críticos para
que o esquema recebesse pouca atenção na época de sua publicação.

\begin{itemize}
    \item As chaves públicas são muito grandes. Para níveis de segurança
    maiores do que 100, têm tamanho maiores do que 100
    quilobytes~\cite[Tabela 1.1]{bernstein2013mcbits}.

    \item A crença na impossibilidade de um esquema de assinatura sobre ele, justificada
    pelo próprio McEliece. Porém em 2001, Courtois, Finiasz, e Sendrier~\cite{courtois2001achieve}
    mostram como construir um tal esquema de assinatura.
\end{itemize}

Depois de anos sem atenção, o esquema de McEliece passa a ser estudado pois, ao contrário do RSA
\cite{rsa1978rsa} e das Curvas Elípticas \cite{miller1986ecc}, esse esquema resiste a ataques quânticos
baseados no algoritmo de Peter Shor \cite{shor1997poly}.
Com o avanços da computação quântica, os principais algoritmos de chave pública em
uso ficam cada vez mais vulneráveis, o que justifica as buscas por algoritmos criptográficos
resistentes a ataques quânticos. Essa busca dá origem à área chamada Criptografia Pós-Quântica,
que estuda, além de esquemas baseados em códigos corretores de erros, esquemas baseados em \emph{hashes},
reticulados, e equações quadráticas multivariadas \cite{bernstein2009post}.


Os principais esquemas de chave pública baseados em códigos corretores de erros são os de McEliece~\cite{mceliece1978}
e de Niederreiter~\cite{niederreiter1986knapsack}.
Os esquemas têm segurança equivalente quando o adversário não tem nenhuma informação sobre a mensagem transmitida,
ou quando são usadas conversões IND-CCA2~\cite{kobara2001semantically}.
E, tanto por ser mais antigo, quanto por ser mais facilmente descrito, os resultados apresentados
nas próximas seções são baseados no esquema de McEliece.

%\subsection{Esquema de McEliece}

No esquema de McEliece, a chave secreta de Alice é um código linear $\mathcal{G}$ com capacidade de
correção de $t$ erros para o qual Alice conhece um decodificador eficiente. A chave pública de Alice,
é uma matriz geradora de $\mathcal{G}$, possivelmente embaralhada de forma que seja difícil usá-la para
recuperar um decodificador para $\mathcal{G}$. Para mandar uma mensagem $\vec{m}$ a Alice,
codifique $\vec{m}$ usando a chave pública de Alice e adicione $t$ erros à codificação, obtendo $c$. Então Alice, que
é a única portadora de um decodificador eficiente para $\mathcal{G}$, decodifica $c$ e obtém $\vec{m}$.

%\subsection{Escolha da família de códigos}


Uma das principais linhas de pesquisa em Criptografia com códigos corretores de erros é diminuir o tamanho das chaves
 do esquema de McEliece através da escolha adequada da família de códigos associada.
Originalmente, McEliece sugeriu o uso de códigos de Goppa binários e
irredutíveis, que, apesar de não sofrerem ataques críticos, resultam em grandes chaves. O motivo principal
por que códigos de Goppa, de taxa\footnote{A taxa de um código linear de dimensão $k$ e comprimento $n$ é igual a $k/n$.}
não não muito alta~\cite{faugere2013distinguisher}, ainda resistem aos ataques é que não se conhece algoritmo eficiente para
distinguir entre matrizes geradoras de códigos de Goppa e de matrizes geradoras de códigos aleatórios.
Algumas
outras famílias de códigos foram propostas, como as dos códigos BCH quase cíclicos~\cite{gaborit2005shorter},
alternantes quase cíclicos~\cite{berger2009reducing}, códigos LDPC~\cite{shokrollahi2000using}, e códigos de
Goppa quase diádicos~\cite{misoczki2009compact}. Apesar de obterem uma boa redução do comprimento da chave,
todas foram mostradas inseguras depois de alguns anos~\cite{otmani2010cryptanalysis, faugere2010algebraic, faugere2016structural}.

Em 2013, uma nova variante do Esquema de McEliece, chamada QC-MDPC McEliece, foi proposta por
Misoczki et al.~\cite{misoczki2013mdpc}. Esta variante promete chaves públicas de 4801 bits
para um nível de segurança de 80-bits, e tem uma boa redução de segurança.
A iniciativa europeia PQCRYPTO, para o desenvolvimento de criptografia pós-quântica,
na revisão de 2015 de seu documento com recomendações de esquemas pós-quânticos~\cite{augot16initial},
considera essa variante como ``sob análise'', junto com a variante Stehlé-Steinfeld~\cite{stehle2011making} do
esquema NTRU~\cite{hoffstein1998ntru}.


Até meados de 2016, o QC-MDPC McEliece não sofrera ataques críticos. Porém, na conferência Asiacrypt de 2016,
Guo, Johansson, e Stankovski~\cite{guo2016key} mostram um ataque de reação eficiente para a
recuperação de chave de um esquema QC-MDPC. O ataque de reação contra o QC-MDPC McEliece se baseia no fato de que os decodificadores
de códigos QC-MDPC são iterativos e podem falhar, e, quando isso ocorre, o destinatário pede para o remetente
reenviar a mensagem com outro erro inserido. A observação dos autores é que
a probabilidade de o decodificador falhar para um erro $\vec{e}$ é significativamente menor quando $\vec{e}$ e
a chave secreta compartilham certas propriedades. Assim, uma atacante pode enviar um grande número de mensagens
encriptadas a Alice de forma a extrair informações que serão usadas para reconstruir a sua chave privada.

A chave secreta do esquema QC-MDPC McEliece é um vetor de $n$ posições e peso $w$, denotado por $\vec{h}$. Porém
basta descobrir a primeira metade de $\vec{h}$, denotado por $\vec{h}_0$, e usar a chave pública para recuperar
a chave privada, como pode ser visto na Seção~\ref{cap:mdpc}. O ataque de reação recupera o conjunto
de distâncias circulares entre entradas não nulas de $\vec{h}_0$, chamado seu espectro, e usa esse espectro para
reconstruir a chave. Como exemplo, o espectro do vetor $[1\, 1\, 0\, 0\, 0\, 1\, 0]$ é o conjunto
$\{ 1, 2, 3 \}$. Note que a distância entre as posições 1 e 6 não é 5, mas sim 2, pois trata-se de distâncias
circulares, que para um vetor $v$, sempre são menores do que $\|v\|/2$.

\paragraph{}

Nosso objetivo é analisar o ataque de reação contra o QC-MDPC McEliece sob as três perspectivas discutidas a seguir.

\paragraph{Reconstrução de \hz com o espectro recuperado com erros}
    \mbox{}

    O algoritmo de reconstrução de \hz mostrado pelos autores do ataque precisa
    que o espectro tenha sido recuperado sem erros. Dependendo do decodificador
    usado, pode ser que sejam necessários muitos pedidos de decodificação para
    obter a separação entre as classes de erros.

\paragraph{Diminuir o número de decodificações necessárias para atacar conversões CCA2}
    \mbox{}

    Este objetivo engloba o anterior, pois, se houver meios de reconstruir \hz
    mesmo com erros de recuperação do espectro, o ataque aplicado a conversões
    CCA2 ficaria mais eficiente.

\paragraph{Atacar QC-MDPC McEliece com decodificadores por decisões suaves}
    \mbox{}

    Os autores do ataque de reação conjecturaram que o ataque serviria para
    o QC-MDPC McEliece implementado com decodificação com decisões suaves.
    Pelos nossos testes, também conjecturamos que esses decodificadores podem
    ser atacados. E se esse for o caso, a variante \emph{Soft McEliece}~\cite{baldi2016soft}
    também deve ser mostrada insegura.

\section{O que foi feito}

Nesta seção, trato em alto nível do que fizemos até agora. Os resultados e detalhes de implementação
requerem certos pré-requisitos sobre o ataque de reação aos códigos QC-MDPC, portanto não caberiam aqui. Assim
a Seção~\ref{cap:resultados} ao final desse texto é dedicada aos resultados preliminares.

\subsection{Seminários}

Desde que começamos a estudar o esquema de McEliece, apresentei os seguintes seminários internos,
de que participaram o Professor Routo, seu aluno de iniciação científica Gervásio,
e nosso colega doutorando Gláucio, que é aluno do professor Paulo Barreto.

\begin{enumerate}
    \item Códigos de Goppa binários e irredutíveis.
    \item Esquema de McEliece.
    \item Ataque por criptanálise algébrica aos Códigos de Goppa quase $p$-ádicos.
    \item Conversões de segurança para o Esquema de McEliece.
    \item Ataque de reação contra o QC-MDPC McEliece.
\end{enumerate}

Também cursei uma disciplina de segurança da informação na Escola Politécnica, ministrada pelo
Professor Marcos Simplício, em que apresentei um seminário sobre o esquema de McEliece, e um artigo
sobre este trabalho. Todo o material elaborado para a matéria está disponibilizado em
\url{github.com/thalespaiva/segurinfo}.

\subsection{Código}

Até agora, escrevi código em C, SageMath, e Python 3 para implementar:
\begin{enumerate}
    \item o esquema de McEliece com códigos de Goppa em SageMath;
    \item a criação, codificação e decodificação de códigos LDPC, MDPC, e QC-MDPC em C e SageMath;
    \item o ataque de reação aos códigos QC-MDPC em C.
\end{enumerate}

Quando possível, usei SageMath ou Python 3 pois o código é mais legível, e potencialmente mais didático.
Mas como o ataque de reação é computacionalmente custoso, implementei em C,
usando OpenMP para definir partes concorrentes.

\subsection{Dissertação}

Boa parte das próximas seções devem fazer parte da dissertação, embora aqui apareçam de forma
resumida, com seções mescladas. A monografia está em constante evolução no repositório
\url{github.com/thalespaiva/msc}. A estrutura esperada e curtas explicações de
cada seção são dadas a seguir.


\begin{mdframed}
\scriptsize{
\begin{description}
    \item[1 Introdução] \mbox{}

    \item[2 Preliminares] \mbox{}

    \item[3 Fundamentos da Teoria de Códigos] \mbox{}
    \begin{description}
        \item[3.1 Teoria de Códigos] \mbox{}

        Introduz os conceitos básicos de Teoria de Códigos, como espaço de mensagens,
        códigos identificadores ou corretores de erros, codificação e decodificação, canais ruidosos.

        \item[3.2 Modelos de Canais Ruidosos] \mbox{}

        Define os dois modelos de canal ruidoso que são úteis para a criptografia: canal binário simétrico
        e canal de ruído branco gaussiano aditivo. O primeiro modelo é usado em praticamente todas as variantes
        do esquemas de McEliece. O segundo modelo é usado apenas no esquema de McEliece com erros
        suaves, ou contínuos, de Baldi~\cite{baldi2016soft}.

        \item[3.3 Códigos Lineares] \mbox{}

        Define conceitos fundamentais como códigos lineares, peso, e
        distância de Hamming. Mostra cotas para distâncias, e capacidade de correção de códigos lineares.
        Também define os principais problemas como a decodificação por síndrome, e a busca por palavras
        de baixo peso.

    \end{description}
    \item[4 Algumas Famílias de Códigos Notáveis] \mbox{}
    \begin{description}
        \item[4.1 Códigos de Repetição] \mbox{}

        Essa curta seção define os códigos de repetição. Apesar de simples, esta
        seção não só tem caráter didático, pois ajuda o leitor a se familiarizar,
        com códigos lineares, mas será útil na análise dos decodificadores de códigos
        LDPC por passagem de mensagem. Isso pois nós de variáveis nos grafos de Tanner
        de códigos LDPC, ou MDPC, são vistos como decodificadores de códigos de
        repetição \cite[pg. 214]{ryan2009channel}.

        \item[4.2 Códigos de Verificação Única de Paridade] \mbox{}

        A justificativa é similar à da seção anterior, com a diferença de que códigos
        de verificação única de paridade estão relacionados aos nós de verificação
        em grafos de Tanner de códigos LDPC.

        \item[4.3 Códigos Quase Cíclicos] \mbox{}

        Introduz os códigos quase cíclicos, que são a principal forma usada para
        diminuir as chaves públicas nos esquemas de McEliece, como em códigos QC-MDPC.

        \item[4.4 Códigos de Goppa] \mbox{}

        Introduz os códigos algébricos de Goppa usados no esquema original de McEliece,
        mostrando sua capacidade de correção,
        o algoritmo de decodificação de Patterson \cite{patterson1975algebraic}, e
        mostrando como gerar instâncias aleatórias.

        \item[4.5 Códigos LDPC] \mbox{}

        Define os códigos LDPC de Gallagher~\cite{gallager1962low}, mostrando como
        gerar instâncias aleatórias, mostrando decodificadores por passagem de mensagem,
        tanto por decisão abrupta quanto por decodificação suave.

    \end{description}
    \item[5 Esquemas de McEliece e Niederreiter] \mbox{}
    \begin{description}
        \item[5.1 Esquema de McEliece] \mbox{}

        Apresenta detalhadamente o esquema original de McEliece. Discute os tamanhos das chaves.

        \item[5.2 Esquema de Niederreiter] \mbox{}

        Similar à seção anterior para o esquema de Niederreiter.

        \item[5.3 Segurança dos Esquemas] \mbox{}
        \begin{description}
            \item[5.3.1 Equivalência entre dois Esquemas] \mbox{}

                Mostra como o esquema de McEliece tem segurança equivalente à
                do esquema de Niederreiter, que pode ser visto como o seu dual.

            \item[5.3.2 Redução de Segurança] \mbox{}

                Discute as hipóteses em que é baseada a segurança do esquema de McEliece e mostra
                a redução do problema da decodificação ao problema de quebrar um texto cifrado no
                esquema de McEliece.

            \item[5.3.3 Possíveis Ataques ao Esquema de McEliece Original] \mbox{}

                Mostra os ataques não-críticos e críticos. Os não críticos
                são por decodificação por conjunto de informação,
                e busca por palavras de baixo peso. Os críticos são ataques
                de decodificação com informação parcial sobre a mensagem, ou ataques
                de reação \cite{sun2000further, kobara2001semantically}. Mostrando que o e
            \item[5.3.4 Conversões de Segurança] \mbox{}

                Discute por que o esquema de McEliece não pode ser usado, a menos que para
                troca de chaves, sem uma conversão de segurança. E mostra ao menos duas conversões,
                como as $\alpha$ e $\gamma$
                de Kobara e Imai~\cite{kobara2001semantically}, que transformam o esquema
                de McEliece num esquema IND-CCA2. Sugiro mostrar a $\alpha$ por simplicidade,
                e a $\gamma$ pois é a mais eficiente. Ambas são mostradas seguras sob
                o modelo de Oráculos Aleatórios.
        \end{description}
    \end{description}
    \item[6 Algumas Variantes com Chaves Compactas Quebradas] \mbox{}
        Mostra variantes como as que usam códigos de Goppa Quase Cíclicos,
        códigos de Goppa Quase p-ádicos, e códigos LDPC. A ideia é dar ao leitor
        certa intuição sobre os tipos de vulnerabilidade que esquemas de McEliece
        com chaves compactas podem ter.
    \item[7 Esquema de McEliece com códigos QC-MDPC] \mbox{}
    \begin{description}
        \item[7.1 Códigos QC-MDPC] \mbox{}

            Introduz os códigos QC-MDPC. Mostra algoritmos para a construção,
            codificação, e decodificação usando esses códigos.
        \item[7.2 QC-MDPC McEliece] \mbox{}

            Mostra como usar os códigos QC-MDPC no esquema de McEliece, e compara
            com o esquema de McEliece original. Mostra os tamanhos de chave e
            discute a sua redução de segurança.

        \item[7.3 Ataque de Reação aos Códigos QC-MDPC] \mbox{}

            Introduz o ataque de reação ao QC-MDPC McEliece. Discute o desempenho
            do ataque e possíveis melhorias.

    \end{description}

    \item[8 Melhorias sobre o Ataque de Reação] \mbox{}
    
        Mostra nossas propostas de modificação do algoritmo. Faz tanto a análise
        teórica quanto a prática dos algoritmos modificados.


    \item[9 Conclusão] \mbox{}

\end{description}
}
\end{mdframed}

\section{O que será feito}

\newcommand{\mybar}[1]{\ganttbar[bar label node/.append style={align=right}]{#1}}

\fbox{
\begin{ganttchart}[
hgrid,
vgrid,
x unit=10mm,
y unit chart=15mm,
time slot format=isodate-yearmonth,
compress calendar,
canvas/.style={draw=none}
]{2016-12}{2017-08}
\gantttitlecalendar{year, month} \\
\mybar{Análise da reconstrução  \ganttalignnewline da chave com erros}{2016-12}{2017-02} \\
\mybar{Simulação com \ganttalignnewline decodificadores SPA}{2016-12}{2017-02} \\
\mybar{Análise do ataque \ganttalignnewline contra decodificadores SPA}{2017-01}{2017-03} \\
\mybar{Simulações do ataque  \ganttalignnewline contra conversão CCA2}{2017-01}{2017-03} \\
\mybar{Análise do ataque  \ganttalignnewline contra conversão CCA2}{2017-02}{2017-04} \\
\mybar{Qualificação}{2017-02}{2017-02} \\
\mybar{Documentação das \ganttalignnewline implementações}{2017-06}{2017-08} \\
\mybar{Preparação \ganttalignnewline da defesa}{2017-06}{2017-08} \\
\mybar{Defesa}{2017-08}{2017-08} \\
\mybar{Escrita da dissertação}{2016-12}{2017-08}
\end{ganttchart}
}


\section{Alguns resultados elementares de Teoria de Códigos}

O esquema de McEliece é baseado em códigos corretores de erros, que são
meios eficientes de transmitir mensagens, de uma fonte a um receptor,
através de um canal, possivelmente ruidoso.
Quando um canal de transmissão não é ruidoso, a meta é codificar uma mensagem
de modo que a mensagem transmitida tenha o mínimo possível de
símbolos, e a mensagem original possa ser decodificada da transmitida.
Por sua vez, numa transmissão feita por um canal ruidoso, a meta é codificar
a mensagem de modo que a mensagem original possa ser recuperada, mesmo que
alguns símbolos sejam alterados por conta de ruídos intrínsecos ao canal.

A Figura~\ref{fig:codific_canal_gen} exemplifica a transmissão de uma mensagem $\vec{m}$
por um canal ruidoso. Na figura, $\mathcal{M}$ é o conjunto de mensagens possíveis,
$E$ é o algoritmo de codificação, $\vec{e}$ é o erro aleatório do canal adicionado bit a bit
a $\vec{c}$, e $D$ é o algoritmo de  decodificação. Naturalmente, espera-se que
$E$ e $D$ rodem em tempo polinomial, e $E$ é tipicamente determinístico, enquanto
$D$ pode ser probabilístico. Idealmente, queremos que $\vec{m} = \hat{m}$ ao final da transmissão.
Porém, se o erro $\vec{e}$ fizer $\vec{c'}$ ser muito diferente de $\vec{c}$, pode ser que o
algoritmo $D$ não seja capaz de recuperar a mensagem $\vec{m}$ corretamente.

\usetikzlibrary{calc,trees,positioning,arrows,chains,shapes.geometric,%
decorations.pathreplacing,decorations.pathmorphing,shapes,%
matrix,shapes.symbols}

\tikzstyle{rec}=[draw, minimum height=2em]
\begin{figure}[h]
\centering
\begin{tikzpicture}[auto]
  \node [rec] (fonte) {Fonte};
  \node [rec] (codif) [below of=fonte, node distance=2.3cm] {Codificador};
  \node [rec] (canal) [right of=codif, node distance=3cm] {Canal};
  \node [rec] (decod) [right of=canal, node distance=3cm] {Decodificador};
  \node [rec] (recep) [above of=decod, node distance=2.3cm] {Receptor};

  \path[->] (fonte) edge node {$\vec{m} \in \mathcal{M}$} (codif);
  \path[->] (codif) edge node [below=10pt]{$\vec{c} \gets E(\vec{m})$} (canal);
  \path[->] (canal) edge node [below=10pt]{$\vec{c}' \gets \vec{c} \oplus \vec{e}$} (decod);
  \path[->] (decod) edge node {$\hat{\vec{m}} \gets D(\vec{c'})$} (recep);

\end{tikzpicture}
\caption{Transmissão de uma palavra $\vec{m}$ através de um canal ruidoso.}
\label{fig:codific_canal_gen}
\end{figure}


\begin{definition}
    Um \emph{código binário $[n, k]$-linear} é um subespaço vetorial de dimensão $k$
    do espaço $\mathbb{F}_2^n$.
\end{definition}

Por serem subespaços vetoriais, códigos lineares têm representações compactas
através da imagem de matrizes, ou equivalentemente, através do núcleo de matrizes.
Destas representações, seguem naturalmente as seguintes definições.

\begin{definition}
    Seja $\mathcal{C}$ um código binário $[n, k]$-linear. Se $\mathcal{C}$ for igual ao espaço gerado por
    combinações lineares das linhas de uma matriz $G$ de $\Fb ^{k \times n}$, dizemos que $G$ é uma \emph{matriz
    geradora} de $\mathcal{C}$.

    Analogamente, se $\mathcal{C}$ é o núcleo de uma matriz $H$ de  $\Fb^{n - k \times n}$,
    dizemos que $H$ é uma \emph{matriz de paridade} de $\mathcal{C}$.
\end{definition}

Assim, se $G$ e $H$ são matrizes geradoras quaisquer de um código $[n, k]$-linear $\mathcal{C}$, temos que:
$$
\mathcal{C} = \{ \vec{m}G : \vec{m} \in \Fb^k \} = \{ \vec{c} \in \Fb^n : \vec{c}H^T = 0 \}.
$$

Uma matriz de paridade tem esse nome pois, para um vetor $\vec{c} = [c_1 \ldots c_n ]$ pertencer a um código que admite
matriz de paridade $H$, as seguintes equações devem ser satisfeitas:
\[
\begin{array}{ccccccccc}
    c_1h_{11} & \oplus & c_2h_{12} & \oplus & \ldots & c_nh_{1n} & \oplus & = & 0 \\
    c_1h_{21} & \oplus & c_2h_{22} & \oplus & \ldots & c_nh_{2n} & \oplus & = & 0 \\
    \vdots    &        & \vdots    &        & \ldots &           & \oplus & = & \vdots \\
    c_1h_{r1} & \oplus & c_2h_{r1} & \oplus & \ldots & c_nh_{rn} & \oplus & = & 0
\end{array}
\]
que por serem equações sobre $\Fb$, são ditas equações de paridade.


Para verificar se um dado vetor pertence a um código, podemos multiplicar à esquerda por $H^T$
e ver se chegamos ao vetor 0 ou não. Mas para a decodificação, muitas vezes é útil saber quais as
equações de paridade que não são satisfeitas por um dado vetor, que é o conceito de síndrome.

\begin{definition}
    A \emph{síndrome} de um vetor $\vec{v}$, denotada por $s(\vec{v})$, em relação a um código que admite matriz
    de paridade $H$,  é
    $$
        s(\vec{v}) = \vec{v}H^T.
    $$

    Claro que a síndrome de um vetor é 0 se e somente se este vetor pertence ao código.
\end{definition}



Dois conceitos importantes para o estudo de códigos são o de peso e distância. Com eles,
podemos tratar de $\Fb^{n}$ como um espaço métrico.

\begin{definition}
    O \emph{peso de Hamming} de um vetor $\vec{v}$, denotado por $\weight(\vec{v})$, é o número total de suas coordenadas
    não nulas.

\end{definition}
\begin{definition}
    A \emph{distância de Hamming} entre dois vetores $\vec{u}$ e $\vec{v}$, denotada por $\dist(\vec{u}, \vec{v})$,
    é o número total de coordenadas em que $\vec{u}$ e $\vec{v}$ diferem. Equivalentemente
    $\dist(\vec{u}, \vec{v}) = \weight(\vec{u} \oplus \vec{v})$.
\end{definition}

Agora estamos aptos a definir um problema fundamental em teoria de códigos, e
o problema \cNP-difícil\cite{berlekamp1978inherent} em que é baseado o esquema de McEliece.

\begin{definition}
    O \emph{problema da decodificação por distância mínima} é: dado um código
    $[n, k]$-linear $\mathcal{C}$, e um vetor $c'$ de $\Fb^n$, encontre o vetor $c$
    de $\mathcal{C}$ tal que $\dist(c, c')$ é mínima.
\end{definition}


O esquema de McEliece original usa códigos de Goppa. Estes são códigos algébricos
que são bons candidatos ao uso criptográfico, mas não são muito interessantes
para chaves compactas. Algumas de suas propriedades são listadas a seguir.
\begin{itemize}
    \item Cada código é gerado por um polinômio irredutível $g$ de $\mathbb{F}_{2^m} [x].$
    \item A capacidade de correção é igual ou superior ao grau $t$ de $g.$
    \item É fácil construir decodificadores de $t$ erros eficientes conhecendo $g$.
    \item Não se conhece algoritmo eficiente para construir decodificadores sem conhecer $g$.
    \item É difícil em geral distinguir matrizes geradoras de Goppa e geradoras de aleatórios,
        embora seja possível para k próximo de n \cite{faugere2013distinguisher}.
\end{itemize}
