X-Wing: PQC Key Encapsulation, But Better

X-Wing: PQC Key Encapsulation, But Better

We are migrating away from ECDH towards a post-quantum method. This involves the usage of key encapsulation, and where we generate a secret key which is encapsulated by a public key and then decapsulated by an associated private key. While ML-KEM is the method of choice at the moment, it is likely that we will use a hybrid method, such as ML-KEM768 and X25519.

X-Wing is one solution to this, and is optimised to use X25519 and ML-KEM-768 [here][1]:

Overall, the paper demonstrates that X-Wing exhibits excellent performance levels and is secure if either X25519 or ML-KEM-768 is secure. The main difference between X-Wing and the X25519Kyber768 standard [here] is:

At the present time, X-Wing is being drafted by the IETF [here]:

The main steps are:

sk,pk= ML-KEM-768.KeyGen_internal(z): Generate a deterministic key pair from a 32-byte seed value (z).

ss,ct = ML-KEM-768.Encaps(pk, w): Encapsulate a secret (ss) into the ciphertext (ct) using a public key (pk) and a seed (w). The ciphertext is deterministic.

ss2= ML-KEM-768.Decap(ct sk): Recover a shared secret (ss2) from a ciphertext (ct) using the private key (sk).

This can be illustrated with:

The Golang code for this is [here]:

package main

import (

 "fmt"
 "math/rand"
 "github.com/cloudflare/circl/kem/xwing"
)


func main() {


 seed := make([]byte, 32)
 rand.Read(seed)

 sk, pk := xwing.DeriveKeyPairPacked(seed)

 eseed := make([]byte, 64)
 rand.Read(eseed)

 ss, ct, _ :=xwing.Encapsulate(pk, eseed)

 ss2 := xwing.Decapsulate(ct, sk)


 fmt.Printf("Seed for keys %x\n\n", seed)
 fmt.Printf("Seed for encapsulation %x\n\n", eseed)
 fmt.Printf("PK (first 100 bytes) %.200x (size=%d bytes)\n\n", pk,len(pk))
 fmt.Printf("SK %x (size=%d bytes)\n\n", sk,len(sk))

 fmt.Printf("Cipher (first 100 bytes): %.200x (size=%d bytes)\n\n", ct,len(ct))

 fmt.Printf("Shared secret (generated) %x\n\n", ss)
 fmt.Printf("Shared secret (decapsulated) %x\n\n", ss2)


}

and a sample run is [here]:

Seed for keys 443d6bf9fd37c9b3fbcb641206216662bbe188da987b87086e28e10f5899a1ee

Seed for encapsulation d429878feb6adbe4d20209c8dff8cb83ede58ef1b4c65ceb27a06d57baf8746a1faba4a85d020361e22956dc89251c6ed79b925618d89430122c55c97968d306

PK (first 100 bytes) 19dc2f25a48dd4f8520a97cbf0e48e805428a00364cbb63f06379a45
b53ba3b662029c8af5f12ba7a5bd68bb62971657cf33466ad295ca7557baf951486711e204c7
1e65622dc4761c5c723777c10b7051ed40bb6b23c46aea2a5f579e00938d1c2722268b2ee6847
14658b453b4bce7a844055c31ac962488445646bc91a67ac96c42ca304a70a719873836c2fe9
2422a2b564e1387cf622e51a1360f13c500c5c9bed92422627d7086462cc26a8d744dc330323
6549bb32a3ee0492a62d4239e73024ab8b3374b (size=1216 bytes)

SK 443d6bf9fd37c9b3fbcb641206216662bbe188da987b87086e28e10f5899a1ee (size=32 bytes)

Cipher (first 100 bytes): d0c62d70fc6e7ac9058edf6be7017df61a09d98146bee2f9469
76a45a3e7be57f4be5896139fd9ebb99cec7febad80ef4598297bd5a6b617a3aae07448e6083
e02820dcbcca0731ff5db2533894fe3629ad7642589eba33e5fe92535291d4c912230ff009d
f1c4442b16f3e8bc18bccb1f1baa23af3992a037d4aafb36a637653c7caf711eb09e33cfbbad
4633ffd3eb6f5b38b156d3a17615a371cf1d9607ef9fc5b7b624fc814636f88499230c1f9970
f4fbce0584b07680340d53c47ba922d18d69a2cf4338e9 (size=1120 bytes)

Shared secret (generated) 1be72faba7b4a6eea842d56e1d63229abdcb212b98defb46735a45aaaf81f4db

Shared secret (decapsulated) 1be72faba7b4a6eea842d56e1d63229abdcb212b98defb46735a45aaaf81f4db

In this case, we can see that the public key is 1,216 bytes long, the ciphertext is 1,120 bytes long, and the private key is only 32 bytes long (as it is hashed). Normally, in ML-768, the public key is 1,184 bytes long, the private key is 2,400 bytes long, and the ciphertext is 1,088 bytes long. These key sizes are defined the paper with [1]:

References

[1] Barbosa, M., Connolly, D., Duarte, J. D., Kaiser, A., Schwabe, P., Varner, K., & Westerbaan, B. (2024). X-wing: The hybrid kem you’ve been looking for. Cryptology ePrint Archive.