<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%% ------------------------------------------------------------------------- %%
%!TEX root = quali.tex

\chapter{Resultados Preliminares}
\label{cap:resultados}

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 Ã&nbsp;
taxa 0.0006, e outro prÃ³ximo Ã&nbsp; 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{ReconstruÃ§Ã£o da chave a partir do espectro}

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} &amp; Tempo de execuÃ§Ã£o \\ \midrule
0                                                                              &amp; 4s                \\
41                                                                             &amp; 11s               \\
82                                                                             &amp; 22s               \\
123                                                                            &amp; 1m41s             \\
164                                                                            &amp; 4m56s             \\
205                                                                            &amp; 18m24s            \\
246                                                                            &amp; 47m58s            \\
287                                                                            &amp; 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 Ã&nbsp; 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$) &amp; Probabilidade ($\lambda_i$) &amp; Acumulada $\downarrow$ &amp; Acumulada $\uparrow$ \\ \midrule
0              &amp; 0.6589889     &amp; 0.6589889 &amp; 1.0000000 \\
1              &amp; 0.2748075     &amp; 0.9337965 &amp; 0.3410106 \\
2              &amp; 0.0573330     &amp; 0.9911295 &amp; 0.0662031 \\
3              &amp; 0.0079677     &amp; 0.9990972 &amp; 0.0088701 \\
4              &amp; 0.0008287     &amp; 0.9999260 &amp; 0.0009024 \\
5              &amp; 0.0000688     &amp; 0.9999949 &amp; 0.0000737 \\
6              &amp; 0.0000047     &amp; 0.9999997 &amp; 0.0000049 \\
7              &amp; 0.0000002     &amp; 1.0000000 &amp; 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 Ã&nbsp; 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 Ã&nbsp; 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 &lt; d_2 &lt; \ldots &lt; 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 Ã&nbsp; distÃ¢ncia de $B(i)$
Ã&nbsp; origem, dada por $i_1 &lt; i_2 &lt; \ldots &lt; 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 &amp; Tempo de execuÃ§Ã£o (s) \\ \midrule
1                 &amp; 30.14                 \\
2                 &amp; 432.61                \\
3                 &amp; 46.10                 \\
4                 &amp; 114.15                \\
5                 &amp; 176.47                \\
6                 &amp; 313.73                \\
7                 &amp; 3.827                 \\
8                 &amp; 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 Ã&nbsp; metade das tentativas por distÃ¢ncia usadas para gerar estes desafios.
</pre></body></html>