Процеси та методи вибору загальносистемних параметрів перспективного алгоритму електронного підпису на основі алгебраїчних решіток

Автор(и)

  • В.А Кулібаба

DOI:

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

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

загальносистемні параметри, алгоритми постквантового електронного підпису, алгебраїчні решітки, функції хешування, криптографічна стійкість.

Анотація

Важливою особливістю перехідного та постквантового періоду є застосування нових математичних методів для протидії квантовому криптоаналізу. Особливу увагу світове криптографічне співтовариство приділяє відкритому конкурсу на постквантовий стандарт електронного підпису. Проблемним питанням є доведення стійкості нових математичних методів синтезу перетворень типу електронний підпис, зокрема з використанням алгебраїчних решіток. Проаналізовано існуючі алгоритми електронного підпису 2-го етапу конкурсу NIST. Серед обраних кандидатів на стандарт ЕП два із трьох алгоритмів засновані на алгебраїчних решітках, це CRYSTALS-DILITHIUM та FALCON. NIST випустив заяву про те, що скоріше за все буде обрано один із алгоритмів через однакому математичну базу, що застосовується в обох алгоритмах. Розглядаються основні атаки на алгоритми електронного підпису, засновані на проблемі навчання з помилками, а також параметри алгоритму ЕП Dilithium, що впливають на стійкість та складність перетворень. Розглядаються методи генерування загальносистемних параметрів рівнів стійкості 512 біт класичної та 256 біт квантової безпеки, а також захищеність алгоритму від атак сторонніми каналами. Проаналізовано залежність часу вироблення електронного підпису від ключів. Подано результати обчислень параметрів для рівня стійкості 512/256, а також надано рекомендації щодо вибору загальносистемних параметрів. Розглянуто результати 2-го етапу конкурсу постквантових криптоалгоритмів NIST, а також перспективи стандартизації перетворень типу електронний підпис на 3-му етапі. Зроблено висновки про необхідність більш детального вивчення атак на алгоритми, засновані на проблемі навчання з помилками, а також про важливість генерування загальносистемних параметрів більш високих порядків.

Посилання

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. Access mode: http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf.

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

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. Electronic resource. Access mode: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions.

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.

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

Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP 2011, Part I, volume 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, volume 8383 of LNCS, pages 429–445. Springer, Heidelberg, March 2014.

Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures // 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.

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

Кулібаба В.А., Перспективні методи та системи критптографічного захисту інформації / О.М. Олексійчук, В.А. Кулібаба, М.В. Єсіна, С. О. Кандій, Є.В. Острянська, І.Д. Горбенко // Радіотехніка. 2020. Вип. 200. С. 5-13.

##submission.downloads##

Номер

Розділ

Статті