# How to get the same calculation result on an untrusted computer, while withholding some information?

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.

-
The server has no input and there is only one other party? Why not just have the party compute the function? – mikeazo Sep 20 '13 at 19:09
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. – LateralFractal Sep 20 '13 at 23:57

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.

-

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

-