О НЕКОТОРЫХ СВОЙСТВАХ КОЭФФИЦИЕНТОВ ЧИСЛОВОЙ НОРМАЛЬНОЙ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

Аннотация

Булевы функции играют значительную роль в криптографических приложениях, являясь основными примитивами многих криптосистем, в особенности потоковых шифров. Булевы функции имеют приложение также в теории кодирования. Рассмотрению свойств булевых функций, влияющих на стойкость криптосистем, посвящено огромное количество работ, и новые способы исследования булевых функций могут расширить представления об их свойствах. Существуют различные способы задания булевых функций: через таблицу истинности, с помощью алгебраической нормальной формы (в русскоязычной литературе часто используется понятие полиномов Жегалкина), с помощью спектральных характеристик функции, с помощью понятия следа. Каждый из этих способов имеет свои преимущества и недостатки для исследования различных свойств булевых функций, в том числе криптографических (см., например, [1]). Также в [1] представлен еще один способ задания любых комплексозначных функций над n -мерном линейным пространством (в том числе булевых) — так называемая числовая нормальная форма функции. Этот способ описания булевых функций используется реже (чем алгебраическая нормальная форма, спектральное и др.), хотя потенциально несет в себе не меньше информации о них.