Geodesic
On the complexity of the sequential sampling method
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 144-154 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A system of $m$ Boolean equations can be solved by a sequential sampling method using an $m$-step algorithm, where at the $i$-th step the values of all variables essential for the first $i$ equations are sampled and false solutions are rejected based on the right-hand sides parts of the equations, $i=1,\dots,m$. The estimate of the complexity of the method depends on the structure of the sets of essential variables of the equations and attains its minimum after some permutation of the system equations. For the optimal permutation of equations we propose an algorithm that minimizes the average computational complexity of the algorithm under natural probabilistic assumptions. In a number of cases, the construction of such a permutation is computationally difficult; in this connection, other permutations are proposed which are computed in a simpler way but may lead to nonoptimal estimates of the complexity of the method. The results imply conditions under which the sequential sampling method degenerates into the exhaustive search method. An example of constructing an optimal permutation is given. Tab. 2, illustr. 1, biliogr. 11.
Keywords: Boolean function, essential variable, subset lattice of a set, chain in a lattice. 
@article{DA_2024_31_2_a8,
     author = {V. M. Fomichev},
     title = {On~the~complexity of~the~sequential sampling~method},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {144--154},
     year = {2024},
     volume = {31},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_2_a8/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - On the complexity of the sequential sampling method
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 144
EP  - 154
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_2_a8/
LA  - ru
ID  - DA_2024_31_2_a8
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T On the complexity of the sequential sampling method
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 144-154
%V 31
%N 2
%U http://geodesic.mathdoc.fr/item/DA_2024_31_2_a8/
%G ru
%F DA_2024_31_2_a8
V. M. Fomichev. On the complexity of the sequential sampling method. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 144-154. http://geodesic.mathdoc.fr/item/DA_2024_31_2_a8/

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[2] I. V. Konovaltsev, “An algorithm for solving systems of linear equations in finite fields”, Problems of Cybernetics, 19, Fizmatgiz, M., 1967, 269–274 (Russian) | MR

[3] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[4] Courtois N. T., “Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt”, Information security and cryptology — ICISC 2002, Rev. Pap. 5th Int. Conf. (Seoul, Korea, Nov. 28–29, 2002), Lect. Notes Comput. Sci., 2587, Springer, Heidelberg, 2003, 182–199 | DOI | MR | Zbl

[5] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology, DIALOG-MIFI, M., 2010 (Russian)

[6] B. Schneier, Applied Cryptography. Protocols, Algorithms, and Source Code in C, Wiley, Hoboken, NJ, 1993 | MR | Zbl

[7] Mercle R. C., Hellman M., “On the security of multiple encryption”, Commun. ACM, 24:7 (1981), 465–467 | DOI | MR

[8] A. S. Meluzov, “On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables”, Discrete Math. Appl., 21:3 (2011), 381–395 | DOI | DOI | MR | Zbl

[9] V. M. Fomichev, “Estimating nonlinearity characteristics for iterative transformations of a vector space”, J. Appl. Ind. Math., 14:4 (2020), 610–622 | DOI | MR | Zbl

[10] Rivest R. L., “Cryptography”, Handbook of theoretical computer science, v. A, Algorithms and complexity, MIT Press, Cambridge, MA, 1990, 617–755 | MR

[11] Stinson D. R., Cryptography: Theory and practice, CRC Press, Boca Raton, 1995, 434 pp. | MR | Zbl