Аналіз захищеності постквантового алгоритму електронного підпису rainbow від потенційних атак - Малєєва, Г. А. (ХНУРЕ, 2021)
Многомерная криптография на основе открытого ключа является кандидатом для постквантовой криптографии, и это позволяет генерировать особенно короткие подписи и быструю проверку. Схема подписей Rainbow, предложенная Дж. Дином и Д. Шмидтом, является такой многомерной криптосистемой и считается защищенной от всех известных атак. Необходимость проведения исследований ЦП Rainbow обосновывается тем, что назрела необходимость разработки и принятия постквантового национального стандарта ЦП, а также тем, что в процессе проведения конкурса NIST США математических основ применения метода криптографического преобразования Rainbow получены перспективные результаты. Поэтому считается важным их учет и использование в Украине. Схема подписи Rainbow может быть реализована просто и эффективно с помощью линейных алгебраических методов над небольшим конечным полем и, в частности, создает короткие подписи, в отличие от тех, что используются в RSA и других постквантовых подписях. Во 2-м раунде NIST PQC предлагаются защищенные наборы параметров Rainbow и проанализированы несколько атак на них. При сравнении ЭП предпочтение отдается методам ЭП, которые прошли отбор по безусловными критериям, а также имеют лучшие показатели по интегральным условным критериям, поскольку такая методика является более рациональной. В частности, атака Rainbow-Band-Separation (RBS) является лучшей среди известных атак на Rainbow с определенным набором параметров и важна. Атака Rainbow-Band-Separation восстанавливает секретный ключ Rainbow, решая определенные системы квадратичных уравнений, а его сложность оценивается по известному показателю, который называется степенью регулярности. Однако, как правило, степень регулярности больше, чем степень решения в экспериментах, и точной оценки получить невозможно. В работе предложен новый показатель сложности атаки Rainbow-Band-Separation с помощью алгоритма F4, который дает более точную оценку по сравнению с показателем, использует степень регулярности. Цель работы – сравнительный анализ ЭП на основе MQ-преобразований по критерию устойчивость-сложность и попытка понять безопасность Rainbow от атаки RBS с помощью F4.
Keywords: многомерная криптография; анализ атак; постквантовий период