\section{Improving the reconstruction algorithm}\label{sec:idea}

The first observation is that, with a slight modification of the
spectrum recovery algorithm for $\hz$, we can simultaneously recover
the spectrum of both $\hz$ and $\ho$. The only reason why Guo et al.
decided to recover the spectrum of only one of $\hz$ or $\ho$ is because
their reconstruction algorithm does not gain any information by using the
spectrum of both. For completeness, Algorithm~\ref{alg:spec_recovery} presents
the algorithm for recovering the spectra of both \hz and \ho.


\begin{algorithm}
  \KwData{$n, r, w, t$ parameters of the QC-MDPC code \\
    \myinput{$\mathcal{D}$ the decoder reaction oracle}
  }
  \KwResult{$\vec{a}_0, \vec{b}_0, \vec{a}_1, \vec{b}_1$}
  \Begin{
    $\vec{a}_0 \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\
    $\vec{b}_0 \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\
    $\vec{a}_1 \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\
    $\vec{b}_1 \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\

    \For{each possible decoding trial $i = 1, 2, \ldots, M$} {
      $\vec{c} \gets $ a random encrypted with error $ \vec{e} = \vec{\vec{e}_0 \| \vec{e}_1}$ \\

      $v = \mathcal{D}(\vec{c})$ \\

      \For{each distance $d$ in $\sigma(\vec{e}_0)$} {
        $\vec{a}_0[d] \gets \vec{a} + v$ \\
        $\vec{b}_0[d] \gets \vec{a} + 1$ \\
      }
      \For{each distance $d$ in $\sigma(\vec{e}_1)$}{
        $\vec{a}_1[d] \gets \vec{a} + v$ \\
        $\vec{a}_1[d] \gets \vec{a} + 1$ \\
      }
    }
    $\vec{p}_0 \gets $ zero-initialized array with $\lfloor r/2 \rfloor$ positions \\

  \Return{$\vec{a}_0, \vec{b}_0, \vec{a}_1, \vec{b}_1$}
  }
  \caption{Estimating the probabilities of error for distances in
    $\sigma(\hz)$ and $\sigma(\ho)$}
  \label{alg:spec_recovery}
\end{algorithm}



% \begin{figure}[!h]
%   \centering
%   \includegraphics[scale=1]{figures/intro/classification_cca2_accuracy.pdf}
%   \caption{Legenda}
%   \label{figRotulo}
% \end{figure}

\begin{figure}[!h]
  \centering
  \includegraphics[scale=1]{figures/intro/100M_cca_dec_annotated.pdf}
  \caption{Legenda}
  \label{figRotulo}

  \includegraphics[scale=1]{figures/intro/30M_cca_dec.pdf}
  \caption{Legenda}
  \label{figRotulo}
\end{figure}

% 0.7340206 51.552795
% 4.404124  60.869564
% 6.6061854 69.35818
% 11.010309 78.46791
% 19.084536 86.54244
% 28.626804 92.546585
% 44.041237 96.06625
% 63.125774 98.13664
% 91.018555   99.37888
% 115.241234  99.58592
% 148.27217   100.2070
% 353.79794   100.41408


Our main idea is to explore the relation
$\ho \mat{B} = \hz$.
Let $Z_0$ and $Z_1$ be sets of indexes of the some of the null entries of $\hz$ and $\ho$, respectively.
Denote by $\mat{B}^{Z_0}$ the matrix formed by 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 respective 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}

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 answer two questions.


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 on the vector $\ho$?
To answer this first question is important because
if the kernel of $\mat{B}^{Z_0}_{Z_1^\prime}$ is a large subspace, then finding a low weight
vector can be costly. The answer is given in the next section, and is that
the kernel consists only of $\ho$ with probability approximately $1 - 1/2^{|Z_1| + |Z_2| - r}$. Therefore  we want the sum $|Z_1| + |Z_2|$ to be larger than $r$, but not necessarily much larger since the probability increase fast with respect to the difference.

How some information about the spectra of both $\hz$ and $\ho$ can help us
construct the sets $Z_0$ and $Z_1$?
Let us consider $\sigma(\hz)$ the spectrum of $\hz$. Suppose we know that $d$ is in
$\sigma(\hz)$, and we also know that the distances $f_1, \ldots, f_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
\[
  [
    \,
    \rlap{$
      \phantom{0 \, * \, \ldots \, * \,}
      \overbrace{
        \phantom{
          1 \, * \, \ldots \, * \, 0 \, * \, \ldots \, *
          0 \, *, \, \ldots, \, * \, 1 \,
        }
      }^d
    $}
    \rlap{$
      \underbrace{\phantom{\, 0 \, * \, \ldots \, * \, 1 \,}}_{f_1}
    $}
    \, 0 \, * \, \ldots \, *
    \underbrace{\, 1 \, * \, \ldots \, * \, 0 \,}_{f_1}
    * \, \ldots \, *
    \rlap{$
      \underbrace{\phantom{\, 0 \, * \, \ldots \, * \, 1 \,}}_{f_1}
    $}
    \, 0 \, * \, \ldots \, *
    \underbrace{\, 1 \, * \, \ldots \, * \, 0 \, }_{f_1}
    * \ldots * \,
  ].
\]
And if we consider all other $f_i$, it is possible to know the positions of a
number of zeros in this shift of $\hz$, which will be our set $Z_0$. An
analogous construction can be made for $Z_1$. In the next section, we discuss
the relation between the number of known distances inside and outside of the
spectrum of $\hz$ ($\ho$), and the size of the set $Z_0$ ($Z_1$) we can construct.


The problem we face now is that $Z_0$ and $Z_1$ might not be related to the
same amount of shifts for $\hz$ and $\ho$, respectively. To deal with it, we
can fix one of the sets, namely $Z_1$, and try, for all $i = 0, 1, \ldots, r - 1$,
to find a low weight row in the kernel of the matrix $\mat{B}_{Z_1^\comp}^{Z_0^{(i)}}$, where $Z_0^{(i)}$
is the set of indexes in $Z_0$, circular shifted by $i$ positions.


We now describe our algorithm for recovering the key, which is described in pseudo-code
in Algorithm~\ref{alg:proposed_algo}.
Let $D_0$ and $D_1$ be sets of distances such that $D_0 \cap \sigma(\hz) = \emptyset$ and
$D_1 \cap \sigma(\ho) = \emptyset$. Let $s_0$ and $s_1$ be distances which are known to
be in $\sigma(\hz)$ and $\sigma(\ho)$, respectively.

Fix $\hz$ as the row of $\mat{H}_0$ that starts with an 1. Then we can take $Z_0$ as the set of indexes
$i$ such that the circular distance from 0 to $i$ is not in the spectrum of $\hz$. We want to construct
a $Z_1$ in a similar fashion, but since we fixed $\hz$, we cannot fix $\ho$. Therefore, for every index $i$ of $\ho$ we build a set $I_i$ which is the set of positions which can contain that are in the spectrum assuming that for $Z_1$ for every index $i$ of $\ho$, that is built

For all index $i$ of $\ho$, we build a set $I_i$ of all indexes $p$ of $\hz$ such that the circular distance between $i$ and $p$ is in $S_1$. The sets $I_i$ are candidates for $Z_1^\comp$. Finally, to find $\ho$,
we look for a vector of $w$ in the left kernel of the matrix $\mat{B}^{Z_0}_{I_1}$, for all $I_i$.


\begin{algorithm}[]
  \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$ or $\perp$}

  $Z_0 \gets \{ i \in [r]: \dist(0, i) \in D_0 \text{ or } \dist(s_0, i) \in D_0 \}$ \\
  $\mat{B}_\alpha \gets $ submatrix of $\mat{B}$ taking columns from $Z_0$ \\

  \For{$p = 1$ to $r$}{
    $q \gets p + s_1 \mod r$ \\
    $\bar{Z}_1 \gets \{ i \in [r]: \dist(p, i) \notin D_1 \text{ and } \dist(q, i) \notin D_1 \}$

    $\mat{B}_\beta \gets $ submatrix of $\mat{B}_\alpha$ taking rows from $\bar{Z}_1$ \\
    $\mat{K} \gets $ left kernel matrix of $\mat{\hat{B}}$ in row reduced echelon form \\
    \For{each row $\vec{v}$ in $\mat{K}$}{
      \If{$\weight(\vec{v}) = w/2$}{
        $\vec{h_1} \gets \vec{0} \in \Fb^r$ \\
        \For{each $i$ = 1 to $|\vec{v}|$}{
          $\vec{h_1}[Z_1[i]] \gets \vec{v}[i]$
        }
        \Return{$\ho$}
      }
    }
  }
  \Return{$\perp$}
 \caption{Proposed key recovery algorithm}
\end{algorithm}

The next sections are dedicated to show that the algorithm has good performance and typically finds $\ho$.
