Factoring ⇒ Claw-free permutations (GMR)

Fully-black-box reduction · standard model · GMR88 · security loss: a factor of about 2: such integers are about half of all Blum integers, and every claw factors N

Statement

Let $N=pq$ with $p\equiv 3(\mathrm{mod}8)$ and $q\equiv 7(\mathrm{mod}8)$. Then

$$f_0(x):=x^2\mathrm{mod}N,f_1(x):=4x^2\mathrm{mod}N$$

are permutations of ${\mathrm{QR}}_N$ with trapdoor $(p,q)$, and if factoring Blum integers is hard they form a claw-free pair — GMR88. Such $N$ are exactly the Blum integers with $N\equiv 5(\mathrm{mod}8)$, about half of them, so a claw finder with advantage $\epsilon$ factors a uniform Blum integer with probability about $\epsilon /2$ — standard.

Sketch

A claw $x^2\equiv 4y^2(\mathrm{mod}N)$ with $x,y\in {\mathrm{QR}}_N$ gives $N\mid (x-2y)(x+2y)$. Since $N\equiv 5(\mathrm{mod}8)$, the Jacobi symbol of $2$ is $-1$, so $\pm 2y$ has Jacobi symbol $-1$ while $x$ has $+1$; hence $x\not\equiv \pm 2y$ and $\gcd (x-2y,N)$ is a prime factor — GMR88.

Notes

• GMR88 build their signature scheme from such a pair: FAC ⇒ DS — GMR88.
• A claw-free pair yields collision-resistant hashing: Claw-free permutations ⇒ CRHF — Dam87.