Signature scheme against an unbounded rival

Question

I've seen this: Can a computationally unbounded adversary break any public-key encryption scheme?

And I've read the following theorem:

Theorem (Lamport, GMR, Naor-Yung, Rompel, Goldreich) If one-way functions exist then there are signature schemes which are existentially unforgeable under chosen plaintext attacks.

I was wondering if this implies, that given an unbounded rival, no signature scheme exists that this rival can't break. This is due to the fact that the rival can inverse the 'OWF'.

Any thoughts? Corrections?

Answer 1

Actually, the conclusion you drew doesn't follow from the theorem; the theorem says "if you have a OWF, then a secure signature scheme exists"; it doesn't say "if you don't have a OWF, then there are no secure signature schemes". As far as the theorem goes, there might be another way to generate a signature scheme; the proof implied by the theorem doesn't work, but there might be another proof that does.

However, it turns out that your conclusion is indeed correct; if you have an unbounded rival, then with the public key, he can forge the signature for any message he wants.

The proof needn't be fancy; all the unbounded adversary does is consider all possible signatures, check each one against the public key, and selects the one that validates. This obviously works no matter how the signature algorithm works internally.