MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity

Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, Tyge Tiessen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

507 Downloads (Pure)

Abstract

We explore cryptographic primitives with low multiplicative complexity. This is motivated by recent progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where primitives from symmetric cryptography are needed and where linear computations are, compared to non-linear operations, essentially “free”. Starting with the cipher design strategy “LowMC” from Eurocrypt 2015, a number of bitoriented proposals have been put forward, focusing on applications where the multiplicative depth of the circuit describing the cipher is the most important optimization goal.

Surprisingly, albeit many MPC/FHE/ZK-protocols natively support operations in GF(p) for large p, very few primitives, even considering all of symmetric cryptography, natively work in such fields. To that end, our proposal for both block ciphers and cryptographic hash functions is to reconsider and simplify the round function of the Knudsen-Nyberg cipher from 1995. The mapping F(x) := x3 is used as the main component there and is also the main component of our family of proposals called “MiMC”. We study various attack vectors for this construction and give a new attack vector that outperforms others in relevant settings.

Due to its very low number of multiplications, the design lends itself well to a large class of applications, especially when the depth does not matter but the total number of multiplications in the circuit dominates all aspects of the implementation. With a number of rounds which we deem secure based on our security analysis, we report on significant performance improvements in a representative use-case involving SNARKs.
Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2016 : Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Part I
Publication date2016
Pages191-219
ISBN (Print)978-3-662-53886-9
ISBN (Electronic)978-3-662-53887-6
DOIs
Publication statusPublished - 2016
Event22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016) - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016
Conference number: 22
http://www.asiacrypt2016.org/

Conference

Conference22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016)
Number22
CountryViet Nam
CityHanoi
Period04/12/201608/12/2016
Internet address
SeriesLecture Notes in Computer Science
Volume10031
ISSN0302-9743

Keywords

  • Distributed cryptography
  • Cryptanalysis
  • Block ciphers
  • Hash functions
  • Zero knowledge

Fingerprint Dive into the research topics of 'MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity'. Together they form a unique fingerprint.

Cite this