Discrete-logarithm scheme

Theorem 9.11. If the discrete logarithm in the given family of groups is hard, the corresponding discrete-logarithm scheme from Definition 9.10 is secure. ... 

Lemma 9.22 (Complexity of the factoring schemes). In the following, the complexity of the schemes from Definition 9.17 and Lemma 9.19 is summarized. To avoid confusion when comparing the results with those of the discrete-logarithm scheme, where the size of k is usually different, the length I = r1 2 (=2k) is used as a parameter. 

Signing requires one exponentiation in G with a number of length p, which corresponds to one exponentiation in with the same exponent. (Thus, in contrast to the discrete-logarithm scheme, signing is not significantly more efficient than testing.)... 

Remark 9.23 (Small message spaces). As with the discrete-logarithm scheme, the message-block spaces are very simple, so that random choice of a message block and membership tests can be carried out efficiently, if they are needed in an application. 

The most important complexity parameters for the discrete-logarithm scheme and the factoring schemes are summarized in Table 9.1. To enable a comparison of the schemes, the complexity parameters are presented as functions of input parameters that yield similar message-block spaces and security. This means ... 

For similar message spaces, k in the discrete-logarithm scheme is set equal to p in the factoring schemes. Note, however, that p is arbitrary, whereas k is restricted by something like 160 < k < Ipl2. 

Discrete-logarithm scheme Factoring scheme with zero-knowledge proof Factoring scheme with local verifiability... 

Lengths are in bits multiplications are modulo a number of length I, except for the two multiplications in sign in the discrete-logarithm scheme, where the modulus is only of length p. The parameters p, I, and c are discussed in the text above. 

Discrete-Logarithm Scheme with Shorter Secret Key... 

It is a variant of the discrete-logarithm scheme where half of each one-time secret key is reused for the next signature. For simplicity, it is immediately presented with subgroups of prime fields, i.e., in a form similar to Lemma 9.12. Moreover, the length of the public key is not minimized for the moment, and the scheme is presented for message blocks see Remark 10.25. 

The abbreviated names of the constructions mean bottom-up tree authentication (10.9), top-down tree authentication (10.13), top-down tree authentication with a small amount of private storage (10.19), the discrete-logarithm scheme with minimized secret key (10.22) without combination with tree authentication, and the construction with a list-shaped tree for a fixed recipient from Section 10.6. The first column of lower bounds is for standard fail-stop signature schemes (Sections 11.3 and 11.4), the second one for standard information-theoretically secure signature schemes (Section 11.5) here the length of a test key has been entered in the row with the public keys. 

For the upper bounds on standard fail-stop signature schemes, the constructions are based on the discrete-logarithm scheme (Lemmas 9.12 and 9.14). Bottom-up tree authentication is evaluated for the case where the risk bearers trust a fast hash... 

The practical complexity of the discrete logarithm has developed surprisingly similar to that of factoring (see Section 8.4.2), although no reduction between the two problems is known. As a consequence, the efficiency of the ElGamal scheme and RSA is rather similar, too. 

This implies that all types of schemes also exist both on the factoring assumption and on a discrete-logarithm assumption (with [Damg88]). 

The bank is the stronger partner in several ways. It can select the signature schemes and security parameters and thus provide for its own security. Moreover, it can inform itself about how trustworthy the cryptologic assumption is, both initially and while the scheme is in use, whereas many clients will already be deterred by the name of a factoring or discrete-logarithm assumption. 

All these simplifications can be applied to the construction of efficient fail-stop signature schemes based on the discrete-logarithm assumption, see Remark 9.16. 

Lemma 8.23. If the discrete logarithm is hard for the given generation scheme for subgroups of prime fields, Construction 8.22 is a family of groups of prime order where the discrete logarithm is hard. ... 

In this section, an efficient standard fail-stop signature scheme with prekey for signing one message block is shown where the security for the risk bearer can be proved on the abstract discrete-logarithm assumption. Recall that this scheme (for subgroups of prime fields) is due to [HePe93]. 

Prekey generation is of the same order of complexity as key generation in ordinary digital signature schemes As in the discrete-logarithm case, it is dominated by the primality tests needed for the generation of two primes. 

In the following, first a general theorem about combinations of hash functions and standard fail-stop signature schemes with prekey is presented formally. If a concrete fail-stop signature scheme based on a factoring or discrete-logarithm assumption is used, it is natural to combine it with a family of hash functions based on the same assumption. These special cases are considered afterwards. 

In Section 10.4, additional measures are added so that the amount of private storage is small all the time. Those measures are constructed specifically for the general construction framework from Section 9.2 and thus for the efficient schemes based on factoring and discrete logarithms. 

ElGa85 Taher ElGamal A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms IEEE Transactions on Information Theory 31/4 (1985) 469-472. 

---