×

MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. (English) Zbl 1404.94035

Cheon, Jung Hee (ed.) et al., 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. Berlin: Springer (ISBN 978-3-662-53886-9/pbk; 978-3-662-53887-6/ebook). Lecture Notes in Computer Science 10031, 191-219 (2016).
Summary: 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 [I. Dinur et al., Lect. Notes Comput. Sci. 9453, 535–560 (2015; Zbl 1382.94092)], 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 \(\mathrm{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 [L. R. Knudson and K. Nyberg [J. Cryptography 8, No. 1, 27–37 (1995; Zbl 0817.94016)]. The mapping \(F(x) := x^3\) 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.
For the entire collection see [Zbl 1349.94005].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abdelraheem, M.A., Ågren, M., Beelen, P., Leander, G.: On the distribution of linear biases: three instructive examples. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 50–67. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-32009-5_4 · Zbl 1294.94029 · doi:10.1007/978-3-642-32009-5_4
[2] Arbitman, Y., Dogon, G., Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: Swifftx: a proposal for the SHA-3 standard. Submission to NIST (2008)
[3] Albrecht, M., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. Cryptology ePrint Archive, Report 2016/492 (2016). http://eprint.iacr.org/2016/492 · Zbl 1404.94035
[4] Ågren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: a new version of grain-128 with optional authentication. IJWMC 5(1), 48–59 (2011) · doi:10.1504/IJWMC.2011.044106
[5] Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, May 1996, pp. 99–108. ACM Press (1996) · Zbl 0921.11071 · doi:10.1145/237814.237838
[6] Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5_17 · Zbl 1370.94477 · doi:10.1007/978-3-662-46800-5_17
[7] Albrecht, M., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. Cryptology ePrint Archive, Report 2016/687 (2016). http://eprint.iacr.org/2016/687 · Zbl 1370.94477
[8] Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. Cryptology ePrint Archive, Report 2016 (2016). http://eprint.iacr.org/ · Zbl 1370.94477
[9] Banerjee, A., Brenner, H., Leurent, G., Peikert, C., Rosen, A.: SPRING: fast pseudorandom functions from rounded ring products. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 38–57. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46706-0_3 · Zbl 1382.94056 · doi:10.1007/978-3-662-46706-0_3
[10] Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, 18–21 May 2014, pp. 459–474. IEEE Computer Society (2014) · doi:10.1109/SP.2014.36
[11] Bertoni, G., Daemen, J., Peeters, M., Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-78967-3_11 · Zbl 1149.94304 · doi:10.1007/978-3-540-78967-3_11
[12] Bardet, M., Faugère, J.-C., Salvy, B.: On the complexity of the F5 Gröbner basis Algorithm. J. Symb. Comput. 70, 49–70 (2014) · Zbl 1328.68319 · doi:10.1016/j.jsc.2014.09.025
[13] Becker, T., Kredel, H., Weispfenning, V.: Gröbner Bases: A Computational Approach to Commutative Algebra. Springer, New York (1993) · Zbl 0772.13010 · doi:10.1007/978-1-4612-0913-3
[14] Boyar, J., Matthews, P., Peralta, R.: Logic minimization techniques with applications to cryptology. J. Cryptology 26(2), 280–312 (2013) · Zbl 1279.94056 · doi:10.1007/s00145-012-9124-7
[15] Boyar, J., Peralta, R.: A small depth-16 circuit for the AES S-box. In: Gritzalis, D., Furnell, S., Theoharidou, M. (eds.) Information Security and Privacy Conference (SEC). IFIP Advances in Information and Communication Technology, vol. 376, pp. 287–298. Springer, Heidelberg (2012) · doi:10.1007/978-3-642-30436-1_24
[16] Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40084-1_6 · Zbl 1317.68050 · doi:10.1007/978-3-642-40084-1_6
[17] Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). http://eprint.iacr.org/2013/404 · Zbl 1382.94059
[18] Canteaut, A.: Differential cryptanalysis of feistel ciphers and differentially \[ \delta \] -uniform mappings. In: Workshop on Selected Areas in Cryptography, SAC 1997, Workshop Record, pp. 172–184 (1997)
[19] Canteaut, A., Carpov, S., Fontaine, C., Lepoint, T., Naya-Plasencia, M., Paillier, P., Sirdey, R.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. To appear in Proceedings of FSE 2016, available on Cryptology ePrint Archive, Report 2015/113 (2016). http://eprint.iacr.org/ · Zbl 1387.94071
[20] Costello, C., Fournet, C., Howell, J., Kohlweiss, M., Kreuter, B., Naehrig, M., Parno, B., Zahur, S.: Geppetto: versatile verifiable computation. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, pp. 253–270. IEEE Computer Society (2015) · doi:10.1109/SP.2015.23
[21] Carlet, C., Goubin, L., Prouff, E., Quisquater, M., Rivain, M.: Higher-order masking schemes for S-boxes. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 366–384. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-34047-5_21 · Zbl 1312.94037 · doi:10.1007/978-3-642-34047-5_21
[22] Cannière, C., Preneel, B.: Trivium. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 244–266. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-68351-3_18 · Zbl 1285.94054 · doi:10.1007/978-3-540-68351-3_18
[23] Daemen, J., Peeters, M., Van Assche, G., Rijmen, V.: Nessie proposal: Noekeon. In: First Open NESSIE Workshop (2000)
[24] De Win, E., Bosselaers, A., Vandenberghe, S., De Gersem, P., Vandewalle, J.: A fast software implementation for arithmetic operations in GF(2n). In: Kim, K., Matsumoto, T. (eds.) Advances in Cryptology – ASIACRYPT ’96. Lecture Notes in Computer Science, vol. 1163, pp. 65–76. Springer, Berlin Heidelberg (1996) · Zbl 1005.94535 · doi:10.1007/BFb0034836
[25] ENISA. Algorithms, key sizes and parameters report – 2013 recommendations. Technical report, European Union Agency for Network and Information Security, October 2013
[26] Grosso, V., Leurent, G., Standaert, F.-X., Varıcı, K.: LS-designs: bitslice encryption for efficient masked software implementations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 18–37. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46706-0_2 · Zbl 1382.94111 · doi:10.1007/978-3-662-46706-0_2
[27] Guajardo, J., Paar, C.: Efficient algorithms for elliptic curve cryptosystems. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 342–356. Springer, Heidelberg (1997). doi: 10.1007/BFb0052247 · Zbl 0937.94009 · doi:10.1007/BFb0052247
[28] Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.: MPC-friendly symmetric key primitives. Cryptology ePrint Archive, Report 2016 (2016). http://eprint.iacr.org/
[29] Hasan, M.A.: Look-up table-based large finite field multiplication in memory constrained cryptosystems. IEEE Trans. Comput. 49(7), 749–758 (2000) · doi:10.1109/12.863045
[30] Harper, G., Menezes, A., Vanstone, S.: Public-key cryptosystems with very small key lengths. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 163–173. Springer, Heidelberg (1993). doi: 10.1007/3-540-47555-9_14 · Zbl 0787.94017 · doi:10.1007/3-540-47555-9_14
[31] Jakobsen, T., Knudsen, L.R.: The interpolation attack on block ciphers. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 28–40. Springer, Heidelberg (1997). doi: 10.1007/BFb0052332 · Zbl 1385.94047 · doi:10.1007/BFb0052332
[32] Koc, C.K., Acar, T.: Montgomery multiplication in GF(2k). Des. Codes Crypt. 14(1), 57–69 (1998) · Zbl 0887.11054 · doi:10.1023/A:1008208521515
[33] Knudsen, L.R., Nyberg, K.: Provable security against a differential attack. J. Crypt. 8(1), 27–37 (1995) · Zbl 0817.94016
[34] Knudsen, L.R., Robshaw, M.: The Block Cipher Companion. Information Security and Cryptography. Springer, Heidelberg (2011) · Zbl 1243.68010 · doi:10.1007/978-3-642-17342-4
[35] SCIPR lab. libsnark. https://github.com/scipr-lab/libsnark
[36] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-71039-4_4 · Zbl 1154.68403 · doi:10.1007/978-3-540-71039-4_4
[37] Lebreton, R., Mehrabi, E., Schost, É.: On the complexity of solving bivariate systems: the case of non-singular solutions. In: Kauers, M. (ed.) International Symposium on Symbolic and Algebraic Computation, ISSAC’13, Boston, MA, USA, 26–29 June 2013, pp. 251–258. ACM (2013) · Zbl 1360.68941 · doi:10.1145/2465506.2465950
[38] Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49890-3_13 · Zbl 1384.94086 · doi:10.1007/978-3-662-49890-3_13
[39] Menezes, A.J., Vanstone, S.A., Van Oorschot, P.C.: Handbook of Applied Cryptography, 1st edn. CRC Press Inc., Boca Raton (1996) · Zbl 0868.94001 · doi:10.1201/9781439821916
[40] NIST. DRAFT FIPS PUB 202, SHA-3 standard: permutation-based hash and extendable-output functions (2014)
[41] Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, pp. 458–467. IEEE Computer Society (1997) · doi:10.1109/SFCS.1997.646134
[42] Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994). doi: 10.1007/3-540-48285-7_6 · Zbl 0951.94510 · doi:10.1007/3-540-48285-7_6
[43] Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106–110 (1978) · Zbl 0375.68023 · doi:10.1109/TIT.1978.1055817
[44] Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. Commun. ACM 59(2), 103–112 (2016) · doi:10.1145/2856449
[45] Shoup, V.: Number theory library 5.5.2 (NTL) for C++. http://www.shoup.net/ntl/
[46] Stoss, H.-J.: The complexity of evaluating interpolation polynomials. Theor. Comput. Sci. 41, 319–323 (1985) · Zbl 0601.65006 · doi:10.1016/0304-3975(85)90078-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.