Abstract
Google's CECPQ1 experiment in 2016 integrated a post-quantum key-exchange algorithm, newhope1024, into TLS 1.2. The Google-Cloudflare CECPQ2 experiment in 2019 integrated a more efficient key-exchange algorithm, ntruhrss701, into TLS 1.3. This paper revisits the choices made in CECPQ2, and shows how to achieve higher performance for post-quantum key exchange in TLS 1.3 using a higher-security algorithm, sntrup761. Previous work had indicated that ntruhrss701 key generation was much faster than sntrup761 key generation, but this paper makes sntrup761 key generation much faster by generating a batch of keys at once. Batch key generation is invisible at the TLS protocol layer, but raises software-engineering questions regarding the difficulty of integrating batch key exchange into existing TLS libraries and applications. This paper shows that careful choices of software layers make it easy to integrate fast post-quantum software, including batch key exchange, into TLS with minor changes to TLS libraries and no changes to applications. As a demonstration of feasibility, this paper reports successful integration of its fast sntrup761 library, via a lightly patched OpenSSL, into an unmodified web browser and an unmodified TLS terminator. This paper also reports TLS 1.3 handshake benchmarks, achieving more TLS 1.3 handshakes per second than any software included in OpenSSL.
Introduction
As quantum computers loom on the horizon, the cryptographic community is racing to upgrade the Transport Layer Security (TLS) protocol to be "post-quantum" (PQ). Current standards like Elliptic Curve Cryptography (ECC) will be trivial for a large-scale quantum computer to break. However, moving to PQ cryptography isn't a simple drop-in replacement. PQ algorithms typically involve much larger keys and ciphertexts, and they can be significantly more computationally expensive.
Previous industry experiments, such as Google’s CECPQ2, prioritized the ntruhrss701 algorithm due to its fast key generation. This paper introduces OpenSSLNTRU, a high-performance integration of the sntrup761 algorithm into TLS 1.3. The authors demonstrate that through mathematical optimization and clever software engineering, it is possible to achieve higher security levels than previous experiments while actually outperforming standard, non-quantum-resistant algorithms like X25519 in terms of handshakes per second.
Methodology
Batch Key Generation and AVX2 Optimization
The primary bottleneck in sntrup761 is computing modular inverses. The authors utilize "Montgomery’s trick," which allows for the simultaneous computation of multiple independent inverses. By generating keys in batches of 32, the cost of the expensive inversion step is amortized, turning 32 inversions into a single inversion plus a series of much cheaper multiplications.
Furthermore, the implementation includes highly optimized polynomial multiplication for Intel Haswell CPUs using the AVX2 instruction set. This involves a mix of Karatsuba's algorithm and Bernstein’s 5-way recursive algorithm for arithmetic, alongside a radix-2 Number Theoretic Transform (NTT) manufactured via Schönhage’s trick.
Software Architecture and Integration
To ensure real-world feasibility without breaking existing systems, the authors developed an OpenSSL ENGINE module called engNTRU. This plugin handles the PQ logic and batching state, allowing a lightly patched OpenSSL to work with unmodified applications, such as the Epiphany web browser or the stunnel proxy.
As shown in the handshake diagram, the libssl patch allows the server to encapsulate via PKE+NIKE logic while remaining compatible with the standard TLS 1.3 flow. This design decouples fast-moving PQ research from the stable TLS ecosystem.
Performance Evaluation
The performance of OpenSSLNTRU was evaluated through microbenchmarks of core arithmetic operations and macrobenchmarks of full TLS 1.3 handshake throughput.
As detailed in the comparison table, batching fundamentally changes the performance hierarchy. Traditionally, ntruhrss701 was considered faster than sntrup761. However, with batching, sntrup761 key generation cycles dropped from 814,608 to 156,317 per key—making it significantly faster than the ntruhrss701 implementation used in CECPQ2.
Key results include:
- Handshake Throughput: In end-to-end tests,
sntrup761achieved approximately 600 handshakes per second, outperforming both NIST P-256 (~490/sec) and X25519 (~510/sec). - Security Gain: These speeds were achieved while providing a security level of $2^{153}$ (Core-SVP), compared to $2^{136}$ for the algorithm used in CECPQ2.
Limitations and Future Work
Despite these gains, several challenges remain:
- Statefulness: Batch key generation introduces state into the TLS stack (the pool of pre-generated keys), adding complexity to memory management.
- Authentication: This work focuses on Key Encapsulation Mechanisms (KEMs) for confidentiality. It does not address post-quantum signatures for authentication, which involve even larger data sizes.
- Network Sensitivity: While faster on a Gigabit LAN, the larger packet sizes of PQ keys (kilobytes vs. bytes for ECC) could lead to higher latency on slower or congested networks.
Summary updated