Lower Bounds on Signatures From Symmetric Primitives

Abstract

We show that every black-box construction of one-time signature schemes from a random oracle achieves security at most poly(q)2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sup> . 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(0.812-o(1))q</sup> 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 ideal-cipher 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.