Застосування послідовного методу для побудови статистичної атаки на шифросистему LPN-C над кільцем лишків за модулем 2N

Анотація

Шифросистема LPN-C є однією з перших постквантових симетричних шифросистем, стійкість яких базується на складності розв’язання задачі LPN. Оригінальна версія шифросистеми визначається над полем з двох елементів, проте вона природним чином узагальнюється на випадок довільного скінченного кільця. Як правило, таке узагальнення, пов’язане з ускладненням алгебраїчної структури об’єкту, на основі якого будується та чи інша шифросистема, збільшує її стійкість відносно відомих атак, проте, як показано нижче, шифросистема LPN-C над кільцем за модулем 2N являє собою виняток з цього правила. В даній статті запропоновано атаку на шифросистему LPN-C над кільцем лишків за модулем 2N, яка полягає у відновленні ключа шляхом послідовного розв’язання Nсистем лінійних рівнянь зі спотвореними правими частинами над полем з двох елементів. Показано, що запропонована атака є суттєво більш ефективною в порівнянні з традиційною атакою того ж самого типу, що базується на безпосередньому розв’язанні зазначеної системи рівнянь за допомогою узагальненого алгоритму BKW. Отримані результати свідчать про недоцільність застосування для побудови шифросистем LPN-C кілець лишків за модулем 2N при N≥2, оскільки це не призводить до суттєвого підвищення стійкості у порівнянні з випадком N=1.