hpqc - hybrid post quantum cryptography library

By David Stainton | Friday, April 12, 2024

Tags:

The Katzenpost developement team has recently released a new golang cryptography library known as hpqc. The theme of the library is hybrid post quantum cryptographic constructions, namely:

hybrid KEMs (key encapsulation mechanism)
hybrid NIKEs (non-interactive key exchange)
hybrid signature schemes

In each of the three main subdirectories, “kem”, “nike” and “sign” there exists interface definitions for Scheme, PrivateKey and PublicKey. For signature schemes and KEMs we’re borrowing the interface sets from cloudflare’s circl library.

And each of these subdirectories has a schemes package where all the imeplementations are registered and can be referenced by unique string name, take for examples the KEM schemes documentation. However the implementations that are registered don’t show up in the API docs but we can see them in the source code.

hpqc gives you the power to compose an arbitrary number of KEMs and NIKEs, for example the above source file defines many KEMs in composition like this one:

	combiner.New(
		"X25519-mlkem768-ctidh512",
		[]kem.Scheme{
			adapter.FromNIKE(x25519.Scheme(rand.Reader)),
			mlkem768.Scheme(),
			adapter.FromNIKE(ctidh512.Scheme()),
		},
	),

This library makes seven unique contributions in golang:

a set of generic NIKE interfaces for NIKE scheme, public key and private key types

NIKE interfaces documentation source code

These are useful for making your cryptographic protocol not rely on a specific NIKE such as an elliptic curve diffiehellman function like x25519 or x448.

generic hybrid NIKE, combines any two NIKEs into one

NIKE hybrid scheme documentation source code

Many cryptographic protocols can use a hybrid post quantum NIKE in place of a NIKE. Here the NIKE interfaces are satisfied by this hybrid scheme type.

security preserving KEM combiner

security preserving KEM combiner documentation source code

Our security preserving KEM combiner can combine an arbitrary number of KEMs althought it’s usually useful enough to combine just two KEMs. We get our design from the KEM Combiners paper which makes the observation that if a KEM combiner is not security preserving then the resulting hybrid KEM will not have IND-CCA2 security if one of the composing KEMs does not have IND-CCA2 security. Likewise the paper points out that when using a security preserving KEM combiner, if only one of the composing KEMs has IND-CCA2 security then the resulting hybrid KEM will have IND-CCA2 security.

Our KEM combiner uses the split PRF design for an arbitrary number of KEMs, here shown with only three, in pseudo code:

func SplitPRF(ss1, ss2, ss3, cct1, cct2, cct3 []byte) []byte {
    cct := cct1 || cct2 || cct3
    return PRF(ss1 || cct) XOR PRF(ss2 || cct) XOR PRF(ss3 || cct)
}

a “NIKE to KEM adapter” which uses an ad hoc hashed elgamal construction

NIKE to KEM adapter documentation source code

It is very common in modern hybrid post quantum cryptographic protocol constructions to see a NIKE adapted into a KEM and then combined with a post quantum KEM.

Our ad hoc hashed elgamal construction for adapting any NIKE to a KEM is, in pseudo code:

func ENCAPSULATE(their_pubkey publickey) ([]byte, []byte) {
    my_privkey, my_pubkey = GEN_KEYPAIR(RNG)
    ss = DH(my_privkey, their_pubkey)
    ss2 = PRF(ss || their_pubkey || my_pubkey)
    return my_pubkey, ss2
}

func DECAPSULATE(my_privkey, their_pubkey) []byte {
    s = DH(my_privkey, their_pubkey)
    shared_key = PRF(ss || my_pubkey || their_pubkey)
    return shared_key
}