ИСТИНА

Проект направлен на решение фундаментальных проблем, связанных с исследованием криптографических, алгоритмических и теоретико-сложностных свойств дискретных функций, естественно возникающих как объекты исследований в криптографии, алгебраической комбинаторике, теории кодирования. Предполагаемые исследования будут способствовать дальнейшему развитию некоторых направлений уже сложившихся областей криптографии, математики и информатики. Поэтому они являются актуальными.

Найдена асимптотическая формула для расстояния Хэмминга от класса всех бент-функций от 2n переменных до класса всех булевых функций от 2n переменных, имеющих в полиноме Жегалкина не более k=k(n) нелинейных слагаемых, при n/k-\log_2k\to+\infty. Улучшены нижние оценки доли булевых функций со значением обобщенного уровня аффинности не менее m, где m>2n/3 и n - число переменных. Исследованы алгебраические и комбинаторные свойства булевых функций, связанные со свойством синхронизации этих функций. Описаны новые классы булевых функций, обладающих свойством синхронизации. Найден новый подход, использующий обобщение понятия подходящей матрицы и позволяющий получить конструкции m-устойчивых булевых функций от n переменных с максимальной нелинейностью 2^{n-1}-2^{m+1} для m\ge cn(1+o(1)), где c=0,5789.... Исследовано одно семейство булевых функций, дающее сглаживающие преобразования для слабых источников случайности, удовлетворяющих определенным сложностным требованиям. Получена оценка ранга подмножества X пространства F_2^n через радиус покрытия кода, лежащего в подпространстве линейных зависимостей векторов из X. Найдена верхняя оценка радиуса покрытия кода, порожденного матрицей инцидентности системы Штейнера S(2,4,v). Получены верхняя точная и асимптотическая оценки ранга подмножества X пространства F_2^n, допускающего встраивание системы Штейнера S(2,4,v). Введено и исследовано понятие суммы (n,k)-продуктов с несократимым разложением. Найдена связь этого понятия с существованием m-устойчивых булевых функций от n переменных с максимально возможной нелинейностью 2^{n-1}-2^{m+1}. Получено необходимое и достаточное условие псевдосвободности в многообразии всех элементарных абелевых p-групп для некоторых семейств вычислительных элементарных абелевых p-групп. Построено псевдосвободное семейство групп экспоненциального размера в многообразии всех элементарных абелевых p-групп исходя из произвольной односторонней p-ичной перестановки, удовлетворяющей некоторому дополнительному условию. Показано, что с использованием только ранее задействованных конструкций нельзя построить m-устойчивые булевы функции от n переменных с максимально возможной нелинейностью 2^{n-1}-2^{m+1} при соотношении m/n, асимптотически меньшем 0,505316.... Доказано, что при m\ge3 билинейная сложность задачи умножения матрицы размера m\times2 на матрицу размера 2\times2 над произвольным полем не меньше чем 3m+2. Тот же результат получен для умножения матрицы размера 2\times m на матрицу размера m\times2 и для умножения матрицы размера 2\times2 на матрицу размера 2\times m. Подготовлено и опубликовано 3-е дополненное издание монографии О.А. Логачева, А.А. Сальникова, С.В. Смышляева и В.В. Ященко "Булевы функции в теории кодирования и криптологии".