%!TEX root = paper.tex

\section{The HQC Encryption Scheme}
\label{sec:hqc}


\subsection{Setup}

On input $1^\lambda$, where $\lambda$ is the security parameter, the setup algorithm
returns the public parameters $n, k, \delta, w, w_\vec{r}, w_\vec{e}$, from
parameters table such as Table~\ref{tab:hqc_params}.
For these parameters, an $[n, k]$ linear code $\mathcal{C}$, with
an efficient decoding algorithm $\Psi$ capable  of correcting random errors of weight
up to $\delta$ with overwhelming probability, is fixed.
Parameters $w, w_\vec{r}$ and $w_\vec{e}$ correspond to
the weights of the sparse vectors defined and used in the next sections.

\addtolength{\tabcolsep}{0.4em}

\begin{table}[ht]
\centering
\caption{Suggested parameters for some security levels~\cite{aguilar2018efficient}.}
\label{tab:hqc_params}
\begin{tabular}{@{}lrrrrrrrl@{}}
\toprule


Instance     & Security  & $n_1$ & $n_2$ & $n \approx n_1 n_2$\footnote{The value of $n$ is the smallest prime number greater than $n_1 n_2$.}
                                                  & $k = k_1$ & $w$ & $w_{\vec{r}} =  w_{\vec{e}}$
                                                                    & $p_\text{fail}$         \\ \midrule
Basic-I      & 128       &  766  &  29   & 22,229 & 256 & 67  & 77  & $2^{-64} $              \\
Basic-II     & 128       &  766  &  31   & 23,747 & 256 & 67  & 77  & $2^{-96} $              \\
Basic-III    & 128       &  796  &  31   & 24,677 & 256 & 67  & 77  & $2^{-128}$              \\ \midrule
Advanced-I   & 192       &  796  &  51   & 40,597 & 256 & 101 & 117 & $2^{-64} $              \\
Advanced-II  & 192       &  766  &  57   & 43,669 & 256 & 101 & 117 & $2^{-128}$              \\
Advanced-III & 192       &  766  &  61   & 46,747 & 256 & 101 & 117 & $2^{-192}$              \\ \midrule
Paranoiac-I  & 256       &  766  &  77   & 59,011 & 256 & 133 & 153 & $2^{-64} $              \\
Paranoiac-II & 256       &  766  &  83   & 63,587 & 256 & 133 & 153 & $2^{-128}$              \\
Paranoiac-III& 256       &  796  &  85   & 67,699 & 256 & 133 & 153 & $2^{-192}$              \\
Paranoiac-IV & 256       &  796  &  89   & 70,853 & 256 & 133 & 153 & $2^{-256}$              \\ \bottomrule
\end{tabular}
\end{table}

\addtolength{\tabcolsep}{-0.4em}


\subsection{Key Generation}

Let $\mat{H} \in \Fb^{n \times 2n}$ be a quasi-cyclic matrix selected at random, in
systematic form, that is $ \mat{H} = [ \, \mat{I} \, | \, \rot(\vec{h}) \,]$,
for some vector $\vec{h}$.
Let $\vec{x}, \vec{y} \in \Fb^n$ be sparse vectors with weight
$\weight(\vec{x}) = \weight(\vec{y}) = w$.
Compute
\[
  \vec{s} = [\vec{x} | \vec{y}] \mat{H}^T = \vec{x} + \vec{y} \cdot \rot(\vec{h})^T
        =  \vec{x} +  \vec{y} \cdot \vec{h}.
\]
The public and secret key are $\pk = [\vec{s} | \vec{h}] $ and $\sk = [\vec{x} | \vec{y}]$,
correspondingly.

From this construction, it is easy to see the relation between recovering the secret key from
the public key and the quasi-cyclic syndrome decoding problem.

\subsection{Encryption}

Let $\vec{m} \in \Fb^k$ be the message to be encrypted.
First, choose two random sparse vectors $\vec{r}_1, \vec{r}_2 \in \Fb^n$ such that
$\weight(\vec{r}_1) = \weight(\vec{r}_2) = w_\vec{r}$.
Then choose a random sparse vector $\vec{e} \in \Fb^n$ such that
$\weight(\vec{e}) = w_{\vec{e}}$. Let
\[
  \vec{u} = [\vec{r}_1 | \vec{r}_2] \mat{H}^T =  \vec{r}_1 +  \vec{r}_2 \cdot \vec{h},
  \text{ and } \vec{v} = \vec{m} \mat{G} + \vec{s} \cdot \vec{r}_2 + \vec{e}.
\]
Return the ciphertext $\vec{c} = [\vec{u} | \vec{v}]$.

\subsection{Decryption}

Compute $\vec{c}' = \vec{v} + \vec{u} \cdot \vec{y}$.
Notice that
\begin{align*}
  \vec{c}' &= \vec{m} \mat{G} + \vec{s} \cdot \vec{r}_2 + \vec{e} +  \left( \vec{r}_1 + \vec{r}_2 \cdot \vec{h} \right) \cdot \vec{y} \\
           &= \vec{m} \mat{G} + \left( \vec{x} + \vec{y} \cdot \vec{h} \right) \cdot \vec{r}_2 + \vec{e} +  \left( \vec{r}_1 + \vec{r}_2 \cdot \vec{h} \right) \cdot \vec{y} \\
             &= \vec{m} \mat{G} + \vec{x} \cdot \vec{r}_2 + \vec{r}_1 \cdot \vec{y} + \vec{e}.
\end{align*}

Intuitively, since $\vec{x}, \vec{y}, \vec{r}_1, \vec{r}_2, $ and $\vec{e}$ all have low weight, we expect
 $\vec{e}' = \vec{x} \cdot \vec{r}_2 + \vec{r}_1 \cdot \vec{y} + \vec{e}$
to have a relatively low weight. This is made precise by Aguilar-Melchor et
 al.~\cite{aguilar2018efficient}, where they propose the public parameters
to ensure that $\weight(\vec{e}')$ is sufficiently low for it to be corrected out
of $\vec{c}'$ with overwhelming probability.

Therefore we can use the decoder $\Psi$ to correct the errors in $\vec{c}'$ and obtain $\vec{c}'' = \Psi(\vec{c}') = \vec{m} \mat{G}$.
We finally get $\vec{m}$ by solving the overdetermined linear system $\vec{m} \mat{G} = \vec{c}''$.


\subsection{Security and Instantiation}

In general, schemes based on syndrome decoding have to take care
to avoid generic attacks based on Information Set
Decoding~\cite{prange1962use,stern1988method,torres2016analysis}.
Furthermore, the quasi-cyclic structure of the code used to secure the secret key
can make the scheme vulnerable to DOOM~\cite{sendrier2011decoding}, or
other structural attacks~\cite{guo2015new,londahl2016squaring}.

To instantiate the scheme, the authors propose parameters for which they
prove very low decryption error probability and resistance to the
attacks mentioned. This error analysis allows the
HQC to achieve IND-CCA2 security using the
transformation of Hofheinz et al.~\cite{hofheinz2017modular}.


Of particular interest for our timing attack, is the way that
code $\mathcal{C}$ is chosen. Their proposal is to build the tensor code
$\mathcal{C} = \mathcal{C}_1 \otimes \mathcal{C}_2$, where the auxiliary codes
are chosen as follows. $\mathcal{C}_1$ is a BCH($n_1, k_1, \delta_1$) code of
length $n_1$, dimension $k_1$.
$\mathcal{C}_2$ is a repetition code of length $n_2$ and dimension $1$,
that can decode up to $\delta_2 = \left \lfloor \frac{n_2 - 1}{2} \right \rfloor$.
Therefore, to encode a message $\vec{m}$ with respect to $\mathcal{C}$ is equivalent
to first encode it using the BCH code $\mathcal{C}_1$, and then encode \emph{each bit} of
the resulting codeword with the repetition code $\mathcal{C}_2$.

The suggested parameters for this instantiation are shown in Table~\ref{tab:hqc_params}.
In this table, column $p_\text{fail}$ contains an upper bound
for the probability of a decryption failure for each instance of the scheme.
The size of the public keys and ciphertexts correspond to $2n$ bits.

