Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Full Domain Hash
open-in-new
<h2 id="security">Security</h2> <p>In the random oracle model, if RSA is ( t ′ , ϵ ′ ) {\displaystyle (t',\epsilon ')} -secure, then the full domain hash RSA signature scheme is ( t , ϵ ) {\displaystyle (t,\epsilon )} -secure where, </p> t = t ′ − ( q hash + q sig + 1 ) ⋅ O ( k 3 ) ϵ = ( 1 + 1 q sig ) q sig + 1 ⋅ q sig ⋅ ϵ ′ {\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}}} . <p>For large q sig {\displaystyle q_{\text{sig}}} this reduces to ϵ ∼ exp ( 1 ) ⋅ q sig ⋅ ϵ ′ {\displaystyle \epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '} . </p><p>This means that if there exists an algorithm that can forge a new FDH signature that runs in time <i>t</i>, computes at most q hash {\displaystyle q_{\text{hash}}} hashes, asks for at most q sig {\displaystyle q_{\text{sig}}} signatures and succeeds with probability ϵ {\displaystyle \epsilon } , then there must also exist an algorithm that breaks RSA with probability ϵ ′ {\displaystyle \epsilon '} in time t ′ {\displaystyle t'} . </p> <ul><li>Jean-Sébastien Coron(AF): On the Exact Security of Full Domain Hash. <a href="/facts/CRYPTO/TgVIMDmb">CRYPTO</a> 2000: pp. 229–235 (<a href="https://www.iacr.org/archive/crypto2000/18800229/18800229.pdf">PDF</a>)</li> <li><a href="/facts/Mihir_Bellare/uRjcPYqu">Mihir Bellare</a>, <a href="/facts/Phillip_Rogaway/hYhbH8V5">Phillip Rogaway</a>: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. <a href="/facts/EUROCRYPT/TgVIMDmb">EUROCRYPT</a> 1996: pp. 399–416 (<a href="http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf">PDF</a>)</li></ul>