\section{OUT}
The original reconstruction algorithm by Guo et al. works by reconstructing

In this section, we consider the family of $(9602, 4801, 90)$-QC-MDPC codes which provides a security level of 80 bits~\cite{misoczki2013mdpc}. The private generator matrices of the codes in this family have two cyclic blocks
fully described by their first rows $h_0$ and $h_1$.

The systematic public generator matrix is
\begin{equation}
  \label{eq:mdpc_matriz_geradora}
  G = \left[
    \qquad I \qquad
    \, \middle\vert \,
    \left( H_{1}^{-1} \cdot H_0 \right)^T \, 
  \right].
\end{equation}


With some basic linear algebra manipulation of $G$, the attacker can build a systematic parity check matrix given by
\begin{equation}
  \label{eq:mdpc_matriz_geradora}
  \pH = \left[
    \qquad I \qquad
    \, \middle\vert \,
    \qquad B \qquad \, 
  \right],
\end{equation}
where $B = H_{0}^{-1} H_1.$

Taking only the first rows of $H_0$ and $H_1$, we can write
\begin{equation} \label{eq:h0B_eq_h1}
    h_0B = h_1.
\end{equation}

This way, we can think of $h_0$ as the linear combination of the rows of $B$ which gives us $h_1$.
Our goal is to recover $h_0$ from $B$ given that $\weight(h_0)~=~\weight(h_1)~=~45$, and using some information about the spectrum of $h_1$.

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

\begin{lemma}
\label{lem:binneg}
Consider a $(n, r, w)$-QC-MDPC code defined by a quasi-cyclic parity matrix with two cyclic blocks with 
signatures $h_0$ and $h_1$. Let $P$ be a random variable that represents the position of the second non-null entry of $\hz$. Then $P$ follows a negative binomial distribution with success probability $1 - \frac{w}{n}$ and stopping the experiment after 2 failures.
\end{lemma}

\begin{example}[Lemma~\ref{lem:binneg}]
For our code Lemma~\ref{lem:binneg} 
\end{example}

\begin{lemma}
Let $I$ be a set of indexes of null entries of $h_1$. Let $K$ be the basis matrix in row reduced echelon form
of the kernel of the linear transformation $B_I(\vec{v}) = \vec{v}B_I$. If the index of the second non-null entry 
of $\hz$ is greater than or equal to the the position of the first non-null entry of the last row of $K$, then $\
hz$ is a row of $K$.
\end{lemma}

\begin{proof}
Suppose that the index of the second non-null entry of $\hz$ is greater than or equal to the position of the last 
row of $K$. Then all linear combinations of two or more 
rows of $K$ will necessarily have more than zero non-nulls entries between the first and second positions of the 
ones of $\hz$. But, from Equation~\ref{eq:h0B_eq_h1} and the definition of $I$, it follows that \hz must be in the kernel of $B_I$. Therefore \hz must be one of the rows of $K$.

\end{proof}

\begin{lemma}
Let $p_i$ be the probability that  between the set of indexes of null entries of $h_1$. Let $K$ be the basis matrix in row reduced echelon form
of the kernel of the linear transformation $B_I(\vec{v}) = \vec{v}B_I$. If the index of the second non-null entry 
of $\hz$ is greater than or equal to the the position of the first non-null entry of the last row of $K$, then $\
hz$ is a row of $K$.
\end{lemma}

\begin{proof}
Suppose that the index of the second non-null entry of $\hz$ is greater than or equal to the position of the last 
row of $K$. Then all linear combinations of two or more 
rows of $K$ will necessarily have more than zero non-nulls entries between the first and second positions of the 
ones of $\hz$. But, from Equation~\ref{eq:h0B_eq_h1} and the definition of $I$, it follows that \hz must be in the kernel of $B_I$. Therefore \hz must be one of the rows of $K$.

\end{proof}


For each row of $K$ let $D_i$ be the distance between the first 

Consider the polynomial $b(x) =$ 


\def\hdots@for#1#2{\multicolumn{#2}c%
  {\m@th\dotsspace@1.5mu\mkern-#1\dotsspace@
   \xleaders\hbox{$\m@th\mkern#1\dotsspace@.\mkern#1\dotsspace@$}%
           \hskip\z@\@plus 1filll
   \mkern-#1\dotsspace@}%
   }


\begin{lemma}

Let $\vec{C}$ be an $r \times r$ circular matrix without repeated elements within its rows.
Consider the submatrix $\vec{S}$ of $\vec{C}$ formed
by taking $u$ random different rows of $\vec{C}$ indexed by $g_1 < g_2 < \ldots < g_u = g_0$. For each $i \in \{ 2, \ldots, r \}$, let 
$N_i$ be a random variable that counts the number of entries in column $i$ of $\vec{S}$
that are entries of at least one of the first $i - 1$ columns of $S$. 
Then
\[
  N_k = \sum_{d = 1}^{k - 1} \Gamma_d, 
\]

where $\Gamma_d$ is the number of elements in the set $ \{ i: g_{i} - g_{i-1} \equiv d \mod r \} $.

\end{lemma}


\begin{proof} We can assume without loss of generality that matrix $\vec{C}$ is the
circulant given by
\[
  \vec{C} = 
    \begin{bmatrix}
  \vec{c}_1 \\
  \vec{c}_2 \\
  \vec{c}_3 \\
  \vdots \\
  \vec{c}_r
  \end{bmatrix} 
  =
  \begin{bmatrix}
    1 & r     & r-1  & \ldots & 2 \\
    2 & 1     & r    & \ldots & 3\\
    3 & 2     & 1    & \ldots & 4 \\
    \vdots & \vdots  & \vdots & \ddots & \vdots \\
    r & r - 1 &  r - 2 & \ldots & 1
  \end{bmatrix}.
\]

Take the rows of $\vec{C}$ indexed by $g_1 < g_2 < \ldots < g_u$ and construct the submatrix $S$ with these rows, obtaining 
\[
  \vec{S} = 
  \begin{bmatrix}
  \vec{c}_{g_1} \\
  \vec{c}_{g_2} \\
  \vdots \\
  \vec{c}_{g_u}
  \end{bmatrix}
  % = 
  % \begin{bmatrix}
  % \vec{s}_1 \\
  % \vec{s}_2 \\
  % \vdots \\
  % \vec{s}_u
  % \end{bmatrix}
  .
\]


We say that the index $g_i$ precedes $g_j$ with distance $d \equiv g_i - g_j \mod r$, if
\[
  \begin{cases}
    j = 1 & \text{if } i = u; \\
    j = i + 1 & \text{if } i \leq u - 1.
  \end{cases}
\]

The main observation for this proof is that the entry in column $k$ of $\vec{c}_{g_j}$ 
appears in the first $k - 1$ columns of $\vec{S}$ if and only if it appears in column $k - d$
of $\vec{c}_{g_i}$, where $g_i$ precedes $g_j$ with distance $d$.

If $g_i$ precedes $g_j$ with distance $d$, then knowing the first $k - 1$ columns of $g_i$ 
help predict the element in column $k$ of $g_j$ if and only if $d < k$. Let $N_k$ be the number
of elements in column $k$ of $\vec{S}$ that appear in the first $k - 1$ columns of $\vec{S}$.
Then the value of $N_k$ is

\[
  N_k = \sum_{d = 1}^{k - 1} \Gamma_d, 
\]

where $\Gamma_d = \left| \{ (g_i, g_j) : \text{such that $g_i$ precedes $g_j$} \} \right|$.

\end{proof}

\begin{corollary}
The expected value of $N_k$ is given by
\[
  \ev(N_k) = u \left( 1 - \left( \frac{r - u}{r - 1} \right)^{k - 1} \right).
\]
\end{corollary}

\begin{proof}

Let $g$ be a given index, and let $D$ denote a random variable that represents the distance with which $g$ precedes its following index. Then $D$ follows a Geometric distribution with probability of success equal to $\frac{u - 1}{r - 1}$, since we already fixed one of the $u$ selected
values in total.

Now let $p_d$ denote the probability that $D$ is equal to $d$. Then
$\Gamma_d$ follows a Binomial distribution with $u$ trials and probability of success equal to $p_d$.
Therefore

\[
  \ev(N_k) = \sum_{d = 1}^{k - 1} \ev(\Gamma_d) = \sum_{d = 1}^{k - 1} u p_d = 
    u\sum_{d = 1}^{k - 1} p_d.
\]

And the cumulative distribution function of $D$ gives us

\[
  \ev(N_k) = u \left( 1 - \left( 1- \frac{u - 1}{r - 1} \right)^{k - 1} \right) = 
  u \left( 1 - \left( \frac{r - u}{r - 1} \right)^{k - 1} \right).
\]


\end{proof}

\begin{lemma}

Let $Q$ be a random variable that represents the position of the first non null entry of the
last line of $K$. Then
\[
  \ev(Q) = \sum_{i=1}^{u} \frac{2^i}{2^i - 1}, 
\]
where $u$ is the rank of K.
\end{lemma}

\begin{proof}
  $K$ is a full-rank generator matrix of $\ker(B_Z)$ in reduced row echelon form.
  We want to write $Q$ as a sum of geometric random variables.
  
  Consider the random variables $Q_1, Q_2, \dots, Q_u = Q$, where $Q_i$ represents the column
  of the first non null entry of the row $i$ of $K$. For each index $i$, 
  we can define the random variable
  \[
    D_i = \begin{cases} 
            Q_{1}           & \text{if } i = 1;\\
            Q_{i} - Q_{i-1} & \text{if } i > 1.
          \end{cases} 
  \]

  These variables can be illustrated by the following matrix:

  \begin{equation}
    K = 
    \begin{bmatrix}
      \underbrace{0 \, \ldots \, 1}_{D_1} & \hdotsfor{4}  \\
      0 \, \ldots \, 0 & \underbrace{0 \, \ldots \, 1}_{D_2} & \hdotsfor{3} \\
      \vdots         & \ddots & \ddots & \hdotsfor{2} \\
      0 \, \ldots \, 0 & 0 \, \ldots \, 0 & \ldots & \underbrace{0 \, \ldots \, 1}_{D_u}  & \dots \dots \dots \dots
    \end{bmatrix}.
  \end{equation}

\end{proof}

Now we can write $Q = \sum_{i= 1}^{u} D_i$, and by the linearity of expectation
\[
  \ev(Q) = \sum_{i= 1}^{u} \ev(D_i).
\]

The main problem in estimating 


\[
  \Pr( D_i = 1 \,| D_1, D_2, \ldots, D_{i - 1}) = \sum_{i= 1}^{u} \ev(D_i).
\]



\begin{lemma}
Let $\mat{C}$ be a dense random binary circulant matrix with full rank. Let $\vec{v}$ be the sum of $u$ different rows randomly selected from $\mat{C}_Z$.
Then the probability that the first $q$ entries of $\vec{v}$ are equal to $0$ is
equal to
\[
  \ev(Q) = \text{really close to u}.
\]
\end{lemma}

\begin{proof}


Let's calculate the probability


\end{proof}


\begin{lemma}
Let $\mat{C}$ be a dense random binary circulant matrix with full rank. Build a matrix $\mat{C}_Z$
by taking $u$ different rows from $\mat{C}$.
Let $Q$ be a random variable that represents the minimum value such that the first $Q$ columns of $\mat{C}_Z$ form a full-rank matrix. Then the expectation of $Q$ is
\[
  \ev(Q) = \text{really close to u}.
\]
\end{lemma}

\begin{proof}

\end{proof}



% \subsubsection*{Acknowledgments}
% ...

% In the bibliography, use \texttt{\textbackslash textsuperscript} for ``st'', ``nd'', ...:
% E.g., \enquote{The 2\textsuperscript{nd} conference on examples}.
% When you use \href{https://www.jabref.org}{JabRef}, you can use the clean up command to achieve that.
% See \url{https://help.jabref.org/en/CleanupEntries} for an overview of the cleanup functionality.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%