Сбалансированная булева функция

В математике и информатике сбалансированная булева функция — это булева функция , выходные данные которой дают как 0 , так и 1 с на входном наборе . Это означает, что для равномерно случайной входной строки битов вероятность получить 1 равна 1/2. ^{[ 1 ]}

Примеры

Примерами сбалансированных логических функций являются функция большинства , ^{[ 1 ]} «функция диктатуры», которая копирует первый бит входных данных на выходные данные, ^{[ 1 ]} и функция проверки четности , которая создает исключительный или из входных битов. ^{[ 2 ]}

Если $f$ представляет собой изогнутую функцию на $n$ биты и $\alpha$ любой ненулевой вектор $n$ бит, затем функция, которая отображает $x$ к $f(x)\oplus f(x\oplus \alpha )$ является сбалансированным. Бент-функции — это именно те функции, для которых это верно, для всех ненулевых вариантов выбора. $\alpha$ . ^{[ 3 ]}

Функцию диктатуры можно оценить после проверки только одного бита входных данных, но этот бит всегда необходимо проверять. Бенджамини, Шрамм и Уилсон описывают более сложный пример, основанный на теории перколяции со свойством, что рандомизированный алгоритм Лас-Вегаса может точно вычислить функцию, гарантируя, что вероятность чтения любого конкретного входного бита мала, примерно обратно пропорциональна квадратному корню. от количества битов. ^{[ 1 ]}

Приложение

Сбалансированные логические функции используются в криптографии , где сбалансированность является одним из «наиболее важных критериев криптостойких логических функций». ^{[ 3 ]} Если функция не сбалансирована, она будет иметь статистическую погрешность , что делает ее объектом криптоанализа, такого как корреляционная атака .

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Бенджамини, Итай ; Шрамм, Одед ; Уилсон, Дэвид Брюс (2005), «Сбалансированные логические функции, которые можно оценить так, что каждый входной бит вряд ли будет прочитан», в Габоу, Гарольд Н.; Феджин, Рональд (ред.), Труды 37-го ежегодного симпозиума ACM по теории вычислений, Балтимор, Мэриленд, США, 22–24 мая 2005 г. , Ассоциация вычислительной техники, стр. 244–250, arXiv : math.PR/ 0410282 , дои : 10.1145/1060590.1060627
^ Чакрабарти, К.; Хейс, Дж. П. (1998), «Сбалансированные логические функции», IEE Proceedings – Computers and Digital Techniques , 145 (1): 52, doi : 10.1049/ip-cdt:19981769
^ Перейти обратно: ^а ^б Себерри, Дженнифер ; Чжан, Сянь-Мо; Чжэн, Юлян (1993), «Нелинейно сбалансированные логические функции и характеристики их распространения», в Стинсон, Дуглас Р. (редактор), « Достижения в криптологии - CRYPTO '93», 13-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 22–26 августа 1993 г., Труды , Конспекты лекций по информатике, том. 773, Springer, стр. 49–60, номер документа : 10.1007/3-540-48329-2_5.

[bsw-1] Перейти обратно: ^а ^б ^с ^д Бенджамини, Итай ; Шрамм, Одед ; Уилсон, Дэвид Брюс (2005), «Сбалансированные логические функции, которые можно оценить так, что каждый входной бит вряд ли будет прочитан», в Габоу, Гарольд Н.; Феджин, Рональд (ред.), Труды 37-го ежегодного симпозиума ACM по теории вычислений, Балтимор, Мэриленд, США, 22–24 мая 2005 г. , Ассоциация вычислительной техники, стр. 244–250, arXiv : math.PR/ 0410282 , дои : 10.1145/1060590.1060627

[ch-2] Чакрабарти, К.; Хейс, Дж. П. (1998), «Сбалансированные логические функции», IEE Proceedings – Computers and Digital Techniques , 145 (1): 52, doi : 10.1049/ip-cdt:19981769

[szz-3] Перейти обратно: ^а ^б Себерри, Дженнифер ; Чжан, Сянь-Мо; Чжэн, Юлян (1993), «Нелинейно сбалансированные логические функции и характеристики их распространения», в Стинсон, Дуглас Р. (редактор), « Достижения в криптологии - CRYPTO '93», 13-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 22–26 августа 1993 г., Труды , Конспекты лекций по информатике, том. 773, Springer, стр. 49–60, номер документа : 10.1007/3-540-48329-2_5.

[ 1 ]

[ 2 ]

[ 3 ]