Paper 2021/1695

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

Lorenzo Grassi, Radboud University, Nijmegen, the Netherlands
Silvia Onofri, Scuola Normale Superiore di Pisa, Pisa, Italy
Marco Pedicini, Università Roma Tre, Roma, Italy
Luca Sozzi, Università degli Studi di Milano, Milano, Italy
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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in TOSC 2022
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
2021-12-30: received
See all versions
Short URL
https://ia.cr/2021/1695
License
Creative Commons Attribution
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.