Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Consider an outsourced database to an untrusted cloud (think CryptDb), the question is how to compute a function $f(.)$ on the data.

I think I understand how (fully or partially) homomorphic encryption works in this situation:

  1. Encrypt the input.
  2. Outsource both the ciphertexts and the (public) function.
  3. The cloud evaluates the functions on ciphertexts, results are also in ciphertexts.

How would garbled circuit (GC) be used in this case? Is it:

  1. Garble the circuit and upload to the cloud.
  2. Garble the inputs and upload to the cloud (ciphertexts).
  3. The cloud evaluates the circuit. Results are in plaintext.

What are the trade-offs between these two approaches, supposing I don't care whether the results are in the clear or encrypted? It looks like both can be used to compute arbitrary functions over ciphertexts.

But if GC can be used only once (true?), is it possible to use the same garbled inputs for more than one GC, or one needs to construct a (GC,garbled input) pair for every single evaluation of the function $f(.)$?

share|improve this question
    
There are theoretical results that allow reusing garbled circuits, but they're very new. To wit: eprint.iacr.org/2012/733.pdf –  pg1989 Oct 16 '13 at 7:00
    
If nobody has given a good answer by tomorrow morning I'll put one up, I did a lot of research in this area a little bit ago. –  pg1989 Oct 16 '13 at 7:01
    
I saw this paper, but it's about combining GC, FHE and ABE to achieve FE. Still uncertain if it answers my questions. –  Anh Oct 16 '13 at 7:45
    
The output of a GC does not have to be in plaintext. If you don't want the person computing the function to know the output just have the output gates map to random values that only you know how to map those to the plaintext. –  mikeazo Oct 16 '13 at 13:43

2 Answers 2

Concerning some trade-offs between GC and FHE, some of these are described in the introductory chapter of Gentry’s PhD thesis available here http://crypto.stanford.edu/craig/. In essence, for a private information retrieval type of scenario where an encrypted data set is stored in the cloud, the communication complexity of a private query is potentially high since the garbled circuit used to represent the query is proportional to the size of the data set. In contrast, the communication complexity of such a query under a homomorphic scheme is proportional to the size of the encrypted response to the query, which in turn is a product of the associated cleartext response multiplied by the scheme’s security parameter. If a central concern is circuit privacy, Gentry considers this to be something that is distinct from homomorphism, but does show (in chapter 20 of the above reference) how a HE scheme can achieve this. This is requires a specific definition of circuit privacy within the context of homomorphic encryption, namely that distributions over the outputs of the scheme’s encryption circuit and evaluation circuit are statistically indistinguishable.

share|improve this answer

Yes, standard GC are not re-usable, thus by means of GC you may outsource the computation of a single function on a single input (i.e. you delegate a function described by a Boolean circuit and later you may ask the evaluation of the function on a single input not fixed in advance). Indeed this is the approach to Verifiable Computation proposed in a paper of Gennaro, Gentry, Parno https://eprint.iacr.org/2009/547 Here, Verifiable means that you also want a proof that the server computed the input on the expected function. How would you extend this idea to multiple inputs? To this scope the authors employ FHE. But maybe this goes beyond your question since the aim of the authors is to achieve verifiability. As said in a previous post, re-usable GC have been proposed but they are indeed based on FHE.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.