%% ------------------------------------------------------------------------- %%
%!TEX root = diss.tex

\chapter{QC-MDPC McEliece}
\label{cap:mdpc}


Em 2013, uma nova variante do Esquema de McEliece foi proposta por
Misoczki et al.~\cite{misoczki2013mdpc}. Esta variante usa códigos QC-MDPC, que são
códigos lineares binários que admitem uma matriz de paridade quase cíclica e moderadamente
esparsa, em contraste com as de baixa densidade dos códigos LDPC, do inglês
\emph{Low Density Parity Check}, de Gallager~\cite{gallager1962low}.

Uma grande diferença entre códigos MDPC e a maioria dos outros códigos
sugeridos para serem usados com o esquema de McEliece~\cite{gaborit2005shorter,berger2009reducing,misoczki2009compact}, é que como os códigos LDPC,
os códigos MDPC não têm estrutura algébrica.
Isso dá certa confiança de que os esquemas usando esses códigos resistam a ataques
de criptanálise algébrica~\cite{faugere2010algebraic,faugere2016structural}.

Apesar serem similares a códigos aleatórios em sua construção, códigos LDPC
não são adequados para o uso no esquema de McEliece~\cite{shokrollahi2000using}. Suas 
matrizes de paridade têm peso muito baixo, o que permite que algoritmos que buscam palavras
de baixo peso recuperem linhas das matrizes de paridade sem muita 
dificuldade~\cite{shokrollahi2000using}.
A ideia dos códigos MDPC é fortalecer o esquema de McEliece com códigos
LDPC,
aumentando a densidade da matriz de paridade de forma que a busca por linhas esparsas da matriz de paridade seja impraticável, obtendo códigos chamados MDPC. Como as chaves públicas do MDPC
ainda são muito grandes, Misoczki et al. mostraram como introduzir certa ciclicidade nas matrizes
para obter chaves compactas comparáveis às do RSA, mas de modo que preservasse a segurança 
do esquema.

Uma implementação eficiente do QC-MDPC McEliece pode ser vista no trabalho
de Maurich et al.~\cite{maurich2015implementing}.
Há duas variantes do esquema QC-MDPC McEliece:
QC-MDPC McEliece suave~\cite{baldi2016soft}, e QC-MDPC McEliece $p$-ário~\cite{guo2016p}.
O esquema QC-MDPC McEliece suave é muito similar ao QC-MDPC McEliece, porém usa
decodificadores baseados em decisões suaves, e os erros inseridos não são binários, mas
números de ponto flutuante. Isso permite inserir informação sobre a mensagem nos erros, 
de modo a obter chaves ainda menores que o QC-MDPC McEliece. Infelizmente,
o esquema pode sofrer ataques por decodificação de mensagens, e também 
é possível atacar o esquema por um ataque de reação similar ao de Guo et al.~\cite{guo2016key} para
o esquema de McEliece~\cite{fabvsivc2017reaction}. 
O esquema QC-MDPC McEliece $p$-ário\footnote{O QC-MDPC $p$-ário foi proposto como alternativa
ao QC-MDPC McEliece por dois dos autores responsáveis pelo ataque de reação contra este esquema.}
usa códigos QC-MDPC em que as entradas não são binárias, 
mas pertencem ao corpo finito de $p$ elementos. Os autores afirmam que é possível baixar significativamente
a probabilidade de falha de decodificação ao usar códigos $p$-ários, o que pode fazer o esquema resistir ao ataque de reação de Guo et al.. 

\section{Códigos QC-MDPC}

\begin{definition}[Códigos MDPC~\cite{misoczki2013mdpc}]
  Um código $[n, r, w]$-MDPC é um código linear de comprimento $n$, e
  codimensão\footnote{A codimensão de um
  código é a dimensão de seu espaço dual, ou equivalentemente o número de linhas
  de uma sua matriz de paridade.}
  $r$, que admite uma matriz de verificação de paridade $\mat{H}$ cujas linhas têm mesmos
  pesos iguais a $w = \mathcal{O} \left( \sqrt{n \log n} \right)$.
\end{definition}


Para conseguir chaves compactas usando códigos MDPC, Misoczki et al. sugerem que
seja usada uma família de códigos MDPC cujas matrizes de paridade são quase-cíclicas.
Uma matriz é quase cíclica se é uma matriz de blocos, com cada um de seus blocos sendo uma
matriz cíclica. Uma matriz cíclica é uma matriz tal que cada uma de suas linhas é uma
rotação circular de uma posição à direita da linha superior. Dessa forma, matrizes
cíclicas podem ser completamente descritas apenas por sua primeira linha.
Como exemplo, as seguinte matrizes $\mat{C}_0$ e $\mat{C}_1$ são cíclicas, enquanto 
a matriz $\vec{C}$ é quase cíclica
\[
  \mat{C}_0 = \left[
    \begin{matrix}
    1&0&0&1 \\
    1&1&0&0 \\
    0&1&1&0 \\ 
    0&0&1&1 \\ 
    \end{matrix}
  \right], \,
  \mat{C}_1 = \left[
    \begin{matrix}
    0&1&0&1 \\
    1&0&1&0 \\
    0&1&0&1 \\ 
    1&0&1&0 \\ 
    \end{matrix}
  \right], \,
  \mat{C} = [\mat{C}_0 | \mat{C}_1].
\]


\begin{definition}[Códigos QC-MDPC~\cite{misoczki2013mdpc}]
  Um {código $[n, r, w]$-QC-MDPC} é um código
  $[n, r, w]$-MDPC que admite uma matriz de verificação de paridade
  quase cíclica $\mat{H}$. Para isso, $n$ deve ser um múltiplo de $r$,
  e o número de blocos cíclicos de $\mat{H}$ é denotado por $n_0 = n/r$.
\end{definition}


Por definição, a matriz de paridade de um código $[n, r, w]$-QC-MDPC
é da forma

\[
  \mat{H} = \left[
    \, \mat{H}_0 \, | \, \mat{H}_1 \, | \, \ldots \, | \, \mat{H}_{n_0 - 1} \,
  \right],
\]
onde cada matriz $\mat{H}_i$ é cíclica. Então, sabendo-se a codimensão $r$, a matriz
$\mat{H}$ é completamente descrita pela sua primeira
linha. Supondo-se que $\mat{H}_{n_0 - 1}$ é inversível, o que será garantido pelo algoritmo
de construção de códigos MDPC, pode-se
verificar, comprovando que $\mat{G} \mat{H}^T = \mat{0}$, que uma possível matriz geradora 
$\mat{G}$ do código de matriz de paridade $\mat{H}$ é
\begin{equation}
\label{eq:mdpc_matriz_geradora}
  \mat{G} = \left[
    % \begin{matrix}
      \qquad \mat{I} \qquad
    % \end{matrix}
    \, \middle\vert \,
    \begin{matrix}
      {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_0 \right)}^T \, \\ \addlinespace
      {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_1 \right)}^T \, \\ \addlinespace
      \vdots \, \\ \addlinespace
      {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_{n_0 - 2}\right)}^T  \,

    \end{matrix}
  \right].
\end{equation}

Usar a matriz geradora pública em forma sistemática, como está a $\mat{G}$ apresentada, 
não permite transmissão segura de mensagens não aleatórias. Mas usando conversões
de segurança como as de Kobara e Imai~\cite{kobara2001semantically}, não 
há nenhuma perda de segurança em usar a matriz nessa forma. 
Então pelo resto deste texto,
supomos que a matriz $\mat{G}$ é dada na forma sistemática. Para construí-la
basta que seja dado o seu segundo bloco.
O que permite a representação compacta da chave pública do QC-MDPC McEliece é o fato
de que cada bloco $\mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_i$ da matriz $\mat{G}$ é 
cíclico~\cite{misoczki2013mdpc}, e pode ser totalmente descrito por sua primeira linha.

\paragraph{Construção do código}
\label{sec:construcao_mdpc}
\mbox{}

Para construir um código $[n, r, w]$-QC-MDPC aleatório, onde $n$ é um múltiplo de $r$,
escolha aleatoriamente um
vetor binário $\vec{h}$, de comprimento $n$ e peso $w$. Divida $\vec{h}$ em
$n_0 = n/r$ partes $\vec{h}_0, \ldots, \vec{h}_{n_0 - 1}$, todas de comprimento $r$,
de forma que $\vec{h} = [\vec{h}_0, \vec{h}_1, \ldots, \vec{h}_{n_0 - 1}]$.
Construa a matriz de paridade $\mat{H}$ na forma
\[
  \mat{H} = \left[
    \, \mat{H}_0 \, | \, \mat{H}_1 \, | \, \ldots \, | \, \mat{H}_{n_0 - 1} \,
  \right],
\]
onde cada matriz $\mat{H}_i$ é a matriz cíclica que tem como primeira linha o 
vetor $\vec{h}_i$. Se o bloco $\mat{H}_{n_0 - 1}$ não for inversível, o que ocorre
com baixa probabilidade~\cite{maurich2015implementing}, escolha um 
novo vetor $\vec{h}$ e recomece o procedimento. Agora a matriz geradora pode ser construída
usando a equação~\ref{eq:mdpc_matriz_geradora}.

Um modo simples de agilizar a construção de códigos QC-MDPC, é observar que
a álgebra das matrizes cíclicas $r \times r$ é isomorfa à dos polinômios
em $ \mathbb{F}_2[x] $ módulo $x^r - 1$. Dessa forma, as multiplicações e inversões de
matrizes cíclicas podem ser computadas mais eficientemente~\cite{misoczki2013mdpc}.

Tipicamente, as matrizes de paridade dos códigos usados no QC-MDPC McEliece 
que oferecem menores tamanhos de chave têm
apenas dois blocos. Como exemplo, considere as matrizes de paridade e geradora de um código
$(40, 20, 6)$-QC-MDPC mostradas, respectivamente, à esquerda e à direita na
Figura~\ref{fig:check_gen_matrices_qcmdpc}. Nesta figura, retângulos mais escuros representam
1's, enquanto os mais claros representam 0's. Note que a matriz geradora não é esparsa.

\begin{figure}[H]
    \includegraphics[width=.45\textwidth]{figuras/mdpc/check_mat.pdf}
    \includegraphics[width=.45\textwidth]{figuras/mdpc/gen_matrix.pdf}
    \caption{Matrizes de paridade e geradora, respectivamente à esquerda e à direita,
    de um código $(40, 20, 6)$-QC-MDPC}
    \label{fig:check_gen_matrices_qcmdpc}
\end{figure}


\paragraph{Codificação}
\mbox{}

A codificação de um vetor $\vec{m}$ é simplesmente o vetor $\vec{c}$, produto da
multiplicação $\vec{c} = \vec{m}\mat{G}$. Como $\mat{G}$ em geral está na forma sistemática
$\mat{G} = [\, \mat{I} \mid \mat{P} \,]$, para alguma matriz $\mat{P}$,
a codificação é ligeiramente simplificada para
$\vec{c} = [\vec{m} | \vec{m}\mat{P} ]$.

\paragraph{Decodificação}
\mbox{}


Por serem baseados nos códigos LDPC, é comum decodificar códigos MDPC com
algoritmos daqueles códigos. Mas como as matrizes de verificação de paridade
de códigos MDPC são mais densas, é de se esperar que os algoritmos de decodificação
para códigos LDPC não sejam tão eficientes. Isso motivou algumas melhorias
tanto para diminuir o número de iterações para a decodificação, quanto
para diminuir a probabilidade de falha.

Há duas classes de decodificadores para códigos LDPC: 
os por decisões abruptas, e os por decisões suaves.
Com algoritmos de decisão abrupta, a decodificação de uma mensagem transmitida é feita através de
sucessivas inversões de seus bits, até possivelmente chegar à mensagem original.
Por isso, estes algoritmos são chamados de \emph{bit-flipping}.
Os decodificadores por decisão suave usam algoritmos de 
propagação de crença~\cite{mackay1999good}
sobre a probabilidade de cada bit da mensagem transmitida ser 1 ou não.

Ambas as classes de algoritmos podem falhar com certa probabilidade, sendo que tipicamente
algoritmos de \emph{bit-flipping} têm taxas de falha mais altas do que algoritmos
de propagação de crença~\cite{mackay1999good}.
Apesar de serem capazes de corrigir mais erros, os decodificadores por decisões
suaves são significativamente mais lentos do que os de \emph{bit-flipping}.
Por isso, e por terem implementação e análise mais fáceis, os decodificadores por decisão
abrupta são mais usados nas implementações~\cite{maurich2015implementing,heyse2013smaller}. 
Em particular, Misoczki et al. sugerem o uso do
decodificador por \emph{bit-flipping} descrito pelo Algoritmo~\ref{alg:rafael_bit_flipping}.
Para uma análise experimental detalhada de variantes do algoritmo de \emph{bit-flipping}
aplicados a códigos QC-MDPC, veja os estudo de Hayse et al.~\cite{heyse2013smaller},
e Maurich et al.~\cite{maurich2015implementing}.


\begin{algorithm}[h]
  \Entrada{$\mat{H}$ matriz de paridade esparsa $r \times n$ de um código LDPC\\
    \myinput{$\vec{y}$ uma palavra transmitida a ser decodificada}
    \myinput{\texttt{max\_it} o número máximo de iterações}
  }
  \Saida{A decodificação estimada de $\vec{y}$, ou $\perp$ se o número máximo de
         iterações for excedido}
  \Inicio{
    \var{it} $\gets$ 0 \\
    \Enqto{$ \vec{y}\mat{H}^T \neq \vec{0} $ e $\var{it} < \var{max\_it}$}{
      \Para{cada $j = 1, 2, \ldots, n$}{
        $ f_j \gets $ Número de vizinhos de $v_j$ insatisfeitos
      }
      $\var{max\_upc} \gets \max \left\{ f_j \right\} $ \\
      \Para{cada $j = 1, 2, \ldots, n$}{
        \Se{$f_j \geq \var{max\_upc} - \delta$}{
          $y_j \gets \bar{y_j}$
        }
      }
      $\var{it} \gets \var{it} + 1$
    }
    \Se{$\var{it} \geq \var{max\_it}$}{
      \Retorna{$\perp$}
    }
    \Senao{
      \Retorna{$\vec{y}$}
    }
  }
  \caption{Algoritmo de \emph{bit-flipping} sugerido Misockzi et al.~\cite{misoczki2013mdpc}}
  \label{alg:rafael_bit_flipping}
\end{algorithm}

Note como o Algoritmo~\ref{alg:rafael_bit_flipping} é similar ao
Algoritmo~\ref{alg:huff_bit_flipping} analisado na Seção~\ref{cap:prelim_ldpc}.
A única diferença é que agora é usado um $\delta$ que aumenta o número de bits que são
invertidos a cada iteração, podendo fazer o algoritmo terminar num menor número de passos.
O valor ótimo de delta deve ser estimado através de simulações.

\section{QC-MDPC McEliece}

\begin{definition}[Esquema de McEliece]

    O \emph{Esquema QC-MDPC McEliece} é uma tripla de algoritmos
    $\left( \alg{GeraChaves}, \alg{Encripta}, \alg{Decripta} \right)$, em que cada algoritmo é
    definido como os seguintes.

    \alg{GeraChaves} é o algoritmo para geração de um par de chaves.
    Dado um nível de segurança $\lambda$, siga os seguintes passos.
    \begin{enumerate}
        \item Escolha os parâmetros $n, r, w,$ e $t$ 
            de uma família $\mathcal{F}$ de códigos
            de QC-MDPC que suporta um nível de segurança $\lambda$ usando, por exemplo,
            a Tabela~\ref{tab:mdpc_param_sugerido}.
        \item Tome $\mat{H}$ uma matriz de paridade de um código escolhido
          aleatoriamente da família $\mathcal{F}$.
        \item Calcule $\mat{G}$ sistemática tal que $\mat{G}\mat{H}^T = \mat{0}$ 
        usando a equação~\ref{eq:mdpc_matriz_geradora}.
        \item Construa $\vec{h}_i$, e $\vec{g}_j$, que são
        as primeiras linhas de cada bloco cíclico de $\mat{H}$ e $\mat{G}$, respectivamente. Faça
        \[
            \vec{h} = [ \vec{h}_0 | \vec{h}_1 | \ldots | \vec{h}_{n_0 - 1}], 
            \qquad \text{ e } \qquad \vec{g} = [\vec{g}_0 | \vec{g}_1 | \ldots |
              \vec{g}_{n_0 - 2}].
        \]
        \item Devolva o par de chaves secreta e pública, dados respectivamente por
        \[
        \sk = \vec{h}, \quad \text{ e } \quad \pk = \vec{g}.
        \]
    \end{enumerate}


    \alg{Encripta} é o algoritmo de encriptação.
    Dada uma mensagem $\vec{m}$, e a chave pública do destinatário \pk, siga os seguintes passos.
    \begin{enumerate}
        \item Tome o vetor $\vec{g}$ de \pk que permite reconstruir a matriz geradora pública.
        \item Construa a matriz geradora sistemática $\mat{G}$ usando as primeira linhas
                de cada bloco cíclico $\vec{g}$.
        \item Tome um $\vec{e}$, um vetor de peso $t$ aleatoriamente escolhido de $\Fb^n$.
        \item Devolva o vetor $\vec{c} \gets \vec{m}\mat{G} + \vec{e}$.
    \end{enumerate}

    \alg{Decripta} é o algoritmo de decriptação.
    Dado um texto encriptado $\vec{c}$ e a chave secreta do destinatário \sk, siga os seguintes passos.
    \begin{enumerate}
        \item Construa a matriz de paridade $\mat{H}$ usando a primeira linha $h$ e
                de \sk e o tamanho de cada bloco $r$.
        \item Use o algoritmo de \emph{bit-flipping} com a matriz esparsa $\mat{H}$
            para decodificar $ \vec{c} $ e obter $\vec{m}$.
        \item Se o algoritmo falhar, peça para o remetente reenviar a mensagem,
            que com alta probabilidade será encriptada com um vetor de erro que
            o decodificador pode corrigir.
    \end{enumerate}

\end{definition}

\section{Segurança do esquema}


Para códigos QC-MDPC, não são necessárias as matrizes embaralhadoras
$\mat{S}$ e $\mat{P}$. Isso pois, com conversões IND-CCA2, não há vazamentos sobre informações
da mensagem mesmo usando $\mat{G}$ sistemática, e é supostamente difícil de se
obter $\mat{H}$ a partir de $\mat{G}$.
Os parâmetros sugeridos por Misoczki et al.~\cite{misoczki2013mdpc} para alguns níveis de segurança são descritos na Tabela~\ref{tab:mdpc_param_sugerido}.

\begin{table}[H]
\centering
\caption{Parâmetros sugeridos para cada nível de segurança~\cite{misoczki2013mdpc}}
\label{tab:mdpc_param_sugerido}
\begin{tabular}{@{}ccccccc@{}}
\toprule
Segurança & $n_0$ & $n$   & $r$   & $w$ & $t$ & Tamanho da Chave em bits \\ \midrule
80        & 2     & 9602  & 4801  & 90  & 84  & 4801             \\
128       & 2     & 19714 & 9857  & 142 & 134 & 9857             \\
256       & 2     & 65542 & 32771 & 274 & 264 & 32771            \\ \bottomrule
\end{tabular}
\end{table}


A redução de segurança do QC-MDPC McEliece se baseia na hipótese de que é difícil
distinguir matrizes geradoras de códigos QC-MDPC de matrizes geradoras de 
códigos quase cíclicos aleatórios. Este é um problema
similar ao de encontrar palavras de pesos baixos em códigos lineares. Sob essa
hipótese razoável, prova-se que quebrar o esquema QC-MDPC não é mais fácil do que
resolver o problema da decodificação por síndrome, que é conhecidamente \cNP-difícil,
e conjecturado tipicamente difícil. 
Porém essa boa redução de segurança
não leva em conta o fato de o algoritmo de decriptação falhar com certa probabilidade.
Isto não seria um problema se o algoritmo falhasse com probabilidade independente
da similaridade entre o erro usado na encriptação e a chave secreta. Infelizmente, 
este não é o caso, e o QC-MDPC pode ser atacado usando as reações do decriptador,
isto é, se foi ou não possível decriptar a mensagem, para
um grande número de mensagens encriptadas~\cite{guo2016key}.
