%!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]{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}
    \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}

