Infoscience

Conference paper

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).

Related material