Paper 2021/1695

Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over ${\mathbb{F}}_p^n$

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 $$. In this paper, we start an analysis of new non-linear permutation functions over $$ that can be used as building blocks in such symmetric-key primitives. Given a local map $$, we limit ourselves to focus on S-Boxes over $$ for $$ defined as $$ where $$. As main results, we prove that - given any quadratic function $$, the corresponding S-Box $$ over $$ for $$ is never invertible; - similarly, given any quadratic function $$, the corresponding S-Box $$ over $$ for $$ is never invertible. Moreover, for each $$, we present (1st) generalizations of the Lai-Massey construction over $$ defined as before via functions $$ for each $$ and (2nd) (non-trivial) quadratic functions $$ such that $$ over $$ for $$ is invertible. As an open problem for future work, we conjecture that for each $$ there exists a \textit{finite} integer $$ such that $$ over $$ defined as before via a quadratic function $$ is \textit{not} invertible for each $$. 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: Small correction of the security analysis and of the formula for computing the number of rounds.