Застосування швидкого перетворення Фур’є для розв’язання задачі LPN над скінченними фробеніусовими кільцями

Анотація

Задача LPN є однією з найвідоміших обчислювально складних задач. В найбільш загальному формулюванні вона полягає в розв’язанні системи лінійних рівнянь зі спотворенимим правими частинами над довільним скінченним кільцем і включає в себе, як окремий випадок, задачу декодування випадкового лінійного коду над скінченним полем. На сьогодні відомі (як симетричні, так і асиметричні) криптосистеми і протоколи, стійкість яких базується на складності розв’язання задачі LPN. Тому розробка більш ефективних, в порівнянні з відомими, алгоритмів вирішення цієї задачі є актуальним напрямом сучасної криптології. Найнадійнішим (та найбільш трудомістким) методом розв’язання задачі LPN є метод максимуму правдоподібності. Відомо, що для систем лінійних рівнянь зі спотвореними правими частинами над скінченним полем або кільцем лишків за модулем степеня двійки можна зменшити трудомісткість цього методу, використовуючи алгоритми швидкого перетворення Фур’є. Поряд з тим, питання про те, наскільки широким є клас скінченних кілець із зазначеною властивістю є на сьогодні відкритим. В даній статті показано, що таким є клас скінченних фробеніусових кілець. Цей клас є дуже потужним і включає в себе, зокрема, будь-які кільця головних (лівих чи правих) ідеалів. Отримані результати свідчать про те, що при розв’язанні задачі LPN над довільним скінченним фробеніусовим кільцем можна використовувати алгоритми швидкого перетворення Фур’є, добре відомі для випадку скінченного поля або кільця лишків за модулем степеня двійки. Це надає можливість помітно зменшити трудомісткість розв’язання цієї задачі методом максимуму правдоподібності.