To: cypherpunks@cyberpass.net 
Subject: non-interactive forward secrecy / identity based crypto 
From: Adam Back
Date: Sun, 31 May 1998 12:24:01 +0100 

Some time back I posed the problem of constructing a function
exhibiting non-interactive forward secrecy.

My earlier attempts at constructing such a function got as far as
considering Diffie-Hellman with a composite modulus (ie like an RSA
modulus n = p.q), to allow one to compute discrete logarithms using
the knowledge of p and q, and then destroy p and q losing the
advantage of computing discrete logarithms mod n.  (Thanks to Lewis
McCarthy for comments on this earlier).

The advantage is not great enough to be practical because computing
discrete logarithms in for example 512 bit fields is feasible, but
pretty expensive, and yet we would like to use public keys 1024 bits
or larger.

It seemed plausbile that one could speed up the discrete logarithm
operation mod n by giving p and q special forms which did not as a
side effect weaken the hardness of factoring the resulting n.  At this
point I ran out of expertise.

However in trying to come up to speed on discrete logarithm algorithms
to work on this problem, I discover that the identity based crypto
people have already used this very construct and solved the problem.

There is a class of crypto called identity based crypto where one
employs a Trusted Agent to compute private keys for users based on the
users identity.  This is useful because it removes the need for key
distribution as the users identity _is_ their public key.  However it
has the killer disadvantage that the Trusted Agent can decrypt any
traffic (yuck!)

So all we have to do to convert such identity based schemes into
non-interactive forward secrecy schemes is to act as our own identity
based crypto protocol "trusted agent" during key generation, and
destroy the trusted agents private keys after key generation.
Generate ourselves as big a set of conveniently reproducable
"identities" as we require, and generate the corresponding private
keys.  Then we can destroy private keys and no longer be able to
re-create them.

An example scheme is therefore:

Choose primes p and q with special forms to speed up discrete log
algorithm, n = p.q

Key generation private information:
        p, q     (destroyed after key generation)

Public keys:
        n, y_0, g       (g is not technically a generator as n is not prime)

Private keys:
        x_i

Where:
        x_i computed by discrete log from relation: 
                y_i = g ^ x_i mod n
        using special form p and q

Encryption (standard Elgamal with the current time period public key y_i):
        a = g ^ k mod n
        b = y_i ^ k M mod n

Decryption:
        M = b / a ^ x_i mod n

Forward secrecy is obtained by deleting x_i.

y_0 could be any standardised shared constant. y_i any function to
combine time value i with y_0 to arrive at unique y_i, for example:

        y_i = y_0 + i
or      y_i = h( y_0 || i )

The public key for this scheme is therefore no larger than typical for
public key crypto systems not exhibiting forward secrecy.

The recipient would delete x_i values after appropriate delay to allow
for time taken for message delivery.  Or the originator could delay
deletion by selecting a public key for a period i further in the
future.

I think this should be practical enough to implement into mixmaster as
a way to introduce forward secrecy.  I also think it should be
practical for for example a new algorithm for PGP.  There are
tradeoffs in reliability -- for high paranoia where the sender doesn't
want the message to be recoverable even hours after sending the
chances of the message being rendered unreadable due to delivery
delays are increased.  However time periods of a month or so are
probably practical and likely introduce little extra unreliability
based on typical delivery delays.

Messages after a reply to a first message could be made more
immediately forward secret using normal forward secrecy techniques if
more immediate forward secrecy were deemed useful.

Below are some references from Handbook of Applied cryptography which
I would be interested on comments on, online referenes to, or
summaries of.

-Adam

Handbook of Applied Cryptography:

p114 references p536 on composite fields (Zn*,n=p.q)

p537 references

Shmuely [1127] and McCurley [825] consider composite Diffie-Hellman

p538 says and references:

Maurer and Yacobi [824] (modifying their earlier proposal [823])
propose an identity-based one-pass key pre-distribution scheme using
composite modulus Diffie-Hellman, featuring implicitly-certified
public key-agreement keys essentially consisting of a users identity
(or email address); the corresponding private key is the discrete
logarithm of this, computed by a trusted authority which, knowing the
factorization of an appropriately chosen modulus n, can thereby
compute logarithms.

p538 says and references:

Okamoto and Tanaka [946] propose identity-based key agreement
protocols combining exponentail key agreement and RSA, including one
using timestamps and providing entity authentication, anda simpler
protocol providing (implicit) key authentication.

[823] U Maurer and Y Yacobi "Non-interactive public key cryptography",
Advances in Cryptology, Eurocrypt 91 (LNCS 547), 498-507, 1991

[824] U Maurer and Y Yacobi "A remark on a non-interactive public-key
distribution system", Eurocrypt 92 (LNCS 658), 458-460, 1993

[825] K S McCurley "A key distribution system equivalent to
factoring", Journal of Cryptology, 1 (1998), 95-105

[946] E Okamoto and K Tanaka "Key distribution system based on
identification information", IEEE Journal on Selected Areas in
Communications, 7 (1989), 481-485

[1127] T Okamoto, "A single public-key authentication scheme for
multiple users", Systems and Computers in Japan, 18 (1987), 14-24.
Translated from Denshi Tsushin Gakkai Ronbunshi vol 69-D no.10,
October 1986, 1481-1489.