Post-quantum secure remote password protocol from RLWE problem. (English) Zbl 1426.94102
Chen, Xiaofeng (ed.) et al., Information security and cryptology. 13th international conference, Inscrypt 2017, Xi’an, China, November 3–5, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10726, 99-116 (2018).
Summary: Secure remote password (SRP) protocol is an augmented password-based authenticated key exchange (PAKE) protocol based on discrete logarithm problem (DLP) with various attractive security features. Compared with basic PAKE protocols, SRP does not require server to store user’s password and user does not send password to server to authenticate. These features are desirable for secure client-server applications. SRP has gained extensive real-world deployment, including Apple iCloud, 1Password etc. However, with the advent of quantum computer and Shor’s algorithm, classic DLP-based public key cryptography algorithms are no longer secure, including SRP. Motivated by importance of SRP and threat from quantum attacks, we propose a RLWE-based SRP protocol (RLWE-SRP) which inherit advantages from SRP and elegant design from RLWE key exchange. We also present parameter choice and efficient portable \(\mathrm{C++}\) implementation of RLWE-SRP. Implementation of our 209-bit secure RLWE-SRP is more than 3x faster than 112-bit secure original SRP protocol, 5.5x faster than 80-bit secure J-PAKE and 14x faster than two 184-bit secure RLWE-based PAKE protocols with more desired properties.
For the entire collection see [Zbl 1387.94003].
For the entire collection see [Zbl 1387.94003].
References:
| [1] | Bliss - strongSwan. https://wiki.strongswan.org/projects/strongswan/wiki/BLISS |
| [2] | Abdalla, M.; Pointcheval, D.; Menezes, A., Simple password-based encrypted key exchange protocols, Topics in Cryptology - CT-RSA 2005, 191-208, 2005, Heidelberg: Springer, Heidelberg · Zbl 1079.94529 · doi:10.1007/978-3-540-30574-3_14 |
| [3] | Aguilar-Melchor, C.; Barrier, J.; Guelton, S.; Guinet, A.; Killijian, M-O; Lepoint, T.; Sako, K., NFLlib: NTT-based fast lattice library, Topics in Cryptology - CT-RSA 2016, 341-356, 2016, Cham: Springer, Cham · Zbl 1334.94055 · doi:10.1007/978-3-319-29485-8_20 |
| [4] | Albrecht, MR; Player, R.; Scott, S., On the concrete hardness of learning with errors, J. Math. Cryptology, 9, 3, 169-203, 2015 · Zbl 1352.94023 · doi:10.1515/jmc-2015-0016 |
| [5] | Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange-a new hope. IACR Cryptology ePrint Archive 2015, 1092 (2015) |
| [6] | Apple: iOS Security. https://www.apple.com/business/docs/iOS_Security_Guide.pdf |
| [7] | Bellovin, S.M., Merritt, M.: Encrypted key exchange: password-based protocols secure against dictionary attacks. In: Proceedings of 1992 IEEE Computer Society Symposium on Research in Security and Privacy, pp. 72-84. IEEE (1992) |
| [8] | Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., Stebila, D.: Frodo: take off the ring! practical, quantum-secure key exchange from lwe. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1006-1018. ACM (2016) |
| [9] | 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 (SP), pp. 553-570. IEEE (2015) |
| [10] | Boyko, V.; MacKenzie, P.; Patel, S.; Preneel, B., Provably secure password-authenticated key exchange using Diffie-Hellman, Advances in Cryptology — EUROCRYPT 2000, 156-171, 2000, Heidelberg: Springer, Heidelberg · Zbl 1082.94535 · doi:10.1007/3-540-45539-6_12 |
| [11] | Braithwaite, M.: Experimenting with Post-Quantum Cryptography. https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html |
| [12] | Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science 2001, pp. 136-145. IEEE (2001) |
| [13] | Denning, DE; Sacco, GM, Timestamps in key distribution protocols, Commun. ACM, 24, 8, 533-536, 1981 · doi:10.1145/358722.358740 |
| [14] | Diffie, W.; Hellman, M., New directions in cryptography, IEEE Trans. Inf. Theory, 22, 6, 644-654, 1976 · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638 |
| [15] | Ding, J.; Alsayigh, S.; Lancrenon, J.; Saraswa, RV; Snook, M.; Handschuh, H., Provably secure password authenticated key exchange based on RLWE for the post-quantum world, Topics in Cryptology - CT-RSA 2017, 183-204, 2017, Cham: Springer, Cham · Zbl 1383.94052 · doi:10.1007/978-3-319-52153-4_11 |
| [16] | Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology EPrint Archive 2012, 688 (2012) |
| [17] | Dousti, M.S., Jalili, R.: Forsakes: a forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Adv. Math. Commun. 9(4), 471-514 (2015). http://aimsciences.org/journals/displayArticlesnew.jsp?paperID=11939 · Zbl 1366.94551 |
| [18] | Goldberg, J.: Three layers of encryption keeps you safe when ssl/tls fails. https://blog.agilebits.com/2017/02/23/three-layers-of-encryption-keeps-you-safe-when-ssltls-fails/ |
| [19] | Gonzláez, S., Huguet, L., Martínez, C., Villafañe, H.: Discrete logarithm like problems and linear recurring sequences. Adv. Math. Commun. 7(2), 187-195 (2013). http://aimsciences.org/journals/displayArticlesnew.jsp?paperID=8550 · Zbl 1271.11116 |
| [20] | Hao, F.; Ryan, PYA; Christianson, B.; Malcolm, JA; Matyas, V.; Roe, M., Password authenticated key exchange by juggling, Security Protocols XVI, 159-171, 2011, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-22137-8_23 |
| [21] | Katz, J.; Vaikuntanathan, V.; Matsui, M., Smooth projective hashing and password-based authenticated key exchange from lattices, Advances in Cryptology - ASIACRYPT 2009, 636-652, 2009, Heidelberg: Springer, Heidelberg · Zbl 1267.94122 · doi:10.1007/978-3-642-10366-7_37 |
| [22] | Krawczyk, H.; Shoup, V., HMQV: a high-performance secure Diffie-Hellman protocol, Advances in Cryptology - CRYPTO 2005, 546-566, 2005, Heidelberg: Springer, Heidelberg · Zbl 1145.94445 · doi:10.1007/11535218_33 |
| [23] | Lyubashevsky, V.; Peikert, C.; Regev, O.; Gilbert, H., On ideal lattices and learning with errors over rings, Advances in Cryptology - EUROCRYPT 2010, 1-23, 2010, Heidelberg: Springer, Heidelberg · Zbl 1279.94099 · doi:10.1007/978-3-642-13190-5_1 |
| [24] | Micheli, G.: Cryptanalysis of a noncommutative key exchange protocol. Adv. Math. Commun. 9(2), 247-253 (2015). http://aimsciences.org/journals/displayArticlesnew.jsp?paperID=11174 · Zbl 1361.94045 |
| [25] | Morhaime, M.: Important security update. http://us.blizzard.com/en-us/securityupdate.html |
| [26] | Peikert, C.; Mosca, M., Lattice cryptography for the internet, Post-Quantum Cryptography, 197-219, 2014, Cham: Springer, Cham · Zbl 1383.94037 |
| [27] | Perrin, T., Wu, T., Mavrogiannopoulos, N., Taylor, D.: Using the secure remote password (SRP) protocol for TLS authentication. https://tools.ietf.org/html/rfc5054 |
| [28] | Regev, O., On lattices, learning with errors, random linear codes, and cryptography, J. ACM (JACM), 56, 6, 34, 2009 · Zbl 1325.68101 · doi:10.1145/1568318.1568324 |
| [29] | Shor, PW, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev., 41, 2, 303-332, 1999 · Zbl 1005.11507 · doi:10.1137/S0036144598347011 |
| [30] | Stephens-Davidowitz, N.: Discrete gaussian sampling reduces to CVP and SVP. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1748-1764. Society for Industrial and Applied Mathematics (2016) · Zbl 1410.68175 |
| [31] | Wu, T.D., et al.: The secure remote password protocol. In: NDSS, vol. 98, pp. 97-111 (1998) |
| [32] | Zhang, J.; Zhang, Z.; Ding, J.; Snook, M.; Dagdelen, Ö.; Oswald, E.; Fischlin, M., Authenticated key exchange from ideal lattices, Advances in Cryptology - EUROCRYPT 2015, 719-751, 2015, Heidelberg: Springer, Heidelberg · Zbl 1375.94164 |
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.
