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


\chapter{Esquema de McEliece com códigos QC-MDPC}
\label{cap:mdpc}
Em 2013, uma nova variante do Esquema de McEliece foi proposta por
Misoczki et al.~\cite{misoczki2013mdpc}. Esta variante usa códigos QC-MDPC, que são
códigos lineares binários que admitem uma matriz de paridade quase cíclica e moderadamente
esparsa, em contraste com as de baixa densidade dos códigos LDPC de Gallager~\cite{gallager1962low}.

A ideia dos autores foi fortalecer o esquema de McEliece com códigos LDPC~\cite{shokrollahi2000using},
aumentando a densidade da matriz de paridade de forma que a busca por linhas esparsas da matriz de paridade
ficasse intratável, obtendo códigos chamados MDPC. Mas como as chaves públicas usando códigos MDPC
ainda eram muito grandes, os autores mostraram como introduzir certa ciclicidade nas matrizes, de
modo a manter o esquema seguro, e obter chaves compactas comparáveis às do RSA.

Além da variante de Misoczki et al.\, há duas outras variantes que usam códigos QC-MDPC,
como a chamada QC-MDPC suave~\cite{baldi2016soft}, e a QC-MDPC $p$-ária~\cite{guo2016p}.
Ainda não se sabe como o ataque de Guo e Johansson afeta a segurança desses dois
esquemas últimos esquemas.


\section{Códigos QC-MDPC}

\begin{definition}[Códigos MDPC e QC-MDPC~\cite{misoczki2013mdpc}]
  Um \emph{código $(n, r, w)$-MDPC} é um código linear de comprimento $n$, e codimensão
  \footnote{A codimensão de um código é a dimensão de seu espaço dual, ou equivalentemente o número de linhas
  de uma sua matriz de paridade.}
  $r$, que admite uma matriz de verificação de paridade $H$ cujas linhas têm mesmos
  pesos iguais a $w = \mathcal{O} \left( \sqrt{n \log n} \right)$.

  Quando $H$ é quase cíclica, um tal código é dito um \emph{código $(n, r, w)$-QC-MDPC}. Quando não
  há dúvidas de que código estamos tratando, denotamos por $n_0$ o número de blocos cíclicos de $H$.
  E como blocos cíclicos são matrizes quadradas $r \times r$, é claro que $n_0 = \frac{n}{r}$.
\end{definition}

Assim, por definição, a matriz de paridade de um código $(n, r, w)$-QC-MDPC
é da forma
\[
  H = \left[
    \, H_0 \, | \, H_1 \, | \, \ldots \, | \, H_{n_0 - 1} \,
  \right].
\]


Onde cada $H_i$ é cíclica. Então $H$ é completamente descrita pela sua primeira
linha, e seu número de linhas $r$, ou equivalentemente o número de blocos $n_0$.

Supondo que $H_{n_0 - 1}$ é inversível, o que será garantido pelo algoritmo
de construção de códigos MDPC da Seção~\ref{sec:construcao_mdpc}, é fácil verificar
que uma possível matriz geradora do código de matriz de paridade $H$ é\@
\begin{equation}
\label{eq:mdpc_matriz_geradora}
  G = \left[
    % \begin{matrix}
      \qquad I \qquad
    % \end{matrix}
    \, \middle\vert \,
    \begin{matrix}
      {\left( H_{n_0 - 1}^{-1} \cdot H_0 \right)}^T \, \\ \addlinespace
      {\left( H_{n_0 - 1}^{-1} \cdot H_1 \right)}^T \, \\ \addlinespace
      \vdots \, \\ \addlinespace
      {\left( H_{n_0 - 1}^{-1} \cdot H_{n_0 - 2}\right)}^T  \,

    \end{matrix}
  \right].
\end{equation}

Em todo o resto deste texto, supomos que a matriz geradora $G$ está na forma
sistemática, pois não há perda de segurança quando se usa conversões IND-CCA2,
como a de Kobara e Imai.

\subsection{Construção do código}
\label{sec:construcao_mdpc}

Para construir um código $(n, r, w)$-QC-MDPC aleatório, basta escolher aleatoriamente um
vetor linha $h$, de comprimento $n$ e peso $w$, cujas últimas $r$ colunas
gerem uma matriz quase cíclica inversível. Assim, usa-se esse vetor $h$ como gerador
da matriz quase cíclica $H$, de verificação de paridade. E claro que a matriz
geradora poderá ser derivada de $H$ a partir da Equação~\ref{eq:mdpc_matriz_geradora}.

Um modo simples de agilizar a construção de códigos QC-MDPC, é observar que
a álgebra das matrizes cíclicas $r \times r$ é isomorfa à dos polinômios
em $ \mathbb{F}_2[x] $ módulo $x^r - 1$. Dessa forma, as multiplicações e inversões de
matrizes são computacionalmente eficientes.


Tipicamente, as matrizes de paridade dos códigos usados no QC-MDPC McEliece têm
apenas dois blocos. Como exemplo, considere as matrizes de paridade e geradora de um código
$(40, 20, 6)$-QC-MDPC mostradas, respectivamente, à esquerda e à direita na
Figura~\ref{fig:check_gen_matrices_qcmdpc}.

\begin{figure}[H]
    \includegraphics[width=.45\textwidth]{figuras/mdpc/check_mat.pdf}
    \includegraphics[width=.45\textwidth]{figuras/mdpc/gen_matrix.pdf}
    \caption{Matrizes de paridade e geradora, respectivamente à esquerda e à direita,
    de um código $(40, 20, 6)$-QC-MDPC.}
    \label{fig:check_gen_matrices_qcmdpc}
\end{figure}


\subsection{Codificação}

A codificação de um vetor $m$ é simplesmente o vetor $c$, produto da
multiplicação $c = mG$. E, como $G$ tipicamente está na forma sistemática $G = [\, I \mid P \,]$,
a codificação é ligeiramente simplificada para $c = m\|mP$.

\subsection{Decodificação}


Por serem baseados nos códigos LDPC, é comum decodificar códigos MDPC com
algoritmos daqueles códigos. Mas como as matrizes de verificação de paridade
de códigos MDPC são mais densas, é de se esperar que os algoritmos de decodificação
para códigos LDPC não sejam tão eficientes. Isso motivou algumas melhorias para
diminuir tanto para diminuir o número de iterações para a decodificação, quanto
para diminuir a probabilidade de falha.

Há duas classes de códigos LDPC, os por decisões abruptas, e os por decisões suaves.
Com algoritmos de decisão dura, a decodificação de uma mensagem transmitida é feita através de
sucessivas inversões de seus bits, até possivelmente chegar na mensagem original.
Por sua vez, os de decisão suave usam algoritmos de propagação de crença
sobre a probabilidade de determinado bit da
mensagem transmitida ser 1 ou não.

Para adquirir certa intuição sobre as duas classes de decodificadores, considere as
Figuras~\ref{fig:decod_dura} e~\ref{fig:decod_suave}. Elas mostram a decodificação
de uma palavra $c' = c \oplus e$ para a palavra $c$. A primeira mostra a decodificação
usando o algoritmo de \emph{bit-flipping}, e a segunda mostra a mesma decodificação usando o algoritmo de
propagação de crença. Os dois exemplos são decodificações para um código LDPC real gerado
aleatoriamente. Este código tem tamanho $n = 50$, dimensão $k = 25$, e tem colunas de mesmo
peso $w_c = 4$. Não é feito nenhum controle sobre o peso das linhas, nem sobre a
maximização da cintura. E os algoritmos que implementei são os mesmos de Gallager.

\begin{figure}[htpb]
  \includegraphics[width=\textwidth] {figuras/teocod/hard_decision_dec.pdf}
  \caption{Decodificação por decisão dura.}
\label{fig:decod_dura}
\end{figure}


\begin{figure}[htpb]
  \includegraphics[width=\textwidth]{figuras/teocod/soft_decision_dec.pdf}
  \caption{Decodificação por decisão suave.}
\label{fig:decod_suave}
\end{figure}

Apesar de serem capazes de corrigir mais erros, os decodificadores por decisões
suaves são significativamente mais lentos do que os por decisão abruptda. Por isso,
e por terem implementação e análise mais fáceis, os decodificadores por decisão
abrupta são mais comuns. Em particular, Misoczki et al. sugerem o uso de um
decodificador por decisão abrupta, que é uma variação do algoritmo de \emph{bit-flipping},
e é descrito pelo Algoritmo~\ref{alg:rafael_bit_flipping}. Para uma análise experimental detalhada de variantes do algoritmo de \emph{bit-flipping}
aplicados a códigos QC-MDPC, veja o estudo de Hayse, Maurich, e Güneysu~\cite{heyse2013smaller}.



\begin{algorithm}[H]
  \Entrada{$H$ matriz de paridade $r \times n$ de um código LDPC.\\
    \myinput{$y$ uma palavra transmitida a ser decodificada.}
    \myinput{\texttt{max\_it} o número máximo de iterações.}
  }
  \Saida{Uma decodificação estimada de $y$, ou $\perp$ se o número máximo de
         iterações for excedido.}
  \Inicio{
    $s \gets Hy$ \\
    \texttt{it} $\gets$ 0 \\
    \Enqto{$ s \neq 0 $ e \emph{\texttt{it}} < \emph{\texttt{max\_it}}}{
      \Para{cada $j = 1, 2, \ldots, n$}{
        $ f_j \gets \left|\{ \, i : s_i h_{ij} = 1 \text{ para } i = 1, \ldots, r \, \}\right| $
      }
      $\texttt{max\_upc} \gets \max \left\{ f_j \right\} $ \\
      \Para{cada $j = 1, 2, \ldots, n$}{
        \Se{$f_j \geq \texttt{\emph{max\_upc}} - \delta $}{
          $y_j \gets \bar{y_j}$
        }
      }
      $s \gets Hy$ \\
    }
    \Se{$s = 0$}{
      \Retorna{$y$}
    }
    \Senao{
      \Retorna{$\perp$}
    }
  }
  \caption{Variante do algoritmo de \emph{bit-flipping} sugerido Misockzi et al.~\cite{misoczki2013mdpc}. }
\end{algorithm}
\label{alg:rafael_bit_flipping}

\section{QC-MDPC McEliece}

\begin{definition}[Esquema de McEliece]

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

    \textbf{\alg{KeyG}en} é 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, r, w, t)$ de uma família $\mathcal{F}$ de códigos
            de QC-MDPC que suporta um nível de segurança $\lambda$ usando, por exemplo,
            a Tabela~\ref{tab:mdpc_param_sugerido}.
        \item Tome $\bar{H}$ uma matriz de paridade escolhido aleatoriamente da família $\mathcal{F}$.
        \item Calcule $G$ sistemática tal que $GH^T = 0$ usando a Equação~\ref{eq:mdpc_matriz_geradora}.
        \item Construa $h_i$, e $g_j$, as primeiras linhas de cada bloco cíclico de $H$ de $G$, respectivamente. E faça
        \[
            h \gets h_0 \| h_1 \| \ldots \| h_{n_0}, \qquad {e} \qquad g \gets g_0 \| g_1 \| \ldots \| g_{n_0 - 1}.
        \]
        \item Devolva o par de chaves secreta e pública, dados respectivamente por
        \[
        \sk \gets (h, r), \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 Construa a matriz geradora sistemática $G$ usando as primeira linhas
                de cada bloco cíclico $g$.
        \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 pública em $(h, r) \gets \pk $.
        \item Construa a matriz de paridade $H$ usando a primeira linha $h$ e
                o tamanho de cada bloco $r$.
        \item Use o algoritmo de \emph{bit-flipping} com a matriz esparsa $H$
            para decodificar $ \vec{c} $ e obter $m$.
        \item Se o algoritmo falhar, peça para o remetente reenviar a mensagem,
            que com alta probabilidade será encriptada com um padrão de erros que
            o decodificador pode corrigir.
    \end{enumerate}

\end{definition}



Os parâmetros sugeridos para alguns níveis de segurança são descritos na Tabela~\ref{tab:mdpc_param_sugerido}.

\begin{table}[H]
\centering
\caption{Parâmetros sugeridos para cada nível de segurança.}
\label{tab:mdpc_param_sugerido}
\begin{tabular}{@{}ccccccc@{}}
\toprule
Segurança & $n_0$ & $n$   & $r$   & $w$ & $t$ & Tamanho da Chave \\ \midrule
80        & 2     & 9602  & 4801  & 90  & 84  & 4801             \\
128       & 2     & 19714 & 9857  & 142 & 134 & 9857             \\
256       & 2     & 65542 & 32771 & 274 & 264 & 32771            \\ \bottomrule
\end{tabular}
\end{table}

Note que, para códigos QC-MDPC, não há necessidade das matrizes embaralhadoras
$S$ e $P$. Isso pois, com conversões IND-CCA2, não há vazamentos sobre informações
da mensagem mesmo usando $G$ sistemática, e é supostamente difícil de se
obter $H$ a partir de $G$.

A redução de segurança do QC-MDPC McEliece se baseia na hipótese de que é difícil
distinguir códigos QC-MDPC de códigos apenas quase cíclicos, que é um problema
próximo ao de encontrar palavras de pesos baixos em códigos lineares. E sob essa
hipótese razoável, prova-se que quebrar o esquema QC-MDPC não é mais fácil do que
resolver o problema da decodificação por síndrome, que é conhecidamente \cNP-difícil,
e conjecturado tipicamente difícil. Porém, essa boa redução de segurança,
baseada em problemas aceitos como difíceis, não leva em conta o fato de
o algoritmo de decriptação falhar com certa probabilidade, em torno de 0.1\%~\cite{maurich2015implementing}.
Como a falha gera um pedido ao remetente, um ataque de reação é possível.

\section{Ataque de reação aos códigos QC-MDPC}

Na AsiaCrypt 2016, Guo, Johansson, e Stankovski~\cite{guo2016key} mostraram
um ataque de reação para a recuperação de chave para o esquema de McEliece instanciado
com códigos QC-MDPC. O ataque é inteiramente derivado da obervação de que a probabilidade de haver um
erro de decodificação de um vetor $\vec{c} = \vec{m} \oplus \vec{e}$ é menor quando o
a primeira linha do primeiro bloco cíclico $\vec{h}_0$, e o vetor de erro $\vec{e}$,
compartilham algumas propriedades. Dessa forma, uma atacante Eva envia desafios
de decodificação com erros artificialmente construídos, de modo a capturar
informações estruturais sobre a $\vec{h}_0$. Depois, com essas informações,
Eva reconstroi o vetor $\vec{h}_0$, e com $H_0$ e a chave pública,
a atacante recupera a chave $H$ completamente.


\subsection{Descrição do ataque}

A informação sobre \hz que o ataque é capaz de recuperar o seu espectro,
que é o conjunto das menores distâncias cíclicas entre as suas entradas não nulas.
A definição formal de distância cíclica é dada a seguir.

\begin{definition}[Distância cíclica e par $d$-distante]
    Seja $e$ um vetor de comprimento $r$ com elementos. A \emph{distância cíclica} entre duas
    posições $i$ e $j$ o único inteiro positivo $d$ menor do que $\lfloor r/2 \rfloor$
    tal que $d \equiv j - i \mod r$ ou $d \equiv i - j \mod r$.

    Dizemos que um par de índices $(s_1, s_2)$ é \emph{d-distante} se sua distância cíclica é $d$.
\end{definition}


Formalmente, o espectro é definido a seguir.


\begin{definition}[Espectro]
  Seja $v = [v_1 \, \ldots \, v_r ]$ um vetor de comprimento $r$ com elementos em $\mathbb{F}_2$. O espectro de $v$,
  denotado por $\sigma(v)$, é o conjunto
  \[
    \sigma(v) = \left\{ d \in \mathbb{Z} : \text{existe um par $d$-distante de entradas não nulas em $v$} \right\}.
  \]
\end{definition}

Como exemplo, considere o vetor $[1 \, 0 \, 0 \, 1 \, 0 \, 1 \, 0 \, 0 \, 0 \, 1]$. Seu espectro é o
conjunto $\{ 1, 2, 3, 4, 5 \}.$ Note que uma distância cíclica entre elementos de
um vetor de comprimento $r$ sempre é igual ou inferior a $\lfloor r/2 \rfloor$, e o número
máximo de elementos distintos de seu espectro é igual a $\lfloor r/2 \rfloor$.

O ataque consiste em duas fases: a de recuperação do espectro de \hz, e a de reconstrução de \hz a partir
de seu espectro. A ideia é enviar mensagens encriptadas com erros artificiais de modo
a testar cada uma das possíveis distâncias, $d = 1, \ldots, \lfloor r/2 \rfloor$, e usar
a taxa de falha do decodificador para descobrir se cada $d$ está ou não em $\sigma(\hz)$.
Para testar cada distância $d$, os autores introduzem um conjunto de erros chamado $\Psi_d$,
definido a seguir.

\begin{definition}[Conjunto $\Psi_d$]
    Suponha que queremos obter informações sobre uma chave privada de um código de comprimento $n$,
    codimensão $r = n/2$,
    e que corrige $t$ erros. O \emph{conjunto de testes da distância $d$} é definido como o conjunto
\[
  \Psi_d = \left\{ \, \left( \vec{e} \mid \vec{0} \right) : \text{ e $e$ tem $\frac{t}{2}$ pares distintos de índices d-distantes}  \, \right\},
\]
    em que o comprimento de $\vec{e}$ é igual a $r$.
\end{definition}

Os autores do ataque observaram que para cada distância $d$, quando a encriptação usa erros
em $\Psi_d$, a taxa de falha de decodificadores por \emph{bit-flipping} tende a ser mais significativamente
mais baixa quando $d$ pertence ao espectro de \hz do que quando $d$ não pertence ao espectro.
Isso acontece pois, quando $d \in \sigma(\hz)$, os erros em $\Psi_d$ fazem com que
a primeira iteração do algoritmo de \emph{bit-flipping} tenha mais sucesso na primeira iteração.
Na próxima seção, analisamos o ataque um pouco mais detalhadamente.


\subsection{Explicação do ataque}

Como o algoritmo de \emph{bit-flipping} tipicamente termina em poucas iterações,
o seu desempenho na primeira iteração é crítico para que ele possa corrigir o
padrão de erros. Nesse algoritmo, cada variável $v_j$ tem um contador associado
$f_j$. Este contador é incrementado quando $v_j$ faz parte de uma equação de
paridade não satisfeita. Analisando a primeira iteração do algoritmo na decodificação
de um vetor $\vec{c} = \vec{m} \oplus \vec{e} = [v_1, v_2, \ldots, v_n]$, temos que a síndrome
de $\vec{c}$ é
\[
  \vec{s} = \vec{c}H^T = \vec{e}H^T = [ s_1, s_2, \ldots, s_r],
\]


onde cada $s_i$ é da forma
\[
  s_i = \sum_{j=1}^{n} h_{ij} e_j.
\]

Dessa forma, se $s_i = 0$, a equação foi satisfeita, e nenhum contador é incrementado.
E se $s_i = 1$, são incrementados os contadores de cada variável que aparece
na equação $i$.

Podemos analisar a primeira iteração de decodificação um pouco mais detalhadamente,
ao considerar quantos contadores são incrementados corretamente. Para simplificar
a escrita, chame de $\lambda_j$ o número de colunas de $e$ tais que $h_{ij} = 1$, ou seja
$ \lambda_j = \# \{j : h_{ij}e_j = 1\}$. Note que $\lambda_j = s_j \mod 2$, mas em geral
$\lambda_j \neq s_j$, então $s_j$ só nos dá informação sobre a paridade de $\lambda_j$.

Se $\lambda_j = 0$ temos que a equação $j$
não poderia identificar nenhum bit incorreto, e os contadores das
$w$ variáveis na equação $j$ não são modificados. Por outro lado, se $\lambda_j  = 1$, temos que a equação $j$
captura apenas $1$ bit incorreto, mas incrementa todos os contadores das suas $w$ variáveis, sendo que
apenas $1$ dos contadores deveria ser incrementado.

Dizemos que $l$ contadores são \emph{tratados corretamente} quando uma equação
insatisfeita incrementa $l$ contadores de variáveis que estavam em erro,
ou quando uma equação satisfeita deixa de incrementar $l$ contadores que não
estavam em erro. Analogamente, dizemos que que $l$ contadores são
\emph{tratados incorretamente} quando uma equação
insatisfeita deixa de incrementar $l$ contadores de variáveis que não estavam em erro,
ou quando uma equação satisfeita deixa de incrementar $l$ contadores que
estavam em erro. É claro, pela definição, que a soma do número de contadores tratados
correta e incorretamente numa equação é sempre $w$.
A Tabela~\ref{tab:tratamento_contadores} mostra a relação entre $ \lambda_j $
e o tratamento dos contadores.

\begin{table}[H]
\centering
\caption{Relação entre $ \lambda_j $ e o número de contadores tratados correta ou incorretamente.}
\label{tab:tratamento_contadores}
\begin{tabular}{@{}ccc@{}}
\toprule
$ \lambda_j $ & \begin{tabular}[c]{@{}c@{}}contadores tratados \\ corretamente\end{tabular} & \begin{tabular}[c]{@{}c@{}}contadores tratados\\ incorretamente\end{tabular} \\ \midrule
$0$                           & $w$                                                                          & $0$                                                                           \\
$1$                           & $1$                                                                          & $w - 1$                                                                           \\
$2$                           & $w - 2$                                                                      & $2$                                                                           \\
$3$                           & $3$                                                                          & $w - 3$                                                                           \\
$\vdots$                      & $\vdots$                                                                     & $\vdots$                                                                           \\
\bottomrule
\end{tabular}
\end{table}


Assim, para o decodificador cometer menos erros na primeira iteração, é
interessante que $ \lambda_j $ seja um número par pequeno, ou um
ímpar grande. Em particular, queremos aumentar a probabilidade de $ \lambda_j $ ser
$0$ com alta probabilidade, e diminuir a probabilidade de $\lambda_j$ ser $1$.
O ataque constroi erros que aumentam a probabilidade de a primeira
iteração ser boa se os erros e a chave compartilharem distâncias entre as entradas
não nulas.

Para os testes de decodificação, os erros serão retirados aleatoriamente dos conjuntos $\Psi_d$.
Quando selecionamos erros em $\Psi_d$, e existe ao menos um par $d$ distante em $\vec{h}_0$, então
garantidamente imporemos um par de uns em ao menos $t/2$ equações, como ilustra a Figura~\ref{fig:ddistantes}.
. Essa mudança na distribuição
de $\lambda_j$ é detectável por meio de simulações, e a mudança relatada pelos autores está na
Tabela~\ref{tab:lambdas_dist}. Com a probabilidade de $\lambda_j$ ser 0 ser ligeiramente aumentada\%,
e a probabilidade de $\lambda_j$ ser 1 ser ligeiramente diminuida, quando $\vec{h}_0$ contém um
par $d$-distante, a probabilidade de a primeira iteração tratar corretamente mais contadores é maior.

\begin{figure}[H]
    \includegraphics[width=0.5\textwidth]{figuras/mdpc/heatmap.pdf}
    \caption{Erro em $\Psi_4$ sobreposto a um bloco cíclico.}
    \label{fig:ddistantes}
\end{figure}



\begin{table}[]
\centering
\caption{Diferentes distribuiçãoes de $\lambda_j$ quando os erros são tirados de $\Psi_d$.}
\label{tab:lambdas_dist}
\begin{tabular}{@{}ccc@{}}
\toprule
\multirow{2}{*}{$\lambda_j$} & \multicolumn{2}{c}{Probabilidade}                                                                                                                                                            \\ \cmidrule(l){2-3}
                             & \begin{tabular}[c]{@{}c@{}}$\vec{h}_0$ não \\ contém nem um \\ par $d$-distante\end{tabular} & \begin{tabular}[c]{@{}c@{}}$\vec{h}_0$ contém \\ ao menos um \\ par $d$-distante\end{tabular} \\ \midrule
0                            & 0.4485                                                                                       & 0.4534                                                                                        \\
1                            & 0.3663                                                                                       & 0.3602                                                                                        \\
$ \geq 2$                    & 0.1852                                                                                       & 0.1864                                                                                        \\ \bottomrule
\end{tabular}
\end{table}


Por meio de simulações, os autores encontraram a distribuição das taxas de erros, quando
há ou não distâncias $d$-distantes. Eles sugerem que as distribuições podem ser aproximadas para
distribuições normais, com certas médias e variâncias mostradas na Tabela~\ref{tab:taxas}.
Assim, por meio de testes de hipótese, é possível classificar uma distância como
existente ou não em $\vec{h}_0$.

\begin{table}[H]
\centering
\caption{Taxas médias de falhas de decodificação quando há ou não pares $d$-distantes em $\vec{h}_0$.}
\label{tab:taxas}
\begin{tabular}{@{}clc@{}}
\begin{tabular}[c]{@{}c@{}}Existe par $d$-distante\\ em $\vec{h}_0$?\end{tabular} & Taxa média de erro & Desvio padrão      \\
Sim                                                                               & 0.0044099          & 0.00003868         \\
Não                                                                               & $\leq 0.0009116$  & $\leq 0.00001304$
\end{tabular}
\end{table}


O Algoritmo~\ref{alg:calc_espectro} formaliza os passos que vimos até agora para
encontrar o conjunto de distâncias existentes em $\vec{h}_0$.

\begin{algorithm}[H]
  \Entrada{Parâmetros $n, r, w, t$ do código QC-MDPC. \\
    \myinput{$\mathcal{D}$ o oráculo de reação do decodificador.}
    \myinput{$M$ o número de desafios de decodificação para cada distância.}
  }
  \Saida{$\sigma(\vec{h}_0)$ o espectro de \hz.}
  \Inicio{
    \Para{cada distância $d = 1, 2, \ldots, \lfloor \frac{r}{2} \rfloor $ } {
      $p \gets 0$ \\
      \Para{cada iteração $i = 1, 2, \ldots, M$}{
        $e \xleftarrow{\$} \Psi_{d}$ \\
        $\vec{c} \xleftarrow{\$} \mathcal{C}$ \\
        \Se{$\mathcal{D}(c \oplus e) = 1$}{
          $ p \gets p + 1 $
        }
      }
      Decida se $d \in \sigma(\hz)$ com base na proporção $\frac{p}{M}$ \\
    }
    \Retorna{$\sigma(\vec{h}_0)$}
  }
  \caption{Cálculo do conjunto de distâncias em $\vec{h}_0$ como em \cite{guo2016key}}
  \label{alg:calc_espectro}
\end{algorithm}



E finalmente, depois de calculado o conjunto de distâncias existentes em $\vec{h}_0$, fazemos
uma busca em profundidade com as distâncias encontradas, usando o Algoritmo recursivo~\ref{alg:rec_h0}.
Essa busca encontra \hz, a menos de um \emph{shift} circular, o que não faz diferença, já que qualquer \emph{shift}
gera uma matriz equivalente a $H$. Também é fácil testar se a $\vec{h}_0$ é mesmo
o vetor, bastando recuperar $H$ por meio de álgebra linear simples, e ver se $G$ é o núcleo de $H$.

Primeiro, tome a menor distância do espectro, chamada $d_0$. Depois, construa
um conjunto com posições em potencial de \hz, chamado $\mathcal{B}$.
O conjunto $\mathcal{B}$ contém o subconjunto das posições possíveis $\{ 1, 2, \ldots, r-1 \}$
dos elementos para os quais as distâncias até a posição 0 e até a posição $d_0$ estejam no espectro. Ou seja:
\[
    \mathcal{B} = \{ b : \dist_c(b, 0) \in \sigma(\hz) \land \dist_c(b, d_0) \in \sigma(\hz) \}.
\]

Sendo $b_0 < b_1 < b_2 < \ldots $ uma ordenação do conjunto $\mathcal{B}$, faça uma busca em profundidade
na árvore da Figura~\ref{fig:profund_busca}. Quando a distância de um nó a um de seus ancestrais
não existir no espectro de \hz, busque o próximo nó filho de seu pai, se existir, ou suba de nível, recursivamente.
Apesar de parecer uma busca demorada, os autores notam que é esperado que a árvore passe a ter poucos filhos
rapidamente, devido à baixa probabilidade de várias distâncias em comum estarem no espectro.

\begin{figure}[H]

    \Tree   [.0
                [.$b_0$
                    [.$b_1$ [.$b_2$ $\vdots$ ]
                        [.$b_3$ $\vdots$ ]]
                    [.$b_1$ [.$b_2$ $\vdots$ ]
                        [.$b_3$ $\vdots$ ]]
                ]
            ]

    \caption{Árvore de busca de \hz.}
    \label{fig:profund_busca}
\end{figure}



\begin{algorithm}[H]
  \Entrada{Parâmetros $n, r, w, t$ do código QC-MDPC. \\
    \myinput{O conjunto de distâncias $\sigma(\vec{h}_0)$.}\\
    \myinput{Chave parcial $\vec{h}_0$.}
    \myinput{Nível da recursão $l$.}

  }
  \Saida{O vetor recuperado  $\vec{h}_0$ ou $\perp$ se não houver um vetor com espectro $\sigma(\vec{h}_0)$.}
  \Inicio{
    \Se {$l = w$}{
      \Retorna{$\vec{h}_0$}
    }
    \Para{todo bit $j = 1, \ldots, n$}{
      \Se{todas as distâncias entre bits não nulos e $j$ estiver em $\sigma(\vec{h}_0)$} {
        Adicione bit $j$ a $\vec{h}_0$ \\
        \textsc{Chamada recursiva}$(\sigma(\vec{h}_0), \vec{h}_0, l + 1)$ \\
        \Se{$\vec{h}_0$ for a chave secreta}{
          \Retorna{$\vec{h}_0$}
        }
        Remova bit $i$ de $\vec{h}_0$
      }
    }
    \Retorna{$\perp$}
  }
  \caption{Recuperação de $\vec{h}_0$.}
  \label{alg:rec_h0}
\end{algorithm}



% \begin{figure}[H]
%     \includegraphics[width=\textwidth]{figuras/mdpc/intro/hist_tempo_execucao.pdf}
%     \caption{Distribuição de frequências para o tempo de recuperação de $\vec{h}_0$ para 1000 códigos aleatórios.}
%     \label{fig:hist_spec}
% \end{figure}

Com pequenas modificações, o ataque pode funcionar até para conversões IND-CCA2
do esquema de McEliece, embora menos eficientemente. Claro que apenas a primeira
fase é afetada quando se usa conversões de segurança.

Restam alguns ramos de investigação
interessantes como a possibilidade de se recuperar a $\vec{h}_0$ mesmo com erros no conjunto de distâncias,
ou saber se o ataque funciona com decodificadores por decisões suaves.
