Paper 2021/1695
Invertible Quadratic NonLinear Layers for MPC/FHE/ZKFriendly Schemes over $\mathbb F_p^n$
Abstract
Motivated by new applications such as secure MultiParty Computation (MPC), Fully Homomorphic Encryption (FHE), and ZeroKnowledge proofs (ZK), many MPC, FHE and ZKfriendly symmetrickey 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 nonlinear layer via power maps $x\mapsto x^d$. In this paper, we start an analysis of new nonlinear permutation functions over $\mathbb{F}_p^n$ that can be used as building blocks in such symmetrickey primitives. Given a local map $F:\mathbb{F}_p^m \rightarrow \mathbb{F}_p$, we limit ourselves to focus on SBoxes over $\mathbb{F}_p^n$ for $n\ge m$ defined as $\mathcal{S}_F(x_0, x_1, \ldots, x_{n1}) = y_0\ y_1\ \ldots \ y_{n1}$ where $y_i := F(x_i, x_{i+1}, \ldots, x_{i+m1} )$. As main results, we prove that  given any quadratic function $F:\mathbb{F}_p^2 \rightarrow \mathbb{F}_p$, the corresponding SBox $\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 SBox $\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 LaiMassey 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) (nontrivial) 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 nonlinear 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 rewritten  More examples  Additional section with open problems for future works  Typos corrected
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published by the IACR in TOSC 2022
 Keywords
 Multiplicative Complexity NonLinear Layer MPC/FHE/ZKFriendly Schemes Poseidon
 Contact author(s)

lgrassi @ science ru nl
silvia onofri @ sns it
marco pedicini @ uniroma3 it
sozzi luca97 @ gmail com  History
 20220826: last of 4 revisions
 20211230: received
 See all versions
 Short URL
 https://ia.cr/2021/1695
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1695, author = {Lorenzo Grassi and Silvia Onofri and Marco Pedicini and Luca Sozzi}, title = {Invertible Quadratic NonLinear Layers for MPC/FHE/ZKFriendly 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} }