Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher

Мета цієї роботи — проведення порівняльного аналізу зазначених шифросистем, а також коректне обґрунтування умов, що забезпечують CPA-стійкість шифросистеми NTRUCipher. Окремим результатом є аналітичні оцінки ймовірності помилкового розшифрування повідомлень для NTRUCipher, що є важливим для належног...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
1. Verfasser:	Матійко, А.А.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Математичне та комп'ютерне моделювання. Серія: Технічні науки
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/168575
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher / А.А. Матійко // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 81-87. — Бібліогр.: 7 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-168575
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1685752025-02-09T14:58:22Z Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher The comparative analysis of ntrucipher and ntruencrypt encryption schemes Матійко, А.А. Мета цієї роботи — проведення порівняльного аналізу зазначених шифросистем, а також коректне обґрунтування умов, що забезпечують CPA-стійкість шифросистеми NTRUCipher. Окремим результатом є аналітичні оцінки ймовірності помилкового розшифрування повідомлень для NTRUCipher, що є важливим для належного вибору параметрів шифросистеми при її практичному застосуванні. The purpose of this article is to conduct a comparative analysis of the abovementioned encryption schemes and to prove correctly the conditions that ensure the CPA-security of the NTRUCipher encryption scheme. A certain result is analytical bounds of decryption failure probability in NTRUCipher encryption scheme. This result is important for the proper parameters’ choice of the encryption scheme in its practical implementation. 2019 Article Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher / А.А. Матійко // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 81-87. — Бібліогр.: 7 назв. — укр. 2308-5916 DOI: 10.32626/2308-5916.2019-19.81-87 https://nasplib.isofts.kiev.ua/handle/123456789/168575 621.391:519.2 uk Математичне та комп'ютерне моделювання. Серія: Технічні науки application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Мета цієї роботи — проведення порівняльного аналізу зазначених шифросистем, а також коректне обґрунтування умов, що забезпечують CPA-стійкість шифросистеми NTRUCipher. Окремим результатом є аналітичні оцінки ймовірності помилкового розшифрування повідомлень для NTRUCipher, що є важливим для належного вибору параметрів шифросистеми при її практичному застосуванні.
format	Article
author	Матійко, А.А.
spellingShingle	Матійко, А.А. Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher Математичне та комп'ютерне моделювання. Серія: Технічні науки
author_facet	Матійко, А.А.
author_sort	Матійко, А.А.
title	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher
title_short	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher
title_full	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher
title_fullStr	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher
title_full_unstemmed	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher
title_sort	порівняльний аналіз алгоритмів шифрування ntruencrypt та ntrucipher
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
url	https://nasplib.isofts.kiev.ua/handle/123456789/168575
citation_txt	Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher / А.А. Матійко // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 81-87. — Бібліогр.: 7 назв. — укр.
series	Математичне та комп'ютерне моделювання. Серія: Технічні науки
work_keys_str_mv	AT matíjkoaa porívnâlʹnijanalízalgoritmívšifruvannântruencrypttantrucipher AT matíjkoaa thecomparativeanalysisofntrucipherandntruencryptencryptionschemes
first_indexed	2025-11-27T02:34:03Z
last_indexed	2025-11-27T02:34:03Z
_version_	1849909154967191552
fulltext	Серія: Технічні науки. Випуск 19 81 10. Малачівський П. С., Пізюр Я. В. Розв’язування задач в середовищі Maple. Львів : Видавництво «РАСТР–7». 2016. 282 с. CHEBYSHEV APPROXIMATION BY RATIONAL EXPRESSION FUNCTIONS OF TWO VARIABLES The method for constructing of Chebyshev approximation by rational expression for function of two variables is proposed. Idea of the method is based on constructing the boundary power-average approximation in p L norm with p   . Least square method with two weight functions is used to construct of this approximation. One weight function ensures the con- struction of power-average approximation, and another refines parameters of rational expression by linearization scheme. Iterative refinement of weight functions values is proposed. Results of test examples solving con- firm the effectivity of proposed method. Key words: Chebyshev approximation by rational expression, function of two variables, power-average approximation, least square method. Одержано 31.01.2019 УДК 621.391:519.2 DOI: 10.32626/2308-5916.2019-19.81-87 А. А. Матійко Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського», м. Київ ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ШИФРУВАННЯ NTRUENCRYPT ТА NTRUCIPHER Асиметрична система шифрування NTRUEncrypt запропо- нована в 1996 р. та є однією з найшвидших постквантових шиф- росистем. Вона включена до стандарту ANSI X9.98-2010 та є прототипом широкого класу криптосистем з однойменною на- звою, стійкість яких базується на складності знаходження коро- тких векторів в деяких решітках. Криптографічні властивості шифросистеми NTRUEncrypt достатньо повно досліджені, а її останні модифікації представлено на поточному конкурсі NIST із стандартизації постквантових асиметричних алгоритмів шиф- рування, інкапсуляції ключів та цифрового підпису. Однією з актуальних задач у галузі криптології є створення симетричних шифросистем, стійкість яких, аналогічно асиметри- чним, базується на складності розв’язанні лише однієї конкретної задачі (наприклад, для RSA це — задача факторизації чисел). У зв’язку з цим в 2017 р. на базі NTRUEncrypt запропонована симе- трична шифросистема NTRUCipher, для якої проведено поперед- ній аналіз стійкості та запропоновано алгоритм вибору парамет- © А. А. Матійко, 2019 Математичне та комп’ютерне моделювання 82 рів. Поряд з тим, у доведенні CPA-стійкості алгоритму шифру- вання NTRUCipher містяться суттєві помилки; до того ж залиша- ється не вирішеною задача порівняльного аналізу шифросистем NTRUCipher та NTRUEncrypt за стійкістю та практичністю. Мета цієї роботи — проведення порівняльного аналізу за- значених шифросистем, а також коректне обґрунтування умов, що забезпечують CPA-стійкість шифросистеми NTRUCipher. Окремим результатом є аналітичні оцінки ймовірності помилко- вого розшифрування повідомлень для NTRUCipher, що є важ- ливим для належного вибору параметрів шифросистеми при її практичному застосуванні. Показано, що значення ймовірності помилкового розшифрування повідомлень у шифросистемі NTRUCipher змінюється в межах від 357 2  до 157 2  водночас як значення цієї ймовірності для шифросистеми NTRUEncrypt змі- нюється в межах від 160 2  до 74 2  . Крім того, отримані оцінки не базуються на жодних евристичних припущеннях. Ключові слова: постквантова криптографія, NTRUEn- crypt, NTRUCipher, ймовірність помилкового розшифрування, CPA-стійкість. Вступ. Однією з актуальних задач у галузі криптології є ство- рення симетричних шифросистем, стійкість яких базується на складно- сті розв’язанні лише однієї конкретної обчислювальної задачі. Прикла- дом такої шифросистеми є NTRUCipher [1], що являє собою симетрич- ний аналог відомої асиметричної шифросистеми NTRUEncrypt [2]. По- передній аналіз стійкості NTRUCipher, проведений в [1], містить суттє- ві помилки. Крім того, залишається не вирішеною задача порівняльно- го аналізу шифросистем NTRUCipher та NTRUEncrypt за стійкістю та практичністю. Мета роботи — проведення порівняльного аналізу зазначених шифросистем, а також коректне обґрунтування умов, що забезпечу- ють CPA-стійкість шифросистеми NTRUCipher. Окремим результа- том є аналітичні оцінки ймовірності помилкового розшифрування повідомлень для NTRUCipher, які не базуються на жодних евристич- них припущеннях. Означення основних понять та загальний опис шифросистем. Нехай n та q — взаємно прості натуральні числа, , 3n q  , q не ді- литься на 3. Позначимо q кільце класів лишків за модулем q , елемен- ти якого ототожнимо з цілими числами, що належать інтервалу [ ( 1) / 2, ( 1) / 2]q q   для непарного q та інтервалу [ / 2, / 2 1]q q  для парного q . Позначимо , [ ] / ( 1) n n q qR x x   — кільце зрізаних поліно- Серія: Технічні науки. Випуск 19 83 мів степеня не вище n над кільцем q , * ,n qR — множину оборотних елементів кільця ,n qR . Нехай S — множина всіх малих поліномів (коефіцієнти яких належать множині { 1 , 0 ,1 }) степеня не вище n , eS — певна фіксо- вана підмножина множини S . Для будь-яких натуральних чисел 1 2,d d позначимо 1 2 ,d dS — множину всіх малих поліномів степеня не вище n , серед коефіцієнтів яких є точно 1d , що дорівнюють 1 , та точно 2d , що дорівнюють 1 . В табл. 1 наведено означення шифросистем NTRUCipher [1] та NTRUEncrypt [2]. Як видно з таблиці, обидві шифросистеми мають схожу будову. При цьому в NTRUCipher використовується тільки секретний ключ, що є у два рази коротше секретного ключа шифро- системи NTRUEncrypt. Отже, основними критеріями, за якими про- ведено порівняльний аналіз зазначених шифросистем, є: 1) малість ймовірності помилкового розшифрування повідомлень [3, 4]; 2) умови стійкості відносно атак на основі підібраних відкритих по- відомлень (CPA-стійкості) [5]. Таблиця 1 Опис шифросистем NTRUEncrypt та NTRUCipher NTRUEncrypt NTRUCipher асиметричний алгоритм шифрування симетричний алгоритм шифрування секретний ключ: ( , ),F g де ,d d F S є таким, що * , 1 3 n q f F R   ; ' 1, ' d d g S   , де ' / 3d n    секретний ключ: ,d d F S є таким, що * , 1 3 n q f F R   відкритий ключ: 3 /h g f (обчислюється в кільці * ,n q R ) __ алгоритм зашифровування: ( , ) ( 3 ) mod h m r m rh e q    , де m S — відкритий текст, ,d d r S та e e S — незалежні випа- дкові поліноми алгоритм зашифровування: ( , ) ( 3 / 3 ) mod h m r m r f e q    , де m S — відкритий текст, ,d d r S та e e S — незалежні випадкові полі- номи алгоритм розшифровування: ( ) (mod ) mod 3 f D c cf q , де ,n q c R — шифротекст алгоритм розшифровування: ( ) (mod ) mod 3 f D c cf q , де ,n q c R — шифротекст Математичне та комп’ютерне моделювання 84 Враховуючи обмеження щодо обсягу статті, доведення отрима- них тверджень не наводяться. Ймовірність помилкового розшифрування повідомлень. В роботі [4] для NTRUEncrypt отримано оцінку ймовірності ( , )erp F g  , { ( ( , )) }m r f hD E m r m   за умови, що {0}eS  , поліноми ,d dF S і ' 1,d dg S  є фіксованими, а коефіцієнти поліномів m , r є незалеж- ними випадковими величинами, розподіленими за законами 1 ( 1) ( 1) 'i ig g d n         , 1 ( 0) 1 2 'ig d n      , ( 1) ( 1) ( 0) 1/ 3i i im m m          , (1) 1 ( 1) ( 1)i ir r dn         , 1 ( 0) 1 2ir dn      ; (2) 2 ( 2) ( , ) 2 exp{ } 72(2 2 ' 1) er q p F g n d d      . (3) Для шифросистеми NTRUCipher має місце таке твердження. Твердження 1. Нехай ,d dF S , {0}eS  , а коефіцієнти поліно- мів m і r є незалежними випадковими величинами, розподіленими за законами (1) і (2) відповідно. Тоді для ймовірності ,( ) { ( ( , )) }er m r f hp F D E m r m   справедлива нерівність 2 ( 8) ( ) 2 exp{ } 72(2 1) er q p F n d     . (4) В табл. 2 для низки пар ( , )n d , перші п’ять з яких рекомендова- но в [6], а дві останні — в [3], наведені значення 2log erp для шиф- росистем NTRUEncrypt та NTRUCipher; при цьому 2048.q  Таблиця 2 Результати оцінювання параметрів, що характеризують частоту виникнення помилок розшифрування ( , )n d 2 log er p (NTRUEncrypt) 2 log er p (NTRUCipher) (401, 113) 160,49 357,69 (449, 134) 138,12 300,18 (677, 157) 99,24 254,32 (1087, 120) 75,84 334,92 (1171, 106) 73,28 380,29 (443, 143) 134,58 280,76 (743, 247) 74,28 157,92 Як видно з даної таблиці, значення ймовірності помилкового ро- зшифрування повідомлень шифросистеми NTRUCipher на декілька Серія: Технічні науки. Випуск 19 85 порядків нижча і змінюється в межах від 357 2  до 157 2  водночас, коли значення цієї ймовірності для шифросистеми NTRUEncrypt змі- нюється в межах від 160 2  до 74 2  . При ( , ) (401, 113)n d  в обох шифросистемах спостерігається найменша ймовірність виникнення помилок розшифрування повідомлень. Умови CPA-стійкості шифросистем. Нагадаємо відоме озна- чення CPA-стійкості симетричної шифросистеми (див., наприк- лад, [5]). Розглядається така «гра» між противником і дослідником: 1) дослідник генерує секретний ключ k ; 2) противник може подавати на вхід оракула kE , що здійснює заши- фрування, будь-які відкриті та отримувати відповідні шифровані повідомлення; 3) противник подає досліднику пару різних повідомлень 0m та 1m однакової довжини; 4) дослідник вибирає випадкове рівноймовірне число {0, 1}b та повертає противнику шифроване повідомлення ( )k bc E m ; 5) противник може звертатися до оракула kE (як в п. 2)) і повинен відновити значення b . Шифросистема називається ( , )T  -CPA-стійкою, якщо будь- який алгоритм відновлення значення b з імовірністю 1 / 2  у наве- деній «грі» виконує не менше ніж T операцій. CPA-стійкість асимет- ричних шифросистем визначається аналогічним чином. Відомі наступні обчислювально складні задачі, пов’язані з NTRU-подібними шифросистемами [7]. Задача 1 (NTRU Decision Key Craking Problem) полягає у встановленні закону розподілу випадкового елемента h , який з імо- вірністю 1 / 2 :  має рівномірний розподіл на множині ,n qR (гіпотеза 0H );  формується за правилом 3 /h r f , де r і f є незалежними ви- падковими елементами з рівно ймовірним розподілом на множи- нах S і ,d dS * ,n q R відповідно (гіпотеза 1H ). Задача 2 (NTRU Search Key Craking Problem) полягає у тому, щоби для заданої множини eS S та згенерованого випадкового рівноймовірного елемента h ,n qR встановити закону розподілу ви- падкового елемента c , який з імовірністю 1 / 2 : Математичне та комп’ютерне моделювання 86  має рівномірний розподіл на множині ,n qR (гіпотеза 0H );  формується за правилом 3( )c hr e  , де r і e є незалежними випадковими елементами з рівноймовірним розподілом на мно- жинах S і eS відповідно (гіпотеза 1H ). Відомо [7], що шифросистема NTRUEncrypt  є CPA-стійкою лише за умови, що обидві задачі (1 і 2) є обчислю- вально складними;  може не бути CPA-стійкою, якщо задача 2 не є обчислювально складною (наприклад, коли {0}eS  ). Другим результатом цієї статті є наступне твердження. Твердження 2. Нехай існує CP-атака на NTRUCipher зі складністю T та ймовірністю успіху 1 / 2  . Тоді існує алгоритм розв’язання За- дачі 1 зі складністю T с та ймовірністю успіху 1/ 2 (1 )  , constс  . Іншими словами, шифросистема NTRUCipher є CPA-стійкою за умови високої обчислювальної складності лише задачі 1. Висновки. Симетрична система шифрування NTRUCipher буду- ється подібно до її асиметричного аналога NTRUEncrypt, але викори- стовує секретний ключ, що має вдвічі меншу довжину. Значення ймовірності помилкового розшифрування повідомлень в NTRUCipher є на декілька порядків нижче і змінюється в межах від 357 2  до 157 2  водночас, як значення цієї ймовірності для NTRUEncrypt змінюється в межах від 160 2  до 74 2  . Крім того, шифросистема NTRUCipher є CPA-стійкою за більш слабких умов в порівнянні з NTRUEncrypt. Для забезпечення стійкості першої шифросистеми достатньо лише високої обчислювальної складності задачі 1, в той час як друга шиф- росистем є стійкою за умови високої складності обох задач 1 і 2 (і може бути не стійкою у протилежному випадку). Список використаних джерел: 1. Valluri M. R. NTRUCipher-lattice based secret key encryption. arXiv: 1710.01928V2. 6/10/2017 2. Hoffstein J., Pipher J., Silverman J.H. NTRU: a new high speed public key cryptosystem. Preprint, presented at the rump session of Crypto’96. 1996. 3. Hirschhorn P., Hoffstein J., Howgrave-Graham N., Whyte W. Choosing NTRU parameters in light of combined lattice reduction and MITM aproaches. Applied Cryptography and Network Security, LNCS. 2009. Vol. 5536. P. 437–455. 4. Олексійчук А. М., Матійко А. А. Оцінки ймовірності помилкового роз- шифрування повідомлень у шифросистемі NTRUEncrypt при фіксовано- му ключі. Захист інформації. 2018. № 2. С. 89–94. 5. Katz J., Lindell Y. Introduction to modern cryptography. CRC Press, 2015. Серія: Технічні науки. Випуск 19 87 6. Chen C., Hoffstein J., Whyte W., Zhang Z. NIST PQ Submission: NTRUEncrypt. A lattice based algorithm. URL: https://cscr.nist.gov/Projects/- Post-Quantum-Cryptorraphy, 2017. 7. Steinfeld R. NTRU cryptosystem: resent developments and emerging mathe- matical problems in finite polynomial rings. URL: http://users.monach.edu.au/- ~rste /NTRU_survey.pdf. 2014. THE COMPARATIVE ANALYSIS OF NTRUCIPHER AND NTRUENCRYPT ENCRYPTION SCHEMES The asymmetric encryption scheme NTRUEncrypt proposed in 1996 and is one of the fastest post-quantum encryption schemes. It is included in the ANSI X9.98-2010 standard and is the prototype of cryptosystems’ wide class with the same name, which security is based on the difficulty of finding short vectors in some lattices. The cryptographic properties of NTRUEncrypt en- cryption scheme are sufficiently explored and its latest modifications are pre- sented at the current NIST competition to standardize post-quantum asym- metric encryption, key encapsulation and digital signature. 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 (for example, for RSA this is the problem of factorization of numbers). Due to this, in 2017 the symmetric encryption scheme NTRUCipher based on NTRUEncrypt was proposed. For it, a preliminary security analysis was performed and a parameter selection algorithm was proposed. At the same time, there are essential errors in the proof of CPA-se- curity of the encryption algorithm NTRUCipher. Moreover, the problem of comparative analysis of NTRUCipher and NTRUEncrypt encryption schemes is not solved for security and practicality. The purpose of this article is to conduct a comparative analysis of the abovementioned encryption schemes and to prove correctly the conditions that ensure the CPA-security of the NTRUCipher encryption scheme. A certain result is analytical bounds of decryption failure probability in NTRUCipher encryption scheme. This result is important for the proper parameters’ choice of the encryption scheme in its practical implementa- tion. It is shown that the decryption failure probability in the NTRUCipher varies from 357 2  to 157 2  while the value of this probability for the NTRUEncrypt encryption scheme varies from 160 2  to 74 2  . In addition, the obtained bounds are not based on any heuristic assumptions. Key words: post-quantum cryptography, NTRUEncrypt, NTRUCipher, decryption failure probability, CPA-security. Одержано 21.01.2019

Порівняльний аналіз алгоритмів шифрування NTRUEncrypt та NTRUCipher

Institution

Ähnliche Einträge