Paper 2022/342

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

Lorenzo Grassi, Radboud University Nijmegen (Nijmegen, The Netherlands)
Morten Øygarden, Simula UiB (Bergen, Norway)
Markus Schofnegger, Horizen Labs (Austin, United States)
Roman Walch, Graz University of Technology (Graz, Austria), Know-Center GmbH (Graz, Austria), TACEO GmbH (Graz, Austria)

The area of multi-party computation (MPC) has recently increased in popularity and number of use cases. At the current state of the art, Ciminion, a Farfalle-like cryptographic function, achieves the best performance in MPC applications involving symmetric primitives. However, it 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 pseudo-random functions (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 present a novel primitive in symmetric cryptography called Megafono. Megafono is a keyed extendable PRF, expanding a fixed-length input to an arbitrary-length output. Similar to Farfalle, an initial keyed permutation is applied to the input, followed by an expansion layer, involving the parallel application of keyed ciphers. The main novelty regards the expansion of the intermediate/internal state for "free", by appending the sum of the internal states of the first permutation to its output. The combination of this and other modifications, together with the impossibility for the attacker to have access to the input state of the expansion layer, make Megafono very efficient in the target application. As a concrete example, we present the PRF Hydra, an instance of Megafono based on the Hades strategy and on generalized versions of the Lai--Massey scheme. 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.

Note: Compared to the previous version we simplified the design by giving specific instantiations of the non-linear layers instead of describing them in a general way. A note with the changes compared to the first version, in which Megafono and Hydra were quite different, is still present in the paper.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
MegafonoHydraFarfalleCiminionMPC Applications
Contact author(s)
lgrassi @ science ru nl
morten oygarden @ simula no
mschofnegger @ horizenlabs io
roman walch @ iaik tugraz at
2023-02-23: last of 2 revisions
2022-03-14: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.