Posted by: jonkatz | February 4, 2010

Signatures from one-way functions

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:

1. Start with a one-time signature scheme $\Pi'$ 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).
2. Use $\Pi'$ in a binary tree to obtain a (many-time) signature scheme \$\Pi\$.
3. Step 2 actually gives a scheme $\Pi$ 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 $\Pi$ could be implemented fairly easily, and (for practical parameters) would “only” be a factor of 100 or so slower than $\Pi'$. 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 $t$-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?

Responses

1. Signatures have always felt to me like one of the ‘hardest’ basic objects to construct, even harder than CCA2-secure encryption — which is weird and unexpected, since in principle they can come from one-way functions.

The root difficulty seems to be that the security reduction for a signature scheme has to answer queries — and not just answer them, but answer them all ‘meaningfully.’ That is, every message query must be answered by a signature that actually verifies correctly. This is in contrast to CCA security, where the scheme gets to declare a whole swath of ciphertext queries ‘off-limits’ by having them decrypt to \bot.

I agree that the current situation is really unsatisfactory.

2. to me it seems like the root of the difficulty, and the main difference from encryption, is that the adversary is in complete control of the forgery it gives you — there is no way to cook up public parameters for the scheme so that the adversary’s forgery “hits” some special value you used. more to the point, one can consider a “selectively secure” unforgeability notion (has this appeared before?) where the adversary has to declare the message it intends to forge on *up front*, before seeing the vk. It can later make as many signature queries as it likes (not for the declared message to forge, of course). I think it is much easier to design signatures secure under this notion.

3. @Chris: I agree: one of the weird things about signatures is that, on the one hand, they can be constructed from the weakest assumption; on the other hand, constructing them from essentially *any* assumption is pretty hard.

@Adam: I think the issue you raised is the reason for needing a tree-based construction. But why should we need to involve UOWHFs and PRFs also? I’m not sure if a “selectively secure” scheme could be constructed that avoids those primitives. (Also, unfortunately, I don’t think selective security for signatures buys you a lot. In particular I don’t know of any easy transformation from that notion to the standard one.)

4. Chris, your intuition can be formalized (I hope :)) if one looks at LEAKAGE-RESILIENT (LR) signature vs. encryption. As far as I know, efficient LR encryption (even CCA) can be built from hash proof systems, which results in a variety of EFFICIENT schemes.
See Lecture 12 of my course notes from http://www.cs.nyu.edu/courses/fall09/G22.3220-001/syllabus.html

For LR signatures, I strongly suspect they cannot be built not only from OWFs, but from ANY non-black-box assumption (e.g., TDPs, hash proof systems, or anything else you want). The only constructions we know are from various forms of NIZK. Jon’s asiacrypt’09 paper uses simulation-sound NIZK, which does not give any efficient candidates. In my new paper with students which we almost finish, we generalize it to slightly weaker form of “true statement simulation-extractabe NIZK”. The latter finally allow for the FIRST efficient instantiation (in the standard model). But it is still MUCH more complicated than CCA encryption. In fact, our construction uses CCA encryption as a building block critically to achieve efficiency.
See Lecture 13 of the notes (although there we do not show an efficient instantiation, and only sketch the main ideas).

So I think we are getting closer to formalizing your claim than signatures might be harder than encryption, at least for LR schemes :).

Yevgeniy

5. @Jon, you can always just apply the lossy reduction of guessing the forgery message. At least if you start with exponential hardness this should be OK. I’m not exactly sure how much selective security simplifies things; it seems interesting to think about. My intuition is that it should make encryption-type techniques more applicable. Not that we have a construction of CCA enc from TDF either…

6. @Jon: It seems easy to construct a “random message unforgeable” signature scheme secure against chosen message attacks, starting from a trapdoor permutation. Thus, in some sense, the hardness of constructing signature schemes lies in dealing with the the fact that the adversary can choose which message he forges a signature on.

(Actually, even this construction needs a chameleon hash, and constructing that might involve UOWHFs. Well, at least, we don’t run into trees).

7. oh, good point. actually, i think chameleon hashing can be constructed from a claw free TDP? combining this approach with what i said above, it seems we get a simple fully secure scheme from subexponentially hard claw free TDPs. not too bad.

8. well, chameleon hashing is still definitely stronger than UOWHF. But at least this gets rid of PRF and trees.

9. @Vinod: Maybe I’m missing something, but I don’t see the construction. (Or rather, I see one construction but the proof seems to break down.)

As far as I can tell, a chameleon hash is the same as a signature scheme secure against one-time non-adaptive chosen message attacks. (Which, of course, is easy to construct from OWF.) So that shouldn’t be the barrier.

And of course, clawfree permutations imply collision-resistant hash functions so that at least eliminates the problems with UOWHFs…

10. I assume Vinod’s construction is:

Sign(m) = f^{-1}(h(m;r)), m, r

where f is TDP, h is chameleon hash?

It seems that chameleon hash lets you easily answer the chosen-message queries in reduction. But doesn’t it also destroy the reduction to inverting a TDP, even for a random message forgery? Now the adversary doesn’t need to compute f^{-1}(m) to sign m, but rather needs to invert h(m;r) which is in his control, even if we force him to sign a random m. I don’t see the proof.

On a different note, one other disadvantage of sigs from OWF is that they are long. Even if we just use Random Oracles, it seems that to get security 2^{-s}, the sig length would be s^3
(you need s one-time sigs, each of which consists of s blocks of length s). I always wondered if you can do better, or show some black-box lower bound….

11. Barak-Mahmoody and earlier work by myself and Gennaro-Gertner gives bounds on the efficiency of one-time signatures based on random oracles and OWPs, respectively. It is a great question to try to prove some kind of bound on the signature length. Another great direction is to show stronger efficiency lower bounds for many-time sigs.

12. How about the following using simulation-sound (ss)-NIZK:

PK: Run the simulator to get crs.

SignKey: Trapdoor t to the crs which allows proving
FALSE statements.

Sign(m): Construct a trivially false statement such as: “v=f(m)” where v is f(m’), m’ is different from m, and f is one-way TDP. Now construct a convincing proof p for this false statement under the crs in PK using the trapdoor t. The signature is just this proof p and f (we can put f also in PK if we want).

Verify(m, p, PK). Check that v is not equal to f(m), and p convinces the nizk verifier for the crs.

Forgery for any new m implies breaking simulation soundness. ss-nizk can be constructed from CRHF and certified-TDP.

13. OK I guess my previous post misses the point about simplicity of the proof: if you write down the whole proof, you will perhaps need to write down the cook-levin reduction… there we go. so much for the simplicity!

14. @Omkant: Your idea is similar to the signature scheme of Bellare-Goldwasser (Crypto ’89) that uses NIZK instead of SS-NIZK.

While I wouldn’t include the Cook-Levin reduction in the proof (all that is required is its existence), a complete proof would require the construction of NIZK…not exactly simpler.

15. Regarding Vinod’s (failed) construction, can’t we at least still make it go through using subexp hardness?

16. Hi Jon,

just found this blog. Nice topic. As a third step of the construction you mention a little trick by Goldreich to get rid of the statefulness using PRFs. Which trick would this be?
And by the way, for the stateful scheme we have implementations that are compareable to actual RSA implementations regarding efficiency (less than a factor of 2 slower)

17. this is proven that the existence of one way functions implies the existence of one time signatures, but how about the reverse? does the existence of one time signatures implies the existence of one way functions? if so, how?can you please prove this for me?