Record Details

Порівняльний аналіз складності методів лінеаризації та перебору розв’язання систем нелінійних булевих рівнянь

Наукові журнали Національного Авіаційного Університету

View Archive Info
 
 
Field Value
 
Title Порівняльний аналіз складності методів лінеаризації та перебору розв’язання систем нелінійних булевих рівнянь
Comparative analysis of the complexity of the linearization and enumeration methods for solving systems of nonlinear boolean equations
Сравнительный анализ сложности методов линеа-ризации и перебора решения систем нелинейных булевых уравнений
 
Creator Лещенко, Владислав Вадимович; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
Пекарчук, Ніна Андріївна; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
Савчук, Михайло Миколайович; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
 
Subject Інформаційна безпека
системи нелінійних випадкових булевих рівнянь; алгоритми розв’язку систем; методи лінеаризації та повного перебору; складність алгоритмів; статистичне моделювання; криптоаналіз
УДК 621.391:519.2
Information security
systems of nonlinear Boolean equations; algorithms for solving systems; linearization and enumeration methods; complexity of algorithms; statistical modeling; cryptanalysis
UDC 621.391:519.2
Информационная безопасность
системы нелинейных случайных булевых уравнений; алгоритмы решения систем; методы линеаризации и полного перебора; сложность алгоритмов; статистическое моделирование; криптоанализ
УДК 621.391:519.2
 
Description Проблема знаходження розв’язків систем нелінійних рівнянь з багатьма змінними над скінченними алгебраїчними структурами та побудови ефективних алгоритмів їх пошуку є важливою для багатьох прикладних задач  у різноманітних галузях і актуальність цієї проблеми зростає з часом. Стійкість багатьох існуючих криптосистем базується на складності задачі розв’язання систем нелінійних рівнянь багатьох змінних над скінченними полями. В загальному вигляді ця задача є задачею -повною. Але існує багато випадків, коли до таких систем можна запропонувати методи більш швидкі ніж методи повного перебору. Оскільки вибір методу може значно зменшити час та необхідні ресурси на знаходження розв’язків системи, природньо виникають питання оцінки складності різних методів розв’язання для систем з різними наборами параметрів, а також пошуку спеціальних найбільш ефективних методів для конкретного класу систем. У статті розглядаються найбільш важливі для криптографії та криптоаналізу системи нелінійних рівнянь з багатьма змінними над скінченним полем . Предметом дослідження є порівняльний аналіз складності методу лінеаризації з введенням нових змінних для розв’язання систем нелінійних рівнянь над полем з багатьма невідомими та  методу повного перебору в залежності від параметрів системи. Метою роботи є отримання середніх оцінок складності методів та знаходження межі в області зміни параметрів перевизначеної сумісної системи рівнянь, яка дає можливість з двох вказаних методів вибрати більш швидкий і ефективний. Запропоновані імовірнісні моделі для отримання теоретичних, асимптотичних оцінок середньої складності методів  та проведення низки статистичних  експериментів з отриманням середніх оцінок методом Монте-Карло.  Показано, що  існує границя в області зміни параметрів, що залежить, перш за все, від співвідношення максимального степеня рівнянь системи та числа невідомих, яка визначає, коли метод лінеаризації працює краще за повний перебір. Теоретичні та експериментальні дані застосовано для побудови цієї границі.  Аналітичний вираз для лінії розмежування в області зміни параметрів системи отримано з використанням методу найменших квадратів.
The problem of finding solutions to systems of multivariate nonlinear equations over finite algebraic structures and constructing efficient algorithms for their search is important for many applied problems in various fields, and the relevance of this problem increases over time. The security of many existing cryptosystems is based on the complexity of the problem of solving systems of multivariable nonlinear equations over finite fields. In general, this task is an -complete problem. But there are many cases where such systems can be solved by methods faster than the brute-force methods. Since choosing a method can significantly reduce the time and resources required to find system solutions, the questions of assessing the complexity of different methods of solutions for systems with different sets of parameters, as well as finding the special best performing methods for a particular classes of systems, naturally arise. The paper deals with the most important for cryptography and cryptanalysis systems of multivariate nonlinear equations over the finite field . The subject of the study is a comparative analysis of the complexity of the method of linearization with the introduction of new variables for solving systems of nonlinear equations over the field  with many unknowns, and the method of complete enumeration, depending on the system parameters. The purpose of the work is obtaining average estimates of the complexity of the methods, and determining the boundary in the parameter space of the overdefined consistent system of equations, which makes it possible to choose the faster and more efficient method of the two considered. Probabilistic models for obtaining theoretical, asymptotic estimates of the average complexity of the methods, and for conducting a number of statistical experiments with obtaining the average estimates by the Monte Carlo method, are proposed. It is shown that there exists a boundary in the parameter space, depending on, first of all, the relation between the maximum degree of equations of the system and the number of unknowns, which determines when the linearization method works better than the complete enumeration. Theoretical and experimental data have been used to construct this boundary. The analytical expression for the separation line in the parameter space of the system was obtained by the least squares method.
Проблема нахождения решений систем нелинейных уравнений со многими переменными над конечными алгебраическими структурами и построения эффективных алгоритмов их поиска важна для многих прикладных задач в различных областях и актуальность этой проблемы возрастает со временем. Стойкость многих существующих криптосистем базируется на сложности задачи решения систем нелинейных уравнений многих переменных над конечными полями. В общем виде эта задача является задачей -полной. Но существует много случаев, когда к таким системам можно предложить методы более быстрые чем методы полного перебора. Поскольку выбор метода может значительно уменьшить время и необходимые ресурсы на нахождение решений системы, естественно возникают вопросы оценки сложности различных методов решения для систем с разными наборами параметров, а также поиска специальных наиболее эффективных методов для конкретного класса систем. В статье рассматриваются наиболее важные для криптографии и криптоанализа системы нелинейных уравнений со многими переменными над конечным полем . Предметом исследования является сравнительный анализ сложности метода линеаризации с введением новых переменных для решения систем нелинейных уравнений над полем  со многими неизвестными и метода полного перебора в зависимости от параметров системы. Целью работы является получение средних оценок сложности методов и нахождения границы в области изменения параметров переопределенной совместной системы уравнений, которая дает возможность из двух указанных методов выбрать более быстрый и эффективный. Предложенны вероятностные модели для получения теоретических, асимптотических оценок средней сложности методов и проведения ряда статистических экспериментов с получением средних оценок методом Монте-Карло. Показано, что существует граница в области изменения параметров, зависисящая, прежде всего, от соотношения максимальной степени уравнений системы и числа неизвестных, которая определяет, когда метод линеаризации работает лучше чем полный перебор. Теоретические и экспериментальные данные применены для построения этой границы. Аналитическое выражение для линии разграничения в области изменения параметров системы получено с использованием метода наименьших квадратов.
 
Publisher National Aviation University
 
Contributor —
—
—
 
Date 2020-03-31
 
Type —
—
—
 
Format application/pdf
application/pdf
application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/ZI/article/view/14662
10.18372/2410-7840.22.14662
 
Source Ukrainian Information Security Research Journal; Том 22, № 1 (2020); 33-42
Защита информации; Том 22, № 1 (2020); 33-42
Захист інформації; Том 22, № 1 (2020); 33-42
 
Language uk
 
Rights Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим: Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договоронности, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами: Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
 

Технічна підтримка: НДІІТТ НАУ