%!TEX root = paper.tex

\section{Analysis}
\label{sec:analysis}

In this section we analyze two aspects of the attack. First we explain why it
is possible to distinguish between distances inside and outside the spectrum based on
decryption time.
Then we analyze the complexity of the randomized key reconstruction algorithm, and how it compares
to the one presented by Guo et al.~\cite{guo2016key}.

\subsection{Distinguishing Distances Inside and Outside the Spectrum}
\label{sec:analysis_spectrums}

We know that the decryption time is related to the number of errors left by
the repetition code (RC) decoder.
Our main observation is that the number of RC decoding errors depends on how the
spectrums of $\vec{r}_1$ and $\vec{r}_2$ relate to those of $\vy$ and $\vx$, respectively.


Consider the error to be corrected by the RC decoder, given by
\[
  \vec{e}' = \vec{r}_1 \cdot \vy + \vec{r}_2 \cdot \vx + \vec{e}.
\]
An RC decoding error occurs when $\vec{e}'$ contains more than $(n_2 - 1)/2$ nonzero
errors in the same repetition block.
Therefore, an RC decoding error has higher probability of occurring when the spectrum
of $\vec{e}'$ contains small distances with high multiplicity, and in particular,
when $\sigma(\vec{e}')$ contains a lot of distances lower than the repetition block length $n_2$.
We also expect that $\sigma(\vec{e}')$ contains small distances when $\sigma(\vec{r}_2 \cdot \vx)$ and
$\sigma(\vec{r}_1 \cdot \vy)$ also contain small distances.
In the following discussion, we focus on $\vec{r}_1 \cdot \vy$, but we could have
used $\vec{r}_2 \cdot \vx$ without any difference.

The above paragraph motivates us to better understand what causes the spectrum of $\vec{r}_1 \cdot \vy$ to
contain small distances.
Unfortunately, the strong dependency between the rows of $\rot(\vy)^T$ can make it
very hard to perform a satisfactory statistical analysis on the product $\vec{r}_1 \cdot \vy$.

Therefore, we study a simpler problem, namely to describe $\sigma(\vec{r}_1 \cdot \vy)$
as a function of $\sigma(\vec{r}_1)$ and $\sigma(\vy)$,
but restricted to the case where $\weight(\vec{r}_1) = \weight(\vy) = 2$.
Even though it is not the general case, it can give us a good intuition on why the attack works.
The analysis is given in the following lemma. First we discuss the implications
of the lemma and how it can be
used to distinguish between distances inside and outside the spectrums of the secret key,
and then we prove it.

\begin{lemma}
\label{lem:spectrum_of_product}

Let $\vy, \vec{r} \in \Fb^n$ be two binary vectors of weight 2, where $n$ is an odd prime.
Let $\alpha$ and $\beta$ be the only distances in $\sigma(\vy)$ and
$\sigma(\vec{r})$, respectively.
Then, we have the following possibilities.\footnote{Recall that we use $(\gamma : m) \in \sigma(\vy)$ to
denote that cyclic distance $\gamma$ occurs $m$ times between non-null entries of \vy.}

If $\alpha = \beta$, then
\begin{align}
  \sigma(\vec{r} \cdot \vy) = \{ \dist_n(0, 2\alpha): 1 \} = \{ \dist_n(0, 2\beta): 1 \}. \label{mathlin:in_spec}
\end{align}

If $\alpha \neq \beta$, then
\begin{align}
  \sigma(\vec{r} \cdot \vy) = \{
    &\alpha : 2, \label{mathlin:alpha} \\
    &\beta: 2, \label{mathlin:beta} \\
    &|\beta - \alpha| : 1, \label{mathlin:beta_minus_alpha} \\
    &\dist_n(0, \beta + \alpha): 1\}. \label{mathlin:beta_plus_alpha}
\end{align}

\end{lemma}


\paragraph{Interpreting Lemma~\ref{lem:spectrum_of_product}.}
Intuitively, $\alpha$ represents distances inside the spectrum of the secret vector $\vy$, while
$\beta$ represents distances inside the spectrum of $\vec{r}_1$.
We now restate the observations from Section~\ref{sec:spectrum_recovery} with brief
discussions on why they happen, using the lemma to help us.

\begin{enumerate}


  \item When $\beta$ decreases from $\beta = n_2 - 1$ to $\beta = 1$, the value of $\Ty[\beta]$ increases,
    getting significantly higher than the rest of the values in $\Ty$.

    \begin{itemize}
    \item[]
    From (\ref{mathlin:beta}), distance $\beta$ in $\sigma(\vec{r}_1)$ can cause $\sigma(\vec{r}_1 \cdot \vec{x})$
    to contain $\beta$ with multiplicity 2. Therefore when $\beta < n_2$, it can be responsible for more
    RC errors than values of $\beta \geq n_2$.
    The reason why $\Ty[\beta]$ gets increasingly higher when $\beta$ approaches 1 is that,
    we get an increasing incidence of $\beta + \alpha < n_2$, where $\alpha \in \sy$.
    Therefore, from (\ref{mathlin:beta_plus_alpha}), these values of $\beta$ tend to cause more distances lower than $n_2$
    in $\sigma(\vec{r}_1 \cdot \vy)$.

    \end{itemize}

  \item When $\beta \in \sy$, the value of $\Ty[\beta]$ is lower than the average in the neighborhood of $\beta$.
    \begin{itemize}

    \item[]
    Comparing both cases considered by the lemma, we see that values of $\beta = \alpha$ for some $\alpha \in \sy$
    (Case~1) are expected to produce a lower number of small
    distances in $\sigma(\vec{r}_1 \cdot \vec{x})$ than values of $\beta \neq \alpha$ for
    all $\alpha \in \sy$ (Case~2).

    \end{itemize}

  \item When $\beta$ has a large number of neighbors in $\sy$, the value of $\Ty[\beta]$ tends to be higher.

    \begin{itemize}
    \item[]
    Using (\ref{mathlin:beta_minus_alpha}), we have that $\Ty[\beta]$ tends to be
    higher when more values of $\alpha \in \sy$ satisfy $|\beta - \alpha| < n_2$.
    In fact, the lemma even helps us formalize the neighborhood of $\beta$ as the distances $d$
    between $\beta - n_2 < d < \beta + n_2$.

    \end{itemize}
\end{enumerate}

We now proceed with the proof of Lemma~\ref{lem:spectrum_of_product}.

\begin{proof}[Lemma~\ref{lem:spectrum_of_product}]
Let $\alpha_1, \alpha_2$ and $\beta_1, \beta_2$ be the positions of the two ones in $\vy$ and
$\vec{r}$, respectively.
We can suppose without loss of generality that
\[
  \alpha_2 = \alpha_1 + \alpha \bmod n, \text{ and } \beta_2 = \beta_1 + \beta \bmod n,
\]
since if this is not the case, we can just swap the corresponding values.

The product $\vec{r} \cdot \vy$ consists of the
sum of two circular shifts of \vy: one by $\beta_1$, and the other of $\beta_2$ positions,
denoted by $\shift_{\beta_1}(\vy)$ and $\shift_{\beta_2}(\vy)$, respectively. More formally
\[
  \vec{r} \cdot \vy = \vec{r} \rot(\vy)^T = \shift_{\beta_1}(\vy) + \shift_{\beta_2}(\vy),
\]
where
\begin{align*}
  \supp(\shift_{\beta_1}(\vy))
    &= \{ \alpha_1 + \beta_1 \bmod n, \alpha_2 + \beta_1 \bmod n\}  \\
    &= \{ \alpha_1 + \beta_1 \bmod n, \alpha_1 + \alpha + \beta_1 \bmod n\},
\end{align*}
\text{and}
\begin{align*}
  \supp(\shift_{\beta_2}(\vy))
    &= \{ \alpha_1 + \beta_2 \bmod n, \alpha_2 + \beta_2 \bmod n\} \\
    &= \{ \alpha_1 + \beta_1 + \beta \bmod n, \alpha_1 + \alpha + \beta_1 + \beta \bmod n\}.
\end{align*}

Therefore the weight of $\vec{r} \cdot \vy$ is at most 4, but can be lower if the supports above share some of their entries.
We consider separately the cases when $\alpha = \beta$ and $\alpha \neq \beta$.
These cases are illustrated in Figure~\ref{fig:x_shifts_for_two_cases}.


\begin{figure}[h]
\centering

  \def \nodesize {0.3cm}

  \begin{tikzpicture}[darkstyle/.style={draw,minimum size=\nodesize}]
    \foreach \x in {0,...,10}
      \foreach \y in {0,...,10}
        {
          \node [darkstyle]  (\x{X}\y) at (\nodesize*\x,\nodesize*\y) {};
        }


  \node [darkstyle,fill=black]  (xa1b1) at (\nodesize*1,\nodesize*6) {};
  \node [darkstyle,fill=black]  (xa2b1) at (\nodesize*5,\nodesize*6) {};

  \node [darkstyle,fill=black]  (xa1b2) at (\nodesize*5,\nodesize*2) {};
  \node [darkstyle,fill=black]  (xa2b2) at (\nodesize*9,\nodesize*2) {};


  % \draw [decorate,decoration={brace,raise=4pt},yshift=2pt]
  % (1*\nodesize, 10*\nodesize) -- (5*\nodesize, 10*\nodesize);
  % (1*\nodesize, 10*\nodesize) -- (5*\nodesize, 10*\nodesize);

  % \node [black] {\footnotesize $P_2$};

  \draw[decoration={brace,raise=8pt},decorate]
    (1*\nodesize, 10*\nodesize) -- node[above=10pt] {$\alpha$} (5*\nodesize, 10*\nodesize);


  \draw[decoration={brace,raise=8pt,mirror},decorate]
    (0*\nodesize, 6*\nodesize) -- node[left=10pt] {\rotatebox{90}{$\beta = \alpha$}} (0*\nodesize, 2*\nodesize);

  \node[below= 8pt of 1{X}0] (label_a1) {\rotatebox{90}{$\alpha_1 + \beta_1$}} ;
  \draw[->](label_a1.north)-|(1{X}0.south);

  \node[below= 8pt of 5{X}0] (label_a2) {\rotatebox{90}{$\alpha_1 + \alpha + \beta_1 $}} ;
  \draw[->](label_a2.north)-|(5{X}0.south);

  \node[below= 8pt of 9{X}0] (label_a1_2a) {\rotatebox{90}{$\alpha_1 + 2\alpha + \beta_1 $}} ;
  \draw[->](label_a1_2a.north)-|(9{X}0.south);

  \node[right= 8pt of 10{X}6] (label_b1) {$\beta_1$};
  \draw[->](label_b1.west)--(10{X}6.east);

  \node[right= 8pt of 10{X}2] (label_b2) {$\beta_1 + \beta$};
  \draw[->](label_b2.west)--(10{X}2.east);

  \end{tikzpicture}% NO EMPTY LINE HERE!!!!
  \qquad
  \begin{tikzpicture}[darkstyle/.style={draw,minimum size=\nodesize}]
    \foreach \x in {0,...,10}
      \foreach \y in {0,...,10}
         {
         \node [darkstyle]  (\x{X}\y) at (\nodesize*\x,\nodesize*\y) {};}

  \node [darkstyle,fill=black]  (xa1b1) at (\nodesize*1,\nodesize*6) {};
  \node [darkstyle,fill=black]  (xa2b1) at (\nodesize*5,\nodesize*6) {};

  \node [darkstyle,fill=black]  (xa1b2) at (\nodesize*4,\nodesize*3) {};
  \node [darkstyle,fill=black]  (xa2b2) at (\nodesize*8,\nodesize*3) {};


  % \draw [decorate,decoration={brace,raise=4pt},yshift=2pt]
  % (1*\nodesize, 10*\nodesize) -- (5*\nodesize, 10*\nodesize);
  % (1*\nodesize, 10*\nodesize) -- (5*\nodesize, 10*\nodesize);

  % \node [black] {\footnotesize $P_2$};

  \draw[decoration={brace,raise=8pt},decorate]
    (1*\nodesize, 10*\nodesize) -- node[above=10pt] {$\alpha$} (5*\nodesize, 10*\nodesize);


  \draw[decoration={brace,raise=8pt,mirror},decorate]
    (0*\nodesize, 6*\nodesize) -- node[left=10pt] {$\beta$} (0*\nodesize, 3*\nodesize);

  \node[below= 8pt of 1{X}0] (label_a1) {\rotatebox{90}{$\alpha_1 + \beta_1$}} ;
  \draw[->](label_a1.north)-|(1{X}0.south);

  \node[below= 8pt of 5{X}0] (label_a2) {\rotatebox{90}{$\alpha_1  + \alpha + \beta_1$}} ;
  \draw[->](label_a2.north)-|(5{X}0.south);


  \node[below= 8pt of 4{X}0] (label_a1_b) {\rotatebox{90}{$\alpha_1 + \beta + \beta_1$}} ;
  \draw[->](label_a1_b.north)-|(4{X}0.south);


  \node[below= 8pt of 8{X}0] (label_a1_a_b) {\rotatebox{90}{$\alpha_1 + \alpha + \beta + \beta_1 $}} ;
  \draw[->](label_a1_a_b.north)-|(8{X}0.south);

  \node[right= 8pt of 10{X}6] (label_b1) {$\beta_1$};
  \draw[->](label_b1.west)--(10{X}6.east);

  \node[right= 8pt of 10{X}3] (label_b2) {$\beta_1 + \beta$};
  \draw[->](label_b2.west)--(10{X}3.east);

  \end{tikzpicture}
  \caption{The cases when $\alpha = \beta$ (left), and $\alpha \neq \beta$ (right).}
  \label{fig:x_shifts_for_two_cases}
\end{figure}

\paragraph{Case $\alpha = \beta$.}
In this case, we have:
\begin{align*}
  \supp(\shift_{\beta_1}(\vy))
    &= \{ \alpha_1 + \beta_1 \bmod n, \alpha_1 + \alpha + \beta_1 \bmod n\},
\end{align*}
\text{and}
\begin{align*}
  \supp(\shift_{\beta_2}(\vy))
    &= \{ \alpha_1 + \beta_1 + \alpha \bmod n, \alpha_1 + 2\alpha + \beta_1 \bmod n\}.
\end{align*}

The supports of the shifts share the entry $\alpha_1 + \beta_1 + \alpha \bmod n$.
But notice that this is the only shared entry, since the fact that
$n$ is odd implies $\alpha_1 + \beta_1 \not\equiv \alpha_1 + \beta_1 + 2\alpha \mod n$.
Then, summing the shifts of $\vy$ we get
\[
  \supp(\vec{r} \cdot \vy) = \{ \alpha_1 + \beta_1 \bmod n, \alpha_1 + 2\alpha + \beta_1 \bmod n\}.
\]
Therefore, using the facts that $\alpha \leq \lfloor n/2 \rfloor$ and $n$ is odd, we get
\begin{align*}
  \sigma(\vec{r} \cdot \vy)
    &= \{ \dist_n ( \alpha_1 + \beta_1 \bmod n, \alpha_1 + 2\alpha + \beta_1 \bmod n) : 1\} \\
    &= \{ \dist_n ( 0, 2\alpha \bmod n) : 1\} \\
    &= \{ \dist_n ( 0, 2\alpha) : 1\}.
\end{align*}


\paragraph{Case $\alpha \neq\beta$.}
We begin by showing that the supports of the shifts do not share any entry.
It is clear that $\alpha_1 + \beta_1$ is not equivalent to $\alpha_1 + \beta_1 + \beta$ nor
$\alpha_1 + \alpha + \beta_1 + \beta$ $(\bmod n)$ since $1 < \alpha, \beta \leq (n - 1)/2$.
The same can easily be seen for $\alpha_1 + \alpha + \beta_1$.

Therefore,  spectrum of $\vec{r} \cdot \vy$ consists of the following distances.
\begin{enumerate}
  \item $\dist_n(\alpha_1 + \beta_1, \alpha_1 + \beta_1 + \beta) = \dist_n(0, \beta) = \beta.$
  \item $\dist_n(\alpha_1 + \beta_1, \alpha_1 + \alpha + \beta_1) = \dist_n(0, \alpha) = \alpha.$
  \item $\dist_n(\alpha_1 + \beta_1, \alpha_1 + \alpha + \beta_1 + \beta) = \dist_n(0, \alpha + \beta).$
  \item $\dist_n(\alpha_1 + \beta_1 + \beta, \alpha_1 + \alpha + \beta_1) = \dist_n(\beta, \alpha) = \dist_n(0, \alpha - \beta) = | \alpha - \beta | .$
  \item $\dist_n(\alpha_1 + \beta_1  +\beta, \alpha_1 + \alpha + \beta_1 + \beta) = \dist_n(0, \alpha) = \alpha.$
  \item $\dist_n(\alpha_1 + \alpha + \beta_1, \alpha_1 + \alpha + \beta_1 + \beta) = \dist_n(0, \beta) = \beta.$
\end{enumerate}
Counting the multiplicities of these distances, we get the desired result.
\qed
\end{proof}

\subsection{Probabilistic Analysis of the Key Reconstruction Algorithm}
\label{sec:analysis_randomized_key_reconstruction_algorithm}

In this section, we first analyze our randomized variant of the key reconstruction algorithm,
given as Algorithm~\ref{alg:randomized_reconstruction} in Section~\ref{sec:spectrum_recovery}.
We then compare it to Guo's et al. recursive algorithm, described as Algorithm~\ref{alg:rec_h0}
in the end of Section~\ref{sec:prelim}.

In each iteration, the algorithm performs a random walk down the search
tree, starting from the root $\{0, s\}$, corresponding to $\ell = 2$,
and ending in one of its leaves. Therefore, for the algorithm to succeed in
finding $\vy$,
it has to choose, in each level of the search, an element in
$\supp(\vy)$.

Let $s$ be a distance in $\sigma(\vy)$.
Suppose the search is at level $\ell$, and the algorithm has chosen, until now, the
elements $V_\ell=~\{ v_1 = 0, v_2 = s, \ldots v_\ell \}$, all in the support of $\vy$.
Let $\Gamma_\ell$ be the set of possible choices at level $\ell$, then
\[
    \Gamma_\ell =  \left\{ p \in \left( \{0, \ldots, n - 1\} - V_\ell \right): \dist_n(p, v) \notin D \text{ for all } v \in V \right\}.
\]
We now have exactly $w - |V_\ell|$ good choices for the next level,
which gives us
\[
    \Pr \left( v_{\ell+1} \in \supp(\vy) \mid V_\ell \subset \supp(\vy) \right)
        = \frac{w - |V_\ell|}{|\Gamma_\ell|}
        = \frac{w - \ell}{|\Gamma_\ell|}.
\]
Remember that the spectrum recovery algorithm can find either $\vy$ or $\mirror(\vy)$,
and both are of interest to the attacker.
Therefore, we can write the probability that the algorithm
successfully finds the key as
\begin{align*}
    \Pr (\text{Success})
        &= 2 \prod_{\ell = 2}^{w - 1} \frac{w - \ell}{|\Gamma_\ell|},
\end{align*}
where the product starts at level $\ell = 2$ since the search begins
with $V_2 = \{0, s \}$, and it ends at level $\ell = w - 1$ because this is
the last level in which a choice is made. The factor 2 comes from the mirror test.


Unfortunately, it is not easy to compute the distribution of  $|\Gamma_\ell|$, because of the dependency
between distances in $D$ and  elements in $V_\ell$. However, we can approximate its expected value
using an argument similar to the one used by Guo et al.~\cite{guo2016key}.
Let $\alpha$ be the probability that a distance is not
in $D$, that is $\alpha =  1 - |D|/ \lfloor n/2 \rfloor $.
At level $\ell$, there are $w - \ell$ choices that
are in $\supp(\vy)$, and  $\ell$ positions already in $V_\ell$.
For the other $n - w$ positions that are not in the support of $\vec{y}$, we expect a fraction of
$\alpha^\ell$ of them to have survived the sieves of each level. Therefore, we have
\[
    \EE |\Gamma_\ell| \approx (n - w) \alpha^\ell + w - \ell.
\]

We define the work factor $\textbf{WF}_\textsc{Rand}$ of this algorithm as the
expected number of paths it needs to explore until it finds the secret
key. Then, using the
approximation above, its value is
\begin{align*}
  \WF_\textsc{Rand} &= \frac{1}{\Pr(\text{Success})} \\
  &\approx \frac{1}{2}
  \prod_{\ell = 2}^{w - 1}
  \frac
    { (n - w) \alpha^\ell + w - \ell }
    {w - \ell}
  =
  \frac{1}{2}
  \prod_{\ell = 2}^{w - 1}
  \left(
  \frac
    { (n - w) \alpha^\ell}
    {w - \ell} + 1
  \right).
\end{align*}

Looking at the term in each level $\ell$, they appear to be lower than the corresponding ones
for Guo's et al. algorithm. However, just looking at the expressions, it is not clear how they compare.

To better understand how they compare, consider
Figure~\ref{fig:gjs_vs_randomized}, which shows a concrete comparison of the work factors for both algorithms when
the input $D$ has an increasing number of distances outside the spectrum. We considered parameters for three
HQC variants. Since the range of $|D|$ varies according to the parameters $n$ and $w$, we normalized its value
with respect to the average of the total number of distances outside the spectrum, denoted by $\Delta$.
To estimate $\Delta$ for each pair $(n, w)$, we generated 1000 different random vectors and computed the average
number of distances outside the spectrums.
We can see that the work factor of the randomized algorithm is typically more than 3 orders of magnitude
lower than Guo's et al.~\cite{guo2016key} recursive one.

\begin{figure}[htb!]
  \centering
  \includegraphics[scale=1]{figures/analysis/gjs_vs_randomized_sm.pdf}
  \caption{Comparison between Guo's et al.~\cite{guo2016key} key reconstruction algorithm and our randomized variant with
  respect to the expected number of paths until the secret key is found. For each set of parameters ($n, w$)
  the value of $|D|$ is normalized using the average number of distances outside the spectrum, denoted by $\Delta$.}
  \label{fig:gjs_vs_randomized}
\end{figure}
