?
On a new classification of Boolean functions
Математические вопросы криптографии. 2019. Vol. 10. No. 2. P. 159-168.
Федоров С. Н.
Рассматривается недавно предложенный подход к исследованию булевых функций, в основе которого лежит понятие класса Δ-эквивалентности: множества булевых функций с одной и той же функцией автокорреляции. Такая классификация представляется полезной, поскольку многие криптографические характеристики булевых функций, принадлежащих одному и тому же классу Δ-эквивалентности, одинаковы.
Приоритетные направления:
математика
Язык:
английский
Сысоева Л. Н., Moscow University Mathematics Bulletin 2017 Vol. 72 No. 2 P. 61-69
Добавлено: 17 мая 2017 г.
Яшунский А. Д., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 4 С. 3-9
Рассматриваются индуцированные системой булевых функций алгебры бернуллиевских распределений, у которых основное множество имеет единственную предельную точку. Доказан критерий того, что алгебра, порождаемая заданным множеством распределений, имеет единственную предельную точку. ...
Добавлено: 9 сентября 2020 г.
Сысоева Л. Н., Вестник Московского университета. Серия 1: Математика. Механика 2016 № 4 С. 12-17
Рассматривается задача о реализации булевых функций инициальными булевыми ав- томатами с двумя константными состояниями и n входами, т.е. автоматами с двумя состо- яниями, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n ≥ 1. Найдена максимальная возможная мощность множества булевых функций, реализуемых булевым ...
Добавлено: 28 февраля 2017 г.
Сысоева Л. Н., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 6 С. 51-55
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n > 0.
Построен пример инициального булева автомата с минимальным количеством константных состояний и n входами, реализующего максимальное возможное число булевых функций от n фиксированных переменных, при ...
Добавлено: 14 октября 2018 г.
Ложкин С. А., Шуплецов М. С., Коноводов В. А. и др., Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС) 2016 Т. 1 С. 40-47
В работе рассматривается задача построения каталогов схем, реализующих функции алгебры логики малого количества переменных. Эта задача рассматривается на примере синтеза контактных схем. Для решения задачи были разработаны алгоритмы синтеза схем и на их основе реализованы программные инструменты, с помощью которых для целого ряда функций алгебры логики пяти переменных получены новые более оптимальные схемы, а также ...
Добавлено: 2 декабря 2019 г.
Сысоева Л. Н., Moscow University Mathematics Bulletin 2013 Vol. 68 No. 4 P. 211-214
Добавлено: 28 февраля 2017 г.
Lozhkin S. A., Danilov B.R., Computational Mathematics and Modeling 2012 Vol. 23 No. 4 P. 487-506
В работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе Б, в которой задержки базисных элементов по различным входам могут различаться. В рассматриваемой модели получены асимптотические оценки вида τБn±O(1), где τБ ― константа, зависящая только от базиса Б, для задержки мультиплексорной функции порядка n, то есть функции с n адресными и 2n информационными переменными ...
Добавлено: 2 декабря 2019 г.
Сысоева Л. Н., Moscow University Mathematics Bulletin 2016 Vol. 71 No. 4 P. 140-145
Добавлено: 28 февраля 2017 г.
Фомин Д. Б., Математические вопросы криптографии 2019 Vol. 10 No. 2 P. 169-180
В данной работе представлены новые классы 8-ми битовых подстановок, построенных с использованием конструкции типа «бабочка». Данные классы определяют новый способ построения 2n-битовых подстановок с использованием n-битовых. В работе будут представлены классы подстановок обладающие хорошими криптографическими свойствами и могут быть эффективно реализованы как программно так и аппаратно. ...
Добавлено: 4 мая 2019 г.
Ложкин С. А., Данилов Б. Р., Прикладная математика и информатика 2011 № 39 С. 107-129
В работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе Б, в которой задержки базисных элементов по различным входам могут различаться. В рассматриваемой модели получены асимптотические оценки вида τБn±O(1), где τБ ― константа, зависящая только от базиса Б, для задержки мультиплексорной функции порядка n, то есть функции с n адресными и 2n информационными переменными ...
Добавлено: 2 декабря 2019 г.
Сысоева Л. Н., Вестник Московского университета. Серия 1: Математика. Механика 2017 № 2 С. 19-28
Рассматривается задача о реализации булевых функций инициальными булевыми ав- томатами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n ≥ 1. Получена точная оценка максимального числа булевых функций от n фиксированных переменных, реализуемых инициальным булевым ...
Добавлено: 28 февраля 2017 г.
Сысоева Л. Н., Интеллектуальные системы. Теория и приложения 2016 Т. 20 № 4 С. 98-103
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n ≥ 1. Найдены все множества максимальной мощности, состоящие из булевых функций, которые могут быть реализованы одним ...
Добавлено: 28 февраля 2017 г.
Ивченко Г. И., Медведев Ю. И., Математические вопросы криптографии 2012 Т. 3 № 3 С. 21-34
Предлагается общая вероятностная модель для булевых функций от n переменных, задаваемая произвольной вероятностной мерой на множестве всех таких функций. Выводится характеристическая функция спектра Уолша случайной функции и находятся точные и асимптотические (при n→∞) распределения некоторых его характеристик для случая
параметрической меры. ...
Добавлено: 19 ноября 2012 г.
Сысоева Л. Н., Moscow University Mathematics Bulletin 2019 Vol. 74 No. 6 P. 241-245
Добавлено: 22 ноября 2020 г.
Федоров С. Н., Логачёв О. А., Сукаев А. А., Информатика и ее применения 2019 Т. 13 № 2 С. 37-46
Как известно, вычислительная задача решения систем нелинейных уравнений над полем из двух элементов является NP-трудной. Этим обстоятельством обуславливается стремление исследователей разрабатывать алгоритмы ее решения, минимизирующие необходимые вычислительные ресурсы для тех или иных классов систем уравнений.
В статье предлагается метод решения систем квадратичных булевых уравнений, использующий представление функций их аффинными нормальными формами, то есть, в некотором смысле, аппроксимацию ...
Добавлено: 16 июня 2021 г.
Сысоева Л. Н., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. Гл. 3. С. 184-187.
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n > 0. Построен пример инициального булева автомата с минимальным количеством константных состояний и n входами, реализующего максимальное возможное число булевых ...
Добавлено: 31 октября 2019 г.
Яшунский А. Д., Lobachevskii Journal of Mathematics 2019 Vol. 40 No. 9 P. 1423-1432
We consider Bernoulli distribution algebras, i.e. sets of distributions that are closed under transformations achieved by substituting independent random variables for arguments of Boolean functions from a given system. We establish that, unless the transforming set contains only essentially unary functions, the set of algebra limit points is either empty, single-element or no less than ...
Добавлено: 9 сентября 2020 г.
Федоров С. Н., Логачёв О. А., Ященко В. В., Дискретная математика 2021 Т. 33 № 2 С. 66-85
Рассматривается действие на множестве булевых функций расширения G полной аффинной группы преобразований с помощью группы аффинных функций: действие заключается в преобразовании булевых функций невырожденными аффинными заменами переменных и сложением с аффинными булевыми функциями. Введены и исследованы параметры булевых функций, инвариантные относительно действия группы G: амплитуда (тесно связанная с нелинейностью), размерность функции и некоторые другие. Эти ...
Добавлено: 16 июня 2021 г.
Федоров С. Н., Логачёв О. А., Ященко В. В., Discrete Mathematics and Applications 2019 Vol. 29 No. 2 P. 89-101
Добавлено: 16 июня 2021 г.
Федоров С. Н., Логачёв О. А., Сукаев А. А., Информатика и ее применения 2019 Т. 13 № 1 С. 67-74
Аффинная нормальная форма позволяет рассматривать произвольную булеву функцию на определенных плоскостях (так называемых локальных аффинностях) как аффинную. Данное представление — по сути, аффинная аппроксимация — булевых функций может помочь в решении систем нелинейных уравнений над полем из двух элементов. Задача решения таких систем (специального вида), среди прочего, используется в ряде методов синтеза и анализа средств ...
Добавлено: 4 сентября 2019 г.
Сысоева Л. Н., Ученые записки Казанского университета. Серия: Физико-математические науки 2014 Т. 156 № 3 С. 116-122
Рассматривается задача о реализации булевых функций обобщенными альфа-формулами. Вводится понятие обобщенной альфа-формулы. Определяется понятие универсального множества обобщенных альфа-формул для заданного множества булевых функций. Вводится понятие двойственных обобщенных альфа-формул, формулируется принцип двойственности. Показывается, что для каждого n ≥ 2 для множеств всех булевых функций от n переменных, сохраняющих константы 0 или 1, существуют универсальные множества. ...
Добавлено: 11 ноября 2017 г.
Подольский В. В., Logical Methods in Computer Science 2013 Vol. 9 No. 2 P. 1-17
An integer polynomial p of n variables is called a threshold gate for a Boolean function f of n variables if for all x∈{0,1}n f(x)=1 if and only if p(x) > 0. The weight of a threshold gate is the sum of its absolute values. In this paper we study how large a weight might be needed if ...
Добавлено: 20 октября 2014 г.
Федоров С. Н., Логачёв О. А., Ященко В. В., Дискретная математика 2018 Т. 30 № 4 С. 29-40
В работе вводится новое отношение эквивалентности на множестве булевых функций: ∆-эквивалентными объявляются функции, имеющие одну и ту же функцию автокорреляции. Оказывается, что данная классификация хорошо согласуется с криптографическими свойствами булевых функций: многие из изучаемых в криптографии характеристик таких функций сохраняются внутри класса ∆-эквивалентности. Например, все бент-функции (от фиксированного числа переменных) составляют один класс. ...
Добавлено: 4 сентября 2019 г.
Сысоева Л. Н., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 229-232.
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n>1. Получены точные оценки на максимальное число булевых функций от n фиксированных переменных, реализуемых инициальным булевым автоматом ...
Добавлено: 1 марта 2017 г.