[noise] Post-Quantum Noise with New Hope

[Rhys Weatherley]

On Sat, Jul 16, 2016 at 4:44 AM, Trevor Perrin <trevp at trevp.net> wrote:

>
> The Noise spec actually has no definition of what a DH() function should
> do!  That needs fixing, e.g. with terms like "Non-Interactive Key Exchange"
> (NIKE) and "Gap-DH" or something to justify key reuse.
>

Yep.

>
> NewHope wouldn't meet those criteria:
>  * Unlike a NIKE, NewHope required ordered messages: one party presents a
> public key, and the other party gives them a value they can derive a shared
> secret from.  Rhys finesses this ("unbalanced" vs "balanced" DH), but I
> sort of feel that "balanced" aka "non-interactive" is the essence of DH.
> Instead, NewHope seems more like a One-Pass Key Exchange (OPKE) or Key
> Encapsulation Method (KEM) [1].  The KEM term is used in related works
> (NewHope also uses it, so does NTRU-Prime [2], and Peikert [3]).
>

"KEM" is fine by me.

I realised this morning that old school modexp-DH can be either "balanced"
or "unbalanced".  If the group prime and generator are agreed to ahead of
time by Alice and Bob, then the system is "balanced".  But if the
parameters are dynamic and sent by Alice in the handshake, then it becomes
"unbalanced".  I believe that TLS uses modexp-DH this way for forward
secrecy.

We've been spoilt by Curve25519/448 in which all group parameters are fixed
by the algorithm definition.  But that's actually unusual for DH schemes,
not the norm.  Schemes can have their parameters fixed to make them
"balanced", but New Hope explicitly rejects parameter fixing.

(3)  Add new tokens for NewHope, and other post-quantum options.  For
> example:
>
>   "ekem1" - Sends the first NewHope message, or a similar one-time public
> key from (SIDH, NTRU-Prime, etc).  Encrypts the value if "k" is present.
>
>   "ekem2" - Sends the second NewHope message, or a similar encapsulated
> key, that is combined with "ekem1" to produce a 32-byte key which is
> provided to MixKey().  Encrypts the value if "k" is present.
>

Great minds.  This is actually similar to my original thoughts on using New
Hope.  Initially, I was thinking of special "qa" and "qb" tokens but once I
found a way to implement "qa = e", and "qb = e, dhee" I set it aside in
favour of making the least number of changes to the structure of Noise.
And like you I wasn't sure whether such tokens would end up being specific
to New Hope.

I'd definitely be on board with (3) - it would be simpler to get right than
nested handshakes and SSK's.

Cheers,

Rhys.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20160716/8364a111/attachment.html>