Материалы что дал Мухачев / Материалы что дал Мухачев / Білети_коротки_відповіді / Білети_відпові_БСДМ / Mg_Vidp39

39. Визначення рівноймовірної булевої функції. Визначення лінійної булевої функції. Доведення рівноймовірності лінійної булевої функції.

Широко відомою властивістю деяких булевих відображень , важливою для криптографічних застосувань, є рівноймовірність (збалансованість, урівноваженість).

Ця властивість полягає в тому, що всі елементи області значень мають прообрази однакової потужності, тобто для кожного .

Вектор значень рівноймовірної булевої функції, таким чином, містить однакове число нулів і одиниць. Дійсно, , тому прообрази нуля і одиниці містять по -вимірних векторів кожний. Але - це половина від розмірності вектора значень.

Властивістю рівноймовірності володіють, наприклад, відмінні від нуля лінійні функції виду , де - ненульовий вектор коефіцієнтів, . Дійсно, нехай і серед коефіціентів знаходяться хоча б одна одиниця.

Перепозначимо індекси змінних і коефіціентів таким чином, щоб коефіціент . Тоді .

Кількість всіх варіантів комбінацій бітів дорівнює . Тому рівняння має розв'язків і вектор значень функції містить однакове число нулів і одиниць. Таким чином, -рівноймовірна.