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 Fp 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 → x2 over Fp for a prime p ≥ 3, which is (obviously) 2-bounded sur.... https://tosc.iacr.org/index.php/ToSC/article/view/10980

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

• Bibliographic citation: Bounded Surjective Quadratic Functions over Fnp for MPC-/ZK-/FHE-Friendly Symmetric Primitives ; volume:2023 ; number:2 ; year:2023 ; IACR transactions on symmetric cryptology ; 2023, Heft 2 (2023)

Contributors, Places and Time

• Creator: Grassi, Lorenzo

Further information

• DOI: 10.46586/tosc.v2023.i2.94-131
• URN: urn:nbn:de:101:1-2023102518561273457219
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 14.08.2025, 10:57 AM CEST