We Need Non-Interactive Post-Quantum KEMs

Design a system that allows you to encrypt data online, but only decrypt it offline (i.e. in an airgapped environment).

If you’re in the world of symmetric cryptography, this is impossible. Fortunately, we can use asymmetric cryptography to accomplish this goal.

In the 2000’s, your design might have looked like this:

  1. Generate a 128-bit random key k.
  2. Encrypt k with an RSA public key p to obtain w.
  3. Encrypt the message m with k, using AES-CBC, to obtain c.
  4. Store w, c for offline decryption, wipe k from memory.

Since 2015, your approach might have shifted a bit:

  1. Generate an ephemeral ECDH keypair (sk_e, pk_e).
  2. Perform a scalar multiplication of the ephemeral secret key sk_e with the recipient’s public key pk.
  3. Hash the output of step 2 as a 256-bit random key, k.
  4. Encrypt the message m with k, using an AEAD mode, to yield (c, t).
  5. Store (pk_e, c, t) for offline decryption, wipe k from memory.

Different approaches, different algorithms, but the same workflow works in both cases. We’re using asymmetric cryptography to somehow manage the symmetric key used for actual message encryption. As long as our asymmetric algorithms are secure, and our keys are kept away from attackers, this approach is secure.

This was made possible because RSA encryption and ECDH key agreement are both non-interactive protocols that operate with static keypairs.

The CRQC Has Entered the Facility

Unfortunately, a Cryptography-Relevant Quantum Computer (CRQC) defeats both RSA and ECDH and renders the above algorithms insecure.

NIST and Post-Quantum Cryptography

In response to the looming threat of a CRQC, NIST has been working with the cryptography community to standardize post-quantum asymmetric cryptography (KEMs and signature algorithms).

At the end of Round 3, some algorithms are being standardized and a few more are being studied.

NIST Post-Quantum Round 3 Finalists

  • KEMs:
    • CRYSTALS-Kyber
  • Signatures:
    • CRYSTALS-Dilithium
    • FALCON
    • SPHINCS+

NIST Post-Quantum Round 4 Candidates

  • KEMs
    • BIKE
    • Classic McEliece
    • HQC
    • SIKE

Which KEMs Are Non-Interactive?

Let’s start with the Round 3 KEM finalist: Kyber. From this document:

Using IND-CCA2 security by default makes it safe to use Kyber with static keys and as a consequence also to re-use ephemeral keys for some time.

If you can use Kyber with static keys, it logically follows that you can use Kyber in a non-interactive setting without facing insecurity.

So, y’know, good job, NIST!

However, this isn’t true of many Round 4 candidates.

BIKE

Key reuse or adapting BIKE to asynchronous protocols (e.g. email) require to secure long term static keys. Those usage models are possible but no longer provides forward secrecy and require IND-CCA security. Note that they are not compliant with BIKE’s current specification.

BIKE Specification

Static keys are a no-go with BIKE.

Classic McEliece

The cryptanalysis literature is unclear on the security of Classic McEliece with static keys, but the authors claim IND-CCA2.

However, the enormous public key sizes make it less attractive than alternatives.

HQC

Static keys are discussed briefly by the specification, but there are attacks against static keys against HQC and BIKE.

SIKE

You should not use SIKE with static keys.

Considerations for Round 4 and Beyond

Although it’s currently believed that CRYSTALS-Kyber is sufficient for non-interactive use cases, we’re putting a lot of eggs in one basket.

If Kyber is ever broken by cryptanalytic advancement, then we will need to ensure the alternatives we consider aren’t limited to the TLS use-case.

As it stands today, Classic McEliece is the only Round 4 candidate that might be safe for these use cases if Kyber is broken.

Do We Really Need Offline Decryption?

Yes, and for reasons beyond keeping email encryption on life support.

A lot of systems implement this today with RSA. You’re leaving a lot of commercial use-cases in the dark if you don’t support non-interactive key exchanges in your scope.

Post-Quantum security is important for TLS, and I don’t want to diminish the work that’s been done already, but it’s not important for only TLS.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: