%-*- 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 known as Post-Quantum
Cryptography~\cite{bernstein2009post}.

One scheme that relies on a different problem, namely the \cNP-hard syndrome decoding
problem~\cite{berlekamp1978inherent}, is the McEliece scheme. This scheme was developed in the same decade as RSA~\cite{rsa1978rsa},
but was put aside since the public key size of around 100kB, for a security level of
100 bits, were intractably large at that time. Despite it's huge keys, both encryption
and decryption are more efficient than the respective 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 to build an efficient decoder for $\mathcal{G}$. If we want to send a message $\vec{m}$ to Alice, 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 $\mathcal{G}$, which she uses for obtaining $\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 admit
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
keys, most of them were shown insecure~\cite{otmani2010cryptanalysis, faugere2010algebraic, faugere2016structural}.

In 2013, a new variant of the McEliece scheme called 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, for the development of post quantum cryptography,
confirms this variant as a serious candidate for a post quantum secure standard, in
the 2015 revision of it's paper with recommendations for post quantum secure systems~\cite{augot16initial}.

Until the end of 2016, QC-MDPC has not suffered critical attacks. However at Asiacrypt
2016 Guo, Johansson, e Stankovski~\cite{guo2016key} present an efficient reaction attack
for key recovery on QC-MDPC. This attack is based on the fact that QC-MDPC
decoders are probabilistic and 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 which 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 has two phases. The first is
the collection phase, where an attacker Eve sends a number of ciphertexts to her target
Alice, and recording for which error patterns the decoder failed or succeeded, to obtain information about Alice's secret key. The second phase is the reconstruction phase, where Eve, without
interacting any further with Alice, tries to build Alice's secret key with the information
gathered in the first phase. In the original attack, the complexity of the reconstruction phase is much lower than that of the collection.

We address the following three problems of the original reconstruction algorithm:
\begin{enumerate}
    \item it cannot recover the secret key when the information about it is incomplete;
    \item the time to reconstruct the key grows too fast for higher security levels;
    \item it is recursive and not naturally parallel, therefore 10 cores might not make the algorithm 10 times faster.
\end{enumerate}

We address these three
We propose a new reconstruction algorithm that uses information of the spectra of both
$\hz$ and $\ho$. This algorithm is much faster than the original with the full spectrum, and
it can deal with incomplete information about the spectra. We analyze the expected time to recover
the key in function of the parameters of the system, and the number of decoding trials for thep
spectrum estimation phase.




