A Note on the Walsh Spectrum of Power Residue S-Boxes

Abstract

Let ${\mathbb{F}}_q$ be a prime field with $q\ge 3$, and let $d,m\ge 1$ be integers such that $\gcd \left(d,q\right)=1$ and $m\mid (q-1)$. In this paper we bound the absolute values of the Walsh spectrum of S-Boxes $S(x)=x^d\cdot T\left(x^{\frac{q-1}{m}}\right)$, where $T$ is a function with $T(x)\ne 0$ if $x\ne 0$. Such S-Boxes have been proposed for the Zero-Knowledge-friendly hash functions Grendel and Polocolo. In particular, we prove the conjectured correlation of the Polocolo S-Box.