Full-domain hash

Full domain hash (abbreviation FDH ) is a signature method from the field of cryptology . The recipient of a message can use it to check whether the message that the sender has sent to him has been modified by a third party or not.

The principle of the procedure is to first hash a message and then apply any trapdoor one- way permutation to it. The hash function is modeled as a random oracle , the image set of which is equal to the definition range of the one-way permutation. This is where the name full-domain hash comes from.

Description of the protocol

The full-domain hash process is an asymmetrical signature process whose public key is formed from a trapdoor one-way permutation and a random oracle . The associated secret key is the reverse function of trapdoor one-way permutation. ${\displaystyle (f,G)}$ ${\displaystyle f\colon \{0,1\}^{k}\rightarrow \{0,1\}^{k}}$ ${\displaystyle G\colon \{0,1\}^{*}\rightarrow \{0,1\}^{k}}$ ${\displaystyle f^{-1}}$

The signature of a message is calculated by the following function: ${\displaystyle x}$

${\displaystyle \operatorname {sig} (x)=f^{-1}(G(x))}$

The message is then sent to the recipient along with the signature.

The recipient receives the message together with the signature . With the verification function ${\displaystyle x}$ ${\displaystyle y=\operatorname {sig} (x)}$

${\displaystyle \operatorname {ver} (x,y)={\begin{cases}{\text{wahr}}&{\text{wenn }}f(y)=G(x)\\{\text{falsch}}&{\text{sonst}}\end{cases}}}$

he checks the message. This outputs true if and only if the message has not been changed.

RSA full domain hash

If the RSA function with the parameters known from RSA is used as a trapdoor one-way permutation , then one speaks of the RSA full-domain hash. The process has been proven to be secure, which means that no existential falsification can be generated even with an attack using freely selectable plain text . ${\displaystyle f}$ ${\displaystyle f(x)=x^{e}{\bmod {N}}}$

Security of the RSA full domain hash

If RSA is -safe, then the RSA full-domain hash method based on the random oracle model is -safe with ${\displaystyle (t',\epsilon ')}$ ${\displaystyle (t,\epsilon )}$

${\displaystyle t=t'-(q_{\mathrm {hash} }+q_{\mathrm {sig} }+1)\cdot {\mathcal {O}}(k^{3})}$

${\displaystyle \epsilon =\left(1+{\frac {1}{q_{\mathrm {sig} }}}\right)^{q_{\mathrm {sig} }+1}\cdot q_{\mathrm {sig} }\cdot \epsilon '}$

Note that Jean-Sébastien's article apparently assumes Coron . For large , this boils down to . ${\displaystyle q_{\mathrm {sig} }>0}$ ${\displaystyle q_{\mathrm {sig} }}$ ${\displaystyle \epsilon \sim \exp(1)\cdot q_{\mathrm {sig} }\cdot \epsilon '}$

That means: If there is an algorithm that can create an existential forgery for the full-domain hash method with a runtime of and probability of success of , at most calculating and requiring at most signatures, then there is an algorithm that uses discrete logarithms of RSA modules calculated with a duration of and probability of success of . ${\displaystyle t}$ ${\displaystyle \epsilon }$ ${\displaystyle q_{\mathrm {hash} }}$ ${\displaystyle q_{\mathrm {sig} }}$ ${\displaystyle t'}$ ${\displaystyle \epsilon '}$

relevance

The authors of Full-Domain-Hash have proposed another method, the Probabilistic Signature Scheme (PSS), which they believe has better cryptographic properties. Therefore, FDH is practically not used, as PSS was standardized within the framework of PKCS # 1 v2.1.

swell

• Douglas R. Stinson: Cryptography. Theory and Practice. 3. Edition. Chapman & Hall / CRC, 2005, ISBN 1-58488-508-4 , pages 304-307
• Jean-Sébastien Coron: On the Exact Security of Full Domain Hash. (PDF; 103 kB) CRYPTO 2000: pages 229–235
• Mihir Bellare , Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. (PDF; 196 kB) EUROCRYPT 1996: pages 399-416