Paper 2016/467

Speeding up R-LWE post-quantum key exchange

Shay Gueron and Fabian Schlieker

Abstract

Post-quantum cryptography has attracted increased attention in the last couple of years, due to the threat of quantum computers breaking current cryptosystems. In particular, the key size and performance of post-quantum algorithms became a significant target for optimization. In this spirit, Alkim \etal have recently proposed a significant optimization for a key exchange scheme that is based on the R-LWE problem. In this paper, we build on the implementation of Alkim \etal, and focus on improving the algorithm for generating a uniformly random polynomial. We optimize three independent directions: efficient pseudorandom bytes generation, decreasing the rejection rate during sampling, and vectorizing the sampling step. When measured on the latest Intel processor Architecture Codename Skylake, our new optimizations improve over Alkim \etal by up to 1.59x on the server side, and by up to 1.54x on the client side.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Post-quantum key exchangeRing-LWEsoftware optimizationAVX2AVX512AES-NI
Contact author(s)
shay @ math haifa ac il
History
2016-05-17: received
Short URL
https://ia.cr/2016/467
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/467,
      author = {Shay Gueron and Fabian Schlieker},
      title = {Speeding up R-{LWE} post-quantum key exchange},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/467},
      year = {2016},
      url = {https://eprint.iacr.org/2016/467}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.