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