We show that every black-box construction of one-time signature schemes from a random oracle achieves security at most poly(q)2^q, where q is the total number of queries to the oracle by the generation, signing, and verification algorithms. That is, any such scheme can be broken with probability close to 1 by a (computationally unbounded) adversary making poly(q)2^q queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamport?s scheme achieves 2^{(0.812 - o(1))q} security using q queries.

Our results extend (with a loss of a constant factor in the number of queries) also to the random permutation and idealcipher oracles, and so can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives such as block ciphers, hash functions, and message authentication codes.