%!TEX root = diss.tex

\chapter{Variante probabilística do algoritmo de reconstrução}
\label{cap-variante_probab}

O algoritmo de reconstrução de chave apresentado por Guo et al.~\cite{guo2016key} a partir do espectro pode ser muito ineficiente
para níveis de segurança mais altos que 80. Isso ocorre pois o número de estados
possíveis é bem maior, podendo o algoritmo ficar preso por muito tempo num ramo próximo à raiz
que não é parte da chave. A proposta apresentada neste capítulo é uma variante do
algoritmo de Guo et al. de reconstrução em que, para cada nível da árvore de busca, um nó filho
é escolhido aleatoriamente. Usando o fato de que bastam poucos níveis da árvore de busca
corretamente percorridos para que a chave seja determinada, é possível mostrar que o número esperado
de operações usando este algoritmo probabilístico é significativamente menor do que usando o de Guo et al..
Como exemplo, para os parâmetros de segurança de 80 bits, e considerando que o algoritmo tem o espectro completo
de $\hz$, o algoritmo termina em média após apenas 100 caminhos testados. Nos testes
usando um chip Intel i7 870, usando apenas 1 \emph{thread}, a chave é tipicamente
encontrada em menos de 1 segundo, em contraste com a média de 144 segundos do trabalho de
Guo et al.. Para níveis de segurança mais altos, as diferenças entre os tempos são ainda maiores.
Além disso, é trivialmente paralelizável, e é capaz de encontrar eficientemente a chave com uma
$d$-exclusão para $\vec{p}_0$ menor do que o algoritmo de Guo et al..


\section{Descrição do algoritmo}

O algoritmo é uma extensão probabilística muito simples do algoritmo de reconstrução de Guo
et al.~\cite{guo2016key}. Ao invés de escolher deterministicamente o passo seguinte numa
busca em largura, a proposta é percorrer a árvore de busca escolhendo aleatoriamente
o próximo nó filho a ser percorrido. A descrição formal é dada no
Algoritmo~\ref{alg:recuperacao_probab}. Note que a descrição é dada em função de $\hz$
por simplicidade, mas ele pode ser usado diretamente usando os parâmetros
correspondentes para $\ho$, isto é, $s_1$ e $D_1$.


\SetKwRepeat{Do}{faça}{enquanto}

\begin{algorithm}[!h]
  \Entrada{$n, r, w, t$ parâmetros do código QC-MDPC a ser atacado\\
    \myinput{$\hat{w}$ o peso do vetor \hz}\\
    \myinput{$s_0$ uma distância pertencente a $\sigma(\hz)$}\\
    \myinput{$D_0$ um conjunto de distâncias que não pertencem a $\sigma(\hz)$}\\
  }
  \Saida{$V$ o suporte de uma rotação do vetor $\hz$}
  \Inicio{
    \Do{$V$ não for o suporte de uma rotação de $\hz$}{
        $V \gets \{1, 1 + s_0\}$ \\
        $F_2 \gets \left\{ i \in [\lfloor r/2 \rfloor] - V : \dist_r(i, v) \notin D_0
                \, \forall v \in V \right\}$ \\
        $l \gets 2$ \\
        \Enqto{$|V| < \hat{w}$ e $|F_l| > 0$}{
            $p \gets $ uma entrada escolhida aleatoriamente de $F_l$ \\
            $V \gets V \cup \{ p \}$ \\
            $F_l \gets F_l - \{p\}$ \\
            $F_{l + 1} \gets \left\{ i \in F_l : \dist_r(i, v) \notin D_0
                \, \forall v \in V \right\}$ \\
            $l \gets l + 1$ \\
        }

    }
    \Retorna{$V$}
  }
  \caption{\textsc{ReconstruçãoProbabilística} : variante probabilística do algoritmo de reconstrução de chave}
  \label{alg:recuperacao_probab}
\end{algorithm}

A seguir é dada uma breve descrição do algoritmo.
Os parâmetros $s_0$, que é uma distância dentro do espectro,
e $D_0$, que é um conjunto de distâncias fora do espectro,
são calculados como descrito na Seção~\ref{sec:d0_d1_s0_s1}. 
A cada iteração, o algoritmo começa com o
conjunto $V = \{ 1, s_0 + 1\}$ e tenta completá-lo com mais
$\hat{w} - 2$ posições, sem que ocorra nenhuma distância fora do espectro, isto é, distâncias
em $D_0$ são proibidas. 
Para completar o vetor $V$, o algoritmo escolhe aleatoriamente 
uma distância do conjunto 
auxiliar $F_l$, que contém, para cada nível $l$,
as posições possíveis para completar suporte. Ou seja,
$F_l$ contém os elementos de $[r]$ que não pertencem a $V$,
e cuja distância até qualquer posição em $V$ não está em $D_0$.

Nas próximas seções, é explicado por que essa variante probabilística tem
um desempenho melhor do que a busca em profundidade sugerida por Guo et al..
Para isso é feita uma análise probabilística do algoritmo, e depois é mostrado
o seu desempenho na prática.

\section{Análise probabilística}
\label{cap-variante_probab_analise}

Em cada iteração, o algoritmo
percorre a árvore de busca, da raiz até alguma de suas folhas,
escolhendo aleatoriamente por qual filho irá seguir no próximo nível.
Então a probabilidade de o algoritmo de construção encontrar \hz é exatamente
a probabilidade de que cada filho escolhido seja um elemento do suporte de \hz.

Seja $s_0$ uma distância pertencente ao espectro de \hz.
Suponha que estamos no nível $l$ da árvore de busca, tendo até agora seguido o caminho
$V=~\{ v_1 = 1, v_2 = 1 + s_0, \ldots v_l \}$, formado apenas por elementos do suporte de uma mesma rotação
de \hz. Seja $F_l$ o conjunto dos filhos válidos no nível $l$, então
\[
    F_l =  \{ p \in [r] - V: \dist_r(p, v) \notin D_0 \text{ para todo } v \in V \}.
\]
Como o peso de \hz é $\hat{w}$, temos ao menos $\hat{w} - |V|$ escolhas de interesse para
o próximo filho.
Assim, a probabilidade de escolher um filho $v_{l+1}$ dentro do suporte de $\hz$ quando estamos no
nível $l$, dado que todos os elementos que percorremos pertencem ao suporte de $\hz$, é
\[
    \Pr \left( v_{l+1} \in \supp(\hz) \mid V \subset \supp(\hz) \right)
        = \frac{\hat{w} - |V|}{|F_l|}
        = \frac{\hat{w} - l}{|F_l|}.
\]
Podemos então escrever a probabilidade de o algoritmo ter sucesso como
\begin{align*}
    \Pr (V = \supp(\hz))
        &= \Pr( v_{\hat{w}} \in \supp(\hz) \mid V - \{v_{\hat{w}}\} \subset \supp(\hz)) \\
        &= \prod_{i = 2}^{\hat{w} - 1} \frac{\hat{w} - l}{|F_l|}.
\end{align*}
Lembre que o limite inferior do produto é $i = 2$ pois, como o valor inicial de $V$
é $\{1, 1 + s_0\}$, a busca começa no segundo nível da árvore. O limite superior
do produto é $\hat{w} - 1$ pois é neste nível em que ocorre a última decisão de por
qual filho seguir.
Podemos simplificar um pouco mais esse produto, considerando $\tau + 1$ como o primeiro valor de $l$ para que
$|F_l| = \hat{w} - l$. A partir deste nível $\tau + 1$, os elementos em $F_\tau$ são justamente os
elementos que faltam para se chegar ao suporte de $\hz$. Com isso obtemos
\begin{align*}
    \Pr (V = \supp(\hz))
        = \prod_{i = 2}^{\tau} \frac{\hat{w} - l}{|F_l|}.
\end{align*}


A distribuição da variável aleatória $|F_l|$ não é fácil de ser computada pois as distâncias em $D_0$
são dependentes dos elementos em $V$.
Mas podemos aproximar o valor de sua esperança com um argumento similar ao
usado por Guo et al..  Seja $\alpha$ a probabilidade de que uma distância não
seja uma distância em $D_0$\footnote{A razão $\alpha$ nesta seção é exatamente a mesma
da Seção~\ref{sec:reconst_guo}, com a diferença de que agora é definida a partir da $d$-exclusão.}, então $\alpha =  1 - |D_0|/ \lfloor r/2 \rfloor $.
Suponha novamente que $V$ só contenha elementos do suporte de \hz.
No nível $l$, há $\hat{w} - l$ filhos que são
posições que pertencem ao suporte de $\hz$, que são justamente as posições que
faltam para completar $V$. Para as $(r - \hat{w})$ posições
que não pertencem ao suporte, esperamos que $\alpha^l$ delas tenham sobrevivido
aos crivos das posições possíveis feitos em cada nível. Assim, temos
\[
    \EE |F_l| \approx (r - \hat{w}) \alpha^l + \hat{w} - l.
\]
Com isso, podemos aproximar a probabilidade
de uma certa iteração do algoritmo encontrar a chave como
\[
    \Pr (V = \supp(\hz))
        \approx
        \prod_{l = 2}^{\hat{w} - 1}
        \frac{\hat{w} - l}
        { (r - \hat{w}) \alpha^l + \hat{w} - l
          }.
\]
Seja $W$ a variável aleatória que conta o número de caminhos tetados até que a chave
seja encontrada. Então a esperança de $W$ é
\begin{align}
    \EE(W) = \frac{1}{\Pr (V = \supp(\hz))} =
    \prod_{l = 2}^{\hat{w} - 1}
    \frac
      { (r - \hat{w}) \alpha^l + \hat{w} - l }
      {\hat{w} - l}
    =
    \prod_{l = 2}^{\hat{w} - 1}
    \left(
    \frac
      { (r - \hat{w}) \alpha^l}
      {\hat{w} - l} + 1
    \right).
    \label{eq:ev_w}
\end{align}


Não é fácil limitar superiormente $\EE(W)$ em função de
de $\alpha$, $r$, e $\hat{w}$. O problema parece similar 
ao de encontrar uma cota superior para um símbolo $q$ de
Pochammer, para o qual não parece haver resultado que podemos usar~\cite{weisstein2008q}.
Para limitar $W$ por meio de uma expressão ligeiramente mais simples, considere
$\tau$ como sendo o menor inteiro maior que 1 tal que
\[
    \prod_{l = \tau}^{\hat{w} - 1}
    \left(
    \frac
      { (r - \hat{w}) \alpha^l}
      {\hat{w} - l} + 1
    \right) < r.
\]
Então podemos escrever
\[
  \EE(W) < 
    r \prod_{l = 2}^{\tau - 1}
    \left(
    \frac
      { (r - \hat{w}) \alpha^l}
      {\hat{w} - l} + 1
    \right) < 
    r \prod_{l = 2}^{\tau - 1}
    \left(
    \frac
      { (r - \hat{w}) \alpha^l}
      {\hat{w} - \tau} + 1
    \right).
\]
Mas, como $0 \leq \alpha \leq 1$, note que
\[
    \frac{ (r - \hat{w}) \alpha^l}
       {\hat{w} - \tau} + 1 = 
    \frac{ (r - \hat{w}) \alpha^l + \hat{w} - \tau}
      {\hat{w} - \tau} < 
      \frac{ r - \hat{w} + \hat{w} - \tau}
      {\hat{w} - \tau} = 
      \frac{ r - \tau}
      {\hat{w} - \tau} < \frac{r}{\hat{w} - \tau}.
\]
Portanto o valor esperado de $W$ pode ser limitado superiormente por
\[
  \EE(W) < 
    r \prod_{l = 2}^{\tau - 1}
        \frac
          { r}
          {\hat{w} - \tau}  = 
    r \left( \frac{ r}{\hat{w} - \tau} \right)^{\tau - 2} <
    \hat{w} \left( \frac{ r}{\hat{w} - \tau} \right)^{\tau - 1} 
    .
\]
Compare este valor com o valor esperado de caminhos que o algoritmo 
de reconstrução de Guo et al.~\cite{guo2016key} faz até recuperar a chave, denotado
por $W_\textsc{g}$. Da Seção~\ref{sec:reconst_guo}, vale que
\[
  W_\textsc{g} = \Gamma/2 \geq \frac{1}{2}\left( \lfloor r/2 \rfloor \alpha^2 \right)^{\phi/2},
\]
onde $\phi$ é o menor inteiro positivo tal que $(r/2) \alpha^{\phi + 2} < 1$. Pode-se 
perceber que os expoentes $\tau - 1$ e  $\phi/2$ são os parâmetros mais críticos para se 
determinar $\EE(W)$ e $\EE(W_\textsc{g})$, mas infelizmente não é óbvia a relação entre $\phi$ e $\tau$. 

Para comparar os expoentes $\tau - 1$ e  $\phi/2$, foram considerados os seus valores para
os níveis de segurança 80, 128, e 256, e diferentes valores válidos de $\alpha$. Os
resultados podem ser vistos na Figura~\ref{fig:taus_vs_alphas}. Note que, para valores
de $\alpha$ não muito altos, $\tau - 1 < \phi/2$, o que sugere que o algoritmo 
probabilístico tem melhor desempenho do que o algoritmo original.
Na seção seguinte, o desempenho real do algoritmo probabilístico é avaliado, e comparado com
o desempenho previsto pela Equação~\ref{eq:ev_w}.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_prob/taus_vs_alphas.pdf}
  \caption{Comparação entre os valores de $\tau - 1$ e $\phi/2$ para os níveis de segurança
  80, 128, e 256, e valores válidos de $\alpha$}
  \label{fig:taus_vs_alphas}
\end{figure}



\section{Resultados experimentais}

Para testar a eficiência do algoritmo probabilístico, 
o algoritmo foi implementado em C, e
seu desempenho foi avaliado para níveis de segurança $80$, $128$, e $256$.
A Figura~\ref{fig:niters} mostra os resultados dos números de caminhos testados
até a chave ser encontrada e também as estimativas para estes números segundo a
Equação~\ref{eq:ev_w}.
Foram considerados diferentes valores de $|D_0|$, isto é, do número de distâncias
$d$-excluídas.
Para poder comparar as curvas, foi considerada a $d$-exclusão normalizada, isto é,
o tamanho de $|D_0|$ dividido pelo número médio de distâncias fora do espectro.
O eixo das ordenadas está em escala logarítmica, o que evidencia o crescimento
superexponencial do número de caminhos explorados em relação a menores $d$-exclusões.
Conforme o nível de segurança aumenta,
a eficiência do algoritmo é significativamente reduzida para $d$-exclusões menores.
Parece que as estimativas para $\EE(W)$ se adequam bem aos valores observados. 

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_prob/niters_ataque_probab.pdf}
  \caption{Número de caminhos até encontrar a chave em função da proporção das entradas fora do
  espectro que são conhecidas}
  \label{fig:niters}
\end{figure}

Para dar um exemplo concreto do tempo de execução, o algoritmo foi executado
numa máquina com um processador Intel Xeon E7-2870 a uma frequência de 2.40GHz,
usando os seus 16 processadores.
Para cada nível de segurança, foram feitos 50 testes para cada valor de $|D_0|$,
que é o conjunto das distâncias $d$-excluídas.
Para cada teste, as distâncias $d$-excluídas foram escolhidas aleatoriamente.
A Figura~\ref{fig:comp_prob} mostra a mediana do tempo de execução do algoritmo.
Note que o algoritmo termina muito rapidamente quando há informação completa sobre o
espectro\footnote{Nesse caso o \emph{speedup} usando 16 processadores é bem ruim, 
deixando o algoritmo mais lento do que se fosse executado sem paralelização.}.
Para o nível de segurança de 80 bits, pode-se ver que o algoritmo é eficiente mesmo 
quando apenas $63\%$ das distâncias fora do espectro são conhecidas. 

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_prob/tempo_prob.pdf}
  \caption{Mediana do tempo de execução do algoritmo probabilístico}
  \label{fig:comp_prob}
\end{figure}



Para comparar os desempenhos do algoritmo probabilístico
com o do algoritmo original de Guo et al., 
considere as curvas de $W_\textsc{prob}$
e $W_\textsc{g}$, que representam os números esperados 
de caminhos que o algoritmo probabilístico e o algoritmo de Guo et al., respectivamente,
devem testar até encontrar a chave.
Os resultados são mostrados na Figura~\ref{fig:comp_prob}, e
sugerem  que o algoritmo probabilístico é significativamente melhor
do que o algoritmo original para as $d$-exclusões consideradas.
Não só o algoritmo probabilístico é mais eficiente do que o original quando são dadas as 
mesmas entradas, como o algoritmo probabilístico recuperando uma chave no nível de segurança de
256 bits parece ser mais eficiente do que o original recuperando uma chave do nível de 80 bits.
É importante notar que, para $d$-exclusões muito baixas, o algoritmo original 
passa a ser mais eficiente do que o probabilístico, porém no ponto em que isso ocorre,
o número esperado de caminhos até a chave ser encontrada já é grande o suficiente
para ser impraticável o uso de qualquer um dos dois algoritmos.


\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_prob/comp_prob_com_guo.pdf}
  \caption{Comparação entre os números esperados de caminhos percorridos até encontrar a chave para
  o algoritmo probabilístico ($W_\textsc{prob}$) e para o algoritmo original de Guo et al. ($W_\textsc{g}$). Para
  cada curva, o valor entre parênteses é o nível de segurança correspondente}
  \label{fig:comp_prob}
\end{figure}

Seja\footnote{Este parágrafo e o próximo supõem que o leitor está familiarizado 
com as construções dos conjuntos $D_0$ e $D_1$ como descrito na Seção~\ref{sec:d0_d1_s0_s1}.} $q$ uma $d$-exclusão suficiente para que o algoritmo probabilístico termine rapidamente, onde
rapidamente deve ser definido pelo atacante de maneira que leve em conta seu
poder computacional. Por exemplo, para o nível de
segurança de 80 bits, podemos considerar que o algoritmo trata eficientemente
de uma $d$-exclusão de 1000 entradas, que normalizada equivale a aproximadamente 63\%
das distâncias fora do espectro. 
O algoritmo probabilístico, como o algoritmo de Guo et al.,
pode ser executado usando tanto $D_0$ como $D_1$, que são os
conjuntos estimados das distâncias fora dos
espectros correspondentes de \hz e $\ho$. Então, para
que o algoritmo possa encontrar a chave, basta que ao menos um dos conjuntos $D_0$
ou $D_1$ consista de $q$ entradas fora de seu espectro correspondente.
Em outras palavras, sejam $d_0$ e $d_1$ as $d$-exclusões obtidas para as saídas do
algoritmo de estimação dos espectros, então, para o algoritmo recuperar a chave, 
é suficiente que
\[
  |D_0| = |D_1| = q \geq \max(d_0, d_1).
\]

A Figura~\ref{fig:d_exc_probab} mostra, para o nível de segurança de 80 bits,
a relação entre $\max(d_0, d_1)$ e o número de decodificações. Os dados usados são
os resultados dos testes de decodificação para os 200 códigos da Seção~\ref{sec:d0_d1_s0_s1}.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_prob/d_exc_probab.pdf}
  \caption{A relação entre o número de testes de decodificação e o valor do máximo das $d$-exclusões obtidas para distâncias em $\hz$ e $\ho$}
  \label{fig:d_exc_probab}
\end{figure}

A Figura~\ref{fig:hist_ataque_probab} mostra, para o nível de segurança de 80 bits, 
o histograma do número de testes de decodificação necessários para que o algoritmo
recupere a chave com $q = 1000$, considerando os testes da Seção~\ref{sec:d0_d1_s0_s1}.
A mediana é 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}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/ataque_prob/hist_ataque_prob.pdf}
  \caption{Histograma do número de testes de decodificação para que o algoritmo encontre a chave}
  \label{fig:hist_ataque_probab}
\end{figure}

Mesmo o algoritmo probabilístico obtendo bons resultados em relação ao algoritmo original,
a $d$-exclusão de que ele consegue tratar eficientemente não é muito boa para níveis de
segurança mais altos. A próxima seção mostra um algoritmo robusto em relação a
esse problema.

