**Lower Bounds on Signatures From Symmetric Primitives**

*Boaz Barak and Mohammad Mahmoody*

**Abstract: **We show that every construction of one-time signature schemes from a random oracle achieves black-box security at most
$2^{(1+o(1))q}$, where $q$ is the total number of oracle queries asked by the key generation, signing, and verification
algorithms. That is, any such scheme can be broken with probability close to $1$ by a (computationally unbounded)
adversary making $2^{(1+o(1))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 one-time signatures (Lamport'79) achieves $2^{(0.812-o(1))q}$ black-box security using $q$ queries to the oracle.

Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.

**Category / Keywords: **foundations / signature schemes, random oracle, symmetric primitives

**Original Publication**** (with minor differences): **Annual Symposium on Foundations of Computer Science (FOCS), 2007.

**Date: **received 23 Jan 2008, last revised 30 Mar 2019

**Contact author: **mohammad at virginia edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20190331:001045 (All versions of this report)

**Short URL: **ia.cr/2008/033

[ Cryptology ePrint archive ]