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

Сергій Михайлович Ігнатенко

Анотація


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

Ключові слова


постквантова криптографія; шифросистема LPN-С; система лінійних рівнянь зі спотвореними правими частинами; кільце лишків за модулем 2N; послідовний метод; узагальнений алгоритм BKW; швидка статистична атака

Посилання


А. Алексейчук, С. Игнатенко, "Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2N", Реєстрація, зберігання і обробка даних, Т. 7, №1,С. 11-23, 2005.

Г. Балакин, Ю. Никольский, "Последовательное применение метода максимума правдоподобия к решению систем уравнений с мешающими параметрами", Обозрение прикл. промышл. матем, Т. 2, Вып. 3, С. 468-476, 1995.

М. Гаврилкевич, В. Солодовников, "Эффективные алгоритмы решения задач линейной алгебры над полем из двух элементов", Обозрение прикл. промышл. матем, Т. 2, Вып. 3, С. 400-437, 1995.

А. Олексійчук, С. Ігнатенко, М. Поремський, "Системи лінійних рівнянь зі спотвореними правими частинами над скінченними кільцями", Математичне та комп’ютерне моделювання. Серія: Технічні науки, вип. 15, С. 150-155, 2017.

M. Albrecht, C. Cid, J.-C. Faugere, R. Fitzpatric, L. Perret, "Algebraic algorithms for LWE problems", Cryptology ePrint Archive, Report 2014/1018. http://eprint.iacr.org/2014/1018.

E. Berlekamp, R. McElice, H. van Tilborg, "On the inherent intractability of certain coding problems", IEEE Trans. Inform. Theory, vol. 24, no. 3, pp. 384-386, 1978.

A. Blum, A. Kalai, H. Wasserman, "Noise-tolerant learning, the parity problem, and the statistical query model", J. ACM, vol. 50, no. 3, pp. 506-519, 2003.

A. Blum, M. Furst, M. Kearns, R. Lipton, "Cryptographic primitives based on hard learning problems", Crypto’93. LNCS 773. Springer-Verlag, pp. 278-291.

S. Bogos, F. Tramer, S. Vaudenay, "On solving LPN using BKW and variants. Implementation and Analysis", Cryptology ePrint Archive, Report 2015/049. http://eprint.iacr.org/2015/049.

H. Gilbert, J.B. Mattew, M.J.B. Robshaw, Y. Seurin, "How to Encrypt with the LPN Problem", ICALP (2), Proceedings. Springer Verlag, pp. 679-690, 2008.

O. Regev, "On lattices, learning with errors and random linear codes, and Cryptography", STOC 2005, Proceedings. Springer Verlag, pp. 84-93, 2005.

B. Zhang, C. Xu, W. Meier "Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0", Cryptology ePrint Archive, Report 2016/311. http://eprint.iacr.org/2016/311.


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

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory

Ulrich's Periodicals Directory