Метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем

Скорочена інформація про документ
dc.contributor.advisorОлексійчук, Антон Миколайович
dc.contributor.authorМатійко, Александра Андріївна
dc.date.accessioned2023-12-15T15:16:13Z
dc.date.available2023-12-15T15:16:13Z
dc.date.issued2023
dc.description.abstractМатійко А.А. Метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії з галузі знань 12 Інформаційні технології за спеціальністю 125 Кібербезпека. – Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського”, Київ, 2023. Дисертаційна робота присвячена вирішенню актуальної наукової задачі, яка полягає у розробці методу побудови симетричних NTRU-подібних шифросистем, що є обґрунтовано стійкими відносно атак на основі підібраних відкритих текстів. Протягом останніх років проведено численні дослідження у галузі квантових комп’ютерів, які використовують квантово-механічні явища для розв’язання обчислювальних задач, що є практично нерозв’язними за допомогою звичайних комп’ютерів. Оскільки створення квантових комп’ютерів є лише питанням часу, це серйозно загрожує конфіденційності та цілісності інформації у спеціальних інформаційно-комунікаційних системах. Виходячи з цього, у 2016 р. Національний інститут стандартів і технологій США оголосив відкритий конкурс зі стандартизації асиметричних постквантових криптопримітивів. Майже третина усіх криптосистем і протоколів, представлених на цьому конкурсі, належить до NTRU-подібних. (Зауважимо, що асиметрична шифросистема NTRU є на сьогодні однією з найшвидших та представляє широкий клас постквантових криптосистем з однойменною назвою, стійкість яких базується на складності знаходження коротких векторів у деяких решітках в евклідовому просторі). До того ж, новітній постквантовий алгоритм відкритого шифрування, стандартизований в Україні (ДСТУ 8961:2019 «Скеля») також є NTRU-подібним. Однією з актуальних задач сучасної криптології є створення постквантових симетричних шифросистем, стійкість яких, аналогічно асиметричним, базується на складності розв’язанні лише однієї обчислювальної задачі. Зауважимо, що сучасні блокові чи потокові шифри не володіють такою властивістю. При цьому тривіальний метод побудови симетричних шифросистем, виходячи з асиметричних (шляхом “засекречування відкритого ключа”), виявляється цілком неприйнятним, оскільки не гарантує стійкості отриманих шифросистем відносно певних атак на основі підібраних відкритих текстів. Єдиною відомою на сьогодні симетричною NTRU-подібною шифросистемою є алгоритм NTRUCipher, запропонований в 2017 р. Розробником шифросистеми проведено попередній аналіз її стійкості та наведено рекомендації стосовно вибору параметрів, які гарантують її стійкість відносно розглянутих ним атак. Поряд з тим, як показують подальші дослідження, шифросистема NTRUCipher є вразливою відносно деяких інших атак, причому природний спосіб модифікувати цю шифросистему задля підвищення її стійкості не приводить до успіху. Як наслідок, постає потреба у створенні методів побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем, які відрізняються за сутністю від відомої. Таким чином, існує певне протиріччя між потребами практики в обґрунтовано стійких постквантових (зокрема, NTRU-подібних) симетричних шифросистемах та відсутністю методів побудови таких шифросистем. Зазначене протиріччя приводить до наукової задачі, яка полягає у розробці методу побудови симетричних NTRU-подібних шифросистем, що є обґрунтовано стійкими відносно атак на основі підібраних відкритих текстів. Для розв’язання поставленої наукової задачі використано методи теорії скінченних полів, теорії дискретного перетворення Фур’є на скінченних абелевих групах, лінійної алгебри, теорії ймовірностей та кореляційного криптоаналізу. Метою дисертаційної роботи є створення обґрунтовано стійких симетричних NTRU-подібних шифросистем для систем захисту інформації в інформаційно-комунікаційних системах. Об’єктом дослідження у дисертаційній роботі є процес перетворення інформації з використанням сучасних NTRU-подібних шифросистем, а предметом дослідження – методи побудови та обґрунтування стійкості зазначених шифросистем відносно атак на основі підібраних відкритих текстів. В роботі вперше отримано аналітичні співвідношення для оцінювання ймовірності оборотності випадкових поліномів, які використовуються в NTRU-подібних шифросистемах. На відміну від відомого співвідношення для ймовірності оборотності випадкового рівноймовірного елементу кільця зрізаних поліномів, отримані співвідношення є справедливими для більш загальної схеми формування випадкових поліномів. Вони базуються на застосуванні апарату перетворення Фур’є розподілів ймовірностей на скінченному полі та надають змогу оцінювати (а в окремих практично важливих випадках – обчислювати) значення ймовірності оборотності випадкових поліномів, що використовуються в ролі компонентів секретних ключів NTRU-подібних шифросистем. Удосконалено аналітичні співвідношення для оцінювання ймовірності помилкового розшифрування повідомлень в NTRU-подібних шифросистемах. На відміну від раніше відомих, отримані співвідношення є справедливими для усіх видів сучасних NTRU-подібних шифросистем (як асиметричних, так і симетричних). Окрім того, вони дозволяють оцінювати ймовірність помилкового розшифрування повідомлень в NTRU-подібних шифросистемах при фіксованому ключі, надаючи, таким чином, більш адекватну інформацію про частоту виникнення помилок при розшифруванні. Дістав подальший розвиток метод оцінювання стійкості симетричних шифросистем NTRUCipher та NTRUCipher+ за рахунок дослідження трьох додаткових атак на ці шифросистеми. Для зазначених атак отримано аналітичні оцінки складності та показано, що, принаймні, одна з них може бути реалізована в режимі реального часу (хоча й не дозволяє відновлювати ключі шифросистем, а тільки відрізняти послідовності їхніх шифрованих повідомлень від суто випадкової послідовності). Вперше запропоновано метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем. Показано, що на відміну від відомих симетричних NTRU-подібних шифросистем, запропоновані шифросистеми мають обґрунтовану стійкість відносно атак на основі підібраних відкритих повідомлень, яка базується на складності еталонної обчислювально складної задачі Decision-Ring-LWE. Практичне значення одержаних результатів полягає в тому, що дисертанткою розроблено програмні реалізації, які дозволяють в режимі реального часу обчислювати значення параметрів для побудови запропонованих обґрунтовано стійких NTRU-подібних шифросистем, обчислювати ймовірність оборотності випадкових поліномів та ймовірність помилкового розшифрування повідомлень у довільних NTRU-подібних шифросистемах. Крім того, отримані в роботі результати дозволяють: - зменшити ймовірність необоротності випадкового полінома в кільці Rn.q (з 0,5 до 2 15 10- , - ) за рахунок належного вибору параметрів q і n NTRU-подібної шифросистеми; -вибирати параметри NTRU-подібних шифросистем, що забезпечують належне (мале) значення ймовірності помилкового розшифрування повідомлень при фіксованому секретному ключі; -встановити, що трудомісткість BKW-атаки на шифросистему NTRUCipher+ є в 15 2 - 69 2 разів вище в порівнянні з трудомісткістю аналогічної атаки на шифросистему NTRUCipher; -довести, що шифросистема NTRUCipher+ є цілком вразливою відносно розрізнювальної атаки, яка може бути реалізована в режимі реального часу (при цьому найбільше значення обсягу матеріалу, потрібного для реалізації атаки становить 19 t -2 ); – обирати параметри NTRU-подібних шифросистем, які гарантують їхню стійкості на заздалегідь визначеному рівні - (зокрема n -631, q -2693 , d -56 при 128 --2 , n -883, q -8089, d -168 при 256 --2 ). Наукові та практичні результати дисертаційної роботи реалізовані в Службі зовнішньої розвідки України в результаті виконання НДР “Дорадо” та НДР “Сарган”, а також в науково-технічних розробках АТ “Інститут інформаційних технологій”.uk
dc.description.abstractotherMatiyko A. Method of constructing provable secure NTRU-like encryption schemes. – Qualifying scientific work as a manuscript. Ph.D thesis in the field of knowledge 12 Information technologies in specialty 125 Cybersecurity. – National technical university of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, 2023. This thesis is devoted to solving actual scientific problem of development the method of constructing NTRU-like encryption schemes that are provable secure against chosen plaintext attacks. In recent years, numerous researches have been carried out in the field of quantum computers, which use quantum mechanical phenomena to solve computational problems that are practically unsolvable with the help of conventional computers. Since the creation of quantum computers is only a matter of time, it seriously threatens the confidentiality and integrity of information in special information and communication systems. Based on this, in 2016 the US National Institute of Standards and Technology announced an open competition for the standardization of asymmetric post-quantum crypto primitives. Almost a third of all cryptosystems and protocols presented at this competition belong to NTRUlike. (Note that the NTRU asymmetric encryption scheme is currently one of the fastest and represents a wide class of post-quantum cryptosystems with the same name, the security of which is based on difficulty of finding short vectors in some lattices in Euclidean space). In addition, the latest post-quantum public-key encryption algorithm standardized in Ukraine (DSTU 8961:2019 “Skelya”) is also NTRU-like. One of the most important problem in the field of cryptology is the design of symmetric encryption schemes, whose security, similarly to the asymmetric one, is based on the complexity of solving only one particular problem. Note that modern block or stream ciphers do not have this property. At the same time, the trivial method of constructing symmetric encryption schemes, based on asymmetric ones (by “secrecy of the public key”), turns out to be completely unacceptable, since it does not guarantee the security of received encryption schemes against chosen plaintext attack. The only symmetric NTRU-like encryption scheme known today is the NTRUCipher, which was proposed in 2017. The developer of encryption scheme conducted a preliminary analysis of its security and gave recommendations regarding the selection of parameters that guarantee its security against attacks considered by him. In addition, further research shows that NTRUCipher is vulnerable to several other attacks, and the natural way to modify this encryption scheme to make it more robust does not lead to success. As a result, there is a need to create methods of constructing provable secure NTRU-like encryption schemes, which differ in essence from the known one. Thus, there is a certain contradiction between the needs of practice in provable secure post-quantum (in particular, NTRU-like) symmetric encryption schemes and the lack of methods for constructing such encryption schemes. This contradiction leads to a scientific problem, which consists in the development of a method of constructing provable secure NTRU-like encryption schemes against chosen-plaintext attacks. The methods of finite field theory, discrete Fourier transform theory on finite Abelian groups, linear algebra, probability theory, and correlation cryptanalysis were used to solve the scientific problem. The aim of Ph.D thesis is to create provable secure symmetric NTRU-like encryption schemes for information security systems in information and communication systems. The object of research in Ph.D thesis is a process of information transformation using modern NTRU-like encryption schemes, and the subject of research is methods of constructing and security evaluation of encryption schemes against chosen-plaintext attacks. For the first time, analytical relations for estimating the probability of reversibility of random polynomials used in NTRU-like encryption schemes were obtained. In contrast to the known relation for the probability of reversibility of a random equiprobable element of a truncated polynomials ring, the obtained relations are valid for a more general scheme of random polynomials formation. They are based on the application of the Fourier transformation of probability distributions on a finite field and make it possible to estimate (and in some practically important cases to calculate) the probability value of reversibility of random polynomials used as components of secret keys of NTRU-like encryption schemes. Analytical relations for estimating decryption failure probability in NTRUlike encryption schemes were improved. Unlike the previously known ones, the obtained relations are valid for all types of modern NTRU-like encryption schemes (both asymmetric and symmetric one). In addition, they make it possible to estimate the decryption failure probability of messages in NTRU-like encryption schemes for a fixed key, thus providing more adequate information about the frequency of decryption failure. The method of estimating the security of symmetric encryption schemes NTRUCipher and NTRUCipher+ due to the research of three additional attacks on these encryption schemes was further developed. Analytical estimates of complexity for the mentioned attacks were obtained and it was shown that at least one of them can be implemented in real time (although it does not allow to recover the keys of encryption schemes but only to distinguish the sequences of their encrypted messages from a purely random sequence). For the first time, the method of constructing provable secure NTRU-like encryption schemes was proposed. It is shown that, in contrast to known symmetric NTRU-like encryption schemes, the proposed encryption schemes have provable security against chosen plaintext attacks, which is based on the complexity of reference computational Decision-Ring-LWE problem. The practical significance of the obtained results consist in developing the software implementations that allow in real time to calculate the parameters values for constructing proposed provable secure NTRU-like encryption schemes, to calculate the probability of reversibility of random polynomials and the decryption failure probability in arbitrary NTRU-like encryption schemes. In addition, the results obtained in this thesis allow: -reduce the probability of irreversibility of a random polynomial in the ring Rn.q (з 0,5 до 2 15 10- , - ) due to proper selection of parameters q and n of NTRU-like encryption scheme; -choose the parameters of NTRU-like encryption schemes that provide an appropriate (small) value of decryption failure probability of messages for a fixed secret key; -establish that complexity of BKW-attack on the NTRUCipher+ encryption scheme is in 15 2 - 69 2 times higher compared to the complexity of a similar attack on the NTRUCipher encryption scheme; -prove that the NTRUCipher+ encryption scheme is quite vulnerable to a distinguishing attack that can be implemented in real time (at the same time, the largest value of the material’s amount required to implement the attack is 19 t -2 ); -choose parameters of NTRU-like encryption schemes that guarantee their security at a predetermined level - (in particular n -631, q -2693 , d -56 at 128 --2 , n -883, q -256 --2 ). Scientific and practical results of the thesis were implemented at the Foreign Intelligence Service of Ukraine (in the research scientific works «Dorado» and «Sargan») and in the scientific and technical developments of JSC «Institute of Information Technologies».uk
dc.format.extent183 с.uk
dc.identifier.citationМатійко, А. А. Метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем : дис. … д-ра філософії : 125 Кібербезпека / Матійко Александра Андріївна. – Київ, 2023. – 183 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/63144
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectкібербезпекаuk
dc.subjectкриптоаналізuk
dc.subjectпостквантова криптографіяuk
dc.subjectкриптосистеми на основі решітокuk
dc.subjectстатистичні атакиuk
dc.subjectNTRU-подібні шифросистемиuk
dc.subjectобґрунтування стійкостіuk
dc.subjectймовірність помилкового розшифруванняuk
dc.subjectcybersecurityuk
dc.subjectcryptanalysisuk
dc.subjectpost-quantum cryptographyuk
dc.subjectlatticebased cryptosystemsuk
dc.subjectstatistical attacksuk
dc.subjectNTRU-like encryption schemesuk
dc.subjectprovable securityuk
dc.subjectdecryption failure probabilityuk
dc.subject.udc621.391:519.2:004.056.55uk
dc.titleМетод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистемuk
dc.typeThesis Doctoraluk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Matiyko_dys.pdf
Розмір:
4.17 MB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.1 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Дисертації (СК №1)
Дисертації (вільний доступ)