ユニバーサル一方向ハッシュ関数

暗号学において、ユニバーサル一方向ハッシュ関数( UOWHF、しばしば「ウーフ」と発音される) は、暗号学にとって特に重要なユニバーサルハッシュ関数の一種である。UOWHF は、衝突耐性ハッシュ関数(CRHF)の代替として提案されている。CRHF は、強い衝突耐性特性を持つ。つまり、ランダムに選択されたハッシュ関数パラメータが与えられた場合、ハッシュ関数の衝突を見つけるのは困難である。対照的に、UOWHF では、ハッシュ関数パラメータとは無関係に 1 つの原像が選択された衝突を見つけるのが困難であることが求められる。このプリミティブは、 Moni NaorとMoti Yungによって提案され、「ターゲット衝突耐性」ハッシュ関数としても知られている。これは、トラップドア関数のない一般的なデジタル署名スキームの構築に使用され、また、選択暗号文の安全な公開鍵暗号化スキーム内でも使用された。

UOWHF ファミリには、それぞれ使用される確率が同じである有限数のハッシュ関数が含まれています。

UOWHF のセキュリティ プロパティは次のとおりです。は 2 つのフェーズで動作するアルゴリズムです。 ${\displaystyle A}$

• 最初は、入力を受け取らず（またはセキュリティ パラメータのみを受け取り）、値を選択します。${\displaystyle A}$${\displaystyle x}$
• ハッシュ関数は、ファミリーからランダムに選択されます。 は を受け取り、となるように出力する必要があります。${\displaystyle H}$${\displaystyle A}$${\displaystyle H}$${\displaystyle y\neq x}$${\displaystyle H(x)=H(y)}$

すると、すべての多項式時間において、成功する確率は無視できるほど小さくなります。 ${\displaystyle A}$${\displaystyle A}$

UOWHF は CRHF よりも計算コストが低いと考えられており、ハッシュ関数の選択が事前ではなく実行のどこかの段階で行われる方式で効率化の目的でよく使用されます。たとえば、Cramer-Shoup 暗号システムでは、暗号文の有効性チェックの一部として UOWHF を使用します。

• 原像攻撃

• Goldreich, Oded (2004)。暗号の基礎。第 2 巻。ケンブリッジ大学出版局。

• Moni NaorとMoti Yung、「ユニバーサル一方向ハッシュ関数とその暗号化アプリケーション」、1989 年。