Discrete-logarithm assumption

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. 

Other more or less formal abstract discrete-logarithm assumptions, such as in [BoKK90, McCu90, OkSS93] differ in the following points (apart from the absence of sets All0 Does one need... 

The most well-known and well-investigated discrete-logarithm assumption is that for multiplicative groups of finite prime fields, i.e., the cyclic groups "ZLp of order p - 1. It is called the standard discrete-logarithm assumption in the foUowing. Of coiu-se, p - 1 is even and therefore not a prime, hence these groups cannot be used directly here. 

If one wants a relation with the standard discrete-logarithm assumption, one must ensure that the quotient d = p-V)lq, i.e., the index of the subgroup, is only polynomial in k. 

Three other concrete discrete-logarithm assumptions that could be used are mentioned. 

It is easy to see that the remaining requirements made in the abstract discrete-logarithm assumption hold for this algorithm. Furthermore, once the order q of the group is known, it can be verified much quicker If the curve is defined over a field Zp, its order is known to be in the interval p + 1 2Vp- Hence, if q is from this interval, =, and g I, then the group order must be q, because any multiple would be too large. 

Apart from defining more such classes, one can also define details within each definition in different ways, e.g., requirements on the domains and membership tests (similar to the discrete-logarithm assumptions). In particular, all the following definitions contain sets Good and All of good keys or all acceptable keys, i.e., they make provisions for different interest groups the use of these sets is considered in Remark 8.38. Furthermore, not aU the simple relations between the definitions that one could prove are mentioned below. 

All the classes of function families shown in Figure 8.5 can be constructed both on the abstract discrete-logarithm assumption (see Section 8.5.3) and on the factoring assumption (see Section 8.5.5), and those without homomorphism properties also on the abstract assumption that a claw-intractable family of permutation pairs exists (see Section 8.5.4). An overview of these constractions is given in Figures 8.6 and 8.7. The top layer of both figures is identical to the bottom layer of Figure 8.5. 

This section contains the constructions of function families, as defined in Sec tion 8.5.2, on the abstract discrete-logarithm assumption. For an overview, see Figure 8.6 some details are summarized in Table 8.2. The earliest of the following... 

Case 1 Qmu = 2. If Qmu is the constant 2, i.e., all the tuples are pairs. Lemma 8.40d implies that the algorithm A that first calls A and then outputs x = -viV2 whenever V2 0 contradicts the discrete-logarithm assumption. (It only makes a negligible difference in the probabilities that both components of g are generators in the lemma, but not in the discrete-logarithm assumption.) Hence the assumed algorithm A cannot exist. 

The following table summarizes the most important parameters of the constructions of collision-intractable families of bundling homomorphisms, hiding homomor-phisms, and fixed-size hash functions based on the discrete-logarithm assumption. Note that the main use of fixed-size hash functions is in the constmction of real hash functions. 

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

As the construction is spread out in a modular way over several definitions, it seems useful to summarize the result. For even more concreteness, this is done for subgroups of prime fields, i.e., on a concrete discrete-logarithm assumption (Definition 8.21b). 

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. 

---