Alternatives to FHE for secure function evaluation

Question

As a followup to a previous question I asked which was more related to Fully Homomorphic Encryption (FHE), what other cryptographic methods are available for computing a private function on public and/or private input? And, what are the benefits/limitations when compared to FHE?

In specific I am interested in Yao's Garbled Circuits construction and a newer publication I recently came across due to Parno et al., which uses functional encryption (aka attribute based encryption). If there are any others, I'd be interested in them too.

Answer 1

Yao's garbled circuit is simple to understand. First of all, note that if we can securely compute $\mathsf{NAND/NOR}$ of two input bit, we can perform any boolean operation. Yao's garbled circuit tries to achieve the same. Lets look at scrambled $\mathsf{OR}$ gate.

1. Alice creates a set of four keys, $K_{x=0},K_{x=1},K_{y=0},K_{y=1}$
2. She then creates 4 “boxes” for each of the table entries, $B_{00}=0,B_{01}=1,B_{10}=1,B_{11}=1$.
3. She then encrypt each box with the corresponding keys, for example, $B_{00}$ is encrypted with $K_{x=0},K_{y=0}$, permutes the box and send the box to Bob.
4. Bob gets the key corresponding to Alice's input from Alice and the key corresponding to his input by using $\mathsf{OT}^2_1$.
5. Bob computes the output by decrypting the only box he can.

NOT gate is even simpler and I leave it for exercise for you. Else, you can always fall on the famous GMW paper, "How to play any mental game."

For attribute based cryptography, you can have a look at the bibliography at the webpage of Liang. There is a good talk given by Waters at MSR website on his work on Unbounded HIBE and Attribute based Encryption.

Now to include few questions later asked by Mike,

1. Computation overhead: a lot of overhead, for sure. Theoretically, you are fine as long as the overhead is polynomial which is the case in Yao's garbled circuit. But in practice, it is a lot.
2. Any circuit: yes, as long as they are boolean circuit. NOR and NAND are universal gates.
3. Interaction is a requirement if you are trying to do Secure party computation. If you are fine with Secure function evaluation, then you can do away with interaction. All you need is a non-interactive zero knowledge proof. The drawback is that that NIZK is proven zero knowledge only in random oracle model. Recall that NIZKP helps in proving to the other party that the gates are constructed properly without any interaction. This will work fine if you are doing SFE because there is no binding on the second party to share the output to the first party.
4. The result are in clear, but here you are assuming authenticated secure channel. If you are in standard model of communication, there are ways to go around this as well in a very standard way.
5. Reusuability of the garbled circuit is a different issue. You can use proactive cryptosystem to make it reusable. Stand-alone Yao's garbled circuit is not reusable. (Proactive cryptography works in the scenario where you don't change the shares after some time epoch. It is first studied in the realms of secret sharing, where the first share are formed as in normal SS, but later on, when you need to redistribute the share for same secret, you construct a polynomial with constant 0 and redistribute the share as in normal SS.)
6. Jarecki and Shmatiko made a garbled circuit secure against active adversary by incorporating that the first party proves in ZK-way the correctness of every gate. Note that in garbled circuit, one party construct the circuit and other computes. It thereby, does not prevent against unfair adversary. Till now, there is no way to get fair computation using Yao's method
7. They can be made verifiable by a very standard way. I am not sure if all the standard methods can be applied or not.

The advent of FHE helps in most of these areas, but at the moment FHE is still in a baby-stage. I cannot wait for it to become very efficient.

Summary

|System | plaintext output | Circuit size | Reusable          | Verifible | Currently Practical | 1 block of AES |
------------------------------------------------------------------------------------------------------------------
|FHE    |       N          |      Any     |     Y             |     N?    |          N          |     1 week     |
------------------------------------------------------------------------------------------------------------------
|GC     |       Y          |      Any     | Y (special        |     Y     |          Y
|       |                  |              |    constructions) |           | (with caveats)      |    0.2 sec     |
------------------------------------------------------------------------------------------------------------------
|FE     |       Y          |       ?      |         Y         |     Y     |          ?          |       ?        |
------------------------------------------------------------------------------------------------------------------

Answer 2

Functional encryption is bigger framework, not necessarily attribute based encryption.It tries to provide a framework for Identity Based Encryption, Attribute Based Encryption and Predicate Encryption.

Recently a paper came up showing the connections between Functional Encryption and Fully Homomorphic Encryption. Here. Iam yet to go through it thoroughly though.

Other than that iam not aware of any alternatives to FHE for secure function evaluation