On Wed, Aug 5, 2015 at 7:35 AM, Jeff Burdges <[email protected]> wrote: > > Question : Can we design a post-quantum ratchet like Axolotl? It could > use NTRU or perhaps another approach. > > > Here would be my naive approach : > > Afaik, any "two step" ratchet like Axolotl, Axolotl without hash > iteration, etc. needs to communicate the curve25519 public key that > updates the ratchet for the current message in a header outside the body > of the message itself. > > If we leave this key unencrypted, then an attacker with information on > weaknesses in a sizable portion of the curve25519 key space could > examine a conversation history in parallel to discover how much of the > conversation they could potentially decipher, and then choose to spend > their resources attacking all those keys, again in parallel.
As an aside, discrete log is "random self-reducible" - if you can solve a "sizeable portion" of instances, you can solve all of them. > [...] There might be simpler ways to do effectively the same > things too. You could do an expensive post-quantum calculation alongside an EC key agreement, hash the results, and then use the shared secret as input to a ratcheting protocol. If you wanted the ratchet protocol to also do an OTR/Axolotl-like "DH" step but with post-quantum added, you could consider a few things: - Perform the PQ+ECDH steps in parallel, to keep the complexity manageable, i.e. consider the combination of new PQ and new EC keys as a single "thing" - Maybe perform PQ+ECDH updates less frequently, i.e. instead of Alice and Bob ping-ponging new PQ+EC keys as fast as they can, defer introducing a new key until some time has elapsed, to amortize costs - Separate the notion of "I'm acknowledging your last update" from "here is my new PQ+EC key", so that Bob could tell Alice to stop re-sending her last update keys (to save space) prior to sending his next key. Trevor _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
