弱衝突耐性・強衝突耐性

違いがよくわからないぞ

色々しらべて、よりイメージしやすく分かりやすい説明を考えました。
wikiに載っている説明をどう解釈するのか

以下wiki引用
弱衝突耐性(第二現像計算困難性)：
入力m1が与えられたとき、hash(m1)=hash(m2)となるような別の入力m2を求めることが困難でなくてはならない
強衝突耐性：
hash(m1)=hash(m2)となる2つの異なるメッセージm1とm2を探し出すことが困難でなくてはならない

自分はこの説明で何となくしかわかりませんでしたが、理解が進み、こんな解釈をしました。
・弱衝突耐性
要は1つのハッシュ値が固定で、それと一致するハッシュ値を持つメッセージm2を見つけ出せるか
・強衝突耐性
とりあえず一致するハッシュ値はなんでもよいけど、同じハッシュ値をもつメッセージのペアm1,m2を見つけ出せるか

一致させる必要のあるハッシュ値が特定のハッシュ値なのか
ハッシュ値自体は何でもよいけど、とにかく2つのハッシュ値を一致させる必要があるのか
つまり、1つの固定ハッシュに注目するか、2つの不定ハッシュに注目するのか、が違いになると思います。

理想的なハッシュ関数

理想的なハッシュ関数はこの2つの性質を備えている必要があります。
「弱衝突耐性」というのは一致するハッシュ値にあたる(=衝突)事象の起こり難さ(=耐性)として楽な条件(=弱)ということだそうです。(←修正：コメントありがとうございます。) したがって弱衝突耐性の方が一致するハッシュ値に当たりづらい=破るのはより困難ということになります。強衝突耐性に関しても同様に考えられます。「弱」という漢字が使われており、誤解しやすいかもしれないですが、何に対して弱いのかきちんと理解しておくことが大切ですね。

特定のハッシュ値に一致するペアを探す(弱衝突耐性)よりも、あるハッシュ値に一致するペアを探す(強衝突耐性)方が簡単であることの具体例として以下を考えました。
ex. 2セット(A,B)のトランプ104枚から赤のダイヤのクイーンに一致するペアを探す(→ペアとしては1枚しか見つからない)よりは、数字絵柄は何でもよいけどよりあえず一致するペアを探してくれと言われた方がすぐ見つかります(→ペアとしては1～Kの13ペア見つかる)。そういうことです。

いままでの説明で弱衝突耐性と強衝突耐性が理解できていれば、弱衝突耐性は強衝突耐性を包含していることに気づくはずです。したがって、もし弱衝突耐性が破られたとしたら、その時点ですでに強衝突耐性は破られたとみなせることも納得できます。

誕生日のパラドックス

「何人集まれば、その中に同じ誕生日の人が2人以上いる確率が50%を超えるか？」という問題

答えとしては23人で50%を超えます。
366人集まれば、確実に1人は被るので100%になることはわかりますが、その半数以下でも99.9%以上の割合で同じ誕生日の人が現れます。感覚的に「・・・あれ？」となる人が多いのでイメージとの乖離でパラドックスと呼ばれています。(論理的には全然パラドックスじゃありません。)
実際に考える際は、自分以外のうちの人同士で誕生日が一致する可能性を考慮する必要があり、余事象で求めます。感覚的にはそのグループの中に自分と同じ誕生日の人がいる確率だけ計算すればよい、と考える人が多いのでよく取り上げられる題材です。
[計算式]
P(n) = 1-(364/365)^n
n=253のときにはじめて0.5 <= Pとなります。