Bounded Surjective Quadratic Functions over for MPC-/ZK-/FHE-Friendly Symmetric Primitives
Lorenzo Grassi, Ruhr University Bochum, Bochum, Germany
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 for a large prime 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. With respect to one-to-one functions, any output of a -bounded surjective function admits at most pre-images. The simplest example is the square map over for a prime , which is (obviously) -bounded surjective.
When working over for , 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 for , they proved that the shift-invariant non-linear function over defined as where is never invertible for any . Here, we prove that
- the quadratic function for that minimizes the probability of having a collision for over is of the form (or equivalent);
- the function over defined as before via (or equivalent) is -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.