### Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over $\mathbb F_p^n$

##### 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}_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} )$. 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}_F$ 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}_F$ 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}_F$ 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 \textit{finite} integer $n_{\text{max}}(m)$ such that $\mathcal{S}_F$ over $\mathbb{F}_p^n$ defined as before via a quadratic function $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$ is \textit{not} invertible for each $n\ge n_{\text{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.

Note: - Proofs partially re-written - More examples - Additional section with open problems for future works - Typos corrected

Available format(s)
Category
Secret-key cryptography
Publication info
Keywords
Multiplicative Complexity Non-Linear Layer MPC/FHE/ZK-Friendly Schemes Poseidon
Contact author(s)
lgrassi @ science ru nl
silvia onofri @ sns it
marco pedicini @ uniroma3 it
sozzi luca97 @ gmail com
History
2022-08-26: last of 4 revisions
See all versions
Short URL
https://ia.cr/2021/1695

CC BY

BibTeX

@misc{cryptoeprint:2021/1695,
author = {Lorenzo Grassi and Silvia Onofri and Marco Pedicini and Luca Sozzi},
title = {Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over $\mathbb F_p^n$},
howpublished = {Cryptology ePrint Archive, Paper 2021/1695},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1695}},
url = {https://eprint.iacr.org/2021/1695}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.