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

Антон Миколайович Олексійчук, Сергій Михайлович Ігнатенко

Анотація


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

 


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


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

Посилання


А. Алексейчук, С. Игнатенко, "Нижняя граница вероятности восстановления истинного решения системы линейных уравнений с искаженной правой частью над кольцом вычетов по модулю ", Захист інформації, № 4, С. 6-12, 2006.

А. Алексейчук, С. Игнатенко, "Оценки эффективности универсальных методов восстановления искаженных линейных рекуррент над кольцом вычетов по модулю ", Збірник наукових праць ІПМЕ НАН України, Вып. 20, С. 40-48, 2003.

Г. Балакин, "Введение в теорию случайных систем уравнений", Труды по дискретной математике, М.: ТВП, Т. 1, С. 1-18, 1997.

Р. Блейхут, Быстрые алгоритмы цифровой обработки сигналов Пер. с англ. М.: Мир, 1989, 448 с.

С. Игнатенко, "Модификация метода максимума правдоподобия решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю ", Захист інформації, № 1, С. 63-72, 2007.

А. Левитская, "Системы случайных уравнений над конечными алгебраическими структурами", Кибернетика и системный анализ, Т. 41, № 1, С. 82-116, 2005.

Р. Лидл, Г. Нидеррайтер, Конечные поля, пер. с англ, М.: Мир, 1988, 818 с.

С. Чечёта, Введение в дискретную теорию информации и кодирования: учебное издание, М.: МЦНМО, 2011, 224 с.

M. Albrecht, C. Cid, J. Faugere, R. Fitzpatric, L. Per-ret, "Algebraic algorithms for LWE problems", Cryptology ePrint Archive, Report 2014/1018. [Electronic resource]. Access: 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.

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

J. Golić, G. Morgari, "Vectorial fast correlation attacks", Cryptology ePrint Archive, Report 2004/247. [Electronic resource]. Access: http://eprint.iacr.org/ 2004/247.

F. Jönsson, T. Johansson, "Correlation attacks on stream ciphers over ", The 2001 International Symposium on Information Theory. ISIT’2001, Proceedings. Springer Verlag, pp. 140, 2001.

A. Juels, S. Weis, "Authenticating pervasive devices with Human protocols", Crypto’95. LNCS 3126. Springer-Verlag, pp. 293-308, 1995.

E. Kiltz, D. Masny, K. Pietrsak, "Simple chosen-ciphertext security from low-noise LPN", Public Key Cryptography. PKC 2014. Springer-Verlag, pp. 1-18, 2014.

A. Maximov, T. Johansson, "Fast computation for large distribution and its cryptographic application" Advanced in Cryptology. ASIACRYPT 2005. LNCS 3788. Springer-Verlag, pp. 313- 332.

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

J. Wood, "Duality for modules over finite rings and application to coding theory", Amer. J. Math, vol. 121, pp. 555-575, 1999.

J. Wood, "A coding-theoretic characterization of finite Frobenius rings", [Electronic resource]. Access: https://www.semanticshol.org/paper/2006.

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. [Electronic resource]. Access: 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