%-*- root: paper.tex -*-

\section{Complexity analysis}

In this section we explain why, when $Z_0$ and $Z_1$ are sufficiently large, we should expect,
for each iteration of the algorithm, the nullity of
the matrix $\mat{B}_\beta$ to be less than 1.


\subsection{The probability that the kernel have low nullity}

\begin{lemma}
  Let $\mat{H} = [ \, \mat{H}_0 \mid \mat{H}_1 \, ] $ be some private parity check matrix of
  a user of the QC-MDPC scheme, and let $\mat{B} = \mat{H}_0 \mat{H}_1^{-1}$.
  Let $Z_0$ and $Z_1$ be two sets of indexes of entries which are known to be null for
  the first lines of $\vec{H}_0$ and $\vec{H}_1$, respectively. Let $U$ be a random variable
  that counts the number of vectors $ \vec{u} \in \Fb^{r}$ such that $\supp(\vec{u}) \notin Z_1$ and $ \supp (\vec{u} \mat{B}) \notin Z_0 $. Then the probability that $U > 1$ is given by
  \[
    \Pr ( U > 1 ) \approx \frac{1}{2^{|Z_0| + |Z_1| - r}}.
  \]

\end{lemma}

Suppose we have two vectors $\vec{u}$ and $\vec{v}$ in $\Fb^r$ such that
$\vec{u} \mat{B} = \vec{v}$. Then multiplying the two sides by $\mat{H}_1$ and grouping the terms on the left gives us $\vec{u} \mat{H}_0 + \vec{v} \mat{H}_1 = \vec{0}$.
Therefore, $\vec{u} \mat{B} = \vec{v}$ if and only if the vector $\vec{v} \| \vec{u}$ is in the QC-MDPC code with parity check $\mat{H}$. Assuming that the probability of
$\vec{v} \| \vec{u}$ is a codeword is independent of its weight, and given by $2^{-r}$,
we have that
\begin{align*}
  \Pr ( U > 1 )
  & \leq \sum_{\vec{u} : \supp(\vec{u}) \notin Z_1} \sum_{\vec{v}: \supp(\vec{v}) \notin Z_0}
    \Pr(\vec{u} \| \vec{v} \text{ is a codeword}) \\
  & \leq 2^{r -  |Z_0|} 2^{r - |Z_1|} \frac{1}{2^r}.
\end{align*}


\begin{lemma}
  The complexity of the attack in the worst case is
  \[
    \WF(\textsc{Alg}_2) = r + r|Z_0| + r(1 + r + |Z_0||Z_1^\comp| + |Z_1^\comp|  |Z_0|^2 + 1).
  \]

  And since $|Z_0| = \mathcal{O}(r)$ and $z_1^\comp = \mathcal{O}(r)$, we have that
  \[
    \WF(\textsc{Alg}_2) = \mathcal{O}(r^4).
  \]

\end{lemma}

We can also show that the proposed algorithm, slightly modified, is more efficient
than the original under the original setup, that is, given the full spectrum of $\hz$, and without any information of $\ho$.


\subsection{The sizes of $Z_0$ and $Z_1$ and the number of distances outside the spectra}

Let $D_0$ and $D_1$ be sets of distances outside the spectra of $\hz$ and $\ho$,
respectively. We now analyze the relation between the number of distances in $D_0$
and  and the number of positions in $Z_0$, and analogously for $D_1$ and $Z_1$.

It is clear that when the size of $D_0$ increases, so it does the number of entries
we can add to $Z_0$ for each known non-null entry of $\hz$. But it is not easy to
find a closed formula for their relation, because of the interdependence between the distances. As such, we run simulations for
assessing the average value of the $|Z_0|$ for different security levels, when
different numbers of ones are fixed in $\hz$. Of course the distributions of
$|Z_1|$ and $|Z_0|$ are identical. The results for the security levels
80 $(r = 4801, w = 45)$, and 128 $(r = 9857, w = 71)$ are shown in
Figure~\ref{fig:known_outspec_vs_known_ones}.


% \begin{figure}[!h]
%   \centering
%   \includegraphics[scale=1]{figures/ourattack/known_outspec_vs_known_ones.pdf}
%   \caption{Legenda}
%   \label{fig:known_outspec_vs_known_ones}
% \end{figure}

These plots are useful when studying the tradeoff between considering more
fixed ones when defining $Z_0$ or $Z_1$, or performing more decoding trials.
Section~\ref{sec:seila} shows how we might use this information. But for now,
we are interested in fixing two ones for both $Z_0$ and $Z_1$, as our
algorithm does.



