Оптимізація функції множення поліномів для звичайної та product форми задання одного з поліномів

Анотація

У роботі проведено дослідження та виконано розробку ефективного алгоритму множення тернарного полінома у кільці  з урахуванням його структури. Розглядаються варіанти для поліномів із звичайною структурою з фіксованою кількістю ненульових елементів «1» («–1») та у PRODUCT-формі, у якій поліном є результатом обчислення , де  та мають відповідно  елементів із значеннями «1» та «–1». Приводяться результати оптимізації за допомогою векторизованих наборів інструкцій (а саме, набір інструкцій AVX2), розпаралелювання та спеціальних засобів для мінімізації та компенсування використання не вирівняної пам’яті. Критичний код написано на асемблері під мікропроцесорну архітектуру x86-64, яка є однією з найрозповсюдженіших на сьогоднішній день. Отримані часові показники оптимізованої реалізації алгоритму для наборів параметрів для 256, 384 та 512 біт класичної безпеки та зроблено порівняння ефективності з алгоритмом множення поліномів, що був запропонований у асиметричній постквантовій криптосистемі на алгебраїчних решітках NTRU Prime. Тестування здійснено на процесорі Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz на операційній системі Linux 4.15.0-44-generic #47-Ubuntu SMP x86-64. Результати, що отримані, на наш погляд — надзвичайно актуальні. Вони можуть бути корисними для криптологів та інших фахівців, що займаються розробкою нових, ефективних криптографічних алгоритмів та протоколів для постквантового періоду. Це пояснюється тим, що для класів криптосистем, у яких використовуються перетворення у кільцях поліномів, як базові операції, а саме операцій множення, займає найбільше часу та тому потребує значної оптимізації. Значна перевага розробленого алгоритму — можливість його розпаралелювання на багатопроцесорних системах, що є значною перевагою порівняно з алгоритмом, що представлені в NTRU Prime.