[noise] Post Quantum SIDHp751 with Noise

[Trevor Perrin]

On Fri, Jul 22, 2016 at 11:41 PM, Rhys Weatherley <rhys.weatherley at gmail.com
> wrote:

> The "sidh" branch in Noise-C now contains a back-end for SIDHp751
>
[...]

> SIDHp751 is a full Diffie-Hellman scheme, supporting both ephemeral and
> static public keys, so all Noise handshake patterns are possible.  I've
> added a page to the wiki [3] providing the details.  There are some
> suggestions there as to how to modify the Noise specification to better
> accommodate post-quantum algorithms.
>
[...]

> If we are looking to only add post-quantum forward secrecy to Noise at the
> moment, New Hope looks like the better bet.
>
[...]

> [1] https://www.microsoft.com/en-us/download/details.aspx?id=52438
> [2] https://eprint.iacr.org/2016/413.pdf
> [3]
> https://github.com/noiseprotocol/noise_wiki/wiki/Post-Quantum-Noise-with-SIDHp751
>


Great work and writeup!

The fact that SIDH key pairs are generated specifically for either the
"Alice" or "Bob" role is an interesting twist.  You make a good observation
that Noise with SIDH could still support all patterns if each party has a
doubled static "keypair" that contains both "Alice" and "Bob" SIDH
keypairs, and uses one or the other, as needed.

At the PETS conference I talked with Peter Schwabe, Isis, and others about
PQ key exchange, and Peter mentioned this same idea (attributing it to MSR).

That's not exactly the same as "doubling" the ephemeral for 25519+NewHope,
but it's another case of redefining the "e" and "s" tokens to contain a
tuple of public keys.  So I think that's turning out to be a good approach
(as opposed to defining new tokens).

For the near term, I agree that NewHope / RLWE is faster, more-studied, and
sufficient to the immediate goal of forward-secrecy.  It's also the
algorithm Tor is most interested in, so if we flesh out a NewHope extension
we can pitch it to them, and possibly get some real deployment.


Your proposed spec extensions make sense, but the Alice and Bob labelling
seems somewhat specific to SIDH, so there's a question whether extensions
like this should be:

 (a) integrated into the main pseudocode in the main spec
 (b) described in a separate section of the main spec (like PSK or SSK)
 (c) described in a separate extension document

I lean away from (a) because I worry the spec is already too long.  I think
Noise is fundamentally simple, but it will help people appreciate that
simplicity if we cordon off new concepts (like "Alice" and "Bob" labelling)
into a separate section - or, probably better, a separate document.


Assuming we want to work on a NewHope extension, we could either work in
the Wiki, or store it in Git using similar document structure to the main
spec (e.g. Pandoc markdown).  Since they're both Markdown, maybe we should
start fleshing that out on the Wiki, with the idea of moving to Git /
Pandoc later, once we establish more processes for that?


Trevor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20160724/d718bd11/attachment.html>