The Full-Domain Hash (FDH) Signature Scheme

Full-domain hash (FDH) gives what is perhaps the most intuitively appealing approach to constructing digital signatures, and can be viewed as a secure realization of the original ideas of Diffie and Hellman.

At a high level, the public key in FDH consists of (a description of) a trapdoor permutation ; the secret key is (the description of) the inverse . Letting be a hash function (that will be modeled as a random oracle) mapping messages to the domain of , the signature on a message is simple . Verification of a candidate signature can be done by simply checking whether . This is formalized as below, where the main difference is that we are more precise regarding our use of

• The FDH signature schemeLet be a trapdoor permutation family, and let be a hash function.
• Key generation: Compute . The public key is and the secret key is .
• Signature generation: To compute the signature on a message , compute followed by . Then output the signature .
• Signature verification: To verify a signature on a message , compute followed by . Then output 1 iff .

Theorem :  If is a doubly enhanced trapdoor permutation, and is modeled as a random oracle, then Construction above is strongly unforgeable under an adaptive chosen-message attack.

Messages in FDH have unique signatures, so unforgeability implies strong unforgeability.

Given a PPT adversary attacking the FDH signature scheme, making hash queries (i.e., queries to the random oracle computing ) and forging a signature with probability , we construct a PPT algorithm inverting with probability at least . Since must be polynomial, we conclude that must be negligible.

Because is doubly enhanced, there exists  an algorithm that takes as input and outputs a tuple such that (1) and , and (2) the distribution on is statistically close to uniform.

For simplicity we will assume that the distribution on is uniform. We also make three assumptions, without loss of generality, regarding the behavior of :

1. never repeats a query to the random oracle.
2. Before making a signature query on a message , adversary first makes the hash query .
3. Before outputting a forgery , adversary first makes the hash query .

Our algorithm proceeds as follows:

Algorithm

The algorithm is given as input, with . Its goal is to output such that .

• Choose .

• Run on the public key . Store triples in a table, initially empty. An entry indicates that has set , and (in particular, is a valid signature on ).

• When makes its th random oracle query , answer it as follows:

  When requests a signature on a message , let be such that and answer this query as follows:

• If , then there is an entry in the table. Return
• If then abort.
• If , return .
• Otherwise, compute , return as the answer to the query, and store in the table.

• If outputs a forgery with , return .

We may easily observe that as long as does not abort, the simulation it provides for is perfect. Specifically:

1. The public key has the correct distribution.
2. 's th query to the random oracle is answered with the random string . By definition of , all of 's other queries to the random oracle are also answered with a random string.
3. Signing queries (assuming does not abort) are also answered correctly; this, again, follows from the properties of .

Moreover, if outputs a forgery with then

and so correctly solves its given instance. The theorem follows from the fact that the guess made by (representing a guess of the hash-query index for which will produce its forgery) is correct with probability .