Design Validations for Discrete Logarithm Based Signature Schemes

A number of signature schemes and standards have been recently designed, based on the discrete logarithm problem. Examples of standards are the DSA and the KCDSA. Very few formal design/security validations have already been conducted for both the KCDSA and the DSA, but in the "full" so-called random oracle model. In this paper we try to minimize the use of ideal hash functions for several Discrete Logarithm (DSS-like) signatures (abstracted as generic schemes). Namely, we show that the following holds: "if they can be broken by an existential forgery using an adaptively chosen-message attack then either the discrete logarithm problem can be solved, or some hash function can be distinguished from an ideal one, or multi-collisions can be found." Thus for these signature schemes, either they are equivalent to the discrete logarithm problem or there is an attack that takes advantage of properties of practical hash functions (SHA-1 or whichever high quality cryptographic hash function is used). What is interesting is that the schemes we discuss include KCDSA and slight variations of DSA. Further, since our schemes are very close to their standard counterparts they benefit from their desired properties (efficiency of computation/space, employment of certain mathematical operations and wide applicability to various algebraic structures). We feel that adding variants with strong validation of security is important to this family of signature schemes since, as we have experienced in the recent past, lack of such validation has led to attacks on standard schemes, years after their introduction. In addition, schemes with formal validation which is made public, may ease global standardization since they neutralize much of the suspicions regarding potential knowledge gaps and unfair advantages gained by the scheme designer's country (e.g. the NSA being the designers of DSS).


Published in:
Public Key Cryptography, Third International Workshop on Practice and Theory in Public Key Cryptography, PKC 2000, 1751, 276-292
Presented at:
Public Key Cryptography, Third International Workshop on Practice and Theory in Public Key Cryptography, PKC 2000, Melbourne, Victoria, Australia, January 18-20, 2000
Year:
2000
Other identifiers:
Laboratories:




 Record created 2007-01-19, last modified 2018-03-17

n/a:
Download fulltext
PS

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)