誕生日のパラドックス

誕生日のパラドックス

誕生日のパラドックスとは、特定の人数が集まると、その中に同じ誕生日の人がいる確率が50%を超えるという、直感に反した現象を指します。興味深いことに、366人（閏年の場合367人）集めれば確実に同じ誕生日の人が見つかりますが、驚くべきことに、わずか23人の集団でもその確率は50%を超えるのです。

この現象は、論理的な矛盾に基づくものではなく、人々の直感とは異なる結果を導くため「パラドックス」と呼ばれています。このパラドックスは、Z.E. Schnabelによる「湖にいる魚の総数の推定」に関連しており、統計学の手法である標的再捕獲法（capture-recapture法）にも関連します。

誕生日問題

この確率を求める課題は「誕生日問題」として知られています。例えば、22人の中に自分と同じ誕生日の人がいる確率は驚くほど低いですが、これは「あなた以外の人」が同じ誕生日である場合も考慮しなければならないからです。

誕生日の一致の確率を求めるためには、まず全員の誕生日が異なる場合の確率を考えます。例えば、1人目が誕生日の日付を選んだ後、2人目が同じ日でない確率は364日から選ぶため364/365になります。同様に、3人目は363/365、4人目は362/365と続き、n人目は(365-n+1)/365になります。

これに基づき、全員の誕生日が異なる確率は次のように表されます。

$$
p_1(n) = rac{364}{365} imes rac{363}{365} imes rac{362}{365} imes ext{...} imes rac{365-n+1}{365} = rac{365!}{365^n(365-n)!}
$$

したがって、同じ誕生日の人が少なくとも2人いる確率は次式で計算できます。

$$
p_2(n) = 1 - rac{_{365}P_n}{365^n}
$$

特に、n=23のとき、p2の値は0.507となり、これは50%を超えています。

誕生日攻撃

誕生日のパラドックスの概念は暗号技術においても応用されており、特に「誕生日攻撃」として知られる手法に利用されます。これは、特定のハッシュ関数において、同じハッシュ値を持つ2つの異なるメッセージを見つけ出すための攻撃方法です。

例えば、Nビットのハッシュ関数において、メッセージを探すためには通常2^(N-1)回の試行が必要とされますが、誕生日攻撃を用いると試行回数は2^(N/2)と、はるかに少なくなります。これにより、暗号学的な設計においては、ハッシュ値のサイズを適切に選定する重要性を示しています。

CTRモードの乱数識別性

さらに、CTRモードで使用される擬似乱数生成器は、ブロック長Lが与えられたとき、2^(L/2)回の乱数出力後に真の乱数と識別できる確率が1/2になることが示されています。これに対して、同じ値に戻らない設計のため、CTRモードでは同じ値を持つブロックが存在することはありません。

このように、誕生日のパラドックスは確率論や統計学の面白い側面を示すだけでなく、暗号学における安全性を考える上でも重要な概念となっています。

もう一度検索