Свойства координатных функций одного класса подстановок на Fn | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/15

Свойства координатных функций одного класса подстановок на Fn

В классе Fn подстановок на Fn, координатные функции которых существенно зависят от всех переменных, рассматривается подкласс Kn, подстановки в котором получены из тождественной подстановки с помощью n независимых транспозиций. Приводятся некоторые свойства координатных функций подстановок из Kn. Экспериментально подсчитана мощность |Kn| для n = 3,..., 6.

Properties of coordinate functions for a class of permutations on Fn.pdf Для n E Z обозначим через Fn класс функций F : Fn ^ Fn, где F = (f1... fn), таких, что координатные функции f : Fn ^ F2, г = 1,... , n, существенно зависят от всех n переменных и функция F - подстановка (т.е. обратима). В [1] предложен алгоритм построения некоторой функции из Fn, который состоит в следующем: стартуя с тождественной подстановки F, на г-м шаге, г = 1,... , n, выбираем пару наборов a, b, отличающихся только в г-й компоненте и не выбранных на предыдущих шагах, и меняем местами значения F(a) и F(b). Обозначим класс подстановок, которые можно получить алгоритмом (при всевозможных способах выбора пар a,b), через Kn. В [1] доказано, что Kn = 0 для всех n> 2 и K2 = F2 = 0. В данной работе приведены результаты исследования функций из Kn. Для булевой функции f от n переменных обозначим w(f) вес функции f, deg f - её степень, N/ - нелинейность (расстояние до класса аффинных функций A(n)), cor(f) - максимальный порядок корреляционной иммунности, AI(f) -алгебраическую иммунность; пусть d(f, д) -расстояние между функциями f и д. Утверждение 1. Пусть F = (f1... fn) E Kn, n > 2. Тогда для всех г E {1,... , n} имеет место: 1) deg fi = n - 1; 2) = 2; 3) cor(fi) = 0; 4) AI(fi) = 2. Доказательство. 1) По построению d(fi,xi) = 2, т.е. w(fi ф xi) = 2. По утверждению о связи веса и степени функции [2, лемма 3] w(fi ф xi) ^ 2n-deg(/i®xi). Отсюда получаем deg(fi ф xi) = = n - 1 и, ввиду равенства deg(fi ф xi) = deg fi, свойство 1 доказано. 2) N/. ^ 2, так как d(fi,xi) = 2 и xi E A(n); N/. = 0, так как degfi = n - 1 > 1; N/. = 1, так как fi и все аффинные функции, кроме констант, уравновешены, а векторы значений уравновешенных функций не могут отличаться ровно на одном наборе. 3) Свойство следует из неравенства Зигенталера [2, лемма 4] для уравновешенных функций: cor(fi) ^ n - deg fi - 1 = 0. AI(/)-2 n - 1 4) В [3, теорема 1] получена следующая оценка: N/ ^ 2 Е ( • ). С учётом i=0 г N/ = 2 отсюда получаем AI(fi) ^ 2. С другой стороны, никакая аффинная функция д = const не может быть аннигилятором fi, так как иначе, ввиду уравновешенности fi и д, получим д = fi, что не так (fi E A(n)). То же верно и для аннигилятора функции fi ф 1. Следовательно, AI(fi) = 2. Утверждение доказано. ■ Замечание 1. Утверждение 1 остаётся верным и для модификации алгоритма построения подстановок из класса Kn, предложенной в [1] и состоящей в том, что отправной точкой алгоритма является не обязательно тождественная подстановка, а такая, что каждая координатная функция существенно зависит ровно от одной переменной (т. е. fi = xj или fi = xj). Приведём некоторые экспериментальные данные. В таблице указаны мощности классов Kn для n = 3,..., 6; для построения всех функций из понадобилось больше 1,5 ч. Мощность |Kn| быстро растёт с ростом n, тем не менее |Kn| ^ |Fn|; например, в результате перебора 8! = 40 320 подстановок на F3 установлено, что |F3| = 24576. n |Kn| 3 8 4 608 5 250 624 6 390 317 056 Обозначим Kn класс подстановок, которые можно получить с помощью модификации алгоритма (см. замечание 1). Очевидно, что |K| ^ 2nn!|Kn| (2n способов инвертировать переменные и n! способов переставить их); в частности, для n = 3 эта граница равна 384, для n = 4 - уже 233 472 и т. д. Вопрос о достижимости границы и близости к ней мощности |K | составляет предмет дальнейших исследований. Экспериментально подсчитаны характеристики координатных функций fi подстановок из Fn. Для n = 3 оказалось, что всегда Nf Е {0, 2}, deg fi Е {1, 2}. Все подстановки на F2 перебрать не удалось; из 10 000 000 опробованных оказалось, что классу F4 принадлежат 7842 917 и для них Nf Е {2, 4} и deg fi Е {2, 3}. Поскольку отмеченные в утверждении 1 свойства 2-4 координатных функций подстановок из Kn (а в силу замечания 1 - и из Кг) свидетельствуют об их криптографической слабости, актуальна задача разработки алгоритма построения любой подстановки класса Fn. Кроме того, для синтеза криптосхем с функциональными ключами [4, 5] интересны обратимые векторные булевы функции, координатные функции которых зависят от заданного числа (не от всех) аргументов. В [1,6] полностью решена задача существования таких функций; остаётся открытым вопрос их построения и исследования криптографических свойств.

Ключевые слова

векторная булева функция, обратимые функции, нелинейность булевой функции, корреляционная иммунность, алгебраическая иммунность, vector Boolean functions, invertible functions, non-linearity, correlation immunity, algebraic immunity

Авторы

ФИООрганизацияДополнительноE-mail
Карпова Любовь Александровна Томский государственный университет студентка кафедры защиты информации и криптографииlubakarpova1135@gmail.com
Панкратова Ирина Анатольевна Томский государственный университет кандидат физико-математических наук, доцент, доцент кафедры защиты информации и криптографииpank@isc.tsu.ru
Всего: 2

Ссылки

Pankratova I. A. Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables // Материалы Междунар. науч. конгресса по информатике: Информационные системы и технологии. Республика Беларусь, Минск, 24-27 окт. 2016. Минск: БГУ, 2016. С. 519-521.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях // Матем. вопросы кибернетики. 2002. Вып. 11. С. 91-148.
Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Т. 18. Вып.3. С. 152-159.
Агибалов Г. П. SIBCiphers - симметричные итеративные блочные шифры из булевых функций с ключевыми аргументами // Прикладная дискретная математика. Приложение. 2014. №7. С. 43-48. URL: http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000488056
Агибалов Г. П. Криптоавтоматы с функциональными ключами // Прикладная дискретная математика. 2017. №36. С. 59-72.
Панкратова И. А. Об обратимости векторных булевых функций // Прикладная дискретная математика. Приложение. 2015. №8. С. 35-37. URL: http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000515624
 Свойства координатных функций одного класса подстановок на F<sup>n</sup> | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/15

Свойства координатных функций одного класса подстановок на Fn | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/15