Welcome to the resource topic for 2023/690
Title:
Invertible Quadratic Non-Linear Functions over \mathbb F_p^n via Multiple Local Maps
Authors: Ginevra Giordani, Lorenzo Grassi, Silvia Onofri, Marco Pedicini
Abstract:The construction of invertible non-linear layers over \mathbb F_p^n that minimize the multiplicative cost is crucial for the design of symmetric primitives targeting Multi Party Computation (MPC), Zero-Knowledge proofs (ZK), and Fully Homomorphic Encryption (FHE). At the current state of the art, only few non-linear functions are known to be invertible over \mathbb F_p, as the power maps x\mapsto x^d for \gcd(d,p-1)=1. When working over \mathbb F_p^n for n\ge2, a possible way to construct invertible non-linear layers \mathcal S over \mathbb F_p^n is by making use of a local map F:\mathbb F_p^m\rightarrow \mathbb F_p for m\le n, that is, \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}, \ldots, x_{i+m-1}). This possibility has been recently studied by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022. Given a quadratic local map F:\mathbb F_p^m \rightarrow \mathbb F_p for m\in\{1,2,3\}, they proved that the shift-invariant non-linear function \mathcal S_F over \mathbb F_p^n defined as before is never invertible for any n\ge 2\cdot m-1.
In this paper, we face the problem by generalizing such construction. Instead of a single local map, we admit multiple local maps, and we study the creation of nonlinear layers that can be efficiently verified and implemented by a similar shift-invariant lifting. After formally defining the construction, we focus our analysis on the case \mathcal S_{F_0, F_1}(x_0, x_1, \ldots, x_{n-1}) = y_0\|y_1\|\ldots \|y_{n-1} for F_0, F_1 :\mathbb F_p^2\rightarrow \mathbb F_p of degree at most 2. This is a generalization of the previous construction using two alternating functions F_0,F_1 instead of a single F. As main result, we prove that (i) if n\ge3, then \mathcal S_{F_0, F_1} is never invertible if both F_0 and F_1 are quadratic, and that (ii) if n\ge 4, then \mathcal S_{F_0, F_1} is invertible if and only if it is a Type-II Feistel scheme.
ePrint: https://eprint.iacr.org/2023/690
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 .