Методи обчислення системних параметрів для електронного підпису «Сrystals-Dilithium» 128, 256, 384 та 512 біт рівнів безпеки

Автор(и)

  • І.Д. Горбенко
  • А.М. Олексійчук
  • О.Г. Качко
  • Ю.І. Горбенко
  • М.В. Єсіна
  • С.О. Кандій

DOI:

https://doi.org/10.30837/rt.2020.3.202.01

Ключові слова:

алгебраїчні решітки, атаки, безпека, загальносистемні параметри, модель безпеки, модель загроз, модель порушника, підпис, поліном, Dilithium

Анотація

На світовому рівні зусилля значного числа криптологів-теоретиків, математиків та криптологів-практиків зосереджені на відкритому конкурсі NIST PQC. Одним із основних завдань конкурсу є розробка та прийняття постквантового чи постквантових стандартів ЕП. Фіналістами другого етапу конкурсу NIST стали три механізми ЕП – CRYSTALS-DILITHIUM, Falcon та Rainbow. Окрім цього були визначені три альтернативні кандидати, які потребують більш детального дослідження. Всесторонній аналіз фіналістів є важливою задачею для криптологів світової криптоспільноти. Причому, безпека, тобто доведення криптографічної стійкості двох кандидатів-фіналістів на стандарт ЕП – CRYSTALS-DILITHIUM та Falcon, ґрунтується на проблемах з теорії та практики алгебраїчних решіток. Метод (схема) ЕП Dilithium ґрунтується на підході, що отримав назву "Fiat-Shamir з перериваннями". У статті розглядається сутність алгоритму ЕП CRYSTALS-DILITHIUM. Також проводиться детальний аналіз можливих атак на алгоритм та механізми їх реалізації. Розглядаються та аналізуються моделі порушника, загроз та безпеки. Надаються основні визначення щодо моделей безпеки ЕП. Описуються основні елементи конструкції механізму перспективного постквантового ЕП Dilithium в узагальненому вигляді. Наводяться загальні оцінки щодо рівня безпеки ЕП Dilithium. Приводиться обґрунтування та сутність моделей загроз, порушника та безпеки. Досліджується стійкість алгоритму ЕП Dilithium. Метою статті є обґрунтування моделі безпеки, класифікація, первинний аналіз та оцінка відомих атак на криптосистему ЕП CRYSTALS-DILITHIUM, встановлення обмежень та розробка практичних алгоритмів обчислення (генерації) загальносистемних параметрів для забезпечення 128, 256, 384 і 512 біт безпеки щодо класичного та 64, 128, 192 та 256 біт щодо квантового криптоаналізу.

Посилання

Chen L, Jordan S, Liu Y-K, Moody D, Peralta R, Perlner RA, Smith-Tone D (2016) Report on Post-Quantum Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105. https://doi.org/10.6028/NIST.IR.8105.

Gorjan Alagic Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process. NISTIR 8309 / Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, Daniel Smith-Tone // 22 July 2020. Режим доступу: https://doi.org/10.6028/NIST.IR.8309.

ЕП Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé CRYSTALS-Dilithium: Algorithm Specifications and Supporting Documentation. Access mode: https://pq-crystals.org/dilithium/data/dilithium-specification.pdf.

Post-Quantum Cryptography. Round 2 Submissions. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions.

Горбенко Ю. І. Аналіз можливостей квантових комп’ютерів та квантових обчислень для криптоаналізу сучасних криптосистем / Ю. І. Горбенко, Р. С. Ганзя // Східно-європейський журнал передових технологій. 2014. № 1/9 (67). С. 8–15.

ISCI’2019: Information Security in Critical Infrastructures. Collective monograph. Edited by Ivan D. Gorbenko and Alexandr A. Kuznetsov. ASC Academic Publishing, USA, 2019. 445 p.

Gorbenko Ivan The problem of cryptographic transformations standardization and the state of its solution / Ivan Gorbenko, Olena Kachko, Oleksandr Kuznetsov, Yurii Gorbenko, Maryna Yesina // VII Міжнар. наук.-техн. конф. “Захист інформації і безпека інформаційних систем” : Праці Науково-технічної конференції, 30–31 травня 2019 р. Львів : Нац. ун-т “Львівська політехніка”, 2019. С. 84-85.

Горбенко І. Д. Порівняння, оцінювання, дослідження можливості використання та переваг постквантових алгоритмів / І. Д. Горбенко, В. А. Пономар, М. В. Єсіна // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні. Київ : Нац. техн. ун-т України "Київський політехнічний інститут імені Ігоря Сікорського", 2017. Вип. 2(34). С. 9-32.

Горбенко Ю. І. Аналіз можливостей квантових комп’ютерів та квантових обчислень для криптоаналізу сучасних криптосистем / Ю. І. Горбенко, Р. С. Ганзя // Східно-європейський журнал передових технологій. 2014. № 1/9 (67). С. 8–15.

Квантовые компьютеры. [Електронний ресурс]. Режим доступу: http://www.nkj.ru/archive/articles/5309/.

Горбенко І. Д., Постквантова криптографія та механізми її реалізації / І. Д. Горбенко, О. О. Кузнецов, О. В. Потій, Ю. І. Горбенко, Р. С., Ганзя, В. А. Пономар // Радиотехника. 2017. Вып. 186. С. 32–52.

ДСТУ 8961:2019 Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів. [Електронний ресурс]. Режим доступу: http://online.budstandart.com/ua/catalog/doc-page.html?id_doc=88056.

Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In ASIACRYPT, pages 598–616, 2009.

Vadim Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT, pages 738–755, 2012.

Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical lattice-based cryptography: A signature scheme for embedded systems. In CHES, pages 530–547, 2012.

Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. Cryptology ePrint Archive, Report 2017/916, 2017. Access mode: https://eprint.iacr.org/2017/916.

Lyubashevsly V (2009) Fiat-Shamir with aborts: Applications to Lattice and Factoring-Based Signatures. International Conference on the Theory and Application of Cryptology and Information Security – ASIACRYPT (Springer), pp. 598-616. https://doi.org/10.1007/978-3-642-10366-7_35.

Don J, Fehr S, Majenz C, Schaffner C (2019) Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. Annual International Cryptology Conference – CRYPTO (Springer), p. 356-383. https://doi.org/10.1007/978-3-030-26951-7_13.

Єсіна М. В. Моделі безпеки постквантових криптографічних примітивів / М. В. Єсіна // Міжнародний науковий симпозіум “Питання оптимізації обчислень (ПОО-XLVІ)”, 2019 р. Математичне на комп’ютерне моделювання. Серія: Технічні науки. Вип. 19. С. 49-55.

V. Shoup On Formal Models for Secure Key Exchange, Theory of Cryptography Library, 1999. [Електронний ресурс]. Режим доступу: http://philby.ucsd.edu/cryptolib/1999/9912.html.

M. Bellare, R. Canetti, H. Krawczyk A modular approach to the design and analysis of authentication and key-exchange protocols. 30th STOC 1998.

Privacy for Code-Based Encryption in the Standard Model. In: Lange T., Takagi T. (eds) Post-Quantum Cryptography. PQCrypto 2017. Lecture Notes in Computer Science, vol 10346. Springer, Cham.

M. Bellare, A. Boldyreva, A. Desai, D. Pointcheval Key-privacy in public-key encryption. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248. Р. 566–582. Springer, Heidelberg (2001). doi:10.1007/3-540-45682-1.

Державна служба спеціального зв’язку та захисту інформації України. Наказ від 20.07.2007 №141 «Положення про порядок розроблення, виробництва та експлуатації засобів криптографічного захисту конфіденційної та відкритої інформації з використанням електронного цифрового підпису» № 862/14129.

Закон України «Про основні засади забезпечення кібербезпеки України» // Відомості Верховної Ради (ВВР). 2017. № 45. Ст. 403.

Закон України «Про електронні довірчі послуги» // Відомості Верховної Ради (ВВР), 2017. № 45. Ст. 400).

Закон України "Про захист інформації в інформаційно-телекомунікаційних системах".

Закон України "Про захист персональних даних.

Горбенко Ю. І. Методи побудування та аналізу криптографічних систем : монографія. Харків : Форт, 2015. 959 с.

Горбенко І. Д. Прикладна криптологія: Монографія / Горбенко І. Д., Горбенко Ю. І. 2-ге вид. Харків : Форт, 2012. 868 с.

Albrecht M.R., Goepfert F., Virdia F., Wunderer T. Revisiting the expected cost of solwing uSVP and applications to LWE // Cryptology ePrint Archive, Report 2017/815. Access mode: http://eprint.iacr.org/2017/815.

Albrecht M.R., Player R., Scott S. On the concrete hardness of learning with errors // Cryptology ePrint Archive, Report 2015/046. Access mode: http://eprint.iacr.org/2015/046.

Rachel Player Parameter selection in lattice-based cryptography. Access mode: https://pure.royalholloway.ac.uk/portal/files/29983580/2018playerrphd.pdf.

Gottfried Herold, Elena Kirshanova and Alexander May. On the asymptotic complexity of solving LWE // Designs, Codes and Cryptography, Jan 2017.

Shi Bai and Steven D. Galbraith. Lattice decoding attacks on binary LWE // Willy Susilo and Yi Mu, editors, ACISP 14, vol. 8544 of LNCS, pages 322–337. Springer, Heidelberg, July 2011.

Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors // Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP 2011, Part I, vol. 6755 of LNCS, pages 403–415. Springer, Heidelberg, July 2011.

Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, and Ludovic Perret. Algebraic algorithms for LWE. Cryptology ePrint Archive, Report 2014/1018, 2014. Access mode: http://eprint.iacr.org/2014/1018.

Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. On the complexity of the BKW algorithm on LWE // Designs, Codes and Cryptography, 74:325–354, 2015.

Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Lazy modulus switching for the BKW algorithm on LWE // Hugo Krawczyk, editor, PKC 2014, vol. 8383 of LNCS, pages 429–445. Springer, Heidelberg, March 2014.

Richard Lindner and Chris Peikert. Better key sizes (and attacks) for LWE-based encryption // Aggelos Kiayias, editor, CT-RSA 2011, vol. 6558 of LNCS, pages 319–339. Springer, Heidelberg, February 2011.

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model // Journal of the ACM, 50(4): 506–519, July 2003.

Leon Groot Bruinderink1 and Peter Pessl2 . Differential Fault Attacks on Deterministic Lattice Signatures.

Lyubachevsky V., Ducas L., Kiltz E. [et all]. CRYSTALS–Dilithium. Techn. rep. NIST (2017). [Electronic resource]. Access mode: https://crc.nist.gov./projects/post-quantum-cryptogtraphy/ round-1-submissions.

Albrecht M.R., Goepfert F., Virdia F., Wunderer T. Revisiting the expected cost of solwing uSVP and applications to LWE // Cryptology ePrint Archive, Report 2017/815. Access mode: http://eprint.iacr.org/2017/815.

Peikert C., How (not) to instanaite Ring-LWE // Cryptology ePrintAchive 2016/351, 2016.

Горбенко І. Д. Особливості побудування та аналіз електронних підписів 5 рівня безпеки для постквантового періоду на основі алгебраїчних решіток / І. Д. Горбенко, О. Г. Качко, А. М. Олексійчук, Ю. І. Горбенко, В. П. Звєрєв, М. В. Єсіна, В. А. Пономар // Прикладная радиоэлектроника. Харьков : ХНУРЭ, 2019. Т. 18, № 3, 4. С. 123–136.

##submission.downloads##

Номер

Розділ

Статті