To: coderpunks@toad.com
Subject: non-interactive forward secrecy
From: Adam Back
Date: Fri, 6 Sep 1996 22:08:36 +0100 
Cc: cypherpunks@toad.com 

[This discussion is driven by the desirability of having forward
secrecy in mixmaster for the mix packets delivered by email where the
interactive nature of normal DH is incovenient]

Anyone have any ideas for a non-interactive forward secrecy protocol?

Aside from actually doing the DH key exchange via email (painful), I
have one suggestion for a protocol, perhaps people can improve on
this:

Assuming common prime p, and generator g:

Two remailers A and B.  A wants to send messages to B without having to
wait for replies from B.

B generates ys (y0,y1,...,yn), 

        where y(i+1) = hash(y(i))

then computes Ys (Y0,Y1,...,Yn)

        where Y(i) = g ^ y(i) mod p

B sends A Ys, and discards ys.

Now A can send B n consecutive packets with forward secrecy before
receiving any more packets from B.

(B keeps y0, and overwrites it with y1 = hash(y0), etc, so that all B
ever has to hand is the current y(i), and y(i-1) is hard to compute
from y(i) because of the hash functions properties.)

This isn't truly non-interactive, it just reduces the number of
interactions, to an interactive exchange in 1 out of n cases.

(you could randomly chose ys rather than having related ys, and delete
y(i) after use, but this has higher storage requirements (n rather
than 1 on the recipient)).


Heres the obvious construction for a truly non-interactive forward
secrecy protocol based on DH.  (That is it only requires 1
interactive exchange).

Aside from the obvious of having a huge n, and the above protocol,
which would have large space requirements, what we're after is a way
to do this with negligable space requirements.

Say that we have the two parties Alice and Bob.  Bob doesn't loose
much by having his secret (x) related as above.

1.      x(i+1) = f1( x(i) )
2.      X(i+1) = f2( X(i) )
3.      f1 is non reversible

f1 should have hash-like properties (it should be non-reversible).

Do functions f1 and f2 satisfying 1, 2 and 3 exist?  Is there another
way to achieve this?

(My closest attempt so far, based on the hardness of discrete square roots:

        f1(x) = x^2 (mod p)
        f2(X) = X^2 (mod p)

doesn't work because g^(x^2 mod p) mod p != g^(x^2) mod p)

Adam
--
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)