Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over Fnp

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 Fp 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 ↦→ xd . In this paper, we start an analysis of new non-linear permutation functions over Fnp that can be used as building blocks in such symmetric-key primitives. Given a local map F: Fmp → Fp, we limit ourselves to focus on S-Boxes over Fnp for n ≥ m defined as SF (x0, x1, …, xn−1) = y0∥y1∥ … ∥yn−1 where yi:= F (xi, xi+1, …, xi+m−1). As main results, we prove that • given any quadratic function F: F2p → Fp, the corresponding S-Box SF over Fnp for n ≥ 3 is never invertible; • similarly, given any quadratic function F: F3p → Fp, the corresponding S-Box SF over Fnp for n ≥ 5 is never invertible. Moreover, for each p ≥ 3, we present (1st) generalizations of the Lai-Massey construction over Fnp defined as before via functions F: Fmp → Fp for each n = m ≥ 2 and (2nd) (non-trivial) quadratic functions F: F3p → Fp such that SF over Fnp for n ∈ {3, 4} is invertible. As an open problem for future work, we conjecture that for each m ≥ 1 there exists a finite integer nmax(m) such that SF over Fnp defined as before via a quadratic function F: Fmp → Fp is not invertible for each n ≥ nmax(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.