Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over Fnp
Application to Poseidon
DOI:
https://doi.org/10.46586/tosc.v2022.i3.20-72Keywords:
Multiplicative Complexity, Non-Linear Layer, MPC/FHE/ZK-Friendly Schemes, PoseidonAbstract
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 Fp 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↦xd. In this paper, we start an analysis of new non-linear permutation functions over Fnp that can be used as building blocks in such symmetrickey primitives. Given a local map F : Fmp→ Fp, we limit ourselves to focus on S-Boxes over Fnp for n ≥ m defined as SF (x0, x1, . . . , xn−1) = y0|y1| . . . |yn−1 where yi := F(xi, xi+1, . . . , xi+m−1). As main results, we prove that
• given any quadratic function F : F2p→ Fp, the corresponding S-Box SF over Fnp for n ≥ 3 is never invertible;
• similarly, given any quadratic function F : F3p → Fp, the corresponding S-Box SF over Fnp for n ≥ 5 is never invertible.
Moreover, for each p ≥ 3, we present (1st) generalizations of the Lai-Massey construction over Fnp defined as before via functions F : Fmp → Fp for each n = m ≥ 2 and (2nd) (non-trivial) quadratic functions F : F3p → Fp such that SF over Fnp for n ∈ {3, 4} is invertible. As an open problem for future work, we conjecture that for each m ≥ 1 there exists a finite integer nmax(m) such that SF over Fnp defined as before via a quadratic function F : Fmp →Fp is not invertible for each n ≥ nmax(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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Lorenzo Grassi, Silvia Onofri, Marco Pedicini, Luca Sozzi
This work is licensed under a Creative Commons Attribution 4.0 International License.