[noise] Post-Quantum Noise with New Hope

[Rhys Weatherley]

On Sat, Jul 16, 2016 at 8:34 PM, Trevor Perrin <trevp at trevp.net> wrote:

>  * Maybe we should clarify which tokens are data and which are
> computations in the notation, e.g. capitalization?
>

> Noise_XX(s, rs):                 Noise_XXekem(s, rs):
>   -> e                             -> e, ekem1, s
>   <- e, DHEE, s, DHSE              <- e, ekem2, DHEE, EKEM21, s, DHSE
>   -> s, DHSE                       -> s, DHSE
>

Arrgh!  My handshake is shouting at me! :-)

I don't think it helps to say "keys are generated here and computation
happens there".  "ekem21" is where the result of the computation is mixed
into the chaining key, but the actual computation can happen as soon as the
side is in possession of a local private key and a remote public key
relevant to the "dhxy" or "ekemxy" token. e.g. Ahead-of-time computation in
a background thread on multi-core CPU's.

 * Schemes like NTRU Prime allow reusable keys.  We might be able to extend
> our naming convention for that with "skem".  I.e., you could do mutual
> post-quantum auth as well as forward-secrecy with something like:
>
> Noise_XXskem(s, rs):
>   -> e, ekem1
>   <- e, ekem2, DHEE, EKEM21, s, DHSE, skem1
>   -> skem2, SKEM21, s, DHSE, skem1,
>   <- skem2, SKEM21
>

I think at that point it might be simpler to run two Noise_XX() handshakes
in parallel and mix them with SSK's.  Or just switch completely to a
post-quantum "XX" and drop the classical handshake.

How about we apply some KISS?  The odd one out is ekem: there is a need for
adding another ephemeral-only exchange for obtaining extra forward secrecy
from a different algorithm.

Noise_XXf(s, rs):
    -> e, f
    <- e, f, dhee, dhff, s, dhse
    -> s, dhse

Where "f" stands for "forward secrecy ephemeral".

The "f" algorithm doesn't have to be post-quantum.  I can see a use for
"25519+448" where 448 is used to add extra forward secrecy to strengthen
25519-based handshakes: 128-bit level authentication with 224-bit level
secrecy.

Here, "dhff" is the point where the computation is mixed in, but it is
implementation-specific as to where it is convenient to perform that
computation.  Maybe "mixff" instead of "dhff" if you don't want to imply
that the algorithm is DH.

This could be extended to SKEM by adding "g", "dhgg", "dhfg", and "dhgf"
tokens where "g" is fulfilling the "s" role for the post-quantum part of a
mixed handshake.

I had a quick look at SIDH: it is more balanced with keypairs generated
separately from each other.  The wrinkle is that Alice and Bob use
different algorithms to generate their private keys and to perform the
later shared secret computations.  But we could handle that with some rule:
"the initiator is Alice and the responder is Bob; reversed for fallback
patterns".  If SIDH is used for ekem only, then the rule can be "whoever
goes first is Alice".

Cheers,

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