Workshop on Privacy in the Electronic Society 2010

Today there were two interesting talks at the Workshop on Privacy in the Electronic Society (which is co-located with CCS 2010) that relate to the work we're doing at Bristol: The first one was on "Deniable Cloud Storage: Sharing Files via Public-key Deniability", a paper written by Paolo Gasti , Giuseppe Ateniese and Marina Blanton. In their paper they look at the scenario where multiple people collaborate on some files which are stored in a computing cloud and one of these persons is forced to hand over all of his/her keys to the attacker. If such a scenario has to be expected (e.g. because you have to travel to a country where the authorities can not be trusted) they show that you can prepare for this scenario: Based on Paillier's homomorphic scheme and RSA-OAEP they construct a deniable encryption scheme in which the attacker will not be able to tell whether you are revealing the true information or a manufactured false document. (Unless he can exploit a side-channel which in this case might be done using a lie detector.)

The other interesting talk was on "Investigating Privacy-Aware Distributed Query Evaluation", a paper written by Nicholas Farnan, Adam Lee and Ting Yu in which they describe their work on assuring privacy for SQL queries. The problem they are facing is that one query which combines data from multiple databases should not reveal more than possible to any of the databases: Each database should only see the information related directly to the data it is supposed to deliver. Additionally, the data bases should not learn the entire query, they should only learn the part of the query that has to be answered by them. If you have been reading the previous entries of this blog, that might remind you of the i-Hop homomorphic scheme presented by Gentry et al. at Crypto 2010 and indeed I believe that the i-Hop scheme can be used to solve some of the open issues that Farnan, Lee and Yu listed in their talk today.
However, that is not the solution they took. Instead they started looking at current implementations of SQL: SQL just describes what you want to learn with the query but it does not say how the answer has to be computed. One technique to do so are mutant query trees and these are what Farnan et al. looked at. In their research they ask how to split these tree into queries solvable by each database without revealing more than necessary and how to »homomorphise« (this is not the term they used but I guess it is the best generic description of what they are doing) them. So instead of designing a secure system that can be used to answer database queries (with a potentially large overhead) they took a very efficient, highly engineered database system and try to retro fit security into it.
It would be interesting to see, whether both approaches can meet in the middle to solve the security issues that Farnan et al. still have without suffering too much of an efficiency backlash from using the i-Hop scheme (or similar schemes).