\section{Preliminaries}

In this brief section, 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 an 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}$. Analogously, 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}[Syndrome]
    The \emph{syndrome} of a vector $\vec{v}$, denoted by $s(\vec{v})$, with relation to a code that admits a parity
    check matrix $\mat{H}$, is the vector
    $$
        s(\vec{v}) = \vec{v}H^T.
    $$

    By this definition, it should be clear that the syndrome of a vector is $\vec{0}$ if and only if
    this vector is an element of the code.
\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 \emph{Hamming distance} between two vectors in the same binary linear subspace, denoted by $\dist(\vec{u}, \vec{v})$,
    is the number of coordinates in which they differ. Equivalently,
    $\dist(\vec{u}, \vec{v}) = \weight(\vec{u} \oplus \vec{v})$.
\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 what 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}$.

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


Since the distance spectrum is the same for all the rows of a circulant matrix $\mat{V}$,
we can define the spectrum $\mat{V}$ as the spectrum of one of it's rows.


\begin{definition}
    Let $\mat{V}$ be an matrix of $\Fb^{r \times r}$. Then the spectrum of $\mat{V}$ is the
    set
    \[
        \sigma(\mat{V}) = \sigma(\vec{v}_1),
    \]
    where $\vec{v}_1$ is the first row of $\mat{V}$.
\end{definition}
