完全なドメインハッシュ

暗号学において、フルドメインハッシュ( FDH ) はハッシュと署名のパラダイムに従うRSAベースの署名方式です。ランダムオラクルモデルでは、安全であることが証明されています(つまり、適応型選択メッセージ攻撃の下では存在的に偽造不可能です) 。FDH では、イメージサイズが RSA モジュラスのサイズに等しい関数を使用してメッセージをハッシュし、その結果を秘密の RSA 指数で乗算します。

ランダムオラクルモデルでは、RSAが-secureである場合、フルドメインハッシュRSA署名スキームは-secureである。ここで、 ${\displaystyle (t',\epsilon ')}$${\displaystyle (t,\epsilon )}$

${\displaystyle {\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\cdot {\mathcal {O}}\left(k^{3}\right)\\\epsilon &=\left(1+{\frac {1}{q_{\text{sig}}}}\right)^{q_{\text{sig}}+1}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}}$。

大きい場合、これは に減少します。 ${\displaystyle q_{\text{sig}}}$${\displaystyle \epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '}$

つまり、時間tで実行され、最大 個のハッシュを計算し、最大 個の署名を要求し、確率 で成功する新しい FDH 署名を偽造できるアルゴリズムが存在する場合、時間 の確率で RSA を破るアルゴリズムも存在するはずです。 ${\displaystyle q_{\text{ハッシュ}}}$${\displaystyle q_{\text{sig}}}$${\displaystyle \epsilon }$${\displaystyle \epsilon '}$${\displaystyle t'}$

• Jean-Sébastien Coron(AF): フルドメインハッシュの正確なセキュリティについて。CRYPTO 2000: pp. 229–235 (PDF)
• Mihir Bellare、Phillip Rogaway : デジタル署名の正確なセキュリティ - RSA と Rabin を使用した署名方法。EUROCRYPT 1996 : pp. 399–416 (PDF)