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

share|improve this question
    
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
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.