How to rerandomize Yao Circuits

For today's coverage of CRYPTO 2010 we (Stephen Williams and I) picked the "i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits" paper by C. Gentry, S. Halevi and V. Vaikuntanathan. Not only did Vaikuntanathan give a really good talk but also the ideas of the paper are quite appealing. Suppose you have the following setting:

• Alice encrypts a message m into an ciphertext c0 and sends c0 to the server 1
  
• who has to evaluate a function c1<-F1(c0) such that Dec(c1)=f1(m). He then passes c1 on to server 2
  
• who evaluates a similar function c2<-F2(c1) such that Dec(c2)=f2(f1(m)).
  
• It goes on like his until the last (xth) Server sends cx to Dora who knows the secret key and computes Dec(cx)=...(f2(f1(m))).
  

Sounds cool, doesn't it?

Well, there's a nasty little problem which got solved by Gentry, Halevi and Vaikuntanathan (GHV) in their paper: How do you keep the functions fi that were applied to the ciphertexts secret if Alice, some of the servers and Dora work together to reveal the function that has been used? GHV use garbled Yao circuits to implement the functions evaluated by the servers. While these circuits look completely random to Dora, who gets all of them, they don't look as random to the servers who created them. So if Dora gives the entire garbled circuit to the collaborating servers, they are able to de-garble the circuit and the functions of the honest servers that should be protected can be reconstructed by the dishonest ones. However, if each server can re-randomize the previous circuits passed on to him, the previous servers can not derandomize their part of the entire circuit and therefore the honest server protected his function. GHV show in their paper how to achieve this re-randomization using the DDH based encryption scheme from Boneh, Halevi, Hamburg and Ostrovsky (proposed at Crypto'08). That rocks!

The claim that this could actually be of practical relevance is believable. Yao's circuits were once thought to be slow, but recent work by researchers here at Bristol has shown them to be practical. Furthermore, a homomorphic encryption scheme is considered to be "compact" if the ciphertext size remains constant; using the re-randomizable Yao circuits GHV create a "non-compact" homomorphic encryption scheme whose ciphertext size grows after every function applied to the scheme. However, and this is the interesting part, the growth of the ciphertext is polynomial and may thus still be practical. As Vaikuntanathan pointed out in his talk, people should look at how many "hops" (or functions) are going to be applied with the homomorphic encryption scheme; if this number is low, their "non-compact" version may be suitable.

So, why does anyone actually care about this? One possible application (here we slightly generalize Vaikuntanathan's example of e-mail filtering) is searching a database for keywords where the keywords are supplied by multiple parties and neither the database nor the keywords of the other parties should be revealed to any party.