Paper 2022/1313
Bounded Surjective Quadratic Functions over $\mathbb F_p^n$ for MPC/ZK/FHEFriendly Symmetric Primitives
Abstract
Motivated by new applications such as secure MultiParty Computation (MPC), Fully Homomorphic Encryption (FHE), and ZeroKnowledge proofs (ZK), many MPC, FHE and ZKfriendly symmetrickey primitives that minimize the number of multiplications over $\mathbb 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 LaiMassey schemes and (ii) SPN constructions instantiated with invertible nonlinear SBoxes. 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/ZKfriendly symmetric primitives instantiated with noninvertible bounded surjective functions. With respect to onetoone functions, any output of a $l$bounded surjective function admits at most $l$ preimages. The simplest example is the square map $x\mapsto x^2$ over $\mathbb F_p$ for a prime $p\ge 3$, which is (obviously) $2$bounded surjective. When working over $\mathbb F_p^n$ for $n\ge 2$, we set up bounded surjective functions by reconsidering the recent results proposed by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022 as starting points. Given a quadratic local map $F:\mathbb F_p^m \rightarrow \mathbb F_p$ for $m\in\{1,2,3\}$, they proved that the shiftinvariant nonlinear function over $\mathbb F_p^n$ defined as $\mathcal S_F(x_0, x_1, \ldots, x_{n1}) = y_0\ y_1\ \ldots \ y_{n1}$ where $y_i := F(x_i, x_{i+1})$ is never invertible for any $n\ge 2\cdot m1$. Here, we prove that  the quadratic function $F:\mathbb F_p^m \rightarrow \mathbb F_p$ for $m\in\{1,2\}$ that minimizes the probability of having a collision for $\mathcal S_F$ over $\mathbb F_p^n$ is of the form $F(x_0, x_1) = x_0^2 + x_1$ (or equivalent);  the function $\mathcal S_F$ over $\mathbb F_p^n$ defined as before via $F(x_0, x_1) = x_0^2 + x_1$ (or equivalent) is $2^n$bounded surjective. As concrete applications, we propose modified versions of the MPCfriendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the FHEfriendly 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published by the IACR in TOSC 2023
 Keywords
 Bounded Surjective FunctionsLocal MapsQuadratic Functions
 Contact author(s)
 Lorenzo Grassi @ ruhrunibochum de
 History
 20230526: last of 3 revisions
 20221004: received
 See all versions
 Short URL
 https://ia.cr/2022/1313
 License

CC BYSA
BibTeX
@misc{cryptoeprint:2022/1313, author = {Lorenzo Grassi}, title = {Bounded Surjective Quadratic Functions over $\mathbb F_p^n$ for {MPC}/{ZK}/{FHE}Friendly Symmetric Primitives}, howpublished = {Cryptology ePrint Archive, Paper 2022/1313}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1313}}, url = {https://eprint.iacr.org/2022/1313} }