Improved authenticated key agreement protocol based on Bi-ISIS problem

doi:10.19682/j.cnki.1005-8885.2020.0011

The Journal of China Universities of Posts and Telecommunications ›› 2020, Vol. 27 ›› Issue (3): 93-102.doi: 10.19682/j.cnki.1005-8885.2020.0011

Received:2019-09-24 Revised:2019-12-08 Online:2020-06-24 Published:2020-08-30
Supported by:
This work was supported by the China State Cryptography Development Fund of Thirteen Five-year (MMJJ20170110).

Abstract

Abstract: In the post quantum era, public key cryptographic scheme based on lattice is considered to be the most promising cryptosystem that can resist quantum computer attacks. However, there are still few efficient key agreement protocols based on lattice up to now. To solve this issue, an improved key agreement protocol with post quantum security is proposed. Firstly, by analyzing the Wess-Zumino model + ( WZM + ) key agreement protocol based on small integer solution (SIS) hard problem, it is found that there are fatal defects in the protocol that cannot resist man-in-the-middle attack. Then based on the bilateral inhomogeneous small integer solution (Bi-ISIS) problem, a mutual authenticated key agreement (AKA) protocol with key confirmation is proposed and designed. Compared with Diffie-Hellman (DH) protocol, WZM + key agreement protocol, and the AKA agreement based on the ideal lattice protocol, the improved protocol satisfies the provable security under the extend Canetti-Krawczyk (eCK) model and can resist man-in-the-middle attack, replay attack and quantum computing attack.

Key words: lattice, small integer solution problem, key agreement protocol, provable security, eCK model

References 33

1.	Dodis Y, Mironov I, Stephens-Davidowitz N. Message transmission with reverse firewalls-secure communication on corrupted machines. Advances in Cryptology: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO’16): Part 1, Aug 14-18, 2016, Santa Barbara, CA, USA, LNCS 9814. Berlin, Germany: Springer, 2016: 341-372
2.	Benzvi A, Blackburn S R, Tsaban B. A practical cryptanalysis of the algebraic eraser. Advances in Cryptology: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO’16): Part 1, Aug 14-18, 2016, Santa Barbara, CA, USA, LNCS 9814. Berlin, Germany: Springer, 2016: 179-189.
3.	Diffie W, Hellman M. New directions in cryptography. IEEE Transactions on Information Theory, 1976, 22(6): 644-654.
4.	Ajtai M. Generating hard instances of lattice problems. Proceedings of the 28th ACM Symposium on Theory of Computing (STOC’96), May 22-24, 1996, Philadelphia, PA, USA. New York, NY, USA: ACM, 1996: 99-108
5.	Libert B, Ling S, Nguyen K, et al. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors. Advances in Cryptology: Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’16): Part 1, May 8-12, 2016, Vienna, Austria. LNCS 9666. Berlin, Germany: Springer, 2016: 1-31.
6.	Fiore D, Mitrokotsa A, Nizzardo L, et al. Multi-key homomorphic authenticators. Advances in Cryptology: Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’16): Part 2, Dec 4-8, 2016, Hanoi, Vietnam. LNCS 10032. Berlin, Germany: Springer, 2016: 499-530.
7.	Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, 2007, 37(1): 267-302.
8.	Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009, 56(6): 1-37.
9.	Clear M, Mcgoldrick C. Multi-identity and multi-key leveled FHE from learning with errors. Advances in Cryptology: Proceedings of the 35th Annual Cryptology Conference (CRYPTO’15): Part 2, Aug 16-20, 2015, Santa Barbara, CA, USA. LNCS 9216. Berlin, Germany: Springer, 2015: 630-656.
10	Ling S, Nguyen K, Wang H X. Group signatures from lattices: Simpler, tighter, shorter, ring-based. Public-Key Cryptography: Proceedings of the IACR International Workshop on Public Key Cryptography (PKC’15), Mar 30-Apr 1, 2015, Gaithersburg, MD, USA. LNCS 9020. Berlin, Germany: Springer, 2015:427-449.
11	Gorbunov S, Vaikuntanathan V, Wee H. Predicate encryption for circuits from LWE. Advances in Cryptology: Proceedings of the 35th Annual Cryptology Conference (CRYPTO’15): Part 2, Aug 16-20, 2015, Santa Barbara, CA, USA. LNCS 9216. Berlin, Germany: Springer, 2015: 503-523.
12	Katz J, Vaikuntanathan V. Smooth projective hashing and password based authenticated key exchange from lattices. Advances in Cryptology: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’09), Dec 6-10, 2009, Tokyo, Japan. LNCS 5912. Berlin, Germany: Springer, 2009: 636-652.
13	Ding J T. A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report. International Association for Cryptologic Research (IACR), 2012: 1-13.
14	Ding J T, Xie X, Lin X D. A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report. International Association for Cryptologic Research (IACR), 2014: 1-15.
15	Wang S B, Zhu Y, Ma D, et al. Lattice-based key exchange on small integer solution problem. Science China (Information Sciences), 2014, 57(11):1-12.
16	Zhang J, Zhang Z F, Ding J T, et al. Authenticated key exchange from ideal lattices. Advances in Cryptology: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’15), Apr 26-30, 2015, Sofia, Bulgaria. LNCS 9057. Berlin, Germany: Springer, 2015: 719-751.
17	Gupta D S, Biswas G P. Cryptanalysis of Wang et al’. lattice-based key exchange protocol. Perspectives in Science, 2016, 8: 228-230.
18	Mao S W, Zhang P, Wang H Z, et al. Cryptanalysis of a lattice based key exchange protocol. Science China (Information Sciences), 2017, 60 (2):1-3.
19	Peikert C. Lattice cryptography for the Internet. Post-Quantum Cryptography: Proceedings of the 6th International Workshop on Post-Quantum Cryptography (PQCrypto’14), Oct 1-3, 2014, Waterloo, Canada. LNCS 8772. Berlin, Germany: Springer, 2014: 197-219.
20	Yao Y Q, Li Z J. A novel fuzzy identity based signature scheme based on the short integer solution problem. Computers and Electrical Engineering, 2014, 40(6): 1930-1939.
21	Bos J W, Costello C, Naehrig M, et al. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. Proceedings of the 2015 IEEE Symposium on Security and Privacy, May 17-21, 2015, San Jose, CA, USA. Piscataway, NJ, USA: IEEE, 2015: 553-570.
22	Bai S, Galbraith S D, Li L Z, et.al. Improved combinatorial algorithms for the inhomogeneous short integer solution problem. Journal of Cryptology, 2019, 32(1): 35-83.
23	Jing Z J, Gu C S, Yu Z M, et.al. Cryptanalysis of lattice-based key exchange on small integer solution problem and its improvement. Cluster Computing, 2019, 22(S1): 1717-1727.
24	Gupta D S, Biswas G P . A novel and efficient lattice-based authenticated key exchange protocol in C-K model. International Journal of Communication Systems, 2018, 31(3): e3473.
25	Ding J T, Schmitt K, Zhang Z. A key exchange based on the short integer solution problem and the learning with errors problem. Codes, Cryptology and Information Security: Proceedings of the 3rd International Conference on Codes, Cryptology, and Information Security (C2SI’19), Apr 22-24, 2019, Rabat, Morocco. LNCS 11445. Berlin, Germany: Springer, 2019: 105-117.
26	LaMacchia B, Lauter K, Mityagin A. Stronger security of authenticated key exchange. Provable Security: Proceedings of the 1st International Conference on Provable Security (ProvSec’07), Nov 1-2, 2007, Wollongong, Australia. LNCS 4784. Berlin, Germany: Springer, 2007: 1-16.
27	Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08), May 17-20, 2008, Victoria, Canada. New York, NY, USA: ACM, 2008: 197-206.
28	Goldwasser S, Micali S. Probabilistic encryption and how to play mental poker keeping secret all partial information. Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC’82), May 5-7, 1982, San Francisco, CA, USA. New York, NY, USA: ACM, 1982: 365-377.
29	Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols. Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS’93), Nov 3-5, 1993, Fairfax, VA, USA. New York, NY, USA: ACM, 1993: 62-73.
30	Burgisser P. Completeness and reduction in algebraic complexity theory. Algorithms and computation in mathematics, Vol 7. Berlin, Germany: Springer, 2000: 11-63.
31	Feng D G. Research on theory and approach of provable security. Journal of Software, 2005, 16(10): 1743-1756 (in Chinese)
32	Alawatugoda J. Generic construction of an eCK-secure key exchange protocol in the standard model. International Journal of Information Security, 2017,16(5): 541-557.
33	Alawatugoda J, Boyd C, Stebila D. Continuous after-the-fact leakage resilient key exchange. Information Security and Privacy: Proceedings of the 19th Australasian Conference on Information Security and Privacy (ACISP’4), Jul 7-9, 2014, Wollongong, Australia. LNCS 8544. Berlin, Germany: Springer, 2014: 258-273.

Metrics

Comments

Copyright © 2020 The Journal of China Universities of Posts and Telecommunications
　 Adress: P.O. Box 231,Beijing University of Posts and Telecommunications,10 Xi Tucheng Road,Beijing 100876,P.R.China　Post Code: 100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
Support by: Beijing Magtech Co.Ltd