Bounded Surjective Quadratic Functions over Fnp for MPC-/ZK-/FHE-Friendly Symmetric Primitives

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. These symmetric primitives are usually defined via invertible functions, including (i) Feistel and Lai-Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes. However, the “invertibility” property is actually never required in any of the mentioned applications.
In this paper, we discuss the possibility to set up MPC-/FHE-/ZK-friendly symmetric primitives instantiated with non-invertible bounded surjective functions. In contrast to one-to-one functions, each output of a l-bounded surjective function admits at most l pre-images. The simplest example is the square map x → x² over F_p for a prime p ≥ 3, which is (obviously) 2-bounded surjective. When working over Fⁿ_p for n ≥ 2, we set up bounded surjective functions by re-considering the recent results proposed by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022 as starting points. Given a quadratic local map F : F^m_p → F_p for m ∈ {1, 2, 3}, they proved that the shift-invariant non-linear function over Fⁿ_p defined as S_F (x₀, x₁, . . . , x_n−1) = y₀∥y₁∥ . . . ∥y_n−1 where yi := F(x_i, x_i+1) is never invertible for any n ≥ 2 · m − 1. Here, we prove that • the quadratic function F : F^m_p → F_p for m ∈ {1, 2} that minimizes the probability of having a collision for S_F over Fⁿ_p is of the form F(x₀, x₁) = x²₀ + x1 (or equivalent);
• the function S_F over Fⁿ_p defined as before via F(x₀, x₁) = x²₀ +x₁ (or equivalent) is 2ⁿ-bounded surjective.
As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the FHE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the bounded surjective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.