%!TEX root = paper.tex

\section{The QC-MDPC McEliece}
\label{sec:mdpc}

\subsection{The QC-MDPC McEliece}

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
Gallager's low density parity-check codes (LDPC)~\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.

\begin{definition}[QC-MDPC]
    An $(n, r, {w})$-QC-MDPC code is a
    quasi-cyclic linear code of length $n$,
    co-dimension $r$ which divides $n$, that has 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 parameters suggested by Misoczki et al.~\cite{misoczki2013mdpc} are shown in Table~\ref{tab:qc_mdpc_params}.
The suggested parameters for the QC-MDPC McEliece entail extremely small keys
when compared with the key size of hundreds of megabytes for the original McEliece
scheme~\cite{bernstein2013mcbits}.
% We
% only show the parameters where $n_0 = 2$ because they entail for smaller keys,
% and the reaction attack~\cite{guo2016key} is described for these parameters, even
% though it can be adapted for other numbers of cyclic blocks.

\begin{table}[ht]
\centering
\caption{Suggested QC-MDPC parameters for some security levels~\cite{misoczki2013mdpc}}
\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              \\
80        & 3     & 10779 & 3593  & 153 & 53  & 7186              \\
80&4&12316&3079&220&42&9237 \\ \midrule
128       & 2     & 19714 & 9857  & 142 & 134 & 9857              \\
128       & 3     & 22299 & 7433  & 243 & 85  & 14866             \\
128&4&27212&6803&340&68&20409 \\ \midrule
256       & 2     & 65542 & 32771 & 274 & 264 & 32771             \\
256       & 3     & 67593 & 22531 & 465 & 167 & 45062             \\
256&4&81932&20483&644&137&61449 \\ \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-quantum cryptography, the European PQCRYPTO, considered the QC-MDPC McEliece as a strong candidate for long-term secure communication~\cite{augot16initial}.

We now show the algorithms for key generation,
encryption, and decryption. The encryption and decryption algorithms can be
adapted to support CCA2 security, for example, using one of Kobara and Imai
conversions~\cite{kobara2001semantically}.

\subsubsection{Key generation}
\label{sec:mdpc_key_gen}

Suppose we want to generate keys for the QC-MDPC McEliece with the security level $\lambda$.
Let $n_0, n, r,$ and $w$ be parameters supporting this security level $\lambda$, which can
be taken from Table~\ref{tab:qc_mdpc_params}.

First generate a random QC-MDPC code by choosing at random a
vector $\vec{h}$ from $\Fb^n$, such that the weight of $\vec{h}$ is ${w}$.
Break $\vec{h}$ into $n_0 = n/r$ equal parts
$\vec{h} = [ \, \vec{h}_0 \, | \, \vec{h}_1 \, | \,
\ldots \, | \, \vec{h}_{n_0 - 1} \, ]$. Then build the parity-check matrix
$\mat{H}$ as

\[
  \mat{H} = \left[
    \, \mat{H}_0 \, | \, \mat{H}_1 \, | \, \ldots \, | \, \mat{H}_{n_0 - 1} \,
  \right],
\]
where each $\mat{H}_i$ is the cyclic matrix with $\vec{h}_i$ as its first row.
It is required that the block $\mat{H}_{n_0 - 1}$ is invertible. If it is not,
restart the key generation procedure by picking another $\vec{h}$ at random.

We now build the generator matrix as
\begin{equation}
\label{eq:mdpc_gen_matrix}
  \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}
\mbox{} % otherwise the matrix is rendered over the subsubsection title
and one can check that $\mat{G}\mat{H}^T = \vec{0}$ with a simple evaluation.
Since each $\mat{H}_i$ is cyclic, each product
$ \left( \mat{H}_{n_0 - 1}^{-1} \mat{H}_i \right)^T$ is also cyclic.


The secret key is the matrix $\mat{H}$ and the public key is the matrix $\mat{G}$.
Both of the matrices admit compact representation because of their cyclic blocks.


Note that if one attacker can recover the cyclic matrix $\mat{H}_{n_0 - 1}$, which is invertible
by construction, then she can recover all the other cyclic matrices $\mat{H}_{i}$ using simple
linear algebra. In fact, since each matrix $\mat{H}_i$ has high rank with high probability,
if an attacker can recover any cyclic matrix $\mat{H}_j$, she might be able to recover
$\mat{H}_{n_0 - 1}$ by finding its first line $\vec{h}_{n_0 - 1}$, which is a low weight
solution of the linear equation
\[
  \vec{h}_{n_0 - 1} \mat{B}_j = \mat{h}_j,
\]
where $\vec{h}_j$ is the first line of $\mat{H}_j$, and $\mat{B}_j = \mat{H}_{n_0 - 1}^{-1} \mat{H}_j $
is known.
As such, it is desirable that the hardness to recover each block be approximately the same.
This implies that the weights
of the vectors $\vec{h}_i$ must not differ too much, which is easily done by
fixing the weight of each block as $\hat{w} = w/n_0$.

\subsubsection{Encryption}

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

\subsubsection{Decryption}

Since the ciphertext is just a corrupted codeword, decrypting $\vec{c}$
is equivalent to correct the errors from $\vec{c}$.
This is achieved with iterative decoders~\cite{gallager1962low},
which can be of two types: based on either hard or soft decision.
Soft decision based decoders have better error correction
capability, but are less efficient. It is usual to decode QC-MDPC codes
with hard decision based decoders, because the main problem here is not
efficient communication, but secure communication. Therefore
one does not need to correct a lot of
errors, but only enough to make the scheme secure. 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 to occur when
decoding a vector $\vec{c} = \hat{\vec{c}} + \vec{e}$ is lower when the spectrums of the blocks of
$\vec{h}$ are similar to the corresponding spectrums of the blocks of the error $\vec{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 is done in two parts. In the first, the attacker collects information about the key
by sending challenge ciphertexts to the secret key holder Alice, and recording Alice's reactions
when she tries to decode these ciphertexts.
The first part is the only part where the attacker needs to interact with the
secret key holder.
In the second part, the attacker tries to reconstruct the key using the
information previously collected. These two parts are described next.

\subsubsection{Spectrum recovery}

This is the part where the reactions of the receiver are exploited. Let Alice
be the secret key holder who we want to attack.
The idea is to send Alice valid ciphertexts, and record
when she could not decode the challenge. Since the attacker generated all ciphertexts, then,
for each one of them, he knows the error
 $\vec{e} = [\, \vec{e}_0 \, | \, \vec{e}_1 \, ]$ that was added to the codeword,
and thus he can compute both $\sigma(\vec{e}_0)$ and $\sigma(\vec{e}_1)$.
Since each challenge ciphertext is valid and randomly generated, CCA2 conversions, such
as the ones by Kobara and Imai~\cite{kobara2001semantically},
do not protect the algorithm against this recovery procedure.

A slightly modified version of Guo's et al. spectrum recovery algorithm is given by
Algorithm~\ref{alg:spec_recovery}.
The spectrum recovery procedure by Guo et al. only
recovers the spectrum of $\ho$ because their reconstruction algorithm gains nothing
by also considering the spectrum of \hz. Guo et al. chose to recover $\ho$
because, from it, one can completely recover the secret key by using simple linear
algebra, as discussed in the end of Section~\ref{sec:mdpc_key_gen}.
In contrast, our reconstruction algorithm uses
information on both blocks of $\vec{h}$, therefore the presented spectrum recovery
algorithm simultaneously recovers information on the spectrums of both $\hz$ and $\ho$.
Further, simultaneously recovering both spectrums does not affect significantly
the complexity of the spectrum recovery algorithm because the cost of the decryption
dominates the costs involved in estimating the spectrums.

\begin{algorithm}[ht]
  \KwData{$n, r, w, t$ parameters of the QC-MDPC code \\
    \myinput{$\mathcal{D}$ target's decoder reaction oracle (1 for success, 0 for fail)}
    \myinput{$M$ number of decoding challenges}
  }
  \KwResult{$\vec{p}_0, \vec{p}_1$ estimated probabilities of error for distances in
  $\sigma(\hz)$ and $\sigma(\ho)$}
  \Begin{
    $\vec{a}_0,\vec{b}_0, \vec{a}_1, \vec{b}_1 \gets $
      zero-initialized arrays with $\lfloor r/2 \rfloor$ entries each \\

    \For{each decoding trial $i = 1, 2, \ldots, M$} {
      $\vec{c} \gets $ a random ciphertext encrypted with error
         $ \vec{e} = [ \, \vec{e}_0 \, | \, \vec{e}_1 \, ]$ of weight $t$\\

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

      \For{each distance $d$ in $\sigma(\vec{e}_0)$} {
        $\vec{a}_0[d] \gets \vec{a}_0[d] + v$ \\
        $\vec{b}_0[d] \gets \vec{b}_0[d] + 1$ \\
      }
      \For{each distance $d$ in $\sigma(\vec{e}_1)$}{
        $\vec{a}_1[d] \gets \vec{a}_1[d] + v$ \\
        $\vec{b}_1[d] \gets \vec{b}_1[d] + 1$ \\
      }
    }
    $\vec{p}_0, \vec{p}_1 \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\
    \For{each distance $d$ in $\{ 1, 2, \ldots, \lfloor r/2 \rfloor \}$ }{
      $\vec{p}_0[d] \gets \vec{a}_0[d]/\vec{b}_0[d]$ \\
      $\vec{p}_1[d] \gets \vec{a}_1[d]/\vec{b}_1[d]$ \\
    }
  \Return{$\vec{p}_0$ and $\vec{p}_1$}
  }
  \caption{Estimating the probabilities of error for distances in
    $\sigma(\hz)$ and $\sigma(\ho)$}
  \label{alg:spec_recovery}
\end{algorithm}



\begin{figure}[ht]
  \centering
  \includegraphics[scale=1]{figures/intro/200M_cca_dec_annotated.pdf}
  \caption{Histogram of failure rates for 200M decoding trials}
  \label{fig:hist_200M}

  \includegraphics[scale=1]{figures/intro/30M_cca_dec.pdf}
  \caption{Histogram of failure rates for 30M decoding trials}
  \label{fig:hist_30M}
\end{figure}


To study how large should be the number of decoding trials $M$ for a successful
attack, we introduce the concept of $d$-exclusion obtained by the spectrum recovery
algorithm. It is simply the maximum number $d$ of distances which we can consider outside
of the spectrum based only on the recovered vector of estimated
probabilities of failure. The formal definition is given next.

\begin{definition}
We say that the output $\vec{p}_0$ of the spectrum recovery algorithm obtains
a $d$-exclusion for the spectrum of a vector $\vec{h}_i$ if
there exists a number $p \in (0, 1)$ such that
\begin{enumerate}
  \item $\vec{p}_0[d] \geq p \text{ only if } d \notin \sigma(\vec{h}_i);$
  \item $\# \{ \vec{p}_0[d] \geq p \} = d.$
\end{enumerate}

When $ d = \lfloor r/2 \rfloor - |\sigma(\vec{h}_i)|$, that is, $d$ is the number of
distances outside the spectrum of $\vec{h}_i$, we say that $\vec{p}_0$
obtains total exclusion.

\end{definition}

One of the weaknesses of the reconstruction algorithm by Guo et al., which we discuss
in Section~\ref{sec:key_reconstruction}, is that its efficiency depends on an almost
total exclusion.
As such, the number of decoding challenges $M$ must be set so that it occurs.
Guo et al. empirically evaluated that, for 80 bits security parameters, total
exclusion usually occurs for values of
$M$ between 203 million and 356 million decoding challenges.
Figure~\ref{fig:hist_200M} illustrate a total exclusion, while
Figure~\ref{fig:hist_30M} shows the result of 30 million decoding challenges,
where it is not possible to clearly classify a distance as inside or outside the spectrum.


When total exclusion for \ho occurs, the authors suggest the use of some clustering
procedure
for gathering the distances inside $\sigma(\ho)$. Then $\sigma(\ho)$ is passed to the
reconstruction algorithm,
which is described next.

\subsubsection{Key reconstruction}
\label{sec:key_reconstruction}

Given $\sigma(\ho)$, the reconstruction algorithm by Guo et al. is a simple pruned
depth-first search in a tree. As such, it is recursive, and it is not obvious how one should
parallelize it. Its description is given as Algorithm~\ref{alg:rec_h0}.

Guo's et al. reconstruction algorithm as presented assumes
that one knows the weight $\hat{w}$ of $\ho$, which might not be the case for a real attacker.
But one can adapt this algorithm to consider an interval of weights for $\ho$. Guo et. al
consider $\hat{w} = w/n_0$, since making the weights of the cyclic blocks equal
is a secure approach for generating the secret key.

\begin{algorithm}[!h]
  \KwData{$n, r, w, t$ parameters of the QC-MDPC code \\
    \myinput{$\hat{w} = w/n_0$ the weight of \ho}
    \myinput{$\sigma(\ho)$ the spectrum of $\ho$}\\
    \myinput{$V$ the partially recovered support of a shift of \ho (initially set to $\{1, s_1 + 1\}$,
      where $s_1 \in \sigma(\ho))$ } \\
  }
  \KwResult{$\vec{V}$ the support of some shift of \ho, or $\perp$ if $\sigma(\ho)$ is an invalid spectrum}
  \Begin{
    \If {$|V| = \hat{w}$}{
      \If {$V$ is the support of a shift of $\ho$}{ \label{line:shady}
        \Return{$V$}
      }
      \Else{
        \Return{$\perp$}
      }
    }
    \For{each position $j = 2, \ldots, r$ which are not in $V$}{
      \If{$\dist_r(v, j) \in \sigma(\ho)$ for all $v$ in $V$} { \label{line:sieve}
        Add $j$ to $V$ \\
        $\var{ret} \gets $ recursive call with the updated set $V$ \\
        \If{$ \var{ret} \neq \perp $}{
          \Return{$V$}
        }
        Remove $j$ from $V$
      }
    }
    \Return{$\perp$}
  }
  \caption{Guo's et al. key recovery algorithm}
  \label{alg:rec_h0}
\end{algorithm}


We explain how the test in line~\ref{line:shady} can be done.
We want to test if a vector $\vec{v}$ of weight
$\hat{w}$ and support $V$ is a shift of $\ho$. Consider $\mat{B} = (\mat{H_1}^{-1} \mat{H_0})^T $ the right part
of the public matrix $\mat{G}$. Compute the vector
$\vec{u} = (\mat{B}^{-1})^T \vec{v}$. If the weight of $\vec{u}$ is $\hat{w}$, then there are two
possibilities. One, which has high probability, is that $\vec{v}$ is a shift of \ho and $\vec{u}$
is a shift of $\vec{u}$ by the same number of positions. The other possibility is that we can use
$[\, \vec{v} \, | \, \vec{u} \,]$ to build an alternative moderate density quasi-cyclic parity-check matrix
for the secret code. The key found is valid in both cases.

The main argument by Guo et al. for the efficiency of their algorithm is that unfruitful branches are
pruned relatively early in the search. More specifically, if the position of a small number of
non-null entries in the first half of $\ho$ are known, then all the other positions in the
support of $\ho$ are easily determined.

Following Guo's et al. notation, we now describe their analysis
for estimating the number $\Gamma$ of maximum paths in the search tree to be explored until the key is found.
Let $\alpha$ be the fraction of the
$\lfloor r/2 \rfloor $ possible distances that belong to the spectrum $\sigma(\ho)$, that is
$\alpha = |\sigma(\ho)|/\lfloor r/2 \rfloor$. The search starts in the root, at level 0, which
contains the positions $1$ and $s_1 + 1$.
Then it is expected that approximately $|\sigma(\ho)|\alpha$ of the
possible positions $j$ in the first half of $\ho$, that is $j < r/2$,
are such that both $\dist_r(j, 1)$ and $\dist_r(j, s_1 + 1)$
are in $\sigma(\ho)$.
For each new level in the search tree, it is expected that a fraction $\alpha$ of
the possible positions in the previous level survive the sieve imposed by
line~\ref{line:sieve}.
Then at level $\ell$ in the search tree, we expect to have around
$|\sigma(\ho)| \alpha^{\ell} = \lfloor r/2 \rfloor \alpha^{\ell + 1} $ nodes. Denote by $\phi$ the level for which each
node in level $\phi$ has an expected number of child nodes lower than or equal to 1, that is
$\phi = \min \{\ell : \lfloor r/2 \rfloor \alpha^{\ell + 2} \leq 1\}$.
Then, Guo's et al.~\cite{guo2016key} estimate on the number of possible paths is

\mathindent=2mm % <-- [A]
\[
  \Gamma = \prod_{\ell = 1}^\phi |\sigma (\ho)| \alpha^\ell
  = \prod_{\ell = 1}^\phi \left( \lfloor r/2 \rfloor \alpha \right) \alpha^\ell =
  \lfloor r/2 \rfloor ^\phi \alpha^{\phi(\phi + 3)/2}.
\]
\mathindent=7mm % <-- [A]



Guo et al. did not present a detailed analysis of the practical performance of their
algorithm,
they just state
that it
typically succeeds in a few minutes. However
in the Asiacrypt presentation~\cite{Guo2016Youtube}
of their work,
Guo shows that their algorithm runs in 144
seconds on average, and it runs in 49 minutes in the worst case, for the security level
of 80 bits using $n_0 = 2$ cyclic blocks.
They did not consider security levels higher than 80 or other values
of $n_0$.

The estimates on the number of paths $\Gamma$ for different security levels,
and supposing that the complete spectrum of $\ho$ is known, are
shown in Table~\ref{tab:guo_time}. For each line of the table,
the parameters $\alpha$ were obtained by simulations by considering the
lengths of the spectrums of $5000$ different vectors of length $r$ and weight $\hat{w}$
generated at random. We can see that the number of paths grows significantly
as the security level increases or higher values of $n_0$ are considered.
This can make the use of Guo's et al. algorithm
impractical for security levels higher than 80 and $n_0 > 2$.

\begin{table}[ht]
\centering
\caption{Estimates on the maximum number of paths $\Gamma$ in the search tree
used by Guo's et al. algorithm for different security parameters}
\label{tab:guo_time}
\begin{tabular}{@{}ccccccc@{}}
\toprule
Security  & $n_0$ & $r$   & $\hat{w} = w/n_0$   & $\alpha$ & $\phi$ & $\Gamma$ \\ \midrule
80        & 2     & 4801  & 45                  & 0.340528  & 6   & $2^{25.41}$              \\
80        & 3     & 3593  & 51                  & 0.513207  & 10  & $2^{45.55}$              \\
80        & 4      & 3079  & 55                 & 0.625694  & 14  & $2^{67.73}$ \\ \midrule

128       & 2     & 9857 & 71                   & 0.398296 & 8  & $2^{39.70}$              \\
128       & 3     & 7433 & 81                   & 0.585685 & 14 & $2^{74.19}$             \\
128       &4      & 6803 & 85                   & 0.654577 & 18 & $2^{95.62}$ \\ \midrule

256       & 2     & 32771 & 137                 & 0.435026 & 10 & $2^{61.95}$             \\
256       & 3     & 22531 & 155                 & 0.655827 & 21 & $2^{129.28}$             \\
256       &4      & 20483 & 161                 & 0.718417 & 26 & $2^{166.50}$ \\ \bottomrule
\end{tabular}
\end{table}


As observed by Fab{\v{s}}i{\v{c}} et al.~\cite{fabvsivc2017reaction}, given a vector
$\vec{v}$ with support $V~=~\{ j_0, j_1, \ldots, j_{\hat{w}-1} \},$ for some $j_i$,
then one can build a vector with the same spectrum as $\vec{v}$, namely the vector
with support
% \mathindent=2mm % <-- [A]
% \[
  $\hat{{V}}~=~\{j_0, j_1, r - j_{\hat{w}-1} + j_1, r - j_{\hat{w} -2} + j_1, \ldots, r - j_2 + j_1\}$.
% \]
% \mathindent=1mm % <-- [A]
Suppose a valid support $V$ with $\hat{w}$ elements is found but turns out
to be an invalid key in the check of line~\ref{line:shady} of Algorithm~\ref{alg:rec_h0}.
Then one can build another set $\hat{V}$ as described above, and perform the
same check of line~\ref{line:shady} for this set $\hat{V}$.
This optimization may cut in half the number of paths Guo's et al. algorithm have to explore
until a key is found. For the experimental analysis of Section~\ref{sec:experimental_results},
our implementation of their algorithm uses this optimization; that is why our implementation
is twice as efficient than Guo's et al.. However,
since the number of paths $\Gamma$ can be very large, this optimization is not enough
to make the algorithm efficient against most of the security parameters, as indicated
by our experimental analysis in Section~\ref{sec:experimental_results}.

