nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity

verfasst von : Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, Tyge Tiessen

Erschienen in: Advances in Cryptology – ASIACRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \(\text {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) := 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Efficient and Provable White-Box Primitives

Nächstes Kapitel Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks

Nur mit Berechtigung zugänglich

This claim is supported by our experiments. In particular, for a field \(\mathbb {F}_{2^n}\) and using \(x^3\) as permutation, we observed:

after 1 round, all terms appear (percentage: 100 \(\%\));
after 2 round, 8 terms appear instead of 10 (percentage: 80 \(\%\));
after 3 round, 19 terms appear instead of 28 (percentage: 67.86 \(\%\));
after 4 round, 54 terms appear instead of 82 (percentage: 65.85 \(\%\));
after 5 round, 161 terms appear instead of 244 (percentage: 66 \(\%\));
after 6 round, 531 terms appear instead of 730 (percentage: 72.74 \(\%\));

and so on, where the percentage of the non-null terms continues to grow for the next rounds. For example, for the particular field \(GF(2^{17})\), after 10 rounds almost all the terms are non-zero.

For example, suppose that \(t\ge 8\). The idea is to precompute \(g_0\), \(g_1\) (defined as before) and also \(g_2 :={ (g_1)}^4 \cdot g_1\). Thus, in the for loop \(0 \le i \le \lfloor t/4 \rfloor \) and \(A \leftarrow A^8 \cdot g_2\). Finally, after the for loop and before the if-statement, one has to take care of the case t mod \(4 \ne 0\).

Actually, the best result is obtained for \(t=6\), that is for the exponent 63. But since \(\gcd (63, 2^{129}-1)=7\), the round function defined using the exponent 63 is not a permutation.

[AÅBL12]

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 CrossRef

[ADL+08]

Arbitman, Y., Dogon, G., Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: Swifftx: a proposal for the SHA-3 standard. Submission to NIST (2008)

[AGR+16]

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

[ÅHJM11]

Å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)CrossRef

[Ajt96]

Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, May 1996, pp. 99–108. ACM Press (1996)

[ARS+15]

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

[ARS+16a]

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

[ARS+16b]

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/

[BBL+15]

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

[BCG+14]

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)

[BDPA08]

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 CrossRef

[BFS14]

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)MATHCrossRef

[BKW93]

Becker, T., Kredel, H., Weispfenning, V.: Gröbner Bases: A Computational Approach to Commutative Algebra. Springer, New York (1993)MATHCrossRef

[BMP13]

Boyar, J., Matthews, P., Peralta, R.: Logic minimization techniques with applications to cryptology. J. Cryptology 26(2), 280–312 (2013)MathSciNetMATHCrossRef

[BP12]

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)

[BSCG+13]

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 CrossRef

[BSS+13]

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

[Can97]

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)

[CCF+16]

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/

[CFH+15]

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)

[CGP+12]

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 CrossRef

[CP08]

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 CrossRef

[DPVAR00]

Daemen, J., Peeters, M., Van Assche, G., Rijmen, V.: Nessie proposal: Noekeon. In: First Open NESSIE Workshop (2000)

[DWBV+96]

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)CrossRef

[ENI13]

ENISA. Algorithms, key sizes and parameters report – 2013 recommendations. Technical report, European Union Agency for Network and Information Security, October 2013

[GLSV14]

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

[GP97]

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 CrossRef

[GRR+16]

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/

[Has00]

Hasan, M.A.: Look-up table-based large finite field multiplication in memory constrained cryptosystems. IEEE Trans. Comput. 49(7), 749–758 (2000)MathSciNetCrossRef

[HMV93]

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 CrossRef

[JK97]

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 CrossRef

[KA98]

Koc, C.K., Acar, T.: Montgomery multiplication in GF(2k). Des. Codes Crypt. 14(1), 57–69 (1998)MathSciNetMATHCrossRef

[KN95]

Knudsen, L.R., Nyberg, K.: Provable security against a differential attack. J. Crypt. 8(1), 27–37 (1995)MathSciNetMATH

[KR11]

Knudsen, L.R., Robshaw, M.: The Block Cipher Companion. Information Security and Cryptography. Springer, Heidelberg (2011)MATHCrossRef

[Lab]

SCIPR lab. libsnark. https://github.com/scipr-lab/libsnark

[LMPR08]

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 CrossRef

[LMS13]

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)

[MJSC16]

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 CrossRef

[MVO96]

Menezes, A.J., Vanstone, S.A., Van Oorschot, P.C.: Handbook of Applied Cryptography, 1st edn. CRC Press Inc., Boca Raton (1996)MATHCrossRef

[NIS14]

NIST. DRAFT FIPS PUB 202, SHA-3 standard: permutation-based hash and extendable-output functions (2014)

[NR97]

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)

[Nyb94]

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 CrossRef

[PH78]

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)MathSciNetMATHCrossRef

[PHGR16]

Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. Commun. ACM 59(2), 103–112 (2016)CrossRef

[Sho]

Shoup, V.: Number theory library 5.5.2 (NTL) for C++. http://www.shoup.net/ntl/

[Sto85]

Stoss, H.-J.: The complexity of evaluating interpolation polynomials. Theor. Comput. Sci. 41, 319–323 (1985)MathSciNetMATHCrossRef

Titel: MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity
verfasst von: Martin Albrecht
Lorenzo Grassi
Christian Rechberger
Arnab Roy
Tyge Tiessen
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – ASIACRYPT 2016
Print ISBN: 978-3-662-53886-9

Electronic ISBN: 978-3-662-53887-6

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53887-6_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner