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.

Homomorphic encryption is often touted for its ability to

  1. Compute on encrypted data with public functions
  2. Compute an encrypted function on public (or private) data

I feel I have a good grasp of #1 as most of the papers I've come across on homomorphic encryption (both partially and fully) seem to deal with this type of problem, but #2 I haven't been able to wrap my head around.

So, to whittle this down to the simplest case, given a fully homomorphic encryption scheme, let the public input be $a,b,c,d$ (each is a single bit for simplicity). How would I construct a function to compute $(a\vee b) \wedge (c\vee\neg d)$ such that whoever I give it to will not know what the actual function is (granted this is such a simple example they could easily create a brute-force lookup table)?

I'm not looking for an exact function, but how this would be done in general. How does it change if I make it that $a,b,c,d$ are private (to the function creator)? Is the process similar for partially homomorphic (where only the $\wedge$ or $\vee$ operations are possible)?

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

Theoretically, with fully-homomorphic encryption (like with Gentry's scheme), you could make a circuit (with memory) which computes over encrypted data and outputs encrypted results. The circuit could be a general-purpose CPU, and the encrypted data the code which is to be executed (reading this again, I think this is what @ByteCoin suggests).

Since this method requires doing some pretty heavy stuff for every gate in the circuit (including every gate which is used for RAM in our custom CPU) and for every clock cycle as well, the cost would be tremendous (polynomial, yes, but with a hell of an exponent).

Now this would work over encrypted data, and produce encrypted results. If you want an encrypted function which runs over public input data and produces a public output, then the party who holds the decrypting key must be involved at some point. Without such a party, I don't think it is known whether it is doable.

share|improve this answer
    
I wasn't really talking about a function in which the data and the result are public. The data could be public, but the result would still be encrypted. –  mikeazo Jan 21 '12 at 0:08
    
after sleeping on it a few times, I think I'm starting to understand. It took my back to my digital systems class as an undergrad, remembering how RAM is constructed, how the ALU is constructed, etc. Does sound very hefty though. –  mikeazo Jan 23 '12 at 14:04
    
even if the party with decrypting key is involved, how is such computation of encrypted function carried out without decrypting the function ? –  sashank Apr 16 '13 at 2:48
    
The function itself is not usually encrypted. –  Thomas M. DuBuisson Apr 22 '13 at 2:46
add comment

I haven't seen homomorphic schemes touted as enabling encrypted functions on public data. Please provide a reference. It would seem to contradict papers such as "On the (Im)possibility of Obfuscating Programs"

However, it would seem possible to imagine a program of sufficient generality that divides its input data into two sets. The first set corresponds to the input of the unencrypted function and the second set influences the programs operations on the input data. So in short the program is simulating some sort of processor and the second set of data is the program running on the processor. If the inputs are commitments to the real input data and program then the operation of the program should be obscure until the result is calculated whereupon the resulting commitments need to be opened. This would seem to approach the functionality you require.

share|improve this answer
    
Public data could be encrypted with the public key by anyone.. I might not have been very clear on this. Perhaps I should have said a private function with public input and private output. For example, the Paillier cryptosystem allows encrypted polynomials to be evaluated at a public point, but the result is private. –  mikeazo Jan 21 '12 at 0:13
    
You may require homomorphic encryption to do the task, but homomorphic encryption is not constructed to perform the task. For example, Mohassel had a paper in CANS 2011 titled "Fast Computation on Encrypted Polynomials and Applications" which if I remember correctly performs the task of evaluation of encrypted polynomial by using additive homomorphic encryption scheme. You can find work on this line, but sure enough, homomorphic encryption is devised to evaluate a publicly known circuit on encrypted data, nothing more than that! –  Jalaj Jan 21 '12 at 15:51
    
@Jalaj, your comment seems to contradict a number of things I've read (for example, see section 2.2 of research.microsoft.com/pubs/148825/ccs2011_submission_412.pdf). Care to explain? –  mikeazo Jan 23 '12 at 14:02
    
I just read the abstract and the first page of the introduction. This paper also concerns with only performing some circuit operation (publicly known) on encrypted data. It does not perform publicly known data on private circuit. It does not say that the motivation of constructing a FHE is to compute private functions. The prime motivation was to compute public function on encrypted data. –  Jalaj Jan 23 '12 at 14:47
    
I went through Section that you mentioned. It clearly says, "With FHE, some functions can be evaluated privately" and this is exactly what I mentioned in my comment. You may evaluate private function using FHE, but FHE was not motivated to do this. The paper I mentioned does exactly the same! Primitives are developed and their applications are found later on. For example, PSG are used to construct randomness extractor, but well, PRG was not developed to do that task: the prime motivation of PRG was to derandomize $\mathsf{BPP}$. There are many such examples. –  Jalaj Jan 23 '12 at 14:52
show 5 more comments

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.