%!TEX root = paper.tex

\section{Background}
\label{sec:prelim}


\begin{definition}[Linear codes]
    A \emph{binary $[n, k]$-linear code} is a $k$-dimensional linear subspace of $\mathbb{F}_2^n$,
    where $\Fb$ denotes the binary field.
\end{definition}

\begin{definition}[Generator and parity-check matrices]
    Let $\mathcal{C}$ be a binary $[n, k]$-linear code. If $\mathcal{C}$ is the linear subspace spanned by
    the rows of a matrix $\mat{G}$ of $\Fb ^{k \times n}$, we say that $\mat{G}$ is a \emph{generator matrix}
    of $\mathcal{C}$. Similarly, if $\mathcal{C}$ is the kernel of a matrix $\mat{H}$ of  $\Fb^{(n - k) \times n}$,
    we say that $\mat{H}$ is a  \emph{parity-check matrix} of $\mathcal{C}$.
\end{definition}

\begin{definition}[Weight]
    The Hamming \emph{weight} of a vector $\vec{v}$, denoted by $\weight(\vec{v})$, is the number of its non-null entries.
\end{definition}


\begin{definition}[Support]
    The \emph{support} of a vector $\vec{v}$, denoted by $\supp(\vec{v})$, is the set of indexes of its non-null entries.
\end{definition}

We use zero-based numbering for the vectors indexes as we believe it allows more concise descriptions in
some of the algorithms and analysis.



\begin{definition}[Cyclic matrix]
The \emph{cyclic matrix} defined by a vector $\vec{v} = [v_0, \ldots, v_{n - 1}]$, is the matrix
\[
  \rot(\vec{v}) =
  \begin{bmatrix}
      v_{0}     & v_{n - 1} & \ldots & v_{1} \\
      v_{1}     & v_{0}     & \ldots & v_{2} \\
      \vdots    & \vdots    & \ddots & \vdots \\
      v_{n - 1} & v_{n - 2} & \ldots & v_{0}
  \end{bmatrix}.
\]
\end{definition}

\begin{definition}[Vector product]
The \emph{product of two vectors} $\vec{u}, \vec{v} \in \Fb^n$ is given as
\[
  \vec{u} \cdot \vec{v} = \vec{u} \rot(\vec{v})^T = \left( \rot(\vec{v}) \vec{u}^T \right)^T
  = \vec{v} \rot(\vec{u})^T = \vec{v} \cdot \vec{u}.
\]
\end{definition}


\begin{definition}[Syndrome decoding problem]
  Consider the following input: a random binary matrix $\mat{H} \in \Fb^{k \times n}$, a random vector
  $\vec{s} \in \Fb^k$, and an integer $w > 0$. The syndrome decoding problem asks for a $\vec{v}$ of weight
  $w$ such that $\vec{v} \mat{H}^T = \mat{s}$.

  The quasi-cyclic syndrome decoding problem is a restriction of the syndrome decoding problem, in which
  $\mat{H}$ is a block matrix consisting of cyclic blocks.
\end{definition}
The syndrome decoding problem is proven to be
\textbf{NP}-hard~\cite{berlekamp1978inherent}.
Despite no complexity result on the quasi-cyclic variant, it is considered hard since all known
decoding algorithms that exploit the cyclic
structure have only a small advantage over general decoding algorithms for the non-cyclic case.

\begin{definition}[Circular distance]
    The \emph{circular distance} between the indexes $i$ and $j$ in a vector of length
    $n$ is
    \[
        \dist_n(i, j) =
        \begin{cases}
            |i - j|     & \text{ if } |i - j| \leq \lfloor n/2 \rfloor, \\
            n - |i - j| & \text{ otherwise.}
        \end{cases}
    \]
\end{definition}

We next define the spectrum of a vector, which is a crucial concept for the rest of the
paper. The importance of the spectrum for the attack comes from the fact that it is
precisely the spectrum of the key that can be recovered by the timing attack.
Intuitively, the spectrum of a binary vector $\vec{v}$ is the set of circular distances
that occur between two non-null entries of $\vec{v}$.

\begin{definition}[Spectrum of a vector]
    Let $\vec{v} = [v_0, v_1, \ldots, v_{n - 1}]$ be an element of $\Fb^n$. Then the \emph{spectrum} of $\vec{v}$ is the
    set
    \[
        \sigma(\vec{v}) = \{ \dist_n(i, j) : i \neq j, \, {v}_i = 1, \text{ and } {v}_{j} = 1 \}.
    \]
    In some cases, it is important to consider the multiplicity of each distance $d$, that is
    the number of pairs of non-null entries that are at distance $d$ apart. In such cases,
    we abuse notation and write $(d: m) \in \sigma(\vec{v})$ to denote that $d$ appears
    with multiplicity $m$ in vector $\vec{v}$.
\end{definition}


\begin{definition}[Mirror of a vector]
    Let $\vec{v} = [v_0, v_1, \ldots, v_{n - 1}]$ be an element of $\Fb^n$. Then the \emph{mirror} of $\vec{v}$ is the
    vector
    \[
        \mirror(\vec{v}) = [v_{n - 1}, v_{n - 2} ,\ldots, v_0].
    \]
    We sometimes abuse notation and write $\mirror(V)$, where $V$ is the support of a vector $\vec{v}$,
    to represent the support of the mirror of $\vec{v}$.
\end{definition}

Notice that the spectrum of a vector is invariant with respect to its circular shifts and its mirror.

Guo et al.~\cite{guo2016key} showed that it is possible to reconstruct a sparse vector from
its spectrum. To solve this problem, they propose an algorithm that consists of a simple pruned
depth-first search. Its description is given as
Algorithm~\ref{alg:rec_h0}.\footnote{Here we present a slightly more general version of Guo's et al. reconstruction algorithm
that does not require the key's spectrum to be completely determined, but the idea is the same.}
The main argument by Guo et al. for the efficiency of their algorithm is that unfruitful branches are
pruned relatively early in the search.



\begin{algorithm}[!ht]
  \KwData{$n, w$ the length and weight of the secret vector $\vy$ \\
    \myinput{$D$ a set of distances outside $\sigma(\vy)$}\\
    \myinput{$s$ a distance inside $\sigma(\vy)$}\\
    \myinput{$V$ the partially recovered support of a shift of \vy (initially set to $\{0, s\}$,
             where $s \in \sigma(\vy))$ is known } \\
  }
  \KwResult{$\vec{V}$ the support of some shift of \vy, or $\perp$ if $\sigma(\vy)$ is an invalid spectrum}
  \Begin{
    \If {$|V| = w$}{
      \If {$V$ is the support of a shift of $\vy$}{ \label{line:shady_gjs}
        \Return{$V$}
      }
      \ElseIf {$\mirror(V)$ is the support of a shift of $\vy$}{ \label{line:mirror_test_gjs}
        \Return{$\mirror(V)$}
      }
      \Else{
        \Return{$\perp$}
      }
    }
    \For{each position $j = 1, \ldots, n - 1$ which are not in $V$}{
      \If{$\dist_n(v, j) \not\in D$ for all $v$ in $V$} { \label{line:sieve_gjs}
        Add $j$ to $V$ \\
        $\var{ret} \gets $ recursive call with the updated set $V$ \\
        \If{$ \var{ret} \neq \perp $}{
          \Return{$V$}
        }
        Remove $j$ from $V$
      }
    }
    \Return{$\perp$}
  }
  \caption{GJS key reconstruction algorithm~\cite{guo2016key}}
  \label{alg:rec_h0}
\end{algorithm}



Let $\alpha$ be the fraction of the
$\lfloor n/2 \rfloor $ possible distances that are not in $D$, that is
$\alpha = 1 - |D|/\lfloor n/2 \rfloor$.
For each new level in the search tree, it is expected that a fraction $\alpha$ of
the possible positions in the previous level survive the sieve imposed by
line~\ref{line:sieve_gjs}.
Let $\textsc{MaxPaths}$ be the total number of paths that Guo's et al.~\cite{guo2016key} algorithm
can explore. Then
\[
  \textsc{MaxPaths} = \prod_{\ell = 2}^{w - 1} \max \left( 1, \lfloor n/2 \rfloor \alpha^\ell \right)
  = \lfloor n/2 \rfloor ^\phi \alpha^{\phi(\phi + 3)/2},
\]
where $\ell$ represents the level in the search tree, and $\phi$ is the level at which each node has an expected
number of child nodes lower than or equal to 1.
Notice that, on average, the mirror test in line~\ref{line:mirror_test_gjs}
cuts in half the number of paths the algorithm needs to explore until
it finds the key. From the remaining paths, we expect that half of them have to be taken until the key is found.
Therefore, considering $\WF_\textsc{GJS}$ to be the average number of paths the algorithm explores until a key is found,
we have
\[
  \WF_\textsc{GJS} =  \frac{1}{4} \textsc{MaxPaths} = \frac{1}{4} \lfloor n/2 \rfloor ^\phi \alpha^{\phi(\phi + 3)/2}.
\]
