# Outsourcing arbitrary computations securely

Consider the following scheme. Alice wants Bob to make some computations for her, but she doesn't want to reveal the data on which he's going to do it. So, she encrypts the data, sends them to Bob, he makes some (Turing-complete) computations on them, and sends an encrypted answer. For example (C++-like pseudocode)

// Alice: range of numbers (ideally, 2^32 for int's)
const int max = 117
int a = 3, b = 5;
// Alice: ready some random keys
int ra = rand() % max, rb = rand() % max;
// Alice: encrypt inputs
int ea = (a + ra) % max, eb = (b + rb) % max;
// Bob: compute sum of inputs
int er = (ea + eb) % max;
// Alice: decrypt result
int r = (er - ra - rb + 2 * max) % max;
// Alice: yeah, it was 8!
cout << r << endl;


Mention that neither Bob has access to inputs and outputs, nor there are some unencrypted data used in process. Though, such a scheme has several drawbacks:

• Obviously, we shouldn't use modulo of rand that simply, because in current implementation it prefers some results over others.
• The data are not that much encrypted, because their distribution didn't change.
• To compute some arbitrary function Alice and Bob should send the data for each operation, while ideally there should be only two: Alice sends inputs, Bob responds with outputs. Possibly, this could be solved by sending a seed for PRNG, generating "salt" for single steps of computation.

Such kind of computations must have already been studied somewhere, though I don't know, how they're called. Could you suggest some good keywords and sources to start with?

-
You are looking for secure function evaluation, i.e., a secure 2 party computation where only one party provides input. Garbled circuits (GCs) and fully homomorphic encryption (FHE) are tools that can be used to realize what you describe. – DrLecter Dec 19 '13 at 23:54

What you are seeking for is a special case of secure multiparty computation, namely secure function evaluation or also called secure 2 party computation.

However, general solutions to this problem require interaction, meaning that the parties performing the computation need to exchange more than two messages. You write:

To compute some arbitrary function Alice and Bob should send the data for each operation, while ideally there should be only two: Alice sends inputs, Bob responds with outputs.

Within recent years, two solutions to this problem have attracted much research interest, namely:

Garbled circuits (GCs)

Have initially have been proposed by Yao back in 1982 as a general idea to perform secure two party computation, i.e., to evaluate $f(a,b)$ between two parties with $A$ having input $a$ and $B$ having input $b$ without neither learning the other's input but the result.

One can generalise this to receiving $A$ and $B$ possibly different outputs for two possible different functions $f_A$ and $f_B$. We can also emulate this by a function $f$ to be evaluated as $f((a,r_A),(b,r_B))=(f_A(a,b)\oplus r_A\|f_B(a,b)\oplus r_B)$ for $r_A$ and $r_B$ being uniform random strings. Lets say that $A$ holds the input $a$ and setting the input $b$ of $B$ (the one computing the evaluation) to be simply nothing, allows $B$ to obtain the evaluation $f$ without learning $a$ and only learning $f(a)\oplus r_A$ but not learning $f(a)$. Sending this back to $A$, $A$ can retrieve $f(a)$.

Having this scenario it can be realised with GCs by letting $A$ build the GC and give it to $B$ along with the garbled input, $B$ evaluates the GC and learns only the garbled output, which is sent back to $A$ and $A$ receives the output.

Garbled circuits can be built using symmetric encryption and oblivious transfer.

You may look at the Might Be Evil project for an implementation of GC and further pointers.

Fully Homomorphic Encryption (FHE)

A first FHE construction has been proposed by Gentry back in 2009 and there has been much progress since then. Loosely speaking, FHE represents an (public key) encryption scheme which allows you to evaluate any function $f$ which can be represented as a circuit on encrypted data such that the input is a ciphertext $c$ for message $x$ and the output is a ciphertext $c_f$ containing $f(x)$. Consequently, $A$ can encrypt some $x$ to obtain $c$, give it to $B$ and $B$ can evaluate $f$ on $c$ without learning neither $x$ nor $f(x)$ but only $c_f$. Giving $c_f$ back to $A$, $A$ can decrypt to obtain $f(x)$.

Simple Operations

If you only want $B$ to add or multiply encrypted values you can use additively homomorphic or multiplicatively homomorphic encryption schemes which are entire practical, but leave you with very limited computations.

Some remarks

The practicality of GC and FHE largely depends on your setting and the circuit to be evaluated and is unfortunately not that nice as one would desire.

FHE is impractical at the moment, but since FHE schemes are typically constructed via a bootstrapping approach from certain somewhat homomorphic encryption (SHE) schemes (which allow to evaluate a certain class of circuits homomorphically), using a "customised" SHE scheme may be practical for some approaches, see e.g., here.

This is a very active field of research and one could write a lot about that. However, I hope this gives you some pointers to look at for further reading.

-
+1 Is it correct to assume that an additively homomorphic homomorphic encryption scheme is more limited than FHE only in a practical sense, for you could imagine a secure (if very slow) server that did all of its multiplications as series of additions? – Drux Dec 21 '13 at 2:32
@Drux We are speaking of boolean circuits here and having only access to addition will not allow you to do arbitrary computations, i.e., we know that we can express any function as a circuit over $Z_2$, but not over a group with only addition. – DrLecter Dec 21 '13 at 7:37
Can you please given an example of a calculation in $Z_2$ where this doesn't work. In rings such as $R$ you can do $3 * 2 = 2 + 2 + 2$ or even $3 + 2 = (1 + 1 + 1) + (1 + 1)$. Isn't $Z_2$ also (such) a ring? I guess I'm missing something simple. – Drux Dec 21 '13 at 8:00
How would you compute for instance $max(a,b)$ having only access to addition? – DrLecter Dec 21 '13 at 8:11
Good question :) Actually, there is a work which shows how to use homomorphic encryption (over semi-groups) which allows to compute $AND$ in a clever way to evaluate circuits belonging to the class $NC^1$, but not any arithmetic circuit over $Z_2$. You may ask the question here to figure out how the property is called? – DrLecter Dec 21 '13 at 9:36