<div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Aug 4, 2022 at 4:11 PM Viktor Dukhovni <<a href="mailto:cryptography@dukhovni.org">cryptography@dukhovni.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Sun, Jul 31, 2022 at 11:11:49AM -0400, Phillip Hallam-Baker wrote:<br>
<br>
> I am trying to get some info on the mechanism underlying NIST's chosen key<br>
> exchange, Kyber. [...]<br>
> <br>
> So does anyone have a pointer to a YouTube with a good description of the<br>
> Lattice crypto approach? Just telling me something is a lattice is really<br>
> telling me nothing at all. It might as well be a Hausdorffian Manifold with<br>
> Lipschitz signature.<br>
<br>
Do you really want to open the black box, or are you looking for a<br>
better description of the knobs on the front panel?  My guess is mostly<br>
the latter...<br></blockquote><div><br></div><div><div class="gmail_default" style="font-size:small">Actually, I am trying to understand what I now believe was misunderstanding </div><div class="gmail_default" style="font-size:small">on the part of the cryptographers supposedly providing an explanation.</div><br></div><div><div class="gmail_default" style="font-size:small">The NIST competition has a very specific interface which is indeed a black box </div><div class="gmail_default" style="font-size:small">that can slot into the same hole that is already in my code.</div><br></div><div><div class="gmail_default" style="font-size:small">What people seem to have provided in the 'explanations' is explanations of </div><div class="gmail_default" style="font-size:small">what is inside the box. The Kyber algorithm is a Key Encapsulation, it has </div><div class="gmail_default" style="font-size:small">plaintext recovery. But the NIST interface requires this to be wrapped so </div><div class="gmail_default" style="font-size:small">that what we actually have doesn't allow the key to be chosen by the encryptor.</div><div class="gmail_default" style="font-size:small"><br></div></div><div class="gmail_default" style="font-size:small"></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
The main difference is that with DH, if you know the recipient's public<br>
key, you can perform the agreement without the recipient's help.  With<br>
Kyber, none of the the published protocols in figures 1, 2 and 3 on page<br>
8 of:<br>
<br>
    <a href="https://eprint.iacr.org/2017/634.pdf" rel="noreferrer" target="_blank"><span class="gmail_default" style="font-size:small"></span>https://eprint.iacr.org/2017/634.pdf</a><br>
<br>
seem to make it possible to encapsulate a key without a full round-trip.<br>
But it should be noted that figure 1 is ephemeral-ephemeral, while<br>
figures 2 and 3 are *authenticated* key agreement protocols.<br></blockquote><div><br></div><div><div class="gmail_default" style="font-size:small">And that paper is 2017 and the algorithm that was selected was not the one</div><div class="gmail_default" style="font-size:small">in the paper, there is a wrapper around the IND-CPA functions.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><div class="gmail_default">People have been telling me that Kyber requires a complete redesign of</div><div class="gmail_default">existing systems and that does not appear to be the case at all.</div></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">So yes I do actually need to understand more than just the black box because </div><div class="gmail_default" style="font-size:small">there are actually two boxes at issue here. There is an outer box which is the </div><div class="gmail_default" style="font-size:small">one that NIST selected and there is an inner box. </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The confused commentary being provided is coming from people who are </div><div class="gmail_default" style="font-size:small">making incorrect assertions about what the algorithm is actually capable of </div><div class="gmail_default" style="font-size:small">based on using the IND-CPA primitive directly rather than the KEM-ENC</div><div class="gmail_default" style="font-size:small">wrapper selected by NIST.</div></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div></div></div></div>