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

Application to Poseidon

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 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↦x^d. In this paper, we start an analysis of new non-linear permutation functions over Fⁿ_p that can be used as building blocks in such symmetrickey primitives. Given a local map F : F^m_p→ F_p, we limit ourselves to focus on S-Boxes over Fⁿ_p for n ≥ m defined as S_F (x₀, x₁, . . . , x_n−1) = y₀|y₁| . . . |y_n−1 where y_i := F(x_i, x_i+1, . . . , x_i+m−1). As main results, we prove that
• given any quadratic function F : F²_p→ F_p, the corresponding S-Box S_F over Fⁿ_p for n ≥ 3 is never invertible;
• similarly, given any quadratic function F : F³_p → F_p, the corresponding S-Box S_F over Fⁿ_p for n ≥ 5 is never invertible.
Moreover, for each p ≥ 3, we present (1st) generalizations of the Lai-Massey construction over Fⁿ_p defined as before via functions F : F^m_p → F_p for each n = m ≥ 2 and (2nd) (non-trivial) quadratic functions F : F³_p → F_p such that S_F over Fⁿ_p 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 n_max(m) such that S_F over Fⁿ_p defined as before via a quadratic function F : F^m_p →F_p is not invertible for each n ≥ 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.