Abstract
We show that matrix multiplication, matrix inversion, convolution, and sorting can be securely "outsourced", in the following sence: A customer who needs these computations done on some data but lacks the computational resources (or programming expertise) to do so, can use an external agent to perform these computations without revealing to the agent either the actual data or the actual answer to the computation. This general situation currentlly arises in many practical situations, including the finacial services and petroleum services industries. The general idea is for the customer to do some carefully designed local preprocessing of data before sending it to the agent, and also some local postprocessing of the answer returned by the agent, in order to extract from it the true answer. The pre- and post- processing should not take more time than proportional to the size of the input, which is unavoidable because the customer must at least read the input once. The purpose of the preprocessing step that the customer performs locally is to "hide" the real data The purpose of the postprocessing is to extract from the noisy answer returned by the agent the true answer that the customer seeks.
