---
title:      'Noise Extension: Hybrid Forward Secrecy with Kyber'
author:     'Rhys Weatherley (rhys.weatherley@gmail.com)'
revision:   '1draft'
date:       '2017-07-03'
---

1. Introduction
---------------

This document describes the post-quantum key exchange algorithm Kyber
and provides information for using it with the Noise protocol and the
Hybrid Forward Secrecy extension.

Kyber [1] is a post-quantum key-encapsulation mechanism (KEM) based on
the hardness of Module-LWE (Learning With Errors).

The KEM is similar in behaviour to the classical RSA algorithm in that
Alice generates a random value, encrypts it with the Bob's public key,
and then sends that to Bob.  Using his public key, Bob can recover the
random value and decrypt any ciphertext that follows.

With the reference implementation of Kyber [2], public keys are 1088 bytes
in size, private keys are 1248 bytes in size, and the encrypted ciphertext
values are 1184 bytes in size.  The result is a 32-byte shared secret.

In this extension, the initiator generates a Kyber keypair and sends
the public key to the responder.  The responder generates a random shared
secret and encrypts it with the public key.  The encrypted value is sent
back to initiator who decrypts it with their private key to recover the
shared secret.  At the end of the Noise handshake, all key values are
discarded.

Other HFS primitives such as 25519, 448, and NewHope derive an emphemeral
shared secret through mutual agreement with both parties possessing a
keypair.  The Kyber CCA transform that we use here has mutual/contributory
behaviour as well despite only using a single keypair: both parties contribute
to the final result and neither party can solely determine the value of
the shared secret.

2. Definition of `Kyber` for use in Noise
-----------------------------------------

The name of the algorithm shall be `Kyber`.

In this definition, we use the function names from the `kem.c` file
in the reference implementation of Kyber [2]:

 * `crypto_kem_keypair()` returns the 1088-byte public and 1248-byte private
   components of a new random keypair.
 * `crypto_kem_enc()` generates a 1184-byte ciphertext and a 32-byte secret
   given a remote 1088-byte public key.
 * `crypto_kem_dec()` recovers a 32-byte secret given a 1184-byte ciphertext
   and a local 1248-byte private key.

The function and constants for hybrid forward secrecy are defined
formally as follows:

 * **`GENERATE_KEYPAIR_F(rf)`**:
   * If `rf` is empty, then set `f.public_key` and `f.private_key`
     to the result of `crypto_kem_keypair()`.
   * If `rf` is not empty, then set `f.public_key` and `f.shared` to
     the ciphertext and shared secret that result from calling
     `crypto_kem_enc()` with `rf.public_key`.

 * **`FF(key_pair, public_key)`**: If `key_pair` was generated by
   `GENERATE_KEYPAIR_F(rf)` with an empty `rf`, then return the result of
   `crypto_kem_dec(key_pair.private_key, public_key)`.  Otherwise
   return `key_pair.shared` and ignore `public_key`.

 * **`FLEN1`** = 1088

 * **`FLEN2`** = 1184

 * **`FFLEN`** = 32

3. Examples
-----------

The following are examples of protocol names involving Kyber:

 * `Noise_XXhfs_25519+Kyber_AESGCM_SHA256`
 * `Noise_XXfallback+hfs_448+Kyber_ChaChaPoly_BLAKE2b`

4. Discussion
-------------

Kyber has support for static keys in addition to the ephemeral key
mechanism described above.  This extension does not currently describe
how Kyber could be used with static keys in Noise, although we
certainly do not rule out the possibility.

The formulation here is a little odd in that it is trying to use a KEM
to perform the role of an ephemeral DH-like function.  If Noise had native
support for KEM functions, perhaps though the addition of new tokens,
then it would be easier to incorporate Kyber into Noise with both
ephemeral and static key roles.

5. References
-------------

[1] Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky,
John M. Schanck, Peter Schwabe, and Damien Stehlé [CRYSTALS – Kyber: a CCA-secure module-lattice-based KEM](https://cryptojedi.org/peter/index.shtml#kyber).

[2] [Reference implementation of Kyber](https://github.com/pq-crystals/kyber).