Paper 2013/251 Original: eprint.iacr.org/2013/251 ↗

Permutation Polynomials and Their Differential Properties over Residue Class Rings

Abstract

This paper mainly focuses on permutation polynomials over the residue class ring $\mathbb{Z}_{N}$, where $N>3$ is composite. We have proved that for the polynomial $f(x)=a_{1}x^{1}+\cdots +a_{k}x^{k}$ with integral coefficients, $f(x)\bmod N$ permutes $\mathbb{Z}_{N}$ if and only if $f(x)\bmod N$ permutes $S_{\mu}$ for all $\mu \mid N$, where $S_{\mu}=\{0< t <N: \gcd(N,t)=\mu\}$ and $S_{N}=S_{0}=\{0\}$. Based on it, we give a lower bound of the differential uniformities for such permutation polynomials, that is, $\delta (f)\geq \frac{N}{\#S_{a}}$, where $a$ is the biggest nontrivial divisor of $N$. Especially, $f(x)$ can not be APN permutations over the residue class ring \mathbb{Z}_{N}$. It is also proved that $f(x)\bmod N$ and $(f(x)+x)\bmod N$ can not permute $\mathbb{Z}_{N}$ at the same time when $N$ is even.