[Cryptography] Kyber PQC Key Exchange

[Stephan Mueller]

Am Sonntag, 31. Juli 2022, 17:11:49 CEST schrieb Phillip Hallam-Baker:

Hi Phillip,

> I am trying to get some info on the mechanism underlying NIST's chosen key
> exchange, Kyber. So far the most accessible explanation is the Python
> implementation.
> 
> If we are going to adopt a new approach to public key, some of us will want
> to understand it. And academic papers that spend the entire time
> referring to the differences with the previous papers are really no help at
> all.
> 
> 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.
> 
> At least some of the information I have received is inconsistent. 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 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.

I have integrated Kyber into my small little crypto library. During that 
process, unfortunately I have not fully understood yet what mathematical 
problem truly is the heart of the issue that is not solvable without the keys.

But I have fully documented the Kex operation in [1] and [2] which should 
answer your 2nd part of your question.
> 
> From what was said at the CFRG meeting, I was expecting I might have to do
> an El Gamal like move and create an ephemeral key pair per document to
> encrypt. But that doesn't seem to be the case looking at the API.

It is creating an ephemeral key, see [1] and [2].
> 
> Then I find mention of 'malleability' which seems utterly odd to me since
> that is an integrity issue and not a confidentiality concern. And I can't
> find the word 'malleable' in the paper.
> 
> From my point of view as a protocol designer, I am really not in the least
> bit concerned about the key sizes, ~1500 bytes is only a concern if you
> need to squeeze public keys into a single Ethernet packet and only then
> because the IEEE can't pull its finger out and give us 64K frames. [That is
> easier than they imagine, just limit the CRC check to the first 1000 bytes
> of a packet so that it covers the headers and allows misrouting of packets
> to be avoided. Payload integrity is now a transport concern.]

[1] Unilateral: https://github.com/smuellerDD/leancrypto/blob/master/kem/api/
lc_kyber.h#L171

[2] Authenticated: https://github.com/smuellerDD/leancrypto/blob/master/kem/
api/lc_kyber.h#L280
> 
> 
> NIST announcement
> NIST Announces First Four Quantum-Resistant Cryptographic Algorithms | NIST
> <https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-qua
> ntum-resistant-cryptographic-algorithms>
> 
> Kyber home page
> Kyber (pq-crystals.org) <https://pq-crystals.org/kyber/index.shtml>
> 
> Kyber submission
> kyber-specification-round3-20210804.pdf (pq-crystals.org)
> <https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf>


Ciao
Stephan