Cryptography Reference
In-Depth Information
The Hashing Paradigm. A common practice is to sign real documents via a two-
stage process: First the document is hashed into a (relatively) short bit string, and
then the basic signature scheme is applied to the resulting string. We note that this
heuristic becomes sound provided the hashing function is collision-free (as defined
in [58]). Collision-free hashing functions can be constructed, assuming the existence of
claw-free collections (as in Definition 2.4.6) [58]. One can indeed postulate that certain
off-the-shelf products (e.g., MD5 or SHA) are collision-free, but such assumptions need
to be tested (and indeed may turn out false). We stress that using a hashing scheme
in the foregoing two-stage process without carefully evaluating whether or not it is
collision-free is a very dangerous practice.
One useful variant on the foregoing paradigm is the use of universal one-way hashing
functions (as defined in [175]), rather than the collision-free hashing used earlier. In
such a case, a new hashing function is selected for each application of the scheme, and
the basic signature scheme is applied both to the (succinct) description of the hashing
function and to the resulting (hashed) string. (In contrast, when using a collision-free
hashing function, the same function, the description of which is part of the signer's
public key, is used in all applications of the signature scheme.) The advantage of using
universal one-way hashing functions is that their security requirement seems weaker
than that for the collision-free condition (e.g., the former can be constructed using any
one-way function [192], whereas this is NOT known for the latter).
Theorem B.2.2 (Plausibility Result [175, 192]): Signature schemes exist if and
only if one-way functions exist.
Unlike the paradigms (and some of the constructions) described earlier, the known
construction of signature schemes from arbitrary one-way functions has no practical
significance. It is indeed an important open problem to provide an alternative construc-
tion that can be practical and still utilize an arbitrary one-way function.
B.2.3. Some Suggestions
B.2.3.1. Suggestions for Further Reading
Fragments of a preliminary draft for the intended chapter on signature schemes can be
obtained on line [100].
In addition, there are the original papers: For a definitional treatment of signature
schemes , the reader is referred to [125] and [183]. Easy-to-understand constructions
appear in [20, 71, 67]. The proof of Theorem B.2.2 can be extracted from [175, 192]:
The first paper presents the basic approach and implements it using any one-way per-
mutation, whereas the second paper shows how to implement this approach using any
one-way function. Variants on the basic model are discussed in [183] and in [50, 137].
For discussion of message-authentication schemes (MACs) the reader is referred to [15].
B.2.3.2. Suggestions for Teaching
We suggest a focus on signature schemes, presenting the main definition and some
construction. One may use [125] for the definitional treatment, but should not use
349
Search WWH ::




Custom Search