DOI: https://doi.org/10.32626/2308-5878.2019-19.28-34

Оптимізація функції множення поліномів для звичайної та 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.


Повний текст:

PDF

Посилання


Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja lange, and Christine van Vredendaal. NTRU Prime. URL: https://ntruprime.cr.yp.to/ntruprime-20160511.pdf.

Gorbenko I. D., Alekseychuk A. N., Kachko O. H., Yesina M. V., Bobukh V. A., Kandyi S. O., Ponomar V. A. Calculation of general parameters form NTRU Prime Ukraine of 6-7 levels of stability. Radiotekhnika : All-Ukr. Sci. Indep. Mag. Kharkiv : KNURE. 2019. № 195. P. 17–25.

Agner Fog. Optimizing subroutines in assembly language. URL: https://www.agner.org/optimize/ optimizing_assembly.pdf.