Optimization of polynomial multiplication algorithm for NTRU-like algorithms

Jazyk: ukrajinština
Rok vydání: 2020
Předmět:
Zdroj: Радіотехніка; № 200 (2020): Радіотехніка; 15-24
Радиотехника; № 200 (2020): Радиотехника; 15-24
Radiotekhnika; № 200 (2020): Radiotekhnika; 15-24
ISSN: 0485-8972
Popis: The problem of cryptographic protection against classical and potential crypto-analytic attacks with the use of quantum computer and quantum mathematics has become an urgent issue. Understanding this problem, technologically advanced states are making significant efforts to analyze the cryptographic stability of existing standards for cryptographic information security in the post-quantum period and are seeking to establish post-quantum standards for asymmetric cryptography. A practical solution to this problem is being pursued globally during the NIST USA international competition. As previous studies have shown, algebraic lattices are now considered to be a reliable mathematical basis on which post-quantum asymmetric encryptions and PIK can be created. NTRU-like algorithms are a class of crypto-transformations algorithms that satisfy basically the requirements of post-quantum cryptography. Algorithms for key generation direct and reverse cryptographic transformations are the basic components in NTRU-like algorithms for asymmetric crypto-transformations. A number of authors today focus on optimizing polynomial multiplication for these algorithms by the criterion of time complexity. A special requirement for them is the independence of the time of the multiplication operation from the polynomials themselves, which makes it impossible to attack by side channels. This paper proposes the use of the NTT and Toom-Kuk algorithms. It proposes a new solution to this problematic issue, which made it possible to obtain an acceleration of almost 2 times while providing a constant polynomial multiplication time. The objective of this article is to optimize the polynomial multiplication algorithm by the time complexity criterion, used to generate keys and perform direct and reverse cryptographic transformations of asymmetric encryptions and PIK on algebraic lattices.
Сегодня актуальной стала проблема криптографической защиты от классических и потенциальных криптоаналитических атак с использованием квантового компьютера и квантовой математики. Понимая эту проблему, технологически развитые государства направляют существенные усилия на анализ криптографической стойкости существующих стандартов криптографической защиты информации в постквантовый период и ведут исследования по созданию постквантовых стандартов асимметричной криптографии. Практическое решение этой проблемы осуществляется на мировом уровне в процессе проведения NIST США международного конкурса. Как показывают предварительные исследования, надежной математической основой, на которой могут быть созданы постквантовые АСШ и ПИК, сейчас считаются алгебраические решетки. NTRU-подобные алгоритмы – класс алгоритмов криптопреобразования, которые в основном удовлетворяют требованиям постквантовой криптографии. В NTRU-подобных алгоритмах асимметричных криптопреобразований основными составляющими являются алгоритмы генерации ключей и выполнения прямых и обратных криптографических преобразований. Ряд авторов сосредоточены на оптимизации умножения полиномов для этих алгоритмов по критерию временной сложности. Особым требованием к ним является независимость времени выполнения операции умножения от самых полиномов, что делает невозможным осуществлять атаку сторонними каналами. В работе предлагается использовать алгоритмы NTT и Tooмa – Kyка. Предложено новое решение этой проблемы, которое позволило получить ускорение практически в два раза при обеспечении константного времени умножения полиномов. Цель статьи – оптимизация алгоритма умножения полиномов по критерию временной сложности, который используется для генерирования ключей и выполнения прямых и обратных криптографических преобразований АСШ и ПИК на алгебраических решетках.
Наразі актуальною стала проблема криптографічного захисту від класичних та потенційних криптоаналітичних атак з використанням квантового комп’ютера та квантової математики. Розуміючи цю проблему, технологічно розвинені держави направляють суттєві зусилля на аналіз криптографічної стійкості існуючих стандартів криптографічного захисту інформації у постквантовий період та ведуть пошук щодо створення постквантових стандартів асиметричної криптографії. Практичне вирішення цієї проблеми здійснюється на світовому рівні в процесі проведення NIST США міжнародного конкурсу. Як показують попередні дослідження, надійною математичною основою, на якій можуть бути створені постквантові АСШ та ПІК, нині вважаються алгебраїчні решітки. NTRU-подібні алгоритми – клас алгоритмів криптоперетворень, які в основному задовольняють вимогам постквантової криптографії. В NTRU-подібних алгоритмах асиметричних криптоперетворень основними складовими є алгоритми генерування ключів та виконання прямих та зворотних криптографічних перетворень. Ряд авторів сьогодні зосереджені на оптимізації множення поліномів для цих алгоритмів за критерієм часової складності. Особливою вимогою до них є незалежність часу виконання операції множення від самих поліномів, що робить неможливим здійснювати атаку сторонніми каналами. В роботі пропонується використання алгоритмів NTT та Tooмa – Kyка. Запропоновано нове рішення цієї проблеми, яке дозволило отримати прискорення практично в два рази при забезпеченні константного часу множення поліномів. Мета статі – оптимізація алгоритму множення поліномів за критерієм часової складності, який використовується для генерування ключів та виконання прямих та зворотних криптографічних перетворень АСШ та ПІК на алгебраїчних решітках.
Databáze: OpenAIRE
Externí odkaz: