Record Details

Верхні оцінки значень індексу розгалуження матриць над кільцями лишків за модулем степеня двійки

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

View Archive Info
 
 
Field Value
 
Title Верхні оцінки значень індексу розгалуження матриць над кільцями лишків за модулем степеня двійки
Upper bounds for a branch number of matrices over a ring of integers modulo power of two
Верхние оценки значений индекса ветвления матриц над кольцами вычетов по модулю степени двойки
 
Creator Курінний, Олег Вікторович; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
Яковлєв, Сергій Володимирович; Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
 
Subject Інформаційна безпека
індекс розгалуження; кільце лишків; двійкові матриці; диференціальний криптоаналіз; лінійний криптоаналіз
УДК 004.056.55:512.643
Information security
branch number; ring of integers modulo n; binary matrices; differential cryptanalysis; linear cryptanalysis
UDC 004.056.55:512.643
Информационная безопасность
индекс ветвления; кольцо вычетов; двоичные матрицы; дифференциальный криптоанализ; линейный криптоанализ
УДК 004.056.55:512.643
 
Description Індекс розгалуження – один з найважливіших криптографічних параметрів лінійних перетворень у блокових шифрах, який суттєво впливає на стійкість до диференціального та лінійного криптоаналізу. Добре відомі методи побудови у матричній формі лінійних перетворень над скінченними полями, які мають максимально можливе значення індексу розгалуження (MDS-матриці). У той же час важливе криптографічне значення мають операції у кільці лишків за модулем степеня двійки, оскільки вони ефективно реалізуються у сучасних обчислювальних архітектурах і при цьому підвищують стійкість криптоперетворень до алгебраїчних атак. Відомі методи побудови MDS-матриць незастосовні для кілець лишків за непростим модулем. У даній роботі доведено, що матриця над будь-яким кільцем лишків за парним модулем не може мати максимальний індекс розгалуження. Також доведено, що індекс розгалуження матриць над кільцем лишків за модулем степеня двійки є інваріантом при зведенні матриці за модулем 2, а тому для даного класу матриць будуть справедливі усі відомі аналітичні результати, одержані для класу двійкових матриць – зокрема, верхні обмеження на індекс розгалуження. Сформульовано умови для двійкових матриць, необхідні для високого значення індексу розгалуження. Одержані результати дозволяють будувати блокові шифри із потенційно підвищеною стійкістю до алгебраїчних та інтегральних атак, зберігаючи при цьому обґрунтовану стійкість до диференціального та лінійного криптоаналізу.
Branch number is a very important cryptographic parameter of linear mappings used in block ciphers. It significantly affects security against differential and linear cryptanalysis due to “wide trail strategy” of block cipher design. Many techniques are well known to generate linear mappings with maximal possible branch number in matrix form over finite fields (so-called MDS-matrices). In the same time operations over integers modulo power of two are important for cryptographic purposes. They are very efficient in modern computing architectures and increase security of cryptographic functions against algebraic attacks. But known techniques of MDS-matrix generating are not applicable to a ring of integers modulo composite number. In this work we proved that any square matrix over a ring of integers modulo even number cannot have a maximal branch number. We proved that the branch number of any square matrix over a ring of integers modulo power of two is invariant under reduction modulo 2. Thus, any analytic result known for binary matrices is valid for matrices modulo power of two, including upper bounds for the branch number. Consequently, the branch number of this type of matrix cannot exceed about two thirds of a matrix size. Also we formulated some requirements for binary matrices to obtain high value of the branch number; we show that such matrices cannot have both sparse (low weight) and dense (high weight) columns. At the end we shortly consider how the security of binary ciphers (e.g. ARIA or Midori) against linear and integral cryptanalysis can be increased by replacing binary matrix with matrix over a ring of integers modulo power of two in linear layer. The results of this work allow to create block ciphers with potentially improved security against algebraic and integral attacks and reasonable security against differential and linear cryptanalysis.
Индекс ветвления – один из важнейших криптографических параметров линейных преобразований в блочных шифрах, который существенно влияет на стойкость к дифференциальному и линейному криптоанализу. Хорошо известны методы построения в матричной форме линейных преобразований над конечными полями, которые имеют максимально возможное значение индекса ветвления (MDS-матрицы). В то же время важное криптографическое значение имеют операции в кольцах вычетов по модулю степени двойки, поскольку они эффективно реализуются в современных вычислительных архитектурах и при этом повышают стойкость криптопреобразований к алгебраическим атакам. Известные методы построения MDS-матриц неприменимы для колец вычетов по непростому модулю. В данной работе доказано, что матрица над любым кольцом вычетов по чётному модулю не может иметь максимальный индекс ветвления. Также доказано, что индекс ветвления матрицы над кольцом вычетов по модулю степени двойки инвариантен при сведении матрицы по модулю 2, поэтому для данного класса матриц будут справедливы все известные аналитические результаты, полученные для класса двоичных матриц – в частности, верхние ограничения на индекс ветвления. Сформулированы условия для двоичных матриц, необходимые для высокого значения индекса ветвления. Полученные результаты позволяют строить блочные шифры с потенциально повышенной стойкостью к алгебраическим и интегральным атакам, сохраняя при этом обоснованную стойкость к дифференциальному и линейному криптоанализу.
 
Publisher National Aviation University
 
Contributor —
—
—
 
Date 2020-03-31
 
Type —
—
—
 
Format application/pdf
application/pdf
application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/ZI/article/view/14661
10.18372/2410-7840.22.14661
 
Source Ukrainian Information Security Research Journal; Том 22, № 1 (2020); 27-32
Защита информации; Том 22, № 1 (2020); 27-32
Захист інформації; Том 22, № 1 (2020); 27-32
 
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).
 

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