Bundling homomorphism

The bundling homomorphisms, which are defined next, are basically bundling functions that are homomorphisms. 

Definition S.30. A coliision-intractabie family of bundling homomorphisms is a collision-intractable family of bundling functions with the following additional properties and components ... 

Similar to bundling homomorphisms, hiding homomorphisms are basically hiding functions that are homomorphisms. 

After all the mathematical and computational preparations, it is quite clear that pair exponentiation in a family of groups of prime order where the discrete logarithm is hard yields a collision-intractable family of bundling homomorphisms. (It was first used in this way in [HePe93].) It only remains to be decided how the security parameters are related, because the family of groups has only one, k, whereas the family of bundling homomorphisms has two, say k and T for distinction. The following facts are known ... 

Sets of keys For all k, T e N, a key K = (q, desc, g) for the bundling homomorphisms is considered both good and acceptable if (q, desc) is an acceptable group description and g really consists of two generators. Thus... 

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. 

The construction of a collision-intractable family of bundling homomorphisms from iterated squaring and doubling is basically Construction 8.56, based on the claw-intractable families of permutation pairs from Construction 8.64. The new points are ... 

Construction 8.66. The family of iterated squaring and doubling as bundling homomorphisms has the following components ... 

Theorem 8.67 (Iterated squaring and doubling as bundling homomor-phisms). On the factoring assumption. Construction 8.66 defines a collision-intractable family of bundling homomorphisms. ... 

In this section, a framework for constructing standard fail-stop signature schemes with prekey for signing one message block from a collision-intractable family of bundling homomorphisms is described. Two parameters (the exact family of... 

A collision-intractable family BundFam of bundling homomorphisms. The same... 

A zero-knowledge proof scheme gen °, ZKP) with generation algorithm, goodness predicate, and external verifiability for the keys of the bundling homomorphisms, i.e., for the pair CorrFam, GoodFam) ... 

Prekey generation A prekey is primarily a key of the family of bundling homomorphisms, i.e., it specifies one such homomorphism. The security parameter k for this homomorphism is the same k as that for the signature scheme, whereas T is chosen as tau k, a). The zero-knowledge proof scheme is adapted accordingly. Additionally, the security parameters are in the prekey. This means ... 

All the algorithms are polynomial-time in the correct parameters. This is clear if one recalls that the definition of bundling homomorphisms contains algorithms... 

Recall that, according to the conventions after Definition 8.30, the domain Gjf of a bundling homomorphism is written additively and the codomain Hf multiplicatively. Hence 0 and 1 are the neutral elements in these two groups. 

Of course, in the present context, the scheme is constructed by using the family of pair exponentiations as bundling homomorphisms from Section 8.5.3 in the general construction framework from Section 9.2. 

BundFam, the collision-intractable family of bundling homomorphisms, is given by Construction 8.44, i.e., pair exponentiation in the given family of groups. Its... 

The corresponding main public key is the pair (mfci, mk2) of images under the bundling homomorphism, i.e.,... 

Remark 9.20. In the scheme with local verifiability, the random choice of jkj and sk2 is rather inefficient because of the computation of Jacobi symbols. One could avoid this if the bundling homomorphism were based on RQR% instead of RQR. However, no polynomial-time membership test in RQR" is known, and hence Definition 8.29 is not fulfilled. Nevertheless, it is now shown that the random choice in the main key generation of the signature scheme can be restricted to RQR, while maintaining the weaker membership tests for RQR in test and in verify simple. 

In the key-generation protocol, the signer s entity chooses an additional value e Gjf randomly as an encryption key. (Recall from Remark 10.16c that the prekey is of the formprek = ( 1 , 1 ° K, K°), where X is a key of a family of bundling homomorphisms.) It keeps e secret all the time. Thus skjemp priv = (e, skjemp) and sk temp auth = (par, prek, j). 

---