Can someone explain the two definitions in relation to each other?

Is a claw-free permutation a permutation without a trapdoor?

For your convenience, here's the definition of a "claw-free permutation":

Let $f_1,f_2$ be permutations. A triple $(x,y,z)$ is called a claw iff $f_1(x)=f_2(x)=z$. A pair $f_1,f_2$ of permutations is called claw-free iff there exists no efficient algorithm that can find a claw for these permutations.

The definition of a trapdoor permutation is a bit lengthier and thus only given as a reference.

  • 2
    $\begingroup$ I'm not sure I understand what you mean by "a claw-free permutation", given that the definitions only ever talks about pairs. Does that mean a function that is claw-free with every function but itself? $\endgroup$ – SEJPM Apr 18 '18 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.