%!TEX root = paper.tex

\section{Our reconstruction algorithm}
\label{sec:idea}
Up to this point, we analyzed the algorithm by Guo et al.. From this section on, we describe our
original results. We begin by considering the reconstruction algorithm for the case where
the number of cyclic blocks in the secret matrix $\mat{H}$ is $n_0 = 2$, because the exposition is
simpler in this case. We then discuss how to adapt the algorithm for the case where $n_0 = 2$
for $n_0 \geq 3$.

\subsection{Case $n_0 = 2$}

Consider the public generator matrix of a QC-MDPC with $n_0 = 2$ given as
\begin{equation*}
\label{eq:mdpc_gen_matrix}
  \mat{G} = \left[
    % \begin{matrix}
      \qquad \mat{I} \qquad
    % \end{matrix}
    \, \middle\vert \,
    \begin{matrix}
      {\left( \mat{H}_{1}^{-1} \cdot \mat{H}_0 \right)}^T \, \\ \addlinespace
    \end{matrix}
  \right].
\end{equation*}
Let $\mat{B} = \mat{H}_{1}^{-1} \mat{H}_0$ be the transpose
of the right block of
the public generator matrix.
Our main idea is to explore the relation
$\ho \mat{B} = \hz$, where $\ho$ and $\hz$ are corresponding lines
of the matrices $\mat{H}_1$ and $\mat{H}_0$, respectively.
Let $Z_0$ and $Z_1$ be sets of indexes of some of the null entries of $\hz$ and $\ho$,
respectively.
Denote by $\mat{B}^{Z_0}$ the matrix consisting of the columns of $\mat{B}$ whose indexes are in $Z_0$.
Then it should be clear that
\begin{align*}
    \ho \mat{B}^{Z_0} = \vec{0}.
\end{align*}

Note that we can discard the entries of $\ho$ whose indexes are in $Z_1$,
if we discard the corresponding columns in $\mat{B}^{Z_0}$. Let $Z_1^\comp$ be the complement of $Z_1$ with respect to the possible indexes of $\ho$. Then

\begin{align*}
    \ho^{Z_1^\comp} \mat{B}^{Z_0}_{Z_1^\comp} = \vec{0},
\end{align*}
where $\ho^{Z_1^\comp}$ is the vector consisting of the columns of $\ho$ whose indexes are
in $Z_1^\comp$, and $\mat{B}^{Z_0}_{Z_1^\comp}$ is the matrix consisting of the lines from
$\mat{B}^{Z_0}$ whose indexes are in $Z_1^\comp$.
In other words, $\ho^{Z_1^\comp}$ is in the left kernel of the matrix $\mat{B}^{Z_0}_{Z_1^\prime}$. Then we can compute the kernel matrix of $\mat{B}^{Z_0}_{Z_1^\prime}$ and hope to find $\ho^{Z_1^\comp}$
in one of its columns. To use this in our favor, we need to solve three problems,
which we discuss next.

The first problem is that if the kernel of $\mat{B}^{Z_0}_{Z_1^\prime}$ is a large subspace, then finding a low weight vector in it can be
very difficult. To deal
with it, we must find out how large must the sets $Z_0$ and $Z_1$ be so that the kernel of $\mat{B}^{Z_0}_{Z_1^\prime}$ consists only of the vector $\ho$.
The answer is given in Section~\ref{sec:z0_z1_sizes}, and it is that
the kernel consists only of $\ho$ with approximate probability $1 - 1/2^{|Z_0| + |Z_1| - r}$. Therefore  we want the sum $|Z_0| + |Z_1|$ to be larger than $r$, but not necessarily much larger since the probability increases fast with respect to the difference.


The second problem is to find how much information we need about the
spectrums of both
 $\hz$ and $\ho$ so that we can build large enough sets $Z_0$ and $Z_1$.
Let us consider $\sigma(\hz)$ the spectrum of $\hz$. Suppose we know that $s_0$ is in
$\sigma(\hz)$, and we also know that the distances $d_1, \ldots, d_l$ are not in $\sigma(\hz)$. Letting $*$ denote
unknown entries, we know that there
must exist a shift of $\hz$ which has the following format
\mathindent=3mm % <-- [A]
\[
  [
    \rlap{$
      \phantom{0  *  \ldots  * }
      \overbrace{
        \phantom{
          1  *  \ldots  *  0  *  \ldots  *
          0  *,  \ldots,  *  1
        }
      }^{s_0}
    $}
    \rlap{$
      \underbrace{\phantom{ 0  *  \ldots  *  1 }}_{d_1}
    $}
     0  *  \ldots  *
    \underbrace{ 1  *  \ldots  *  0 }_{d_1}
    *  \ldots  *
    \rlap{$
      \underbrace{\phantom{ 0  *  \ldots  *  1 }}_{d_1}
    $}
     0  *  \ldots  *
    \underbrace{ 1  *  \ldots  *  0  }_{d_1}
    * \ldots *
  ].
\]
\mathindent=7mm % <-- [A]
Further, if we consider all other $d_i$, it is possible to know the positions of
a hopefully large number of zeros in this shift of $\hz$, which will be our set $Z_0$.
To get a distance $s_0$ that is in the spectrum $\sigma(\hz)$ with high
probability, one can take the distance with least probability of failure estimated
by the spectrum recovery algorithm.
An analogous construction can be made for $Z_1$. In Section~\ref{sec:d_exclusion},
we discuss the relation between the number of known distances inside and outside $\sigma(\hz)$ and $\sigma(\ho)$, and the sizes of the sets $Z_0$ and $Z_1$, respectively.


The third and last problem is that the positions $Z_0$ and $Z_1$ are built based only
on \emph{circular} distances. As such, there are no guaranties that $Z_0$ and $Z_1$
are positions of zeros in \emph{shifts by the same number of positions} of both \hz and \ho,
respectively. To deal with it, we
can fix one of the sets, namely $Z_1$, and try iteratively, for each $p = 0, 1, \ldots, r - 1$,
to find a low weight row in the kernel of the matrix $\mat{B}_{Z_1^\comp}^{Z_0^{(p)}}$,
where $Z_0^{(p)}$ is the set of indexes in $Z_0$, circularly
shifted by $p$ positions.

\begin{algorithm}[!h]
  \label{alg:proposed_algo}

  \KwData{ $r, w$ parameters of the QC-MDPC code to be broken\\
  \myinput{   $D_0$ a set of distances not in the spectrum of $\hz$}
  \myinput{   $D_1$ a set of distances not in the spectrum of $\ho$ }
  \myinput{   $s_0$ a distance in the spectrum of $\hz$ }
  \myinput{   $s_1$ a distance in the spectrum of $\ho$ }
  \myinput{   $\mat{B}$ the right block of the public generator matrix }
  }

  \KwResult{$\ho$ which is some line of the matrix $\mat{H}_1$, 
  or $\perp$ if $\ho$ could not be found}

  $Z_1^\comp \gets \{ i \in [r]: \dist(1, i) \notin D_1 \text{ and }
    \dist(s_1 + 1, i) \notin D_1 \}$ \label{line:z1} \\
  $\mat{B}_{Z_1^\comp} \gets $ rows of $\mat{B}$ whose indexes are in $Z_1^\comp$
    \label{line:bz1} \\


  \For{$p = 0$ to $r - 1$}{ \label{line:main_loop}
    $Z_0 \gets \{ i + p \mod r: \dist(1, i) \in D_0 \text{ or } \dist(s_0 + 1, i) \in D_0 \}$ \label{line:z0} \\

    $\mat{B}^{Z_0}_{Z_1^\comp} \gets $ columns of $\mat{B}^{Z_1^\comp}$ whose indexes
      are in $Z_0$ \label{line:bz0z1} \\

    $\mat{K} \gets $ left kernel matrix of $\mat{B}^{Z_0}_{Z_1^\comp}$
      \label{line:kernel} \\
    \If{$\dim \mat{K} = 1$}{
      $\vec{v} \gets $ the only row in $\mat{K}$ \\
      \If{$\weight(\vec{v}) \leq w$}{ \label{line:weight}
        $\ho  \gets \vec{0} \in \Fb^r$ \\
        \For{each $i$ = 1 to $|\vec{v}|$}{ \label{line:v_loop}
          $\ho [Z_1[i]] \gets \vec{v}[i]$
        }
        \Return{$\ho$}
      }
    }
  }
  \Return{$\perp$}
 \caption{Proposed key recovery algorithm}
\end{algorithm}

We now put
everything
together to give a full description of
our algorithm to
reconstruct the key as Algorithm~\ref{alg:proposed_algo}.
Since the algorithm is not recursive and uses common operations,
it is straightforward to compute its complexity.

\begin{lemma}
Let $\mat{H} = [ \mat{H}_0 | \mat{H}_1 ]$ be the secret matrix of an $[n, r, w]$-QC-MDPC code.
Let $Z_0$ be a set of indexes of null entries in some line of $\mat{H}_0$. Similarly,
let $Z_1$  be a set of indexes of null entries in some line of $\mat{H}_1$.
Consider $Z_1'$ to be the complement of $Z_1$ with respect to all possible indexes, that is
$Z_1' = [r] - Z_1$.
Then the complexity of Algorithm~\ref{alg:proposed_algo} is
\mathindent=0mm % <-- [A]
  \[
    \mathcal{O} \left( r + r|Z_1^\prime| + r \left( r + |Z_0||Z_1^\comp| +
      |Z_1^\comp|^2  |Z_0 + Z_1^\comp| + |Z_1^\comp| \right) \right).
  \]
  \mathindent=7mm % <-- [A]
Further, since both $|Z_0|$ and $|Z_1^\comp|$ are $\mathcal{O}(r)$, the complexity of
the attack can be simplified to $\mathcal{O}(r^4)$.
\end{lemma}

\begin{proof}

We analyze the cost of each line of Algorithm~\ref{alg:proposed_algo}.
Lines~\ref{line:z1} and~\ref{line:z0} are $\cO(r)$.
The cost of building $\mat{B}_{Z_1^\prime}$ in
line~\ref{line:bz1} is $\cO(r|Z_1^\prime|)$, and the cost of building
$\mat{B}_{Z_1^\prime}^{Z_0}$ in line~\ref{line:bz0z1} is $\cO(|Z_0||Z_1^\prime|)$.
The loop in line~\ref{line:main_loop} performs $r$ iterations in the worst case. The kernel computation in line~\ref{line:kernel} is the most expensive computation,
and it costs $|Z_1^\prime|^2 |Z_1^\prime + Z_0|$. The weight computation in line~\ref{line:weight}
costs $\cO(r)$. Finally, the loop in line~\ref{line:v_loop} iterates $|\vec{v}| =
|Z_1^\prime|$ times. Putting these costs together gives the desired result.

\QED

It is important to note that the lemma above does not say anything about the probability
of the algorithm finding the key. It only states that the algorithm runs in $\cO(r^4)$,
whether it finds the key or not.


\end{proof}

\subsection{Case $n_0 \geq 3$}
\label{sec:case_big_n0}

When $n_0 \geq 3$, the public generator matrix $\mat{G}$ is given by
Equation~\ref{eq:mdpc_gen_matrix}, that is
\begin{equation*}
  \mat{G} = \left[
    % \begin{matrix}
      \quad \mat{I} \quad
    % \end{matrix}
    \, \middle\vert \,
    \begin{matrix}
      \quad \mat{B_0}^T \quad \\ \addlinespace
      \quad \mat{B_1}^T \quad \\ \addlinespace
      \quad \vdots \quad    \\ \addlinespace
      \quad \mat{B_{n_0 - 2}}^T \quad\,
    \end{matrix}
  \right],
\end{equation*}
where $\mat{B}_i = {\left( \mat{H}_{n_0 - 1}^{-1} \cdot \mat{H}_i \right)}$
for each $i = 0, 1, \ldots, n_0 - 2$.

Then we can write, for each $i$, an equation of the form
$\mat{H}_{n_0 - 1} \mat{B}_i = \mat{H}_i$, where $\mat{B}_i$ is known,
and we can obtain information on the spectrums of $\mat{H}_{n_0 - 1}$ and
$\mat{H}_i$ by adapting Algorithm~\ref{alg:spec_recovery} to the corresponding
number of blocks $n_0$. Therefore, we can use our algorithm to recover $\mat{H}_{n_0 - 1}$
and $\mat{H}_i$. Once $\mat{H}_{n_0 - 1}$ is recovered, all the other
$\mat{H}_i$ blocks can be recovered because $\mat{H}_i = \mat{H}_{n_0 - 1} \mat{B}_i$.

The complexity of the reconstruction algorithm when $n_0 \geq 3$ is the same as
when $n_0 = 2$, that is $\cO(r^4)$. The weight of each block of $\mat{H}$ when
$n_0 \geq 3$ is slightly higher than for $n_0 = 2$. For example, for 80 bits
of security, the weight of each block of $\mat{H}$ is around $90/2 = 45$ when $n_0 = 2$, and
around $220/4 = 55$ when $n_0 = 4$. When the number of blocks $n_0$ increases,
the size of $r$ gets smaller, for the same security level. This implies that the blocks
of $\mat{H}$ are less sparse when $n_0 \geq 3$ than when $n_0 = 2$, which can
impact negatively on the probability of the key reconstruction algorithm finding the key.
This increased density is also bad for Guo's et al. algorithm, which has to explore 
a larger search tree.

\mbox{}

Upon preparation of this paper, it came to our knowledge
that the linear relation $\ho \mat{B} = \hz$
was also explored by Rossi et al.~\cite{rossiside}.
However our algorithm is significantly different than theirs, mainly because we
use information on both $\vec{h}_0$ and $\vec{h}_1$, while their algorithm uses
only information on $\vec{h}_0$.
This allows our algorithm to perform better.


The next sections are to show how to estimate the probability that the attack
succeeds in recovering the key, and its relation
to the size of the $d$-exclusion obtained by the spectrum recovery algorithm.
