積み重ね補題

Principle used in linear cryptanalysis

暗号解読において、積み上げ補題（piling-up lemma）は、線形暗号解読においてブロック暗号の作用に対する線形近似を構築するために用いられる原理である。これは、線形暗号解読の解析ツールとして松井充（1993）によって導入された。 ^[1]この補題は、独立2値確率変数の線形ブール関数（XOR節）のバイアス（期待値の1/2からの偏差）が、入力バイアスの積と関係していることを示している。^[2]

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

または

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

はバイアス（ゼロに向かう^[3]）であり、不均衡は[ 4 ^{] [5]である。} ${\displaystyle \epsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}$ ${\displaystyle I\in [-1,1]}$

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

${\displaystyle I(X)=P(X=0)-P(X=1)=2\epsilon (X)}$。

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

解釈

この補題は、独立した 2 値変数を 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}$

期待値の定式化

確率変数が の値を取る場合、積み上げ補題はより自然に表現できます。変数（0を1に、1を-1にマッピングする）を導入すると、XOR演算は積に変換されます。 ${\displaystyle \{-1,1\}}$ ${\displaystyle \chi _{i}=1-2X_{i}=(-1)^{X_{i}}}$

${\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}$

が成り立ちます。ここで、Xはバイナリ変数(つまり、ビット: 0 または 1)です。

P (A) を「A が真である確率」とします。もし P (A) が 1 に等しい場合、Aは確実に発生し、もし P (A) が 0 に等しい場合、A は発生しません。まず、2 つの 2 値変数、つまり と の piling-up 補題を考えます。 ${\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})}$

X ₁ = X ₂ = 0 とX ₁ = X ₂ = 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)}$

さて、積み上げ補題の中心的な仮定を立てなければなりません。すなわち、ここで扱う2値変数は独立である、つまり、ある変数の状態は他の変数の状態に影響を与えない、ということです。したがって、確率関数は次のように展開できます。

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =P(X_{1}=0)P(X_{2}=0)+P(X_{1}=1)P(X_{2}=1)}$
	${\displaystyle =p_{1}p_{2}+(1-p_{1})(1-p_{2})}$
	${\displaystyle =p_{1}p_{2}+(1-p_{1}-p_{2}+p_{1}p_{2})}$
	${\displaystyle =2p_{1}p_{2}-p_{1}-p_{2}+1}$

ここで確率p ₁とp ₂を次のように表す。1/2⁠ + ε ₁および⁠1/2⁠ + ε ₂、ここでεは確率バイアス、つまり確率が⁠から逸脱する量である。1/2⁠。

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =2(1/2+\epsilon _{1})(1/2+\epsilon _{2})-(1/2+\epsilon _{1})-(1/2+\epsilon _{2})+1}$
	${\displaystyle =1/2+\epsilon _{1}+\epsilon _{2}+2\epsilon _{1}\epsilon _{2}-1/2-\epsilon _{1}-1/2-\epsilon _{2}+1}$
	${\displaystyle =1/2+2\epsilon _{1}\epsilon _{2}}$

したがって、上記のXOR合計の確率バイアス ε _{1,2は 2ε 1} ε ₂です。

この式は、次のようにさらに多くのXに拡張できます。

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

εのいずれかがゼロの場合、つまり2値変数の1つが偏りがない場合、確率関数全体も偏りがなく、次の式に等しいことに注意してください。1/2⁠。

バイアスの関連する少し異なる定義は、 実際には以前の値の2倍のマイナスです。利点は、 ${\displaystyle \epsilon _{i}=P(X_{i}=1)-P(X_{i}=0),}$

${\displaystyle \varepsilon _{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 _{total}=(-1)^{n+1}\prod _{i=1}^{n}\varepsilon _{i},}$

ランダム変数を追加することは、それらの（2 番目の定義）バイアスを乗算することになります。

練習する

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

しかし、実際には、積み上げ補題の導出で仮定されているように、2値変数は独立ではありません。この補題を適用する際には、この点を念頭に置く必要があります。この補題は、自動的に暗号解読を行う公式ではありません。

参照

• 独立した実変数の和の分散

参考文献

1. 松井充 (1994). 「DES暗号の線形解読法」.暗号学の進歩 – EUROCRYPT '93 . コンピュータサイエンス講義ノート. 第765巻. pp.  386– 397. doi :10.1007/3-540-48285-7_33. ISBN 978-3-540-57600-6. S2CID  533517。
2. Li, Qin; Boztaş, S. (2007年12月). 「拡張線形暗号解析と拡張積分補題」(PDF) . ISC Turkey . S2CID  5508314. 2017年1月17日時点のオリジナル(PDF)からアーカイブ。
3. バイアス（および不均衡）は絶対値として取ることもできます。反転した符号のバイアス（1 に向かうバイアス）を使用する場合、補題では右側に追加の (-1)^(n+1) 符号係数が必要になります。
4. ハーペス, カルロ; クレイマー, ゲルハルト G.; マッシー, ジェームズ L. (1995). 「線形暗号解読の一般化と松井の積み上げ補題の適用可能性」.暗号学の進歩 – EUROCRYPT '95 . コンピュータサイエンス講義ノート. 第921巻. pp.  24– 38. doi :10.1007/3-540-49264-X_3. ISBN 978-3-540-59409-3。
5. Kukorelly, Zsolt (1999). 「積み上げ補題と従属確率変数」.暗号と符号化. コンピュータサイエンス講義ノート. 第1746巻. pp.  186– 190. doi :10.1007/3-540-46665-7_22. ISBN 978-3-540-66887-9。
6. Nyberg, Kaisa (2008年2月26日). 「線形暗号解析（暗号学講義）」(PDF) .ヘルシンキ工科大学、理論計算機科学研究所.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Piling-up_lemma&oldid=1230036792"