Asiacrypt 2011 Day 1

One of the interesting talks today is a talk given by Peter Sebastian Nordholt on "Lower and upper bounds for deniable public-key encryption". A deniable cryptosystem is introduced to allow sender or receiver to deny a message exchange and combat coercion. For example, if the adverary can threaten the communicating particies into revealing the internal states or parameters after the execution of the communication, the cryptosystem is still secure under this kind of coercion. According which parties can be coerced by the adversary, we can distinguish between three kinds of deniability: sender deniability, receiver deniability and bi-deniability. A deniability public-key encryption is a public-key encryption which is deniable.The main contribution of this paper is to derive upper and lower bounds on how secure a deniability public-key encryption scheme can be as a function of the key size.

For the lower bounds, the author have the following results:

1. Receiver deniable: a public encryption with l-bit keys can be at most (1/2)* ((l+1)^(-1)) -receiver deniable

2. Sender deniable: the author do't know a non-trivel lower bound

3. Bi-deniable: at most (1/2)*((l+1)^(-1)) -bi-deniable.

For the upper bounds, the author have the following results:

1. Receiver deniable: let k be the length of the secret key, there exist a (1/n)-sender-deniable puvlic-key encryption scheme with key length l=O((n^2)* k).

2. Sender deniable: let k be the length of the secret key, there exist a (1/n)-sender-deniable puvlic-key encryption scheme with key length l=O(n* k).

3. Bi-deniable: let k be the length of the secret key, there exist a (1/n)-sender-deniable puvlic-key encryption scheme with key length l=O((n^4 )* k).