Paper 2021/1695

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

Lorenzo Grassi and Silvia Onofri and Marco Pedicini and Luca Sozzi

Abstract

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(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$ 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$ 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$ 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 finite integer $n_{max}(m)$ such that $\mathcal S$ over $\mathbb F_p^n$ defined as before via a quadratic function $F:\mathbb F_p^m \rightarrow \mathbb F_p$ is not invertible for each $n\ge n_{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: Typos corrected