Paper 2013/718

NTRU-KE: A Lattice-based Public Key Exchange Protocol

Xinyu Lei and Xiaofeng Liao


Public key exchange protocol is identified as an important application in the field of public-key cryptography. Most of the existing public key exchange schemes are Diffie-Hellman (DH)-type, whose security is based on DH problems over different groups. Note that there exists Shor's polynomial-time algorithm to solve these DH problems when a quantum computer is available, we are therefore motivated to seek for a non-DH-type and quantum resistant key exchange protocol. To this end, we turn our attention to lattice-based cryptography. The higher methodology behind our roadmap is that in analogy to the link between ElGamal, DSA, and DH, one should expect a NTRU lattice-based key exchange primitive in related to NTRU-ENCRYPT and NTRU-SIGN. However, this excepted key exchange protocol is not presented yet and still missing. In this paper, this missing key exchange protocol is found, hereafter referred to as NTRU-KE, which is studied in aspects of security and key-mismatch failure. In comparison with ECDH (Elliptic Curve-based Diffie-Hellman), NTRU-KE features faster computation speed, resistance to quantum attack, and more communication overhead. Accordingly, we come to the conclusion that NTRU-KE is currently comparable with ECDH. However, decisive advantage of NTRU-KE will occur when quantum computers become a reality.

Note: NO.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Key exchangeDiffie-HellmanNTRUquantum resistance
Contact author(s)
xy-lei @ qq com
691709302 @ qq com
2013-11-03: received
Short URL
Creative Commons Attribution


      author = {Xinyu Lei and Xiaofeng Liao},
      title = {NTRU-KE: A Lattice-based Public Key Exchange Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2013/718},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.