Application of algebraic-ring in key exchange protocol
Subject Areas : General algebraic systems
1 - Department of Mathematics, University of Kashan, Kashan, Iran
2 - Department of Mathematics, University of Kashan, Kashan, Iran
Keywords: Diffie-Hellman key exchange, Lattice based cryptography, Learning with error, Ideal lattice,
Abstract :
In this article, we present a non-interactive key exchange protocol with a faster run time, which is based on a Module-LWE. The Structure of protocol is designed just by relating the error vectors of both sides, without any use of a reconciliation mechanism. The idea is that as error vectors get closer to each other the success probability of the protocol increases. The innovation in this scheme is the use of high-order bits in the keys computed by both sides. Compared to the existing lattice-based key-exchange protocols, this scheme leads to lower computational complexity and longer parameters.
[1] M. Ajtai, The shortest vector problem in L2is NP-hard for randomized reductions, Proceedings of the 30th ACM Symposium on the Theory of Computing. (1998), 10-19.
[2] E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, New Hope Without Reconciliation, 2016.
[3] E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, Post-Quantum Key Exchange-A New Hope, Proceedings of the 25th USENIX Security Symposium, 2016.
[4] W. Diffie, M. Hellman, New directions in cryptography, IEEE transactions on Information Theory. 22 (1976), 644-654.
[5] G. Hanrot, X. Pujol, D. Stehlé, Algorithms for the Shortest and Closest Lattice Vector Problems, Coding and Cryptology, Third International Workshop, IWCC, 6639 of LNCS, 2011.
[6] V. Lyubashevsky, C. Peikert, O. Regev, On Ideal Lattices and Learning with Errors over Rings, Advances in Cryptology-Eurocrypt. (2010), 1-23.
[7] D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science, 671, 2002.
[8] D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, Springer, 2012.
[9] D. Micciancio, O. Regev, Lattice-based cryptography, Post-quantum Cryptography. (2009), 147-191.
[10] C. Peikert, A decade of lattice cryptography, Foundations and Trends in Theoretical Computer Science. 10 (2016), 283-424.
[11] C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, Proceedings of the 49th ACM Symposium on Theory of Computing. (2009), 333-342.
[12] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the 37th ACM Symposium on Theory of Computing. (2005), 84-93.
[13] O. Regev, The learning with errors problem (invited survey), In Proceedings of the 25th Annual IEEE Conference on Computational Complexity-CCC. (2010), 191-204.
[14] P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, 35th FOCS IEEE Computer Society Press. (1994), 124-134.
[15] P. Van Emde Boas, Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, Technical Report, Universiteit van Amsterdam, Mathematisch Institut, 1981.
[16] K. Xagawa, Cryptography with Lattices, PhD thesis, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2010.