%!TEX root = paper.tex

\section{Experimental Results}
\label{sec:expresults}

In this section, we present our results for the timing attack against the Basic-I parameters of the HQC.
We consider the two parts of the attack separately. First we run experiments on the key reconstruction
algorithm to find out how much information on the spectrum it needs to run efficiently. We then
run simulations to estimate how many decryptions timings an attacker needs to perform to
be able to reconstruct the key.
The source code and data are available at \url{www.ime.usp.br/~tpaiva}.

\subsection{Performance of the Key Reconstruction Algorithm}
\label{sec:performance_key_reconstruction}

We want to determine how many entries outside the spectrum of the secret vector $\vy$
the attacker needs to know for the key reconstruction algorithm to efficiently reconstruct the vector.
In other words, we are interested in how large the set $D$ needs to be.
Figure~\ref{fig:gjs_vs_randomized} gives us a hint on this matter, but it does not give us a concrete
estimation of the key reconstruction algorithm's performance.

Table~\ref{tab:key_reconstruction_performance} shows the performance of both key reconstruction algorithms,
the GJS and our randomized variant,
when given sets $D$ of different sizes for the Basic-I HQC parameters.
For each considered size for the set $D$,
we generated 10 random secret keys and considered $D$ as a random set of $|D|$ distances outside the spectrum.
The distance $s$ was selected at random from the secret key spectrum.
For a more clear interpretation of the results, we considered, in the second column,
the approximate average number $\Delta = 9104$ of distances not in the spectrum, to normalize the values $|D|$.
We then ran C implementations of the algorithms with parameters $D$ and $s$.
This experiment was performed on an Intel i7-8700 CPU at 3.20GHz, using its 12 hyperthreads.

\begin{table}[ht!]
\centering
\caption{Performance of the key reconstruction algorithms when input $D$ has different sizes, for the Basic-I HQC parameters.}%
\label{tab:key_reconstruction_performance}
\addtolength{\tabcolsep}{1pt}
\begin{tabular}{@{}rrrrrrr@{}}
\toprule
 &  & \multicolumn{3}{c}{\begin{tabular}[c]{@{}c@{}} \textbf{Randomized variant of} \\ \textbf{the GJS reconstruction algorithm} \end{tabular}} &  & \multicolumn{1}{c}{\begin{tabular}[c]{@{}c@{}}\textbf{GJS reconstruction}\\  \textbf{algorithm}\end{tabular}} \\ \cmidrule(lr){3-5} \cmidrule(l){7-7}
$|D|$ & $|D|/\Delta$ & $\WF_\textsc{Rand}$ & \begin{tabular}[c]{@{}l@{}}Median of the \\ number of paths\end{tabular} & \begin{tabular}[c]{@{}l@{}}Median of the\\ CPU time (s)\end{tabular} &  & \begin{tabular}[c]{@{}l@{}}Median of the\\ CPU time (s)\end{tabular} \\ \midrule
9104 & 100\% & 28 & 63 & 0.51 & & 0.98  \\
8648 & 95\% & 99 & 80 & 0.51 & & 10.78  \\
8192 & 90\% & 407 & 232 & 0.50 & & 772.64  \\
7736 & 85\% & 1957 & 1714 & 0.75 & & 6801.10   \\
7280 & 80\% & 11394 & 9995 & 1.96 & & -  \\
6824 & 75\% & 83670 & 54721 & 10.02 & & -  \\
6368 & 70\% & 816671 & 365604 & 75.63 & & -  \\
5912 & 65\% & 11355108 & 8472060 & 2767.90 & & -  \\
5456 & 60\% & 246873607 & {-} & {-} &  & -  \\ \bottomrule
\end{tabular}
\end{table}

We can see that our randomized algorithm performs much
better than Guo's et al.~\cite{guo2016key} one. This
not only implies that the randomized algorithm allows faster key reconstruction,
but also that it allows the
attacker to recover the key with less interaction with the secret key holder.
The estimates for the number of paths $\WF_\textsc{Rand}$ appear to be sufficiently
accurate for our purposes, with only a minor
discrepancy when $D/\Delta = 100\%$ that happens because of the concurrent hyperthreads.
From $D/\Delta = 60\%$ down, the randomized algorithm starts taking too long to finish.
Therefore, we consider that we are able to efficiently reconstruct the key when
$D/\Delta \geq 65\%$.


\subsection{Communication Cost}
\label{sec:number_of_decryption_timings}

We now analyze how many decryption challenges an attacker needs to send to the secret key
holder for a successful attack.
In this paper, we only considered the Basic-I HQC parameters, but this experiment
can easily be extended for the other parameters.

For the analysis, 10 secret keys were generated at random, and for each of them
we ran the spectrum recovery algorithm for $M = 700$ million challenges.
For each number challenges $i$, consider the quality of the decryption
time estimates $\Tx^i$ and $\Ty^i$, given by
\begin{align*}
    \qual(\Tx^i) &= \max \left\{ \mu : \textsc{BuildD}(\Tx^i, \mu) \cap \sx = \emptyset \right\}, \text{ and } \\
    \qual(\Ty^i) &= \max \left\{ \mu : \textsc{BuildD}(\Ty^i, \mu) \cap \sy = \emptyset \right\},
\end{align*}
where \textsc{BuildD} is the algorithm described in the end of Section~\ref{sec:spectrum_recovery}.
For the \textsc{BuildD} procedure, we considered the window size $\eta = 11$, which was obtained by the
independent simulation described in the end of Section~\ref{sec:spectrum_recovery}.

Based on the results from the previous section,
we consider that the key reconstruction algorithm
can efficiently recover \vx or \vy, when either $\qual(\Tx^i)$ or $\qual(\Ty^i)$ is greater than 5912, correspondingly.

Figure~\ref{fig:number_of_challenges} shows the result of the experiment.
We can see that with about 400 million of challenges, efficient key reconstruction is possible.
After 600 million challenges, almost all distances outside the spectrum can
be correctly identified.

\begin{figure}[htb!]
  \centering
  \includegraphics[scale=1]{figures/expresults/number_of_challenges.pdf}
  \caption{Number of decryption timings an attacker needs to perform before the key can be
  successfully reconstructed. A confidence level of 95\% was considered for the error bars.}
  \label{fig:number_of_challenges}
\end{figure}