О сложности метода последовательного опробования

О сложности метода последовательного опробования

Фомичёв В. М.
Дискретный анализ и исследование операций, 31, 2, 144–154 (2024)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2024.31.766

Аннотация:

Система $m$ булевых уравнений может быть решена методом последовательного опробования с помощью $m$-шагового алгоритма, где на $i$-м шаге опробуются значения всех переменных, существенных для первых $i$ уравнений, и ложные решения отбраковываются по правым частям уравнений, $i = 1, \dots , m$. Оценка сложности метода, зависящая от структуры множеств существенных переменных уравнений, достигает минимума при некоторых перестановках уравнений системы. Предложен алгоритм оптимальной перестановки уравнений, минимизирующей среднюю вычислительную сложность алгоритма в естественных вероятностных предположениях. В ряде случаев оптимальные перестановки определены неоднозначно, и их нахождение является вычислительно сложным. Метод последовательного опробования вырождается в полный перебор, если каждое уравнение системы зависит существенно от всех переменных. Приведён пример построения оптимальной перестановки. 
Табл. 2, ил. 1, билиогр. 11.

Литература:
  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
     
  2. Коновальцев И. В. Об одном алгоритме решения систем линейных уравнений в конечных полях // Проблемы кибернетики. Т. 19. М.: Физматгиз, 1967. С. 269–274.
     
  3. Strassen V. Gaussian elimination is not optimal // Numer. Math. 1969. V. 13. P. 354–356.
     
  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). Heidelberg: Springer, 2003. P. 182–199. (Lect. Notes Comput. Sci.; V. 2587).
     
  5. Фомичёв В. М. Методы дискретной математики в криптологии. М.: ДИАЛОГ-МИФИ, 2010. 424 с.
     
  6. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: ТРИУМФ, 2002. 1040 с.
     
  7. Mercle R. C., Hellman M. On the security of multiple encryption // Commun. ACM. 1981. V. 24, No. 7. P. 465–467.
     
  8. Мелузов А. С. Построение эффективных алгоритмов решения систем полиномиальных булевых уравнений методом опробования части переменных // Дискрет. математика. 2011. Т. 23, № 4. С. 66–79.
     
  9. Фомичёв В. М. Оценка характеристик нелинейности итеративных преобразований векторного пространства // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 4. С. 131–151.
     
  10. Rivest R. L. Cryptography // Handbook of theoretical computer science. V. A: Algorithms and complexity. Cambridge, MA: MIT Press, 1990. P. 617–755.
     
  11. Stinson D. R. Cryptography: Theory and practice. Boca Raton: CRC Press, 1995. 434 p.

Исследование выполнено за счёт бюджетов организаций, обозначенных автором на первой странице статьи.

Фомичёв Владимир Михайлович
  1. ООО «Код Безопасности», 
    1-й Нагатинский пр-д, 10, стр. 1, 115230 Москва, Россия
  2. Институт проблем информатики ФИЦ «Информатика и управление» РАН, 
    ул. Вавилова, 44, корп. 2, 119333 Москва, Россия

E-mail: fomichev.2016@yandex.ru

Статья поступила 30 марта 2023 г. 
После доработки — 17 октября 2023 г. 
Принята к публикации 22 декабря 2023 г.

Abstract:

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.

References:
  1. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  2. I. V. Konovaltsev, An algorithm for solving systems of linear equations in finite fields, in Problems of Cybernetics, Vol. 19 (Fizmatgiz, Moscow, 1967), pp. 269–274 [Russian].
     
  3. V. Strassen, Gaussian elimination is not optimal, Numer. Math. 13, 354–356 (1969).
     
  4. N. T. Courtois, Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt, in Information Security and Cryptology — ICISC 2002 (Rev. Pap. 5th Int. Conf., Seoul, Korea, Nov. 28–29, 2002) (Springer, Heidelberg, 2003), pp. 182–199 (Lect. Notes Comput. Sci., Vol. 2587).
     
  5. V. M. Fomichev, Methods of Discrete Mathematics in Cryptology (DIALOGMIFI, Moscow, 2010) [Russian].
     
  6. B. Schneier, Applied Cryptography. Protocols, Algorithms, and Source Code in C (Wiley, Hoboken, NJ, 1993; TRIUMF, Moscow, 2002 [Russian]).
     
  7. R. C. Mercle and M. Hellman, On the security of multiple encryption, Commun. ACM 24 (7), 465–467 (1981).
     
  8. A. S. Meluzov, On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables, Diskretn. Mat. 23 (4), 66–79 (2011) [Russian] [Discrete Math. Appl. 21 (3), 381–395 (2011)].
     
  9. V. M. Fomichev, Estimating nonlinearity characteristics for iterative transformations of a vector space, Diskretn. Anal. Issled. Oper. 27 (4), 131–151 (2020) [Russian] [J. Appl. Ind. Math. 14 (4), 610–622 (2020)].
     
  10. R. L. Rivest, Cryptography, in Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity (MIT Press, Cambridge, MA, 1990), pp. 617–755.
     
  11. D. R. Stinson, Cryptography: Theory and Practice (CRC Press, Boca Raton, 1995).