On 2010-11-10 00:26, Jonathan Katz wrote: > - Some people mentioned that 2^k security requires signatures of length 2k, > presumably by analogy with hash functions.
To be precise, security against a "duplicate signature attack" (as defined in <http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.163>) requires that. The reason is just the obvious generic birthday attack: there are expected to be collisions once on the order of 2^k signatures of length 2k bits have been generated. (It does not matter that the signing function is randomized; the success probability in finding a collision can be higher than for a deterministic random oracle, but cannot be lower.) > Although I see some intuition for > thinking this, I don't see formally why this must be the case. (In particular, > I don't see why it's an issue if two legitimately issued signatures happen to > be the same, as long as they couldn't have been forged in advance.) It's not a problem unless you're using a protocol that assumes that a signature must be associated with a particular message. For example, suppose that you have a system that uses countersigned signatures to record that a piece of code has passed some verification procedure. That is, the author of a piece of code signs it, presents it to a verifier, and if the verifier is satisfied then they countersign the signature. Later, the code is presented together with the countersigned signature to another party, who will run it if both signatures are valid. There is an implicit assumption here that the author's signature is valid only for one piece of code, which is correct for some signature schemes and not for others. You could argue quite convincingly that this is a protocol design error (i.e. the verifier's signature should also have been on the code itself), but it's not a totally implausible error. -- David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com
signature.asc
Description: OpenPGP digital signature
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
