Top

International Journal of Information Security

Published in:

09-12-2017 | Regular Contribution

Comparing apples with apples: performance analysis of lattice-based authenticated key exchange protocols

Authors: Nina Bindel, Johannes Buchmann, Susanne Rieß

Published in: International Journal of Information Security | Issue 6/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In view of the expected cryptanalysis (of both classical and quantum adversaries), it is important to find alternatives for currently used cryptographic primitives. In the past years, several authenticated key exchange protocols (AKE) that base their security on presumably quantum hard problems, such as lattice-based AKEs, were proposed. Since very different proposals for generic AKEs as well as direct AKEs, i.e., protocols directly based on lattice-based problems without additional authentication, exist, the performance of lattice-based AKEs is not evaluated and compared thoroughly. In particular, it is an open question whether the direct constructions are more efficient than generic approaches as it is often the case for other primitives. In this paper, we fill this gap. We compare existing lattice-based authenticated key exchange protocols, generic and direct. Therefore, we first find the most efficient suitable primitives to instantiate the generic protocols. Afterward, we choose parameters for each AKE yielding approximately 100 or 192 bits of security. We implement all protocols using the same libraries and compare the resulting performance. We find that our instantiation of the AKE by Peikert (PQCrypto, 2014) is the most efficient lattice-based AKE. Particularly, it is faster than the direct AKE by Zhang et al. (EUROCRYPT, 2015).

previous article A framework for estimating information security risk assessment method completeness

next article Talos: no more ransomware victims with formal methods

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

In 2015, the NSA announced to start changing from classical to post-quantum cryptography [35]. In 2016, NIST started its preparations for its upcoming post-quantum standardization challenge [34].

We do not consider the AKE proposed in [17] since the authors already instantiate their protocol with NTRU-based primitives and compare it to ZZDSD.

Our software is available on https://www.cdc.informatik.tu-darmstadt.de/cdc/personen/nina-bindel.

We do not consider the running times of the IND-CCA secure KEM based on NewHope in this section since the FOT is a generic transformation which can be applied to the other KEMs as well. Hence, it is enough to compare only the IND-CPA secure KEMs.

In our implementation, we instantiate the hash function H by first using \(\mathsf {SHA256}\) and then using its random output bit string for sampling from \(D_{\sigma _3}^n\)

Akleylek, S., Bindel, N., Buchmann, J., Krämer, J., Azzurra Marson, G.: An efficient lattice-based signature scheme with provably secure instantiation. In: Progress in Cryptology—AFRICACRYPT 2016—8th International Conference on Cryptology in Africa, Fes, Morocco, 3–15 April 2016, Proceedings, pp. 44–60 (2016)

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef

Alkim, E., Bindel, N., Buchmann, J., Özgür Dagdelen, Eaton, E., Gutoski, G., Krämer, J., Pawlega, F.: Revisiting TESLA in the quantum random oracle model. Cryptology ePrint Archive, Report 2015/755 (2015). http://eprint.iacr.org/2015/755

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange—a new hope. In: 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, 10–12 August 2016, pp. 327–343 (2016)

Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: Benaloh, J. (ed.) CT-RSA 2014, LNCS, vol. 8366, pp. 28–47. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-04852-9_2 CrossRef

Bansarkhani, R.E., Buchmann, J.: Improvement and efficient implementation of a lattice-based signature scheme. In: Lange et al. [30], pp. 48–67. https://doi.org/10.1007/978-3-662-43414-7_3 CrossRef

Barreto, P., Longa, P., Naehrig, M., Ricardini, J., Zanon, G.: Sharper ring-lwe signatures. Cryptology ePrint Archive, Report 2016/1026 (2016). http://eprint.iacr.org/2016/1026

Bellare, M., Rogaway, P.: Entity authentication and key distribution. In: Stinson, D.R. (ed.) CRYPTO’93, LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)

Bernstein, D.J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., Wilcox-O’Hearn, Z.: SPHINCS: practical stateless hash-based signatures. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I, LNCS, vol. 9056, pp. 368–397. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_15

10.

Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: 2015 IEEE Symposium on Security and Privacy, pp. 553–570. IEEE Computer Society Press, San Jose, CA, USA (2015). https://doi.org/10.1109/SP.2015.40

11.

Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011, LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011)CrossRef

12.

Buchmann, J., Cabarcas, D., Göpfert, F., Hülsing, A., Weiden, P.: Discrete ziggurat: a time-memory trade-off for sampling from a Gaussian distribution over the integers. In: Lange et al. [30], pp. 402–417. https://doi.org/10.1007/978-3-662-43414-7_20 CrossRef

13.

Buchmann, J.A., Dahmen, E., Hülsing, A.: XMSS: a practical forward secure signature scheme based on minimal security assumptions. In: Yang, B. (ed.) Post-Quantum Cryptography—4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29–December 2 2011. Proceedings, Lecture Notes in Computer Science, vol. 7071, pp. 117–129. Springer (2011)

14.

Canetti, R., Krawczyk, H.: Security analysis of ike’s signature-based key-exchange protocol. In: Advances in Cryptology—CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, 18-22 August 2002, Proceedings, pp. 143–161 (2002)

15.

Chen, A.I.T., Chen, M.S., Chen, T.R., Cheng, C.M., Ding, J., Kuo, E.L.H., Lee, F.Y.S., Yang, B.Y.: SSE implementation of multivariate PKCs on modern x86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009, LNCS, vol. 5747, pp. 33–48. Springer, Heidelberg (2009)

16.

Dagdelen, Ö., Bansarkhani, R.E., Göpfert, F., Güneysu, T., Oder, T., Pöppelmann, T., Sánchez, A.H., Schwabe, P.: High-speed signatures from standard lattices. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014, LNCS, vol. 8895, pp. 84–103. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-319-16295-9_5

17.

del Pino, R., Lyubashevsky, V., Pointcheval, D.: The Whole is Less Than the Sum of Its Parts: Constructing More Efficient Lattice-Based AKEs, pp. 273–291. Springer International Publishing, Cham (2016)

18.

Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (Proposed Standard) (2008). http://www.ietf.org/rfc/rfc5246.txt. Updated by RFCs 5746, 5878, 6176

19.

Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 05, LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005)CrossRef

20.

Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report 2012/688 (2012). http://eprint.iacr.org/2012/688

21.

Ducas, L.: Accelerating bliss: the geometry of ternary polynomials. Cryptology ePrint Archive, Report 2014/874 (2014). http://eprint.iacr.org/2014/874

22.

Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay J.A. (eds.) CRYPTO 2013, Part I, LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_3 CrossRef

23.

Dwarakanath, N.C., Galbraith, S.D.: Sampling from discrete gaussians for lattice-based cryptography on a constrained device. Appl. Algebra Eng. Commun. Comput. 25(3), 159–180 (2014)MathSciNetCrossRef

24.

Fujioka, A., Suzuki, K., Xagawa, K., Yoneyama, K.: Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism. In: Chen, K., Xie, Q., Qiu, W., Li, N., Tzeng, W.G. (eds.) ASIACCS 13, pp. 83–94. ACM Press, Hangzhou (2013)

25.

Fujioka, A., Suzuki, K., Xagawa, K., Yoneyama, K.: Strongly secure authenticated key exchange from factoring, codes, and lattices. Des. Codes Cryptogr. 76(3), 469–504 (2015)MathSciNetCrossRef

26.

Fujisaki, E., Okamoto, T.: How to enhance the security of public-key encryption at minimum cost. In: Imai, H., Zheng, Y. (eds.) PKC’99, LNCS, vol. 1560, pp. 53–68. Springer, Heidelberg (1999)CrossRef

27.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press, Victoria (2008)

28.

Güneysu, T., Lyubashevsky, V., Pöppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: Prouff, E., Schaumont, P. (eds.) CHES 2012, LNCS, vol. 7428, pp. 530–547. Springer, Heidelberg (2012)CrossRef

29.

Katz, J., Lindell, Y.: Introduction to Modern Cryptography (Chapman & Hall/Crc Cryptography and Network Security Series). Chapman & Hall/CRC, Boca Raton (2007)

30.

Krawczyk, H.: HMQV: a high-performance secure Diffie–Hellman protocol. In: Shoup, V. (ed.) CRYPTO 2005, LNCS, vol. 3621, pp. 546–566. Springer, Heidelberg (2005)CrossRef

31.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010, LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010)

32.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43 (2013)MathSciNetCrossRef

33.

Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-LWE cryptography. In: Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 26–30 May 2013. Proceedings, pp. 35–54 (2013)

34.

National Institute of Standards and Technology (NIST): Post-quantum cryptography: Nist’s plan for the future (2015)

35.

National Security Agency (NSA): Cryptography today. https://www.nsa.gov/ia/programs/suiteb_cryptography/ (2015)

36.

Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Advances in Cryptology—CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, 5–19 August 2010. Proceedings, pp. 80–97 (2010)

37.

Peikert, C.: Lattice cryptography for the internet. In: Post-Quantum Cryptography—6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, 1–3 October 2014. Proceedings, pp. 197–219 (2014)

38.

Peikert, C.: A decade of lattice cryptography. Found. Trends Theor. Comput. Sci. 10(4), 283–424 (2016)MathSciNetCrossRef

39.

Petzoldt, A., Chen, M., Yang, B., Tao, C., Ding, J.: Design principles for HFEv- based multivariate signature schemes. In: Iwata, T., Cheon, J.H.(eds.) Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29–December 3, 2015, Proceedings, Part I, Lecture Notes in Computer Science, vol. 9452, pp. 311–334. Springer (2015). https://doi.org/10.1007/978-3-662-48797-6 MATH

40.

Wolchok, S., Wustrow, E., Halderman, J.A., Prasad, H.K., Kankipati, A., Sakhamuri, S.K., Yagati, V., Gonggrijp, R.: Security analysis of India’s electronic voting machines. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM CCS 10, pp. 1–14. ACM Press, Chicago (2010)

41.

Zhang, J., Zhang, Z., Ding, J., Snook, M., Dagdelen, Ö.: Authenticated key exchange from ideal lattices. In: Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26–30 April 2015, Proceedings, Part II, pp. 719–751 (2015)

Title: Comparing apples with apples: performance analysis of lattice-based authenticated key exchange protocols
Authors: Nina Bindel
Johannes Buchmann
Susanne Rieß
Publication date: 09-12-2017
Publisher: Springer Berlin Heidelberg
Published in: International Journal of Information Security / Issue 6/2018
Print ISSN: 1615-5262
Electronic ISSN: 1615-5270
DOI: https://doi.org/10.1007/s10207-017-0397-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2018

Optimization algorithm for k-anonymization of datasets with low information loss

Talos: no more ransomware victims with formal methods

OnionDNS: a seizure-resistant top-level domain

DomainProfiler: toward accurate and early discovery of domain names abused in future

A framework for estimating information security risk assessment method completeness

Optimal noise functions for location privacy on continuous regions

Premium Partner