Welcome to the resource topic for 2021/1695
Title:
Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over \mathbb F_p^n
Authors: Lorenzo Grassi, Silvia Onofri, Marco Pedicini, Luca Sozzi
Abstract: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 \mathbb F_p for a large prime p have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps x\mapsto x^d. In this paper, we start an analysis of new non-linear permutation functions over \mathbb F_p^n that can be used as building blocks in such symmetric-key primitives. Given a local map F:\mathbb F_p^m \rightarrow \mathbb F_p, we limit ourselves to focus on S-Boxes over \mathbb F_p^n for n\ge m defined as \mathcal S(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} ). As main results, we prove that - given any quadratic function F:\mathbb F_p^2 \rightarrow \mathbb F_p, the corresponding S-Box \mathcal S over \mathbb F_p^n for n\ge 3 is never invertible; - similarly, given any quadratic function F:\mathbb F_p^3 \rightarrow \mathbb F_p, the corresponding S-Box \mathcal S over \mathbb F_p^n for n\ge 5 is never invertible. Moreover, for each p\ge 3, we present (1st) generalizations of the Lai-Massey construction over \mathbb F_p^n defined as before via functions F:\mathbb F_p^m \rightarrow \mathbb F_p for each n=m\ge 2 and (2nd) (non-trivial) quadratic functions F:\mathbb F_p^3 \rightarrow \mathbb F_p such that \mathcal S over \mathbb F_p^n for n\in \{3,4\} is invertible. As an open problem for future work, we conjecture that for each m\ge 1 there exists a finite integer n_{max}(m) such that \mathcal S over \mathbb F_p^n defined as before via a quadratic function F:\mathbb F_p^m \rightarrow \mathbb F_p is not invertible for each n\ge n_{max}(m). Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.
ePrint: https://eprint.iacr.org/2021/1695
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 .