%!TEX root = slides.tex

\section{Ataque de reação ao QC-MDPC McEliece}

\begin{frame}[fragile]{Ataque de reação ao QC-MDPC McEliece}

Observações importantes para o ataque:
\begin{enumerate}
    \item O vetor $\vec{h}_0$ pode determinar a chave completamente
    \item O decodificador pode falhar, pedindo então o reenvio
    \item A taxa de falha está relacionada com o vetor de erros $\vec{e}$
    \item Taxa de falha é menor se $\vec{h}_0$ e $\vec{e}$ compartilham certa \textbf{propriedade}
        \label{enum:taxa_aderencia}
\end{enumerate}

$\Rightarrow$ taxas de falha para erros conhecidos extraem informação de $\vec{h}_0$

\end{frame}




\begin{frame}[fragile]{Ataque de reação ao QC-MDPC McEliece}

\begin{alertblock}{Definição}
    \textit{
    O espectro de distâncias de um vetor $\vec{v}$, denotado por $\sigma(\vec{v})$, é o
    conjunto de distâncias cíclicas entre posições não-nulas de $\vec{v}$.
    }
\end{alertblock}

Por exemplo:
\begin{itemize}
    \item $\vec{v} = [ \, 1 \, 0 \, 0 \, 0 \, 0 \, 1 \, 0 \, 0 \, 0 \, 0 \, 1 \,  ]$
    \item $\sigma(\vec{v}) = \{ 1, 5 \}$
    \item 1 tem multiplicidade $\mu(1) = 1$
    \item 5 tem multiplicidade $\mu(5) = 2$
\end{itemize}

\end{frame}


\begin{frame}[fragile]{Ataque de reação ao QC-MDPC McEliece}

\begin{alertblock}{Fato \scriptsize (observação \ref{enum:taxa_aderencia} reescrita)}
    Seja $\vec{e}_0$ a primeira metade do erro $\vec{e}$ usado para encriptar uma mensagem.
    Quanto mais distâncias em comum em $\sigma(\vec{h}_0)$ e $\sigma(\vec{e}_0)$,
    e mais altas as suas multiplicidades, menor a probabilidade de o decodificador falhar para o erro $\vec{e}$.
\end{alertblock}


\begin{figure}[H]
    \includegraphics[width=\textwidth]{figuras/ataque/taxa_dentro_fora_generico.pdf}
\end{figure}

\end{frame}



\begin{frame}[fragile]{Testando se uma distância pertence ao espectro}

Para testar se uma distância $d$ pertence ao espectro $\sigma(\vec{h}_0)$:

\begin{enumerate}
    \item Tome o conjunto de erros de testes para a distância $d$
    \[
      \Psi_d = \left\{ \, \left( \vec{e}_0 \mid \vec{0} \right) : \text{$\vec{e}_0$ tem $\frac{t}{2}$ pares distintos de índices d-distantes}  \, \right\}
    .\]

    \item $p \gets 0$:
    \item Faça $M$ iterações do seguinte procedimento:
    \begin{enumerate}
        \item Selecione um erro $\vec{e}$ de $\Psi_d$ aleatoriamente
        \item Encripte uma mensagem qualquer $\vec{m}$ obtendo $\vec{c} \gets \vec{m}G \oplus \vec{e}$
        \item Envie $\vec{c}$ ao destinatário
        \item Se decodificação falhar, faça $p \gets p + 1$
    \end{enumerate}
    \item Use a taxa de falha $p/M$ para decidir se $d$ pertence ao espectro
\end{enumerate}

\end{frame}


\begin{frame}[fragile]{Explicação do ataque}

    Decodificadores por \emph{bit-flipping} terminam tipicamente em poucas
    iterações $\approx 3-6$

    $\Rightarrow$ Uma boa primeira iteração é crucial para a decodificação correta

    Considere as equações de paridade:
    \[
        s_j = \sum_{i=1}^{n} h_{ij} c'_i \mod 2, \text{ para $j = 1, 2, \ldots, r$}
    \]
    Vale que
    \[
        s_j = \sum_{i=1}^{n} h_{ij} e_i \mod 2
    \]
    Então $\#\{ h_{ij} =  e_i \} $ determina $s_j$
\end{frame}


\begin{frame}[fragile]{Explicação do ataque}

    Considere os contadores de equações insatisfeitas de cada variável no
    algoritmo de \emph{bit-flipping}
    \begin{itemize}
        \item Há exatamente $w$ variáveis em cada equação
        \item Se $s_j = 1$, os $w$ são incrementados
        \item Se $s_j = 0$, nenhum dos $w$ contadores é incrementados
    \end{itemize}

    \begin{table}[H]
    \centering
    \label{tab:tratamento_contadores}
    \begin{tabular}{@{}ccc@{}}
    \toprule
    $\#\{ h_{ij} =  e_i \} $ & \begin{tabular}[c]{@{}c@{}}contadores tratados \\ corretamente\end{tabular} & \begin{tabular}[c]{@{}c@{}}contadores tratados\\ incorretamente\end{tabular} \\ \midrule
    $0$                           & $w$                                                                          & $0$                                                                           \\
    $1$                           & $1$                                                                          & $w - 1$                                                                           \\
    $2$                           & $w - 2$                                                                      & $2$                                                                           \\
    $3$                           & $3$                                                                          & $w - 3$                                                                           \\
    $\vdots$                      & $\vdots$                                                                     & $\vdots$                                                                           \\
    \bottomrule
    \end{tabular}
    \end{table}



\end{frame}


\begin{frame}[fragile]{Explicação do ataque}

    Erros em $\Psi_d$ aumentam a chance de uma boa primeira iteração quando
    $d$ pertence ao espectro

    Isso pois garante que ao menos t/2 pontos em que $h_{ij} e_i = 1$ apareçam de
    forma controlada (em pares)
    \begin{figure}[H]
        \includegraphics[width=0.7\textwidth]{figuras/ataque/heatmap.pdf}
    \end{figure}


\end{frame}


\begin{frame}[fragile]{Explicação do ataque}

    \begin{table}[]
    \centering
    \caption{Diferentes distribuições de $\# \{ h_{ij} e_i = 1 \}$ quando os erros são tirados de $\Psi_d$ \cite{guo2016key}}
    \label{tab:lambdas_dist}
    \begin{tabular}{@{}ccc@{}}
    \toprule
    \multirow{2}{*}{$\# \{ h_{ij} e_i = 1 \}$} & \multicolumn{2}{c}{Probabilidade}                                                                                                                                                            \\ \cmidrule(l){2-3}
                                 & \begin{tabular}[c]{@{}c@{}}$\vec{h}_0$ não \\ contém nem um \\ par $d$-distante\end{tabular} & \begin{tabular}[c]{@{}c@{}}$\vec{h}_0$ contém \\ ao menos um \\ par $d$-distante\end{tabular} \\ \midrule
    0                            & 0.4485                                                                                       & \textbf{0.4534 $\uparrow$ }                                                                                        \\
    1                            & 0.3663                                                                                       & \textbf{0.3602 $\downarrow$ }                                                                                        \\
    $ \geq 2$                    & 0.1852                                                                                       & 0.1864                                                                                        \\ \bottomrule
    \end{tabular}
    \end{table}


\end{frame}


\begin{frame}[fragile]{Reconstrução da chave a partir do espectro}

    Queremos reconstruir a chave $\vec{h}_0$ a partir de seu espectro $\sigma(\vec{h}_0)$

    Qualquer \emph{shift} de $\vec{h}_0$ serve como chave

    A partir de $\vec{h}_0$ e $G$ é possível obter $H$ completamente

    Para testar se um vetor é a chave basta obter $H$ e ver se ela é MDPC


\end{frame}


\begin{frame}[fragile]{Reconstrução da chave a partir do espectro}

    \begin{tikzpicture}[level/.style={sibling distance=40mm/#1}]
    \node [circle,draw] (z){$1$}
      child {node [circle,draw] (a) {$2$}
        child {node [circle,draw] (g) {$3$}
          child {node [circle,draw] {$4$}}
          child {node [circle,draw] {$5$}}
          child {node  {$\vdots$}}
        }
        child {node (g) {$\vdots$}}
      }
      child {node [circle,draw] (j) {$3$}
        child {node [circle,draw] (k) {$4$}
          child {node [circle,draw] {$5$}}
          child {node  {$\vdots$}}
        }
        child {node [circle,draw] (g) {$5$}
          child {node [circle,draw] {$6$}}
          child {node  {$\vdots$}}
        }
        child {node (g) {$\vdots$}}
     }
      child {node (j) {$\vdots$}
     };
    \end{tikzpicture}

\end{frame}


\begin{frame}[fragile]{Reconstrução da chave a partir do espectro}


    O número médio de filhos válidos em cada nível decresce exponencialmente!

    Seja $s$ o número de distâncias no espectro:

    \begin{itemize}
        \item O número de distâncias possíveis é $r/2$
        \item A razão de entradas no espectro $\alpha = 2s/r$ é menor do que 1
        \item Há $s$ filhos no nível 1
        \item Há em torno de $s \alpha$ filhos no nível 2
        \item Há em torno de $s \alpha^2$ filhos no nível 3
        \item $\vdots$
    \end{itemize}

\end{frame}



\begin{frame}[fragile]{Notas sobre o ataque}

    O ataque foi feito contra códigos $(9602, 4801, 90)$-QC-MDPC ($\lambda = 80$)

    Foi feita a suposição de que o peso de $\vec{h}_0 = 45$

    Com pequenas alterações pode-se atacar conversões IND-CCA2

    Conjecturaram ser possível o ataque contra decodificadores suaves

    Os autores usaram os decodificadores de \emph{bit-flipping} de Gallager

    A escolha do decodificador tem forte influência na escolha de $M$

\end{frame}


\begin{frame}[fragile]{Sobre a escolha do decodificador}

    \small Separação completa com $M = 100000$ para o decodificador de Gallager
    \begin{figure}[H]
        \includegraphics[width=\textwidth]{figuras/ataque/taxa_gallager.pdf}
    \end{figure}

    \small Não há separação com $M = 100000$ para o decodificador de Misoczki
    \begin{figure}[H]
        \includegraphics[width=\textwidth]{figuras/ataque/taxa_misoczki.pdf}
    \end{figure}

\end{frame}


\begin{frame}[fragile]{Sobre a escolha do decodificador}
    \centering
    \small Separação completa ocorre com $M \approx  250000$ $\Rightarrow$ \textbf{5 dias}!
    \begin{figure}[H]

        \begin{columns}
            \begin{column}{0.1\textwidth}
                \centering
                \footnotesize $M~=~100000$

            \end{column}
            \begin{column}{0.9\textwidth}  %%<--- here
                 \includegraphics[width=1.0\textwidth]{figuras/ataque/mis_sep1.pdf}
            \end{column}
        \end{columns}

        \begin{columns}
            \begin{column}{0.1\textwidth}
                \centering
                \footnotesize $M~=~200000$

            \end{column}
            \begin{column}{0.9\textwidth}  %%<--- here
                 \includegraphics[width=1.0\textwidth]{figuras/ataque/mis_sep2.pdf}
            \end{column}
        \end{columns}

        \begin{columns}
            \begin{column}{0.1\textwidth}
                \centering
                \footnotesize $M~=~300000$

            \end{column}
            \begin{column}{0.9\textwidth}  %%<--- here
                 \includegraphics[width=1.0\textwidth]{figuras/ataque/mis_sep3.pdf}
            \end{column}
        \end{columns}

    \end{figure}

\end{frame}


% \begin{frame}[fragile]{Sobre a escolha do decodificador}
%
%     % \small
%     % \begin{table}[]
%     % \centering
%     % \caption{My caption}
%     % \label{my-label}
%     % \begin{tabular}{@{}ccccc@{}}
%     % \toprule
%     % \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Algoritmo de\\ decodificação\end{tabular}} & \multicolumn{2}{c}{\begin{tabular}[c]{@{}c@{}}Erros em $\Psi_d$\\ com $d \notin \sigma(\vec{h}_0)$\end{tabular}} & \multicolumn{2}{c}{\begin{tabular}[c]{@{}c@{}}Erros em $\Psi_d$\\ com $\mu(d) = 1$\end{tabular}} \\ \cmidrule(l){2-5}
%     %                                                                                       & média                                                 & desvio-padrão                                            & média                                         & desvio-padrão                                    \\ \midrule
%     % Gallager                                                                              & 0.0044099                                             & 0.00003868                                               & 0.0009116                                     & 0.00001304                                       \\
%     % Misoczki                                                                              & 0.0009159                                             & 0.00011083                                               & 0.0005855                                     & 0.00008313                                       \\ \bottomrule
%     % \end{tabular}
%     % \end{table}
%
% \end{frame}
