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

\chapter{Algoritmo iterativo de reconstrução baseado em álgebra linear}
\label{cap:ataque_kernel}

A seção anterior mostra que o simples fato de escolher aleatoriamente qual filho 
seguir na árvore de busca melhora significativamente o desempenho do algoritmo. 
Mesmo assim, a $d$-exclusão com que ele consegue trabalhar eficientemente não é muito baixa.
Além disso, um problema mais crítico é que o desempenho do algoritmo probabilístico
não escala muito bem 
para níveis de segurança mais altos, embora escale melhor do que o algoritmo original.
Nesta seção, é proposto um novo algoritmo para a recuperação de chave que é
totalmente baseado em álgebra linear em $\Fb$. Não sendo uma busca em árvore, o algoritmo
consegue evitar os expoentes crescentes em sua complexidade para cada nível de segurança, presentes 
tanto no algoritmo original quanto no nosso algoritmo probabilístico de busca. Em particular, obedecidas 
certas condições sobre a $d$-exclusão, pode-se mostrar que sua complexidade é $\cO(n^4)$.
O desempenho do algoritmo na prática também é melhor do que os dos outros apresentados,
e ainda tem a vantagem de poder ser paralelizado trivialmente. A $d$-exclusão de que ele precisa 
é significativamente menor do que a do algoritmo probabilístico de busca. Esta proposta
foi submetida à revista \emph{Transactions on Fundamentals of Electronics, 
Communications and Computer Sciences} do IEICE~\cite{paiva2018improving}.


\section{Descrição do algoritmo}\label{sec:idea}

Diferentemente dos outros algoritmos apresentados, este algoritmo usa necessariamente 
informação sobre os espectros de
ambos os blocos da chave \hz e \ho. Além destes dois conjuntos, o algoritmo também
usa $s_0$ e $s_1$, que são, respectivamente, distâncias nos espectros de \hz e de \ho.
Todos esses parâmetros podem ser obtidos usando as descrições da
Seção~\ref{sec:d0_d1_s0_s1}.

Num código $[n, r, w]$-QC-MDPC com dois blocos cíclicos, isto é, $n = 2r$, a matriz
geradora pública é dada por $\mat{G} = \left[ \, \mat{I}  \, | \, \mat{B}^T \, \right]$, onde
$\mat{B} = \mat{H}_1^{-1}\mat{H}_0$. Multiplicando esta equação à esquerda por $\mat{H}_1$,
temos que $\mat{H}_1 \mat{B} = \mat{H}_0$. Desta equação, pode-se obter uma
equação sobre as primeiras linhas das matrizes $\mat{H}_0$ e $\mat{H}_1$, 
dada por $\ho \mat{B} = \hz$.
A ideia do algoritmo é explorar a relação
$\ho \mat{B} = \hz$, onde a matriz $\mat{B}$ é pública, e o espectro parcial de $\ho$
e de $\hz$ pode ser obtido pelo algoritmo de estimação do espectro.
Sejam $Z_0$ e $Z_1$ conjuntos de índices de entradas não nulas de $\hz$ e $\ho$,
respectivamente.
Denote por $\mat{B}^{Z_0}$ a matriz formada pelas colunas de $\mat{B}$ cujos índices
estão em $Z_0$.
Então, por definição
\begin{align*}
    \ho \mat{B}^{Z_0} = \vec{0}.
\end{align*}

As entradas de $\ho$ cujos índices estão em $Z_1$ podem ser descartadas,
se for tomado o devido cuidado de também descartar 
as colunas correspondentes de $\mat{B}^{Z_0}$.
Denote por $Z_1^\comp$ o complemento de $Z_1$ em relação aos possíveis índices das entradas de $\ho$, ou seja $Z_1^\comp = [r] - Z_1$. Então
\begin{align*}
    \ho^{Z_1^\comp} \mat{B}^{Z_0}_{Z_1^\comp} = \vec{0},
\end{align*}
onde $\ho^{Z_1^\comp}$ é o vetor formado pelas colunas de $\ho$ cujos índices estão
em $Z_1^\comp$, e $\mat{B}^{Z_0}_{Z_1^\comp}$ é a matriz formada pelas linhas
de $\mat{B}^{Z_0}$ cujos índices estão em $Z_1^\comp$. Em outras palavras,
$\ho^{Z_1^\comp}$ é um vetor que pertence ao espaço nulo da matriz
$\mat{B}^{Z_0}_{Z_1^\prime}$. Então podemos computar a matriz geradora do espaço nulo
de $\mat{B}^{Z_0}_{Z_1^\prime}$ e, com sorte, $\ho^{Z_1^\comp}$ será uma
de suas colunas. Para transformar essa ideia num algoritmo, é preciso resolver
alguns problemas, que são discutidos a seguir.


O primeiro problema é que encontrar um vetor de baixo peso no
espaço nulo de $\mat{B}^{Z_0}_{Z_1^\prime}$ pode ser impraticável~\cite{stern1988method}.
Uma maneira conservadora de lidar com esse problema é descobrir o quão grandes devem ser
os conjuntos $Z_0$ e $Z_1$ para que o espaço nulo de $\mat{B}^{Z_0}_{Z_1^\prime}$
consista somente no vetor $\ho^{Z_1^\comp}$, a partir do qual é direto obter $\ho$.
A resposta é dada formalmente na Seção~\ref{sec:z0_z1_sizes}, e é que
o espaço nulo é formado apenas pelo vetor $\ho^{Z_1^\comp}$ com probabilidade
aproximada de $1 - 1/2^{|Z_0| + |Z_1| - r}$. Assim, para o ataque ter
boa probabilidade de sucesso, o ideal é que $|Z_0| + |Z_1|$ seja maior do que $r$,
mas não precisa ser necessariamente muito maior, pois a probabilidade aumenta rapidamente em 
relação à soma. Os tamanhos dos conjuntos $Z_0$ e $Z_1$ estão intimamente relacionados às
exclusões obtidas pelo algoritmo de estimação do espectro, o que leva ao próximo problema.

O segundo problema é determinar quanta informação sobre os espectros de $\hz$ e $\ho$
é necessária para que os conjuntos $Z_0$ e $Z_1$ sejam grandes o suficiente.
Este problema está relacionado ao número necessário de decodificações para o ataque ter
sucesso. Seja $\sigma(\hz)$ o espectro $\hz$, suponha que é conhecido que $s_0$ pertence a
$\sigma(\hz)$, e também que é sabido que as distâncias no conjunto
$D_0 = \{ f_1, \ldots, f_l \}$ não
pertencem a
$\sigma(\hz)$. Então, denotando por $*$ entradas desconhecidas, é possível concluir que
existe ao menos uma rotação do vetor $\hz$ com o seguinte formato
\[
  [
    \rlap{$
      \phantom{0  *  \ldots  * }
      \overbrace{
        \phantom{
          1  *  \ldots  *  0  *  \ldots  *
          0  *,  \ldots,  *  1
        }
      }^{s_0}
    $}
    \rlap{$
      \underbrace{\phantom{ 0  *  \ldots  *  1 }}_{f_1}
    $}
     0  *  \ldots  *
    \underbrace{ 1  *  \ldots  *  0 }_{f_1}
    *  \ldots  *
    \rlap{$
      \underbrace{\phantom{ 0  *  \ldots  *  1 }}_{f_1}
    $}
     0  *  \ldots  *
    \underbrace{ 1  *  \ldots  *  0  }_{f_1}
    * \ldots *
  ].
\]
Além disso, se forem considerados todos os outros $f_i$, é possível descobrir as posições de
um grande número de entradas nulas dessa rotação de $\hz$. Justamente estas posições de entradas
nulas formam o conjunto $Z_0$.
Uma construção análoga pode ser feita para o conjunto $Z_1$. Como exemplo, considere
o vetor $\hz = [\,0\,0\,1\,1\,0\,0\,0\,1\,0\,]$, e então $\sigma(\hz) = \{1, 4\}$. Suponha que 
sabemos que a distância $s_0 = 1$ pertence ao espectro $\sigma(\hz)$, e que a
distância no conjunto $D_0 = \{ 3 \}$ não ocorrem em $\hz$.
Então podemos ter certeza de que existe ao menos uma rotação de $\hz$ satisfazendo
o seguinte formato
\[
  [\,1\,1\,*\,0\,0\,*\,0\,0\,*\,],
\]
a partir do qual podemos construir o conjunto $Z_0 = \{ 4, 5, 7, 8 \}$.
Na Seção~\ref{sec:d_exclusion}, é discutida a relação entre o número de distâncias
conhecidas dentro e fora dos espectros $\sigma(\hz)$ e $\sigma(\ho)$, e os
tamanhos dos conjuntos $Z_0$ e $Z_1$, respectivamente.


O terceiro e último problema é que os conjuntos de posições $Z_0$ e $Z_1$
são construídos com base apenas em distâncias circulares. Assim, não há nenhuma garantia de que $Z_0$ e $Z_1$ são posições de entradas nulas em rotações de
$\hz$ e $\ho$ pelo mesmo número de posições.
Em outras palavras, os conjuntos $Z_0$ e $Z_1$ são válidos, com alta probabilidade,
para linhas diferentes de $\mat{H}_0$ e $\mat{H}_1$, respectivamente, e a relação
$\vec{h}_1^\prime \mat{B} = \vec{h}_0^\prime$ vale somente se forem iguais
os índices das linhas de $\mat{H}_0$ e $\mat{H}_1$ em que aparecem
$\vec{h}_0^\prime$ e $\vec{h}_1^\prime$, respectivamente.
Um modo de lidar com isso é fixar um dos conjuntos, a saber $Z_1$, e tentar
iterativamente para cada $p = 0, 1, \ldots, r - 1$
encontrar uma linha de baixo peso na matriz geradora do espaço nulo de
$\mat{B}_{Z_1^\comp}^{Z_0^{(p)}}$,
onde $Z_0^{(p)}$ é o conjunto de posições em $Z_0$ circularmente deslocadas em $p$ posições, ou seja
\[
  Z_0^{(p)} = \{ i + p \mod r : i \in Z_0 \},
\]
onde $0 \mod r$ é identificado com a posição $r$, já que índices de vetores começam em 1.

O valor de $p$ para o qual é possível encontrar a chave é aquele que alinha as
devidas rotações dos vetores $\hz$ e $\ho$ correspondentes a $Z_0$ e $Z_1$.
Na geração de chaves, os vetores $\hz$ e $\ho$ são construídos aleatoriamente, então,
a priori, cada rotação de $\ho$ é equiprovável de estar alinhada com $\hz$.
Isso faz com que a probabilidade de que um deslocamento $p$ alinhe os conjuntos $Z_0$ e $Z_1$
seja $1/r$, ou seja, a distribuição do $p$ é uniforme no conjunto $[r]$. Na prática essa 
probabilidade pode ser ligeiramente mais alta, dependendo das multiplicidades com que
as distâncias $s_0$ e $s_1$ aparecem nos respectivos vetores $\hz$ e $\ho$.

Considere o seguinte exemplo que ilustra o problema das rotações descrito acima.
\[
  \mat{H} = [\mat{H}_0|\mat{H}_1] = 
  \left[
  \begin{array}{cccc|cccc}
  1&0&0&1&1&1&0&1\\
  1&1&0&0&1&1&1&0\\
  0&1&1&0&0&1&1&1\\
  0&0&1&1&1&0&1&1\\
  \end{array}
  \right],
  Z_0 = \{2,3\}, \text{ e } Z_1 = \{1\}.
\]
Pode-se ver que os elementos de $Z_0$ correspondem às posições nulas da primeira linha do
de $\mat{H}_0$. Porém o elemento de $Z_1$ corresponde à terceira
linha de $\mat{H}_1$. Há várias formas de alinhar os dois conjuntos. Uma delas, que 
é a que escolhemos para o algoritmo, é rotacionar o conjunto $Z_0$ em 2 posições, obtendo
o conjunto $Z_0^{(2)} = \{ 4 \mod 4, 5 \mod 4\} = \{ 0, 1 \} = \{ 4, 1 \}$. Note como
$Z_0^{(2)}$ e $Z_1$ são posições de entradas nulas de uma mesma linha de $\mat{H}$, em
relação a $\mat{H}_0$ e $\mat{H_1}$, respectivamente.

Agora é possível dar uma descrição completa do algoritmo, que pode ser vista no 
Algoritmo~\ref{alg:kernel_algo}.
Como o algoritmo não é recursivo e usa apenas operações comuns, não é difícil analisá-lo.
As linhas~\ref{line:z1},~\ref{line:z0bar}, e~\ref{line:z0} são $\cO(r)$.
O custo de construir $\mat{B}_{Z_1^\prime}$ na linha~\ref{line:bz1} é $\cO(r|Z_1^\prime|)$,
e o custo de construir
$\mat{B}_{Z_1^\prime}^{Z_0}$ na linha~\ref{line:bz0z1} é $\cO(|Z_0||Z_1^\prime|)$.
O laço da linha~\ref{line:main_loop} faz $r$ iterações no pior caso. O cálculo da
matriz geradora do espaço nulo na linha~\ref{line:kernel} é a operação mais cara,
custando $|Z_1^\prime|^2 |Z_1^\prime + Z_0|$ operações. O cálculo do peso na linha~\ref{line:weight}
custa $\cO(r)$. Finalmente, o laço da linha~\ref{line:v_loop} itera $|\vec{v}| =
|Z_1^\prime|$ vezes. Isso dá o seguinte lema sobre o desempenho do algoritmo.

\begin{algorithm}[ht]
  \Entrada{ $r, w$ parâmetros do código QC-MDPC\\
  \myinput{   $D_0$ um conjunto de distâncias fora do espectro de $\hz$}
  \myinput{   $D_1$ um conjunto de distâncias fora do espectro de $\ho$ }
  \myinput{   $s_0$ uma distância dentro do espectro de $\hz$ }
  \myinput{   $s_1$ uma distância dentro do espectro de $\ho$ }
  \myinput{   $\mat{B}$ o bloco cíclico à direita da matriz geradora}
  }

  \Saida{$\ho$ ou $\perp$}

  $Z_1^\comp \gets \{ i \in [r]: \dist(1, i) \notin D_1 \text{ e }
    \dist(1 + s_1, i) \notin D_1 \}$ \label{line:z1} \\
  $\mat{B}_{Z_1^\comp} \gets $ linhas de $\mat{B}$ cujos índices estão em $Z_1^\comp$
    \label{line:bz1} \\

  $\bar{Z_0} \gets \{ i \in [r]: \dist(1, i) \in D_0 \text{ ou } \dist(1 + s_0, i) \in D_0 \}$ \label{line:z0bar} \\

  \Para{$p = 0$ to $r - 1$}{ \label{line:main_loop}
    $Z_0 \gets \{ i + p \mod r: i \in \bar{Z_0} \}$ \label{line:z0} \\

    $\mat{B}^{Z_0}_{Z_1^\comp} \gets $ colunas de $\mat{B}^{Z_1^\comp}$ cujos índices
      estão em $Z_0$ \label{line:bz0z1} \\

    $\mat{K} \gets $ matriz geradora do núcleo de $\mat{B}^{Z_0}_{Z_1^\comp}$
      \label{line:kernel} \\
    \Se{$\dim \mat{K} = 1$}{
      $\vec{v} \gets $ única linha de de $\mat{K}$ \\
      \Se{$\weight(\vec{v}) \leq w$}{ \label{line:weight}
        $\ho  \gets \vec{0} \in \Fb^r$ \\
        \Para{cada $i$ = 1 até $|\vec{v}|$}{ \label{line:v_loop}
          $\ho [Z_1[i]] \gets \vec{v}[i]$
        }
        \Retorna{$\ho$}
      }
    }
  }
  \Retorna{$\perp$}
 \caption{Algoritmo de reconstrução de chave baseado em álgebra linear}
  \label{alg:kernel_algo}
\end{algorithm}


\begin{lem}
A complexidade do algoritmo de reconstrução é
  \[
    \mathcal{O} \left( r + r|Z_1^\prime| + r + r \left( r + |Z_0||Z_1^\comp| +
      |Z_1^\comp|^2  |Z_0 + Z_1^\comp| + |Z_1^\comp| \right) \right).
  \]

Como $|Z_0|$ e $|Z_1^\comp|$ são $\mathcal{O}(r)$, a complexidade do 
algoritmo pode ser simplificada para $\mathcal{O}(r^4)$.
\end{lem}


Note que o algoritmo pode não encontrar a chave, e o lema apresentado
não diz nada sobre a probabilidade de encontrá-la. O lema apenas mostra que o algoritmo 
termina em $\cO(r^4)$ passos de qualquer forma, encontrando ou não a chave.
As próximas seções são dedicadas a mostrar que o algoritmo tipicamente encontra a chave, 
desde que a $d$-exclusão obtida pelo algoritmo de estimação do espectro não seja muito baixa.
Em particular, queremos encontrar a relação entre a probabilidade de a reconstrução 
ser bem sucedida e o tamanho da $d$-exclusão obtida.

\section{Análise probabilística}


\paragraph{A probabilidade de o ataque falhar}
\label{sec:z0_z1_sizes}
\mbox{}

Sejam  $Z_0$ e $Z_1$ conjuntos de índices de entradas não nulas de \hz e \ho,
possivelmente rotacionados pelo mesmo número de posições.
Pela construção de $Z_0$ e $Z_1$, a matriz geradora do espaço nulo de 
$\mat{B}^{Z_0}_{Z_1^\comp}$, denotada por $\mat{K}$, tem ao menos uma linha, 
porém em geral a sua dimensão pode ser muito grande.
Para o algoritmo encontrar a chave, a matriz $\mat{K}$ deve ter exatamente uma linha.
Em outras palavras, a equação linear em $\vec{x}$ dada por
$\vec{x} \mat{B}^{Z_0}_{Z_1^\comp} = \vec{0}$ deve ter exatamente uma solução.


O número de soluções para essa equação é exatamente o número de pares de vetores não nulos
$\vec{u}$ e $\vec{v}$ tais que $\vec{u} \mat{B} = \vec{v}$,
sujeitos a $\supp(\vec{u}) \cap  Z_1 = \emptyset$ e $\supp (\vec{v}) \cap Z_0 =
\emptyset $. Multiplicando os dois lados da equação por $\mat{H}_1$ à direita, que é uma matriz não singular, obtemos
\begin{align*}
  \vec{u} \mat{B} = \vec{v} \Leftrightarrow \vec{u} \mat{B} \mat{H}_1 = \vec{v} \mat{H}_1
   \Leftrightarrow  \vec{u} \left( \mat{H}_1^{-1} \mat{H}_0 \right)
     \mat{H}_1 = \vec{v} \mat{H}_1.
\end{align*}
Mas como o produto de matrizes cíclicas é comutativo, então
\begin{align*}
  \vec{u} \mat{H}_0 = \vec{v} \mat{H}_1 &\Leftrightarrow
   \vec{u} \mat{H}_0 + \vec{v} \mat{H}_1 = \vec{0} \\
   &\Leftrightarrow \left[ \vec{u} | \vec{v} \right]
    \left[\begin{array}{c}
      \mat{H}_0 \\
      \hline
      \mat{H}_1 
    \end{array}\right] = \vec{0} \\
   &\Leftrightarrow \left[ \vec{u} | \vec{v} \right] \left[ \mat{H}_0^T | \mat{H}_1^T \right]^T = \vec{0}.
\end{align*}
Ou seja, $\vec{u} \mat{B} = \vec{v}$ se e somente se o vetor
$[\vec{u} | \vec{v}]$ é uma palavra do código  QC-MDPC  com matriz de paridade dada por
$\mat{H}^\prime = \left[ \mat{H}_0^T | \mat{H}_1^T \right]$.


O problema de contar o número de pares desses vetores $\vec{u}$ e $\vec{v}$ está
relacionado à distribuição de pesos num código QC-MDPC, que é um problema 
difícil, e para o qual não parece haver resultados teóricos que podem ser 
usados~\cite{gallager1962low, ryan2009channel}.
Esse problema de contagem fica ainda pior com as restrições sobre os suportes de 
$\vec{u}$ e $\vec{v}$. Para lidar com isso, podemos considerar uma aproximação
comumente usada~\cite{levy1968weight,corr1964statistical}, que considera que a probabilidade 
de o vetor $[ \vec{u} | \vec{v} ]$ estar num código $\mathcal{C}$ é a probabilidade
de que um vetor escolhido aleatória e uniformemente pertença a $\mathcal{C}$, independentemente
das restrições sobre $\vec{u}$ e $\vec{v}$. Então seja $\mathcal{C}$
um código $[n, r, w]$-QC-MDPC, temos a aproximação
\[
  \Pr \left( \, [ \vec{u} | \vec{v} ] \in \mathcal{C} |
    \supp(\vec{u}) \cap  Z_1 = \supp (\vec{v}) \cap Z_0 = \emptyset \right)
    = 2^{-(n - r)}.
\]

Neste trabalho, apenas o caso $n = 2r$ é considerado, então a probabilidade de o 
algoritmo encontrar a chave pode ser aproximada como
\begin{align*}
  \Pr ( \dim \mat{K} > 1 )
  & \approx \sum_{\vec{u} : \supp(\vec{u}) \cap Z_1 = \emptyset} \, \sum_{\vec{v}: \supp(\vec{v}) \cap Z_0 = \emptyset}
    \Pr \left( [\vec{u} | \vec{v}] \in \mathcal{C}
    |
    \supp(\vec{u}) \cap  Z_1 = \supp (\vec{v}) \cap Z_0 = \emptyset \right) \\
  & \approx 2^{r -  |Z_0|} 2^{r - |Z_1|} \frac{1}{2^r}.
\end{align*}

Isso dá o seguinte lema relacionando a probabilidade de o algoritmo encontrar a chave
e os tamanhos dos conjuntos $Z_0$ e $Z_1$.

\begin{lem}
  A probabilidade de o algoritmo encontrar a chave pode ser aproximada por
  \[
    \Pr ( \text{Algoritmo encontrar a chave} ) \approx 1 - 2^{r - |Z_0| - |Z_1|}.
  \]
  \label{lem:prob_low_nul}
\end{lem}

\paragraph{O tamanho da $d$-exclusão para uma alta probabilidade de sucesso}
\label{sec:d_exclusion}
\mbox{}

Sabemos pelo Lema~\ref{lem:prob_low_nul} que o valor de $|Z_0| + |Z_1|$ determina a probabilidade
de o algoritmo encontrar a chave, para um $r$ fixo. Sejam $D_0$ e $D_1$, os conjuntos  das distâncias 
que sabemos estarem fora dos espectros de
\hz e \ho, respectivamente, isto é, são as distâncias $d$-excluídas pelo algoritmo de estimação
dos espectros. O problema tratado nesta seção é o de
determinar como os tamanhos de $D_0$ e $D_1$ afetam
os tamanhos dos conjuntos $Z_0$ e $Z_1$, respectivamente.

Fixe  a probabilidade de o ataque falhar como sendo $1/2^\gamma$, para um certo $\gamma$.
Queremos encontrar o menor inteiro positivo
$d$ tal que, se ambos $|D_0|$ e $|D_1|$ forem maiores ou iguais a $d$, então o algoritmo
encontra a chave com probabilidade maior do que $1 - 1/2^\gamma$, 
para uma grande fração $\alpha$ de todas as chaves secretas possíveis. 
Note que queremos que $\alpha$ e $\gamma$ sejam grandes.

A ideia é fazer uma busca binária pelo menor tal $d$ no conjunto
$[\lfloor r/2 \rfloor] = \{1, \ldots, \lfloor r/2 \rfloor \}$.
O problema é que a interdependência entre as distâncias fora do espectro
torna difícil computar analiticamente a distribuição do conjunto $|Z_0|$
como uma função de $|D_0|$, e similarmente para $|Z_1|$ e $|D_1|$.
Note que, na Seção~\ref{cap-variante_probab_analise}, foi resolvido um problema similar, porém
mais simples pois o interesse era apenas no valor esperado de $|Z_0|$. 
Agora, como a probabilidade de o algoritmo encontrar a chave é exponencial em $|Z_0|$ e
$|Z_1|$, apenas o valor esperado não basta.
Para resolver o problema, foram feitas simulações para estimar, para cada $d$,
a fração $f_d$ das chaves secretas para as quais o algoritmo encontra a chave secreta com probabilidade
maior ou igual a $1 - 1/2^\gamma$ quando $|D_0| = |D_1| = d.$ Para isso, são construídos
$N$ pares válidos $(D_0, Z_0)$ e $(D_1, Z_1)$,
e o estimador para $f_d$ é dado por
\[
  \hat{f}_d = \frac{ \# \{ \text{Pares $Z_0$ e $Z_1$ gerados} : |Z_0| + |Z_1| - r \geq \gamma \} }{N}.
\]
A busca termina com o menor valor de  $d$ para que $\hat{f}_d \geq \alpha$.

A Tabela~\ref{tab:size_d_for_sim} mostra os valores de $d$ obtidos para diferente níveis de segurança
considerando como parâmetros da simulação $N= 5000$, $\alpha = 99\%$, e $\gamma = 20$. 
Para uma comparação entre diferentes níveis de segurança,  também são mostradas as frações
$d/\sigma^\comp$, onde $\sigma^\comp$ é o número médio de distâncias fora do espectro.

\begin{table}[h]
\centering
\caption{Resultados da simulação para os valores de $d$, usando como parâmetros $N = 5000$, $\alpha = 99\%$, e $\gamma = 20$}
\label{tab:size_d_for_sim}
\begin{tabular}{cccc}
\hline
\begin{tabular}[c]{@{}c@{}}Nível de segurança \\ $\lambda$\end{tabular} & \begin{tabular}[c]{@{}c@{}}Tamanho estimado\\ para $D_0$ e $D_1$ \\ pela simulação \\ $d$\end{tabular} & \begin{tabular}[c]{@{}c@{}} Número médio de \\ distâncias fora\\ do espectro\\ $\sigma^\comp$\end{tabular} & 
\begin{tabular}[c]{@{}c@{}} $d$-exclusão normalizada \\ $d/\sigma^\comp$ \end{tabular} \\ \hline
80                                                                  & $d_{80} = 722$                                                                                                      & 1582.12                                                                                                        & $45.63 \%$       \\
128                                                                 & $d_{128} = 1470$                                                                                                     & 2964.72                                                                                                        & $49.58 \%$       \\
256                                                                 & $d_{256} = 4845$                                                                                                     & 9256.64                                                                                                        & $52.34 \%$       \\ \hline
\end{tabular}
\end{table}

 
\section{Resultados experimentais}

A análise do algoritmo apresentada mostra que esse algoritmo tem melhor complexidade
assintótica do que os outros baseados em buscas em árvores. Agora são considerados
os resultados do seu desempenho na prática. O algoritmo foi implementado em
linguagem C, usando a biblioteca M4RI~\cite{M4RI} para o cálculo
da matriz geradora do espaço nulo.

A análise foi feita para os parâmetros que oferecem níveis de segurança 80, 128, e 256 bits
usando $n_0 = 2$ blocos cíclicos. Os testes de desempenho do algoritmo
foram feitos no limite
da $d$-exclusão mínima que o algoritmo precisa para encontrar consistentemente a chave,
ou seja, os valores de $d$ dados pela 
Tabela~\ref{tab:size_d_for_sim} para os tamanhos dos conjuntos $D_0$ e $D_1$.

Note que o tempo total de execução, ou mesmo o número total de ciclos, não é uma métrica
muito informativa para esse algoritmo. Isso pois o número de iterações 
necessário para recuperar a chave segue uma distribuição uniforme sobre o conjunto $[r]$.
Assim, sabendo
o tempo médio de execução para cada iteração, ou o número de ciclos por iteração,
é possível modelar com maior precisão o desempenho do algoritmo.

A Tabela~\ref{tab:attack_performance} mostra o desempenho do algoritmo num computador com 
um processador i7 870 Lynnfield, com frequência de 2.93GHz, e 8GB de RAM.

\begin{table}[h]
\centering
\caption{O desempenho do algoritmo de reconstrução para diferentes níveis de segurança}
\label{tab:attack_performance}
\begin{tabular}{@{}cccc@{}}
\toprule
\begin{tabular}[c]{@{}c@{}}Nível de segurança \\ $\lambda$\end{tabular} & \begin{tabular}[c]{@{}c@{}}Tempo médio\\ por iteração\end{tabular} & \begin{tabular}[c]{@{}c@{}}Número médio \\ de ciclos \\ por iteração\end{tabular} & \begin{tabular}[c]{@{}c@{}}Tempo médio \\ de execução\end{tabular} \\ \midrule
80                                                                  & 0.0169s                                                              & 521048150                                                                           & \textbf{41s}                                                         \\
128                                                                 & 0.1710s                                                              & 4454356686                                                                          & \textbf{14m3s}                                                       \\
256                                                                 & 3.4179s                                                              & 87756949017                                                                         & \textbf{15h33m24s}                                                   \\ \bottomrule
\end{tabular}
\end{table}


% \paragraph{The number of challenges needed for a CCA2 attack}

Como na análise experimental do algoritmo probabilístico, são considerados o
número de testes de decodificação necessários para que 
as $d$-exclusões tanto para $\hz$ quanto $\ho$ sejam suficientes para que o algoritmo
encontre a chave. Chame de $d_0(i)$ e $d_1(i)$ as $d$-exclusões obtidas para $\hz$ e $\ho$, 
respectivamente, com $i$ testes de decodificação. Teoricamente, bastaria tomar o 
primeiro $i$ tal que $d_0(i) + d_1(i) \geq 2 d_\lambda$. 
Mas, como discutido na Seção~\ref{sec:d0_d1_s0_s1}, há o problema
de que, para definir os conjuntos $D_0$ e $D_1$ é necessário saber quais são os valores de 
$d_0(i)$ e $d_1(i)$, o que não se sabe a priori.
Uma ideia conservadora para lidar com isso é sempre construir os conjuntos
$D_0$ e $D_1$ com as $d_\lambda$ distâncias com maior taxa estimada de falha para distâncias
em $\hz$ e em $\ho$, respectivamente. Então o algoritmo pode encontrar a chave após $i$
testes de decodificação se $\min(d_0(i), d_1(i)) \geq d_\lambda$. 

Na prática, porém, executar o algoritmo de construção a cada iteração do algoritmo de estimação
é muito ineficiente. Melhor seria usar uma política como:
faça $M_0 = 10$ milhões de testes de decodificação, e depois, a cada $M_i = 100000$ testes de decodificação, 
execute o algoritmo de reconstrução de chave. Assim a chave é encontrada relativamente cedo, mas sem perder
muito tempo executando o algoritmo de reconstrução sem sucesso.

Para os experimentos, foi considerado apenas o nível de segurança de 80 bits, que é
o mesmo nível de segurança considerado por Guo et al.. Não foram considerados níveis de 
segurança mais altos pois as simulações tomam muito tempo, mas o código-fonte
disponibilizado pode ser usado diretamente para executar simulações para níveis
de segurança mais altos. 
Os dados usados nesta seção são os mesmos resultados de decodificação mostrados
na Seção~\ref{cap:estima_espectro}, isto é, são testes de decodificação para
200 códigos [9602, 4801, 90]-QC-MDPC. 
A Figura~\ref{fig:separation_hist} mostra o histograma das
primeiras iterações $i$ que são um múltiplo de 100000 e em que
$\min (d_0(i), d_1(i)) \geq d_{80} = 722$, considerando os resultados dos 200 códigos.
Similarmente ao algoritmo probabilístico, a mediana do número de testes de decodificação necessários
é em torno de 6 vezes o número médio de testes de decodificação 
necessário pelo algoritmo de Guo et al.~\cite{guo2016key}.

\begin{figure}[!h]
  \centering
  \includegraphics[scale=1]{figuras/expresults/separation_hist.pdf}
  \caption{Histograma do número de testes de decodificação para que o algoritmo encontre a chave}
  \label{fig:separation_hist}
\end{figure}


% \section{Conclusion}

% We propose a new algorithm for key reconstruction that is faster than the
% original one, and uses only 20\% of the information needed by the latter,
% for 80 bits security parameters.
% The algorithm has lower asymptotic complexity, which suggest it scales
% much better for higher security levels. For the security level of 256 bits,
% our rough estimates on the time needed by Guo's et al. algorithm shows
% it would need thousands of years to complete, while ours runs
% in around 16 hours on average, even without parallelization.

% Our algorithm is different in nature
% than the original one: it is based on linear algebra instead of
% a pruned depth-first search in a tree. It also can be straightforwardly
% parallelized, which is not the case for the original one.

% The algorithm is probabilistic, in the sense that it might not work for all codes.
% This could be a weakness, but we show how to select the parameters in
% such a way that the probability of
% failure becomes negligible. The arguments for the probability of success
% are based on a commonly used assumption in coding theory for the distribution
% of low weight codewords. We note that in our 100000 tests for the 80-bit
% security level, the attack has not failed once.

% For future works, it would be interesting to study how the use of other decoding algorithms impacts on the number of decoding trials needed for the attack.
% Another possible research question is to consider variants of the algorithm that
% allows edge cases, where there are less information about both spectrum.
% This is important because it is related to the determination of the lifetime
% of a secret key if one wants to use the QC-MDPC.


% \section{Variantes do algoritmo}

