相関免疫

数学において、ブール関数の相関無依存度（correlation-immunity）とは、その出力が入力の一部とどの程度無相関であるかを示す尺度です。具体的には、ブール関数がm次の相関無依存度を持つとは、関数内のm個以下の変数のすべての部分集合が関数の値と統計的に独立であることを意味します。 ${\displaystyle x_{1},x_{2},\ldots,x_{n}}$ ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$

意味

関数が- 次の相関なしであるとは、任意の独立した2 値ランダム変数に対して、そのランダム変数がを持つ任意のランダムベクトルから独立している場合を指します。 ${\displaystyle f:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle X_{0}\ldots X_{n-1}}$ ${\displaystyle Z=f(X_{0},\ldots ,X_{n-1})}$ ${\displaystyle (X_{i_{1}}\ldots X_{i_{k}})}$ ${\displaystyle 0\leq i_{1}<\ldots <i_{k}<n}$

暗号技術における成果

ストリーム暗号で線形フィードバックシフトレジスタの結合関数として使用される場合、低次の相関耐性を持つブール関数は、高次の相関耐性を持つ関数よりも相関攻撃を受けやすくなります。

ジーゲンターラーは、 n変数の代数次数dのブール関数の相関耐性mがm  +  d  ≤  nを満たすことを示した。これは、与えられた入力変数の集合において、高い代数次数が最大可能な相関耐性を制限することを意味する。さらに、関数が釣り合う場合、m  +  d  ≤  n  − 1となる。 ^{[ 1 ]}

参考文献

1. T. Siegenthaler (1984年9月). 「暗号アプリケーションにおける非線形結合関数の相関耐性」. IEEE Transactions on Information Theory . 30 (5): 776– 780. doi : 10.1109/TIT.1984.1056949 .

さらに読む

1. Cusick, Thomas W. & Stanica, Pantelimon (2009). 「暗号ブール関数とその応用」. Academic Press. ISBN 9780123748904。