[curves] Post-quantum Axolotl

Jeff Burdges burdges at gnunet.org
Wed Jul 22 01:13:31 PDT 2015

What are current opinions on NTRU?  I noticed DJB suggest a variant he
called NTRU' once.  Is anyone actually working on any thing like this?

Has anyone thought much about incorporating NTRU into a Axolotl-like
ratchet?  Is there a good Diffie-Hellman analog for NTRU?

Aside from doing a Diffie-Hellman operation based on NTRU, one could use
Axolotl itself with curve25519 while (a) periodically sending the
partner a new NTRU key in messages protected by Axolotl, and (b) using
the partner's current NTRU key to protect information that updates the
root key.

There are two options here : 

(1)  Send some new piece of information inside the Axolotl envelop.  In
essence, we're laying another type of ratchet inside the Axolotl
ratchet, but probably keeping them in sync for simplicity.

(2)  Encrypt the Axolotl header that contains the new curve25519 public
key with whatever our partner's current NTRU public key is.

Pond encrypts the Axolotl header with a symmetric key derived from the
same key material as root key was a full ratchet round ago.  I'm unsure
if other Axolotl implementations do this, so maybe that's a more radical
departure for them.  

Alice could keep keep this symmetric envelope outside while encrypting
the new curve25519 public key inside it using the NTRU key she obtained
from Bob the previous half ratchet round.

A priori, I'd prefer (2) because it seems to incorporate the NTRU
protection half a ratchet step earlier, but it might complicate
understanding the code slightly.  Does this seem reasonable?


p.s. There is actually a hash-based trick to obtain post-quantum
protection on typical mobile devices.  Just allow users to do an Axolotl
round ratchet using QR codes and the device's camera.  After a single
round the adversary could not record, Axolotl should effectively be as
strong a deterministically generated one-time pad.  I'll write a longer
message about trying to make a weakly post-quantum mix network sometime.

p.s.  Apologies if this belongs more on the messaging list, but I
figured the NTRU question meant to send it here. 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150722/9da0b347/attachment.sig>

More information about the Curves mailing list