Lower Bounds on Signatures from Symmetric Primitives

Details Lower Bounds on Signatures from Symmetric Primitives Lower Bounds on Signatures from Symmetric Primitives

2008-01-23

arxiv.org/abs/0801.3680v2

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds on Signatures from Symmetric Primitives does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower Bounds on Signatures from Symmetric Primitives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds on Signatures from Symmetric Primitives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-282773