Paper 2023/690

Invertible Quadratic Non-Linear Functions over ${\mathbb{F}}_p^n$ via Multiple Local Maps

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 $$, as the power maps $$ for $$. When working over $$ for $$, a possible way to construct invertible non-linear layers $$ over $$ is by making use of a local map $$ for $$, that is, $$ where $$. This possibility has been recently studied by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022. Given a quadratic local map $$ for $$, they proved that the shift-invariant non-linear function $$ over $$ defined as before is never invertible for any $$. 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 $$ for $$ of degree at most 2. This is a generalization of the previous construction using two alternating functions $$ instead of a single $$. As main result, we prove that (i) if $$, then $$ is never invertible if both $$ and $$ are quadratic, and that (ii) if $$, then $$ is invertible if and only if it is a Type-II Feistel scheme.