Mathematical Methods of Cryptography
The method for constructing uniform planar approximations of the filter generator
L. A. Kuschinskaya Lomonosov Moscow State University, Moscow, Russia
Abstract:
We study the possibility of constructing an approximation of filter generator to restore initial state
$u^* \in V_n$ from its output sequence
$z_i=f(A^i(u^*)) \in \{0,1\}$,
$i=0,\ldots,N-1$, where
$A:V_n\to V_n$ is non-degenerate linear mapping,
$f$ is balanced Boolean function. The triple
$(m, L_0, \mathbb T )$ is a key element in the construction of the approximation, where
$m \in \mathbb{N}$,
$L_0$ is coset of the space
$V_n$,
$\mathbb T = ( t_0, t_1, \ldots, t_m )$,
$t_0 = 0$,
$t_0 \leqslant t_1 < \ldots < t_m $. Let
$(m, L_0, \mathbb T )$ be a triple and for
$b_1, \ldots, b_m\in \{0, 1\}$ the probability that
$f(v) {=} b_i$ is greater than
$1/2$ for a random equiprobable choice of a vector
$v$ from
$L_i = A^{ t_i - t_{i-1}}(L_{i-1})$,
$i = 1, \ldots, m$. Then a finite number of such triples with pairwise distinct sets
$L_0$ makes it possible to restore the key with a complexity that is much less than the complexity of enumerating keys in some cases. In this paper, we study the possibility of constructing approximations of a special form, where all cosets
$L_0$ have the same dimension, their union is equal to
$V_n$, and the values of
$m$ are the same for all described triples. Expressions for the optimal values of the parameters
$k$ and
$\delta$ are obtained for some enumeration method for constructing the approximations. It is shown that for $k = \left \lceil \log_2 \left ((Q-\sqrt{Q^2-\pi_0 2^{n+2}})/{2\pi_0} \right ) \right \rceil$ and
$\delta \approx \lceil t_0 \sqrt \Omega \rceil$ it is possible to achieve the minimum length of the generator output sequence required to construct such approximations for a given value of the upper complexity
$Q$ and lower reliability
$\pi_0$ of the initial state recovery method, where
$ \Omega = 2^k$,
$t_0 \approx 1{.}19061 $.
Keywords:
cryptanalysis, key recovery, filter generator, planar approximation.
UDC:
519.7
DOI:
10.17223/20710410/58/6
Fulltext:
PDF file (811 kB)