完全なドメインハッシュ

暗号学において、フルドメインハッシュ（FDH）は、ハッシュ・アンド・サイン・パラダイムに従うRSAベースの署名方式です。ランダムオラクルモデルにおいて、FDHは証明可能に安全（すなわち、適応型選択メッセージ攻撃に対して存在的に偽造不可能）です。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 )