# Can modular exponentiation with a public index be considered a secure permutation?

Secure permutation can be used in Sponge and Duplex constructions to build hash functions and encryption. To potentially use them in public-key cryptography, some arithmetic properties is desired.

Can modular exponentiation with a public index be considered a secure permutation? What public attacks are available? Are there constructions proven to be insecure?

Can modular exponentiation with a public index be considered a secure permutation?

I'll assume the permutation thought is $$f_{(n,e)}:\ x\mapsto x^e\bmod n$$ with odd $$n>2$$, odd $$e>1$$, and $$x$$ in the set $$\{0,1,\ldots n-2,n-1\}$$ less some subset of $$\{0,1,n-1\}$$.

$$f_{(n,e)}$$ is a permutation when $$n$$ is square-free, and $$e$$ is coprime with $$\varphi(n)$$.

When $$n$$ has $$k$$ (distinct) prime factors, $$f$$ has $$3^k$$ stationary points: any $$x$$ with $$x\bmod p\in\{0,1,p-1\}$$ for every prime $$p$$ dividing $$n$$. That always include $$0$$, $$1$$, and $$n-1$$, which is why we may want to remove them.

If $$2^i+3$$ is prime (that is for $$i$$ in A057732), and $$e$$ is coprime with $$2^i+2$$, then $$g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)$$ is a permutation of $$[0,2^i)$$ (which easily maps to the set of $$i$$-bit bitstrings), with the three obvious fixed points removed. We probably also want $$e>i$$, and may want $$e$$ of low Hamming weight. Examples where that construction might be useful: $$(i,e)=(30,65)$$, or $$(i,e)=(784,1025)$$. The later is a 98-byte permutation that's reasonably fast to evaluate. There is good hardware support in some crypto environments.

The permutation is easily invertible when the factorization of $$n$$ is public: we do as in RSA, that's at worse about $$\log_2(n)/\log_2(e)$$ more costly than the direct permutation.

Is that secure? It depends on the usage. It holds $$f_{(n,e)}(x)f_{(n,e)}(y)\bmod n=f_{(n,e)}(x\,y\bmod n)$$, which makes that permutation $$f_{(n,e)}$$ very special, and there's analog property for $$g_{(i,e)}$$. Thus we do not have a good substitute for a random permutation in all use cases of these, but that might do when combined with XOR for a few rounds in some symmetric crypto primitive.