8
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This is essentially the problem of Private Function Evaluation (PFE), which has been studied in relation to MPC. I suppose many of the solutions carry over into FHE based solutions. The generic way to do this is to use a Universal Circuit. I.e., basically a circuit that can be programmed to any other circuit (similar to Thomas Pornins answer). However, this solution has a large overhead and there are better solutions. Here is one work in this direction: eprint.iacr.org/2014/102.pdf $\endgroup$
    – Guut Boy
    Commented Aug 15, 2016 at 11:55

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Commented Jan 21, 2012 at 0:08
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Commented Jan 23, 2012 at 14:04
  • $\begingroup$ even if the party with decrypting key is involved, how is such computation of encrypted function carried out without decrypting the function ? $\endgroup$
    – sashank
    Commented Apr 16, 2013 at 2:48
  • $\begingroup$ The function itself is not usually encrypted. $\endgroup$
    – Thomas M. DuBuisson
    Commented Apr 22, 2013 at 2:46
  • $\begingroup$ @sashank In typical FHE, the function is public and the data is encrypted. What Mike Azo is proposing is one further step of abstraction. The function is now "given a circuit and some input, return the output of applying those inputs to the circuit", and the encrypted data is, "a circuit and some input". $\endgroup$
    – Stephen Touset
    Commented Feb 19, 2016 at 23:21
3
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Commented Jan 21, 2012 at 0:13
  • $\begingroup$ 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! $\endgroup$
    – Jalaj
    Commented Jan 21, 2012 at 15:51
  • $\begingroup$ @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? $\endgroup$
    – mikeazo
    Commented Jan 23, 2012 at 14:02
  • $\begingroup$ 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. $\endgroup$
    – Jalaj
    Commented Jan 23, 2012 at 14:47
  • $\begingroup$ 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. $\endgroup$
    – Jalaj
    Commented Jan 23, 2012 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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