Permutation pair

One might say cryptologically strong instead, if one adheres to the convention from Footnote 3. However, this term is established, and the convention is not always respected anyway. Actually, they are simply called claw-free permutation pairs in [G0MR88]. The two name changes make the notation consistent with related collision-intractable or collision-free families of hash functions (see Section 8.5). The reasons are that the objects called claws do exist, it is only infeasible to find them, and that similar families without trap-doors are needed later. 

All types of fail-stop signature schemes, as far as service is concerned, could be built very early on the abstract assumption that a claw-intractable family of permutation pairs exists, i.e., the assumption from [G0MR88], except that trap-doors are not even needed see [Pfit89, PfWa90],... 

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. 

Figure 8.7. Function families Cases of factoring and claw-intractable permutation pairs.

Signs c denote inclusion arrows denote constructions. The diagram at the bottom commutes, i.e., iterated squaring and doubling is the special case of iterated permutations where the construction of claw-intractable permutation pairs on the factoring assumption is used. 

Claw-intractable permutation pairs were introduced in [G0MR88]. This subsection contains a strong and a weak version of the definition, now without trap-doors. It may be helpful to know that the weak version will be used in the factoring case if one does not want to use a zero-knowledge proof, and thus the modulus n is not necessarily a generalized Blum integer. 

Deflnition 8.26. A strong claw-intractable family of permutation pairs... 

A probabilistic polynomial-time algorithm gen, the key-generation algorithm, that, on input 1 with k g IN, outputs a value K, called a key (representing the description of a permutation pair). 

This section contains the constructions of some types of function families defined in Section 8.5.2 from a claw-intractable family of permutation pairs. An overview is given by the left half of the constractions in Figure 8.7. For some constructions, the underlying family may be weak, for others, it must be strong. 

Lemma 8.55. (Finding claws in collisions). Whenever a claw-intractable family of permutation pairs is given (strong or weak, see Definitions 8.26 and 8.27), the corresponding algorithm claw from collision is defined as follows. (Remember that with the conventions from Definition 8.5, the iterated functions are called Bf. ) It works on inputs of the form K, x, x ) with K e All, where X = (b, y) and x = (b , y ) with b, b e 0, 1 " and y, y e Df. ... 

More formally, one would have to define claw from collision as an operator mapping a family of permutation pairs to an algorithm, but, similar to the notations B etc. from Definition 8.5, the additional notation would not be justified. 

Construction 8.56. Let a weak claw-intractable family of permutation pairs be given (see Definition 8.27). The corresponding family of iterated permutations as bundling functions is defined by the following components, which are written with an asterisk to distinguish them from the components of the family of permutation pairs ... 

Such algorithms can be constructed in a canonical way from those given in the family of permutation pairs. (Note that one can also choose random elements in the codomains efficiently.) ... 

Theorem 8.57 (Iterated permutations as bundling functions). If a strong claw-intractable family of permutation pairs is given. Construction 8.56 defines a collision-intractable family of bundling functions. If the underlying family is weak, all properties except for the bundling property are still guaranteed. ... 

A probabilistic polynomial-time algorithm choose that, with a first input K = K, V )e All, selects a random extended value for a given secret b merely chooses an element y of Dg randomly and outputs b, y). If K g Good, then K G Good, and hence the distribution is uniform by Definition 8.26. Polynomial-time algorithms that compute g r (probabilistically) and g in S g are clear, and those for g in G g and H g can easily be constructed from that for the sets Dg from the family of permutation pairs. 

In the construction of hash functions from a claw-intractable family of permutation pairs, the messages more or less correspond to the string parameter of the function B, but two additional aspects have to be considered ... 

Definition 8.60 (Components for hash functions from permutation pairs). 

The length restriction (Definition 8.26b) implies that a fixed-length encoding exists for each claw-intractable family of permutation pairs. However, to base a construction on it, one must effectively know one. ... 

Key generation gen On input 1 call gew( l ) to generate a key K, choose an element y of D/ randomly (using the algorithm given in the claw-intractable family of permutation pairs), and output... 

Remark 8.63. This family of hash functions can be augmented by short collision proofs according to Remark 8.37 Given a collision of the new family, one can use the extended version of clawJrom collision from Lemma 8.55c to compute either a claw of the underlying family of permutation pairs, or a collision of one of its functions. As the latter is impossible for correctly generated keys, where the functions are permutations, it is clearly infeasible to find collision proofs. ... 

Basically, the constructions are special cases of those described in the previous section, based on the permutation pairs from Definition 8.10. (The origin of the constructions is the same as in the previous section, too The basic idea is from [G0MR88] it was first applied to hash functions in [Damg88] and to bundling and hiding functions in [Pfit89, PfWa90].)... 

Hence this section starts with the construction of claw-intractable families of permutation pairs from these functions. In addition to the results that are then a consequence of Section 8.5.4, most function families in this section are families of homomorphisms, and one can use the results of Section 8.2.3 to show a bundling property even if only a weak claw-intractable family of permutation pairs is given. 

Squaring and Doubling as Claw-Intractable Permutation Pairs... 

The constructions in Section 8.2.3 had different properties depending on whether n was a generalized Blum integer or any element of 4N -1- 1. Thus two different families of good keys. Good and Good weak are provided they lead to a strong and a weak claw-intractable family of permutation pairs, respectively. 

Construction 8.64. The strong and weak GMR family of permutation pairs are defined as follows ... 

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

Before Construction 8.61 can be applied to the weak claw-intractable family of permutation pairs from Construction 8.64, a fixed-length encoding must be fixed. The sets to be encoded are RQR with I/1I2 2k. One can simply represent all their elements as binary numbers of length 2k with leading zeros. Furthermore, the standard prefix-free encoding, prefix Jree, is used for the messages. This yields the following construction. 

A complete formal description and a proof of a special case of bottom-up tree authentication (an optimized construction from strong claw-intractable families of permutation pairs) can be found in [Pfit89, PfWa90]. Hence only a sketch is presented here, whereas top-down tree authentication is treated in more detail. 

---