%% ------------------------------------------------------------------------- %%
%!TEX root = quali.tex
%!TeX spellcheck = pt-BR


\chapter{Esquema de McEliece}
\label{cap:esquemas}


\begin{definition}[Esquema de McEliece]

    Um \emph{Esquema de McEliece} é uma tripla de algoritmos
    $\left( \alg{KeyGen}, \alg{Enc}, \alg{Dec} \right)$, em que cada algoritmo é
    definido como os seguintes.

    \textbf{\alg{KeyGen}} é o algoritmo para geração de um par de chaves.
    Dado um nível de segurança $\lambda$, siga os seguintes passos.
    \begin{enumerate}
        \item Escolha uma tripla de parâmetros $(n, t, k)$ de uma família $\mathcal{F}$ de códigos
            de Goppa que suporta um nível de segurança $\lambda$ usando, por exemplo,
            a Tabela~\ref{tab:mcbits}.
        \item Tome $\bar{G}$ e $g$, respectivamente, uma matriz geradora, e um polinômio de Goppa,
            de um mesmo código $\mathcal{G}$
            escolhido aleatoriamente da família $\mathcal{F}$.
        \item Escolha aleatoriamente $S$, uma matriz $k \times k$ não singular,
            e $P$, uma matriz de permutação $n \times n$. Ambas têm entradas em
            $\Fb$.
        \item Faça $G \gets S \bar{G} P$, e $\hat{G} \gets S \bar{G}.$
        \item Devolva o par de chaves secreta e pública, dados respectivamente por
        $$
        \sk \gets (\hat{G}, P, g), \quad \text{e } \quad \pk \gets (G, t).
        $$
    \end{enumerate}


    \textbf{\alg{Enc}} é o algoritmo de encriptação.
    Dada uma mensagem $\vec{m}$, e a chave pública do destinatário \pk, siga os seguintes passos.
    \begin{enumerate}
        \item Separe os elementos da chave pública em $(G, t) \gets \pk $.
        \item Tome $\vec{e} \gets $ vetor aleatório de $\Fb^n$ de peso $t$
        \item Devolva o vetor $\vec{c} \gets mG \oplus \vec{e}$
    \end{enumerate}

    \textbf{\alg{Dec}} é o algoritmo de decriptação.
    Dado um texto cifrado $\vec{c}$ e a chave secreta do destinatário \sk, siga os seguintes passos.
    \begin{enumerate}
        \item Separe os elementos da chave secreta em $(\hat{G}, P, g) \gets \sk $.
        \item Obtenha o decodificador $\Phi$ a partir de $g$.
        \item Calcule $ \vec{c}_1 \gets \vec{c}P^{-1}$. Assim, $\vec{c}_1$ representa
        $$
            \vec{c}P^{-1} = (\vec{m}G \oplus \vec{e})P^{-1}  = \vec{m}\hat{G} \oplus \vec{e}P^{-1}.
        $$
        \item Calcule $ \vec{c}_2 \gets \Phi(\vec{c}_1)$ que é igual a $\vec{m}\hat{G}$ .
        \item Devolva $ \vec{m} $ que é a solução do sistema sobredeterminado $\vec{m}\hat{G} = \vec{c}_2$.
    \end{enumerate}

\end{definition}

    A Tabela~\ref{tab:mcbits}, adaptada do artigo de Bernstein, Chou, e Schwabe~\cite{bernstein2013mcbits},
    mostra parâmetros de códigos de Goppa para alguns níveis de segurança.

    \begin{table}[H]
    \centering
    \caption{Parâmetros de famílias de códigos de Goppa para cada nível de segurança $\lambda$ \cite{bernstein2013mcbits}.}
    \label{tab:mcbits}
    \begin{tabular}{@{}cccccc@{}}
    \toprule
    $\lambda$ & $n$  & $k$  & $t$ & $m$ & \begin{tabular}[c]{@{}c@{}}Tamanho da chave pública\\ (Bytes)\end{tabular} \\ \midrule
    81        & 2048 & 1751 & 27  & 11  & 65006                                                                      \\
    95        & 2048 & 1608 & 40  & 11  & 88440                                                                      \\
    105       & 2480 & 1940 & 45  & 12  & 130950                                                                     \\
    119       & 2690 & 2018 & 56  & 12  & 169512                                                                     \\
    146       & 3408 & 2604 & 67  & 12  & 261702                                                                     \\
    187       & 4624 & 3389 & 95  & 13  & 523177                                                                     \\
    263       & 6960 & 5413 & 119 & 13  & 1046739                                                                    \\ \bottomrule
    \end{tabular}
    \end{table}

O esquema de McEliece se baseia em duas hipóteses:

\begin{enumerate}
  \item Não existe algoritmo eficiente capaz de decodificar códigos lineares aleatórios.

  \item Para a família de códigos $\mathcal{F}_t^{n, k}$ escolhida, as matrizes públicas
  geradas são indistinguíveis de matrizes aleatórias.

\end{enumerate}

A primeira hipótese é relativamente bem aceita, pois sabe-se que o problema de decodificar códigos
lineares aleatórios é  \cNP-difícil.       Porém, a única família de códigos que
ainda resiste indistinguível é a dos códigos de Goppa.


\section{Segurança}


O principal ataque que o esquema de McEliece sofre é chamado de decodificação por conjunto de informação (ISD) -
\emph{Information Set Decoding}.
Seja $I$ um conjunto de $k$ índices quaisquer do vetor $c$. Se para todo índice $i$ de $I$, temos $e_i = 0$,
e se a submatriz $G_I$ de $G$ formada pelas colunas $k$ de índices em $i$ for inversível, um atacante pode
obter facilmente a mensagem encriptada $m$. Basta fazer a multiplicação $m = c_I G_I^{-1}$, em que $c_I$
denota o vetor formado pelas colunas de $c$ com índices em $I$. Por sorte este ataque não é factível na prática,
já tem complexidade limitada inferiormente por $\binom{n}{k}/\binom{n - t}{k}$.

Vejamos como a captura de certas informações pode deixar o ataque por ISD mais eficiente.
As próximas seções são adaptações do trabalho de Kobara e Imai~\cite{kobara2001semantically}.
\subsection{Ataque por mensagem parcialmente conhecida}

Considere o cenário em que Beto envia $c = mG \oplus e$ à Alice, e suponha que a
adversária Eva conhece os $k_r$ últimos bits de $m$. Sejam de $m_l$ e $m_r$ os
$k_l$ primeiros e os $k_r$ últimos bits de $m$, respectivamente.
Então
\[
    c = m_l G_l \oplus m_r G_r \oplus e,
\]
onde $G_l$ é a matriz formada pelas primeiras linhas de $G$, e $G_r$ a matriz
formada pelas $r$ últimas.

Como Eva conhece $ m_r G_r $, ela pode calcular $c' = c \oplus m_r G_r$. E assim,
a dificuldade de encontrar $m_l$ com a equação
\[
    c' = m_l G_l \oplus e,
\]
é a mesma de recuperar uma mensagem encriptada usando parâmetros $(n, k_l, t)$.

Denotamos por $WF_\alg{KPP} (n, k, t, k_l)$ o esforço necessário para Eva recuperar
uma mensagem $m$ num esquema de McEliece com parâmetros $(n, k, t)$, quando ela
desconhece apenas $k_l$ bits da m. A abreviação \alg{KPP} vem de
\emph{known partial plaintext}, nome comumente usado para este tipo de ataque.

E assim, uma cota superior natural para $\WF_\alg{KPP}$ é
$$
    \WF_\alg{KPP} (n, k, t, k_l) \leq \WF_\alg{ISD}(n, k_l, t) \leq k_l^3\frac{\binom{n}{k_l}}{\binom{n - t}{k_l}}.
$$

\subsection{Ataque por mensagem relacionada}

Para este ataque, abreviado como \alg{RMA}, de \emph{related message attack},
considere que Beto envia a Alice duas mensagens $m_1$ e $m_2$, cujos textos
cifrados são $c_1$ e $c_2$, respectivamente. Suponha que Eva conhece um vetor
$\delta_m$ que relaciona as mensagens enviadas, como por exemplo $\delta_m = m_1 \oplus m_2$.
Então, a soma dos cifrados é

\begin{align*}
    c_1 \oplus c_2 &= \left( m_1 G \oplus e_1 \right) \oplus \left( m_2 G \oplus e_2 \right) \\
                   &= \left(m_1 \oplus m_2 \right) G \oplus (e_1 \oplus e_2) \\
                   &= \delta_m G \oplus (e_1 \oplus e_2).
\end{align*}

E Eva pode calcular
\[
\bar{e} = c_1 \oplus c_2 \oplus \delta_m G,
\]
que é o vetor resultante da soma $e_1 \oplus e_2$.

A importância do vetor $\bar{e}$ na recuperação das mensagnes, é que, se $\bar{e}_i = 0$,
a probabilidade de as i-ésimas entradas dos erros $e_1$ e $e_2$ também serem 0 é
\begin{align*}
  \Pr({e_1}_i = 0 \land {e_2}_i = 0 \mid \bar{e}_i = 0)
    &= \frac{\Pr({e_1}_i = 0 \land {e_2}_i = 0 \land \bar{e}_i = 0)}{\Pr(\bar{e}_i = 0)} \\
    &= \frac{(n - t)^2}{(n - t)^2 + t^2}.
\end{align*}

Essa probabilidade em geral é bem alta. Tome, por exemplo, $n = 6960$ e $t=119$,
que são parâmetros de uma família de códigos de Goppa que permitem um nível
segurança de 263. A probabilidade será
\[
\Pr({e_1}_i = 0 \land {e_2}_i = 0 \mid \bar{e}_i = 0) \geq 99.76\%.
\]

Com isso, Eva pode usar o \alg{ISD} escolhendo aleatoriamente $k$
coordenadas que são nulas em $\bar{e}$.

\subsection{Ataque de reação}

Neste ataque, a adversária Eva tenta obter alguma informação confidencial
através da reação de Alice sobre um pedido de decriptação. Considere que um
remetente envia um texto cifrado $\bar{c}$, não necessariamente válido.
Alice pode:
\begin{itemize}
    \item aceitar $\bar{c}$, após decriptá-lo e obter uma mensagem válida;
    \item rejeitar $\bar{c}$, por não conseguir decriptá-lo, ou por não ser
        o cifrado de uma mensagem válida.
\end{itemize}

Suponha que Eva pode enviar textos a Alice, e observar a sua reação a eles.
Isso ocorre, por exemplo, se Alice, ao não conseguir decriptar um texto, pede ao remetente
que encripte a mensagem novamente e envie o novo cifrado.

Para decifrar o cifrado $c = mG \oplus e$, Eva pode usar as reações de Alice para
reconstruir $e$, e recuperar $m$ usando o Algoritmo~\ref{alg:mce_ataque_reacao}
a seguir.

\begin{algorithm}[H]
  \Entrada{$c$ texto cifrado que Eva quer decifrar. \\
  \myinput{$\pk$ a chave pública de Alice.}
  }
  \Saida{$m$ a decifração de $c$.}
  \Inicio{
    $e \gets [0, \ldots, 0]$ \\
    \Para{cada $i = 1, \ldots, n$} {
        $\bar{c} \gets c$ \\
        $\bar{c}_i \gets c_i \oplus 1$ \\
        \Se{Alice aceita $\bar{c}$}{
            $e_i = 1$
        }
    }
    $(G, t) \gets \pk$ \\
    $m \gets$ solução do sistema sobredeterminado $mG = c \oplus e$ \\
    \Retorna{$m$}
  }
  \caption{Ataque de reação ao esquema de McEliece.}
  \label{alg:mce_ataque_reacao}
\end{algorithm}

Note que o ataque descrito pelo Algoritmo~\ref{alg:mce_ataque_reacao} pode ser
evitado se Alice rejeitar qualquer cifrado que não tenha sido criado com um
erro de peso $t$. Mas mesmo nesse caso, Eva pode gerar $\bar{c}$ invertendo
simultaneamente dois bits de $c$ a cada iteração. E, quando Alice aceita
$\bar{c}$, Eva sabe que exatamente um dos bits alterados está com erro.


\section{Conversões de segurança}

Apesar de a encriptação não ser determinística, é fácil ver que o esquema de McEliece não provê indisguibilidade
de textos legíveis escolhidos (IND-CPA), que é a noção de segurança mais elementar para esquemas de chave pública.
Para ver isso, tome duas mensagens $\vec{m}_1$ e $\vec{m}_2$, e um cifrado $\vec{c}$ de uma das mensagens,
escolhida ao acaso. Para determinar qual mensagem foi encriptada para obter $\vec{c}$, basta
calcular $\delta_1 = \vec{m}_1G \oplus \vec{c}$, e $\delta_2 = \vec{m}_2G \oplus \vec{c}$, e se
$\weight(\delta_1) = t$, então $\vec{c} = \vec{m}_1G$. Caso contrário, necessariamente $\delta_2 = t$,
e $\vec{c} = \vec{m}_2G$.

Assim, para usar o esquema de McEliece de forma segura, é necessário
fazer conversões de segurança. O ideal é atingir IND-CCA2, pois assim nenhum dos
ataques críticos apresentados nas seções passadas são possíveis.

Há conversões genéricas, como a de Pointcheval~\cite{pointcheval2000chosen}, e a
de Fujisaki e Okamoto~\cite{fujisaki1999secure}, que convertem esquemas PTOWF, e
OWE, respectivamente, em esquemas IND-CCA2. Ambas são aplicáveis ao esquema de
McEliece, que é um PTOWF, e portanto um OWE. Porém, por serem genéricas, não usam
o esquema de McEliece do modo mais eficiente possível, e portanto há redundância
de dados maior do que necessária.

Kobara e Imai~\cite{kobara2001semantically}  mostram três conversões eficientes, chamadas
$\alpha$, $\beta$, e $\gamma$, que convertem o esquema de McEliece num esquema
IND-CCA2, sob o modelo de oráculos aleatórios. As suas conversões específicas
chegam a ter redundância de dados\footnote{A redundância de dados em uma conversão é a
diferença entre os comprimentos do texto cifrado e do texto legível.} até 4 vezes menor do que as genéricas, e ainda,
para alguns parâmetros, a conversão $\gamma$ pode ser até mais eficiente em uso de dados
do que o McEliece original sem conversões, pois maximiza a quantidade de informação no vetor de erro.
A Tabela~\ref{tab:comp_redun_conversoes} mostra
a redundância de dados para cada conversão, com diferentes parâmetros $(n, k, t)$ do
esquema de McEliece.



\begin{table}[H]
\centering
\caption{Comparação da redundância de dados para as conversões genéricas e específicas~\cite[Tabela 1 adaptada]{kobara2001semantically}.}
\label{tab:comp_redun_conversoes}
\begin{tabular}{@{}cccc@{}}
\toprule
\multirow{2}{*}{Conversão}                                                   & \multicolumn{3}{c}{\begin{tabular}[c]{@{}c@{}}Redundância de dados  $\|c\| - \|m\|$\\ para parâmetros $(n, k, t)$\end{tabular}} \\ \cmidrule(l){2-4}
                                                                             & (1024, 644, 38)                          & (2048, 1289, 69)                          & (4096, 2560, 128)                         \\ \midrule
Pointcheval                                                                  & 1184                                     & 2208                                      & 4256                                      \\
Fujisaki e Okamoto                                                           & 1024                                     & 2048                                      & 4096                                      \\
\begin{tabular}[c]{@{}c@{}}Kobara e Imai  $\alpha$ e $\beta$\end{tabular} & 540                                      & 919                                       & 1696                                      \\
Kobara e Imai $\gamma$                                                       & 470                                      & 648                                       & 1040                                      \\
McEliece original                                                            & 380                                      & 759                                       & 1536                                      \\ \bottomrule
\end{tabular}
\end{table}

Por ser a conversão mais simples, mostramos aqui a conversão $\alpha$, cuja encriptação
é dada pelo Algoritmo~\ref{alg:mce_enc_ki_conv}, e a decriptação no Algoritmo~\ref{alg:mce_dec_ki_conv}.
Como outras conversões de segurança sob o modelo de oráculos aleatórios, a
ideia central é reduzir a quebra da encriptação de mensagens aleatórias com o esquema de McEliece,
que conjecturamos ser segura, à quebra da encriptação de mensagens não aleatórias, que um atacante pode conhecer parcialmente.

\begin{algorithm}[H] % Enc
  \Entrada{$m$ mensagem que Beto quer enviar a Alice. \\
  \myinput{$\pk$ a chave pública de Alice.}
  }
  \Saida{$c$ o texto cifrado da mensagem $m$.}
  \Inicio{
    $(G, t) \gets \pk$ \\
    $r \gets $ número aleatório $\approx 160$ bits \\
    $z \gets \alg{Hash}(r \| m)$ \\
    $y  \gets \alg{PRNG}(z) \oplus(r \| m)$ \\
    $e_z \gets \alg{IntegerToErrorVector}(z, t)$ \\
    $c \gets (yG \oplus e_z) $ \\
    \Retorna{$c$}
  }
  \caption{Conversão IND-CCA2 de \alg{Enc} \cite{kobara2001semantically}}
  \label{alg:mce_enc_ki_conv}
\end{algorithm}


\begin{algorithm}[H] % Dec
    \Entrada{$c$ texto cifrado recebido por Alice. \\
    \myinput{$\sk$ a chave secreta de Alice.}
    }
    \Saida{$m$ a decifração de $c$.}
    \Inicio{
        $y \gets \alg{Dec}(\alg{Esquerda}(c, k), \sk)$ \\
        $e_z \gets \alg{Esquerda(c, k)} \oplus yG$ \\
        $z \gets \alg{ErrorVectorToInteger}(e_z) $ \\
        $ r \| m \gets \alg{PRNG}(z) \oplus (y) $\\
        \Se{$z = \alg{Hash}(r \| m)$}{
            \Retorna{$m$}
        }
        \Senao{
            \Retorna{$\perp$}
        }
    }
    \caption{Conversão IND-CCA2 de \alg{Dec} \cite{kobara2001semantically}}
    \label{alg:mce_dec_ki_conv}
\end{algorithm}
