The method for constructing uniform planar approximations of the filter generator
Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 57-68

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $.
Mots-clés : cryptanalysis
Keywords: key recovery, filter generator, planar approximation.
@article{PDM_2022_4_a5,
     author = {L. A. Kuschinskaya},
     title = {The method for constructing uniform planar approximations of the filter generator},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {57--68},
     publisher = {mathdoc},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_4_a5/}
}
TY  - JOUR
AU  - L. A. Kuschinskaya
TI  - The method for constructing uniform planar approximations of the filter generator
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 57
EP  - 68
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_4_a5/
LA  - ru
ID  - PDM_2022_4_a5
ER  - 
%0 Journal Article
%A L. A. Kuschinskaya
%T The method for constructing uniform planar approximations of the filter generator
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 57-68
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_4_a5/
%G ru
%F PDM_2022_4_a5
L. A. Kuschinskaya. The method for constructing uniform planar approximations of the filter generator. Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 57-68. http://geodesic.mathdoc.fr/item/PDM_2022_4_a5/