%!TEX root = slides.tex

\section{Esquema de McEliece}



\begin{frame}[fragile]{Um pouco de Teoria de Códigos Lineares}

    \usetikzlibrary{calc,trees,positioning,arrows,chains,shapes.geometric,%
  decorations.pathreplacing,decorations.pathmorphing,shapes,%
  matrix,shapes.symbols}

  \tikzstyle{rec}=[draw, minimum width=4.3em, minimum height=2em]
  \begin{figure}[h]
    \centering
    \begin{tikzpicture}[auto]
      \node [rec] (fonte) {Fonte};
      \node [rec] (codif) [below of=fonte, node distance=3.3cm] {Codificador};
      \node [rec] (canal) [right of=codif, node distance=4cm] {Canal};
      \node [rec] (decod) [right of=canal, node distance=4cm] {Decodificador};
      \node [rec] (recep) [above of=decod, node distance=3.3cm] {Receptor};

      \path[->] (fonte) edge node {$[1 \, 0 \, 1]$} (codif);
      \path[->] (codif) edge node {$[111 \, 000 \, 111]$} (canal);
      \path[->] (canal) edge node {$[011 \, 001 \, 111]$} (decod);
      \path[->] (decod) edge node {$\textcolor{gray}{[111 \, 000 \, 111]} \Rightarrow [1 \, 0 \, 1]$} (recep);

    \end{tikzpicture}
    \caption{Exemplo de transmissão de uma palavra $m$ através de um canal que produziu o
    erro $e = [100 \, 001 \, 000]$, usando um Código de Repetição.}
  \label{fig:codific_canal_ex}
  \end{figure}

\end{frame}

\begin{frame}[fragile]{Códigos Lineares}

    \begin{alertblock}{Definição}
        \textit{
        Um \textbf{código binário $[n, k]$-linear} é um subespaço vetorial de dimensão $k$ do espaço $\mathbb{F}_2^n$. \\
        }
    \end{alertblock}

\end{frame}

\begin{frame}[fragile]{Matrizes Geradoras e de Paridade}
    Então, se \code é um código $[n, k]$-linear:
    \begin{itemize}

        \item \code pode ser descrito por sua \textbf{imagem} ou por seu \textbf{núcleo}


        \item Chama-se \textbf{matriz geradora} toda $G \in \Fb^{k \times n}$ tal que
        \[
            \code = \left\{ mG : m \in \Fb^k  \right\}
        \]


        \item Chama-se \textbf{matriz de paridade} toda $H \in \Fb^{(n - k) \times n}$ tal que
        \[
            \code = \left\{ c \in \Fb^n : cH^T = 0  \right\}
        \]

    \end{itemize}

\end{frame}

\begin{frame}[fragile]{Codificação de Mensagens}

    Fixe $G, H$ matrizes geradora e de paridade de \code:
    \begin{itemize}

        \item Uma mensagem $m$ é codificada como
        \[
            c = mG
        \]

        \item É sobredeterminado o sistema
        \[
            mG = c
        \]

        \item A \textbf{síndrome} de um vetor $\bar{c} \in \Fb^n$ é o vetor
        \[
            s = cH^T \implies \bar{c} \in \code \Leftrightarrow s = 0
        \]

        \item Se $\bar{c} = c \oplus e$, então
        \[
            s = \bar{c}H^T = (c \oplus e)H^T = cH^T \oplus eH^T = eH^T
        \]

    \end{itemize}
\end{frame}


\begin{frame}[fragile]{Peso e distância de Hamming}

    Sejam $u, v$ palavras de $\Fb^n$:
    \begin{itemize}

        \item O \textbf{peso} de $u$ é o número de coordenadas não nulas de $u$:
        \[
            w([1 \, 0 \, 0 \, 1]) = 2
        \]

        \item A \textbf{distância de Hamming} entre $u$ e $v$ é o número de coordenadas
            em que $u$ e $v$ diferem:
        \begin{align*}
             d(u, v) = w(u \oplus v) \\
             d([1 \, 0 \, 0 \, 1], [1 \, 1 \, 0 \, 1]) = 1
        \end{align*}
    \end{itemize}
\end{frame}


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

    Dada uma palavra $\bar{c} \in \Fb^n$, queremos encontrar uma palavra $c$ tal que
    \[
        d(\bar{c}, c) \leq d(\bar{c}, u), \text{ para qualquer $u \in \Fb^n $}.
    \]

    \begin{itemize}

        \item Decodificação \cNP-difícil no pior caso \cite{berlekamp1978inherent}

        \item Conjecturada tipicamente difícil para códigos aleatórios

        \item É preciso desenhar bons códigos que admitam a construção de decodificadores

        \begin{itemize}
            \item Reed-Muller
            \item Goppa
            \item LDPC
        \end{itemize}
    \end{itemize}
\end{frame}




\begin{frame}[fragile]{Esquema de McEliece em alto nível}
    Para Alice enviar uma mensagem a Beto:
    \begin{enumerate}
        \item A chave pública de Beto é uma matriz geradora \gpub de um código Linear
                para o qual apenas Beto conhece um decodificador eficiente
        \item Alice codifica a sua mensagem usando essa \gpub e inverte uma certa quantidade
            de bits aleatórios da mensagem codificada obtendo $c'$
        \item Beto recebe $c'$ e decodifica a mensagem usando o seu decodificador
    \end{enumerate}


\end{frame}

\begin{frame}[fragile]{Códigos de Goppa}

    Usa códigos de Goppa binários e irredutíveis:
    \begin{itemize}
        \item Cada código é gerado por um polinômio irredutível $g$ de $\mathbb{F}_{2^m}[x]$
        \item A capacidade de correção é igual ou superior ao grau $t$ de $g$
        \item É fácil construir $t$-decodificadores eficientes conhecendo $g$
        \item Não se conhece algoritmo eficiente para construir decodificadores sem conhecer $g$

        \item É difícil em geral distinguir matrizes geradoras de Goppa e geradoras de aleatórios

            Embora seja possível para $k$ próximo de $n$ \cite{faugere2013distinguisher}
    \end{itemize}

\end{frame}



\begin{frame}[fragile]{Parâmetros para cada nível de segurança}

    \begin{table}[H]
    \centering
    \caption{Parâmetros de famílias de códigos de Goppa para cada nível de segurança $\lambda$ \cite{bernstein2013mcbits}.}
    \label{tab:mcbits}
    \begin{tabular}{@{}cccccc@{}}
    \toprule
    $\lambda$ & $n$  & $k$  & $t$ & $m$ & \begin{tabular}[c]{@{}c@{}}tamanho da chave pública\\ (Bytes)\end{tabular} \\ \midrule
    81        & 2048 & 1751 & 27  & 11  & 65006                                                                      \\
    95        & 2048 & 1608 & 40  & 11  & 88440                                                                      \\
    105       & 2480 & 1940 & 45  & 12  & 130950                                                                     \\
    119       & 2690 & 2018 & 56  & 12  & 169512                                                                     \\
    146       & 3408 & 2604 & 67  & 12  & 261702                                                                     \\
    187       & 4624 & 3389 & 95  & 13  & 523177                                                                     \\
    263       & 6960 & 5413 & 119 & 13  & 1046739                                                                    \\ \bottomrule
    \end{tabular}
    \end{table}

\end{frame}


\begin{frame}[fragile]{Geração de Chaves}

    \begin{enumerate}
        \item Tome $n, t,$ e $k$ que permitam nível de segurança $\lambda$ Tabela~\ref{tab:mcbits}
        \item $g \gets $ polinômio gerador de um código de Goppa aleatório $\mathcal{G}$
        \item $G \gets $ matriz $k \times n $ geradora de $\mathcal{G}$
        \item $S \gets $ matriz $k \times k $ não singular aleatória
        \item $P \gets $ matriz de permutação $n \times n $ aleatória
        \item \[
        \gpub \gets SGP \qquad \gsec \gets SG
        \]

        \item \[
            \sk \gets (\gsec, P, g) \qquad \pk \gets (\gpub, t)
        \]

        \item \Retorna $\left( \sk, \pk \right)$
    \end{enumerate}

\end{frame}


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

    Para encriptar uma mensagem $m$ com uma chave pública \pk:
    \begin{enumerate}
        \item $(\gpub, t) \gets \pk $ \\
        \item $e \gets $ vetor aleatório de $\Fb^n$ de peso $t$ \\
        \item $c \gets mG \oplus e$ \\
        \item \Retorna $c$
    \end{enumerate}

\end{frame}


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

    Para decriptar um cifrado $c$ com uma chave secreta \sk:
    \begin{enumerate}
        \item $(\gsec, P, g) \gets \sk $ \\
        \item $\Phi \gets $ algoritmo $t$-decodificador para $\mathcal{G}$ usando $g$
        \item $ c_1 \gets cP^{-1} = (mG \oplus e)P^{-1}  = m\gsec \oplus eP^{-1}$ \\
        \item $ c_2 \gets \Phi(c_1) = m\gsec $\\
        \item $ m \gets $ solução do sistema sobredeterminado $m\gsec = c_2$ \\
        \item \Retorna{$m$}
    \end{enumerate}
\end{frame}

\begin{frame}[fragile]{Reduzir Tamanhos das Chaves}

    Ideias para Reduzir Tamanhos de Chaves:
    \begin{itemize}
        \item Usar códigos que corrigem mais erros

        \item Usar códigos que permitem representações compactas
    
    \end{itemize}

\end{frame}
