Paper 2022/1313

Bounded Surjective Quadratic Functions over for MPC-/ZK-/FHE-Friendly Symmetric Primitives

Lorenzo Grassi, Ruhr University Bochum, Bochum, Germany
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 for a large prime have been recently proposed in the literature. These symmetric primitives are usually defined via invertible functions, including (i) Feistel and Lai-Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes. However, the ``invertibility'' property is actually never required in any of the mentioned applications. In this paper, we discuss the possibility to set up MPC-/FHE-/ZK-friendly symmetric primitives instantiated with non-invertible bounded surjective functions. With respect to one-to-one functions, any output of a -bounded surjective function admits at most pre-images. The simplest example is the square map over for a prime , which is (obviously) -bounded surjective. When working over for , we set up bounded surjective functions by re-considering the recent results proposed by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022 as starting points. Given a quadratic local map for , they proved that the shift-invariant non-linear function over defined as where is never invertible for any . Here, we prove that - the quadratic function for that minimizes the probability of having a collision for over is of the form (or equivalent); - the function over defined as before via (or equivalent) is -bounded surjective. As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the FHE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the bounded surjective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in TOSC 2023
Keywords
Bounded Surjective FunctionsLocal MapsQuadratic Functions
Contact author(s)
Lorenzo Grassi @ ruhr-uni-bochum de
History
2023-05-26: last of 3 revisions
2022-10-04: received
See all versions
Short URL
https://ia.cr/2022/1313
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1313,
      author = {Lorenzo Grassi},
      title = {Bounded Surjective Quadratic Functions over $\mathbb F_p^n$ for {MPC}-/{ZK}-/{FHE}-Friendly Symmetric Primitives},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1313},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1313}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.