\section{Encrypted Computing}
\label{sec:Crypto}

A big concern in our global computing approach is that untrusted hosts
get access to client data or client algorithms.  In this section, we
present a methodology for computing on encrypted data and encrypting
the computation itself.  Although we do not present a complete
solution to this challenging problem, we want to show why encrypted
computing is important in a commercial world with mobile or
portable code. To this end, we begin with an example scenario.

Assume the fictitious company Lemon Computers, Inc. wants to run
simulations for their new supercomputer chip, using our proposed
broker architecture. Since the required computational power is so
large, the only sensible choice for the broker might be to assign the
task to Lemon's largest competitor, Prune Corp., which has enough
spare cycles to offer right now.  Lemon can not be sure that Prune's
employees do not eavesdrop on the data sent to their computers and
make a copy of the data, using it to develop their own clone of
Lemon's new chip.  So Lemon wants to encrypt the data before shipping
it to the broker to prevent eavesdroppers on the net from snooping on
the data.  More importantly, the data should remain encrypted on the
machines performing the calculation, and should never be decrypted
during the calculation. Likewise, the result of the computation should
also be produced in encrypted form and not be decrypted before
reaching Lemon's headquarters.

Ideally, we would like to hide three aspects of the computation: the
input, the output, and the actual algorithm.
Encryption is one solution.  Another way to achieve this is to 
split the computation into small segments, such that no part by itself
reveals any useful information about the complete
computation. This can be generalized to a division scheme that
guarantees that even $k$ out of a total of $n$ parts of the
computation do not reveal meaningful information.


\subsection{Processing Encrypted Data}

The idea that clients let service providers work with their private
information without having access to it might look utopian at first
glance, but a closer look reveals that the idea of encrypted computing
is neither completely new nor impractical. Indeed, Feigenbaum
\cite{Feigenbaum85} showed that there are many problems that are 
encryptable, i.e., allow
for an encryption scheme sketched above. The main problems encountered
are making the encryption/decryption process on the client side
computationally inexpensive with respect to the actual computation,
and to make malicious decryption on the host side computationally
infeasible.

We can formalize the processing of encrypted data, as shown in
Figure~\ref{fig-crypto}. Assume a client wants to perform a function
$f$ on input $x$ and output $f(x)$. For some reasons, e.g., lack of
resources, the client cannot compute $f(x)$ directly. However, a
second party, the host, is willing and able to compute functions for
the client.  We define $f$ as fully encryptable if there exists an encoding
function $E$, a decoding function $D$, and a function $f_E$ that
satisfies the equation $f(x)=D(f_E(E(x))$
such that  the host, knowing $E(x)$ and $f_E$ cannot derive $x$, $f$
or $f(x)$. This means that the input $x$, the output $f(x)$ and the
algorithm $f$ are hidden from the host.
The client can now send the encrypted input $E(x)$
and the encrypted program $f_E$
 to the host, which computes $f_E(E(x))$ and sends it back
to the client, which then decodes $f(x)=D(f_E(E(x))$.  The
properties of $E$, $D$, and $f_E$ determine what part of the
computation is actually encrypted. Ideally, the host should not
gain knowledge about the input $x$, the output $f(x)$, or the
algorithm $f_E$.

\begin{figure}[h]
\centerline{\psfig{figure=crypto1_v2.eps,width=3in}}
\caption{\label{fig-crypto} A general scheme for encrypted computing:
  A client, unwilling to compute $f(x)$
  gives the encrypted input $E(x)$ to the host, which computes an
  encrypted version of the output and returns it back to the client
  which can then decode it.}
\end{figure}


Note the fundamental difference between traditional cryptography and
encrypted computing: For a traditional encrypted transmission between
two users, they first have to set up key(s). This can be done using
the well known Diffie-Hellman protocol for public-key encryption.
Alternatively, the two users might agree on keys using a secure
channel provided by other means. This problem is not present in our
encrypted computing example, since the encryption key is not
transmitted at all but rather resides only at the client. The true
challenge in encrypted computing is to send and receive encrypted
data only, and never decrypt the data for the computation, but
directly operate on the encrypted data. 

\subsection{Simple Examples}

Let us start with a trivial example: The client wants to add up two
integers $x$ and $y$, assuming in the following that no overflow
occurs. The client encrypts $x$ and $y$ by adding a random number $h_1$ and
$h_2$, respectively and sends the resulting integers $x+h_1$ and
$x+h_2$ to the host. The host then computes
$(x+h_1)+(y+h_2)=(x+y)+(h_1+h_2)$, and sends this result back to
the client, who then can retrieve the desired result $x+y$ by subtracting
$h_1+h_2$ from the host's reply. Since $h_1$ and $h_2$ act as a
one-time pad, this encryption scheme is provably secure for the input
and output. On the other hand, it is not practical, since the client has to
make 4 arithmetic operations to compute the sum as opposed to just
one. However, other, more complicated problems can be encrypted and
decrypted with very small overhead. Feigenbaum gives an example for
the hard problem of finding a discrete logarithm \cite{Feigenbaum85}.

A more detailed treatise for addition and multiplication of integers
is given by Ahituv et al. \cite{AhituvLN87} and Yu and Yu
\cite{YuY91}. The encryption presented by Yu and Yu \cite{YuY91} is
linear and thus allows for easy repeated addition and multiplication of
encrypted integers. The algorithm is based on a time-reversal diffusion
process. The algorithms in \cite{AhituvLN87} is based on linear
homomorphic functions. Unfortunately, no proper security analysis is
provided for any of those algorithms.  Furthermore, it is not clear
how one can devise a scheme for larger calculations that do not
require frequent interaction between the client and the host. In particular,
we would like to find a generic method of translating any code
sequence into a code sequence that works on encrypted data. This
involves the realization of a comparison between two encrypted numbers
and other primitives. We would also like to identify the amount of
leaked information. Abadi et al.~\cite{AbadiFK89} showed that it is
unlikely hard problems can be encrypted without leaking at least some
properties of the input data.

\subsection{Real-Life Examples}

So far, the examples given covered only basic operations like
summations, multiplications or (discrete) logarithms. We do not (yet)
know of a feasible universal method of converting an arbitrary
algorithm into a safe algorithm working on encrypted data. However, we show a
few more realistic examples that might actually arise in real life
applications. This leaves room for hope that there might be efficient
encryptable algorithms for a larger variety of applications.

Let us consider a Fourier transform $\hat f(.)$ of a
function $f(.)$. The Fourier Transform is a linear transformation,
 i.e., for two
scalar values $s$ and $r$ and two functions $f(.)$ and $g(.)$, the
following relation holds: $\hat{(rf+sg)}(.)=r\hat f(.)+s\hat g(.)$.
Assume the client has a given function $f(.)$ and wants to compute
$\hat f(.)$. Instead of sending $f(.)$ to the host, the client chooses
a random \emph{hiding function} $h$. Since a function is usually given
by its values on a number of points, $h$ is nothing but a vector of
values that can be chosen randomly. Now the client sends out the two
functions $h(.)$ and $g(.)=f(.)+h(.)$ to two independent hosts.  Since
neither host knows of the other's transactions (some feature the broker
architecture has to provide), they cannot recompute $f$ from $g$ and
$h$. Instead, the hosts compute $\hat h$ and $\hat g$ respectively.
After receiving the results, the client combines the results into
$\hat f$ using the equality $\hat f(.)=\hat g(.)-\hat h(.)$.  If the
client cannot be assured that its requests are being watched and used
to reconstruct $f(.)$, it might have a large list of sample hiding
functions $h$ together with the corresponding precomputed Fourier
transform $\hat h$, such that $h$ need not be transmitted.
 
The above example illustrates a feature that can be found in most
examples of encrypted computing: the original data is being perturbed
by a function (key) not known to the host, which is still able to work
on the data and come up with a solution for the perturbed problem. The
client can then remove the effect of the perturbation from the solution
to obtain the correct solution. However, introducing arbitrary
perturbations might upset numerical stability of the used algorithms.
The admissible range of perturbations not only depends on the algorithm,
but also on the data, since a perturbation numerically stable
for one data set might be unstable for another one. It is up to
the application to ensure the perturbation does not affect numeric
stability and sufficiently blurs the original data.

Other examples in scientific computing include matrix calculations.
Instead of asking the host for a solution to the linear equation $Ax=b$
for an $n\times n$ matrix $A$ and $n$-vectors $x$ and $b$, the client might
multiply both $A$ and $b$ by a regular matrix $T$ and then ask the host
for the solution of the equation $(TA)x=(Tb)$, which leaves the host in the
dark about the original input $A$ and $b$. Note that our remarks about 
numerical stability apply for matrix calculations.
%However, the solution $x$ is
%the same for both problems. In order to prevent anyone from
%getting any information from the solution, the client might ask the host for
%the solution of $(TAT^{-1})y=Tb$. 
%The solution of this problems is $y$ satisfying $Tx=y$. This equation
%might now be solved by an independent host.

\subsection{Encrypting Algorithms}

Finally, we want to discuss the following problem: Assume the client
wants to perform a certain algorithm on the host's machine.
The client can prevent the host from knowing what data
it worked on by using one of the previous techniques, but 
the host still can discover the algorithm of the computation.
Knowing the algorithm, the host might deduce some information
(e.g., that the client solves a lot of differential equations
used for shock wave modeling).
Moreover, the host might find the program sent to it very useful,
and decide to keep it and use it on its own data. 

%To prevent reverse engineering, one might scramble or obfuscate the
%algorithm before sending it out to clients. While existing tools
%just rename all variable and method names in Java class files to prevent
%understanding decompiled code, more refined compilers might decide to work with
%transformed variables. For instance, instead of working with variables
%$a$ and $b$ and computing $a*b$, it might work on $\log a$ and $\log
%b$ and compute $\log a + \log b$.

While preventing reverse-engineering is hard, preventing the reuse of
a given program on a different input is even harder. We currently lack
a framework to classify the information-theoretic security of
algorithm encryptions. Therefore, we will just describe one way of
preventing code reuse without giving a security analysis.  We modify
the algorithm to depend on the encrypted input.  This in effect would
make it useless for any other inputs, leaving the host without any
advantage. One first step in this direction would be to use dynamic
compilation and specialization techniques, which enables the client to
send the host a modified version of the program that is optimized for
the specific input and will not produce correct output for other
inputs. For instance, consider the assignment $B:= 3*A+2*d*C$ with
matrices $A,B,C$ and scalar $d$. Assume $A$ is a (constant) matrix
provided as input with $A[1,3]=2$ and $A[2,3]=3$. Then, the above
assignment can be replaced by $B := A[1,3]*A+A[2,3]*d*C$ for the
specific input matrix $A$. The transformed program will then run only
if the input does have the same entries in $A[1,3]$ and $A[2,3]$. If
these specializations are employed throughout a program, it will be hard,
if not impossible to run it on other input or reverse-engineer it.
