LatticeCrypto implements the key exchange protocol proposed by Alkim, Ducas, Pöppelmann and Schwabe [3], which builds upon previous work by Bos, Costello, Naehrig and Stebila [2], and is an instantiation of Peikert’s key exchange [4]. The implementation incorporates novel techniques for computing the Number Theoretic Transform to achieve higher performance. The library is fully protected against timing and cache attacks (i.e., all operations on secret data run in constant time) and is significantly faster than previous implementations, e.g., it is up to 1.4 times faster than the previously fastest R-LWE key exchange implementation at the same security level [3].

The need for post-quantum cryptography

A large-scale quantum computer breaks most public-key cryptography that is currently used on the internet such as RSA encryption and digital signatures, ECDH key exchange and ECDSA signatures. Even if no such quantum computer exists today, the prospect of one being built in the not-too-distant future makes it necessary to prepare our cryptography infrastructure and protect our data against future attacks now. This release is part of a larger effort to identify and deploy asymmetric cryptographic schemes that resist quantum attacks and can replace vulnerable algorithms.

R-LWE-based cryptography

The R-LWE problem was introduced by Lyubashevsky, Peikert, and Regev in [5] as a hard lattice problem for constructing cryptographic schemes. Its additional ring structure leads to significant efficiency and bandwidth improvements over schemes built from the Learning With Errors (LWE) problem introduced by Regev in [6]. Solving the R-LWE problem is currently believed to be infeasible even for a quantum computer, which makes schemes based on its hardness candidates for post-quantum cryptography.

The LatticeCrypto Library:

• Supports arithmetic functions for computations in power-of-2 cyclotomic rings that are the basis for implementing R-LWE-based cryptographic algorithms
• Provides at least 128 bits of classical and quantum security
• Protects against timing and cache-timing attacks through regular, constant-time implementation of all operations on secret key material
• Supports on Windows and Linux, and can be used on a wide range of platforms, including x86, x64, and ARM
• Optional high-performance optimizations in x64 assembly under Linux are included
• Includes testing and benchmarking code.

See [1] for more details.

Download

The LatticeCrypto library is available for download at: https://www.microsoft.com/en-us/download/details.aspx?id=52371

A patch for OpenSSL 1.0.2g to support Peikert’s Ring Learning with Errors (RLWE) key exchang using our LatticeCrypto library is available for download at: https://www.microsoft.com/en-us/download/details.aspx?id=54055

References

[1] P. Longa and M. Naehrig, “Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography”
[2] J. Bos, C. Costello, M. Naehrig, D. Stebila, “Post-quantum key exchange for the TLS protocol from the ring learning with errors problem”, in Proceedings of the IEEE Symposium on Security and Privacy, 2015.
[3] E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, “Post-quantum key exchange – a new hope”, IACR Cryptology ePrint Archive, Report 2015/1092, 2015.
[4] C. Peikert, “Lattice cryptography for the internet”, in Post-Quantum Cryptography – 6th International Workshop (PQCrypto 2014), LNCS 8772, pp. 197-219. Springer, 2014.
[5] V. Lyubashevsky, C. Peikert, O. Regev, “On ideal lattices and learning with errors over rings”, in EUROCRYPT 2010, volume 6110 of LNCS, pages 1–23. Springer, 2010.
[6] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, pp. 84–93. ACM, 2005.