[curves] Post-quantum Axolotl

Jeff Burdges burdges at gnunet.org
Wed Jul 22 01:10:14 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 inside the message envelope 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)  Layer another ratchet inside the envelop provided by Axolotl, maybe
keeping that ratchet synced with Axolotl, or maybe not.

(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 a full ratchet round ago.  I'm unsure
if other Axolotl implementations do this, so maybe adding NTRU in this
way would be 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, not yet sure if this would
complicate the code somehow.  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.  Appears one could
build a post-historical-quantum mix-network using this observation, but
that's a longer message.

-------------- 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/7d1c8cf3/attachment.sig>

More information about the Curves mailing list