Still some more CCS'2010

At CCS'10 Wilko Henecka, Stefan Kögl, Ahmad-Reza Sadeghi, Thomas Schneider and Immo Wehrenberg presented in their paper "TASTY: Tool for Automating Secure Two-partY computations" a new tool to implement a variety of (relatively efficient) secure two-party computation protocols and to compare the results of these protocols. It is based on previous work of the Fairplay Project which uses Yao circuits and previous improvements thereof. In TASTY, the authors implemented further optimization techniques which mainly focus on shifting as much computation as possible into the setup phase. Additionally, the authors implement the additively homomorphic scheme by Paillier and also allow for a hybrid mix of both.

The interesting part is, that now the efficiency of both schemes can be compared. And surprisingly enough, even though additively homomorphic encryption should be expected to be more efficient for multiplications, this does not seem to hold. Indeed the authors show that for some scenarios, Yao Circuits are more efficient at multiplications than the Paillier scheme. This is quite surprising.

Another interesting scheme that was proposed at CCS'10 is that of "Worry-Free Encryption: Functional Encryption with Public Keys" by Hakan Seyalioglu and Amit Sahai. It is based on Yao circuits as well and provides a solution for the following problem:

• A has data d which may only be read by people with who have security clearance x1 but does not want to reveal that d is only accessible to people with security level x1.
• B wants to get d from A without knowing which security level is required for d and without having to reveal his/her own security level xb.

Basically, this can be achieved if you have a function f( ) which produces

d=f(x1)

and different (random) output for all other security levels. This function has to look random so that it does neither reveal d nor x1 and it may only be evaluated once. Of course this is just what can be achieved with Yao Circuits. (This was really just a very fundamental explanation, please read the paper for an accurate description. For example, a central authority is required as well.)