Using a Network of Untrusted Computers for Secure Computing

This paper defines a new problem in distributed computing: How to securely compute one's own problem using a network of untrusted computers? A theoretic solution of the problem is also presented. All secret input data and a secret result are known only by the initiator of the computation. Other computers are used only to carry out the computation using their computer time and memory. The communication can be eavesdropped, and any of untrusted computers can arbitrarily tamper the computation, assuming that no cooperation between untrusted computers occurs. This problem is different from a well-known multiparty distributed computation problem. Here, only one party has all the secret data. The computation is carried out on untrusted computers. An untrusted computer has access to only a small part of secret. Provided no or only a few untrusted computers are cooperating, the secret input data, and the result of the computation is not revealed.