誕生日のパラドックス

「1年は365日とし、部屋に$ N人の人がいるとき、その中に同じ誕生日の人の組が存在する確率が半分を超える最小の$ Nは？」

答えは23人で、この時の確率は約50.7%

ある特定の誕生日の人と同じ誕生日の人を探すのは困難（一方向性と第2原像計算困難性に対応）でも、同じ誕生日を持つ2人を探す（衝突困難性に対応）のは比較的簡単であるというパラドックス

パラドックスを一般化し、以下のように考える

1年を$ Y日とし、部屋に$ N人の人がいるとき、その中に同じ誕生日の人の組が存在する確率が半分を超える最小の$ Nは？

$ Yが十分大きい時、$ N \approx \sqrt Y = Y^{\frac{1}{2}}となる

$ nビットハッシュ関数の$ nビットのハッシュ値の総数は$ 2^n個であるため（上式のYに対応）、これが十分大きい時、衝突困難性は$ N=n^{\frac{1}{2}}回の試行でおよそ$ \frac{1}{2}の確率で破られることになる

従ってビットセキュリティの定義から、強衝突耐性のビットセキュリティは$ \frac{1}{2}になる

対し、弱衝突耐性及び現像計算困難性は$ 2^n回の試行で(高い確率で)破られるため、それらのビットセキュリティは$ nになる

仮に$ n=256とすると、

強衝突耐性を破るための計算回数は、$ \approx 10^{77}

一方向性および第2原像計算困難性を破るための計算回数は$ \approx 10^{154}

強衝突耐性を破るための計算量は他2つと比べてずっと小さい