Sf of a boolean circuit (i.e., the number of AnD, Or, and nOT gates) that computes f. Any function that can be computed in Tf steps on a Turing machine can be expressed as a circuit with about Tf gates. More precisely, Sf < k • Tf • log Tf for some small constant k. Overall, we say that Evaluatee is efficient if there is a polynomial g such that, for any function f that is represented by a circuit of size Sf , Evaluatee(pk, f, c1, …, ct) has complexity at most Sf • g (l).

The circuit representation of f is also useful because it breaks the computation of f down into simple steps—e.g., AND, OR, and NOT gates. Moreover, to evaluate these gates, it is enough to be able to add, subtract, and multiply. (In fact, it is enough if we can add, subtract and multiply modulo 2.) In particular, for x, y Î {0, 1}, we have AnD(x, y) = xy, Or(x, y) = 1 − ( 1 − x)( 1 − y) and nOT(x) = 1 − x. So, to obtain a fully homomorphic encryption scheme, all we need is a scheme that operates on ciphertexts so as to add, subtract, and multiply the underlying messages, indefinitely.

But is the circuit representation of f—or some arithmetized version of it in terms of addition, subtraction, and multiplication—necessarily the most efficient way to evaluate f In fact, some functions, like binary search, take much longer on a Turing machine or circuit than on a random access machine. On a random access machine, a binary search algorithm on t ordered items only needs to “touch” O(log t) of its inputs.

A moment’s thought shows that random-access speed-ups cannot work if the data is encrypted. Unless we know something a priori about the relationship between f and m1, …, mt, the algorithm Evaluatee(pk, f, c1, …, ct) must touch all of the input ciphertexts, and therefore have complexity at least linear in the number of inputs. To put it another way, if Evaluatee (for some reason) did not touch the second half of the ciphertexts, this would leak information about the second half of the underlying messages—namely, their irrelevance in the computation of f—and this leakage would contradict the security of the encryption scheme. While Evaluatee must have running time at least linear in t as an unavoidable cost of the complete privacy that homomorphic encryption provides, a trade-off is possible. If I am willing to reveal—e.g., in the cloud computing context—that the files that I want are contained in a certain 1% of my data, then I may help the cloud reduce its work by a factor of 100.

Another artifact of using a fixed circuit representation of f is that the size of the output—i.e., the number of output wires in the circuit—must be fixed in advance. For example, when I request all of my files that contain a combination of keywords, I should also specify how much data I want retrieved—e.g., 1MB. From my request, the cloud will generate a circuit for a function that outputs the first megabyte of the correct files, where that output is truncated (if too much of my data satisfies my request), or padded with zeros (if too little). A moment’s thought shows that this is also unavoidable. There is no way the cloud can avoid truncating or padding unless it knows something a priori about the relationship between the function and my data.

2. 3. homomorphic encryption: security
In terms of security, the weakest requirement for an encryp-
tion scheme is one-wayness: given the public key pk and a
ciphertext c that encrypts unknown message m under pk, it
should be “hard” to output m. “Hard” means that any algo-
rithm or “adversary” A that runs in poly(l) time has a negligi-
ble probability of success over the choices of pk and m (i.e., the
probability it outputs m is less than 1/lk for any constant k).