Paper 2021/1695

Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over $\mathbb F_p^n$

Lorenzo Grassi, Radboud University, Nijmegen, the Netherlands
Silvia Onofri, Scuola Normale Superiore di Pisa, Pisa, Italy
Marco Pedicini, Università Roma Tre, Roma, Italy
Luca Sozzi, Università degli Studi di Milano, Milano, Italy

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over $\mathbb{F}_p$ for a large prime $p$ have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps $x\mapsto x^d$. In this paper, we start an analysis of new non-linear permutation functions over $\mathbb{F}_p^n$ that can be used as building blocks in such symmetric-key primitives. Given a local map $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$, we limit ourselves to focus on S-Boxes over $\mathbb{F}_p^n$ for $n\ge m$ defined as $\mathcal{S}_F(x_0, x_1, \ldots, x_{n-1}) = y_0\| y_1\| \ldots \| y_{n-1}$ where $y_i := F(x_i, x_{i+1}, \ldots, x_{i+m-1} )$. As main results, we prove that - given any quadratic function $F:\mathbb{F}_p^2 \rightarrow \mathbb{F}_p$, the corresponding S-Box $\mathcal{S}_F$ over $\mathbb{F}_p^n$ for $n\ge 3$ is never invertible; - similarly, given any quadratic function $F:\mathbb{F}_p^3 \rightarrow \mathbb{F}_p$, the corresponding S-Box $\mathcal{S}_F$ over $\mathbb{F}_p^n$ for $n\ge 5$ is never invertible. Moreover, for each $p\ge 3$, we present (1st) generalizations of the Lai-Massey construction over $\mathbb{F}_p^n$ defined as before via functions $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$ for each $n=m\ge 2$ and (2nd) (non-trivial) quadratic functions $F:\mathbb{F}_p^3 \rightarrow \mathbb{F}_p$ such that $\mathcal{S}_F$ over $\mathbb{F}_p^n$ for $n\in \{3,4\}$ is invertible. As an open problem for future work, we conjecture that for each $m\ge 1$ there exists a \textit{finite} integer $n_{\text{max}}(m)$ such that $\mathcal{S}_F$ over $\mathbb{F}_p^n$ defined as before via a quadratic function $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$ is \textit{not} invertible for each $n\ge n_{\text{max}}(m)$. Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.

Note: - Proofs partially re-written - More examples - Additional section with open problems for future works - Typos corrected

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in TOSC 2022
Multiplicative Complexity Non-Linear Layer MPC/FHE/ZK-Friendly Schemes Poseidon
Contact author(s)
lgrassi @ science ru nl
silvia onofri @ sns it
marco pedicini @ uniroma3 it
sozzi luca97 @ gmail com
2022-08-26: last of 4 revisions
2021-12-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lorenzo Grassi and Silvia Onofri and Marco Pedicini and Luca Sozzi},
      title = {Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over $\mathbb F_p^n$},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1695},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.