[解決済み】弱い抵抗と強い抵抗の違いとは？

質問内容

強衝突抵抗と弱衝突抵抗の文章をいくつか読みましたが、違いが分かりませんでした。ただ、耐衝突性が弱いハッシュ関数では衝突の確率が低く、耐衝突性が強いハッシュ関数では衝突の確率が高いということだけは理解できた。何が本当のことなのか、これらのパラメーターの意味は何なのか、理解できませんでした。どなたか教えてください。

どのように解決するのですか？

また、弱衝突抵抗特性は、以下のように呼ばれることもあります。 第二次プリ画像耐性 :

任意の x が与えられたとき、h(x) = h(x') となるような x' は x' != x として存在しない。

一方、強い耐衝突性は次のように定義される。

h(x) = h(x') となるような、x != x'を持つxとx'は存在しない。

両者の定義の明らかな違いは、弱い耐衝突性では、特定のxの選択に縛られることを想定しているのに対し、強い耐衝突性の定義では、xとx'を自由に選択することができる点である。それでも、これは非常に似ているように思われるので、2つの例を見てみましょう。

弱い耐衝突性

弱い衝突耐性にしか興味がない場合の良い例として、単純なパスワードの保存方式がある。ユーザが入力したパスワードのハッシュをデータベースに保存するとする。ユーザーが入力したパスワードのハッシュが、以前に保存した値と等しい場合に認証が成功する（これは本質的に安全でない方式だが、しばらくは我慢してほしい）。さて、この場合、与えられたxは、以前に提供された（未知の）オリジナルのパスワードである。もし攻撃者がquot;second preimage"問題を効率的に解くことができれば、元のxと同じハッシュ値を持つx'を得ることができ、認証に成功することができる。このシナリオでは、任意の衝突を発生させる機能（すなわち、強衝突問題の解決）は一般に役に立たないことに注意してください。なぜなら、得られたxとx'が、すでにデータベースに格納されている実際のパスワードと似ている可能性はあまり高くないからです。

強い耐衝突性

例えば、データベースに保存された任意のデータを一意なIDで検索するようなアプリケーションです。元のデータに対してクエリーを発行する代わりに（データのサイズが無限になる可能性があるため、しばしば非常に遅くなる）、データのハッシュを計算することになります。ハッシュは非常にコンパクトで、サイズも限られているため、より効率的にクエリーを実行することができます。実のところ、このような場合、ハッシュ関数の（2つ目の）前画像耐性は全く気にならないことが多いのです。しかし、気になるのは、2つの異なるデータセットが同じ値にハッシュされるのを絶対に避けたいということです。これは、本質的に衝突です。これは本質的に衝突です。特に衝突を気にする必要はありませんが、この特性は普遍的に保持される必要があります。 任意の 2つのデータセットが同じ値にハッシュします（そのカラムに「一意制約」が定義されていると想像してください）。このようなアプリケーションではセキュリティが問題にならないことが多いので、非暗号化ハッシュを使うことが多いのですが、その理由のほとんどはパフォーマンスが良いことです。

両者の関係

直感的に、またその名前からもわかるように、強い耐衝突性は弱い耐衝突性よりも提供するのが難しいものだと思われます。幸いなことに、この直感はRandom Oracle Modelのもとで正しいことが証明される。もし、quot;second preimage"を解く効率的な確率的多項式アルゴリズムがあれば、quot;collision"を解く効率的アルゴリズムも得られると仮定して、逆接によりこれを証明することができる。

ハッシュ関数hと以下の単純な確率的アルゴリズム[1]を考える。

2ndPreimageを、ハッシュ関数hの"second preimage"を解く別の確率的（e, Q）アルゴリズムとする。

Choose x uniformly at random
value = 2ndPreimage(h, x)
case value == failure -> return failure
case value == x' (!= x) -> return (x, x')

これも強衝突問題を解決する(e, Q)アルゴリズムであることは容易に理解できる。これは、"second preimage"を解くアルゴリズムがあれば、衝突が発生しやすいこのアルゴリズムも使えるということを意味しています。基礎となるハッシュ関数hについて何の仮定もしなかったので、今、安全に次のことが言えます。

強い耐衝突性は弱い耐衝突性を意味するが、その逆は必ずしも成立しない。

[1] e はアルゴリズムの成功確率で、0 <= e < 1。 Q はオラクルクエリー（アルゴリズムの評価）の最大数です。成功した場合、アルゴリズムは有効な解を返し、そうでない場合、失敗を示す値を返す。