%!TEX root = diss.tex
\chapter{Fundamentos}

\section{Notações e definições básicas}

\paragraph{Conjuntos}
\mbox{}

O conjunto $\{1, 2, \ldots, r\}$ é denotado por $[r]$ .
Se $A$ é um conjunto, o número de elementos de $A$ é denotado por $|A|$ ou por $\#A$.
O conjunto dos números naturais é denotado por $\mathbb{N}$.
O símbolo $\Fb$ denota o corpo finito com dois elementos. 
Se $b$ é um elemento de $\Fb$, $\bar{b}$ denota o seu complemento. Então
$\bar{1} = 0$ e $\bar{0} = 1$.

\paragraph{Vetores e Álgebra Linear}
\mbox{}

Letras em negrito minúsculas como $\vec{u}$ representam vetores, enquanto 
maiúsculas como $\mat{H}$ representam matrizes.
Vetores são considerados como linhas. O $T$ sobrescrito denota a transposição
de matrizes ou vetores, então o vetor $\vec{u}^T$ é um vetor coluna.
A dimensão do espaço gerado por uma matriz $\mat{M}$ é denotada por $\dim \mat{M}$.

Índices referentes a posições de vetores começam em 1, de forma que 
se $\vec{v} = [0\,0\,1\,0\,0]$, 
então a posição de índice 3 de $\vec{v}$ tem a entrada 1. 
O suporte de um vetor $\vec{v}$, em geral binário, denotado por $\sup(\vec{v})$
é o conjunto das posições de suas entradas não nulas. Por exemplo, se
$\vec{v} = [0\,0\,1\,1\,0\,1\,0]$, então $\sup(\vec{v}) = \{3, 4, 6\}$.
Se $\vec{v}$ é um vetor, então $\vec{v}[i]$ denota a sua i-ésima entrada.
O símbolo $|$ é usado para separar blocos de uma matriz como
$\mat{H} = [\mat{H}_0 | \mat{H}_1 ]$, ou
de vetores como $\vec{e} = [\vec{e}_0 | \vec{e}_1]$.

O símbolo $\Fb^n$ denota espaço vetorial binário de comprimento $n$. Isto é, $\Fb^n$
é o conjunto de cadeias de $n$ bits, onde a soma entre duas cadeias é feita
bit a bit.
% Em geral, quando tratamos de conjuntos não nomeados preferimos $\#$, 
% como $\#\{1, 2, 3\} = 3$, para melhorar a legibilidade quando os limitantes $|$ e 
% $|$ ficariam distantes.

\paragraph{Algoritmos}
\mbox{}

Em geral, algoritmos são escritos em \emph{CamelCase} e versalete como
em \textsc{QuickSort}.
Classifica-se como algoritmo probabilístico um algoritmo 
que usa um gerador de números aleatórios para tomar decisões.
Se $f$ e $g$ são duas funções de $\mathbb{N}$ em $\mathbb{N}$, dizemos que
$f = \cO(g)$ se existe uma constante $c$ e um inteiro $n_0$
tal que $f(n) \leq cg(n)$ para todo $n > n_0$.
Note que o sinal de igualdade em $f = \cO(g)$ não implica que $g = \cO(f)$.
Um algoritmo de tempo polinomial é aquele que 
executa $\cO(n^c)$ passos até terminar, para alguma constante $c$, onde $n$ é o 
número de bits usados para se armazenar entrada. Similarmente, um algoritmo 
de tempo exponencial é aquele cujo o número de passos 
até o fim da execução é $\cO(k^n)$, para alguma constante $k > 1$.
Dizemos que um algoritmo tem tempo médio polinomial se o tempo esperado de execução
do algoritmo é $\cO(n^c)$, para certa distribuição sobre as entradas. Tipicamente 
é considerada a distribuição uniforme sobre as entradas.
É comum dizer simplesmente algoritmo polinomial no lugar de algoritmo de
tempo polinomial, ou similarmente para tempo exponencial.
Em complexidade computacional, classificam-se como problemas
fáceis aqueles que podem ser resolvidos por algum algoritmo polinomial. Chamam-se 
difíceis aqueles para que não se conhece algoritmo polinomial de resolução.
É importante notar que estas definições de fácil e difícil são assintóticas e
de pior caso, então devem ser um pouco refinadas para usá-las em criptografia.
Um oráculo é um algoritmo que resolve um problema em um passo computacional.

% O produto entre dois elementos é a cadeia formada pelos coeficientes
% do produto de polinômios induzidos pelos elementos, considerando-se que cada cadeia é um polinômio em que o $i$-ésimo bit da 
% cadeia fica associado ao monômio $x^i$, e o produto é feito $\mod x^n - 1$.



\section{Teoria de Códigos}

O esquema de McEliece é baseado em códigos corretores de erros, que são
meios eficientes de transmitir mensagens. Em teoria de códigos, mensagens 
são conjuntos ordenados de símbolos, que devem ser transmitidos de uma fonte a um receptor
através de um canal possivelmente ruidoso~\cite{shannon1948mathematical}.
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 recuperada a partir da transmitida.
Por sua vez, numa transmissão feita por um canal ruidoso, a meta é codificar
a mensagem de modo que esta possa ser recuperada, mesmo que
alguns de seus símbolos sejam alterados por conta de ruídos causados pela imperfeição 
do canal.

A Figura~\ref{fig:codific_canal_gen} exemplifica a transmissão de uma mensagem
por um canal ruidoso. Seguindo o fluxo definido pelos arcos, o processo de transmissão é
descrito a seguir. Uma fonte escolhe
uma mensagem $\vec{m}$ do conjunto $\mathcal{M}$ de mensagens possíveis.
O algoritmo codificador $E$ codifica a mensagem $\vec{m}$ gerando a palavra $\vec{c}$.
Ao passar pelo canal ruidoso, a palavra $\vec{c}$ sofre um erro $\vec{e}$ bit por bit
se tornando a palavra $\vec{c}'$. O algoritmo decodificador $D$ é aplicado sobre $\vec{c}'$
resultando na palavra $\hat{\vec{m}}$. Idealmente, queremos que a mensagem recuperada
$\hat{\vec{m}}$ seja igual à mensagem original $\vec{m}$ com alta probabilidade.
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.
Naturalmente, espera-se que $E$ e $D$ sejam executados em tempo polinomial. $E$ é tipicamente 
um algoritmo determinístico, enquanto $D$ pode ser probabilístico.

\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} + \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}


É comum em teoria de códigos chamar de decodificação de uma mensagem transmitida
tanto a correção de seus erros, quanto a recuperação da mensagem original, embora estas ações 
sejam fundamentalmente diferentes. Em geral, para códigos usados na prática, em sua grande
maioria códigos lineares,
uma vez que os erros da mensagem foram corrigidos,
recuperar a mensagem original é simplesmente resolver um sistema linear.
Neste texto, algoritmos de decodificação são sempre algoritmos corretores de erros, 
omitindo o procedimento de recuperação da mensagem original a partir de sua codificação.

Os códigos mais estudados e usados em sistemas reais são os códigos lineares. 
Um código linear é um subespaço vetorial, o que lhes garante certa estrutura.

\begin{definition}[Código binário linear]
    Um 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}[Matrizes geradora e de paridade]
    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 $\mat{G}$ de $\Fb ^{k \times n}$, dizemos que $\mat{G}$ é uma {matriz
    geradora} de $\mathcal{C}$.

    Analogamente, se $\mathcal{C}$ é o núcleo de uma matriz $\mat{H}$ de  $\Fb^{n - k \times n}$,
    dizemos que $\mat{H}$ é uma {matriz de paridade} de $\mathcal{C}$. Neste trabalho,
    tratam-se principalmente de códigos definidos por sua matriz de paridade. Então,
    para a notação ficar menos carregada, é útil 
    definir a codimensão de um código como $r = n - k$, e então $\mat{H}$ pertence a $\Fb^{r \times n}$.
\end{definition}

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

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


Para verificar se um dado vetor $\vec{v}$ pertence a um código, multiplique $\vec{v}$
à esquerda por $\mat{H}^T$
e verifique se foi obtido o vetor $\vec{0}$. Se sim, todas as equações de paridade foram
satisfeitas, e $\vec{v}$ pertence ao código.
Para a decodificação, muitas vezes é útil saber quais as
equações de paridade que não são satisfeitas por um dado vetor. Chama-se síndrome
de $\vec{v}$ o vetor binário $\vec{s}$ tal que, $\vec{s}[i] = 1$ se e somente se
a $i$-ésima equação de paridade não foi satisfeita para $\vec{v}$. 
Formalmente, a síndrome de um vetor
é definida a seguir.

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

    Então a síndrome de um vetor é $\vec{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, que fazem
de $\Fb^{n}$ um espaço métrico.

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

\end{definition}
\begin{definition}[Distância]
    A distância de Hamming, ou simplesmente distância, 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. Para códigos
    binários, vale que $\dist(\vec{u}, \vec{v}) = \weight(\vec{u} + \vec{v})$.
\end{definition}

Com isso pode ser definido um problema fundamental em teoria de códigos, que é
o problema \cNP-difícil\cite{berlekamp1978inherent} em que é baseado o esquema de McEliece.

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

\paragraph{Códigos de Goppa}
\mbox{}

O esquema de McEliece~\cite{mceliece1978} original usa códigos de Goppa~\cite{goppa1970new,berlekamp1973goppa}. 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. Como não são fundamentais para entender o QC-MDPC McEliece, 
foi optado por não descrevê-los detalhadamente.

Algumas de suas propriedades importantes para o esquema original de McEliece
são listadas a seguir. 
Cada código é gerado por um polinômio irredutível $g(x)$ de $\mathbb{F}_{2^m} [x].$
A capacidade de correção é igual ou superior ao grau $t$ de $g(x)$.
É fácil construir decodificadores de $t$ erros eficientes conhecendo
$g(x)$~\cite{patterson1975algebraic}.
Não se conhece algoritmo eficiente para construir decodificadores sem conhecer $g(x)$.
Parece ser difícil em geral distinguir matrizes geradoras de códigos de Goppa e matrizes
geradoras de códigos aleatórios~\cite{bernstein2013mcbits,bernstein2009post,bernstein2008attacking},
embora seja possível quando $k$ é próximo de $n$~\cite{faugere2013distinguisher}.

\paragraph{Códigos LDPC}
\label{cap:prelim_ldpc}
\mbox{}

Os códigos LDPC foram introduzidos por Gallager~\cite{gallager1962low} na década
de 60. Sua característica determinante é que possuem uma matriz de paridade de 
baixa densidade. Intuitivamente, isso significa que o número de entradas não nulas cresce 
linearmente no número de colunas da matriz. Códigos LDPC não são necessariamente 
binários~\cite{ryan2009channel}, porém apenas os binários interessam
para este trabalho.

\begin{definition}[LDPC]
Um código binário e linear com matriz de paridade $\mat{H}$ pertencente a
$\Fb^{r \times n}$ é dito um código
$[n, r]$-LDPC~\cite{gallager1962low}
se o número de elementos não nulos de $\mat{H}$ é $\mathcal{O}(n)$.
\end{definition}

Para entender o funcionamento do algoritmo de decodificação, é útil considerar 
uma interpretação gráfica para códigos LDPC.

\begin{definition}[Grafo de Tanner]
 Seja $\mat{H} = (h)_{ij}$ uma matriz de um código $[n, r]$-LDPC. Considere os conjuntos de 
 nós $V = \{ v_1, v_2, \ldots, v_n \}$, chamado de nós de variáveis, 
 e $C = \{ c_1, c_2, \ldots, c_r\}$, chamado de nós de verificação. 
 Considere também o conjunto $E$ de arestas entre $V$ e $C$, dado por
\[
  E = \{ (i, j) : h_{ij} = 1 \text{ para algum par de vértices $(c_i, v_j)$} \}.
\]
 Construa o seguinte
 grafo $G = (V \cup C, E)$, em $V \cup C$ é o conjunto de nós, e $E$ é o conjunto de arestas.
 O grafo $G$ chama-se de grafo de Tanner da matriz $\mat{H}$.

 Em geral considera-se uma matriz binária indissociável de seu grafo de Tanner.
 Uma vez que a matriz foi definida, pode-se referenciar o seu grafo de Tanner sem
 explicitamente construí-lo.
\end{definition}

\begin{example}
  Considere $\vec{H}$ a matriz de paridade de um código LDPC definida como
  \[
    \mat{H} =
    \begin{bmatrix}
      1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
      1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
      0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\
      0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
      0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1
    \end{bmatrix}.
  \]
  Esta matriz tem como grafo de Tanner o grafo mostrado na Figura~\ref{fig:exemplo_tanner}.
  \begin{figure}[h]
    \begin{tikzpicture}[thick,
      every node/.style={draw,circle,minimum size=4mm,inner sep=0pt,outer sep=0pt},
      fsnode/.style={fill=white},
      ssnode/.style={fill=gray},
      every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
      -,shorten >= 2pt,shorten <= 3pt,thick
    ]
       %% the check_nodes
       \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]
       \foreach \i in {1,...,5}
         \node[ssnode,on chain] (c\i) [label=above: $c_{\i}$] {};
       \end{scope}

       %% the var_nodes
       \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]
       \foreach \i in {1,...,10}
         \node[fsnode,on chain] (v\i) [label=below: $v_{\i}$] {};
       \end{scope}

       \draw (c1) -- (v1); \draw (c1) -- (v2); \draw (c1) -- (v3); 
       \draw (c1) -- (v4); \draw (c2) -- (v1); \draw (c2) -- (v5); 
       \draw (c2) -- (v6); \draw (c2) -- (v7); \draw (c3) -- (v2); 
       \draw (c3) -- (v5); \draw (c3) -- (v8); \draw (c3) -- (v9);
       \draw (c4) -- (v3); \draw (c4) -- (v6); \draw (c4) -- (v8); 
       \draw (c4) -- (v10); \draw (c5) -- (v4); \draw (c5) -- (v7);
       \draw (c5) -- (v9); \draw (c5) -- (v10);
     \end{tikzpicture}
     \caption{Grafo de Tanner da matriz $\mat{H}$.}
  \label{fig:exemplo_tanner}
  \end{figure}
\end{example}

\begin{definition}[Nó de verificação insatisfeito]
 Seja $\mat{H}$ uma matriz de um código $[n, r]$-LDPC, e seja $\vec{c}$ um
 vetor qualquer em $\Fb^n$. Chame de $\vec{s} = [s_1, s_2, \ldots, s_r]$
 a síndrome de $\vec{c}$, ou seja $\vec{s} = \vec{c}\mat{H}^T$.
 Se $s_i = 0$, dizemos que o nó de verificação $c_i$ está satisfeito. 
 Caso contrário, $s_i = 1$ e dizemos que $c_i$ está insatisfeito.
\end{definition}


Para corrigir erros em códigos LDPC, usam-se algoritmos iterativos de otimização 
local para a decodificação
que localizam as possíveis posições de erros usando o fato de a matriz de paridade ser 
esparsa. Estes algoritmos são eficientes, e conseguem boas capacidades de correção
de erros~\cite{ryan2009channel} porém têm dois problemas.

O primeiro é que todos os algoritmos conhecidos de decodificação para
códigos LDPC têm uma probabilidade, potencialmente pequena mas não negligenciável, 
de não conseguir decodificar algumas mensagens. Este problema não é muito sério 
quando o objetivo é integridade na comunicação, pois basta que o destinatário, 
ao não conseguir decodificar a mensagem, peça para que o remetente reenvie a mensagem.
Mas quando o objetivo é a confidencialidade da mensagem, esse problema possibilita
um ataque ao QC-MDPC McEliece~\cite{guo2016key}. 

O segundo problema, que tem relação com o primeiro, é que não é fácil estimar precisamente
a probabilidade de o decodificador falhar ao decodificar uma 
mensagem usando somente técnicas teóricas~\cite{gallager1962low,ryan2009channel}. 
Em geral a avaliação de decodificadores LDPC é feita através de simulações~\cite{ryan2009channel,maurich2015implementing}.

Os algoritmos de decodificação para códigos LDPC são classificados como
baseados em decisões abruptas ou baseados decisões suaves. Ambos os tipos são
iterativos, e tentam recuperar a mensagem original fazendo alterações
locais\footnote{Dizemos que as alterações são locais pois, para decidir se uma alteração
deve ou não ocorrer, não são levados em conta os valores de todas as posições do vetor, mas 
considera-se apenas um subconjunto delas.}
nas entradas da mensagem recebida. Idealmente, estas alterações
são cada vez mais confiáveis a cada iteração.
Num algoritmo baseado em decisões abruptas, a cada iteração, a mudança local que pode
ocorrer em um bit é a inversão dele. Por este motivo, são chamados de algoritmos
de \emph{bit-flipping}. 
Em contraste, nas iterações de um algoritmo baseados em decisões suaves, considera-se
a probabilidade de cada bit da mensagem recebida ser 0 ou 1.

O primeiro algoritmo de \emph{bit-flipping} para decodificação foi introduzido por
Gallager~\cite{gallager1962low}. Como este foi o algoritmo atacado que 
Guo et al.~\cite{guo2016key} escolheram para formular seu ataque, 
sua descrição foi deixada para a Seção~\ref{cap:ataque_guo}.
Como exemplo de algoritmo decodificador, considere
um algoritmo, similar ao original de Gallager,
sugerido por Huffman e Pless~\cite{huffman2010fundamentals}, que é descrita no
Algoritmo~\ref{alg:huff_bit_flipping}. A cada iteração,
é calculado o número $f_j$ de nós de verificação vizinhos a $v_j$
que estão insatisfeitos. Pode-se descrever alternativamente $f_j$ como
o número de equações de paridade às quais o bit $j$ pertence e que estão insatisfeitas.
No fim da iteração, cada bit $j$ é invertido se e somente se $f_j \geq \max_i f_i$.
O algoritmo realiza esses passos iterativamente até que tenha extraído os
erros da mensagem, ou o número de iterações tenha excedido o máximo permitido $\var{max\_it}$.

\begin{algorithm}[h]
  \Entrada{$\mat{H}$ matriz de paridade esparsa $r \times n$ de um código LDPC\\
    \myinput{$\vec{y}$ uma palavra transmitida a ser decodificada}
    \myinput{\texttt{max\_it} o número máximo de iterações}
  }
  \Saida{A decodificação estimada de $\vec{y}$, ou $\perp$ se o número máximo de
         iterações for excedido}
  \Inicio{
    \var{it} $\gets$ 0 \\
    \Enqto{$ \vec{y}\mat{H}^T \neq \vec{0} $ e $\var{it} < \var{max\_it}$}{
      \Para{cada $j = 1, 2, \ldots, n$}{
        $ f_j \gets $ Número de vizinhos de $v_j$ insatisfeitos
      }
      $\var{max\_upc} \gets \max \left\{ f_j \right\} $ \\
      \Para{cada $j = 1, 2, \ldots, n$}{
        \Se{$f_j \geq \var{max\_upc}$}{
          $y_j \gets \bar{y_j}$
        }
      }
      $\var{it} \gets \var{it} + 1$
    }
    \Se{$\var{it} \geq \var{max\_it}$}{
      \Retorna{$\perp$}
    }
    \Senao{
      \Retorna{$\vec{y}$}
    }
  }
  \caption{Variante do algoritmo de \emph{bit-flipping} sugerido por
    Huffman e Pless~\cite{huffman2010fundamentals}}
  \label{alg:huff_bit_flipping}
\end{algorithm}


O exemplo a seguir pode ajudar a entender o funcionamento do algoritmo e por que
é útil a interpretação gráfica de códigos LDPC.

\begin{example}
Considere o código [10, 5]-LDPC denotado por $\mathcal{C}$ que tem
$\mat{H}$, a mesma considerada no exemplo anterior, como sua matriz de paridade
esparsa
\[
    \mat{H} =
    \begin{bmatrix}
      1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
      1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
      0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\
      0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
      0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1
    \end{bmatrix}.
\]
Seja $\vec{c} = [0 \, 1 \, 1 \, 0 \, 0 \, 0 \, 0 \, 0 \, 1 \, 1]$. Note que 
$\vec{c}$ pertence a $\mathcal{C}$ pois $\vec{c}\mat{H}^T = \vec{0}$.
Suponha que o vetor de erro adicionado a $\vec{c}$
seja $\vec{e} = [0 \, 0 \, 0 \, 0 \, 0 \, 0 \, 0 \, 1 \, 0 \, 0]$,
resultando $\vec{c}' =
 \vec{c} + \vec{e} = [0 \, 1 \, 1 \, 0 \, 0 \, 0 \, 0 \, 1 \, 1 \, 1]$.

A Figura~\ref{fig:exemplo_bf} ilustra as iterações do algoritmo decodificador para
recuperar $\vec{c}$ a partir de $\vec{c}'$. O primeiro grafo mostra os nós 
de variáveis assumindo os valores dos bits em $\vec{c}'$. O segundo grafo
mostra as variáveis de verificação somando $(\text{mod } 2)$ os valores dos nós de variáveis 
vizinhos. As que foram satisfeitas estão pintadas verdes, e as que não foram estão pintadas
de vermelho. O terceiro grafo mostra as variáveis contando quantos de seus nós 
de verificação vizinhos não estão satisfeitos. Nota-se que a variável $v_8$ é a que está com 
mais vizinhos insatisfeitos, portanto seu valor é invertido.
Finalmente no quarto grafo, os nós de verificação fazem novamente a soma 
de suas variáveis vizinhas, e nota-se que não há mais nós insatisfeitos. 
Então o algoritmo termina obtendo $[0, 1, 1, 0, 0, 0, 0, 0, 1, 1]$ como vetor recuperado, que exatamente $\vec{c}$.

    \begin{figure}[h]
      \begin{tikzpicture}[thick,
        every node/.style={draw,circle,minimum size=3mm,inner sep=0pt,outer sep=0pt},
        fsnode/.style={fill=white},
        ssnode/.style={fill=gray},
        onesnode/.style={fill=black, text=white},
        zerosnode/.style={fill=white},
        oknode/.style={fill=green},
        nonode/.style={fill=red},
        every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
        -,shorten >= 2pt,shorten <= 3pt,thick
      ]
        %% the check_nodes
        \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]
            \node[ssnode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[ssnode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[ssnode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[ssnode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[ssnode,on chain] (c5) [label=above: $c_{5}$] {};

        \end{scope}
         %% the var_nodes

        \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]


                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {};
                \node[onesnode,on chain] (v8) [label=below: $v_{8}$] {};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {};

        \end{scope}
         \draw (c1) -- (v1); \draw (c1) -- (v2); \draw (c1) -- (v3); \draw (c1) -- (v4);
         \draw (c2) -- (v1); \draw (c2) -- (v5); \draw (c2) -- (v6); \draw (c2) -- (v7);
         \draw (c3) -- (v2); \draw (c3) -- (v5); \draw (c3) -- (v8); \draw (c3) -- (v9);
         \draw (c4) -- (v3); \draw (c4) -- (v6); \draw (c4) -- (v8); \draw (c4) -- (v10);
         \draw (c5) -- (v4); \draw (c5) -- (v7); \draw (c5) -- (v9); \draw (c5) -- (v10);
       \end{tikzpicture}

\begin{tikzpicture}[thick,
        every node/.style={draw,circle,minimum size=3mm,inner sep=0pt,outer sep=0pt},
        fsnode/.style={fill=white},
        ssnode/.style={fill=gray},
        onesnode/.style={fill=black, text=white},
        zerosnode/.style={fill=white},
        oknode/.style={fill=green},
        nonode/.style={fill=red},
        every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
        -,shorten >= 2pt,shorten <= 3pt,thick
      ]
        %% the check_nodes
        \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]
        % \only<2-3>{
            \node[oknode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[oknode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[nonode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[nonode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[oknode,on chain] (c5) [label=above: $c_{5}$] {};
        % }

        \end{scope}
         %% the var_nodes

        \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]

            % \only<1-2> {

                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {};
                \node[onesnode,on chain] (v8) [label=below: $v_{8}$] {};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {};
            % % }


        \end{scope}
         %
         %
         \draw (c1) -- (v1); \draw (c1) -- (v2); \draw (c1) -- (v3); \draw (c1) -- (v4);
         \draw (c2) -- (v1); \draw (c2) -- (v5); \draw (c2) -- (v6); \draw (c2) -- (v7);
         \draw (c3) -- (v2); \draw (c3) -- (v5); \draw (c3) -- (v8); \draw (c3) -- (v9);
         \draw (c4) -- (v3); \draw (c4) -- (v6); \draw (c4) -- (v8); \draw (c4) -- (v10);
         \draw (c5) -- (v4); \draw (c5) -- (v7); \draw (c5) -- (v9); \draw (c5) -- (v10);
       \end{tikzpicture}


\begin{tikzpicture}[thick,
        every node/.style={draw,circle,minimum size=3mm,inner sep=0pt,outer sep=0pt},
        fsnode/.style={fill=white},
        ssnode/.style={fill=gray},
        onesnode/.style={fill=black, text=white},
        zerosnode/.style={fill=white},
        oknode/.style={fill=green},
        nonode/.style={fill=red},
        every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
        -,shorten >= 2pt,shorten <= 3pt,thick
      ]
        %% the check_nodes
        \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]

        % \only<2-3>{
            \node[oknode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[oknode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[nonode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[nonode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[oknode,on chain] (c5) [label=above: $c_{5}$] {};
        % }
        \end{scope}
         %% the var_nodes

        \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]

            % % \only<3> {
                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {0};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {1};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {1};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {0};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {1};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {1};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {0};
                \node[onesnode,on chain] (v8) [label=below: $v_{8}$] {2};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {1};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {1};
            % }

        \end{scope}
         %
         %
         \draw (c1) -- (v1); \draw (c1) -- (v2); \draw (c1) -- (v3); \draw (c1) -- (v4);
         \draw (c2) -- (v1); \draw (c2) -- (v5); \draw (c2) -- (v6); \draw (c2) -- (v7);
         \draw (c3) -- (v2); \draw (c3) -- (v5); \draw (c3) -- (v8); \draw (c3) -- (v9);
         \draw (c4) -- (v3); \draw (c4) -- (v6); \draw (c4) -- (v8); \draw (c4) -- (v10);
         \draw (c5) -- (v4); \draw (c5) -- (v7); \draw (c5) -- (v9); \draw (c5) -- (v10);
       \end{tikzpicture}

      \begin{tikzpicture}[thick,
        every node/.style={draw,circle,minimum size=3mm,inner sep=0pt,outer sep=0pt},
        fsnode/.style={fill=white},
        ssnode/.style={fill=gray},
        onesnode/.style={fill=black, text=white},
        zerosnode/.style={fill=white},
        oknode/.style={fill=green},
        nonode/.style={fill=red},
        every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
        -,shorten >= 2pt,shorten <= 3pt,thick
      ]
        %% the check_nodes
        \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]

        % \only<4->{
            \node[oknode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[oknode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[oknode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[oknode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[oknode,on chain] (c5) [label=above: $c_{5}$] {};
        % }
        \end{scope}
         %% the var_nodes

        \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]

            % \only<4> {
                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {};
                \node[zerosnode,on chain] (v8) [label=below: $v_{8}$] {};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {};
            % }

        \end{scope}
         %
         %
         \draw (c1) -- (v1); \draw (c1) -- (v2); \draw (c1) -- (v3); \draw (c1) -- (v4);
         \draw (c2) -- (v1); \draw (c2) -- (v5); \draw (c2) -- (v6); \draw (c2) -- (v7);
         \draw (c3) -- (v2); \draw (c3) -- (v5); \draw (c3) -- (v8); \draw (c3) -- (v9);
         \draw (c4) -- (v3); \draw (c4) -- (v6); \draw (c4) -- (v8); \draw (c4) -- (v10);
         \draw (c5) -- (v4); \draw (c5) -- (v7); \draw (c5) -- (v9); \draw (c5) -- (v10);
       \end{tikzpicture}



       \caption{Funcionamento do algoritmo de {bit-flipping}}
    \label{fig:exemplo_bf}
    \end{figure}

\end{example}




\section{Criptografia de chave pública}

Criptografia é o conjunto de técnicas que possibilitam a comunicação segura num meio compartilhado com adversários maliciosos.
Pode-se definir vários conceitos de segurança para a comunicação, sendo que os principais
objetivos de segurança relacionados à criptografia de chave pública são enumerados a seguir.
\begin{enumerate}
  \item Confidencialidade: garante que somente o destinatário da mensagem 
  pretendido pelo remetente consiga lê-la.
  \item Autenticação: permite que um ou mais destinatários de uma mensagem 
  consigam comprovar que esta foi gerada por um dado remetente.
  \item Integridade: permite que um ou mais destinatários de uma mensagem 
  consigam comprovar que esta não foi alterada na transmissão.
  \item Irretratabilidade: garante que o real remetente de uma mensagem não pode negar
    tê-la criado.
\end{enumerate}

Note que 
o termo mensagem aqui é tomado num sentido amplo. Por exemplo, um documento estático numa 
página da web pode ser entendido como uma mensagem de um remetente para vários destinatários. 

A confidencialidade da comunicação é conseguida por esquemas de encriptação, enquanto as
outras três são conseguidas por esquemas de assinatura de mensagens. Neste trabalho
são considerados somente esquemas de encriptação, visto que este é o ponto forte
do esquema de McEliece. 

\paragraph{Esquemas de encriptação}
\mbox{}

Todo esquema de encriptação usa chaves, que são informações
que devem ser combinadas ao texto legível para encriptá-lo e ao texto encriptado para 
decriptá-lo. Os esquemas de encriptação se dividem em dois tipos: esquemas de chave
secreta e esquemas de chave pública. Em esquemas de chave secreta, remetente e 
destinatário compartilham secretamente uma mesma chave, que é usada tanto na encriptação quanto
na decriptação. Estes esquemas têm a desvantagem de exigir que
remetente e destinatário devam, ao menos uma vez, ter acesso a um canal seguro 
de comunicação para combinar uma chave\footnote{A menos que sejam usadas primitivas típicas
de esquemas de chave pública, como esquemas de compartilhamento de chave~\cite{diffie1976new}.}.
Apesar de serem conceitualmente
bem mais antigos do que os de chave pública, há hoje esquemas de chave secreta
bem sofisticados, sendo o AES~\cite{daemen2013design} o principal representante desta classe de esquemas.

Nos esquemas de chave pública, cada usuário possui duas chaves, uma chave secreta e outra pública, 
que são matematicamente relacionadas de forma
que, idealmente, seja computacionalmente impraticável para um atacante obter a chave secreta
de um usuário a partir da sua chave pública. Para enviar uma mensagem para uma destinatária
Alice, usa-se a chave pública de Alice para encriptar a mensagem, e Alice usa a sua chave
secreta para decriptá-la. Esquemas de chave pública foram idealizados por Diffie
e Hellman~\cite{diffie1976new}, que mostraram,
supondo a dificuldade problema do logaritmo discreto, como usuários de uma rede poderiam
decidir uma chave secreta comum sem a necessidade de um canal seguro, mas não mostraram como montar um esquema de encriptação. Os principais esquemas de encriptação de chave 
pública são o RSA de Rivest, Shamir, e Adleman~\cite{rsa1978rsa}, que foi publicado poucos
anos depois do trabalho de Diffie e Hellman, e os baseados em curvas
elípticas~\cite{miller1986ecc}. A seguir é dada uma definição formal de esquemas de 
encriptação de chave pública.

\begin{definition}[Esquema de encriptação~\cite{galbraith2012mathematics}]
  Seja $\lambda$ um inteiro positivo. Defina os seguintes espaços, todos dependentes
  de $\lambda$. $\MS_\lambda$ é o conjunto de mensagens possíveis.
  $\PK_\lambda$ é o conjunto de possíveis chaves públicas.
  $\SK_\lambda$ é o conjunto das possíveis  chaves secretas. 
  $\CS_\lambda$ é o conjunto de todos os textos encriptados possíveis.
  Diz-se que a tupla de algoritmos
  \[
    (\alg{GeraChaves}, \alg{Encripta}, \alg{Decripta})
  \]
  é um esquema de encriptação de chave pública sobre os espaços definidos acima se 
  todos os algoritmos são de tempo esperado polinomial em $\lambda$ e as seguintes condições são obedecidas.

  \begin{enumerate}
    \item O algoritmo gerador de chaves \alg{GeraChaves} é um algoritmo
    probabilístico, toma $\lambda$ como parâmetro,
    e devolve $\sk$ e $\pk$, 
    tais que $\sk \in \SK_\lambda$ e
    $\pk \in \PK_\lambda$.

    \item O algoritmo de encriptação \alg{Encripta} é um algoritmo probabilístico,
    que toma $\vec{m} \in \MS_\lambda$ e $\pk \in \PK_\lambda$ 
    como parâmetros, e devolve $\vec{c} \in \mathcal{C}_\lambda$.

    \item O algoritmo de decriptação \alg{Decripta} é um 
    algoritmo\footnote{Nada impede o algoritmo de decriptação de ser probabilístico, mas 
    não é comum que seja.},
    que toma $\vec{c} \in \mathcal{C}_\lambda$ e $\sk \in \SK_\lambda$ 
    como parâmetros, e devolve um valor
    $\vec{m} \in \MS_\lambda$, ou o símbolo $\perp$. O símbolo $\perp$
    em geral significa uma falha ao decriptar por conta de um texto encriptado
    inválido passado como argumento.

    \item Os três algoritmos são relacionados da seguinte forma.
    Se $\pk$ e $\sk$ são saídas do algoritmo $\alg{GeraChaves}(\lambda)$ para um certo
    $\lambda$, então vale que
    \[
      \alg{Decripta}(\alg{Encripta}(\vec{m}, \pk), \sk) = \vec{m},
    \]
    para todo $\vec{m} \in \MS$.
  \end{enumerate}

  Às vezes, como é o caso do QC-MDPC McEliece, a quarta condição é muito restritiva.
  Então podemos exigir apenas que esta condição valha com alta probabilidade, e também que,
  se
  \[
    \alg{Decripta}(\alg{Encripta}(\vec{m}, \pk), \sk) \neq \perp,
  \]
  então
  \[
    \alg{Decripta}(\alg{Encripta}(\vec{m}, \pk), \sk) = \vec{m}.
  \]
  Ou seja, se o algoritmo de decriptação não falhar, então ele decripta 
  o texto encriptado para a mensagem original.

  Os espaços e algoritmos associados ao esquema dependem de $\lambda$ da seguinte forma:
  o melhor ataque conhecido ao esquema deve terminar num número de passos maior
  ou igual a $2^\lambda$. Por este motivo, $\lambda$ é conhecido como o nível de segurança.
  Tipicamente, os tamanhos dos espaços crescem exponencialmente em função de $\lambda$,
  enquanto os algoritmos de encriptação, decriptação, e geração de chaves
  têm tempo de execução polinomial em $\lambda$.

\end{definition}

\paragraph{Complexidade computacional}
\mbox{}

Como a chave pública é disponível para qualquer atacante, é fundamental para a segurança
de um esquema criptográfico de chave pública que seja difícil 
encontrar a chave secreta de um usuário a partir de sua pública. Para criar esquemas em 
que resolver este problema seja de fato difícil, uma ideia bem aceita na criptografia moderna
é usar classes de problemas cujos melhores ataques não sejam algoritmos polinomiais.

Em teoria da complexidade, problemas computacionais
são separados em classes que 
representam a sua dificuldade. As classes mais usadas são 
descritas em termos de problemas de decisão, ou seja, aqueles cuja resposta é 
sim ou não. Em geral, problemas que não são de decisão podem induzir facilmente problemas
de decisão. Por exemplo, o problema de encontrar o produto entre dois inteiros $a$
e $b$ não é um problema de decisão. Porém um problema de decisão induzido por ele
é decidir se $ab = k$ para um certo $k$. Algumas das principais classes de problemas são dadas a seguir. Note que a dificuldade de um problema é reduzida ao número máximo de passos
que o melhor algoritmo possível dá para resolver a instância mais difícil
deste problema.

\begin{enumerate}
  \item $\cP$ é a classe dos problemas de decisão que podem ser resolvidos
  por algoritmos polinomiais. Um exemplo simples de problema em 
  $\cP$ é decidir se um inteiro $k$ pertence a uma lista com $n$ inteiros. 
  % Um algoritmo que roda em $\cO(n^1)$ passos é: teste
  % cada um dos $n$ elementos da lista, e, se $k$ for encontrado,
  % a resposta é sim, caso contrário a resposta é não. 

  \item $\cNP$ contém problemas de decisão tais que
  cada uma de suas instâncias cuja resposta é ``sim''
  admite um certificado compacto que permite que um algoritmo de tempo polinomial
  comprove que a resposta do problema de decisão é de fato ``sim''. Um certificado compacto é simplesmente
  uma cadeia de bits de tamanho $\cO(n^c)$, onde $n$ é o tamanho da instância do problema.
  Um exemplo de problema em $\cNP$ é o problema de satisfatibilidade de fórmulas
  booleanas (\textsc{SAT}). Um certificado compacto de que uma fórmula é satisfazível
  é uma valoração de suas variáveis que tornam a fórmula satisfeita.
  A primeira definição da classe $\cNP$ foi dada como o
  conjunto dos problemas de decisão que podem ser resolvidos
  polinomialmente por máquinas de Turing não determinísticas, do inglês 
  \emph{nondeterministic polynomial time}. Preferimos para este texto
  a primeira definição pois não usa máquinas não determinísticas.

  \item $co\cNP$ é a classe dos problemas de decisão tais que cada uma 
  de suas instâncias cuja resposta é ``não'' admite um certificado compacto,
  que permite que um algoritmo de tempo polinomial
  comprove que a resposta do problema de decisão é de fato ``não''.
  Um exemplo de problema em co$\cNP$ é o problema de decidir se uma fórmula
  booleana é uma tautologia. Um certificado compacto de que uma fórmula não é uma
  tautologia é uma valoração de suas variáveis que tornam a fórmula insatisfeita.
  Cada problema em $\cNP$ induz um problema em co$\cNP$, e vice-versa.
  Porém note que $co\cNP$ não é o conjunto complementar da classe $\cNP$. 

\end{enumerate}

Destas definições, temos que $\cP \subseteq \cNP$ e $\cP \subseteq \coNP$, já
que, mesmo sem qualquer certificado, pode-se resolver um problema em $\cP$
polinomialmente.
Um dos maiores problemas abertos em teoria da computação é decidir
se $\cP = \cNP$ ou não. Inclusive não se sabe nem se $\cNP = \coNP$. 
Mas em geral, supõe-se que $\cP \neq \cNP$, e que $\cNP \neq \coNP$.
Se $\cP = \cNP$, então $\cNP = \coNP$, porém se $\cNP = \coNP$, pode
ser o caso de $\cP \neq \cNP$.

Um importante subconjunto da classe $\cNP$ é o dos problemas $\cNP$-completos,
denotado por $\cNPC$. Cada problema deste conjunto tem a propriedade de que,
se um dia for descoberto um algoritmo polinomial para resolvê-lo, 
então $\cP = \cNP$. Isso faz com que os problemas $\cNP$-completos sejam
considerados os problemas teoricamente mais difíceis em $\cNP$.
Uma classe que capta problemas, agora não só de decisão, pelo menos tão difíceis quanto os 
problemas mais difíceis em $\cNP$ é a classe dos problemas $\cNP$-difíceis.
Esta classe contém os problemas $\cNP$-completos, mas também contém outros problemas tais
que, se for possível resolver algum deles eficientemente, então pode-se resolver problemas
$\cNP$-completos eficientemente. A menos que $\cP = \cNP$, a classe dos problemas
$\cNP$-difíceis contém problemas bem mais difíceis do que problemas
$\cNP$~-~completos~\cite{arora2009computational}.

A Figura~\ref{fig:classes_complex} mostra como a relação entre as classes de problemas
apresentadas, supondo que $\cP \neq \cNP$ e $\cNP \neq \coNP$. A área pintada de cinza contém a
grande maioria, senão todos, dos problemas usados para a elaboração de esquemas
criptográficos, em suas versões de decisão.

\begin{figure}
\begin{tikzpicture}
\pgftransformscale{.8}

%%% HELP LINES - uncomment to design/extend
% \draw[step=1cm,gray,very thin] (-10,0) grid (10,12);
% \node at (0,0) {\textbf{(0,0)}};

%% Horizontal bar
\draw[very thick] (10,0) -- (-10,0);

% % LOG TIME
% \draw (-1,0) parabola bend (0,2) (1,0) ;
% \node at (0,1) {
%   \begin{tabular}{c}
%   LOG
%   \end{tabular}
% };

% % LOG SPACE
% \draw (-2,0) parabola bend (0,3.5) (2,0);
% \node at (0,2.5) {
%   \begin{tabular}{c}
%   LOG \\ Space
%   \end{tabular}
% };
% NP-hard shallow
\filldraw[fill=lightgray, dashed=black] (-3,12) .. controls (2,4) and (4,7) ..  (8,12);

% NP
\filldraw[fill=lightgray, dashed=black] (-4,0) .. controls (1,11) and (3,11) ..  (6,0);
\node[rotate=-60] at (3,4) {\cNP};


% NP-complete
\node[rotate=-8] at (1.9,7.6) {\cNPC};

% Co-NP
\draw[dashed] (4,0) .. controls (-1,11) and (-3,11) ..  (-6,0);
\node[rotate=60] at (-3,4) {\coNP};

% PTIME
\draw[fill=white] (-3,0) parabola bend (0,4.5) (3,0);
\node at (0,2) {\cP};

% NP-hard
\draw[dashed] (-3,12) .. controls (2,4) and (4,7) ..  (8,12);
\node at (2.6,10.5) {\cNP-difíceis};

\draw[very thick] (10,12) -- (-10,12);


% % PSPACE
% \draw (-6,0) parabola bend (0,7.2) (6,0);
% \node at (0,6.5) {PSPACE};
\end{tikzpicture}
\caption{Relações entre algumas das principais classes de problemas,
supondo que $\cP \neq \cNP$ e $\cNP \neq \coNP$, com destaque para a região onde está a maior parte dos
problemas usados em criptografia}
\label{fig:classes_complex}
\end{figure}


Por exemplo, considere a versão de decisão do problema da fatoração de inteiros,
usado pelo RSA~\cite{rsa1978rsa}.
Neste problema, nos é dado um número inteiro positivo grande $n$, e um outro 
inteiro positivo $m < n$. O problema é decidir se $n$ tem algum divisor
$d$ tal que $1 < d \leq m$. Este problema está em $\cNP$, pois, se a resposta for sim,
basta mostrar um tal $d$ como certificado. Para testar este certificado, basta
ver se o resto da divisão de $n$ por $d$ é 0, o que pode ser feito eficientemente.
Por outro lado, se a resposta for não, um possível certificado é a fatoração completa de
$n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$, onde cada $p_i$ é primo.
Pode-se verificar polinomialmente que cada um dos fatores $p_i$ é realmente primo,
usando por exemplo o AKS~\cite{agrawal2004primes}, e basta efetuar um produto 
para verificar se a fatoração apresentada de fato fatora $n$.
Basta então verificar se cada um dos fatores primos de $n$ são maiores do que $m$, 
aceitando o certificado se todos forem.

A versão de decisão do problema da fatoração também tem a seguinte propriedade:
se existe um algoritmo polinomial para o problema de decisão, então existe um
algoritmo polinomial para fatorar um inteiro. Para provar esta afirmação, considere
que existe um algoritmo polinomial $\alg{DecideFator}$ que resolve o problema
de decisão para dois inteiros $n$ e $m$, como no parágrafo anterior.
% Sabe-se que ao menos um dos fatores de $n$ é menor do que $\sqrt{n}$.
Então podemos
usar o algoritmo $\alg{DecideFator}$ para 
fazer uma busca binária sobre o conjunto\footnote{A busca poderia ser feita
no conjunto $[\sqrt{n}]$, mas optamos por $[n]$ para simplificar a descrição.}
$[n]$ e encontrar o menor fator $d$, que é o menor fator primo, de $n$.
Como $\alg{DecideFator}$ é polinomial no comprimento da representação de $n$, então sua 
complexidade é $\cO\left( (\log n)^c \right)$ para alguma constante $c$. A
busca binária faz $\cO(\log n)$ chamadas ao algoritmo $\alg{DecideFator}$. Então
o custo de todas essas operações para encontrar o primeiro fator primo  de $n$ é
$\cO\left( (\log n) (\log n)^c \right) = \cO \left( (\log n)^{c + 1} \right)$.
Podemos repetir
tal procedimento para encontrar um menor fator primo
de $n/(d_1 \ldots d_i)$ a cada fator $d_i$ encontrado. Como $d_i \geq 2$, 
este procedimento seria executado no máximo $\log_2 n$ vezes. Então a complexidade
de fatorar completamente $n$ é $\cO\left( (\log n)^{c + 2} \right)$, 
que é polinomial no comprimento da representação de $n$.
Não se sabe se existem tais algoritmos polinomiais, mas conjectura-se que não existam.

Os dois parágrafos anteriores ilustram dois fatos importantes sobre os problemas usados
em criptografia. Pode-se ver que as versões de decisão de problemas não são necessariamente 
muito mais fracas do que as suas formulações originais, então muitas vezes podemos 
falar em termos de problemas de decisão. 
Também é mostrado que a versão de decisão do problema de fatoração está
em $\cNP \cap \coNP$, uma classe que acredita-se não conter problemas $\cNP$-completos.
Assim, parece não ser necessário usar problemas $\cNP$-difíceis para obter um esquema criptográfico 
forte, como é o caso do RSA~\cite{rsa1978rsa} que continua sendo usado mesmo
depois de 40 anos desde sua publicação. Para o uso em criptografia, não só é importante
que um algoritmo seja difícil em suas piores instâncias, mas que seja difícil na
grande maioria de suas instâncias.

Apesar de ser um problema muito estudado, não se conhece algoritmo polinomial
para fatorar inteiros em modelos de computação convencionais. Uma análise similar
à mostrada para este problema pode ser feita para o problema do logaritmo discreto,
usado, por exemplo, em criptografia com de curvas elípticas~\cite{miller1986ecc}.
Em suas versões de decisão, estes problemas não foram demonstrados $\cNP$-completos, e 
suspeita-se que sejam mais difíceis do que problemas em $\cP$, porém que de fato não sejam
$\cNP$-completos. Apesar disso, a confiança em esquemas criptográficos baseados nos problemas 
da fatoração
e do logaritmo discreto foi abalada quando Shor publicou seus algoritmos 
quânticos para resolvê-los~\cite{shor1997poly}.
Isso fez com que a principal ameaça a esquemas criptográficos baseados nesses problemas
seja a construção de um computador quântico com um número razoável de bits
quânticos~\cite{chen2016report}.
Os esquemas criptográficos pós-quânticos, isto é, que não sofreram ataques críticos 
por meio de algoritmos quânticos, são em geral baseados em problemas $\cNP$-difíceis, 
mas que também foram suficientemente estudados para que seja estabelecida
certa confiança de que são problemas difíceis em geral, e não apenas no pior caso.

É importante notar que, mesmo que um esquema seja baseado num problema $\cNP$-difícil,
isso não quer dizer que atacar um esquema criptográfico é resolver um problema $\cNP$-difícil.
O que em geral ocorre, e em particular ocorre para o esquema de McEliece, é que
o portador de uma chave secreta do esquema conhece uma instância do problema 
cuja resolução é fácil (por construção), 
porém a sua chave pública é uma instância embaralhada de forma que seja indistinguível 
de uma instância difícil.

\paragraph{Noções de segurança}
\mbox{}

Para analisar formalmente a segurança de esquemas criptográficos usam-se modelos
formais para os objetivos de segurança e para os ataques.
Os principais objetivos de segurança em criptografia de chave pública são dados 
a seguir.

\begin{enumerate}
    \item Encriptação de mão única (OWE): dado um texto encriptado, o adversário
  não consegue decriptar a mensagem.

    \item Indistinguibilidade (IND)~\cite{goldwasser1984probabilistic}: dadas 
    duas mensagens de mesmo comprimento,
  $\vec{m}_0$ e $\vec{m}_1$, o adversário não consegue distinguir entre
  os textos encriptados de $\vec{m}_0$ e $\vec{m}_1$, respectivamente.
  % \]
  Uma definição alternativa é que o adversário não consegue obter informação 
  sobre uma mensagem, a menos de seu comprimento, a partir de sua encriptação.
  
    \item Imaleabilidade (NM)~\cite{dolev2003nonmalleable}: 
    dado um texto encriptado $\vec{c}$, o adversário não consegue alterá-lo para
    $\vec{c}'$ de forma que os textos decriptados de $\vec{c}$ e 
    $\vec{c}'$ sejam relacionados. Ou seja, conhecer $\vec{c}$ não deixa mais fácil gerar
    um tal texto encriptado $\vec{c}'$.

\end{enumerate}


Os modelos de ataque representam formas diferentes de o atacante interagir com 
a chave secreta. Podem ser mais fracos, em que o atacante conhece apenas 
a chave pública, ou mais fortes, em que o atacante pode pedir para um oráculo 
decriptações de textos arbitrários, a menos da decriptação de um texto
encriptado passado como desafio. Os principais modelos de atacantes são os seguintes.


\begin{enumerate}
  \item Ataque passivo (CPA): o atacante conhece apenas a chave pública.
        Também é conhecido como ataque de texto escolhido, do inglês
        \emph{chosen plaintext attack}, pois o atacante pode encriptar textos
        arbitrariamente escolhidos.
        Em esquemas de chave pública, todos os usuários são potencialmente
        atacantes CPA. Então qualquer esquema de chave pública considerável
        deve no mínimo ser seguro contra este tipo de ataque.

  \item Ataque de texto cifrado escolhido (CCA1)~\cite{naor1990public}: 
        o atacante conhece a chave pública e
        pode pedir que sejam decriptados textos encriptados arbitrários
        por um período de tempo. Após este período de tempo, o atacante não pode
        mais interagir com o decriptador, e lhe é dado
        um desafio, de acordo com o objetivo de segurança desejado. O atacante
        então tenta resolver o desafio com uma probabilidade não negligenciável.
  
  \item Ataque adaptativo de texto cifrado escolhido (CCA2)~\cite{rackoff1991non}:
        é similar ao ataque CCA1, com o atacante podendo pedir decriptações
        de textos arbitrários para o portador da chave pública 
        por certo período de tempo, recebendo o desafio ao final do período. 
        A diferença é que o atacante pode continuar pedindo decriptações de
        textos arbitrários, exceto os textos encriptados do desafio.
        Diz-se que o ataque é adaptativo pois agora o atacante pode adaptar 
        os pedidos de decriptação ao desafio, o que não ocorre para atacantes
        CCA1.

  \end{enumerate}

Em geral ataques CCA1 são ataques de recuperação 
de chave, em que o atacante usa os textos decriptados conseguidos para
inferir bits, ou correlações entre bits, da chave.
Em particular, para o ataque de recuperação de chave
ao QC-MDPC McEliece~\cite{guo2016key}, o atacante envia textos encriptados
ao portador da chave secreta, e verifica se o texto foi
ou não decriptado. Como o atacante não precisa saber qual foi o texto 
decriptado, apenas a reação do decriptador, o ataque usa menos informação 
que ataques CCA1, e portanto é mais forte do que estes.

A segurança de um esquema é descrita na forma ``objetivo do ataque-modelo de ataque''.
Por exemplo, se um esquema permite indistinguibilidade de textos encriptados
contra um ataque adaptativo de texto encriptado escolhido, diz-se que ele tem segurança
IND-CCA2. Similarmente, chama-se também de ataque IND-CCA2 um ataque que objetiva 
distinguir textos encriptados interagindo com o decriptador na forma CCA2.

Esquemas criptográficos que não são \OWE certamente 
não podem ser usados de forma segura, pois os adversários podem
decriptar as mensagens. 
Então as noções  mais interessantes contra esquemas de chave pública são
aquelas em que os objetivos são IND ou NM, e os atacantes são CPA, CCA1, ou CCA2.
A Figura~\ref{fig:bellare_notions}
mostra as relações entre tais noções de segurança descobertas
por Bellare et al.~\cite{bellare1998relations}. Nesta figura, uma noção
de segurança implica outra se e somente se há um caminho da primeira até 
a segunda seguindo os arcos direcionados.

\begin{figure}[htbp]
  \centering

  \begin{tikzpicture}
    \node at (0,3) (NMCPA) {NM-CPA};
    \node at (5,3) (NMCCA1) {NM-CCA1};
    \node at (10,3) (NMCCA2) {NM-CCA2};

    \node at (0,0) (INDCPA) {IND-CPA};
    \node at (5,0) (INDCCA1) {IND-CCA1};
    \node at (10,0) (INDCCA2) {IND-CCA2};

    \draw [->] (INDCCA1) -- (INDCPA);
    \draw [->] (INDCCA2) -- (INDCCA1);
    
    \draw [->] (NMCCA1) -- (NMCPA);
    % \draw [->] (NMCCA2) -- (NMCCA1);

    \draw[->] ([yshift=0.1 cm]NMCCA2.west) -- ([yshift=0.1 cm]NMCCA1.east);
    % \draw[->] ([yshift=-0.1 cm]NMCCA1.east) --node[strike out, draw,-]{} ([yshift=-0.1 cm]NMCCA2.west);


    \draw [->] (NMCPA.south) -- (INDCPA.north);
    \draw [->] (NMCCA1.south) -- (INDCCA1.north);

    \draw[->] (INDCCA2.north) -- (NMCCA2.south);
    \draw[->] (NMCCA2.south) -- (INDCCA2.north);
    

    % \draw[->] ([xshift=-0.2 cm]NMCPA.south) 
    %             --node[strike out, draw,-]{} ([xshift=-0.2 cm] INDCCA1.north);
    % \draw[->] ([xshift=0.4 cm]INDCCA1.north) 
    %             --node[strike out, draw,-]{} ([xshift=0.4 cm] NMCPA.south);

  \end{tikzpicture}
  \caption{Relações entre algumas noções de
  segurança~\cite[Figura 1 adaptada]{bellare1998relations}. 
  Uma noção de segurança $A$ implica outra $B$ se e somente se há um caminho de $A$ a $B$}
  \label{fig:bellare_notions}
\end{figure}


\section{Esquema de McEliece}

\label{cap:esquemas}

O esquema de McEliece~\cite{mceliece1978} é um algoritmo de encriptação de chave pública.
O esquema é baseado em códigos corretores de erros. Sua segurança é fundamentada
no problema \cNP-difícil da decodificação por síndrome. 
Foi o primeiro algoritmo a usar um procedimento aleatório para a
encriptação~\cite{menezes1996handbook}, porém não com a intenção de deixá-lo
semanticamente seguro~\cite{goldwasser1984probabilistic}.
A encriptação e a decriptação são mais eficientes do que as respectivas operações
do RSA~\cite{rsa1978rsa} e curvas elípticas~\cite{miller1986ecc}. Porém 
sua usabilidade é prejudicada pelos grandes tamanhos de suas chaves públicas.

A chave pública de um usuário do esquema é a matriz geradora $\mat{G}$ 
de um código \code. A ideia de seu algoritmo de encriptação 
é codificar a mensagem usando $\mat{G}$ e adicionar 
um certo número de erros em posições aleatórias de um 
vetor de um código linear \code. Idealmente este vetor com erros só poderia
ser decodificado por um portador de um decodificador eficiente para \code.
Assim, a segurança do esquema depende da escolha de uma família de códigos tais que
não se saiba construir um decodificador eficiente apenas a partir da matriz geradora do 
código. A família de códigos originalmente sugerida por McEliece é a dos códigos de 
Goppa~\cite{goppa1970new,berlekamp1973goppa}.

A Tabela~\ref{tab:mcbits} mostra os parâmetros
dos códigos de Goppa e os tamanhos das chaves públicas, para cada nível de 
segurança~\cite{bernstein2013mcbits}.

\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}


\paragraph{Descrição do esquema}
\mbox{}

O Esquema de McEliece é uma tripla de algoritmos
$\left( \alg{GeraChaves}, \alg{Encripta}, \alg{Decripta} \right)$, em que cada algoritmo é
definido a seguir.

% \subsubsection{Geração de chaves}
    \alg{GeraChaves} é o algoritmo probabilístico de geração do 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{\mat{G}}$ e $g$, que são respectivamente, uma matriz geradora e um 
            polinômio de Goppa do código $\mathcal{G}$
            escolhido aleatoriamente da família $\mathcal{F}$.
        \item Escolha aleatoriamente $\mat{S}$, uma matriz binária $k \times k$ não singular,
            e $\mat{P}$, uma matriz de permutação $n \times n$. Note que ambas as matrizes
            são binárias.
        \item Faça $\mat{G} = \mat{S} \bar{\mat{G}} \mat{P}$, e $\hat{\mat{G}} = \mat{S} \bar{\mat{G}}.$
        \item Devolva o par de chaves secreta e pública, dadas respectivamente por
        $$
        \sk = (\hat{\mat{G}}, \mat{P}, g), \quad \text{e } \quad \pk = (\mat{G}, t).
        $$
    \end{enumerate}

% \subsubsection{Encriptação}

    \alg{Encripta} é o algoritmo probabilístico 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 $(\mat{G}, t) = \pk $.
        \item Tome um vetor $\vec{e}$ aleatório de peso $t$ de $\Fb^n$ .
        \item Devolva o vetor $\vec{c} = \vec{m}\mat{G} + \vec{e}$.
    \end{enumerate}

% \subsubsection{Decriptação}
    \alg{Decripta} é o algoritmo determinístico 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{\mat{G}}, \mat{P}, g) = \sk $.
        \item Obtenha $\Phi$ que é o decodificador do código de Goppa definido por $g$.
        \item Calcule $ \vec{c}_1 = \vec{c}\mat{P}^{-1}$. Assim, $\vec{c}_1$ representa
        $$
            \vec{c}\mat{P}^{-1} = (\vec{m}\mat{G} + \vec{e})\mat{P}^{-1}  = \vec{m}\hat{\mat{G}} + \vec{e}\mat{P}^{-1}.
        $$
        \item Calcule $ \vec{c}_2 = \Phi(\vec{c}_1)$, que é igual a $\vec{m}\hat{\mat{G}}$ .
        \item Devolva $ \vec{m} $ que é a solução do sistema sobredeterminado $\vec{m}\hat{\mat{G}} = \vec{c}_2$.
    \end{enumerate}


\paragraph{Segurança do esquema}
\mbox{}

A segurança do 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 as matrizes públicas de códigos de Goppa (possivelmente embaralhadas) 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~\cite{berlekamp1978inherent}, e, embora seja
um problema importante e bem estudado, os melhores 
decodificadores de códigos aleatórios conhecidos são algoritmos
exponenciais~\cite{overbeck2009code}. 
A segunda hipótese foi quebrada para
códigos de $[n, k]$-lineares de Goppa com $k$ próximo de
$n$~\cite{faugere2013distinguisher}. Como este caso não é interessante para o esquema
de McEliece, tais distinguidores não afetam significativamente o esquema.


Por ser baseado na impossibilidade de decodificar eficientemente códigos aleatórios, 
o esquema de McEliece é ameaçado por avanços em algoritmos genéricos de decodificação. 
Os melhores decodificadores conhecidos para códigos lineares aleatórios
são decodificadores por conjunto de informação~\cite{prange1962use}.

Como exemplo, é dado a seguir um simples algoritmo genérico para decodificação.
Sejam $\mat{G}$ uma matriz $k \times n$ geradora da chave 
pública de um usuário esquema de McEliece,
 $\vec{m}$ a mensagem secreta, e
$\vec{c} = \vec{m} \mat{G} + \vec{e}$ a mensagem encriptada, usando 
algum erro $\vec{e} = [e_1 e_2 \ldots e_n]$ de peso $t$.
Seja $I$ um conjunto de $k$ índices quaisquer do vetor $\vec{c}$. 
Se $e_i = 0$ para todo índice $i$ de $I$,
e se a submatriz $\mat{G}_I$ de $\mat{G}$ formada pelas colunas $k$ de índices em $i$ for inversível, 
um atacante pode
obter facilmente a mensagem encriptada $\vec{m}$. Basta fazer a multiplicação
 $\vec{m} = \vec{c}_I \mat{G}_I^{-1}$, onde $\vec{c}_I$
denota o vetor formado pelas colunas de $\vec{c}$ com índices em $I$. 
A probabilidade de um atacante escolher $k$ índices $i$ em que $e_i = 0$ é
$\binom{n - t}{k}/\binom{n}{k}$. Então o número esperado de tentativas que ele
deve fazer é $\binom{n}{k}/\binom{n - t}{k}$. Embora tal número de tentativas possa ser 
pequeno quando $n$ é pequeno, ou quando $n$ é próximo de $n - t$, é possível escolher parâmetros
$n, k, t$ de modo que o número esperado de tentativas seja grande.

Há algoritmos similares para a decodificação de códigos 
lineares que podem ser mais eficientes~\cite{prange1962use,lee1988observation,stern1988method,finiasz2009security}. Porém mesmo para eles, através da escolha de $n, k$, e $t$,
para cada nível de segurança $\lambda$,
pode-se fazer o ataque levar tempo esperado exponencial em função de $\lambda$.

% 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}.

% \paragraph{Conversões de segurança}
% \mbox{}

Apesar de a encriptação ser probabilística, pode-se ver que o esquema de McEliece não provê 
indistinguibilidade de textos legíveis escolhidos (IND-CPA), que é 
uma noção básica de segurança para esquemas de chave pública.
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 $\vec{d}_1 = \vec{m}_1\mat{G} + \vec{c}$, e
$\vec{d}_2 = \vec{m}_2\mat{G} + \vec{c}$, e se
$\weight(\vec{d}_1) = t$, então $\vec{c} = \vec{m}_1\mat{G}$. 
Caso contrário, $\vec{c} = \vec{m}_2\mat{G}$.
A segurança do esquema é ainda mais afetada quando parte do texto
legível é conhecido, o que pode diminuir significativamente o número esperado 
de operações necessárias para recuperar a mensagem usando decodificadores por
conjunto de informação~\cite{kobara2001semantically}.

Assim, para usar o esquema de McEliece de forma segura, é necessário
fazer adaptações no esquema, chamadas conversões de segurança,
objetivando atingir segurança contra ataques IND-CCA2.
Há conversões genéricas, como a de Pointcheval~\cite{pointcheval2000chosen}, e a
de Fujisaki e Okamoto~\cite{fujisaki1999secure}, que são aplicáveis ao esquema de
McEliece. 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\footnote{A redundância de dados em uma conversão é a
diferença entre os comprimentos do texto cifrado e do texto legível.}
maior do que necessária.

Kobara e Imai~\cite{kobara2001semantically}  mostraram 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~\cite{bellare1993random}.
As suas conversões específicas
chegam a ter redundância de dados 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 \\ 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 mais simples, é mostrada aqui a conversão $\alpha$, cuja encriptação
é dada pelo Algoritmo~\ref{alg:mce_enc_ki_conv}, e a decriptação pelo 
Algoritmo~\ref{alg:mce_dec_ki_conv}.
Nestas descrições, as funções $\alg{Hash}$ e $\alg{PRNG}$ representam, 
respectivamente, uma função de hash ideal e um gerador ideal de números pseudo-aleatórios
a partir de uma semente passada como argumento. Funções como essas duas são 
modeladas por oráculos aleatórios~\cite{bellare1993random}. Embora funções de hash e
geradores de números pseudoaleatórios modernos sejam, na prática, boas aproximações
para as respectivas funções ideais, não se sabe se é possível construir 
fisicamente tais funções ideais. 
Supõe-se que a saída de $\alg{PRNG}$
é um vetor de bits aleatórios.
$\alg{Esquerda}(\vec{c}, k)$ representa as $k$ primeiras entradas de $\vec{c}$.
A função auxiliar $\alg{InteiroParaVetor}(z)$ codifica o número $z$ num vetor
de peso $t$ e comprimento $n$. Algumas alternativas para implementar esta função 
foram discutidas por Overbeck e Sendrier~\cite{overbeck2009code}.
A função $\alg{VetorParaInteiro}(\vec{e})$ denota a inversa da função
$\alg{InteiroParaVetor}(z)$.
Como outras conversões de segurança sob o modelo de oráculos aleatórios, a
ideia é fazer com que decriptar mensagens
aleatórias encriptadas pelo esquema de McEliece é ao menos tão difícil para um atacante 
quanto decriptar mensagens não aleatórias, que o atacante até pode conhecer parcialmente. 
Além disso, a conversão impõe uma certa relação entre o erro $\vec{e}_z$ e a mensagem
$\vec{m}$, em particular $\alg{VetorParaInteiro}(\vec{e}_z) = \alg{Hash}([\vec{r}|\vec{m}])$,
de tal forma que não é fácil para um atacante alterar o texto encriptado sem 
invalidar esta relação.

\begin{algorithm}[h] % Enc
  \Entrada{$\vec{m}$ mensagem que Beto quer enviar a Alice \\
  \myinput{$\pk$ a chave pública de Alice}
  }
  \Saida{$\vec{c}$ o texto cifrado da mensagem $\vec{m}$}
  \Inicio{
    $(\mat{G}, t) \gets \pk$ \\
    $\vec{r} \gets $ vetor de bits aleatórios ($\approx 160$ bits) \\
    $z \gets \alg{Hash}([\vec{r} | \vec{m}])$ \\
    $\vec{y} \gets \alg{PRNG}(z) + [\vec{r} | \vec{m}]$ \\
    $\vec{e}_z \gets \alg{InteiroParaVetor}(z)$ \\
    $\vec{c} \gets (\vec{y}\mat{G} + \vec{e}_z) $ \\
    \Retorna{$\vec{c}$}
  }
  \caption{$\alg{Encripta}_\alpha$ : 
    conversão IND-CCA2 de \alg{Encripta} \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{$\vec{m}$ a decifração de $\vec{c}$}
    \Inicio{
        $\vec{y} \gets \alg{Decripta}(\alg{Esquerda}(\vec{c}, k), \sk)$ \\
        $\vec{e}_z \gets \alg{Esquerda}(\vec{c}, k) + \vec{y}\mat{G}$ \\
        $z \gets \alg{VetorParaInteiro}(\vec{e}_z) $ \\
        $ [\vec{r} | \vec{m}] \gets \alg{PRNG}(z) + \vec{y} $\\
        \Se{$z = \alg{Hash}([\vec{r} | \vec{m}])$}{
            \Retorna{$\vec{m}$}
        }
        \Senao{
            \Retorna{$\perp$}
        }
    }
    \caption{$\alg{Decripta}_\alpha$: conversão IND-CCA2 de \alg{Decripta} \cite{kobara2001semantically}}
    \label{alg:mce_dec_ki_conv}
\end{algorithm}



