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 state*less*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?

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.

By:

Chris Peikerton February 4, 2010at 11:41 pm

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.

By:

adam oon February 5, 2010at 3:31 am

@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.)

By:

jonkatzon February 5, 2010at 8:16 am

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

By:

Yevgeniyon February 5, 2010at 12:20 pm

@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…

By:

adam oon February 5, 2010at 3:27 pm

@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).

By:

Vinodon February 6, 2010at 12:13 am

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.

By:

adam oon February 6, 2010at 3:12 am

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

By:

adam oon February 6, 2010at 3:49 am

@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…

By:

jonkatzon February 6, 2010at 7:40 pm

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….

By:

Daniel W.on February 7, 2010at 11:54 am

Barak-Mahmoody and earlier work by myself and Gennaro-Gertner gives bounds on the

efficiencyof 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 signaturelength. Another great direction is to show stronger efficiency lower bounds formany-timesigs.By:

jonkatzon February 7, 2010at 12:05 pm

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.

By:

omkanton February 7, 2010at 8:36 pm

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!

By:

omkanton February 7, 2010at 8:43 pm

@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

wouldrequire the construction of NIZK…not exactly simpler.By:

jonkatzon February 7, 2010at 10:16 pm

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

By:

adam oon February 8, 2010at 1:20 am

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)

By:

andreas hon June 10, 2011at 5:13 am

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?

thanks in advance

By:

anonymenouson June 22, 2011at 11:24 am

One-time signatures do imply one-way functions: just consider the function that maps a random string r to the public key output by KeyGen when using that randomness.

By:

jonkatzon June 22, 2011at 1:18 pm

Here’s one I prepared earlier…

http://unitambo.wordpress.com/one-way-function-with-trapdoor-table-pre-print/

By:

Phillip Somervilleon April 28, 2014at 9:13 am