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

\section{Introduction}
\label{sec:intro}

In 1994, Shor~\cite{shor1994algorithms} published two algorithms for quantum computers that solve efficiently two critical problems in modern cryptography: the discrete logarithm and integer factorization problems. With the engineering progress on building larger
quantum computers, the main cryptographic schemes used today become more vulnerable.
This seeds the quest for finding cryptographic primitives
that do not rely on the hardness of these problems, which is an active research area
known as post-quantum cryptography~\cite{bernstein2009post}. The need for
post-quantum secure standards is recognized by the National Institute of Standards and
Technology (NIST), which is calling for proposals~\cite{chen2016report}.

The McEliece scheme~\cite{mceliece1978}
relies on the syndrome decoding problem, which is known to be
 \cNP-hard~\cite{berlekamp1978inherent}.
This scheme was developed in the same decade as the RSA~\cite{rsa1978rsa},
but it was put aside because the public key size of around 100kB, for a security level of
100 bits, were intractably large at that time. Despite its huge keys, both encryption
and decryption are more efficient than the corresponding operations of the RSA and
elliptic curves~\cite{miller1986ecc} schemes.

In the McEliece scheme, Alice's secret key is a linear code $\mathcal{G}$
capable of correcting $t$ errors, for which Alice knows an efficient decoder.
Her public key is the generator matrix of $\mathcal{G}$, possibly scrambled, in such
a form that it is unfeasible for an attacker to use this matrix for building an
efficient decoder for $\mathcal{G}$. To send Alice a message $\vec{m}$,
we encode $\vec{m}$ using her public key and add $t$ intentional errors to this
encoding, giving
us $\vec{c}$. We now can safely send her $\vec{c}$, because Alice is the only one that
has an efficient decoder for $\mathcal{G}$, which
she uses to obtain $\vec{m}$ from $\vec{c}$.

One of the post-quantum cryptography research trends is to lower the public key sizes
of the McEliece scheme by choosing families of error correcting codes that allow
compact representation, without compromising security.
Originally McEliece suggested the use of binary irreducible Goppa
codes~\cite{goppa1970new}, which are still considered secure, at the expense of
huge keys. The majority of other proposed code families rely on a quasi-cyclic or
quasi-dyadic structure for compact
representation~\cite{gaborit2005shorter,berger2009reducing,baldi2007quasi,
misoczki2009compact}. Although they obtain compact
keys, most of them were shown insecure~\cite{otmani2010cryptanalysis, faugere2010algebraic, faugere2016structural}.

In 2013, a new variant of the McEliece scheme that uses quasi-cyclic 
moderate-density parity-check codes (QC-MDPC) was presented by
Misoczki et al.~\cite{misoczki2013mdpc}. This variant promises
extremely compact public keys of only 4801 bits for a security level of
80 bits, and has an apparently strong security reduction.
The European initiative PQCRYPTO, which supports the development of post-quantum cryptography,
considered this variant as a serious candidate for a post-quantum secure standard in
the 2015 revision of its
paper with recommendations for post-quantum secure systems~\cite{augot16initial}.

Until the end of 2016, the QC-MDPC has not suffered critical attacks.
However at Asiacrypt
2016 Guo, Johansson, and Stankovski~\cite{guo2016key} present an efficient reaction attack
for key recovery on the QC-MDPC. This attack is based on the fact that QC-MDPC
decoders can fail. When a decoding failure occurs, the receiver
asks the sender to resend the message, which hopefully, will be encrypted with an error
pattern that the decoder will be able to correct. The main observation of the authors
is that the probability that the decoder fails when correcting the error $\vec{e}$ is
significantly smaller when $\vec{e}$ and the secret key share some certain properties.

The proposed attack is done in two parts. In the first part, an attacker Eve sends a number of
ciphertexts to her target Alice, and records for which error patterns the decoder failed
or succeeded, to obtain some information, which they called the spectrum,
about Alice's secret key. The second part is the reconstruction part, where Eve,
without interacting any further with Alice, tries to build Alice's secret key with the
information gathered in the first part.

We address the following three problems of Guo's et al. reconstruction algorithm:
\begin{enumerate}
    \item it cannot recover the secret key when the information about it is incomplete; \label{it:incomplete}
    \item the number of operations needed to find the key grows very fast with respect to the security level;
    \item it is recursive in nature, and it is not obvious how to parallelize it,
    neither how much one gains by doing it.
\end{enumerate}
The algorithm by Guo et al. and its weaknesses are analyzed in more detail in Section~\ref{sec:key_reconstruction}.

Our proposed algorithm is iterative, it can be parallelized straightforwardly,
and it is based only on linear algebra over $\Fb$.
Our algorithm is able
to deal with less information, therefore an attacker
needs only to perform a lower number of decoding trials.
This is particularly important
because one way to protect the scheme against the reaction attack is to limit the
lifetime of a secret key, which must be determined as a function of
the number of decoding
trials that are sufficient for a successful attack.
The algorithm also has lower asymptotic complexity, which makes it scale a lot better for higher security parameters.

Upon preparation of this paper, it came to our knowledge
that the linear relation which we exploit was also used by Rossi
et al.~\cite{rossiside} in their recent paper on a side-channel attack against 
QcBits~\cite{chou2016qcbits}.
However our algorithm is significantly
different because it uses more efficiently the information given by the reactions of 
the secret key holder in the first part of the attack. This not only makes
it more efficient, but it also allows the algorithm to recover the key with
less interaction with the secret key holder.
Further, our analysis of the algorithm performance is more detailed.


This paper is organized as follows. Section~\ref{sec:prelim}
presents some preliminary concepts.
A review of the QC-MDPC McEliece is done in Section~\ref{sec:mdpc}, 
which ends with a discussion on the performance of the attack by Guo et al.~\cite{guo2016key}.
The presentation of our contributions starts in
Section~\ref{sec:idea}, where our proposed reconstruction
algorithm and its underlining ideas are shown.
The probabilistic analysis of the proposed algorithm is in Section~\ref{sec:complexity}.
Section~\ref{sec:experimental_results} presents the experimental
results. The concluding remarks are in Section~\ref{sec:conclusion}.
