[Cryptography] Kyber PQC Key Exchange

[Viktor Dukhovni]

On Sun, Jul 31, 2022 at 11:11:49AM -0400, Phillip Hallam-Baker wrote:

> I am trying to get some info on the mechanism underlying NIST's chosen key
> exchange, Kyber. [...]
> 
> So does anyone have a pointer to a YouTube with a good description of the
> Lattice crypto approach? Just telling me something is a lattice is really
> telling me nothing at all. It might as well be a Hausdorffian Manifold with
> Lipschitz signature.

Do you really want to open the black box, or are you looking for a
better description of the knobs on the front panel?  My guess is mostly
the latter...

NIST have not yet published the actual standard, they've only announced
the winning algorithms, and some work remains to be done to pin down the
details.

> I am told that I can't use Kyber as a drop in for ECDH because it is
> an interactive key exchange. The API seems to suggest otherwise. From
> a protocol design point of view, there is really no difference between
> a Key Agreement and a Key Encapsulation that can't be fixed with a bit
> of Key Wrap.

The main difference is that with DH, if you know the recipient's public
key, you can perform the agreement without the recipient's help.  With
Kyber, none of the the published protocols in figures 1, 2 and 3 on page
8 of:

    https://eprint.iacr.org/2017/634.pdf

seem to make it possible to encapsulate a key without a full round-trip.
But it should be noted that figure 1 is ephemeral-ephemeral, while
figures 2 and 3 are *authenticated* key agreement protocols.

> The use case I have in mind is:
> 
> 1) Alice exchanges public keys with Bob.
> 2) Alice writes a Word document and encrypts to Bob's public key
> 3) Alice puts enveloped Word document on thumb drive and mails it to Bob
> 4) Bob gets the thumb drive and decrypts the document.

You seem to be looking for an unauthenticated static-ephemeral protocol,
where the sender's message is signed (authenticated) separately, and
perhaps then the sender can derive the shared key without an interaction
with the recipient.

This reënforces the guess that you're not looking for explanations of
internals of "module learning with errors" cryptosystems, but rather
a more detailed exposition of the available protocols and supported
use-cases.

We'll see whether one of these supports zero-RTT static-ephemeral key
exchange.

-- 
    Viktor.

P.S. A very simplified view into the black box is at:

    https://cryptopedia.dev/posts/kyber/