Tuesday, December 6, 2011


The first two days of Asiacrypt 2011 were really great. Met lot of people and discussed various topics, other than my own research area. Yesterday, there were two talks that I liked very much. One of them was on Deniable encryption, about which Ming has already blogged. The other talk was in the same session and on Lossy encryption and selective opening attack (SOA). The motivation for SOA comes from computationally secure multiparty computation (MPC) tolerating adaptive adversary. In such protocols, the adversary can see all the messages in the protocol (the messages exchanged between the honest parties are secure as they are encrypted) and over the course of time, can decide which parties to corrupt (this strategy is called adaptive corruption). Ideally, if the messages of the individual parties are completely independent and the underlying encryption scheme is IND-CPA secure then the security of the MPC protocol is preserved. However, in a typical MPC protocol, the messages exchanged between the parties are not completely independent. In that case, the big question is the following:

suppose the adversary "selectively" get the message and the corresponding randomness used to encrypt the messages of some of the parties in the protocol. Then does that preserve the messages and randomness of the remaining honest parties (assuming that the messages and the randomness of the honest parties need not be independent)?

If an encryption scheme satisfies this property then it is said to be secure against "selective opening attack" (SOA) and using such encryption schemes, we can design computationally secure MPC protocols against adaptive adversary.

The speaker (Benoit Libert) showed how to design lossy encryption scheme secure against SOA. Now let me briefly discuss what is lossy encryption scheme. It can be viewed as a generalization of "dual mode encryption scheme", where there are two modes of encryption: a typical injective or normal mode, where there is a one-to-one correspondence (injective mapping) between plain text and cipher text, while the second mode is a "lossy" mode, where there is no such association. This mean that the cipher text will be independent of the message.

The speaker briefly outlined in his talk, how to design lossy encryption scheme, secure against SOA, from general assumptions, such as re-randomizable encryption, homomorphic encryption and oblivious transfer (OT). I really enjoyed the talk and I really found the concept of lossy encryption and SOA very interesting. Actually, just few days back, I was asking Nigel whether it is possible for anyone to efficiently compute
a message m' and corresponding randomness r', which results in a given cipher text C, which actually is also an encryption of some different message m, under a different randomness r. That is, given C = Enc(m, r), m and r, can one efficiently find another m' and r', such that C = Enc(m', r') = Enc(m, r)? And he said that in general its not possible to do so efficiently, unless the encryption scheme is non-committing. I was not aware of this notion of non-committing encryption and after hearing it, I started to read about it. And then when I listened to yesterday's talk about lossy encryption, then it further widened my interest in this topic. I think it will be a good topic to be discussed in the study group.

No comments:

Post a Comment