Regular contributions Secure outsourcing of sequence comparisons
Mikhail J. Atallah, Jiangtao Li · 2005
Internet computing technologies, like grid computing, enable a weak computational device con- nected to such a grid to be less limited by its inade- quate local computational, storage, and bandwidth re- sources. However, such a weak computational device (PDA, smartcard, sensor, etc.) often cannot avail it- self of the abundant resources available on the net- work because its data are sensitive. This motivates the design of techniques for computational outsourcing in a privacy-preserving manner, i.e., without revealing to the remote agents whose computational power is being used either one's data or the outcome of the compu- tation. This paper investigates such secure outsourcing for widely applicable sequence comparison problems and gives an efficient protocol for a customer to securely outsource sequence comparisons to two remote agents. The local computations done by the customer are lin- ear in the size of the sequences, and the computational cost and amount of communication done by the exter- nal agents are close to the time complexity of the best known algorithm for solving the problem on a single machine.