[cryptography] deniable store and forward with integrity protection?

James A. Donald jamesd at echeque.com
Tue Feb 15 16:03:58 EST 2011

On 2011-02-15 8:05 PM, Daniel Silverstone wrote:
> On Tue, Feb 15, 2011 at 01:13:43PM +1000, James A. Donald wrote:
>> It is fairly easy to design a protocol that achieves this
>> result without a round trip requirement, (authentication
>> without round trips or signature), but has such a protocol
>> already been published and examined?
> The closest I can think of is The Wrestlers Protocol[1] but I don't think it
> fits all your requirements.

The wrestlers protocol is two round trips, or one and a half round trips 
followed by a final trip for the message, for a total of two round 
trips. I am pretty sure I it can be done in half a round trip using 
pairing based cryptography, that is to say, a bilinear map, but do not 
recall seeing that procedure studied in the literature, nor a proof of 
security claimed for it, even though it seems to me the simplest and 
most obvious application of pairing based cryptography.

Indeed, one of the big benefits of pairing based crypography is a 
reduction in round trips

Ann and Bob have well known public keys, and are identified by those 
keys, but do not yet have any shared secret.  If they have a shared 
secret, then standard symmetric cryptography gives them authenticated, 
encrypted, but deniable messages.  Trouble is, however, that 
establishing the shared secret from public keys is not necessarily 
deniable (which problem the Wrestler's protocol addresses.

And if we do not care about contact deniability, and we probably don't, 
since likely adversaries to whom the recipient might rat us out probably 
have message tracing, we do care about round trips.

We would like to send an authenticated encrypted message without a round 
trip to establish a shared secret from shared keys.

Ann constructs a message which must contain a large random value that 
cannot be guessed by adversaries, or else it will be possible for an 
adversary to verify guesses of what her message is. She constructs a 
hash of this message, her public key, and Bob's public key.

She constructs from this hash an elliptic point Q, by treating part of 
the hash as a compressed point.

Ann has secret key a, public key aG, Bob has secret key b, Public key bG

Ann calculates the pairing e(aQ,bG), which will be the shared secret.

She encrypts her message using this shared secret.  She then sends Bob 
the encrypted message, the ellliptic point Q, her public key or 
something that identifies her public key, and Bob's public key, or 
something that identifies his public key.

Bob then calculates the pairing e(aG,bQ), uses it as shared secret to 
decrypt the message.  He then calculates the hash, and verifies that the 
hash does in fact yield Q, which shows that the message did indeed come 
from Ann.

The message he received from Ann must contain what is now a strong 
shared secret, which can be used for subsequent messages.

More information about the cryptography mailing list