Dagstuhl: Cloud Computing

This week I have been at Schloss Dagstuhl as a co-organizer of a workshop on security for cloud computing. Dagstuhl is a computer science research centre in Germany, and every week they invite a bunch of computer scientists to the old Schloss to discuss a particular research topic.

We discussed various topics. From securing data on the cloud, to computing on this data, to verifying the computation and more interestingly we discussed the economics of whether it actually made any sense. In this last topic there were two interesting talks by Ari Juels and Radu Sion. Both essentially contended that economically it may make no sense to perform computation on encrypted data in the cloud. Indeed Radu went even further and suggested that the so-called economic benefits of general cloud computing may be illusory, especially if the amount of data transfer to and from the cloud outweighs the benefit of the outsourced computation. This was done by measuring the cost of various operations in terms of pico-cents.

A related question, debately quite hotly, was whether any of the ANY cryptographic method for computing on encrypted data could have widespread deployment/usage. As usual the "Danish Sugar Beet" auction was mentioned as the application for Multi-Party Computation technology; but this is a niche application and none of us could come up with a commercially compelling large scale application of such techniques. In all cases there seemed to be impediments to deployment, often of a non-technical nature; such as in whose interest would it be to commercially make such systems available?

Dagstuhl is a great place to visit. If you ever get an invite you need to go. Organization is a bit chaotic; but that is the charm. We made the programme up as we went along, and so could respond to the interesting topics that were arising. However, it is probably best to go not in the bleak mid-winter.

Asiacrypt 2011 Day 4

One talk I was interested in today was the talk on the paper "Short signatures from weaker assumptions". In the paper, the authors first propose several new constructions of (m,1)-programmable hash functions (PHFs) for any m≧1. They then show how to use the new (m,1)-PHFs for generic construction of short yet efficient hash-and-sign signatures based on weaker hardness assumptions: the q-DH and RSA assumptions (Note before this work , there are some existing PHFs short signatures based on stronger assumptions: strong q-DH and strong RSA assumption). The resulting signature schemes from weak assumptions are secure in the standard model.

The concrete q-DH signature schemes are the first hash-and-sign schemes from the q-DH assumption and the proposed RSA signature schemes have considerable efficiency improvement compared to the previous standard model RSA-based signatures. Interestingly, the resulting signature schemes offer different tradeoffs between signature size, efficiency and public-key size. The bigger the parameter m in the (m,1)-PHF, the larger the public-key size, the shorter the signature size. Therefore, to obtain extremely short signatures, the size of public-key can get quite large.

Asiacrypt 2011 Day 3

There were two talks discussing secret sharing at Asiacrypt day 3: one talk on the paper "Computational verfiable secret sharing revisited" and the other talk on the paper "Natural generalization of threshold secret sharing".

In the former paper, the authors demonstrate that homomorphism of comments is not a necessary for computational verifiable secret sharing (computational VSS) in the synchronous or in the asynchronous communication model. The author consider computational VSS as a standalone primitive and propose new VSS schemes based on the definitional properties of commitments that are almost as good as the existing VSS schemes based on homomorphic commitments.

In the later paper, the authors study the research for new families of ideal access structures that are among the most generalization of threshold secret sharing. The authors also study the efficiency analysis of the methods to construct ideal secret sharing schemes. By using integer polymatroids, the authors propose a number of new families of ideal multipartite access structures.

ASIACRYPT

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.

Asiacrypt 2011 Day 2

The first talk at Asiacrypt day 2 is the talk on "Bridging brocast encryption and group key agreement". The work bridges two well-studied primitives, broadcast encryption and group key agreement, with a new hybrid primitive referred to as contributory brocadast encryption (CBE). In CBE, a group of members contribute to the public group encryption key. A sender can securely broadcast to any subset of the group members which is chosen in an ad hoc way. CBE incorporates the ideas of broadcast encryption and group key agreement. In the set-up phase, a group of members interact via open networks to negotiate a common encryption key while each member keeps a different secret decryption key. Anyone can necrypt message to any subset of the group members by using the common encryption key and only the intended receiver can decrypt the ciphertext. CBE allows the sender to exclude some group members from reading the ciphertext (compared to group key agreement) and does not need a fully trusted third party to set up the system (compared to broadcast encryption). Finally, a CBE construction proven to be semi-adaptively secure under decision BDHE assumption in the standard model is also proposed.

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).

ICISC 2011: Day 1

Yesterday was Day 1 of ICISC 2011. This year the conference is making its 14th appearance and this time the conference received the maximum number of submission in its history (total 128 submissions) and the acceptance ratio is 25.2%. The emphasis on Day 1 was mostly on practical crypto: one session on side channel, one on network security and one invited talk on light weight crypto. In addition to this, there was one session on hash functions and one on public key cryptography. Apparently I was requested to chair the session on hash functions. This was the first time when I chaired any session and interestingly, I was given 100$ for the same:)-

I could not make much out of yesterday's talks, as most of them were related to the topics that are not my cup of tea. However, I did like the invited talk on light weight cryptography by Thomas Peyrin. Actually this is the first time I listened to any talk on this topic. The speaker very nicely introduced what light weight cryptography means and what are the major goals and challenges. What I could understand from his talk is that the major goal is to design light weight crypto primitives, specifically light weight block ciphers and light weight hash functions, which provide us with appropriate level of security and speed and at the same time not utilizing much resources (in this context, it is the space) so as to be used in applications like RFID. Various guidelines for the design of these primitives, meeting the above requirements were also discussed. The speaker also talked about one of his latest light weight hash function and one light weight block cipher, which were published in CHES 2011 and CRYPTO 2011. However, I could not make much out of them as it became too technical for me. Moreover, I was having severe jet lag (Seoul is around 9hrs ahead of Bristol time) and even now I am finding it difficult to adjust to the local time.

Overall, the first day experience at ICISC 2011 was OK. But I am looking forward specifically for the last day talks, as there are several talks related to protocols and theoretical cryptography and I am hopeful that they will be interesting.