積み重ね補題

暗号解読において、パイリングアップ補題は、ブロック暗号の動作の線形近似を構築するために線形暗号解読で使用される原理です。これは、線形暗号解読の分析ツールとして、松井満（1993）によって導入されました。 ^{[ 1 ]}この補題は、独立した二値確率変数の線形ブール関数（XOR節）のバイアス（期待値の1/2からの偏差）が、入力バイアスの積と関連していることを示しています。^{[ 2 ]}

${\displaystyle \varepsilon (X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=2^{n-1}\prod _{i=1}^{n}\varepsilon (X_{i})}$

または

${\displaystyle I(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=\prod _{i=1}^{n}I(X_{i})}$

どこ${\displaystyle \varepsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}$はバイアス（ゼロ方向^{[ 3 ]}）であり、${\displaystyle I\in [-1,1]}$不均衡：^{[ 4 ] [ 5 ]}​

$\displaystyle \varepsilon (X)=P(X=0)-{\frac {1}{2}}}$

${\displaystyle I(X)=P(X=0)-P(X=1)=2\varepsilon (X).}$

逆に、補題が成り立たない場合、入力変数は独立ではない。^{[ 6 ]}

この補題は、独立した二値変数をXOR演算すると、常にバイアスが減少する（少なくとも増加しない）ことを示唆している。さらに、出力がバイアスを持たないのは、少なくとも1つのバイアスのない入力変数が存在する場合に限る。

2 つの変数については、${\displaystyle I(X\oplus Y)}$は相関尺度である${\displaystyle X}$そして​${\displaystyle Y}$⁠、等しい⁠${\displaystyle P(X=Y)-P(X\neq Y)}$⁠ ;${\displaystyle I(X)}$相関関係として解釈できる${\displaystyle X}$と共に​${\displaystyle 0}$⁠ .

確率変数が の値をとる場合、蓄積補題はより自然に表現できる。${\displaystyle \{-1,1\}}$変数を導入すると${\displaystyle \chi _{i}=1-2X_{i}=(-1)^{X_{i}}}$（マッピング）${\displaystyle 0}$⁠から⁠${\displaystyle 1}$そして​​${\displaystyle 1}$⁠から⁠${\displaystyle -1}$⁠ ) そして、検査により、XOR演算は積に変換されることがわかります。

${\displaystyle \chi _{1}\chi _{2}\cdots \chi _{n}=1-2(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=(-1)^{X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}}}$

そして期待値は不均衡であるため、${\displaystyle E(\chi _{i})=I(X_{i})}$⁠、補題は次のとおりである。

${\displaystyle E\left(\prod _{i=1}^{n}\chi _{i}\right)=\prod _{i=1}^{n}E(\chi _{i}),}$

これは、独立変数の期待値の既知の性質です。

従属変数の場合、上記の定式化には（正または負の）共分散項が加わるため、この補題は成り立ちません。実際、2つのベルヌーイ変数は、無相関（つまり共分散がゼロである；無相関性を参照）である場合に限り独立であるため、積み重ね補題の逆が成り立ちます。つまり、この補題が成り立たない場合、変数は独立（無相関）ではありません。

積み重ね補題により、暗号解読者は次の等式が成り立つ確率を決定できます。

${\displaystyle X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0}$

保持する、そこで⁠${\displaystyle X}$はバイナリ変数（つまりビット：${\displaystyle 0}$または​​${\displaystyle 1}$⁠ )

させよう${\displaystyle P(A)}$⁠ は「～の確率」を表す。${\displaystyle A}$⁠は真です。1に等しい場合、 ⁠${\displaystyle A}$は必ず起こり、それがゼロに等しい場合は、${\displaystyle A}$は起こり得ない。まず、2 つのバイナリ変数に対するパイルアップ補題を考える。${\displaystyle P(X_{1}=0)=p_{1}}$そして​${\displaystyle P(X_{2}=0)=p_{2}}$⁠ .

さて、ここで以下の点を検討してみましょう。

${\displaystyle P(X_{1}\oplus X_{2}=0).}$

XOR演算の特性により、これは以下と同等です。

${\displaystyle P(X_{1}=X_{2}).}$

⁠${\displaystyle X_{1}=X_{2}=0}$そして​​${\displaystyle X_{1}=X_{2}=1}$これらは互いに排他的な事象なので、次のように言うことができます。

${\displaystyle P(X_{1}=X_{2})=P(X_{1}=X_{2}=0)+P(X_{1}=X_{2}=1)=P(X_{1}=0,X_{2}=0)+P(X_{1}=1,X_{2}=1).}$

ここで、パイリングアップ補題の中心的な仮定、すなわち、扱う二値変数は独立である、つまり、ある変数の状態が他の変数の状態に影響を与えない、という仮定を置く必要があります。したがって、確率関数を次のように展開できます。

確率を次のように表現します${\displaystyle p_{1}}$そして​​${\displaystyle p_{2}}$⁠として⁠${\displaystyle {\tfrac {1}{2}}+\varepsilon _{1}}$そして​​${\displaystyle {\tfrac {1}{2}}+\varepsilon _{2}}$⁠、そこで⁠${\displaystyle \varepsilon }$⁠は確率バイアスであり、確率が からどれだけずれているかを示します。${\displaystyle {\tfrac {1}{2}}}$⁠ .

したがって、確率バイアス${\displaystyle \varepsilon _{1,2}}$上記のXOR和は${\displaystyle 2\varepsilon _{1}\varepsilon _{2}}$⁠ .

この公式はさらに多くのものに拡張できます${\displaystyle X}$以下のように：

${\displaystyle P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\varepsilon _{i}}$

いずれかが${\displaystyle \varepsilon }$sはゼロです。つまり、バイナリ変数の 1 つが不偏であるため、確率関数全体が不偏になります。${\displaystyle {\tfrac {1}{2}}}$⁠ .

関連する、やや異なるバイアスの定義は、${\displaystyle \varepsilon _{i}=P(X_{i}=1)-P(X_{i}=0)}$⁠、実際には前の値の2倍を引いた値です。利点は、今なら

${\displaystyle \varepsilon _{\text{total}}=P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)}$

我々は持っています

${\displaystyle \varepsilon _{\text{total}}=(-1)^{n+1}\prod _{i=1}^{n}\varepsilon _{i},}$

ランダム変数を加えるということは、それらの（2番目の定義による）バイアスを掛け合わせることに等しい。

実際には、${\displaystyle X}$⁠はブロック暗号のSボックス（置換要素）の近似値です。通常、${\displaystyle X}$⁠値は S ボックスへの入力であり、${\displaystyle Y}$Sボックスの値は対応する出力です。暗号解読者はSボックスを見るだけで、確率バイアスが何であるかを判断できます。重要なのは、確率がゼロまたは1になる入力値と出力値の組み合わせを見つけることです。近似値がゼロまたは1に近いほど、線形暗号解読においてその近似値はより有用になります。

しかし実際には、二値変数は、積み重ね補題の導出で仮定されているように独立ではありません。この点を補題を適用する際には留意する必要があります。これは自動的な暗号解読式ではありません。

• 分散 § 特性– 独立な実変数の和の分散