バランスの取れたブール関数

数学やコンピュータサイエンスにおいて、バランスの取れたブール関数とは、入力セットに対して出力で得られる0の数と1の数が等しいブール関数のことです。これは、一様ランダムなビット列の入力に対して、 1が得られる確率が1/2であることを意味します。^{[ 1 ]}

バランスのとれたブール関数の例としては、多数決関数^{[ 1 ]、}入力の最初のビットを出力にコピーする「独裁関数」^{[ 1 ]}、入力ビットの排他的論理和を生成するパリティチェック関数^{[ 2 ]などがある。}

もし${\displaystyle f}$は、​${\displaystyle n}$ビット、そして${\displaystyle \alpha }$は、${\displaystyle n}$ビット、次にマッピングする関数${\displaystyle x}$に${\displaystyle f(x)\oplus f(x\oplus \alpha )}$はバランスが取れている。 曲がった関数は、すべての非ゼロの選択に対してこれが真となる関数である。${\displaystyle \alpha }$[ ^{3 ]​}

独裁関数は入力の 1 ビットだけを調べれば評価できますが、そのビットは必ず調べなければなりません。ベンジャミニ、シュラム、ウィルソンは、パーコレーション理論に基づいたより複雑な例を説明しています。この例では、ランダム化されたラスベガス アルゴリズムが関数を正確に計算できる一方で、特定の入力ビットを読み取る確率が小さく、ビット数の平方根にほぼ反比例するという性質があります。^{[ 1 ]}

バランスの取れたブール関数は暗号学で使用され、バランスが取れていることは「暗号学的に強いブール関数の最も重要な基準」の 1 つです。^{[ 3 ]}関数がバランスが取れていない場合、統計的バイアスが 生じ、相関攻撃などの暗号解読の対象となります。