Probability

Discrete Probability

ビット数 n の有限集合 U を以下のように表記する。 n = 8 の 8bit なら 00000000..11111111 すなわち 256 通りの要素を持つ。

有限集合 U における確率関数を P とした時、各要素の確率 P(x) の総和を 1 となるように定義する。

Uniform Distribution

すべての要素が同じ確率である場合 Uniform distribution (一様分布)と呼ぶ。すべての P(x) は同じ値で 1/|U| となる。|U|U の要素数を表す。

Point Distribution

一つの要素だけが真となる場合、 Point distribution (点分布)と呼ぶ。当然ながら一つの要素のみ 1 で、それ以外は 0 になる。

Events

有限集合のうち、特定条件を満たす補集合を Event (事象)と呼ぶ。その補集合を A とした時、その確率を Pr[A] と表す。補集合がすべてを含めば Pr[U] = 1 である。

8bit の集合 U で、下位 2bit が 11 となる補集合を A とした時 Uniform distribution であれば、256 通りのうち、条件を満たすパターン ??????11 は 64 通りなので 64/256 = 1/4 すなわち Pr[A] = 1/4 となる。

二つの事象の確率 Pr[A]Pr[B] の積は、AND 集合の確率 Pr[A ∩ B] に等しい。

二つの事象の確率 Pr[A]Pr[B] の和は、OR 集合の確率 Pr[A ∪ B] 以上となる。条件の重複がなければ等しい。

Random Variables

関数 X の期待値を v とした時、その確率を Pr[X=v] と表す。下位 1bit を返す関数を X としたとき、Pr[X=v]Uniform distribution となる。

Uniform Random Variables

有限集合 U からランダムに取り出す値を r とした時、各要素 a となる確率 Pr[r=a] がすべて 1/|U| となるものを Uniform random variable と呼ぶ。r は引数をそのまま返す Identity function 恒等関数である。

Birthday Pradox

誕生日が同じ人がいる確率が 50% となるには何人いればよいか?という問題がある。正解は 23 人で直感とは異なることから Birthday paradox と呼ばれる。

n 人の中で同じ誕生日の人がいない確率で考える。2 人だけの時に一致しない確率は 364/365 である。n が増えるたびに (365-n+1)/365 と下がっていき、試行回数分の積で求められる。n = 230.492... となり 50% を超える。

2 人だけの時に一致しない確率は 364/365 である。自分と一致する確率で考えると、23 人の時は0.006 とずっと小さいが、23 人分の組み合わせは 253 通りある。同じように考えてみれば、同じく 50% に近づくことが分かる。

有限集合 U からランダムに選択して、衝突する確率が 50% を超えるまでの試行数は以下で求められる。

128bit のハッシュ関数に対し、元メッセージを見つけるまで(原像攻撃)の試行回数の期待値は 2^128 に比例するが、同じハッシュとなる二つのメッセージを見つけるまで(衝突攻撃)の試行回数は、大きく下がり 2^64 に比例する。