%!TEX root = slides.tex

% \begin{frame}[fragile]{Teoria de Códigos}
%     \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 {$m \in \mathcal{M}$} (codif);
%       \path[->] (codif) edge node {$c \gets E(m)$} (canal);
%       \path[->] (canal) edge node {$c' \gets c \oplus e$} (decod);
%       \path[->] (decod) edge node {$\hat{m} \gets D(c')$} (recep);
%
%     \end{tikzpicture}
%     \caption{Transmissão de uma palavra $m$ através de um canal ruidoso.}
%   \label{fig:codific_canal_gen}
%   \end{figure}
%
% \end{frame}



% \section{Esquema de McEliece}
%
% \begin{frame}[fragile]{Esquema de McEliece}
%     Elaborado por McEliece em 1978 \cite{mceliece1978}
%     \begin{itemize}
%         \item Primeiro esquema baseado no problema da decodificação
%         \item Primeiro que usa procedimento aleatório na encriptação
%         \item Operações mais rápidas do que as respectivas do RSA e CE
%     \end{itemize}
%     Porém ficou esquecido pois
%     \begin{itemize}
%         \item Chaves públicas muito grandes: $ \lambda = 100 \Rightarrow $ tamanho $\geq 100 $ kB
%         \item Esquema de assinatura parecia ser impossível, até CFS \cite{courtois2001achieve}
%     \end{itemize}
%     Até que Shor \cite{shor1997poly} mostra algoritmo quântico que resolve $\log$ discreto
%
% \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{algorithm}[H] % KeyGen
%       \Entrada{$\lambda$ nível de segurança. }
%       \Saida{$\left( \sk, \pk \right)$ o par de chaves secreta e pública.}
%       \Inicio{
%         Tome $n, t,$ e $k$ que permitam nível de segurança $\lambda$ Tabela~\ref{tab:mcbits} \\
%         $g \gets $ polinômio gerador de um código de Goppa aleatório $\mathcal{G}$ \\
%         $\bar{G} \gets $ matriz $k \times n $ geradora de $\mathcal{G}$ \\
%         $\Phi \gets $ algoritmo $t$-decodificador para $\mathcal{G}$ \\
%         $S \gets $ matriz $k \times k $ não singular aleatória \\
%         $P \gets $ matriz de permutação $n \times n $ aleatória \\
%         $G \gets S\bar{G}P$ \\
%         $\hat{G} \gets S\bar{G}$ \\
%
%         $\sk \gets (\hat{G}, P, \Phi) $ \\
%         $\pk \gets (G, t) $ \\
%
%         \Retorna{$\left( \sk, \pk \right)$}
%       }
%       \caption{\alg{KeyGen} para a geração de chaves}
%       \label{alg:mce_key_gen}
%     \end{algorithm}
%
% \end{frame}
%
%
% \begin{frame}[fragile]{Encriptação}
%
%     \begin{algorithm}[H] % Enc
%       \Entrada{$m$ mensagem que Beto quer enviar a Alice. \\
%       \myinput{$\pk$ a chave pública de Alice.}
%       }
%       \Saida{$c$ o texto cifrado da mensagem $m$.}
%       \Inicio{
%         $(G, t) \gets \pk $ \\
%         $e \gets $ vetor aleatório de $\Fb^n$ de peso $t$ \\
%         $c \gets mG \oplus e$ \\
%         \Retorna{$c$}
%       }
%       \caption{\alg{Enc} para a encriptação}
%       \label{alg:mce_enc}
%     \end{algorithm}
%
% \end{frame}
%
%
% \begin{frame}[fragile]{Decriptação}
%
%     \begin{algorithm}[H] % Dec
%         \Entrada{$c$ texto cifrado recebido por Alice. \\
%         \myinput{$\sk$ a chave secreta de Alice.}
%         }
%         \Saida{$m$ a decifração de $c$.}
%         \Inicio{
%             $(\hat{G}, P, \Phi) \gets \sk $ \\
%             $ c_1 \gets cP^{-1} = (mG \oplus e)P^{-1}  = m\hat{G} \oplus eP^{-1}$ \\
%             $ c_2 \gets \Phi(c_1) = m\hat{G} $\\
%             $ m \gets $ solução do sistema sobredeterminado $m\hat{G} = c_2$ \\
%             \Retorna{$m$}
%         }
%         \caption{\alg{Dec} para a encriptação}
%         \label{alg:mce_dec}
%     \end{algorithm}
%
% \end{frame}
%
%
% \begin{frame}[fragile]{Segurança}
%
%     Mas não resiste a ataques de:
%     \begin{itemize}
%         \item Mensagem parcialmente conhecida
%         \item Mensagem relacionada (e.g. reenvio de mensagens)
%         \item Reação
%         \item Maleabilidade
%     \end{itemize}
%
%     O esquema de McEliece é apenas OWE
%     \begin{itemize}
%         \item Conversões de segurança obrigatórias
%     \end{itemize}
%
% \end{frame}
%
%
% \begin{frame}[fragile]{Conversão IND-CCA2 de Kobara e Imai}
%     \begin{algorithm}[H] % Enc
%       \Entrada{$m$ mensagem que Beto quer enviar a Alice. \\
%       \myinput{$\pk$ a chave pública de Alice.}
%       }
%       \Saida{$c$ o texto cifrado da mensagem $m$.}
%       \Inicio{
%         $(G, t) \gets \pk$ \\
%         $r \gets $ número aleatório $\approx 160$ bits \\
%         $z \gets \alg{Hash}(r \| m)$ \\
%         $y  \gets \alg{PRNG}(z) \oplus(r \| m)$ \\
%         $e_z \gets \alg{IntParaErro}(z, t)$ \\
%         $c \gets (yG \oplus e_z) $ \\
%         \Retorna{$c$}
%       }
%       \caption{Conversão IND-CCA2 de \alg{Enc} \cite{kobara2001semantically}}
%       \label{alg:mce_enc_ki_conv}
%     \end{algorithm}
% \end{frame}
%
% \begin{frame}[fragile]{Conversão IND-CCA2 de Kobara e Imai}
%     \begin{algorithm}[H] % Dec
%         \Entrada{$c$ texto cifrado recebido por Alice. \\
%         \myinput{$\sk$ a chave secreta de Alice.}
%         }
%         \Saida{$m$ a decifração de $c$.}
%         \Inicio{
%             $y \gets \alg{Dec}(\alg{Esquerda}(c, k), \sk)$ \\
%             $e_z \gets \alg{Esquerda(c, k)} \oplus yG$ \\
%             $z \gets \alg{ErroParaInt}(e_z) $ \\
%             $ r \| m \gets \alg{PRNG}(z) \oplus (y) $\\
%             \Se{$z = \alg{Hash}(r \| m)$}{
%                 \Retorna{$m$}
%             }
%             \Senao{
%                 \Retorna{$\perp$}
%             }
%         }
%         \caption{Conversão IND-CCA2 de \alg{Dec} \cite{kobara2001semantically}}
%         \label{alg:mce_dec_ki_conv}
%     \end{algorithm}
% \end{frame}
%
% \begin{frame}[fragile]{Ataque Genérico por Conjunto de Informação}
%     Decodificação por Conjunto de Informação - ISD
%     \begin{itemize}
%         \item Selecionar $k$ colunas de $c'$ que não estão com erro
%         \item Se as $k$ colunas de $\hat{G}$ formarem matriz inversível $G'$
%         \item Pode-se recuperar $m$ ao resolver o sistema $mG'= c'$
%     \end{itemize}
%
%
%     Ocorre com baixa probabilidade de
%     \[
%         \frac{\binom{n-t}{k}}{\binom{n}{k}}
%     \]
%
%     E assim o trabalho esperado é limitado inferormente
%     \[
%         \frac{\binom{n}{k}}{\binom{n - t}{k}}
%     \]
% \end{frame}
%
%



\begin{frame}[fragile]{Exemplo com um Código de Hamming}
    Considere o código $[7, 4]$-linear \code que tem matriz geradora $G$ e matriz
    de paridade $H$ tais que:
    \[
    G =
    \begin{bmatrix}
        1 & 1 & 1 & 0 & 0 & 0 & 0 \\
        1 & 0 & 0 & 1 & 1 & 0 & 0 \\
        0 & 1 & 0 & 1 & 0 & 1 & 0 \\
        1 & 1 & 0 & 1 & 0 & 0 & 1
    \end{bmatrix}, \quad
    H =
    \begin{bmatrix}
        1 & 0 & 1 & 0 & 1 & 0 & 1 \\
        0 & 1 & 1 & 0 & 0 & 1 & 1 \\
        0 & 0 & 0 & 1 & 1 & 1 & 1
    \end{bmatrix}.
    \]

    \begin{itemize}
        \item A codificação de $m = [1 \, 0 \, 0 \, 1]$ é

        \[
            c = mG = [0 \, 0 \, 1 \, 1 \, 0 \, 0 \, 1].
        \]

        \item Somando o erro $e = [0 \, 1 \, 0 \, 0 \, 0 \, 0 \, 0]$ a $c$ obtemos

        \[
            \bar{c} = c \oplus e = [0 \, 1 \, 1 \, 1 \, 0 \, 0 \, 1].
        \]

        \item A síndrome de $\bar{c}$ é o vetor

        \[
            s = \bar{c}H^T = [0 \, 1 \, 0].
        \]
    \end{itemize}

\end{frame}
