Lower Bounds on Information-Theoretically Secure Signature Schemes

a conventional definition of those properties of information-theoretically secure signature schemes that are needed in the proofs is given. Actually, a rather small set of such properties is sufficient to prove the lower bounds. However, some restrictions are made, too. 

The main restriction, in conventional terms, is that a probabilistic function sign and a deterministic non-interactive function test exist, where each signature is supposed to pass the test of several other participants, called testers. In the classification of Chapter 5, this can be justified for several classes of schemes, e.g.  

Another restriction is that some properties are required without error probability. As ordinary digital signature schemes fulfil these restrictions, it was natural to assume 

The subset of security properties needed to prove the lower bounds only considers the case where all the entities, even those of the attackers, carry out key generation correctly, and neither active attacks on recipients nor provisions for finite transferability are used. Moreover, in the first class of schemes considered above, only unforgeability, and no requirement on disputes, is considered, and in the second class, with the same conventional definition, only the requirement of the signer on disputes, and not that of the recipient. (This suggests that one can prove more stringent bounds by using more requirements.) 

Finally, it is not used that the correct algorithms should work in polynomial time. Hence the definition is immediately made in a functional form corresponding to Definition 7.3. In particular, the secret key sk is assumed to include all the random bits the signer s entity will ever use. 

---

Lower Bounds on Information-Theoretically Secure Signature Schemes 361... 

---