Secure Outsourcing of Some Computations

Abstract

The rapid growth of the Internet facilitates the outsourcing of certain computations, in the following sense: 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. This currently arises in many practical situations, including the financial services and petroleum services industries. The outsourcing is secure if it is done without revealing to the agent either the actual data or the actual answer to the computation. In this paper we describe how representative operations matrix multiplication, matrix inversion, solution of a linear system of equations, convolution, and sorting can be securely outsourced in a practical sense. The general idea is for the customer to do some carefully designed local preprocessing of the data before sending it to the agent, and also some local postprocessing of the answer returned by the agent to extract from it the true answer. The pre- and postprocessing should not take time more 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 with suitably chosen noise, sending to the agent the obfuscated data. The purpose of the postprocessing is to extract from the noisy answer returned by the agent the true answer that the customer seeks.