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

\chapter{Heurística de reconstrução para tratar distâncias classificadas incorretamente}
\label{cap:melhora_busca}

A estimação do espectro sugerida pelos autores do ataque usa um grande número
de pedidos de decodificação a um oráculo decriptador para estimar as taxas
de falha de decodificação para cada distância.
Idealmente gostaríamos de poder classificar toda distância como pertencente ou
não ao espectro. Usando o algoritmo de \emph{bit-flipping} de Gallager, os autores do ataque
conseguem fazer isso através de 100000 testes para cada distância. Porém quando é usada a
variante do \emph{bit-flipping} de Misoczki, que tem menor taxa de falha, 100000 testes
não são suficientes para classificar cada distância, como pode ser observado
na Figura~\ref{fig:taxas_falha}. Note como há dois picos, um próximo à
taxa 0.0006, e outro próximo à taxa 0.0009, que devem corresponder aos centros das distribuições
das taxas de falha para distâncias dentro e fora do espectro, respectivamente. Porém não há um ponto
de separação entre distâncias dentro e fora do espectro.

\begin{figure}[h]
    \includegraphics[width=.8\textwidth]{figuras/intro/taxas_falha.pdf}
    \caption{Histograma das taxas de falha de decodificação estimadas com 100000
    testes para cada distância, usando um código QC-MDPC gerado aleatoriamente.}
    \label{fig:taxas_falha}
\end{figure}


Duas opções possíveis para tratar da não separação completa das distâncias dentro
e fora do espectro são:

\begin{itemize}
    \item fazer um número maior de testes para as distâncias em regiões intermediárias até obter separação;
    \item usar um algoritmo de recuperação de chave que lide com os erros na recuperação
        do espectro.
\end{itemize}

A primeira opção é a mais conservadora. Porém, pode-se demorar muito até
a obtenção de uma separação completa. Usando o \emph{bit-flipping} de Misoczki, as simulações dos
100000 testes para cada uma das 2400 distâncias possíveis de \hz de códigos
(9602, 4801, 90)-QC-MDPC demoram cerca de 48 horas num computador com 8 \emph{threads}.
Como o \emph{bit-flipping} de Misoczki falha cerca de 10 vezes menos do que o de Gallager,
esperamos que haja separação com 10 vezes mais testes para cada distância. Isso é um problema
pois faria a simulação demorar em torno de 20 dias para cada código.
Então vamos explorar uma possível modificação do ataque para lidar com
erros no espectro recuperado.


Nossa primeira observação é que o algoritmo de reconstrução da chave a partir do
espectro tem bom desempenho quando há até cerca de 200 entradas erradas no espectro.
Dessa forma não é necessário haver a separação completa entre distâncias dentro e
fora do espectro.

Nossa segunda observação diz respeito a como decidir quais entradas serão consideradas
como pertencentes ao espectro. Para isso, sugerimos usar o modelo de mistura gaussiana
para achar as distribuições Normais que melhor aproximam as taxas de falha observadas
para cada multiplicidade. Uma vez em posse dessas distribuições, podemos calcular parâmetros
que otimizam o desempenho do algoritmo de recuperação da chave a partir do espectro.

Duas das vantagens de usar esse modelo em relação ao ataque original são:
\begin{itemize}
    \item não é necessário conhecer a priori a distribuição das taxas de falha de
          decodificação para cada decodificador;
    \item o tempo de recuperação é significativamente mais rápido, pois são necessários bem menos
          testes de decodificação, que são a fase mais demorada do ataque.
\end{itemize}

Naturalmente, ambas as vantagens são úteis para estender o ataque ao caso do esquema convertido para IND-CCA2.
Com esse modelo, também fomos capazes de atacar o QC-MDPC McEliece usando decodificadores por decisões
suaves, o que foi conjecturado mas não mostrado pelos autores originais do ataque.



\section{Descrição do algoritmo}

Queremos modificar o algoritmo de reconstrução de chave para que consiga reconstruir
a chave mesmo que o espectro esteja parcialmente correto.
Então começamos analisando o desempenho do algoritmo original.

Os autores declararam que a execução do algoritmo demora em média 144 segundos,
mas não dão uma análise sobre o tempo de execução\footnote{Os autores dizem ``alguns minutos'' no artigo. Mas o tempo
médio de 144 segundos pode ser visto no vídeo da apresentação na Asiacrypt em
\url{https://www.youtube.com/watch?v=tKvDdGLJLZc}.}.
Implementamos o algoritmo com algumas pequenas otimizações e fizemos testes de desempenho com 1000
espectros de $\vec{h}_0$ de códigos aleatórios. Destes testes, $75\%$ das chaves foram recuperadas em
menos de $5$ segundos, e $99.7\%$ das entradas foram recuperadas em menos de $90$
segundos. A distribuição de frequências para os tempos de execução dos testes pode ser vista na
Figura~\ref{fig:hist_spec}.

\begin{figure}[H]
    \includegraphics[width=.8\textwidth]{figuras/intro/hist_tempo_execucao.pdf}
    \caption{Histograma do tempo de recuperação pelo espectro de $\vec{h}_0$ para 1000 códigos aleatórios.}
    \label{fig:hist_spec}
\end{figure}

Pela descrição do Algoritmo~\ref{alg:rec_h0}, é fácil ver que o algoritmo não funciona quando
faltam distâncias no espectro. Porém o algoritmo lida bem
quando o espectro passado tem, além de todas as entradas do espectro real, algumas entradas incorretas adicionadas.
A Tabela~\ref{tab:tempo_tamperspec} mostra resultados de uma simulação
simples do algoritmo de reconstrução para um espectro fixo com 821 distâncias corretas, mas certos números
de entradas erradas adicionais. Dessa forma, mesmo tomando um conjunto que contenha o espectro, mas que também
possua entre 164 e 205 entradas fora do espectro, ainda teremos um bom tempo de execução.
Este é o principal fato usado para baixar o número de testes de decodificação para cada distância.

\begin{table}[h]
\centering
\caption{Tempo de execução do algoritmo de reconstrução quando são inseridas distâncias erradas no espectro.}
\label{tab:tempo_tamperspec}
\begin{tabular}{@{}cc@{}}
\toprule
\begin{tabular}[c]{@{}c@{}}Número distâncias \\ erradas inseridas\end{tabular} & Tempo de execução \\ \midrule
0                                                                              & 4s                \\
41                                                                             & 11s               \\
82                                                                             & 22s               \\
123                                                                            & 1m41s             \\
164                                                                            & 4m56s             \\
205                                                                            & 18m24s            \\
246                                                                            & 47m58s            \\
287                                                                            & 5h18m7s           \\ \bottomrule
\end{tabular}
\end{table}


A análise da complexidade da reconstrução dada pelos autores explica por que o algoritmo é capaz de lidar bem com
distâncias erradas inseridas no espectro. O motivo é que, a cada nível descido na árvore de busca como a da
Figura~\ref{fig:}, o número de filhos de cada nó fica exponencialmente menor.
Assim, para o bom funcionamento do algoritmo de recuperação, precisamos minimizar o número de candidatos
a bits da chave.

Nossa proposta é que o algoritmo de recuperação de chave rode em duas fases:
\begin{enumerate}
    \item Reconstrução da chave parcial usando apenas distâncias que pertencem ao espectro com maior probabilidade;
    \item Completação da chave parcial usando também as distâncias que têm menor probabilidade de pertencer ao espectro.
\end{enumerate}

A ideia é que erros no espectro são péssimos para a Fase 1, porém não tão ruins para a Fase 2.
Isso, pois o algoritmo recupera grande parte da chave rapidamente na Fase 1, com poucos erros no espectro.
Depois é esperado que poucas posições sejam válidas, mesmo com um número até que grande de distâncias erradas no
espectro.



\begin{algorithm}[]
  \Entrada{$\vec{h}_0$ índices não nulos da chave parcialmente recuperada a cada chamada recursiva; na primeira chamada é o conjunto vazio.\\
    \myinput{$B_0$ índices não nulos em potencial de $\vec{h}_0$ com maior probabilidade.}
    \myinput{$S_0$ distâncias pertencentes ao espectro com maior probabilidade.}
    \myinput{$B_1$ índices não nulos em potencial de $\vec{h}_0$ com menor probabilidade.}
    \myinput{$S_1$ distâncias pertencentes ao espectro com menor probabilidade.}
    \myinput{$\delta_b$ estimativa conservadora de $|\hz - B_0|$.}
    \myinput{$\delta_s$ estimativa conservadora de $|\sigma(\hz) - S_0|$.}
  }
  \Saida{O vetor recuperado por referência em $\vec{h}_0$, ou $\perp$ se não encontrar o vetor.}
  \Inicio{
    \Para{todo $j \in B_0$ maior que o último índice não nulo de \hz}{
        \Se{as distâncias entre $j$ e cada índice não nulo de \hz estão em $S_0$} {
            Adicione $j$ a $\vec{h}_0$ \\
            \Se{\alg{ChamadaRecursiva}$(\vec{h}_0, l + 1, B_0, S_0, B_1, S_1) = \top$}{
                \Retorna{$\top$}
            }
            Remova $j$ de $\vec{h}_0$ \\
        }
     }

    \Se {$\weight(\hz) \geq w/2 - \delta_b - \delta_s $} {
       \Retorna{\alg{Fase2}$(\vec{h}_0, B_0, S_0, B_1, S_1, \emptyset, \delta_s)$ \\}
    }
    \Retorna{$\perp$}
  }
  \caption{Reconstrução de \hz.}
  \label{alg:rec_h0_tha}
\end{algorithm}


\begin{algorithm}[]
    \Entrada{$\vec{h}_0$ índices não nulos da chave parcialmente recuperada a ser completada.\\
      \myinput{$B_0$ índices não nulos em potencial de $\vec{h}_0$ com maior probabilidade.}
      \myinput{$S_0$ distâncias pertencentes ao espectro com maior probabilidade.}
      \myinput{$B_1$ índices não nulos em potencial de $\vec{h}_0$ com menor probabilidade.}
      \myinput{$S_1$ distâncias pertencentes ao espectro com menor probabilidade.}
      \myinput{$D$ conjunto de distâncias em $S_1$ usadas; inicialmente é $\emptyset$.}
      \myinput{$\delta_s$ estimativa conservadora de $|\sigma(\hz) - S_0|$.}
    }

  \Saida{O vetor recuperado por referência em $\vec{h}_0$, ou $\perp$ se não encontrar o vetor.}
  \Inicio{

    \Se {$\weight(\hz) = w$}{
        \Se{$\vec{h}_0$ for a chave secreta}{
            \Retorna{$\top$}
        }
        \Senao{
            \Retorna{$\perp$}
        }
    }

    \Para{todo bit em potencial $j \in B_0 \cup B_1$}{
        $D_\text{temp} \gets D$ \\
        \Para {cada bit $b$ não nulo de \hz} {
            $d \gets $ distância circular mínima entre $j$ e $b$ \\
            \Se{$d \in S_1$}{
                $D \gets D \cup {d}$
            }
            \SenaoSe{$d \notin S_0$}{
                \Retorna{$\perp$}
            }
        }
        \Se{$|D| \leq \delta_s $}{
            Adicione $j$ a $\vec{h}_0$ \\
            Chamada recursiva a \alg{Fase2}$(\vec{h}_0, B_0, S_0, B_1, S_1, D, \delta_s)$ \\
            Remova $j$ de $\vec{h}_0$ \\
        }
        $D \gets D_\text{temp}$ \\
    }
    \Retorna{$\perp$}
  }
  \caption{Reconstrução de $\vec{h}_0$ - \alg{Fase2}}
  \label{alg:rec_h0_tha}
\end{algorithm}


É fácil ver que a nossa proposta é uma generalização do algoritmo de
recuperação de chave original. Para isso, tome $B_1 = B_0 = S_1 = S_0 = \sigma(\hz)$, o que faz
$\delta_s = \delta_b = 0$. Agora vamos fazer algumas observações sobre os parâmetros.

\begin{enumerate}
    \item Seja $p$ o número de posições não nulas de \hz que devem ser descobertos na Fase 1.
        Considere $I$ o conjunto de índices não nulos do \emph{shift} circular de \hz que maximiza $|I \cap B_0|$.
        Então uma cota inferior para $p$ é
        \begin{align}
            p \geq w/2 - |I - B_0| - |\sigma(\hz) - S_0|. \label{eq:cota_p}
        \end{align}

        Isso pois $|I - B_0|$ é o número de índices que fazem parte de \hz, mas que $j$ não valerá na Fase 1.
        E $|\sigma(\hz) - S_0|$ é uma cota superior para o número de índices $j$ válidos que serão descartados
        incorretamente pelo fato de a distância entre o índice $j$ e algum outro índice de \hz parcial não estar em $S_0$.
        Isso justifica o limite $\weight(\hz) \geq w/2 - \delta_b - \delta_s $ na Fase 1 do algoritmo.

    \item Na Fase 2, o conjunto $D$ consiste de todas as distâncias de $S_1$ usadas no espectro de $\hz$. É permitido
        o uso máximo de $\delta_s$ distâncias em $S_1$, pois esse é o número de entradas no espectro
        que não devem ter sido capturadas por $S_0$.

\end{enumerate}


Nas próximas seções, mostramos nossa proposta para escolher os conjuntos $S_0, S_1, B_0, $ e $B_1$, e como estimar
 os parâmetros $\delta_s$ e $\delta_b$.


\section{Obtenção dos parâmetros para o algoritmo de reconstrução}


Para estimar os parâmetros para o algoritmo de reconstrução de chave, precisamos de um modo de extrair a distribuição
de probabilidade das taxas de falha para distâncias dentro e fora do espectro. Nossa proposta
 é usar o modelo de mistura gaussiana (GMM)-\emph{Gaussian Mixture Model} - que considera que
a distribuição final, como a da Figura~\ref{fig:taxas_falha}, é uma soma distribuições Normais. Cada distribuição
Normal representa uma multiplicidade possível das distâncias no espectro.
Há algoritmos iterativos eficientes, como o de maximização de esperança,
que permitem essa decomposição. Assim, chamando de $\mathcal{D}$ a distribuição
de probabilidade para as taxas de falha dos testes para uma distância válida aleatória,
o modelo por mistura gaussiana descreve $\mathcal{D}$ como
\[
    \mathcal{D} = \sum_{i = 0}^{\max{\mu[d]}} \lambda_i \mathcal{N}_i.
\]

Cada $\mathcal{N}_i$ é uma distribuição Normal associada à multiplicidade $i$, e cada $\lambda_i$ é
um número real no intervalo $[0, 1]$ chamado peso para a distribuição $\mathcal{N}_i$.
Cada $\lambda_i$ representa a probabilidade de uma distância válida escolhida aleatoriamente ter multiplicidade
$i$, então a soma dos $\lambda_i$ é igual a 1. Note que os $\lambda_i$ são independentes do decodificador,
enquanto os parâmetros de cada Normal $\mathcal{N}_i$ são altamente dependentes do decodificador.
Idealmente, as Normais encontradas pelo GMM seriam as normais que melhor ajustam as taxas de falha observadas
para distâncias com cada uma das multiplicidades possíveis, como ilustra a Figura~\ref{fig:ideal_gmm}.

\begin{figure}[H]
    \includegraphics[width=0.8\textwidth]{figuras/intro/ideal_gmm.pdf}
    \caption{Normais que melhor ajustam as taxas de falha observadas para cada multiplicidade.
    Aglomeramos as multiplicidades iguais ou superiores a 2 em apenas uma normal para que
    as figuras coubessem na mesma escala do gráfico.}
    \label{fig:ideal_gmm}
\end{figure}

\begin{table}[h]
\centering
\caption{Probabilidades estimadas de ocorrerem as multiplicidades mais comuns em vetores de tamanho 4801 e
    peso 45, condizentes com \hz de um código que suporta um nível de segurança de 80.}
\label{tab:prob_multiplicidades}
\begin{tabular}{@{}cccc@{}}
\toprule
Multiplicidade ($i$) & Probabilidade ($\lambda_i$) & Acumulada $\downarrow$ & Acumulada $\uparrow$ \\ \midrule
0              & 0.6589889     & 0.6589889 & 1.0000000 \\
1              & 0.2748075     & 0.9337965 & 0.3410106 \\
2              & 0.0573330     & 0.9911295 & 0.0662031 \\
3              & 0.0079677     & 0.9990972 & 0.0088701 \\
4              & 0.0008287     & 0.9999260 & 0.0009024 \\
5              & 0.0000688     & 0.9999949 & 0.0000737 \\
6              & 0.0000047     & 0.9999997 & 0.0000049 \\
7              & 0.0000002     & 1.0000000 & 0.0000002 \\ \bottomrule
\end{tabular}
\end{table}


Porém a qualidade do ajuste de cada $\mathcal{N}_i$ é dependente do número distâncias com multiplicidade $i$. Para as
multiplicidades mais comuns, como 0 e 1, o ajuste tende a funcionar bem. Mas para multiplicidades maiores, que
são mais raras, o ajuste pode não convergir. A Tabela~\ref{tab:prob_multiplicidades} gerada através de
simulações pelos autores do ataque mostra
as probabilidades de cada multiplicidade ocorrer num $\hz$ de um código $9602, 4801, 90$-QC-MDPC.
Note como apenas em torno de 1\% das distâncias têm multiplicidade maior do que 3, o que para um código em que
$\hz$ tem peso\footnote{Se $\vec{h}$ tem peso 90, o peso esperado de \hz é 45.} 45, equivale a pouco menos
de $0.01 \binom{45}{2} \approx 10$ entradas.


Vemos duas alternativas para tratar da não convergência das Normais do GMM quando tentamos ajustar
mais de duas Normais aos nossos dados:
\begin{enumerate}
    \item ajustar todos os dados a apenas duas Normais, uma para distâncias fora do espectro (multiplicidade 0),
        e outra para distâncias dentro do espectro (multiplicidade igual ou superior a 1);
    \item descartar dados de distâncias que provavelmente têm multiplicidade maior do que 1
        para encontrar um bom ajuste para as duas Normais que representam apenas as multiplicidades 0
        e 1.
\end{enumerate}

A primeira alternativa parece razoável, porém tem o problema de sempre superestimar os dados na cauda direita
da Normal das distâncias dentro do espectro. Isso acontece pela alta variância causada pelas baixas taxas de
falha para distâncias de multiplicidades maiores do que 1, o que é ilustrado pela linha pontilhada verde na
Figura~\ref{fig:gmm_aprox}. Isso é um problema sério para consultas sobre a
inversa da densidade acumulada da Normal das distâncias de dentro do espectro. Por exemplo, a taxa de falha
que deixa à esquerda 99.99\% das distâncias dentro do espectro seria superestimado. E assim, o algoritmo de
recuperação a partir do espectro teria que trabalhar com um número significativamente maior de entradas erradas do que
se o ajuste fosse mais fino.

A segunda alternativa levanta a questão natural de como decidir quais dados descartar para obter um bons ajustes
na maior parte dos casos. Note como aproximadamente 6.62\% das distâncias têm multiplicidade
igual ou superior a 2, pela Tabela~\ref{tab:prob_multiplicidades}. Assim, em torno de 3.31\% dos
dados com menores taxas de falha devem corresponder à cauda esquerda da distribuição das taxas de falha
para distâncias de multiplicidade igual ou superior a 2. Nossa sugestão é descartar entre 2\% e 3\% das menores
taxas de falha para fazer o ajuste. A melhor qualidade do ajuste para zonas intermediárias entre distâncias dentro
e fora do espectro é ilustrada pela linha pontilhada azul da Figura~\ref{fig:gmm_aprox}.


Para gerar os ajustes da Figura~\ref{fig:gmm_aprox}, usamos o pacote mixtools~\cite{benaglia2009mixtools} da linguagem R.
E para facilitar a comparação dos ajustes, são mostrados também os histogramas das taxas de falha para os testes com distâncias dentro e fora do espectro.
Lembre que os todos os ajustes em pontilhado são feitos sem acesso ao espectro de distâncias, então são derivados somente
a partir da distribuição em cinza da Figura~\ref{fig:taxas_falha}.

\begin{figure}[th]
    \includegraphics[width=0.8\textwidth]{figuras/intro/gmm_aprox.pdf}
    \caption{Estimativa das distribuições das taxas de falha para distâncias dentro e fora do espectro.}
    \label{fig:gmm_aprox}
\end{figure}


As seções seguintes mostram uma tentativa de formalizar as escolhas dos parâmetros do algoritmo
de reconstrução da chave. A análise formalização será útil para estimar um bom número de testes
para cada distância para que o algoritmo de reconstrução funcione bem. Porém na prática, o algoritmo
mostrou bom desempenho mesmo quando a escolha de parâmetros é feita de forma extremamente conservadora,
com parâmetros fixos para o pior caso esperado, em todos os desafios.

\subsection{Os conjuntos $S_0$ e $S_1$}

Em posse da distribuição $\mathcal{N}_1$, podemos fazer consultas sobre a inversa de sua função de densidade acumulada.
Isso será útil para tomar o conjunto $S_1$ de modo que $S_0 \cup S_1$ contenham $\sigma(\hz)$ com alta probabilidade.
Mas lembre que o conjunto $S_0$ não pode ser muito grande por conta da performance da Fase 1 do algoritmo
de reconstrução de chave.

Então sejam $f$ a função inversa da densidade acumulada de $\mathcal{N}_1$, e
$d_1 < d_2 < \ldots < d_{\lfloor r/2 \rfloor }$ uma ordenação das distâncias em função de suas taxas
de falha $\pi[d]$, os conjuntos $S_0$ e $S_1$ são construídos como descrito a seguir.

\begin{itemize}
    \item $S_0 = \{ d_1, d_2, \ldots, d_{1000} \}.$
    \item $S_1  = \{ d : \pi[d] \leq f(99.999\%) \} - S_0.$
\end{itemize}


A escolha de 1000 entradas para $S_0$ pode parecer artificial, mas note que é um número que tenta fazer com
que a Fase 1 não demore muito.
O índice $i$ pode ser interpretado como o custo de usar uma distância do
conjunto $S_i$ na reconstrução da chave.


Também podemos estimar o número $\delta_s$ de distâncias do espectro $\sigma(\hz)$ que o conjunto
$S_0$ não captura. Essa quantidade será útil para o algoritmo de reconstrução.
 Por definição, temos
\[
    \delta_s = |\sigma(\hz) - S_0| = |\sigma(\hz)| - |\sigma(\hz) \cap S_0|.
\]

Seja $a$ a densidade acumulada de $\mathcal{N}_1$ até o valor de $\pi[d_{1000}]$.
O valor $a$ é uma estimativa por GMM para a proporção de valores do espectro que $B_0$ captura.
Então um estimador para o valor esperado do número esperado $\delta_s$ é

\begin{align}
    \bar{\delta_s} = \EE(| \sigma(\hz) |) (1 - a). \label{eq:est_s}
\end{align}

Note que o valor de $\EE(| \sigma(\hz) |)$ pode ser estimado usando uma tabela como a Tabela~\ref{tab:prob_multiplicidades}.


\subsection{Os conjuntos $B_0$ e $B_1$}

Queremos construir os conjuntos $B_0$ e $B_1$ de candidatos a índices não nulos de \hz. Uma opção
seria construir esses conjuntos nos baseando nos respectivos conjuntos $S_0$ e $S_1$ da seguinte forma.
Considere $d_1$ como a distância que tem menor taxa de falha $\pi[d]$. A probabilidade $d_1$ pertencer
ao espectro é alta, então suponha que $d_1$ pertence ao espectro\footnote{Essa suposição pode parecer forte,
mas nosso ataque costuma rodar rapidamente. Então, se estiver demorando, digamos, mais do que 40 minutos, podemos
recomeçar o ataque tomando o $d_2$ no lugar de $d_1$, e assim por diante.}.

Seja $\dist_c(i, j)$ a distância circular mínima entre os índices $i$ e $j$ do vetor $\hz$, então
construa:
\begin{itemize}
    \item $\bar{B}_0 = \{i = 1, 2, \ldots, r: \{ \dist_c(i, 0), \dist_c(i, d_1) \} \subset S_0 \};$
    \item $\bar{B}_1 = \{i = 1, 2, \ldots, r: \{ \dist_c(i, 0), \dist_c(i, d_1) \} \subset S_1 \}.$
\end{itemize}

O problema desse modo é que não temos controle sobre o tamanho dos conjuntos, já que não temos nem
uma métrica. Em particular,

Uma proposta que funciona melhor na prática é a seguinte. Para cada índice $i$, defina o
par ordenado $B(i) = (\pi[\dist_c(i, 0)], \pi[\dist_c(i, d_1)])$. E considere o conjunto dos pontos
\[
    B = \{ B(i) : i = 1, 2, \ldots, r \}.
\]

Considere uma ordenação dos índices $i$ em relação à distância de $B(i)$
à origem, dada por $i_1 < i_2 < \ldots < i_r$. Note que como $S_0$, o conjunto $B_0$ também não pode
ser muito grande. Então construa os conjuntos

\begin{itemize}
    \item $B_0 = \{ i_1, i_2, \ldots, i_{800} \};$
    \item $B_1 = \{ i : \| B(i) - (0, 0) \| \leq R \},$ onde o raio $R$ é escolhido de forma deixar alta a probabilidade
    de $B_0 \cup B_1$ conter as entradas não nulas de \hz\footnote{Ou de um \emph{shift} de \hz.}.
\end{itemize}

A probabilidade de um índice não nulo de \hz não pertencer a $B_0 \cup B_1$ pode ser estimada por:
\[
    \Pr(i \notin B_0 \cup B_1 | i \in \hz ) = \Pr( \| B(i) - (0, 0) \| \leq R \, | \, \dist_c(i, 0) \text{ e } \dist_c(i, d_1) \text{ seguem } \mathcal{N}_1).
\]

De forma que essa probabilidade pode ser calculada usando algum método simples de Monte Carlo. Como um que gera
pontos $(X, Y)$, tais que $X, Y \sim \mathcal{N}_1$, e calcula a proporção de pontos que cai fora do círculo
de raio R com centro na origem.

Similarmente ao final da seção anterior, podemos estimar o número $\delta_b$ de entradas do conjunto de posições não nulas
de $\hz$ que não devem ser capturadas por $B_0$. Seja $q$ a probabilidade de um índice não nulo de \hz qualquer não
pertencer a $B_0$. Essa probabilidade pode ser caculada por um método de Monte Carlo parecido com o descrito acima,
usando como raio $R$ a distância entre $B(i_{800})$ e a origem. Assim $\delta_b$
segue uma distribuição binomial com parâmetros $q$ e $w/2 = 45$, e um estimador para o valor
esperado de $\delta_b$ é
\begin{align}
    \bar{\delta_b} = q\frac{w}{2}. \label{eq:est_b}
\end{align}


\subsection{Os parâmetros $\bar{\delta_s}$ e $\bar{\delta_b}$}


A quantidade $ w/2 - \bar{\delta_b} - \bar{\delta_s}$ tenta captar o momento em que se deve
ir da Fase 1 para a Fase 2 do algoritmo de reconstrução de chave.
A ideia é que o algoritmo rode a Fase 1 pelo máximo possível de iterações,
e vá para a Fase 2 quando tiver descoberto um número de entradas não nulas de $\hz$ próximo do máximo possível,
dados $B_0$ e $S_0$.

Assim podemos passar para o algoritmo os estimadores $\bar{\delta_b}$ e $\bar{\delta_s}$
como os das Equações~\ref{eq:est_b}~e~\ref{eq:est_s}.
Ou melhor do que isso. Como temos as distribuições de $\delta_b$ e $\delta_s$, podemos usar estimadores mais
conservadores, que superestimam $\delta_b$ e $\delta_s$ com alta probabilidade, para que nossa cota inferior
seja atingida na Fase 1 com alta probabilidade.

\section{Desempenho na prática}


Fizemos testes de execução do algoritmo de reconstrução de chave contra 8
desafios diferentes. Os desafios consistem do resultado de $M = 100000$ testes
de decodificação para cada possível distância de $\hz$ de um código
$(9602, 4801, 90)$-QC-MDPC, que corresponde a um nível de segurança de 80. Todos
os códigos foram gerados aleatoriamente, a menos da restrição de que o peso de $\hz$
foi imposto em 45, como no ataque original.

Mesmo tendo que lidar com erros no espectro, o algoritmo de reconstrução teve desempenho
comparável ao ataque original. O tempo de execução médio foi de 173 segundos, e
a distribuição dos tempos de execução pode ser vista na Tabela~\ref{tab:tempo_athaque}.

\begin{table}[h]
\centering
\caption{Tempo de execução do ataque para alguns desafios.}
\label{tab:tempo_athaque}
\begin{tabular}{@{}cc@{}}
\toprule
Número do desafio & Tempo de execução (s) \\ \midrule
1                 & 30.14                 \\
2                 & 432.61                \\
3                 & 46.10                 \\
4                 & 114.15                \\
5                 & 176.47                \\
6                 & 313.73                \\
7                 & 3.827                 \\
8                 & 264.24                \\ \bottomrule
\end{tabular}
\end{table}


Como a geração de um desafio custa 2 dias, infelizmente até agora só temos 8 desafios.
Porém os resultados são motivadores, e imaginamos que seja possível usar o ataque usando
$M = 50000$, que equivale à metade das tentativas por distância usadas para gerar estes desafios.



\section{Ineficiência do algoritmo para níveis de segurança maiores}

