%!TEX root = paper.tex

\section{Experimental results}
\label{sec:experimental_results}

The analysis of our algorithm presented in the previous section shows that it
has better asymptotic complexity than Guo's et al. key
reconstruction algorithm. We now show the experimental analysis of the implementation of our algorithm.

We do the experimental analysis in two parts. In the first part, we analyze the performance of our
reconstruction algorithm when reconstructing the key for different security parameters. We also compare
our algorithm with the one by Guo et al. in the best possible scenario for their algorithm, which is
when the spectrum of the key is fully known.

In the second part, we present an empirical analysis of the number of challenges needed for a CCA2 attack
for the 80 bits security parameters with $n_0 = 2$. For this analysis, we simulated the first part of the
attack, that is, the spectrum recovery procedure, against 200 different private keys.

All the source code and data used in this section is publicly available at
\url{www.ime.usp.br/~tpaiva/msc/src}.

\subsection{Performance of the proposed algorithm}

The algorithm's performance was analyzed on an Intel i7 870
Lynnfield CPU, at a 2.93GHz clock frequency, and 8GB of RAM. We implemented the algorithm
in C using the M4RI~\cite{M4RI} library for the kernel matrix computation.

\subsubsection{The algorithm when full spectrums are known}

For some security parameters, when both the spectrums of \hz and \ho are fully known,
the value of $Z_0 + Z_1$ is typically much
larger than $r$. For these parameters, we can consider the set $Z_0$ as
\[
    Z_0 \gets \{ i + p \mod r: \dist(1, i) \in D_0\},
\]
in line~\ref{line:z0} of Algorithm~\ref{alg:proposed_algo}.
In other words, for some parameters, we can consider only one non-null entry when building $Z_0$,
instead of considering two, and $Z_0 + Z_1$ still is sufficiently larger than $r$.

This simple change allows our algorithm to perform a lot better than Guo's et al. algorithm when
full spectrums are known. Table~\ref{tab:performance_comp_full} shows the comparison between
our algorithm and Guo's et al. algorithm when full spectrums are known. The performance of
our algorithm is marked with an asterisk $(*)$ on the parameters for
which the modification above is applicable, that is, the algorithm still finds the key
when $Z_0$ is built with only one non-null entry as reference.

Guo's et al. algorithm performed very poorly for security parameters different from $\lambda = 80$
with $n_0 = 2$. For the security parameters $\lambda = 128$ and $n_0 = 2$, their algorithm took the median
time of around $27$ hours to explore each branch of the search tree.
Parameters for which the algorithm did not run in reasonable time are marked with a hyphen (-) in
Table~\ref{tab:performance_comp_full}.
Considering the values of $\Gamma$ in Table~\ref{tab:guo_time}, it is unrealistic to expect that
Guo's et al. algorithm runs efficiently for the parameters in which $n_0 \geq 3$, or $\lambda = 256$.

\begin{table}[ht]
\centering
\caption{Performance comparison of our algorithm and Guo's et al. algorithm for different different security levels when \emph{full} spectrums are known}
\label{tab:performance_comp_full}
\begin{tabular}{cccc}
\toprule
\begin{tabular}[c]{@{}c@{}}Security \\ level \\ $\lambda$\end{tabular} &
\begin{tabular}[c]{@{}c@{}}$n_0$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Average running time of \\ Guo's et al. algorithm \end{tabular} & \begin{tabular}[c]{@{}c@{}}Average running time  \\ of our algorithm\end{tabular} \\
\midrule
80  & $2$ & 71.18s  &   {0.72s}*     \\
80  & $3$ & - &   {0.21s}* \\
80  & $4$ & - &   {31s} \\ \midrule

128 & $2$ & $\sim 24$ days  & {11s}*       \\
128 & $3$ & - & {3.75s}*       \\
128 & $4$ & -  & {183s}       \\ \midrule

256 & $2$ & - & {141s}*       \\
256 & $3$ & - & {3h40m}        \\
256 & $4$ & - & -       \\ \bottomrule
\end{tabular}
\end{table}



\subsubsection{The algorithm with partial spectrums}

We assess the performance of the algorithm using the minimum amount of information possible, while
retaining a good probability of success. For this we use values $d$ given in
Table~\ref{tab:size_d_for_sim} for the sizes of the sets $D_0$ and $D_1$.

Note that total execution time, or total number of cycles, alone are not very informative
metrics for this algorithm.
This is because the number of iterations for reconstructing a key is a random variable following
a uniform distribution in the set $[r]$. Therefore, if we know the execution time
per iteration, we can model more accurately the performance of the algorithm.
Table~\ref{tab:performance_comp_partial} shows the performance results of our algorithm for different
security parameters. We do not consider the performance of Guo's et al. algorithm in this
table because their algorithm takes too long to finish when partial spectrums are considered,
making its application infeasible.


\begin{table}[t]
\centering
\caption{Performance comparison of our algorithm and Guo's et al. algorithm for different different security levels when \emph{partial} spectrums are known}
\label{tab:performance_comp_partial}
\begin{tabular}{ccccc}
\toprule
\begin{tabular}[c]{@{}c@{}}Security \\ level \\ $\lambda$\end{tabular} &
\begin{tabular}[c]{@{}c@{}}$n_0$ \end{tabular} & $d$-exclusion & \begin{tabular}[c]{@{}c@{}} Average time \\
per iteration \end{tabular} & \begin{tabular}[c]{@{}c@{}} Average total \\
running time \end{tabular} \\
\midrule
80  & $2$ & $d_{80} = 722$ & 0.023s &   55s     \\
80  & $3$ & $d_{80} = 545$ & 0.014s &   25s     \\
80  & $4$ & $d_{80} = 471$ & 0.010s &   15s     \\ \midrule

128 & $2$ & $d_{128} = 1470$ & 0.14s  & 690s       \\
128 & $3$ & $d_{128} = 1116$ & 0.07s  & 260s       \\
128 & $4$ & $d_{128} = 1025$ & 0.05s  & 170s       \\ \midrule

256 & $2$ & $d_{256} = 4845$ & 4.15s & 18h54m       \\
256 & $3$ & $d_{256} = 3347$ & 1.20s & 3h46m        \\
256 & $4$ & - & - & -       \\ \bottomrule
\end{tabular}
\end{table}



\subsection{The number of challenges needed for a CCA2 attack}

We now analyze the number of decoding trials for a CCA2 attack when we use the proposed
algorithm for key reconstruction.
For comparison purposes,
we consider the security level
of 80 bits and $n_0 = 2$, which are the same parameters considered by Guo et. al.

For the analysis, 200 different codes were randomly generated and for each of them, were
performed 100 million decoding trials. The decoder used was the same used by Guo et al.,
that is, algorithm $\mathcal{B}$ considered
by Maurich et al.~\cite{maurich2015implementing}. Each battery of decoding trials looks
like the
one in Figure~\ref{fig:cca2_performance_example}. The y-axis shows the value
$d = \min (d_0, d_1)$, where $d_0$ and $d_1$ are the exclusions obtained for
$\sigma(\hz)$ and $\sigma(\ho)$, respectively.

Since we can successfully reconstruct the key
when the exclusion for both $\sigma(\hz)$ and $\sigma(\ho)$ are greater than or
equal to $d_{80} = 722$, as shown in Table~\ref{tab:size_d_for_sim}, we are interested in
knowing how many decoding trials are needed to obtain a $d$-exclusion of 722 for both
of the spectrums.
In the example shown in Figure~\ref{fig:cca2_performance_example}, the first point where the
attack is possible is at around 30 million decoding trials.


\begin{figure}[!h]
  \centering
  \includegraphics[scale=1]{figures/expresults/cca2_performance_example.pdf}
  \caption{Example of the result of the decoding challenges for one of the 200 codes}
  \label{fig:cca2_performance_example}
\end{figure}


The histogram of the number of decoding trials necessary for a successful attack
is shown in Figure~\ref{fig:separation_hist}.
Guo's et al. algorithm need an almost complete $d$-exclusion to run efficiently,
which occurs after around 200 million\footnote{In their paper, Guo et al. report that
in the best case of their simulation the spectrum was fully recovered after 203 million decoding challenges.}
decoding challenges~\cite{guo2016key}. Our results suggest that when our algorithm is used
to reconstruct the key only around 28 million decoding trials are needed, which
is a significantly improvement on the amount of interaction with the secret key holder.

\begin{figure}[!h]
  \centering
  \includegraphics[scale=1]{figures/expresults/separation_hist.pdf}
  \caption{Histogram of the number of decoding trials for a successful key reconstruction}
  \label{fig:separation_hist}
\end{figure}

