CryptoDB
Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over Fnp: Application to Poseidon
| Authors: |
|
|---|---|
| Download: | |
| 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 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. |
BibTeX
@article{tosc-2022-32408,
title={Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over Fnp: Application to Poseidon},
journal={IACR Transactions on Symmetric Cryptology},
publisher={Ruhr-Universität Bochum},
volume={2022, Issue 3},
pages={20-72},
url={https://tosc.iacr.org/index.php/ToSC/article/view/9849},
doi={10.46586/tosc.v2022.i3.20-72},
author={Lorenzo Grassi and Silvia Onofri and Marco Pedicini and Luca Sozzi},
year=2022
}