Projects per year
Abstract
We explore cryptographic primitives with low multiplicative complexity. This is motivated by recent progress in practical applications of secure multiparty computation (MPC), fully homomorphic encryption (FHE), and zeroknowledge proofs (ZK) where primitives from symmetric cryptography are needed and where linear computations are, compared to nonlinear 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/ZKprotocols 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 KnudsenNyberg 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 usecase involving SNARKs.
Surprisingly, albeit many MPC/FHE/ZKprotocols 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 KnudsenNyberg 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 usecase involving SNARKs.
Original language  English 

Title of host publication  Advances in Cryptology – ASIACRYPT 2016 
Subtitle of host publication  22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 48, 2016, Proceedings, Part I 
Publisher  Springer 
Pages  191219 
Number of pages  29 
Volume  10031 
ISBN (Electronic)  9783662538876 
ISBN (Print)  9783662538869 
DOIs  
Publication status  Epub ahead of print  9 Nov 2016 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer Berlin Heidelberg 
Volume  10031 
ISSN (Print)  03029743 
Projects
 1 Finished

Multilinear Maps in Cryptography
Paterson, K.
Eng & Phys Sci Res Council EPSRC
31/01/14 → 30/01/17
Project: Research