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 

As mentioned before, the definitions could be relaxed by allowing more algorithms to be probabilistic and allowing more small error probabilities. In particular, one could restrict more properties to good keys (which are assumed to be verified with zero-knowledge proofs and thus with error probabilities), instead of all acceptable keys (which are assumed to be locally verifiable). 

Families GoodFam = (Goo ijt)jfceN AllFam = (Aiiidken (called the 

---

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

---