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

\chapter{Ataque de reação ao QC-MDPC McEliece}
\label{cap:ataque_guo}

Na AsiaCrypt 2016, Guo, Johansson, e Stankovski~\cite{guo2016key} mostraram
um ataque de recuperação de chave contra o QC-MDPC McEliece.
O ataque é inteiramente derivado da observação de que a probabilidade
de haver um erro de decodificação de um vetor $\vec{c} = \vec{m} + \vec{e}$ é 
menor quando a primeira linha da matriz esparsa secreta 
$\vec{h}$, e o vetor de erro $\vec{e}$,
compartilham algumas propriedades. Dessa forma, uma atacante Eva pode enviar
desafios de decodificação para a portadora da chave secreta, de modo a capturar
informações estruturais sobre $\vec{h}$. Depois, com estas informações,
Eva pode reconstruir a chave privada~$\vec{h}$. 


\section{Estimação do espectro da chave privada}

O ataque é composto por duas fases. Na primeira, chamada fase de estimação do
espectro, uma atacante envia desafios de decodificação visando obter informação
sobre a chave secreta usada pelo decodificador. A obtenção da informação é feita
através da reação do decodificador, isto é, se o decodificador teve sucesso ou não.
Na segunda fase, chamada
de reconstrução a partir do espectro, a atacante usa as informações obtidas na primeira
fase para reconstruir a chave.

A partir de um número suficiente de reações do decodificador,
é possível, para cada bloco cíclico da chave secreta,
recuperar os conjuntos das distâncias circulares entre as posições não nulas de
cada bloco. Uma distância circular é simplesmente a menor distância entre duas posições, 
supondo que o vetor é circular. 

\begin{definition}[Distância circular e par $d$-distante]
    Seja $\vec{e}$ um vetor binário de comprimento $r$. 
    A distância circular entre duas 
    posições $i$ e $j$ de $\vec{e}$, denotada por $\dist_r(i, j)$,
    é o único inteiro positivo $d$ tal que $ d \leq \lfloor r/2 \rfloor$
    e $d \equiv j - i \mod r$ ou $d \equiv i - j \mod r$.
    Dizemos que o par de índices $s_1$ e $ s_2$ é $d$-distante se sua distância cíclica é $d$.
\end{definition}

\begin{example}
Considere o vetor $\vec{e} = [0\,1\,0\,0\,0\,0\,0\,0\,0\,1\,0]$ de 11 posições. 
As duas posições de suas entradas não nulas são 2 e 10. Então as possíveis distâncias
circulares
entre estas entradas são
os valores $10 - 2 = 8 \mod 11$ e $2 - 10 = -8 \equiv 3 \mod 11$. Como,
dentre os valores possíveis, somente $3$ é menor que ou igual a$\lfloor 11/2 \rfloor$, 
então $\dist_{11}(2, 10) = 3$.
\end{example}

O conjunto de todas as distâncias circulares entre posições de entradas não nulas de um vetor
é chamado de seu espectro. Por esta definição, pode-se ver que o espectro de um vetor é invariante
em relação a rotações de um vetor. Portanto os espectros de todas as linha de uma matriz 
cíclica são iguais. O espectro de um vetor $\vec{v}$ é denotado por $\sigma(\vec{v})$ e 
sua definição formal é dada a seguir.

\begin{definition}[Espectro]
  Seja $\vec{v}$ um vetor binário de comprimento $r$. O espectro de $v$,
  denotado por $\sigma(\vec{v})$, é o conjunto
  \[
    \sigma(\vec{v}) = \left\{ d \in \mathbb{N} : \text{existe um par $d$-distante de entradas não nulas em $\vec{v}$} \right\}.
  \]
O número máximo de distâncias no espectro de um vetor de $r$ posições é igual ao número
de distâncias circulares possíveis, isto é $|\sigma(\hz)| \leq \lfloor r/2 \rfloor$.
\end{definition}

Considere que $\vec{c}$ é um texto que foi encriptado usando o erro
$\vec{e} = [ \vec{e}_0 | \ldots | \vec{e}_{n_0 - 1}]$, 
em que $|\vec{e}_i| = r$, para $i = 0, 1, \ldots, n_0 - 1$.
Então $\vec{c} = \vec{m}\mat{G} + [ \vec{e}_0 | \ldots | \vec{e}_{n_0 - 1}]$. 
Guo et al. observaram que 
a probabilidade de o decodificador falhar ao tentar corrigir o erro $\vec{e}$ é 
mais baixa quanto maiores forem os conjuntos $\sigma(\vec{e}_i) \cap \sigma(\vec{h}_i)$.
Isso acontece pois, quanto maiores as interseções, maior a chance de a decodificação 
ter sucesso na primeira iteração. Uma explicação de por que isso ocorre pode
ser vista na Seção~\ref{sec:explica_guo}.

Na visão do atacante, o ideal seria que ele pudesse escolher com quais erros encriptar
a mensagem de modo a testar suas hipóteses sobre quais distâncias estão dentro do espectro de \hz.
Por exemplo, para testar se uma distância $d$ está no espectro, o atacante poderia
enviar textos cifrados com erros em que grande parte dos pares de suas entradas não nulas
esteja à distância circular de $d$ posições. O problema é que, quando são usadas conversões
IND-CCA2, o atacante não tem controle sobre o vetor de erro. A solução apresentada por Guo et al.
é usar, para cada distância $d$, um valor $\vec{p}_0[d]$ que estima a sua taxa de falha. 
A taxa de falha de uma distância é a razão entre o número de vezes em que ela aparece num
vetor de erros que não foi decodificado corretamente, e o número total de vezes em que ela
aparece nos vetores de erros testados. Ao final do experimento, o vetor $\vec{p}_0[d]$ pode
ser usado para distinguir distâncias dentro e fora do espectro, usando algoritmos de agrupamento (\emph{clustering}). O Algoritmo~\ref{alg:spec_recovery_guo} formaliza o procedimento 
para obter o vetor $\vec{p}_0$. É difícil estimar a priori qual o valor do número de testes de decodificação necessários $M$. Guo et al. usam simulações para isso, e observaram que,
para o nível de segurança de 80 bits, $M = 200$ milhões parece ser, em média,
suficiente para que se possa distinguir as distâncias dentro e fora do espectro de \hz.
A Seção~\ref{cap:estima_espectro} mostra uma análise mais detalhada desse algoritmo.

\begin{algorithm}[ht]
  \Entrada{$n, r, w, t$ parâmetros do código QC-MDPC atacado \\
    \myinput{$\mathcal{D}$ oráculo de reação para o decodificador (devolve 1 para sucesso, ou 0 para falha)}
    \myinput{$M$ número de testes de decodificação}
  }
  \Saida{$\vec{p}_0$ estimativas das taxas de falha para possíveis distâncias em 
  $\sigma(\hz)$}
  \Inicio{
    $\vec{a}_0,\vec{b}_0 \gets $
      vetores com $\lfloor r/2 \rfloor$ entradas inicialmente todas iguais a 0 \\

    \Para{cada teste de decodificação $i = 1, 2, \ldots, M$} {
      $\vec{c} \gets $ um texto aleatório encriptado com erro 
         $ \vec{e} = [ \, \vec{e}_0 \, | \, \vec{e}_x \, ]$, em que $|\vec{e}_0| = r$ \\

      $v = \mathcal{D}(\vec{c})$ \\

      \Para{cada distância $d$ em $\sigma(\vec{e}_0)$} {
        $\vec{a}_0[d] \gets \vec{a}_0[d] + v$ \\
        $\vec{b}_0[d] \gets \vec{b}_0[d] + 1$ \\
      }
    }
    $\vec{p}_0 \gets $ vetor com $\lfloor r/2 \rfloor$ entradas iguais a 0 \\
    \Para{cada distância $d$ em $\{ 1, 2, \ldots, \lfloor r/2 \rfloor \}$ }{
      $\vec{p}_0[d] \gets \vec{a}_0[d]/\vec{b}_0[d]$ \\
    }
  \Retorna{$\vec{p}_0$}
  }
  \caption{Estimação das taxas de falha de decodificação para as 
    possíveis distâncias em $\sigma(\hz)$}
  \label{alg:spec_recovery_guo}
\end{algorithm}



\section{Como o espectro da chave afeta a decodificação de certos erros}
\label{sec:explica_guo}

Algoritmos de \emph{bit-flipping} tipicamente terminam em poucas 
iterações~\cite{maurich2015implementing},
de forma que seu desempenho na primeira iteração é crítico para que consigam corrigir os 
erros. Nestes algoritmos, 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. Considerando a primeira iteração do algoritmo na decodificação
de um vetor $\vec{c} = \vec{m}\mat{G} + \vec{e}$, a síndrome
de $\vec{c}$, em relação à matriz de paridade secreta $\mat{H} = (h)_{ij}$, é
\[
  \vec{s} = \vec{c}\mat{H}^T = \vec{e}\mat{H}^T = [ s_1, s_2, \ldots, s_r],
\]
em que cada $s_i$ é da forma
\[
  s_i = \sum_{j=1}^{n} h_{ij} e_j.
\]
Se $s_i = 0$, a equação $i$ foi satisfeita, e nenhum contador é incrementado.
Caso contrário, se $s_i = 1$, são incrementados os contadores de cada variável que aparece
na equação $i$. Um contador pode ser incrementado corretamente, isto é, quando $e_j = 1$, 
ou incorretamente, quando $e_j = 0$. 

Podemos analisar a primeira iteração de decodificação um pouco mais detalhadamente
ao considerar quantos contadores são incrementados corretamente.
Chame de $\kappa_i$ o número de posições de $\vec{e}$ tais que $e_j = 1$ e $h_{ij} = 1$, 
ou seja $ \kappa_i = \# \{j : h_{ij}e_j = 1\}$.
Intuitivamente, $\kappa_i$ é o número máximo de erros detectáveis pela 
linha $i$ da matriz $\mat{H}$.
Note que $\kappa_i \equiv s_j \mod 2$, mas em geral
$\kappa_i \neq s_j$. Então $s_j$ só dá informação sobre a paridade de $\kappa_i$.

Se $\kappa_i = 0$ temos que a equação $i$
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 $\kappa_i  = 1$, temos que a equação $i$ 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 $\ell$ contadores são \emph{tratados corretamente} quando uma equação
insatisfeita incrementa $\ell$ contadores de variáveis que estavam com erro $(e_j = 1)$,
ou quando uma equação satisfeita deixa de incrementar $\ell$ contadores de variáveis
que estavam sem erro $(e_j = 0)$. Analogamente, dizemos que $\ell$ contadores são
\emph{tratados incorretamente} quando uma equação
insatisfeita deixa de incrementar $\ell$ contadores de variáveis que estavam sem erro,
ou quando uma equação satisfeita deixa de incrementar $\ell$ contadores de variáveis que
estavam com erro. Pela definição, 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 $ \kappa_i $
e o tratamento dos contadores.

\begin{table}[H]
\centering
\caption{Relação entre $ \kappa_i $ e o número de contadores tratados correta ou incorretamente}
\label{tab:tratamento_contadores}
\begin{tabular}{@{}ccc@{}}
\toprule
$ \kappa_i $ & \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}


Para o decodificador cometer menos erros na primeira iteração, é
interessante que o número de contadores tratados corretamente seja alto. Ou seja,
o decodificador deve ter menor taxa de falha quando, para grande parte das equações $i$,
o valor de $\kappa_i$ for um número par pequeno ou um ímpar grande. 

A distinção entre distâncias dentro e fora do espectro ocorre pois, quando uma distância
$d$ pertence simultaneamente a $\sigma(\vec{h}_0)$ e a $\sigma(\vec{e}_0)$, 
é forçado, em ao menos uma equação, que 2 posições de uma mesma linha,
digamos $j_1$ e $j_2$, sejam tais que $h_{ij_1}e_{j_1} = 1$ e $h_{ij_2}e_{j_2} = 1$.
Isto faz com que a distribuição dos $\kappa_i$ tenda a ficar
mais concentrada em valores pares pequenos, o que diminui a probabilidade de o 
decodificador falhar. A Figura~\ref{fig:erro_sobreposto} ilustra o que ocorre
quando sobrepõe-se o erro
\[
  \vec{e}_0 = [0\,0\,0\,0\,1\,0\,0\,0\,1\,0\,0\,0\,0\,0\,0\,0\,0\,0\,0\,0],
\]
à matriz cíclica cuja primeira linha é dada por
\[
  \vec{h}_0 = [0\,0\,0\,0\,1\,1\,0\,0\,0\,1\,0\,0\,0\,1\,1\,0\,0\,0\,1\,0].
\]
Note que $\sigma(\vec{e}) = \{ 3 \}$, e que $\vec{h}_0$ 
tem três pares de 1's à distância circular de 3 posições. Isso impõe pares de posições
em que $h_{ij}e_j = 1$ em 3 linhas, a saber, as linhas 11, 16, e 20.
Esta pequena alteração na distribuição dos $\kappa_i$ é suficiente para, com um
grande número de testes de decodificação, distinguir distâncias dentro e fora do 
espectro de $\vec{h}_0$.

Note que uma discussão análoga pode ser feita para os vetores
$\vec{h}_1, \ldots, \vec{h}_{n_0 - 1}$. Então o algoritmo para distinguir distâncias 
dentro e fora do espectro também serve para cada um desses vetores.

\begin{figure}[h]
    \includegraphics[]{figuras/mdpc/heatmap.pdf}
    \caption{Erro $\vec{e}$ sobreposto à matriz $\mat{H}$, com destaque em preto para os pares de posições
    em que $h_{ij}e_j = 1$, impostos pela similaridade entre os espectros}
    \label{fig:erro_sobreposto}
\end{figure}


\section{Reconstrução da chave a partir do espectro}
\label{sec:reconst_guo}

Depois de identificado o espectro de $\vec{h}_0$ como
$\sigma(\vec{h}_0) = \{ s_1, s_2, \ldots, s_m \}$ , pode-se usá-lo para
reconstruir a chave. 
A proposta de Guo et al. é usar um algoritmo recursivo, que encontra a chave ao fazer uma
busca em profundidade numa árvore. Este procedimento é descrito pelo Algoritmo~\ref{alg:rec_h0}.
O algoritmo encontra \hz, a menos de uma rotação circular, o que não faz diferença,
já que qualquer rotação de $\hz$ gera uma matriz equivalente a $\mat{H}$. 
Para construir $\mat{H}$ a partir de $\vec{h}_0$, primeiro note que, conhecendo
a matriz pública $\vec{G}$ e $\vec{h}_0$, a atacante pode construir
os vetores $\vec{h}_1, \ldots, \vec{h}_{n_0 - 1}$ através da equação~\ref{eq:mdpc_matriz_geradora},
copiada a seguir
\begin{equation*}
  \mat{G} = \left[
    % \begin{matrix}
      \qquad \mat{I} \qquad
    % \end{matrix}
    \, \middle\vert \,
    \begin{matrix}
      {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_0 \right)}^T \, \\ \addlinespace
      {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_1 \right)}^T \, \\ \addlinespace
      \vdots \, \\ \addlinespace
      {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_{n_0 - 2}\right)}^T  \,

    \end{matrix}
  \right].
\end{equation*}
Uma vez que a atacante conhece cada um dos vetores $\vec{h}_i$, isto é, todas primeiras linhas
dos blocos cíclicos de $\mat{H}$,
ela pode facilmente construir $\mat{H}$.
Também é fácil testar se a matriz $\mat{H}$ recuperada é de fato a matriz secreta.
Basta verificar se $\mat{H}$ é uma matriz geradora do núcleo de $\mat{G}$, 
que é a matriz geradora pública, ou seja, testar se $\mat{G}\mat{H}^T = \mat{0}$.

A ideia do algoritmo de reconstrução é tentar recursivamente
colocar o máximo possível de 1's num vetor de tamanho $r$ sem que ocorra uma distância
fora do espectro. Quando é impossível colocar um 1 sem que apareça uma distância
fora do espectro, o algoritmo retira
o último 1 colocado, e retoma a partir da próxima posição possível para um 1.

Para que funcione corretamente, o algoritmo deve conhecer o peso do vetor $\hz$, denotado por
$\hat{w}$. Este valor não é conhecido a priori, porém a recomendação~\cite{misoczki2013mdpc} é que
o peso de $\hz$ seja próximo do de $\ho$, ou seja, $\hat{w} \approx {w}/2$.
Esta escolha garante que $\hz$ e $\ho$ sejam similarmente esparsos, o que é bom para a segurança do esquema.
Por exemplo, se $\ho$ fosse mais esparso que $\hz$, o atacante teria vantagem ao tentar
reconstruir $\ho$, que possui menos entradas não nulas.
Guo et al. consideram que $\hat{w} = {w}/2$ para o ataque, o que nem sempre é o caso, mas
é possível fazer uma pequena modificação em seu algoritmo para lidar com o caso em que $\hat{w} \neq {w}/2$.
A modificação consiste em fazer com que o algoritmo considere como candidato a chave qualquer vetor encontrado com peso dentro de um certo intervalo considerado. Como em geral há poucos candidatos com peso próximo de
$w/2$, e testar se um candidato a chave de fato é uma rotação de $\hz$ é pouco custoso, considerar um
intervalo para $\hat{w}$ não interfere tanto no custo do ataque. Para simplificar as descrições dos algoritmos,
consideramos que $\hat{w}$ é conhecido a priori.


\begin{algorithm}[h]
  \Entrada{$n, r, w, t$ parâmetros do código QC-MDPC a ser atacado\\
    \myinput{$\sigma(\vec{h}_0)$ o espectro de $\hz$}\\
    \myinput{$\hat{w}$ o peso do vetor $\vec{h}_0$}
    \myinput{$V$ o suporte parcial de uma rotação de \hz (inicialmente vale $\{1, 1 + s_1\}$)} \\
  }
  \Saida{$\vec{V}$ uma rotação do vetor $\hz$, ou $\perp$ se $\sigma(\vec{h}_0)$ for inválido}
  \Inicio{
    \Se {$|V| = \hat{w}$}{
        \Se{$V$ é o suporte de uma rotação de \hz} {
            \Retorna{$V$} 
        }
      \Retorna{$\perp$}
    }
    \Para{cada posição possível $j = 2, \ldots, n$}{
      \Se{$\dist_r(v, j) \in \sigma(\hz)$ para todo $v$ em $V$} { \label{lin:incapacidade_de_erros}
        Adicione $j$ a $V$ \\
        $\var{ret} \gets $ chamada recursiva usando o conjunto $V$ atual \\
        \Se{$ \var{ret} \neq \perp $}{
          $\vec{v} \gets $ vetor com suporte $V$\\
          \Se{$\vec{v}$ é uma rotação de $\hz$}{ \label{line:shady}
            \Retorna{$\vec{v}$}
          }
        }
        Remova $j$ de $V$
      }
    }
    \Retorna{$\perp$}
  }
  \caption{Algoritmo recursivo de reconstrução de chave~\cite{guo2016key}}
  \label{alg:rec_h0}
\end{algorithm}


O principal argumento para justificar a eficiência do algoritmo é que ramos da árvore
que não contêm a chave são podados pelo algoritmo num nível não muito baixo da árvore.
Seja $\alpha$ a fração das
$\lfloor r/2 \rfloor $ possíveis distâncias que pertencem a $\sigma(\hz)$, 
isto é $\alpha = |\sigma(\hz)|/ \lfloor r/2 \rfloor $. 
Digamos que a busca começa no nível 0 da árvore, em que já foram colocadas
as posições $1$ e $1 + s_1$ no suporte $V$. 
Para que uma posição $p$ seja válida para entrar no nível 1, 
ambas as distâncias $\dist_r(p, 1)$ e $\dist_r(p, 1 + s_1)$ devem pertencer a $\sigma(\hz)$.
Isso resulta em $r\alpha^2$ posições possíveis para o nível 1. Repetindo uma argumentação 
similar para níveis maiores, pode-se concluir que no nível $\ell$ são esperados em
torno de $r \alpha^{\ell}$ nós. Assim, o número de nós em cada nível
decresce exponencialmente.

Para estimar o número de caminhos possíveis, 
da raiz até uma folha\footnote{Fixada a raiz de uma árvore com arestas direcionais,
uma folha é um nó terminal, ou seja, um nó de que não sai nenhum arco.}
da árvore de busca, que o algoritmo pode explorar, Guo et al.
supõem que as primeiras posições a serem acrescentadas, a menos a posição 1, 
são da forma $1 + s$ para algum $s$ no espectro. Isso não vale em geral, já que posições
maiores do que $\lfloor r/2 \rfloor$ não estão no espectro. Mas com alta probabilidade isso
vale para um pequeno número de posições. Nesse caso, o número de nós no nível $\ell$ da
árvore é próximo de $r/2 \alpha^{\ell + 1}$. Chame de $\phi$ o menor valor de $\ell$ 
tal que $(r/2) \alpha^{\ell + 2} < 1$, isto é, o nível $\phi + 1$ é o primeiro nível 
a ter número esperado de nós menor do que 1. Então o número $\Gamma$
de caminhos diferentes que devem podem ser explorados é em torno de
\begin{align}
  \Gamma \approx \prod_{l = 1}^\phi |\sigma (\hz)| \alpha^l =
  \lfloor r/2 \rfloor ^\phi \alpha^{\phi(\phi + 3)/2}.
  \label{eq:gamma}
\end{align}
O valor de $\phi$, quando o espectro é totalmente conhecido,
tipicamente é baixo, por exemplo $\phi = 6$ para o nível de segurança de 80 bits,
de forma que é razoável esperar, como Guo et al. supõem, que as $2 + \phi$ primeiras entradas 
estejam nas primeiras $\lfloor r/2 \rfloor$ entradas do vetor. Uma vez conhecidas estas
$2 + \phi$ posições de entradas não nulas, a posição das entradas não nulas restantes fica
totalmente determinada com alta probabilidade. A Figura~\ref{fig:tamanho_z0} ajuda a ilustrar,
para o nível de segurança de 80 bits, como o fato de conhecer $\phi + 2 = 8$
posições de entradas não nulas
determina totalmente o restante das entradas não nulas, quando $\sigma(\hz)$ é
totalmente conhecido pelo atacante.
Para gerar esta figura, foram
consideradas as médias, entre 1000 vetores $\hz$ testados, do número de posições nulas 
que não podem ser determinadas quando se conhecem as posições de 
$i$ entradas não nulas, para $i = 1, 2, \ldots 45$. Note que, quando todas as entradas não 
nulas são determinadas, o que é representado pela ordenada 0 no gráfico,
a posição de todas as entradas não nulas é automaticamente fixada, pois cada entrada
é ou nula, ou não nula.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_guo/tamanho_z0.pdf}
  \caption{Média do número de posições de entradas nulas desconhecidas em função
   do número de entradas não nulas conhecidas, tomando a média de 1000 vetores
   $\vec{h}_0$ gerados aleatoriamente com parâmetros para segurança de 80 bits}
  \label{fig:tamanho_z0}
\end{figure}

Para comparar o desempenho do algoritmo original de reconstrução
com os algoritmos de reconstrução propostos neste trabalho, é útil considerar
uma cota inferior para $\Gamma$. Para isso, considere a seguinte manipulação da 
Equação~\ref{eq:gamma}
\[
\Gamma = \lfloor r/2 \rfloor ^\phi \alpha^{\phi^2/2} \alpha^{3\phi/2} 
       = \left( \lfloor r/2 \rfloor \alpha^{\phi + 1} \right)^{\phi/2}  
          \left( \lfloor r/2 \rfloor \alpha^2 \right)^{\phi/2}.
\]
Pela definição de $\phi$, vale que $\lfloor r/2 \rfloor \alpha^{\phi + 1} \geq 1$. Então
\[
\Gamma \geq \left( \lfloor r/2 \rfloor \alpha^2 \right)^{\phi/2}.
\]

Pode-se obter uma cota superior para $\Gamma$ de maneira similar, considerando-se que
\[
\Gamma = \left( \lfloor r/2 \rfloor \alpha^{\phi + 2} \right)^{\phi/2}  
          \left( \lfloor r/2 \rfloor \alpha \right)^{\phi/2}.
\]
Mas agora lembre-se que, para $\phi + 2$, vale a inequação
$\lfloor r/2 \rfloor \alpha^{\phi + 2} < 1$. Então
\[
  \Gamma < \left( \lfloor r/2 \rfloor \alpha \right)^{\phi/2}.
\]

Guo et al. não apresentaram uma análise detalhada do desempenho de seu algoritmo, dizendo
apenas que sua implementação encontra a chave em alguns minutos. Entretanto,
em sua apresentação na Asiacrypt~\cite{Guo2016Youtube},
Guo mostra que, uma vez recuperado totalmente o espectro, sua implementação do algoritmo 
de reconstrução demora em média 144 segundos para encontrar a chave, terminando em 49 minutos no pior caso, 
para o nível de segurança de 80 bits.

Para estimar a performance do algoritmo de Guo et al. para níveis de segurança mais altos,
consideramos uma extrapolação do tempo de execução de sua implementação da seguinte forma.
Seja $\Gamma_\lambda$ o número de caminhos possíveis que o algoritmo pode testar quando 
é recuperado o espectro completo de \hz de um código QC-MDPC que suporta a segurança de
$\lambda$ bits. Supomos que o número médio de caminhos que se deve testar até encontrar a chave é 
$\Gamma_\lambda/2$. Supomos também que o número médio de operações necessárias para testar
cada caminho não depende do nível de segurança. Seja $T_\lambda$ a quantidade média de trabalho,
em alguma medida razoável, para se recuperar a chave através do algoritmo de Guo et al..
Podemos então escrever
\[
  T_\lambda = T_{80} \frac{\Gamma_\lambda}{\Gamma_{80}}.
\].

A Tabela~\ref{tab:guo_time} mostra os resultados da extrapolação supondo que $T_{80} = 144$ segundos,
que é o tempo médio obtido por Guo et al.. Pode-se ver que o desempenho do algoritmo não escala
bem para níveis de segurança mais altos que 80. Os parâmetros $\alpha$ foram obtidos 
através de simulações.
Pode-se ver que o número esperado de caminhos que o algoritmo original de
reconstrução de chave deve visitar até encontrar a chave cresce rapidamente em função 
do nível de segurança.

O tempo esperado para se encontrar a chave pode ser diminuído
através da paralelização da busca. Porém há limites para a paralelização 
da busca em profundidade~\cite{reif1985depth,greenlaw1995limits},
e não é claro quais estratégias de balanceamento de carga entre os \emph{threads}
oferecem melhores \emph{speedups}~\cite{rao1987parallel,reinefeld1994work}.
Além disso, os expoentes crescentes dos valores de
$\Gamma$ para níveis de segurança mais altos fazem com que, mesmo com 
\emph{speedups} lineares, a busca tome muito tempo.

\begin{table}[ht]
\centering
\caption{Desempenho estimado do algoritmo de reconstrução de chave}
\label{tab:guo_time}
\begin{tabular}{@{}ccccc@{}}
\toprule
\begin{tabular}[c]{@{}c@{}}Nível de segurança \\ $\lambda$\end{tabular} & $\alpha$ & $\phi$ & $\Gamma$  & \begin{tabular}[c]{@{}c@{}}Extrapolação\\ para o tempo\\ médio de execução\end{tabular} \\ \midrule
80                                                                  & 0.3409   & 6      & $2^{25.45}$                                                                 & 144s~\cite{Guo2016Youtube}                                                                             \\
128                                                                 & 0.3985   & 8      & $2^{39.72}$                                                                 & $\sim$ 32 dias                                                                   \\
256                                                                 & 0.4351   & 10     & $2^{61.95}$                                                                 & $\sim$ 422930 anos                                                              \\ \bottomrule
\end{tabular}
\end{table}


Um outro problema do algoritmo,
talvez tão crítico quanto o crescimento rápido de $\Gamma$ em função de $\lambda$, é
a impraticabilidade de seu uso quando o espectro não é totalmente conhecido.
Quando o espectro é totalmente conhecido, os valores de $\alpha$ e $\phi$ são dados na
Tabela~\ref{tab:guo_time}.
Quando há distâncias dentro do espectro incorretamente classificadas como fora do espectro,
a linha~\ref{line:shady} do Algoritmo~\ref{alg:rec_h0} faz com que o 
algoritmo seja incapaz de encontrar $\vec{h}_0$. Mas, se algumas distâncias fora do espectro
forem classificadas como dentro do espectro, o algoritmo ainda é capaz de encontrar 
$\vec{h}_0$, embora seu desempenho seja significativamente afetado. 
Um número maior de distâncias classificadas como dentro do espectro implica num maior valor
de $\alpha$. A Figura~\ref{fig:alfa_gamma} mostra como o aumento no valor de $\alpha$ afeta a 
o número esperado de caminhos que o algoritmo deve explorar até que encontre $\vec{h}_0$.

Nas próximas seções, são mostrados algoritmos alternativos para
a reconstrução de chave que, além de mais eficientes do que o original, conseguem trabalhar
eficientemente com maiores valores de $\alpha$.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_guo/alfa_gamma.pdf}
  \caption{Número esperado de caminhos até que se encontre a chave privada em relação 
  ao número de distâncias consideradas como dentro do espectro para os níveis
  de segurança 80, 128, e 256}
  \label{fig:alfa_gamma}
\end{figure}
