Застосування послідовного методу для побудови статистичної атаки на шифросистему LPN-C над кільцем лишків за модулем 2N
DOI:
https://doi.org/10.18372/2410-7840.20.12956Ключові слова:
постквантова криптографія, шифросистема LPN-С, система лінійних рівнянь зі спотвореними правими частинами, кільце лишків за модулем 2N, послідовний метод, узагальнений алгоритм BKW, швидка статистична атакаАнотація
Шифросистема LPN-C є однією з перших постквантових симетричних шифросистем, стійкість яких базується на складності розв’язання задачі LPN. Оригінальна версія шифросистеми визначається над полем з двох елементів, проте вона природним чином узагальнюється на випадок довільного скінченного кільця. Як правило, таке узагальнення, пов’язане з ускладненням алгебраїчної структури об’єкту, на основі якого будується та чи інша шифросистема, збільшує її стійкість відносно відомих атак, проте, як показано нижче, шифросистема LPN-C над кільцем за модулем 2N являє собою виняток з цього правила. В даній статті запропоновано атаку на шифросистему LPN-C над кільцем лишків за модулем 2N, яка полягає у відновленні ключа шляхом послідовного розв’язання Nсистем лінійних рівнянь зі спотвореними правими частинами над полем з двох елементів. Показано, що запропонована атака є суттєво більш ефективною в порівнянні з традиційною атакою того ж самого типу, що базується на безпосередньому розв’язанні зазначеної системи рівнянь за допомогою узагальненого алгоритму BKW. Отримані результати свідчать про недоцільність застосування для побудови шифросистем LPN-C кілець лишків за модулем 2N при N≥2, оскільки це не призводить до суттєвого підвищення стійкості у порівнянні з випадком N=1.Посилання
А. Алексейчук, С. Игнатенко, "Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 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.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
