Faster Post-Quantum TLS 1.3 Based on ML-KEM: Implementation and Assessment (2024)

Motivations.

Recent work presented an accelerated Ed25519 and X25519 AVX-512 engine tailored for TLS 1.3, offering significant performance improvement [55]. Previous work explored optimized PQC implementations using the latest Intel Single Instruction Multiple Data (SIMD) instruction AVX-512 (e.g. [15, 32, 16]). However, the integration of PQC AVX-512 optimized implementations into TLS 1.3 remains unrealized, and there is currently no AVX-512 implementation available for ML-KEM. This gap prompts our focus on optimizing ML-KEM using AVX-512 and seamlessly integrating the optimized ML-KEM implementation into TLS 1.3, and also provides an opportunity to explore the impact of AVX-512 instructions on PQ-TLS handshake protocols.

As of now, existing research on PQ-TLS migration relies on OQS-OpenSSL, which lacks support for OpenSSL3 and remains outdated. However, the latest OQS provider [8] not only supports OpenSSL3 but also facilitates a clear separation between OpenSSL code and PQC KEM code. Our comprehensive integration of ML-KEM using the OQS provider could provide valuable guidance for researchers seeking to migrate to PQ-TLS.

In addition, recent studies [28, 30, 43, 44] have affirmed the sufficiency of IND-1-CCA KEMs for TLS 1.3 handshake to be secure. Intriguingly, IND-1-CCA KEMs can be obtained from any OW-CPA/IND-CPA KEMs without re-encryption and de-randomization [28, 30] that are required by IND-CCA KEMs used in PQ-TLS previously. An idea can be easily deduced that TLS 1.3 handshake might demonstrate improved efficiency by applying such IND-1-CCA KEMs. However, there remains a notable absence of experiments focusing on IND-1-CCA-security KEM TLS 1.3. This gap in research catalyzes us to conduct experiments and evaluations on IND-1-CCA-secure PQ-TLS handshake protocols.

Contributions.

In this work, we aim to bridge the gap between PQC engineering implementations and TLS protocol applications. We approach to this task from both an optimization engineering perspective and a TLS system perspective. We will later open source our code.

2.1 Notation

The notation in this paper is the same as the FIPS 203 draft [51]. We denote $\mathcal{R}_{q}$ as the cyclic polynomial ring $\mathbb{Z}_{q}[x]/(x^{n}+1)$. We define $r^{\prime}=r~{}{\bmod}^{\pm}~{}\alpha$ (resp. $r^{\prime}=r\bmod\alpha$) to be the unique element $r^{\prime}$ in the range $-\left\lfloor{\frac{\alpha}{2}}\right\rfloor<r^{\prime}\leq\left\lfloor{\frac{$ (resp. $0\leq r^{\prime}<\alpha$) such that $\alpha|(r-r^{\prime})$. By default, regular font lettersdenote elements in $\mathcal{R}_{q}$, bold lower-case letters are column vectors and bold upper-case letters are matrices.

2.2 ML-KEM

Through the T-NTT transformation, the $n$-dimensional polynomials $f,g$ are separately decomposed into $\frac{n}{2}$ linear polynomials. Then the original multiplication $f\times g$ is transformed into $\frac{n}{2}$ multiplications of linear polynomials.

Cooley-Tukey transform [17] and Gentleman-Sande transform [24] are used in NTT and INTT respectively, shown in Figure 2 and Figure 2.

2.3 AVX-512 Instruction Set

The AVX-512 instruction set was introduced by Intel in 2013 and initially supported in the 2016 Xeon Phi series processors [2], AVX-512 has since become a pivotal feature for both major CPU manufacturers. AVX-512 offers several key functionalities: it introduces 32 512-bit zmm registers, enabling simultaneous processing of multiple data elements and accelerating vectorized computations. AVX-512 covers a wide range of floating-point and integer operations for diverse computational requirements. Additionally, AVX-512 provides 8 mask registers (k0-k7) for conditional operations, allowing instructions to execute based on conditions. These mask registers enhance the flexibility and efficiency of data processing by enabling advanced operations such as compression/expansion and masking.

2.4 TLS 1.3 and PQ-TLS

TLS is a standard developed by the Internet Engineering Task Force (IETF) in 1999. Its primary role is to encrypt communication between web applications and servers, with the latest version being TLS 1.3 [41]. When initiating a TLS connection, the client and server exchange parameters such as TLS version and ciphersuite. Our study focuses on enhancing TLS security against post-quantum threats, particularly through the adoption of PQC Key Exchange (KEX) in PQ-TLS. PQ-TLS operates in two modes: hybrid mode and PQ-only mode. The hybrid mode, as standardized by the IETF in TLS 1.3 [1], supports simultaneous usage of ECDH and PQC KEM, albeit at the cost of increased data transmission size and computational resources. Conversely, the PQ-only mode exclusively employs PQC KEM for Key Exchange and PQC signature algorithms for authentication.

3.1 Modular Reduction Implementation

Modular reduction plays a crucial role in ML-KEM polynomial arithmetic, where the arithmetic operates over the ring $\mathbb{Z}_{q}$ with $q=3329$. However, AVX-512 instructions lack dedicated support for modular reduction computations. In this context, we introduce the signed versions of two constant-time reduction algorithms commonly utilized in lattice-based cryptography: Montgomery reduction [34] and Barrett reduction [9], as proposed by Seiler [45].
Reduction Algorithms.The Signed Montgomery reduction computes the Hensel remainder of a signed integer within the range $[-\beta q/2,\beta q/2)$, specifically employed in ML-KEM to reduce the product of two 16-bit coefficients. The output remainder integer resides in the Montgomery domain and is further multiplied by $\beta^{-1}$. Barrett reduction operates within a smaller input range compared to Montgomery reduction. Typically, the input to Barrett reduction does not exceed a 16-bit signed integer range. Therefore, Barrett reduction is commonly utilized to reduce coefficients that surpass the range $[-q,q]$ after addition and subtraction operations. The resulting output from Barrett reduction remains within $\mathbb{Z}_{q}$.
AVX-512 Implementations.We give our AVX-512 implementations of signed Montgomery reduction and Barrett reduction.For the modulus $q=3329=2^{13}-2^{9}+1$, we set $\beta=2^{16}$. This configuration ensures that one coefficient occupies 16 bits within a 512-bit vector register, enabling 32-way parallelism. Given that $v$ remains constant in Barrett reduction [45, Sec 3.3], we can precompute $v$ and store it in the vector register. Regarding the computation of $av/2^{\beta}$, it involves two operations: multiplication and division. These two operations can be executed using a single AVX-512 instruction, vpmulhw, which computes the product of every two 16-bit data lanes in vector registers and retains only the higher 16 bits. Additionally, the division by $2^{\lfloor\log(q)\rfloor-1}$ can be efficiently implemented using AVX-512 shift instructions. In Algorithm 1, we introduce a macro red16 designed to compute Barrett reduction using AVX-512 instructions. Within this macro, the zmm\r register holds the output of the Barrett reduction, while zmm\rv stores the constant used in Barrett reduction, represented by $v=\left\lfloor\frac{2^{\lfloor\log(3329)\rfloor-1}2^{16}}{3329}\right\rceil=20$. Additionally, the zmm\rl register stores an immediate value. Furthermore, we will introduce our 32-way Montgomery reduction AVX-512 implementation, combined with butterfly operation, in Section 3.2.

3.2 NTT Implementation

NTT is one of the most intricate components in the ML-KEM AVX-512 implementation. Both NTT and INTT operations in ML-KEM require 7 layers of butterfly operations to obtain the final result. In this section, we will introduce several techniques used in NTT implementation.
Register Allocation.A 512-bit vector register zmm can accommodate a maximum of 32 16-bit integers, requiring only 8 vector registers to store all 256 polynomial coefficients. Therefore, we allocate 8 vector registers for storing coefficients, 2 for intermediate registers, and 2 for constant registers, leaving 20 vector registers unused.
Butterfly Unit. Our Cooley-Tukey butterfly pseudo-code is outlined in Algorithm 3. Registers zmm\l and zmm\r respectively store coefficients $f_{i}$ and $f_{j+len/2}$, while zmm0 holds the modulus $q$. We precompute $q^{-1}\bmod^{\pm}\beta$ into twiddle factors to reduce one multiplication operation in Montgomery reduction. To obtain the low and high bits of the 16-bit integer multiplication product, we utilize vector integer multiplication instructions vpmullw and vpmulhw. These instructions eliminate the necessity of extending coefficients to 32 bits after multiplication. Our Gentleman-Sande Butterfly pseudo-code is presented in Algorithm 2. Similar to the Cooley-Tukey butterfly, registers zmm\l and zmm\r store coefficients $f_{i}$ and $f_{j+len/2}$, respectively. Additionally, registers zmm\zl and zmm\zr hold precomputed $\zeta\cdot q^{-1}$ and $\zeta$ values, respectively. The order of twiddle factors in the NTT differs from that in the INTT, thus the same twiddle factors can be used. However, employing the same twiddle factors table necessitates additional permutation. In our implementation, we opt to utilize two distinct twiddle factors tables for the NTT and INTT.

In the implementation of NTT and INTT, we employ layer merging and coefficient permutation methods to reduce the memory access overhead. Specifically, we merge the 7 layers of NTT. We load all coefficients into 8 vector registers only at the first layer and store them back in memory after completing the final layer computation. Achieving such layer merging incurs some additional overhead for the coefficient permutation. Since each vector register accommodates 32 coefficients, in the initial three layers of the NTT, the coefficients stored in vector registers satisfy the correct distance and can directly perform the Cooley-Tukey butterfly. Starting from the fourth layer, as the butterfly distance becomes 16, the coefficient pairs requiring butterfly operations are housed within the same vector register. Thus, it’s necessary to separate the coefficient pairs at corresponding distances into different vector registers.

As depicted in Figure 3, we can observe the arrangement of coefficients within a vector register during the third to seventh layers of the NTT. The functions Shuffle16, Shuffle8, Shuffle4, Shuffle2, and Shuffle1 are utilized for permuting pairs of 16, 8, 4, 2, and 1 coefficients, respectively. We perform an extra Shuffle1 to bring convenience for polynomial point-wise multiplication. After completing all NTT layers, the coefficients are constrained within the range of signed 16-bit integers, eliminating the need for Barrett reduction in NTT. However, this differs in the case of INTT. We adopt lazy reduction in INTT as outlined in [54].

3.3 SHA3 Keccak Implementation

ML-KEM utilizes SHA3-256, SHA3-512, SHAKE128, and SHAKE256 as hash functions, pseudorandom functions (PRFs), and eXtendable-output functions (XOFs). These algorithms belong to the SHA-3 family [22] developed by NIST and are based on the Sponge Construction [11]. The round function employed in the SHA-3 algorithm is the Keccak-p[1600,24] permutation function, which operates on a 64-bit state. In the previous AVX2 implementation of ML-KEM by the Crystals team, Keccak-p[1600,24] achieved 4-way parallelism due to the 256-bit vector register width. However, with AVX-512 implementation, we can compute 8 Keccak permutation results in parallel, as a 512-bit vector register can process 8 Keccak states concurrently.

3.4 Other Modules

We also implement Compress and Decompress, pkDecode, skDecode, skEncode and pkEncode and several polynomial arithmetic functions. The implementation idea is similar to the AVX2 implementation. For simplicity, we don’t discuss details here. One notable difference is that, in the implementation of pkDecode, skDecode, and Decompress, we utilize the AVX-512 instruction vpermb, which operates on bytes, unlike AVX2 instructions. This instruction allows us to conveniently adjust the order of byte streams. We implement rejection sampling using AVX-512 according to the method presented in [56].

4.1 Batch Key Generation Using Parallel Keccak

The concept of batch key generation was discussed in both [55] and [10]. In [10], Montgomery’s trick was used to compute multiple polynomial inversions, specifically targeting key generation algorithms involving polynomial inversion. On the other hand, [55] introduces an $8\times 1$ X25519 approach to batch 8 key pairs in parallel. We explore the potential applicability of batch key generation in other PQC algorithms. Drawing inspiration from [42], we propose a batch key generation approach for ML-KEM, as outlined in Algorithm 4. The SHA3-256x8 function is constructed based on the 8-way Keccak function discussed in Section 3.3. Our 8-way ML-KEM key generation AVX-512 implementation function is designed to generate 8 independent $(pk,sk)$ pairs simultaneously.

4.2 ML-KEM AVX-512 TLS 1.3 Migration Implementation

We use OQS provider proposed by the Open Quantum Safe (OQS) team [36] and OpenSSL 3.3.0-dev to migrate the ML-KEM AVX-512 implementation. OpenSSL is an open-source software library implementing the SSL and TLS protocols. Most PQ-TLS research works use OQS-OpenSSL to migrate PQC algorithms into TLS 1.3. However, OQS-OpenSSL ceased updates in July 2023 and does not support the latest OpenSSL 3.0 version. The latest OQS provider separates the integration of PQ algorithms into TLS 1.3 from the main logic of OpenSSL, without altering the core cryptographic algorithms. This separation isolates the embedding of post-quantum algorithms from the extensive OpenSSL codebase. For ML-KEM AVX-512 code migration, we choose liboqs 0.10.1 [19]. Liboqs is an open-source C library for quantum-safe cryptographic algorithms. The newest liboqs 0.10.1 version adds ML-DSA and ML-KEM C reference and AVX2 codes. We add our ML-KEM AVX-512 code in the ml_kem directory of liboqs. Besides, we implement the corresponding ML-KEM AVX-512 Keygen, Encaps, and Decaps APIs in liboqs. We define the macro OQS_ENABLE_KEM_ml_kem_512_avx512 in the OQS configuration file. By configuring this macro, users can run ML-KEM-512 AVX-512 code within the liboqs library.

5.1 An Efficient Choice of Key-Exchange: IND-1-CCA KEM

In existing PQ-TLS implementations, the ephemeral KEX is implemented with IND-CCA KEMs. IND-CCA KEMs are usually constructed by applying Fujisaki-Okamoto (FO) transform or its variants (e.g. ML-KEM [51]) on an OW/IND-CPA PKE scheme, while FO transform requires re-encrypting the plaintext during decapsulation, significantly reducing the efficiency of KEMs and increasing the cost of side-channel protection [33].

Recent protocols (e.g. TLS 1.3 and KEMTLS) are designed to achieve forward security. In such protocols, each pair of ephemeral public/private keys is discarded immediately after being used once, and a new key pair will be generated for new messages. This means that an adversary will be able to request a decryption only once for a given key pair. Informally, IND-1-CCA security states that an adversary needs to distinguish an honestly generated key from a randomly generated key with at most one decapsulation query. Thus, the IND-1-CCA security of KEMs is sufficient to replace the Diffie-Hellman (DH) key-exchange, ensuring the security of such protocols. In the security proof of TLS 1.3 handshake under the multi-stage model given in [20], the DH key-exchange could be replaced by an IND-1-CCA KEM and the proof would still hold. This idea inspired a series of work, see [28, 30, 43, 44] for details.

[28] proposed that an IND-$q$-CCA-secure KEM could be obtained from any passively secure PKE (OW-CPA/IND-CPA) without re-encryption. Specifically, [28] presented two constructions named ${T_{CH}}$ and ${T_{H}}$, as well as their security proofs. Both ${T_{CH}}$ and ${T_{H}}$ do not require re-encryption and de-randomization, and such IND-1-CCA KEMs could be used in TLS 1.3 handshake, improving the efficiency while ensuring security. However, ${T_{CH}}$ leads to ciphertext expansion, and the security of ${T_{H}}$ was only proved in ROM, the QROM proof was not provided. Based on [28], [30] provided both ROM and QROM proofs of ${T_{H}}$ and ${T_{RH}}$ (an implicit variant of ${T_{H}}$), with much tighter reductions than [28].

5.2 IND-1-CCA KEM Constructions

In this section, we review the definition of ${T_{CH}}$ and ${T_{H}}/{T_{RH}}$, as well as their reduction tightness in ROM/QROM.
Constructions. The idea of ${T_{CH}}$ is to send an additional hash value along with ciphertext, which will be used for key confirmation in decapsulation (see Figure 4). ${T_{H}}$ works without additional hash value, the key is derived by $H(m,c)$ directly (Figure 5). ${T_{RH}}$ is an implicit variant of ${T_{H}}$, the only difference between ${T_{RH}}$ and ${T_{H}}$ is the return value for invalid decryption. In fact, ${T_{H}}$ and ${T_{RH}}$ is equivalent to ${U^{\bot}}$ and ${U^{\not\bot}}$ in [27], respectively.
Reduction Tightness. The security of ${T_{CH}}$ was proved in ROM and QROM by Huguenin-Dumittan and Vaudenay [28], with tightness ${\epsilon_{R}}\approx O(1/{q_{H}}){\epsilon_{\cal A}}$ and ${\epsilon_{R}}\approx O(1/{{q_{H}}^{3}})\epsilon_{\cal A}^{2}$ respectively, where ${\epsilon_{R}}$ (resp. ${\epsilon_{\cal A}}$) is the advantage of the reduction $R$ (resp. adversary ${\cal A}$) against the underlying PKE (resp. the IND-1-CCA KEM) and ${q_{H}}$ denotes the number of ${\cal A}$’s queries to $H$. Later, they updated an ePrint version of [28] and gave a tighter QROM proof of ${T_{CH}}$ with bound ${\epsilon_{R}}\approx O(1/{{q_{H}}^{2}})\epsilon_{\cal A}^{2}-O({{q_{H}}^{3}}/$. The ROM and QROM proof of ${T_{H}}$ and ${T_{RH}}$ were presented in [30], with tightness ${\epsilon_{R}}\approx O(1/{q_{H}}){\epsilon_{\cal A}}$ and ${\epsilon_{R}}\approx O(1/{{q_{H}}^{2}})\epsilon_{\cal A}^{2}$ respectively. The comparison between FO transform and ${T_{CH}}/{T_{H}}/{T_{RH}}$ is summarized in Table 1.

6.1 Experimental Setup

In this section, we describe our experimental setup. We used an emulation experiment setup in one machine. The benchmark platform is an Intel Xeon Platinum 8475B with 4 vCPUs and 8 GiB memory ¹¹1Our testing machine is provided by Alibaba Cloud, belonging to the compute-optimized instance family c8i. It is powered by an Intel Xeon Sapphire Rapids processor, with the specific specification ecs.c8i.xlarge, featuring 4 vCPUs and 8 GiB of memory.. The OpenSSL version we used is OpenSSL3.3.0-dev. We used GCC 9.4.0 to compile all programs. We disabled AVX-512 instructions when benchmarking ML-KEM AVX2 implementation for better comparison. We didn’t disable Turbo Boost and hyper-threading to simulate real-world conditions during TLS handshake.

6.2 Speed of ML-KEM AVX-512 Implementation

In this section, we conduct a performance evaluation of our ML-KEM AVX-512 implementations. Our approach is built upon the Crystals team’s open-source Kyber Standard Code [5], which was implemented for the FIPS 203 draft. To assess performance, we executed the speed testing program 100,000 times and recorded the median CPU cycle count. The results are summarized in Table 2, which compares various ML-KEM implementations across three security levels. Our implementation achieved a speedup ratio ranging from approximately 1.30$\times$ to 1.64$\times$ compared to the state-of-the-art AVX2 implementation. This performance enhancement can be attributed to the intricate design of our NTT AVX-512 implementation and the vectorization benefits offered by AVX-512 instructions. As illustrated in Table 2, adopting batch method in Section 4.1 can accelerate the key generation process by 3.5$\times$ to 4.9$\times$.

6.3 ML-KEM AVX-512 TLS 1.3 Benchmark

We evaluated the performance of TLS 1.3 handshakes integrated with the ML-KEM AVX-512 implementation in a simulated network environment. Initially, we utilized OpenSSL commands to generate key pairs and server certificates. Subsequently, utilizing the previously generated keys and certificates, we launched a TLS server via the openssl s_server tool [3]. We assessed the handshake connections per second using the openssl s_time tool [4]. Both the server and client were compiled against OpenSSL3.3.0-dev with the OQS provider, thus facilitating support for both hybrid mode and PQ-only mode.
PQ-only ML-KEM PQ-TLS 1.3 Benchmark. In TLS, we mainly observe the ML-KEM algorithm for KEX. However, there are multiple signature algorithms available, each with different security levels. Therefore, observing the combination of different signature algorithms with ML-KEM is crucial and worth considering. For our experiments, we selected three signature algorithms: the standardized post-quantum signature algorithms Dilithium and Falcon, as well as the traditional public key cipher RSA2048.

As shown in Table 3, under PQ-only setting, AVX-512 implementation of ML-KEM brings more handshakes per second compared to AVX2 implementation. This indicates that using AVX-512 to optimize ML-KEM performance can bring improvement to the PQ-TLS handshake. However, the improvement is subtle. Since handshake time is not solely determined by KEX time but also influenced by factors such as transmission time and authentication time, improving the performance of the ML-KEM algorithm does not lead to a significant enhancement in overall handshake time performance. Besides, the handshake time decreases as the security level increases. This is in line with expectations because higher security levels typically result in a slower speed of signature and KEM. Overall, using Dilithium as the signature authentication scheme performs better in handshakes compared to Falcon under the same security level. Compared to RSA2048, using the Dilithium and Falcon post-quantum signature schemes for authentication does not impose significant performance overhead. These conclusions provide insights into the impact of different signature algorithms combined with ML-KEM on TLS handshake performance and serve as a reference for selecting the optimal solution.
Hybrid ML-KEM PQ-TLS 1.3 Benchmark. OQS provider facilitates hybrid key exchange for TLS 1.3 by the IETF draft on Post-Quantum Traditional Hybrid Schemes [29]. Consequently, we also evaluated the performance of ML-KEM and other ECDH curves hybrid schemes. The data from Table 4 indicates a significant decrease in handshake performance in hybrid mode compared to the PQ-only mode. Furthermore, the enhancement in handshake performance achieved through the AVX-512 implementation is minimal. This phenomenon may be attributed to the fact that in hybrid mode, the handshake time is primarily composed of two components: ECDH and ML-KEM. Therefore, solely improving the performance of ML-KEM in hybrid mode is insufficient; there is also a need to enhance the performance of the ECDH scheme.

6.4 TLS 1.3 Handshake with IND-1-CCA KEM

In this section, we implemented IND-1-CCA KEMs based on ${T_{CH}}$ and ${T_{RH}}$ constructions proposed in [28] and [30], integrated the better one into TLS 1.3 and analyzing its performance.
Comparison of KEM Constructions.We constructed two IND-1-CCA KEMs based on the underlying PKE of ML-KEM, employing ${T_{CH}}$ and ${T_{RH}}$ respectively. Both ${T_{CH}}$ and ${T_{RH}}$ utilized SHA3-256 to instantiate the hash function H, consistent with the original $FO$ transform in ML-KEM. Additionally, we fixed the length of the $tag$ in ${T_{CH}}$ to 32 bytes. The results are summarized in Table 5, which compare the execution speed and communication overhead across three constructions (ML-KEM’s original $FO$ construction, ${T_{CH}}$ and ${T_{RH}}$). From the experiment results, the following facts are concluded.For key-generation and encapsulation, ${T_{CH}}$ and ${T_{RH}}$ show rational improvement in efficiency, mainly because they omit the hash of $pk$ in key-generation, as well as the de-randomization in encapsulation. For Decapsulation, ${T_{CH}}$ and ${T_{RH}}$ achieve a speed ratio of at least 3.04$\times$ compared to $FO$ implementation, which can be attributed to removing re-encryption. The improvement becomes more significant as the security level increases because higher security levels result in slower encryption. ${T_{CH}}$ requires extra 32 bytes in ciphertext storage, and ${T_{CH}}$’s decapsulation is slightly slower than ${T_{RH}}$ due to the key confirmation. Overall, KEMs based on ${T_{RH}}$ show better performance in both efficiency and communication overhead.

IND-1-CCA KEM TLS 1.3 Benchmark.The ${T_{RH}}$-based IND-1-CCA KEM is integrated into TLS 1.3 in both PQ-only mode and hybrid mode. We measured the number of handshakes per second and compared the results with the original $FO$ implementation, shown in Table 6.

The results show that ${T_{RH}}$-based IND-1-CCA KEMs increase the number of TLS 1.3 handshakes per second while maintaining communication overhead. Especially in the PQ-only mode with a higher security level, the removal of re-encryption brings more significant improvement, which is in line with our expectations.

Our experiments confirm the advantages of applying IND-1-CCA KEMs in TLS 1.3 at a practical level. Specifically, in application scenarios that place more emphasis on handshake efficiency, IND-1-CCA KEMs have better adaptability than $FO$-based IND-CCA KEMs. These results inspire further research on IND-1-CCA constructions (e.g. tighter reduction) and their TLS 1.3 implementation.