Welcome to the resource topic for 2022/1313
Title:
Weak Bijective Quadratic Functions over \mathbb F_p^n
Authors: Lorenzo Grassi
Abstract:Motivated by new applications such as secure Multi-Party Computation (MPC), Homomorphic Encryption (HE), and Zero-Knowledge proofs (ZK),
many MPC-, HE- and ZK-friendly symmetric-key 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 primitive are usually defined via invertible functions, including (i) Feistel and Lai–Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes (as invertible power maps x\mapsto x^d). 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-/HE-/ZK-friendly symmetric primitives instantiated with non-invertible weak bijective functions. With respect to one-to-one correspondence functions, any output of a weak bijective function admits at most two pre-images. The simplest example of such function is the square map over \mathbb F_p for a prime p\ge 3, for which x^2 = (-x)^2.
When working over \mathbb F_p^n for n\gg 1, a weak bijective function can be set up by re-considering the recent results of Grassi, Onofri, Pedicini and Sozzi as starting point.
Given a quadratic local map F:\mathbb F_p^2 \rightarrow \mathbb F_p, they proved that the non-linear function over \mathbb F_p^n for n\ge 3 defined as \mathcal S_F(x_0, x_1, \ldots, x_{n-1}) = y_0\| y_1\| \ldots \| y_{n-1} where y_i := F(x_i, x_{i+1}) is never invertible. Here, we prove that
– the quadratic function F:\mathbb F_p^2 \rightarrow \mathbb F_p 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 weak bijective.
As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the HE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the weak bijective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.
ePrint: https://eprint.iacr.org/2022/1313
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .