Collision-Intractable Function Families

More generally, for a tuple (fo, of functions with the same codomain, a claw can be defined as a pair of values together with indices of functions, i.e., ((j, x), (i , a )), with i i and/(x) =fi x ). 

If the function/is specified by an algorithm, one must take care what its intended domain is, because an algorithm may produce results even outside this domain. Values should only be regarded as a collision if they are in the domain. (For instance, they must have the correct Jacobi symbol in the factoring case — this is why the sets RQR , where membership can be decided efficiently, were introduced.) 

Collision-intractability is the computational property that it is infeasible to find collisions. It is only defined for families of functions For any single function that has a collision in the mathematical sense, there is an algorithm with constant running time that, independent of any input, always outputs this collision.  

Several classes of collision-intractable functions can be defined. Important ones are collision-intractable families of 

One could exclude this by requiring algorithms to stop with an error message outside their intended domains. However, it is often more efficient to separate the membership test for the domain from the algorithm that computes the function. For instance, the squaring function on RQR would become very inefficient if each application included the computation of the Jacobi symbol of the input and in many situations, the input is the result of a previous squaring and therefore in the correct domain anyway. 

---