Record Details

Application of fast Fourier transform for solving of the LPN problem over finite frobenius rings

Наукові журнали Національного Авіаційного Університету

View Archive Info
 
 
Field Value
 
Title Application of fast Fourier transform for solving of the LPN problem over finite frobenius rings
Применение быстрого преобразования Фурье для решения задачи LPN над конечными фробениусовыми кольцами
Застосування швидкого перетворення Фур’є для розв’язання задачі LPN над скінченними фробеніусовими кільцями
 
Creator Олексійчук, Антон Миколайович; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
Ігнатенко, Сергій Михайлович; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
 
Subject Information security
cryptology; provable security; LPN problem; system of linear equations corrupted by noise; fast Fourier transform; finite Frobenius ring
UDC 621.391:519.2
Информационная безопасность
криптология; обоснованная стойкость; задача LPN; система линейных уравнений с искаженными правыми частями; быстрое преобразование Фурье; конечное фробениусово кольцо
УДК 621.391:519.2
Інформаційна безпека
криптологія; обґрунтована стійкість; задача LPN; система лінійних рівнянь зі спотвореними правими частинами; швидке перетворення Фур’є; скінченне фробеніусове кільце
УДК 621.391:519.2
 
Description The LPN problem is one of the most famous hard computational problems. In the most general formulation, it consists in solving a system of linear equations corrupted by noise over an arbitrary finite ring and includes, as a special case, the problem of decoding a random linear code over a finite field. Numerous (both symmetric and asymmetric) cryptosystems and protocols, which resistance relies on the complexity of solving the LPN problem are known. Therefore, the development of more efficient algorithms for solving this problem, in comparison with known algorithms, is an actual direction of modern cryptology. The most reliable (and most time-consuming) method for solving the LPN problem is the maximum likelihood method. It is well known that for systems of linear equations corrupted by noise over a finite field or a residue ring modulo power of two the complexity of this method can be reduced by applying algorithms for the fast Fourier transform. At the same time the question of how wide is the class of finite rings with this property remains open. In this paper we show that this is the class of finite Frobenius rings. This class is very extensive and includes, in particular, any (left or right) principal ideal ring. The obtained results indicate that it is possible to apply algorithms for the fast Fourier transform, well known for the case of a finite field or a residue ring modulo power of two, to the solving the LPN problem over an arbitrary finite Frobenius ring. This makes to significantly reduce the complexity of solving this problem by the maximum likelihood method.
Задача LPN является одной из самых известных вычислительно трудных задач. В наиболее общей постановке она состоит в решении системы линейных уравнений с искаженными правыми частями над произвольным конечным кольцом и включает в себя, в качестве частного случая, задачу декодирования случайного линейного кода над конечным полем. Известны (как симметричные, так и асимметричные) криптосистемы и протоколы, стойкость которых базируется на сложности решения задачи LPN. Поэтому разработка более эффективных, по сравнению с известными, алгоритмов решения этой задачи является актуальным направлением современной криптологии. Наиболее надежным (и наиболее трудоемким) методом решения задачи LPN является метод максимума правдоподобия. Известно, что для систем линейных уравнений с искаженными правыми частями над конечным полем или кольцом вычетов по модулю степени двойки можно уменьшить трудоемкость этого метода, применяя алгоритмы быстрого преобразования Фурье. Вместе с тем, вопрос о том, насколько широким является класс конечных колец с указанным свойством остается открытым. В данной статье показано, что таким является класс конечных фробениусовых колец. Этот класс очень обширный и включает в себя, в частности, любые кольца главных (левых или правых) идеалов. Полученные результаты свидетельствуют о том, что при решении задачи LPN над произвольным конечным фробениусовым кольцом можно применять алгоритмы быстрого преобразования Фурье, хорошо известные для случая конечного поля или кольца вычетов по модулю степени двойки. Это дает возможность заметно уменьшить трудоемкость решения указанной задачи методом максимума правдоподобия.
Задача LPN є однією з найвідоміших обчислювально складних задач. В найбільш загальному формулюванні вона полягає в розв’язанні системи лінійних рівнянь зі спотворенимим правими частинами над довільним скінченним кільцем і включає в себе, як окремий випадок, задачу декодування випадкового лінійного коду над скінченним полем. На сьогодні відомі (як симетричні, так і асиметричні) криптосистеми і протоколи, стійкість яких базується на складності розв’язання задачі LPN. Тому розробка більш ефективних, в порівнянні з відомими, алгоритмів вирішення цієї задачі є актуальним напрямом сучасної криптології. Найнадійнішим (та найбільш трудомістким) методом розв’язання задачі LPN є метод максимуму правдоподібності. Відомо, що для систем лінійних рівнянь зі спотвореними правими частинами над скінченним полем або кільцем лишків за модулем степеня двійки можна зменшити трудомісткість цього методу, використовуючи алгоритми швидкого перетворення Фур’є. Поряд з тим, питання про те, наскільки широким є клас скінченних кілець із зазначеною властивістю є на сьогодні відкритим. В даній статті показано, що таким є клас скінченних фробеніусових кілець. Цей клас є дуже потужним і включає в себе, зокрема, будь-які кільця головних (лівих чи правих) ідеалів. Отримані результати свідчать про те, що при розв’язанні задачі LPN над довільним скінченним фробеніусовим кільцем можна використовувати алгоритми швидкого перетворення Фур’є, добре відомі для випадку скінченного поля або кільця лишків за модулем степеня двійки. Це надає можливість помітно зменшити трудомісткість розв’язання цієї задачі методом максимуму правдоподібності.  
 
Publisher National Aviation University
 
Contributor —
—
—
 
Date 2017-12-11
 
Type —
—
—
 
Format application/pdf
application/pdf
application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/ZI/article/view/12109
10.18372/2410-7840.19.12109
 
Source Ukrainian Information Security Research Journal; Том 19, № 4 (2017); 271-277
Защита информации; Том 19, № 4 (2017); 271-277
Захист інформації; Том 19, № 4 (2017); 271-277
 
Language uk
 
Rights Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим: Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договоронности, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами: Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
 

Технічна підтримка: НДІІТТ НАУ