TY - JOUR
AU - Grassi, Lorenzo
PY - 2023/06/16
Y2 - 2023/10/04
TI - Bounded Surjective Quadratic Functions over Fnp for MPC-/ZK-/FHE-Friendly Symmetric Primitives
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2023
IS - 2
SE - Articles
DO - 10.46586/tosc.v2023.i2.94-131
UR - https://tosc.iacr.org/index.php/ToSC/article/view/10980
SP - 94-131
AB - <p>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<em><sub>p</sub></em> for a large prime <em>p</em> 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.<br>In this paper, we discuss the possibility to set up MPC-/FHE-/ZK-friendly symmetric primitives instantiated with non-invertible <em>bounded surjective</em> functions. In contrast to one-to-one functions, each output of a <em>l</em>-bounded surjective function admits at most <em>l</em> pre-images. The simplest example is the square map <em>x</em> → <em>x</em><sup>2</sup> over F<em><sub>p</sub></em> for a prime <em>p</em> ≥ 3, which is (obviously) 2-bounded surjective. When working over F<sup><em>n</em></sup><sub><em>p</em></sub> for <em>n</em> ≥ 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<em><sup>m</sup><sub>p</sub></em> → F<sub><em>p</em></sub> for <em>m</em> ∈ {1, 2, 3}, they proved that the shift-invariant non-linear function over F<em><sup>n</sup><sub>p</sub></em> defined as <em>S<sub>F</sub></em> (x<sub>0</sub>, x<sub>1</sub>, . . . , x<sub>n−1</sub>) = y<sub>0</sub>∥y<sub>1</sub>∥ . . . ∥y<sub>n−1</sub> where <em>y</em>i := <em>F</em>(x<sub><em>i</em></sub>, x<sub><em>i</em>+1</sub>) is never invertible for any <em>n</em> ≥ 2 · <em>m</em> − 1. Here, we prove that • the quadratic function F : F<em><sup>m</sup><sub>p</sub></em> → F<sub><em>p</em></sub> for <em>m</em> ∈ {1, 2} that minimizes the probability of having a collision for <em>S<sub>F</sub></em> over F<em><sup>n</sup><sub>p</sub></em> is of the form <em>F</em>(<em>x</em><sub>0</sub>, <em>x</em><sub>1</sub>) =<em> x<sup>2</sup></em><sub>0</sub> + <em>x</em>1 (or equivalent);<br>• the function <em>S<sub>F</sub></em> over F<em><sup>n</sup><sub>p</sub></em> defined as before via <em>F</em>(<em>x</em><sub>0</sub>, <em>x</em><sub>1</sub>) = <em>x</em><sup>2</sup><sub>0</sub> +<em>x</em><sub>1</sub> (or equivalent) is 2<sup><em>n</em></sup>-bounded surjective.<br>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.</p>
ER -