%-*- root: paper.tex -*-

\section{Rise and fall of the QC-MDPC McEliece}



\subsection{Definition}
In 2013, a new variant of the McEliece scheme was proposed by Misoczki et
al.~\cite{misoczki2013mdpc}. This variant
uses quasi-cyclic codes with moderate density parity check matrices, in contrast with the low density ones of Gallager's codes~\cite{gallager1962low}.
The idea is to
increase the density of the parity check matrix to make the code stronger against attacks based on the search for low weight codewords~\cite{shokrollahi2000using}. But keeping a sufficiently low density so that efficient LDPC decoders can still be used.

We first define the QC-MDPC codes

\begin{definition}[QC-MDPC code~\cite{misoczki2013mdpc}]
    An \emph{$(n, r, w)$-QC-MDPC} code is a
    quasi-cyclic linear code of length $n$,
    co-dimension $r$, and that admits a sparse
    parity check matrix $\mat{H}$ with row weights
    $w = \mathcal{O} \left( \sqrt{n \log n} \right)$, and formed by
    $n_0 = n/r$ cyclic blocks.
\end{definition}

The suggested parameters for the QC-MDPC McEliece make for extremely small keys,
when compared with the key size of hundreds of megabytes for the original McEliece scheme~\cite{bernstein2013mcbits}.
Some of the parameters are shown in Table~\ref{tab:qc_mdpc_params}.


\begin{table}[h]
\centering
\caption{Suggested QC-MDPC parameters for some security levels.}
\label{tab:qc_mdpc_params}
\begin{tabular}{@{}ccccccc@{}}
\toprule
Security  & $n_0$ & $n$   & $r$   & $w$ & $t$ & Key size in 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}

Until the end of 2016, the QC-MDPC McEliece was considered one of the most promising candidates for efficient code based
cryptography. The lack of algebraic structure in the code, and the apparently strong security reduction of the scheme,
suggested that it would be hard to compromise the security of the QC-MDPC codes. One of the main initiatives for post-quatum cryptography, European PQCRYPTO, considered the QC-MDPC McEliece as under analysis for long-term secure communication in the document~\cite{augot16initial}.


After three years without suffering major threats, Guo, Johansson, and Stankovski~\cite{guo2016key} present a dangerous
attack against the QC-MDPC scheme. It is a key recovery attack, using the reactions of,



\subsubsection{Key generation.}

We want to generate a random $(n, r, w)$-QC-MDPC.  it amounts to pick a random
vector $\vec{h} = \vec{h_0} \| \vec{h_1} $ of length $n/$ and weight $w$, such that the cyclic matrix $r$ columns
generate an invertible cyclic . Assim, usa-se esse vetor $h$ como gerador
da matriz quase cíclica $H$, de verificação de paridade. E claro que a matriz
geradora poderá ser derivada de $H$ a partir da 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, são computacionalmente eficientes.


\[
  H = \left[
    \, H_0 \, | \, H_1 \, | \, \ldots \, | \, H_{n_0 - 1} \,
  \right].
\]


\begin{equation}
\label{eq:mdpc_matriz_geradora}
  G = \left[
    % \begin{matrix}
      \qquad I \qquad
    % \end{matrix}
    \, \middle\vert \,
    \begin{matrix}
      {\left( H_{n_0 - 1}^{-1} \cdot H_0 \right)}^T \, \\ \addlinespace
      {\left( H_{n_0 - 1}^{-1} \cdot H_1 \right)}^T \, \\ \addlinespace
      \vdots \, \\ \addlinespace
      {\left( H_{n_0 - 1}^{-1} \cdot H_{n_0 - 2}\right)}^T  \,

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


\subsubsection{Encryption.}

The encryption is extremely efficient. Let the vector $\vec{m}$ of
$\Fb^{(n - r)}$ be the message to be encrypted. First we encode the word
obtaining $\vec{\hat{c}} = \vec{m} \mat{G}$. Then we add a random vector $\vec{e}$ of
weight $t$ to $\vec{\hat{c}}$ to get the ciphertext $\vec{c} = \vec{\hat{c}} \oplus \vec{e}$.

\subsubsection{Decryption.}

Since the ciphertext is just a corrupted codeword, decryption $\vec{c}$
is equivalent to correct the errors from $\vec{c}$.
This is achieved with iterative decoders,
which can be of two types: hard and soft decision based.
Soft decision based decoders have better error correction
capability, but are less efficient. Since we don't need to correct a lot of
errors, only enough to make the scheme secure, it is usual to decode QCMDPC codes
with hard decision based decoders. These decoders are called \emph{bit-flipping
decoders}, and some of its variants were studied by Maurich et. al~\cite{maurich2015implementing} in terms of
performance and error correction capability.


\subsection{Reaction attack}

The reaction attack is based on the observation that the probability of a failure occur when decoding a vector $c = m \oplus e$ is lower when the spectrum of the blocks of $\vec{h}$ is similar to the spectrum of the error $e$. When a decoding failure occurs, the receiver asks the sender to resend the message. Therefore the
attacker knows when a failure occurs, and by sending decoding challenges to the
secret key holder, she can get some structural information about the key.

The attack has two parts. In the first, the attacker collects information about the key using decoding challenges. In the second, the attacker tries to reconstruct the key using the information previously collected.





\subsubsection{Spectrum recovery.}

This is the part where the reactions of the receiver are exploited.
For attacking Alice, the idea is to send her valid ciphertexts, and record
when she could not decode the challenge. Since we generated the ciphertext,
we know the error $\vec{e}$ which was summed to the codeword, and can calculate
$\sigma(\vec{e})$.


\begin{algorithm}
  \KwData{$n, r, w, t$ parameters of the QC-MDPC code \\
    \myinput{$\mathcal{D}$ the decoder reaction oracle}
  }
  \KwResult{$\vec{a}_0, \vec{b}_0, \vec{a}_1, \vec{b}_1$}
  \Begin{
    $\vec{a} \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\
    $\vec{b} \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\

    \For{each possible decoding trial $i = 1, 2, \ldots, M$} {
      $\vec{c} \gets $ a random encrypted with error $ \vec{e} = \vec{\vec{e}_0 \| \vec{e}_1}$ \\

      $v \gets \mathcal{D}(\vec{c})$ \\

      \For{each distance $d$ in $\sigma(\vec{e}_0)$} {
        $\vec{a}[d] \gets \vec{a} + v$ \\
        $\vec{b}[d] \gets \vec{a} + 1$ \\
      }
    }

  \Return{$\vec{a}, \vec{b}$}
  }
  \caption{Estimating the probabilities of error for distances in
    $\sigma(\hz)$ as presented by Guo et al.~\cite{guo2016key}}
\end{algorithm}
\label{alg:calc_espectro}



\subsubsection{Key reconstruction}

The original proposed algorithm for key reconstruction is a straight-forward
depth-first search. Let $\sigma(\hz)$ be the given the spectrum of \hz. The algorithm works as follows.

% \begin{enumerate}
%   \item $\hz \gets \{ 1 \} $.
%   \item For each $b = 2, \ldots, r$, do
%   \begin{enumerate}
%       \item[] If $\dist_r (j, b) \in \hz$ for all $j$ currently in \hz:
%       \begin{enumerate}
%         \item[] $\hz \gets \hz \cup b$
%         R

%       \end{enumerate}

%       \item[] $\hz$
%   \item $\hz \gets \{ 0, \min(\hz) \} $.
%   \item $\hz \gets \{ 0, \min(\hz) \} $.
%   \end{enumerate}
% \end{enumerate}


The main argument for assuring the efficiency of the algorithm is that
the number of possible valid paths decrease exponentially as we increase the
depth of the search.

\[
  \WF(\textsc{Alg}_1) = \left( \frac{r}{2} \right) ^\phi \alpha^{\phi(\phi + 3)/2}
\]



