MiMC : Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. / Albrecht, Martin; Grassi, Lorenzo; Rechberger, Christian; Roy, Arnab; Tiessen, Tyge.

Advances in Cryptology – ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I. Vol. 10031 Springer, 2016. p. 191-219 (Lecture Notes in Computer Science; Vol. 10031).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

E-pub ahead of print

Standard

MiMC : Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. / Albrecht, Martin; Grassi, Lorenzo; Rechberger, Christian; Roy, Arnab; Tiessen, Tyge.

Advances in Cryptology – ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I. Vol. 10031 Springer, 2016. p. 191-219 (Lecture Notes in Computer Science; Vol. 10031).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Albrecht, M, Grassi, L, Rechberger, C, Roy, A & Tiessen, T 2016, MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. in Advances in Cryptology – ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I. vol. 10031, Lecture Notes in Computer Science, vol. 10031, Springer, pp. 191-219. https://doi.org/10.1007/978-3-662-53887-6_7

APA

Albrecht, M., Grassi, L., Rechberger, C., Roy, A., & Tiessen, T. (2016). MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. In Advances in Cryptology – ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I (Vol. 10031, pp. 191-219). (Lecture Notes in Computer Science; Vol. 10031). Springer. https://doi.org/10.1007/978-3-662-53887-6_7

Vancouver

Albrecht M, Grassi L, Rechberger C, Roy A, Tiessen T. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. In Advances in Cryptology – ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I. Vol. 10031. Springer. 2016. p. 191-219. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-662-53887-6_7

Author

Albrecht, Martin ; Grassi, Lorenzo ; Rechberger, Christian ; Roy, Arnab ; Tiessen, Tyge. / MiMC : Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. Advances in Cryptology – ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I. Vol. 10031 Springer, 2016. pp. 191-219 (Lecture Notes in Computer Science).

BibTeX

@inproceedings{f716b0971e844c538a78c5320f35c0b6,
title = "MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity",
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 bit-oriented 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)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):=x3F(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.",
author = "Martin Albrecht and Lorenzo Grassi and Christian Rechberger and Arnab Roy and Tyge Tiessen",
year = "2016",
month = "11",
day = "9",
doi = "10.1007/978-3-662-53887-6_7",
language = "English",
isbn = "978-3-662-53886-9",
volume = "10031",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "191--219",
booktitle = "Advances in Cryptology – ASIACRYPT 2016",

}

RIS

TY - GEN

T1 - MiMC

T2 - Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity

AU - Albrecht, Martin

AU - Grassi, Lorenzo

AU - Rechberger, Christian

AU - Roy, Arnab

AU - Tiessen, Tyge

PY - 2016/11/9

Y1 - 2016/11/9

N2 - 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 bit-oriented 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)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):=x3F(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.

AB - 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 bit-oriented 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)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):=x3F(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.

U2 - 10.1007/978-3-662-53887-6_7

DO - 10.1007/978-3-662-53887-6_7

M3 - Conference contribution

SN - 978-3-662-53886-9

VL - 10031

T3 - Lecture Notes in Computer Science

SP - 191

EP - 219

BT - Advances in Cryptology – ASIACRYPT 2016

PB - Springer

ER -