Paper 2022/342

From Farfalle to Megafono via Ciminion: The PRF Hydra for MPC Applications

Lorenzo Grassi, Morten Øygarden, Markus Schofnegger, and Roman Walch

Abstract

Ciminion is an MPC-friendly pseudo-random function (PRF) recently proposed at Eurocrypt’21. As in the case of other MPC-friendly constructions proposed in the literature (e.g., MiMC, HadesMiMC, Rescue), it aims to minimize the number of multiplications in large finite fields. While MiMC, HadesMiMC, and Rescue are block ciphers, Ciminion is a (modified) Farfalle-like cryptographic function. At the current state of the art, it achieves the best performance in MPC applications. However, Ciminion has a critical weakness. Its security highly relies on the independence of its subkeys, which is achieved by using an expensive key schedule. Many MPC use cases involving symmetric PRFs rely on secretly shared symmetric keys, and hence the expensive key schedule must also be computed in MPC. As a result, Ciminion’s performance is significantly reduced in these use cases. In this paper, we solve this problem. Following the approach introduced by Ciminion’s designers, we propose Megafono, a modified version of Farfalle designed for achieving a small multiplicative complexity without any key schedule. Following this strategy, we present the PRF Hydra, which utilizes both a Lai-Massey construction and a novel construction we name Amaryllises in its nonlinear layer. Amaryllises can be seen as a generalized variant of a Lai-Massey scheme, which allows us to further decrease the multiplicative complexity of Hydra. Based on an extensive security analysis, we implement Hydra in an MPC framework. The results show that it outperforms all MPC-friendly schemes currently published in the literature.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
MegafonoHydraFarfalleCiminionLai-MasseyAmaryllisesMPC Applications
Contact author(s)
lgrassi @ science ru nl
morten oygarden @ simula no
markus schofnegger @ tugraz at
roman walch @ iaik tugraz at
History
2022-03-14: received
Short URL
https://ia.cr/2022/342
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/342,
      author = {Lorenzo Grassi and Morten Øygarden and Markus Schofnegger and Roman Walch},
      title = {From Farfalle to Megafono via Ciminion: The PRF Hydra for MPC Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/342},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/342}},
      url = {https://eprint.iacr.org/2022/342}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.