Paper 2017/709

spKEX: An optimized lattice-based key exchange

Sauvik Bhattacharya, Oscar Garcia-Morchon, Ronald Rietman, and Ludo Tolhuizen

Abstract

The advent of large-scale quantum computers has resulted in significant interest in quantum-safe cryptographic primitives. Lattice-based cryptography is one of the most attractive post-quantum cryptographic families due to its well-understood security, efficient operation and versatility. However, LWE-based schemes are still relatively bulky and slow. In this work, we present spKEX, a forward-secret, post-quantum, unauthenticated lattice-based key-exchange scheme that combines four techniques to optimize performance. spKEX relies on Learning with Rounding (LWR) to reduce bandwidth; it uses sparse and ternary secrets to speed up computations and reduce failure probability; it applies an improved key reconciliation scheme to reduce bandwidth and failure probability; and computes the public matrix A by means of a permutation to improve performance while allowing for a fresh A in each key exchange. For a quantum security level of 128 bits, our scheme requires 30% lesser bandwidth than the LWE-based key-exchange proposal Frodo [9] and allows for a fast implementation of the key exchange.

Note: Section on hybrid attack has been added. As a result, the proposed parameters have been altered.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
lattice techniqueskey exchange
Contact author(s)
ludo tolhuizen @ philips com
History
2017-08-17: revised
2017-07-25: received
See all versions
Short URL
https://ia.cr/2017/709
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/709,
      author = {Sauvik Bhattacharya and Oscar Garcia-Morchon and Ronald Rietman and Ludo Tolhuizen},
      title = {spKEX: An optimized lattice-based key exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2017/709},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/709}},
      url = {https://eprint.iacr.org/2017/709}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.