利用者:Eshiho/sandbox

piling-up lemma とは、暗号解読方法の一つで、主に線形解読法においてブロック暗号の線形近似式を構築する際に利用される。 これは松井充(1993)により線形解読法の解析手法の一つとして導入された。

理論

piling-up lemmaは以下の等式が成立する確率を決定することを可能にする:

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

ここで、Xは二値変数(0または1のみを保持する)である。

P(A)を「Aが真となる確率」と定義する。もし1ならAは確実に起こり、0であればAは起きない。 まず、2変数の場合についてpiling-up lemmaを考える。この時、$P(X_{1}=0)=p_{1}$かつ$P(X_{2}=0)=p_{2}$とする。

ここで、以下の式について考える。

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

この式はXORの性質から

$P(X_{1}=X_{2})$

に等しい。

X₁ = X₂ = 0 と X₁ = X₂ = 1はそれぞれ相互に排他的である。よって、以下が言える。

$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)$

ここで、「それぞれの二値変数は独立である。」と仮定する。 Now, we must make the central assumption of the piling-up lemma: the binary variables we are dealing with are independent; すると、ある1つの確率は他のいずれの確率にも影響を及ぼさない。よって、我々はこの確率関数を以下のように拡張することができる。 that is, the state of one has no effect on the state of any of the others. Thus we can expand the probability function as follows:

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

Now we express the probabilities p₁ and p₂ as ½ + ε₁ and ½ + ε₂, where the ε's are the probability biases — the amount the probability deviates from ½.

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

Thus the probability bias ε_1,2 for the XOR sum above is 2ε₁ε₂.

This formula can be extended to more X 's as follows:

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

Note that if any of the ε's is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased — equal to ½.

A related slightly different definition of the bias is $\epsilon _{i}=P(X_{i}=1)-P(X_{i}=0),$ in fact minus two times the previous value. The advantage is that now with

$\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)$

we have

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

adding random variables amounts to multiplying their (2nd definition) biases.

Practice

In practice, the Xs are approximations to the S-boxes (substitution components) of block ciphers. Typically, X values are inputs to the S-box and Y values are the corresponding outputs. By simply looking at the S-boxes, the cryptanalyst can tell what the probability biases are. The trick is to find combinations of input and output values that have probabilities of zero or one. The closer the approximation is to zero or one, the more helpful the approximation is in linear cryptanalysis.

However, in practice, the binary variables are not independent, as is assumed in the derivation of the piling-up lemma. This consideration has to be kept in mind when applying the lemma; it is not an automatic cryptanalysis formula.

References

• Matsui, Mitsuru (1994). “Linear Cryptanalysis Method for DES Cipher”. Advances in Cryptology—EUROCRYPT ’93. Springer. pp. 386–397. doi:10.1007/3-540-48285-7_33