Is offline secure two party computation possible?

Question

Offline secure two-party computation

Is there a solution for the following problem?

• We have a function f(x,y) where the inputs are secret an cannot be known by anyone besides the party that submitted them.
• The output of f is public and can be known by anyone.
• An adversary has access to any machine in the middle (not the devices of the two submitting parties).
• The computation has has to happen on a third party device without interacting with any of the owners of x and y more than once to get an input eg. Enc(x).

To me this sounds pretty much impossible, but since I cannot come up with a proof and the first time I heard of MPC all of it sounded impossible, let's give it a try.

• amon: The central problem is that the decryption Dec(f(Enc(x), Enc(y))) shall be possible, but Dec(Enc(x)) and Dec(Enc((y)) shall be impossible by the third party. This indicates f() needs some way to re-encrypt the output so that it can be decrypted with a different key, without being able to re-encrypt the inputs. This might indeed be possible for some functions f().
• Sebastian Redl: I find your description very hard to understand. Can you maybe try it differently?
• Sebastian Redl: You might also want to consider asking at security.stackexchange.com instead.
• Jakob: @SebastianRedl Hmm can you tell me specifically what you find hard to understand? I'm might ask there although I think a question about crypto design belongs here more then on the security stackexchange.
• Sebastian Redl: For starters, I don't understand what your goal is. To find a suitable function f? What should this function do, besides compute something that may be publicly known? Where does Enc come in? An understandable explanation would be "I want to compute some function f on an untrusted device, without revealing the inputs x and y to the computation." Is that what you want?

Answer 1

I'm not sure I understand your example exactly but I think you are talking about homomorphic encrpytion:

a form of encryption that permits users to perform computations on its encrypted data without first decrypting it.

It's a pretty nascent field and very inefficient compared to standard calcuations.

Answer 2

One way hashes make it possible for f() = x == y, x contains y etc (although now the owner of x knows y and vice-versa, does this count?)

Technically functions which discard information like abs(x) + abs(y) can also work, as you can send x or -x and get the same result, the attacker would have have to make 4 guesses. But I'm not sure how secure this would be considered?

A generic solution for any f is impossible as shown by f() = x

Answer 3

It is possible for some f, impossible for other f.

An example f for which it is possible would be bitwise xor:

Let f(x,y) := xor(x,y)
And enc(x) := xor(x,s) with s being a secret.
dec(x) would be the same as enc(x).

f(enc(x), enc(y)) = xor(xor(x,s), xor(y,s)) = xor(xor(xor(x,y),s),s) = xor(x,y)

An example for which it would be possible:
Let f(x,y) := (x,y)
This is trivial, because you cannot know (x,y) without knowing x and y