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

暗号学において、汎用一方向ハッシュ関数（UOWHF 、しばしば「ウーフ」と発音される）は、暗号学において特に重要な汎用ハッシュ関数の一種である。UOWHFは、衝突耐性ハッシュ関数（CRHF）の代替として提案されている。CRHFは強い衝突耐性特性を持つ。つまり、ハッシュ関数パラメータをランダムに選択した場合、ハッシュ関数の衝突を見つけることは困難である。一方、UOWHFでは、ハッシュ関数パラメータとは無関係に1つの原像が選択された場合に、衝突を見つけることが困難であることが求められる。この基本関数は、モニ・ナオールとモティ・ヤングによって提案され、「ターゲット衝突耐性」ハッシュ関数としても知られている。これは、トラップドア関数を使用しない一般的なデジタル署名方式の構築や、選択暗号文による安全な公開鍵暗号化方式に用いられた。

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よりも計算コストが低いと考えられており、ハッシュ関数の選択が事前ではなく実行の途中で行われる方式において、効率化を目的として最もよく使用されます。例えば、クラマー・ショウプ暗号では、暗号文の妥当性検査の一部としてUOWHFが使用されています。

参照

• 原像攻撃

さらに読む

• Goldreich, Oded (2004). 『暗号の基礎』第2巻. Cambridge University Press.

外部リンク

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