%!TEX root = paper.tex

\section{Probabilistic analysis}
\label{sec:complexity}

\subsection{The probability of the attack failing}
\label{sec:z0_z1_sizes}

Let $Z_0$ and $Z_1$ be sets of indexes, possibly shifted by the same amount
of positions, of some of the null entries of \hz and \ho.
For the algorithm to run successfully,  the kernel matrix $\mat{K}$ of
$\mat{B}^{Z_0}_{Z_1^\comp}$ must have exactly one row. If $Z_0$ and $Z_1$ are indeed
positions of null entries, then $\mat{K}$ has at least one row. In other words, we want
the linear equation $\vec{x} \mat{B}^{Z_0}_{Z_1^\comp} = \vec{0}$ to have no more
than one solution for non-null $\vec{x}$.

Since the solutions of this equation impose a linear combination of the rows of $\mat{B}^{Z_0}_{Z_1^\comp}$
that must sum to $\vec{0}$, it is natural to expect that this equation has fewer solutions when 
when $\mat{B}^{Z_0}_{Z_1^\comp}$ has a large number of columns and a small
number of rows. That is, we want $Z_0$ to be large, and $Z_1^\comp$ to be small, which is 
equivalent to $Z_1$ also large. We want to find how large must these sets be for
the equation to have exactly one solution.

This is a difficult task because the matrix $\mat{B} = \mat{H}_1^{-1} \mat{H}_0$ is inherently dependent on the sets $Z_0$
and $Z_1$, which are also related to $\mat{H}_0$ and $\mat{H}_1$.
In fact, this dependency is what makes the equation always having at least one solution.

To deal with this dependency problem we suggest an approximation that works well on practice consisting in 
considering $\mat{B}^{Z_0}_{Z_1^\comp}$ as a random binary matrix with $|Z_0|$ columns and $|Z_1^\comp|$
rows, such that its kernel contains at least one vector. Under this hypothesis, the sum 
of any set of rows of $\mat{B}^{Z_0}_{Z_1^\comp}$ is a random binary vector of $|Z_0|$ columns. 
Therefore, the probability that any linear combination of the matrix $\mat{B}^{Z_0}_{Z_1^\comp}$ sums to
$\vec{0}$ is $2^{-|Z_0|}$.
Since there are $2^{Z_1^\comp}$ possible linear combinations of the rows of $\mat{B}^{Z_0}_{Z_1^\comp}$, 
the probability that one of them is $\vec{0}$, that is, the probability of the attack failing, is upper
bounded by
\mathindent=2mm % <-- [A]
\begin{align*}
    \Pr ( \text{Algorithm does not recover the key} )
      &\lessapprox \frac{2^{|Z_1|^\comp}}{2^{|Z_0|}} \nonumber \\
      &\lessapprox \frac{2^{r - |Z_1|}}{2^{|Z_0|}} \nonumber \\
      &\lessapprox {2^{r - |Z_1| - |Z_0|}}.  
\end{align*}
\mathindent=7mm % <-- [A]


\subsection{Finding a $d$-exclusion for a high probability of success}
\label{sec:d_exclusion}

The approximation above shows that the value of $|Z_0| + |Z_1|$ determines the probability
that the attack succeeds, for a fixed $r$. We now assess how much the sizes of $D_0$
and $D_1$, the distances which are known to be outside the spectrums
of \hz and \ho, impact on the sizes of $Z_0$ and $Z_1$, respectively.

Fix the probability that the attack fails as $1/2^\gamma$. We want to find the least integer
$d$ such that, if both $|D_0|$ and $|D_1|$ are greater than or equal to d, then the attack
succeeds with probability $1 - 1/2^\gamma$, for a large fraction $\alpha$
of all possible secret keys. Of course we want $\alpha$ and $\gamma$ to be large.

The idea is simply to perform a binary search for the least $d$ in the set
$[\lfloor r/2 \rfloor] = \{1, \ldots, \lfloor r/2 \rfloor \}$.
The problem we face is that the interdependence of the distances outside the spectrum makes it hard to analytically compute the distribution of the size $|Z_0|$ as
a function of $|D_0|$, and similarly for $|Z_1|$ and $|D_1|$. Therefore we use simulations,
for each $d$, to estimate the fraction $f_d$ of secret keys for which the attack succeeds
with probability at least $1 - 1/2^\gamma$ when $|D_0| = |D_1| = d.$ For this,
we build $N$ valid pairs of $(D_0, Z_0)$ and $(D_1, Z_1)$,
and our estimator for $f_d$ is given by
\[
  \hat{f}_d = \frac{ \# \{ \text{Generated $Z_0$ and $Z_1$} : |Z_0| + |Z_1| - r \geq \gamma \} }{N}.
\]
The search ends with the least value of $d$ such that $\hat{f}_d \geq \alpha$.

Table~\ref{tab:size_d_for_sim} shows the values of $d$ obtained for different security levels,
considering as simulation parameters $N = 5000$, $\alpha = 99\%$, and $\gamma = 20$. For
comparison between different security levels, we also put the fractions $d/\sigma^\comp$,
where $\sigma^\comp$ is the average number of distances outside the spectrum.
For each security level, we note that the relative $d$-exclusion needed for the attack to 
successfully find the key grows with $n_0$. The explanation for this fact is that
the blocks of the keys get more dense when $n_0$ is increased,
as discussed in the end of Section~\ref{sec:case_big_n0}.
For the security level of $256$, considering $n_0 = 4$ cyclic blocks, the blocks of the key are
so dense that even knowing all distances outside the spectrum is not enough for the algorithm
to successfully find the key. 

\begin{table}[h]
\centering
\caption{Simulation results for the values of $d$ with simulation parameters $N = 5000$, $\alpha = 99\%$, and $\gamma = 20$.}
\label{tab:size_d_for_sim}
\begin{tabular}{ccccc}
\toprule
\begin{tabular}[c]{@{}c@{}}Security \\ level \\ $\lambda$\end{tabular} &
\begin{tabular}[c]{@{}c@{}}$n_0$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Estimated size\\ for $D_0$ and  $D_1$ \\ by the simulation\\ $d$\end{tabular} & \begin{tabular}[c]{@{}c@{}}Average number of \\ distances outside\\ the spectrum\\ $\sigma^\comp$\end{tabular} & $d/\sigma^\comp$ \\ \midrule
80  & $2$ & $d_{80} = 722$ & 1582.12 & $45.63 \%$       \\
80  & $3$ & $d_{80} = 545$ & 873.85 & $62.36 \%$       \\
80  & $4$ & $d_{80} = 471$ & 576.06 & $81.76 \%$       \\ \midrule

128 & $2$ & $d_{128} = 1470$ & 2964.72  & $49.58 \%$       \\
128 & $3$ & $d_{128} = 1116$ & 1538.19  & $72.55 \%$       \\
128 & $4$ & $d_{128} = 1025$ & 1175.08  & $87.28 \%$       \\ \midrule

256 & $2$ & $d_{256} = 4845$ & 9256.64 & $52.34 \%$       \\ 
256 & $3$ & $d_{256} = 3347$ & 3877.48 & $86.31 \%$       \\ 
256 & $4$ & - & 2882.49 & -       \\ \bottomrule
\end{tabular}
\end{table}


