That digital signature schemes can be constructed based on the (minimal) assumption that one-way functions exist is surely one of the major successes of theoretical cryptography. Reviewing this result recently as part of a survey I am writing, it struck me how complicated the construction is. At a high level, the construction proceeds like this:
- Start with a one-time signature scheme whose message length is twice as long as its public-key length. These are not easy to construct, and appear to require a universal one-way hash function (which can be constructed from any one-way function).
- Use in a binary tree to obtain a (many-time) signature scheme $\Pi$.
- Step 2 actually gives a scheme that is stateful. One can obtain a stateless scheme by applying an idea due to Goldreich that relies on pseudorandom functions (which can be constructed from any one-way function).
Step 2 is fairly easy, and is described in my book. Given a universal one-way hash function (UOWHF), step 1 is not trivial (the issue is that the hash function may have an extremely long key) but it’s not too hard either. Given a pseudorandom function (PRF), step 3 is standard.
The problem is that if we want a complete proof that one-way functions imply signature schemes, we must also prove the existence of UOWHFs and PRFs based on one-way functions. These proofs are themselves quite involved (though there has been some work simplifying them in the past few years). So a complete proof that one-way functions imply signature schemes would run to something like 100 pages. (If I’ve missed something please let me know.)
And let’s not forget about efficiency. Step 2, above, is inefficient by the standards of practical crypto, but not terribly inefficient by the standards of theoretical crypto: scheme could be implemented fairly easily, and (for practical parameters) would “only” be a factor of 100 or so slower than . But building an actual UOWHF or a PRF from a one-way function seems out of the question.
Do things get better, in terms of complexity, if we are willing to make (slightly) stronger assumptions? Unless we are willing to rely on the random oracle model, the answer is: not much. Assuming (trapdoor) one-way permutations allows for simpler constructions of UOWHFs and PRFs, but still all 3 steps sketched above are necessary. Assuming collision-resistant hash functions gives UOWHFs trivially, but doesn’t help with constructing PRFs and doesn’t allow us to eliminate any of the above steps.
Is this inherent? There has been some work proving lower bounds on the efficiency of one-time signature schemes, but to my knowledge no results showing any inherent efficiency “gap” between many-time signatures and one-time signatures. But an even more interesting question (to me) is whether the complexity of the construction can be improved (even at the expense of reduced efficiency). Is the reliance on a PRF to get a stateless scheme really necessary? Are universal one-way hash functions really needed in order to apply the tree-based construction of step 2? Or, for that matter, might there be a totally different approach that doesn’t rely on trees at all? Some hope for this — though I admit it is not much — is that the construction of a one-time signature scheme (or even a -time signature scheme) from one-way functions is simple and self-contained. Why should it be so much more difficult to handle an unbounded number of signatures than it is to handle an arbitrary, but bounded, number of signatures?