%!TEX root = slides.tex

\section{QC-MDPC McEliece}

\begin{frame}[fragile]{Códigos LDPC}
    \begin{alertblock}{Definição}
        \textit{
        Um código binário e linear com matriz de paridade $H$ é dito um código \emph{LDPC}
        se o número de elementos não nulos de $H$ é $\mathcal{O}(n)$.
        } \cite{gallager1962low}
    \end{alertblock}
\end{frame}


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

  \[
    H =
    \begin{bmatrix}
      1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
      1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
      0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\
      0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
      0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1
    \end{bmatrix}
  \]


  \begin{figure}[h]
    \begin{tikzpicture}[thick,
      every node/.style={draw,circle,minimum size=4mm,inner sep=0pt,outer sep=0pt},
      fsnode/.style={fill=white},
      ssnode/.style={fill=gray},
      every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
      -,shorten >= 2pt,shorten <= 3pt,thick
    ]
       %% the check_nodes
       \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]
       \foreach \i in {1,...,5}
         \node[ssnode,on chain] (c\i) [label=above: $c_{\i}$] {};
       \end{scope}

       %% the var_nodes
       \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]
       \foreach \i in {1,...,10}
         \node[fsnode,on chain] (v\i) [label=below: $v_{\i}$] {};
       \end{scope}

       \draw (c1) -- (v1);
       \draw (c1) -- (v2);
       \draw (c1) -- (v3);
       \draw (c1) -- (v4);
       \draw (c2) -- (v1);
       \draw (c2) -- (v5);
       \draw (c2) -- (v6);
       \draw (c2) -- (v7);
       \draw (c3) -- (v2);
       \draw (c3) -- (v5);
       \draw (c3) -- (v8);
       \draw (c3) -- (v9);
       \draw (c4) -- (v3);
       \draw (c4) -- (v6);
       \draw (c4) -- (v8);
       \draw (c4) -- (v10);
       \draw (c5) -- (v4);
       \draw (c5) -- (v7);
       \draw (c5) -- (v9);
       \draw (c5) -- (v10);
     \end{tikzpicture}
     \caption{Grafo de Tanner da matriz $H$.}
  \label{fig:exemplo_tanner}
  \end{figure}
\end{frame}


\begin{frame}[fragile]{Algoritmo de Decodificação por \emph{bit-flipping}}
    \begin{align*}
        m &\gets [0 \, 1 \, 1 \, 0 \, 0 \, 0] \\
        c &\gets mG = [0 \, 1 \, 1 \, 0 \, 0 \, 0 \, 0 \, 0 \, 1 \, 1] \\
        e &\gets [0 \, 0 \, 0 \, 0 \, 0 \, 0 \, 0 \, 1 \, 0 \, 0] \\
        c' &\gets c \oplus e = [0 \, 1 \, 1 \, 0 \, 0 \, 0 \, 0 \, 1 \, 1 \, 1]
    \end{align*}


    \begin{figure}[h]
      \begin{tikzpicture}[thick,
        every node/.style={draw,circle,minimum size=4mm,inner sep=0pt,outer sep=0pt},
        fsnode/.style={fill=white},
        ssnode/.style={fill=gray},
        onesnode/.style={fill=black, text=white},
        zerosnode/.style={fill=white},
        oknode/.style={fill=green},
        nonode/.style={fill=red},
        every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
        -,shorten >= 2pt,shorten <= 3pt,thick
      ]
        %% the check_nodes
        \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]
        \only<1>{
            \node[ssnode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[ssnode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[ssnode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[ssnode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[ssnode,on chain] (c5) [label=above: $c_{5}$] {};
        }
        \only<2-3>{
            \node[oknode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[oknode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[nonode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[nonode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[oknode,on chain] (c5) [label=above: $c_{5}$] {};
        }
        \only<4->{
            \node[oknode,on chain] (c1) [label=above: $c_{1}$] {};
            \node[oknode,on chain] (c2) [label=above: $c_{2}$] {};
            \node[oknode,on chain] (c3) [label=above: $c_{3}$] {};
            \node[oknode,on chain] (c4) [label=above: $c_{4}$] {};
            \node[oknode,on chain] (c5) [label=above: $c_{5}$] {};
        }
        \end{scope}
         %% the var_nodes

        \begin{scope}[yshift=-2cm, start chain=going right,node distance=7mm]

            \only<1-2> {

                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {};
                \node[onesnode,on chain] (v8) [label=below: $v_{8}$] {};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {};
            }
            \only<3> {
                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {0};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {1};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {1};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {0};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {1};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {1};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {0};
                \node[onesnode,on chain] (v8) [label=below: $v_{8}$] {2};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {1};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {1};
            }
            \only<4> {
                \node[zerosnode,on chain] (v1) [label=below: $v_{1}$] {};
                \node[onesnode,on chain] (v2) [label=below: $v_{2}$] {};
                \node[onesnode,on chain] (v3) [label=below: $v_{3}$] {};
                \node[zerosnode,on chain] (v4) [label=below: $v_{4}$] {};
                \node[zerosnode,on chain] (v5) [label=below: $v_{5}$] {};
                \node[zerosnode,on chain] (v6) [label=below: $v_{6}$] {};
                \node[zerosnode,on chain] (v7) [label=below: $v_{7}$] {};
                \node[zerosnode,on chain] (v8) [label=below: $v_{8}$] {};
                \node[onesnode,on chain] (v9) [label=below: $v_{9}$] {};
                \node[onesnode,on chain] (v10) [label=below: $v_{10}$] {};
            }

        \end{scope}
         %
         %
         \draw (c1) -- (v1);
         \draw (c1) -- (v2);
         \draw (c1) -- (v3);
         \draw (c1) -- (v4);
         \draw (c2) -- (v1);
         \draw (c2) -- (v5);
         \draw (c2) -- (v6);
         \draw (c2) -- (v7);
         \draw (c3) -- (v2);
         \draw (c3) -- (v5);
         \draw (c3) -- (v8);
         \draw (c3) -- (v9);
         \draw (c4) -- (v3);
         \draw (c4) -- (v6);
         \draw (c4) -- (v8);
         \draw (c4) -- (v10);
         \draw (c5) -- (v4);
         \draw (c5) -- (v7);
         \draw (c5) -- (v9);
         \draw (c5) -- (v10);
       \end{tikzpicture}
       \caption{Funcionamento do algoritmo de \emph{bit-flipping}.}
    \label{fig:exemplo_bf}
    \end{figure}
\end{frame}

\begin{frame}[fragile]{Algoritmo de \emph{bit-flipping}}

    \begin{algorithm}[H]
      \Entrada{$H, y, \texttt{max\_it} $}
      \Saida{Decodificação de $y$, ou $\perp$ se exceder número de iterações}
      \Inicio{
        \texttt{it} $\gets$ 0 \\
        \Enqto{$ yH^T \neq 0 $ e \emph{\texttt{it}} < \emph{\texttt{max\_it}}}{
          \Para{cada $j = 1, 2, \ldots, n$}{
            $ f_j \gets $ Número de vizinhos de $v_j$ insatisfeitos \\
          }
          $\texttt{max\_upc} \gets \max \left\{ f_j \right\} $ \\
          \Para{cada $j = 1, 2, \ldots, n$}{
            \Se{$f_j \geq \texttt{\emph{max\_upc}} - \delta $}{
              $y_j \gets \bar{y_j}$
            }
          }
        }
        \Se{$yH^T = 0$}{
          \Retorna{$y$}
        }
        \Senao{
          \Retorna{$\perp$}
        }
      }
      \caption{Algoritmo de \emph{bit-flipping}}
    \end{algorithm}
    \label{alg:rafael_bit_flipping}
\end{frame}



\begin{frame}[fragile]{Decodificação por Decisões Abruptas e Suaves}

    \begin{figure}[htpb]
      \includegraphics[scale = 0.83] {figuras/hard.png}
      \label{fig:decod_dura}

      \includegraphics[scale = 0.83]{figuras/soft.png}
      \label{fig:decod_suave}
    \end{figure}

\end{frame}


\begin{frame}[fragile]{Códigos LDPC no esquema de McEliece}

    Uso no esquema de McEliece
    \begin{itemize}
        \item Códigos LDPC são ótimos códigos corretores de erros
        \item Porém são inseguros pois é possível recuperar a matriz esparsa
    \end{itemize}

    Ideia de Misoczki \cite{misoczki2013mdpc}
    \begin{itemize}
        \item Usar códigos LDPC com matriz ligeiramente mais densa
        \item Código fica mais forte contra ataques
        \item Ainda é possível usar algoritmos de decodificação para LDPC
    \end{itemize}
\end{frame}


\begin{frame}[fragile]{Códigos QC-MDPC}
    \begin{alertblock}{Definição}
        \textit{
        Um \textbf{código $(n, r, w)$-MDPC} é um código linear de comprimento $n$, e codimensão
        $r$, que admite uma matriz de verificação de paridade $H$ cujas linhas têm mesmos
        pesos iguais a $w = \mathcal{O} \left( \sqrt{n \log n} \right)$.
        } \cite{misoczki2013mdpc}
    \end{alertblock}


    O problema é que a matriz geradora pode ser densa

\end{frame}

\begin{frame}[fragile]{Códigos QC-MDPC}

    Usar códigos \textbf{quase cíclicos}!
    \begin{itemize}


        \item Matriz de paridade composta de blocos cíclicos

        \item Matriz geradora é também de blocos cíclicos

        \item Matrizes cíclicas são isomorfas a $\mathbb{F}_2[x] $ módulo $x^r - 1$

        \item Matriz geradora pode ser sistemática com conversão IND-CCA2

        \item Matrizes são descritas pela \textbf{primeira linha e número de blocos}
    \end{itemize}


    \begin{alertblock}{Definição}
        Quando $H$ é quase cíclica, um código MDPC é dito um \textbf{código $(n, r, w)$-QC-MDPC}.
        \cite{misoczki2013mdpc}
    \end{alertblock}

\end{frame}

\begin{frame}[fragile]{Matriz de paridade de um código QC-MDPC}
    \begin{figure}[htpb]
      \includegraphics[width=10cm] {figuras/qcmdpc_checkmat.png}
      \label{fig:qcmdpc}
      \caption{Matriz de paridade de código QC-MDPC com dois blocos e $w = 6$.}
    \end{figure}
\end{frame}

\begin{frame}[fragile]{Matriz geradora de um código QC-MDPC}
    Tem forma sistemática
    \[
        G = (\quad I \quad | \quad (H_1^{-1} H_0)^{T})
    \]
    \begin{figure}[htpb]
      \includegraphics[width=10cm] {figuras/qcmdpc_genmat.png}
      \caption{Matriz geradora de código QC-MDPC com dois blocos.}
      \label{fig:qcmdpc_gen}
    \end{figure}
\end{frame}


\begin{frame}[fragile]{QC-MDPC McEliece}

    Descrição do esquema com códigos QC-MDPC
    \begin{itemize}
        \item Chave pública é
            \begin{itemize}
                \item $g$ a primeira linha do segundo bloco da matriz $G$ e
                \item $t$ número de erros que o código corrige com alta probabilidade
            \end{itemize}

        \item Chave privada é a primeira linha esparsa

        \item Segurança baseada na dificuldade de encontrar palavras de baixo peso

        \item Dispensa o uso das matrizes embaralhadoras $S$ e $P$!

        \item Encriptação idêntica à do McEliece original

        \item Decriptação usa algoritmo de \emph{bit-flipping}

        \item Se o algoritmo falhar, peça reenvio de mensagem
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Parâmetros sugeridos para QC-MDPC}

    Baseado nos melhores ataques de decodificação
    \begin{table}[H]
    \centering
    \caption{Parâmetros sugeridos para cada nível de segurança.\cite{misoczki2013mdpc}}
    \label{tab:param_sugerido}
    \begin{tabular}{@{}ccccccc@{}}
    \toprule
    Segurança & $n_0$ & $n$   & $r$   & $w$ & $t$ & \begin{tabular}[c]{@{}c@{}}Tamanho da chave\\ (Bytes)\end{tabular} \\ \midrule
    80        & 2     & 9602  & 4801  & 90  & 84  & 601             \\
    128       & 2     & 19714 & 9857  & 142 & 134 & 1233             \\
    256       & 2     & 65542 & 32771 & 274 & 264 & 4097            \\ \bottomrule
    \end{tabular}
    \end{table}

\end{frame}








% \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}
%
%
