[cryptography] Asynchronous forward secrecy encryption

Adam Back adam at cypherspace.org
Mon Sep 16 09:51:43 EDT 2013

Well aside from the PGP PFS draft that you found (which I am one of the
co-authors of) I also had before that in 1998 observed that any IBE system
can be used to make a non-interactively forware secret system.


There were prior IBE systems (with expensive setup and weak security margin
where you had to compute a 512-bit discrete log during to setup to gain
1024-bit security in the cse of Maurer & Yacobi's [1]), however that IBE ->
NIFS approach become efficient with Boneh & Franklins 2001 Weil pairing
based IBE.

However personally I consider that to still be a bit experimental on the
experimantal sid and prefer still more conventional approaches.

However in the mean time here's another approach for you (all new AFAIK :)
Use the paillier (1999) cryptosystem to compute discrete log mod n^2. 
(Knowledge of lambda(n^2) (the carmichael function of n^2) allows computing
the discrete log in paillier.) Create some relatively arbitrary set of
public keys y_i in an easily (publicly) computable sequence eg y_i=KDF(i). 
Use lambda to compute x_i st y_i = h^x_i mod n^2 with "generator" h.  Delete
lambda (and p,q, e, d etc).

Now encryption is (randomized) Elgamal using y_i, h and x_i during epoch i. 
Or for message i (if you stash a big load of public keys on an auxilliary
server for senders to take).  Should be pretty easy to implement. 

discrete log of y = h^x mod n^2 is computed with l = lamda:

define log(y,h) {
   return (modexp(y,l,n^2)-1)/n * modinv((modexp(h,l,n^2)-1)/n,n)%n;

(in bc syntax).  

or x = (y^l-1 mod n^2)|n / (h^l-1 mod n^2) mod n

where | is literally divided by (no modulus) and / is multiple my modular
inverse mod n.  n is an RSA modulus.


[1] Nov 1996 - U M Maurer and Y Yacobi - "A Non-interactive Public-Key
Distribution System", Designs, Codes and Cryptography vol 9 no. 3 pp 305-316

On Mon, Sep 16, 2013 at 01:45:43PM +0200, Marco Pozzato wrote:
>   Hi all,
>   I'm looking for an asynchronous messaging protocol with support for
>   forward secrecy: I found some ideas, some abstract paper but nothing
>   ready to be used.
>   OTR seems the preeminent protocol, but does not have support for
>   asynchronous communication.
>   This post [1]https://whispersystems.org/blog/asynchronous-security/
>   describes an interesting variation on OTR: the basic idea is to
>   precalculate 100 Diffie-Hellman and consume one at every new message.
>   On the opposite side, for OpenPGP lovers, I found an old
>   extension [2]http://tools.ietf.org/html/draft-brown-pgp-pfs-01 which
>   adopt the same approach, using many short-lived keys, which frequently
>   expire (eg: every week) and are deleted.
>   They are both clever ideas to provide PFS, but what does it mean to the
>   average user? Let say that today I discover an attack run on 1st of
>   August:
>     * OTR variation: I do not know which messages were wiretapped. 100
>       messages could spawn few hours or two months.
>     * OpenPGP: I know I lost messages sent in the first week of August.
>   What do you think about it?
>   Marco
>   1. https://whispersystems.org/blog/asynchronous-security/
>   2. http://tools.ietf.org/html/draft-brown-pgp-pfs-01

>cryptography mailing list
>cryptography at randombit.net

More information about the cryptography mailing list