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

\chapter{Obtendo informação sobre os espectros dos blocos da chave privada}
\label{cap:estima_espectro}

Nesta seção, o algoritmo de estimação do espectro de Guo et al.~\cite{guo2016key}
é analisado mais detalhadamente, e é introduzida uma métrica para a qualidade de sua saída,
chamada $d$-exclusão. A $d$-exclusão representa o número de distâncias que podem consideradas
como fora do espectro, dada a saída do algoritmo de estimação do espectro.
Essa métrica é usada nas próximas seções para medir a eficiência
dos algoritmos de reconstrução de chave. Em particular, queremos algoritmos
que sejam eficientes mesmo com uma baixa $d$-exclusão obtida pelo algoritmo de
estimação do espectro.
Ao final, mostra-se como o número de testes de decodificação afeta a $d$-exclusão
através de simulações.


\section{O algoritmo de recuperação do espectro}

Uma primeira observação é que o algoritmo de recuperação do espectro pode ser adaptado para
que seja extraída mais informação de cada erro de decodificação.
A partir de agora, consideram-se apenas códigos QC-MDPC cuja matriz de paridade esparsa
tem dois blocos cíclicos, isto é, $n_0 = 2$.
O algoritmo apresentado por Guo et al. recupera apenas o
espectro de \hz simplesmente porque seu algoritmo de reconstrução usa informação 
somente sobre \hz. Porém com uma pequena adaptação, o algoritmo é capaz de recuperar
simultaneamente informação sobre \hz e \ho. A descrição do algoritmo com essa adaptação
é dada no Algoritmo~\ref{alg:spec_recovery}. 

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

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

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

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


A Figura~\ref{fig:cca2_exemplo} mostra o resultado do algoritmo contra um código
(9602,4801,90)-QC-MDPC, que eram, até o ataque de reação de Guo et al.~\cite{guo2016key},
parâmetros recomendados para um nível de segurança de 80 bits. Para o gráfico, foram usadas
as taxas de falha para possíveis distâncias em $\hz$, isto é, o vetor
$\vec{p}_0$ devolvido pelo algoritmo de estimação do espectro.
Na figura, fica evidente a forte correlação entre as probabilidades
de falha. Mas, mesmo com $M=100$ milhões de testes de decodificação, não há uma separação completa entre as distâncias dentro e fora do espectro para taxas de falha próximas de 0.00058.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/estima_espectro/estimativa_100M.pdf}
  \caption{Estimativa das probabilidades de falha $\vec{p}_0$, usando $M = 100 $ milhões
  de testes de decodificação, para um código (9602,4801,90)-QC-MDPC gerado aleatoriamente}
  \label{fig:cca2_exemplo}
\end{figure}




\section{Uma métrica para a qualidade da recuperação}

O algoritmo de busca em profundidade para a reconstrução da chave apresentado por
Guo et al. não é capaz de recuperar a chave se uma ou mais distâncias dentro do espectro
forem classificadas incorretamente como fora do espectro. Porém ele consegue lidar com um 
pequeno número de distâncias fora do espectro classificadas como estando dentro do espectro.
Esse fato nos motivou a definir a qualidade de um vetor de probabilidades
recuperado como sendo o número máximo de distâncias cuja taxa de falha é maior do que 
a maior das taxas de falha das distâncias dentro do espectro. Essa métrica 
é chamada de $d$-exclusão, pois ela conta o número máximo de distâncias que podem ser consideradas fora
do espectro ao se considerar apenas um ponto de separação entre distâncias dentro e fora
do espectro.

\begin{definition}
Dizemos que a saída $\vec{p}_i$ do algoritmo de recuperação do espectro obtém uma
$d$-exclusão para  o espectro do bloco $\vec{h}_i$ se existe um número 
$p \in (0, 1)$ tal que
\begin{enumerate}
  \item Se $\vec{p}_i[d] \geq p$ então $d \notin \sigma(\vec{h}_i);$
  \item $\# \{ \vec{p}_i[d] \geq p \} = d.$
\end{enumerate}

Quando $ d = \lfloor r/2 \rfloor - |\sigma(\vec{h}_i)|$, ou seja, $d$ é exatamente o
número de distâncias fora do espectro de $\vec{h}_i$, dizemos que $\vec{p}_i$
obtém $d$-exclusão completa.

\end{definition}

A Figura~\ref{fig:exemplo_d_exclusao} pode ajudar a exemplificar o conceito. 
Aqui foram feitos apenas $M = 30$ milhões de testes de decodificação para um código
(9602,4801,90)-QC-MDPC aleatório e diferente do usado para a Figura~\ref{fig:cca2_exemplo}.
Podemos ver que há uma mistura bem maior entre distâncias dentro e fora do espectro.
A $d$-exclusão obtida é de 983 distâncias, sendo que o total de distâncias fora do 
espectro de $\hz$ é 1587.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/estima_espectro/exemplo_d_exclusao.pdf}
  \caption{Estimativa das probabilidades de falha $\vec{p}_0$ para um código (9602,4801,90)-QC-MDPC gerado aleatoriamente
  usando $M = 100$ milhões de testes de decodificação}
  \label{fig:exemplo_d_exclusao}
\end{figure}

A eficiência de cada um dos algoritmos de reconstrução apresentados neste trabalho será 
analisada em função da $d$-exclusão obtida pelo algoritmo de recuperação do espectro.
Com essa métrica, podemos especificar que o objetivo deste trabalho é encontrar algoritmos
de reconstrução mais eficientes, mas que consigam tratar de menores $d$-exclusões.

Quanto menor a $d$-exclusão que um algoritmo de reconstrução precisa para funcionar 
eficientemente, também menor é o número de decodificações necessárias para quebrar 
uma chave. Estimar este número é importante para determinar qual deve ser a vida útil 
de chaves QC-MDPC para que estas sejam usadas de forma segura. Infelizmente não é
fácil encontrar analiticamente o valor esperado dos tamanhos das $d$-exclusões
em relação ao número $M$ de decodificações. Isso pois essa relação é dependente da taxa de 
falha, que é específica de cada código, e não se conhecem meios analíticos de encontrá-la.
Uma expressão para a probabilidade de a decodificação 
falhar para códigos QC-MDPC seria um bom primeiro passo para desenvolver decodificadores
que, quando falham, não dão informação sobre o espectro. Esta é uma área de pesquisa 
ativa em Teoria de Códigos, e este é um problema difícil~\cite{ryan2009channel}.
Portanto fizemos simulações
para entender a relação entre $M$ e as $d$-exclusões.


\section{Como o número de decodificações afeta a $d$-exclusão}

Para analisar a relação entre o número de decodificações e a $d$-exclusão obtida, 
implementamos em C o esquema QC-MDPC McEliece e foi feita
uma simulação com 200 códigos QC-MDPC para o nível de segurança de 80 bits. Para 
cada código, foram considerados 100 milhões de testes de decodificação usando o algoritmo 
de \emph{bit-flipping} de Gallager~\cite{gallager1962low}. Sua descrição pode ser vista
no Algoritmo~\ref{alg:gall_bit_flipping}, e também pode ser visto como
o algoritmo $\mathcal{B}$ considerado por Maurich et al.~\cite{maurich2015implementing}.
Note que este algoritmo é muito similar aos
outros decodificadores apresentados neste trabalho, com a diferença de que um bit é invertido
se o número de equações de paridade insatisfeitas a que ele pertence for maior do que certos
valores previamente calculados, chamados \emph{thresholds} de Gallager, que só dependem dos
parâmetros $n, k,$ e $w$ do código, e variam de acordo com o número da iteração em questão.
Gallager discute em seu trabalho como calcular os valores dos 
\emph{thresholds}~\cite{gallager1962low}.
Escolhemos esse algoritmo para facilitar a comparação com o trabalho de
Guo et al.~\cite{guo2016key}, já que eles usaram esse mesmo decodificador para seus testes.
Todo o código-fonte e os dados gerados podem ser encontrados em
\url{www.ime.usp.br/~tpaiva/msc}.

\begin{algorithm}[h]
  \Entrada{$\mat{H}$ matriz de paridade esparsa $r \times n$ de um código LDPC\\
    \myinput{$\vec{y}$ uma palavra transmitida a ser decodificada}
    \myinput{\texttt{max\_it} o número máximo de iterações}
  }
  \Saida{A decodificação estimada de $\vec{y}$, ou $\perp$ se o número máximo de
         iterações for excedido}
  \Inicio{
    \var{it} $\gets$ 0 \\
    \Enqto{$ \vec{y}\mat{H}^T \neq \vec{0} $ e $\var{it} < \var{max\_it}$}{
      \Para{cada $j = 1, 2, \ldots, n$}{
        $ f_j \gets $ Número de vizinhos de $v_j$ insatisfeitos
      }
      \Para{cada $j = 1, 2, \ldots, n$}{
        \Se{$f_j \geq \var{GallagerThresholds}[\var{it}]$}{
          $y_j \gets \bar{y_j}$
        }
      }
      $\var{it} \gets \var{it} + 1$
    }
    \Se{$\var{it} \geq \var{max\_it}$}{
      \Retorna{$\perp$}
    }
    \Senao{
      \Retorna{$\vec{y}$}
    }
  }
  \caption{Algoritmo de \emph{bit-flipping} de Gallager~\cite{gallager1962low} usado para os testes de decodificação}
  \label{alg:gall_bit_flipping}
\end{algorithm}


Cada teste de decodificação computa, para cada $M = 1, 2, \ldots, 100$ milhões, 
as $d$-exclusões obtidas para as taxas
de falha para possíveis distâncias em $\sigma(\hz)$ e em $\sigma(\ho)$. 
Um exemplo do resultado de um teste de decodificação pode ser visto na 
Figura~\ref{fig:exemplo_sim_decod}.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/estima_espectro/exemplo_uma_sim_decod.pdf}
  \caption{Relação entre as $d$-exclusões obtidas e número de testes de decodificação,
   para um dos 200 códigos testados}
  \label{fig:exemplo_sim_decod}
\end{figure}

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1]{figuras/estima_espectro/d_sep_obtida_100M_200cods.pdf}
  \caption{Relação entre as $d$-exclusões obtidas e o número de testes de decodificação, considerando
  os resultados para 200 códigos diferentes com parâmetros de segurança de 80 bits}
  \label{fig:d_sep_200cods}
\end{figure}

Tanto pela natureza aleatória dos testes de decodificação e até da geração dos códigos
QC-MDPC, pode haver muita variabilidade nas $d$-exclusões obtidas. Para podermos analisar 
os dados para os 200 códigos testados, a Figura~\ref{fig:d_sep_200cods} mostra os
\emph{boxplots} separados por intervalos de 10 milhões de decodificações. Uma das 
observações que motivaram este trabalho é que a $d$-exclusão cresce rápido no intervalo
entre 0 e 40 milhões de decodificações, e passa a crescer cada vez mais lentamente. Assim,
através de algoritmos de reconstrução que tratem eficientemente de $d$-exclusões entre 750 e 1000, para 80
bits de segurança, 
o número de testes de decodificação de pouco mais de 200 milhões
recomendado por Guo et al. pode ser diminuído para aproximadamente 30 milhões. 


\section{Obtendo distâncias dentro e fora do espectro}
\label{sec:d0_d1_s0_s1}

Para que os algoritmos de reconstrução sejam eficazes, é importante que lhes sejam 
dados como entrada um conjunto, em geral grande (e.g. $\sim r/6$ entradas),
de distâncias fora do espectro, e um outro conjunto, 
em geral pequeno (e.g. 1 entrada), de distâncias dentro do espectro. 

Obter uma distância dentro do espectro é relativamente fácil. 
Pegue a saída $\vec{p}_0$ do algoritmo de estimação de espectro, e tome a distância
$d$ que tenha a menor taxa de falha em $\vec{p}_0$, isto é, $\vec{p}_0[d]$ é mínimo.
Tipicamente, após um pequeno número de testes de decodificação a entrada com menor taxa de falha
de fato está dentro do espectro. Pelo resto do texto, supomos que é fácil obter ao menos
uma distância dentro do espectro de \hz, e outra dentro do espectro de \ho, 
denotadas por $s_0$ e $s_1$, respectivamente.

Obter conjuntos grandes de distâncias fora do espectro é mais difícil.
Idealmente, se fosse conhecido que $q$ distâncias podem ser $d$-excluídas a partir de
$\vec{p}_0$, bastaria tomar as $q$ distâncias com maiores taxas de falha em $\vec{p}_0$. O
problema é que em geral não se sabe qual foi a $d$-exclusão obtida pela saída do algoritmo 
de estimação de espectro. Um modo conservador de lidar com isso é descobrir qual a mínima
$d$-exclusão necessária para que o algoritmo de reconstrução escolhido trabalhe eficientemente.
Uma vez determinado que esta mínima $d$-exclusão é $q$, faça o seguinte.
\begin{enumerate}
  \item Faça $i \gets 1$.
  \item Faça $M_i$ testes de decodificação e atualize os vetores $\vec{p}_0$
  e $\vec{p}_1$. \label{lin:Mdecods}
  \item Construa os conjuntos $D_0$ e $D_1$ 
    com as $q$ entradas cujas taxas de falha são máximas em $\vec{p}_0$ e $\vec{p}_1$, 
    respectivamente.
  \item Execute o algoritmo de reconstrução de chave usando os conjunto $D_0$ e $D_1$
  como o conjunto
  das distâncias $d$-excluídas. Se o algoritmo termina sem encontrar a chave, $D_0$
  ou $D_1$ devem conter alguma distância dentro do espectro, então faça $i \gets i + 1$ e 
  volte para o passo~\ref{lin:Mdecods}. \label{lin:passo_d0_d1}
\end{enumerate}

O passo~\ref{lin:passo_d0_d1} pode variar de acordo com o algoritmo de reconstrução usado.
Por exemplo, o algoritmo de reconstrução de Guo et al. pode ser executado tanto com
$D_0$ quanto com $D_1$. Se ambas as execuções falharem em encontrar a chave, então
isso implica que ambos os conjuntos $D_0$ e $D_1$ contêm entradas dentro dos espectros
correspondentes de \hz e \ho. Em contraste com esse algoritmo, o algoritmo proposto 
na Seção~\ref{cap:ataque_kernel} deve ser executado com ambos os conjuntos $D_0$ e $D_1$.
Se o algoritmo falhar, então ao menos um dos conjuntos contém entradas dentro de seu 
espectro correspondente. 

O número de decodificações a cada fase $M_i$ deve ser modulado de acordo com os tempos de execução 
dos algoritmos. Em geral, é interessante que no começo sejam feitos muitos testes de decodificação, 
pois há baixa probabilidade de se obter uma boa $d$-exclusão com poucos testes, e
depois sejam feitos cada vez menos testes de decodificação a cada execução do algoritmo de 
reconstrução. Por exemplo, para o algoritmo de reconstrução de Guo et al., considerando-se
o nível de segurança de 80 bits, uma parametrização razoável seria $M_0 = 200$ milhões, e 
$M_i = 20$ milhões para todo $i \geq 1$. 