2
$\begingroup$

Consider this command on a trusted computer:

result = function(public data, secret data)
or shorter: r = f(p,s).

How could a function on an untrusted computer produce the same result without the secret data being available to the untrusted computer?

Abstract example:

r = f(p, s) = f'(p1, p2, ... pn)
such that one or more of the public p variables are derived in some fashion from s.

Concrete example:

p is a database table, r is a record and s is a lookup criteria. The database server is untrusted.

Improve this question
$\endgroup$
2
  • $\begingroup$ The server has no input and there is only one other party? Why not just have the party compute the function? $\endgroup$
    – mikeazo
    Commented Sep 20, 2013 at 19:09
  • $\begingroup$ Let's say that the function is computationally expensive or requires a large amount of public information that the trusted computer doesn't want to cache. Hence delegating to the untrusted server if possible. $\endgroup$
    – LateralFractal
    Commented Sep 20, 2013 at 23:57

2 Answers 2

Reset to default
1
$\begingroup$

As @nightcracker explains, fully homomorphic encryption (FHE) is one possible solution (though not practical). There are others, some of which are practical.

Multiparty computation is another possible solution. The tradeoff here is that MPC typically requires more communication than FHE, but the result is that it can be practical for many situations. The Might Be Evil framework would be a good one if you only have 2 parties. VIFF is good for multiple (more than 2) parties. The SPDZ protocol (of which I don't believe there is a publicly available implementation) is a recent protocol that is very efficient. It uses FHE for the preprocessing phase, so that part might not be super practical on computationally challenged devices.

MPC and FHE are both general solutions to the problem. In many instances there might be a specialized protocol that would be better. An example of this is searching on encrypted data, which relates to the example you gave.

Improve this answer
$\endgroup$
2
$\begingroup$

The term you are looking for is homomorphic encryption. This allows you to evaluate a general circuit (so no branches) on encrypted data without knowing the decryption key.

It works in theory, but to my knowledge no practical applications have been developed yet. They are either incomplete (only allowing addition, XOR, or some other operation) or impractically slow (decrypting costs more time than the actual computation).

Improve this answer
$\endgroup$

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.