Paper 2019/397

Feistel Structures for MPC, and More

Martin R. Albrecht, Lorenzo Grassi, Leo Perrin, Sebastian Ramacher, Christian Rechberger, Dragos Rotaru, Arnab Roy, and Markus Schofnegger


We study approaches to generalized Feistel constructions with low-degree round functions with a focus on x -> x^3 . Besides known constructions, we also provide a new balanced Feistel construction with improved diffusion properties. This then allows us to propose more efficient generalizations of the MiMC design (Asiacrypt’16), which we in turn evaluate in three application areas. Whereas MiMC was not competitive at all in a recently proposed new class of PQ-secure signature schemes, our new construction leads to about 30 times smaller signatures than MiMC. In MPC use cases, where MiMC outperforms all other competitors, we observe improvements in throughput by a factor of more than 4 and simultaneously a 5-fold reduction of preprocessing effort, albeit at the cost of a higher latency. Another use case where MiMC already outperforms other designs, in the area of SNARKs, sees modest improvements. Additionally, this use case benefits from the flexibility to use smaller fields.

Note: Results about MPC application have been updated.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
FeistelMultiplicative ComplexityAlgebraic AttackSecure Multiparty Computation (MPC)PQ-secure Signature SchemeSNARKs
Contact author(s)
arnab roy @ bristol ac uk
lorenzo grassi @ iaik tugraz at
2019-06-06: revised
2019-04-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R.  Albrecht and Lorenzo Grassi and Leo Perrin and Sebastian Ramacher and Christian Rechberger and Dragos Rotaru and Arnab Roy and Markus Schofnegger},
      title = {Feistel Structures for MPC, and More},
      howpublished = {Cryptology ePrint Archive, Paper 2019/397},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.