%!TEX root = slides.tex

\section{Introdução}

\subsection{Motivação}

\begin{frame}[fragile]{Motivação}

    \textbf{Por que esquemas criptográficos com códigos corretores?} \\
    \begin{itemize}
        \item[] Computadores quânticos quebram esquemas em uso \cite{shor1997poly}
            \begin{itemize}
                \item como RSA e Curvas Elípticas \cite{rsa1978rsa,miller1986ecc}
            \end{itemize}
        \item[] Ainda resistem a ataques quânticos esquemas baseados em
            \begin{itemize}
                \item Códigos corretores de erros
                \item Reticulados
                \item Hashes
                \item Equações quadráticas multivariadas
            \end{itemize}
        \item[] Esses esquemas são chamados \textbf{Pós-Quânticos}
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Criptografia com Códigos Corretores}

    \textbf{Esquema de McEliece} \cite{mceliece1978} \\
    \begin{itemize}
        \item Esquema original de 1978 ainda não quebrado
        \item Primeiro baseado em códigos corretores de erros
        \item Primeiro a usar procedimento aleatório na encriptação \cite{menezes1996handbook}
        \item Encriptação e Decriptação mais eficientes que RSA e CE \cite{bernstein2013mcbits}
        \item Baseado no problema \cNP-difícil da decodificação por síndrome~\cite{berlekamp1978inherent}
        \item Não é IND-CPA então precisa de conversões obrigatórias~\cite{kobara2001semantically}
    \end{itemize}

    O problema é que usa \textbf{chaves públicas muito grandes}

\end{frame}

\begin{frame}[fragile]{Tamanho das chaves públicas}

    \begin{table}[H]
    \centering
    \caption{Comparação entre alguns esquemas em relação ao tamanho das chaves públicas~\cite{bernstein2013mcbits}.}
    \label{tab:mcbits}
    \begin{tabular}{@{}cccc@{}}
    \toprule
    \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Nível de segurança\\ aproximado\end{tabular}} & \multicolumn{3}{c}{\begin{tabular}[c]{@{}c@{}}Tamanho da chave pública\\ (Bytes)\end{tabular}} \\ \cmidrule(l){2-4}
                                        & Curvas Elípticas                 & RSA                               & McEliece                \\ \midrule
    80  &  20  &  128   &  65006  \\
    112 &  28  &  256   &  169512  \\
    128 &  32  &  384   &  261702  \\
    192 &  48  &  960   &  523177  \\
    256 &  64  &  1920  &  1046739 \\ \bottomrule
    \end{tabular}
    \end{table}


\end{frame}


\begin{frame}[fragile]{Variantes do esquema de McEliece}

        Esquema original usa códigos de \textbf{Goppa binários e irredutíveis}~\cite{goppa1970new, berlekamp1973goppa}

        Algumas famílias de códigos que permitem chaves compactas
        \begin{itemize}
            \item QC-BCH \cite{gaborit2005shorter}
            \item QC-Alternantes \cite{berger2009reducing}
            \item Goppa Quase Diádicos \cite{misoczki2009compact}
            \item LDPC / QC-LDPC \cite{shokrollahi2000using}
            \item MDPC / QC-MDPC \cite{misoczki2013mdpc}
        \end{itemize}

        A maioria foi quebrada pouco depois de sua publicação~\cite{otmani2010cryptanalysis, faugere2010algebraic,faugere2016structural}

        Até 2016 a variante \textbf{QC-MDPC} era tida como a mais promissora\cite{augot16initial}
\end{frame}


\begin{frame}[fragile]{Ataque aos códigos QC-MDPC}

    Ataque de recuperação de chave na Asiacrypt~2016~\cite{guo2016key}
    \begin{itemize}
        \item É um ataque de reação
        \item Ataca QC-MDPC original e as conversões ditas IND-CCA2
        \item Fase 1 de coleta de dados é lenta $\approx$ 1-2 dias
        \item Fase 2 de reconstrução de chave é rápida $\approx$ 3 minutos
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Objetivos}

    \begin{enumerate}
        \item Atacar o QC-MDPC com o decodificador original
        \item Acelerar o ataque balanceando melhor as Fases
        \item Tentar estender o ataque para uma variante do QC-MDPC
    \end{enumerate}

\end{frame}
