%!TEX root = paper.tex

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

We review some concepts from Coding Theory.

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

\begin{definition}[Generator and parity-check matrix]
    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}$.

    Since we are interested in codes defined by their parity-checks, we
    usually consider the co-dimension~$r = n - k$ of the code, instead of its dimension~$k$.
\end{definition}

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

\begin{definition}
    The circular distance between the indexes $i$ and $j$ in a vector of length
    $r$ is
    \[
        \dist_r(i, j) =
        \begin{cases}
            |i - j|     & \text{ if } |i - j| < \lfloor r/2 \rfloor, \\
            r - |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 a reaction 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}$.
Note that spectrum of a vector is invariant for its circular shifts.

\begin{definition}
    Let $\vec{v} = [v_1, v_2, \ldots, v_r]$ be an element of $\Fb^r$. Then the spectrum of $\vec{v}$ is the
    set
    \[
        \sigma(\vec{v}) = \{ \dist_r(i, j) : i \neq j, \, {v}_i = 1, \text{ and } {v}_{j} = 1 \}.
    \]
\end{definition}

When describing the proposed algorithm, it is useful to consider the circular shift
of a set of indexes, defined next.


\begin{definition}
    Let $Z \subset [r] = \{ 1, 2, \ldots, r \}$ be a set of possible indexes of a vector in $\Fb^r$. Then the circular
    shift of $Z$ by $p$ positions is the set
    \[
        Z^{(p)} = \{ i + p \mod r : i \in Z \}.
    \]
\end{definition}
