Paper 2016/687

Ciphers for MPC and FHE

Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner

Abstract

Designing an efficient cipher was always a delicate balance between linear and non-linear operations. This goes back to the design of DES, and in fact all the way back to the seminal work of Shannon. Here we focus, for the first time, on an extreme corner of the design space and initiate a study of symmetric-key primitives that minimize the multiplicative size and depth of their descriptions. This is motivated by recent progress in practical instantiations of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where linear computations are, compared to non-linear operations, essentially ``free''. We focus on the case of a block cipher, and propose the family of block ciphers ``LowMC'', beating all existing proposals with respect to these metrics. As examples, we give concrete instatiations for 80-bit, 128-bit, and 256-bit security. We sketch several applications for such ciphers and give implementation comparisons suggesting that when encrypting larger amounts of data the new design strategy translates into improvements in computation and communication complexity by up to a factor of 5 compared to AES-128, which incidentally is one of the most competitive classical designs. Furthermore, we identify cases where ``free XORs'' can no longer be regarded as such but represent a bottleneck, hence refuting this commonly held belief with a practical example.

Note: Compared to the conference version, this paper includes among others (1) updated security analysis and round formula taking recent cryptanalysis into account (LowMC v2). (2) more examples of concrete instantiations, optimizing for metrics such as ANDdepth, #ANDs/bits, and #ANDs separately, incl. concrete instances with 256-bit security. (3) updated benchmarks for LowMCv2 parametersets.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in Eurocrypt 2015
Keywords
block ciphermultiplicative complexitymultiplicative depthsecure multiparty computationfully homomorphic encryption
Contact author(s)
christian rechberger @ groestl info
History
2016-07-12: received
Short URL
https://ia.cr/2016/687
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/687,
      author = {Martin Albrecht and Christian Rechberger and Thomas Schneider and Tyge Tiessen and Michael Zohner},
      title = {Ciphers for MPC and FHE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/687},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/687}},
      url = {https://eprint.iacr.org/2016/687}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.