nach oben

Journal of Cryptographic Engineering

Erschienen in:

20.01.2019 | Regular Paper

A toolbox for software optimization of QC-MDPC code-based cryptosystems

verfasst von: Nir Drucker, Shay Gueron

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The anticipated emergence of quantum computers in the foreseeable future drives the cryptographic community to start considering cryptosystems, which are based on problems that remain intractable even with large-scale quantum computers. One example is the family of code-based cryptosystems that relies on the syndrome decoding problem. Recent work by Misoczki et al. (in: 2013 IEEE international symposium on information theory, pp 2069–2073, 2013. https://doi.org/10.1109/ISIT.2013.6620590) showed a variant of McEliece encryption which is based on quasi cyclic moderate density parity check (QC-MDPC) codes and has significantly smaller keys than the original McEliece encryption. It was followed by the newly proposed QC-MDPC-based cryptosystems CAKE (Barreto et al. in: IMA international conference on cryptography and coding, Springer, Berlin, pp 207–226, 2017) and Ouroboros (Deneuville et al. in Ouroboros: a simple, secure and efficient key exchange protocol based on coding theory, Springer, Cham, pp 18–34, 2017. https://doi.org/10.1007/978-3-319-59879-6_2). These motivate dedicated new software optimizations. This paper lists the cryptographic primitives that QC-MDPC cryptosystems commonly employ, studies their software optimizations on modern processors, and reports the achieved speedups. It also assesses methods for side channel protection of the implementations and their performance costs. These optimized primitives offer a useful toolbox that can be used, in various ways, by designers and implementers of QC-MDPC cryptosystems. Indeed, we applied our methods to generate a platform-specific additional implementation of “BIKE”—a QC-MDPC key encapsulation mechanism (KEM) proposal submitted to the NIST Post-Quantum Project (NIST:Post-Quantum Cryptography—call for proposals, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography, 2017). This gave a \(5\times \) speedup compared to the reference implementation.

Vorheriger Artikel Uniform Montgomery multiplier

Nächster Artikel A new class of irreducible pentanomials for polynomial-based multipliers in binary fields

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

Nur mit Berechtigung zugänglich

See Definition 1 for the relation between polynomials in \({\mathbb {F}}_{2}[x] \big / (x^r-1)\), vectors and strings.

a.k.a “side channel protected” and “Isochronous.”

For example, let \(X \sim U(0,3)\) be a uniform random variable and let \(Y = X \pmod {3}\). The distribution of Y is: \(P(Y=0)= \frac{1}{2}\), \(P(Y=\)\(1) = P(Y=2) = \frac{1}{4}\). Clearly, the “smaller” value Y=0 occurs more frequently than the others.

All the hash functions discussed in this paper are also collision resistant.

The code for the primitives can be found in [16]. In addition, we used these techniques to build the “additional” software implementation of BIKE (posted in the Additional implementation section of [17]). This Additional code was part of the official BIKE submission (together with the reference and optimized implementations of the BIKE team).

Intel^® Core 4770M CPU at 3.40 GHz Core^® i\(7-770\).

Aguilar, C., Blazy, O., Deneuville, J.C., Gaborit, P., Zémor, G.: Efficient encryption from random quasi-cyclic codes. IEEE Trans. Inf. Theory 64(5), 3927–3943 (2018)MathSciNetCrossRef

Aragon, N., Barreto, P.S.L.M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Gueron, S., Guneysu, T., Melchor, C.A., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J.P., Zémor, G.: BIKE: Bit Flipping Key Encapsulation. https://bikesuite.org/spec.html (2017). Retrieved 8 Jan 2019

Baldi, M., Chiaraluce, F., Garello, R.: On the usage of quasi-cyclic low-density parity-check codes in the McEliece cryptosystem. In: 2006 First International Conference on Communications and Electronics, pp. 305–310 (2006). https://doi.org/10.1109/CCE.2006.350824

Baldi, M., Chiaraluce, F., Garello, R., Mininni, F.: Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem. In: 2007 IEEE International Conference on Communications, pp. 951–956 (2007). https://doi.org/10.1109/ICC.2007.161

Baldi, M., Bodrato, M., Chiaraluce, F.: A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In: Security and Cryptography for Networks, pp. 246–262 (2008)

Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures, pp. 1–15. Springer, Berlin (2013)MATH

Barker, E.B., Kelsey, J.M.: SP 800-90A. Recommendation for random number generation using deterministic random bit generators. Tech. rep., NIST, Gaithersburg, MD, United States (2012)

Barreto, P.S., Gueron, S., Gueneysu, T., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J.P.: CAKE: Code-based Algorithm for Key Encapsulation. In: IMA International Conference on Cryptography and Coding, pp. 207–226. Springer (2017)

Barreto, P.S.L.M.: Private communication (2017)

10.

Bodrato, M.: Towards optimal Toom–Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0. In: Carlet, C., Sunar, B. (eds.) Arithmetic of Finite Fields, pp. 116–133. Springer, Berlin (2007)CrossRef

11.

Cayrel, P.L., Hoffmann, G., Persichetti, E.: Efficient Implementation of a CCA2-Secure Variant of McEliece Using Generalized Srivastava Codes, pp. 138–155. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-30057-8_9 CrossRefMATH

12.

Chaulet, J., Sendrier, N.: Worst case QC-MDPC decoder for McEliece cryptosystem. In: 2016 IEEE International Symposium on Information Theory (ISIT), pp. 1366–1370 (2016). https://doi.org/10.1109/ISIT.2016.7541522

13.

Cook, S.A., Aanderaa, S.O.: On the minimum computation time of functions. Trans. Am. Math. Soc. 142, 291–314 (1969)MathSciNetCrossRef

14.

Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 157–174. Springer (2001)

15.

Deneuville, J.C., Gaborit, P., Zémor, G.: Ouroboros: A Simple, Secure and Efficient Key Exchange Protocol Based on Coding Theory, pp. 18–34. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_2 CrossRefMATH

16.

Drucker, N., Gueron, S.: A-toolbox-for-software-optimization-of-qc-mdpc-code-based-cryptosystems. https://github.com/Shay-Gueron/A-toolbox-for-software-optimization-of-QC-MDPC-code-based-cryptosystems (2017). Accessed 1 Jan 2019

17.

Drucker, N., Gueron, S.: Additional implementation of BIKE. https://bikesuite.org/additional.html (2018). Retrieved 8 Jan 2019

18.

Faugère, J.C., Otmani, A., Perret, L., de Portzamparc, F., Tillich, J.P.: Structural cryptanalysis of McEliece schemes with compact keys. Des. Codes Cryptogr. 79(1), 87–112 (2016). https://doi.org/10.1007/s10623-015-0036-z MathSciNetCrossRefMATH

19.

Gallager, R.: Low-density parity-check codes. IRE Trans. Inf. Theory 8(1), 21–28 (1962). https://doi.org/10.1109/TIT.1962.1057683 MathSciNetCrossRefMATH

20.

Gueron, S.: Intel’s new AES instructions for enhanced performance and security. In: FSE, vol. 5665, pp. 51–66. Springer (2009)

21.

Gueron, S.: Intel® advanced encryption standard (AES) new instructions set Rev. 3.01. Intel Corporation. Intel Corporation. https://www.intel.com.bo/content/dam/doc/white-paper/advanced-encryption-standard-new-instructions-set-paper.pdf (2010)

22.

Gueron, S.: A j-lanes tree hashing mode and j-lanes SHA-256. J. Inf. Secur. 4(01), 7 (2013)

23.

Gueron, S.: Parallelized hashing via j-lanes and j-pointers tree modes, with applications to SHA-256. J. Inf. Secur. 5(03), 91 (2014)

24.

Gueron, S., Kounavis, M.: Efficient implementation of the Galois Counter Mode using a carry-less multiplier and a fast reduction algorithm. Inf. Process. Lett. 110(14), 549–553 (2010). https://doi.org/10.1016/j.ipl.2010.04.011 MathSciNetCrossRefMATH

25.

Gueron, S., Kounavis, M.E.: Intel® carry-less multiplication instruction and its usage for computing the GCM mode. White Paper (2010)

26.

Gueron, S., Krasnov, V.: Simultaneous hashing of multiple messages. J. Inf. Secur. 3(04), 319 (2012)

27.

Gueron, S., Schlieker, F.: Speeding up R-LWE Post-quantum Key Exchange, pp. 187–198. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-47560-8_12 CrossRef

28.

Guo, Q., Johansson, T., Stankovski, P.: A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors, pp. 789–815. Springer, Berlin (2016). https://doi.org/10.1007/978-3-662-53887-6_9 CrossRefMATH

29.

Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2010)MATH

30.

Intel Corporation.: Intel\(^{\textregistered }\) Architecture Instruction Set Extensions and Future Features Programming Reference. https://software.HrBintel.com/sites/default/files/managed/c5/15/architecture-instructiHrBon-set-extensionsprogramming-reference.pdf (2017). Retrieved 8 Jan 2019

31.

Intel Corporation.: Intel Intrinsics Guide. https://software.intel.com/sites/landingpage/IntrinsicsGuide/ (2018). Retrieved 8 Jan 2019

32.

Jovanovic, B.D., Levy, P.S.: A look at the rule of three. Am. Stat. 51(2), 137–139 (1997)

33.

Kabatianskii, G., Krouk, E., Smeets, B.: A Digital Signature Scheme Based on Random Error-Correcting Codes, pp. 161–167. Springer, Berlin (1997). https://doi.org/10.1007/BFb0024461 CrossRefMATH

34.

Karatsuba, A., Ofman, Y.: Multiplication of multidigit numbers on automata. Sov. Phys. Dokl. 7, 595 (1963)

35.

Guido, B., Joan, D., Michaël, P., Gilles, V. A., Ronny, V.K.: Keccak Code Package (KCP). https://github.com/gvanas/KeccakCodePackage (2017). Retrieved 30 Nov 2017

36.

Maurich, I.V., Oder, T., Güneysu, T.: Implementing QC-MDPC McEliece encryption. ACM Trans. Embed Comput. Syst. 14(3), 44:1–44:27 (2015). https://doi.org/10.1145/2700102 CrossRef

37.

McEliece, R.: A public-key cryptosystem based on algebraic. Coding Thv 4244, 114–116 (1978)

38.

Misoczki, R., Barreto, P.S.L.M.: Compact McEliece Keys from Goppa Codes, pp. 376–392. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-05445-7_4 CrossRefMATH

39.

Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. Cryptology ePrint Archive, Report 2012/409. http://eprint.iacr.org/2012/409 (2012). Retrieved 8 Jan 2019

40.

Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In: 2013 IEEE International Symposium on Information Theory, pp. 2069–2073 (2013). https://doi.org/10.1109/ISIT.2013.6620590

41.

Monico, C., Rosenthal, J., Shokrollahi, A.: Using low density parity check codes in the McEliece cryptosystem. In: 2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060), IEEE, p. 215 (2000). https://doi.org/10.1109/ISIT.2000.866513

42.

NIST.: NIST:Post-Quantum Cryptography—call for proposals. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography (2017). Retrieved 1 Nov 2018

43.

OpenSSL.: OpenSSL, Commit: 2dbfa8444bdf7669a54006c4a83d1e60ba374528. https://github.com/openssl/openssl (2017). Retrieved 30 Sept 2017

44.

Phesso, A., Tillich, J.P.: An Efficient Attack on a Code-Based Signature Scheme, pp. 86–103. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_7 CrossRefMATH

45.

Gaudry, P., Brent, R., Zimmermann, P., Thomé, E.: gf2x-1.2. https://gforge.inria.fr/projects/gf2x/ (2017). Retrieved 8 Jan 2019

46.

Shoup, V.: Number Theory C++ Library (NTL) version 10.5.0. http://www.shoup.net/ntl (2017). Retrieved 30 Nov 2017

47.

Stern, J.: A new identification scheme based on syndrome decoding. In: Annual International Cryptology Conference, pp. 13–21. Springer (1993)

48.

Toom, A.L.: The complexity of a scheme of functional elements realizing the multiplication of integers. Sov. Math. Dokl. 3, 714–716 (1963)MATH

Titel: A toolbox for software optimization of QC-MDPC code-based cryptosystems
verfasst von: Nir Drucker
Shay Gueron
Publikationsdatum: 20.01.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 4/2019
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-018-00200-4

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"

Weitere Artikel der Ausgabe 4/2019

Kite attack: reshaping the cube attack for a flexible GPU-based maxterm search

RNS Montgomery reduction algorithms using quadratic residuosity

Physical model of sensitive data leakage from PC-based cryptographic systems

A new class of irreducible pentanomials for polynomial-based multipliers in binary fields

Uniform Montgomery multiplier

Fast unified elliptic curve point multiplication for NIST prime curves on FPGAs