Генерація загальносистемних параметрів для криптосистеми Falcon для 256, 384, 512 біт безпеки

Автор(и)

  • І.Д. Горбенко
  • С.О. Кандій
  • М.В. Єсіна
  • Є.В. Острянська

DOI:

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

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

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

Анотація

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

Посилання

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.

Сryptography Standardization Process. Electronic resource]. Access mode: http://www.nist.gov/pqcrypto.

Post-Quantum Cryptography. Round 2 Submissions. [Electronic resource]. Access mode: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions.

Falcon. [Electronic resource]. Access mode: https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions.

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. [Electronic resource]. Access mode: http://eprint.iacr.org/2017/916.

Dominique Unruh. Post-quantum security of fiat-shamir // IACR Cryptology ePrintArchive, 2017:398, 2017.

Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and newcryptographic constructions // Richard E. Ladner and Cynthia Dwork, editors,40th ACM STOC,pages 197–206. ACM Press, May 2008.

PQC Standardization Process: Third Round Candidate Announcement. July 22, 2020. [Electronic resource]. Access mode: https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement

Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction // Marc Fischlin and Jean-Sébastien Coron, editors,EUROCRYPT 2016, Part I, volume9665 ofLNCS, pages 820–849, Vienna, Austria, May 8–12, 2016. Springer, Heidelberg,Germany.

Thomas Prest. Sharper bounds in lattice-based cryptography using the Rényi divergence // Takagiand Peyrin [TP17], pages 347–374.

Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretchedNTRU assumptions – cryptanalysis of some FHE and graded encoding schemes // Matthew Robshaw and Jonathan Katz, editors,CRYPTO 2016, Part I, volume 9814 ofLNCS, pages 153–178, Santa Barbara, CA, USA, August 14–18, 2016. Springer, Heidel-berg, Germany.

Thomas Prest.Gaussian Sampling in Lattice-Based Cryptography // Theses, École NormaleSupérieure, December 2015

##submission.downloads##

Номер

Розділ

Статті