Document Type : Research Paper


Department of Mathematics‎, ‎Kashan University‎, ‎Kashan‎, ‎Iran


‎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‎.


Main Subjects

[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.