%!TEX root = paper.tex

\section{Introduction}

Hamming Quasi-Cyclic (HQC)~\cite{melchor2018hamming}
is a code-based public-key encryption scheme.
It is based on the hardness of
the quasi-cyclic syndrome decoding problem, a conjectured hard problem from Coding Theory.
It offers reasonably good parameters, with better key sizes than the
classical McEliece scheme~\cite{mceliece1978,bernstein2019classic,albrecht2018nts},
but without relying on codes with a secret sparse structure, such
as QC-MDPC~\cite{misoczki2013mdpc} and  QC-LDPC~\cite{baldi2014ldpc_crypto}.

One of the most interesting features HQC provides is a detailed
analysis of the decryption failure probability, which makes it possible
to choose parameters that provably avoid
reaction attacks~\cite{guo2016key,fabvsivc2017reaction} that compromise the security
of QC-LDPC and QC-MDPC encryption schemes.
This makes it one of the most promising code-based candidates in
NIST's Post-Quantum standardization process.
However, the negligible probability of decoding failure comes at the expense of low encryption rates.


% HQC~\cite{melchor2018hamming}
% is a code-based public key encryption scheme based based on the
% difficulty of decoding quasi-cyclic random codes. Beside its efficiency and
% relatively low key sizes, one of the main features
% introduced by HQC is a detailed analysis of the probability of occurring
% decryption errors. In particular, this feature protects it against
% reactions attack, which are a serious threat to the QC-MDPC and QC-LDCP variants of
% the McEliece scheme~\cite{guo2016key,fabvsivc2017reaction}.

% The scheme was selected for the second round on the NIST PQC Standardization
% Process, which suggest that the confidence on HQC is high. As pointed
% by NIST in their status report on the first round submissions, HQC presents the strongest argument for CCA2 security among other code-based schemes~\cite{nist2019status}.

The scheme uses an error correction code $\mathcal{C}$ as a public parameter.
The secret key is a sparse vector, while the public key is its syndrome
with respect to a systematic quasi-cyclic matrix chosen at random, together with
the description of this matrix.
To encrypt a message, the sender first encodes it with
respect to the public code $\mathcal{C}$, then adds to it a binary error vector which
appears to be random for anyone who is not the intended receiver.
The receiver, using the sparseness of her secret key,
is able transform the ciphertext in such a way to significantly reduce the weight of the error vector.
Then, the receiver can use the efficient decoding procedure for $\mathcal{C}$ to
correct the remaining errors of the transformed ciphertext to recover the message.


The code $\mathcal{C}$ proposed by Aguilar-Melchor et al.~\cite{melchor2018hamming}
is a tensor code between a BCH code and a repetition code.
One drawback of the HQC implementation submitted to NIST is that the decoder~\cite{joiner1995decoding}
for the BCH code is not constant-time, and depends on the weight of the error it corrects.
This makes the decryption operation vulnerable to timing attacks.

The use of non-constant-time decoders has been exploited to attack code-based schemes
such as QC-MDPC~\cite{eaton2018qc}, and recently, RQC~\cite{aguilar2018efficient},
which is a variant of HQC in the rank metric that uses Gabidulin codes~\cite{gabidulin1985theory},
was shown vulnerable to timing attacks~\cite{Bettaieb2019rqcattack}.
However, timing attacks exploiting non-constant-time decoders are not exclusive to code-base
schemes, and the use of BCH codes in LAC~\cite{lac2018} has been shown to
leak secret information from timing~\cite{cryptoeprint:2019:292}.

\paragraph{Contributions.}
We present the first timing attack on HQC. The attack follows Guo et al.~\cite{guo2016key}
idea: first we show how to obtain information, which is called the spectrum,
on the secret key by timing a large number of decryptions,
and then use the information gathered to reconstruct the key.
We analyze in detail the reason behind the information leakage.
As a minor contribution, we show that a randomized variant of Guo's et al. algorithm
for key reconstruction is better than their recursive algorithm when the attacker has partial
information on the secret key's spectrum. This is useful to reduce the number
of decryption timings the attacker needs to perform.


Shortly after this paper was accepted for publication, Wafo-Tapa et al.~\cite{cryptoeprint:2019:909}
published a preprint in the Cryptology ePrint Archive in which they also present a timing attack
against HQC.
Our attack is stronger in the sense that we target the CCA secure version of HQC, while they
target only the CPA secure version. However, their paper comes with a countermeasure, which
consists of a constant-time BCH decoder with a low overhead.


\paragraph{Paper organization.}
In Section~\ref{sec:prelim}, we review some background concepts for understanding HQC and our
attack. The HQC is described in Section~\ref{sec:hqc}.
The attack is presented in Section~\ref{sec:attack}. Some mathematical and algorithmic
aspects of the attack are analyzed in detail in Section~\ref{sec:analysis}.
In Section~\ref{sec:expresults}, we analyze the practical performance of the attack
against concrete HQC parameters. We conclude in Section~\ref{sec:conclusion}.


