Paper 2014/992

Incentivized Outsourced Computation Resistant to Malicious Contractors

Alptekin Kupcu

Abstract

With the rise of Internet computing, outsourcing difficult computational tasks became an important need. Yet, once the computation is outsourced, the job owner loses control, and hence it is crucial to provide guarantees against malicious actions of the contractors involved. Cryptographers have an almost perfect solution, called fully homomorphic encryption, to this problem. This solution hides both the job itself and any inputs to it from the contractors, while still enabling them to perform the necessary computation over the encrypted data. This is a very strong security guarantee, but the current constructions are highly impractical. In this paper, we propose a different approach to outsourcing computational tasks. We are not concerned with hiding the job or the data, but our main task is to ensure that the job is computed correctly. We also observe that not all contractors are malicious; rather, majority are rational. Thus, our approach brings together elements from cryptography, as well as game theory and mechanism design. We achieve the following results: (1) We incentivize all the rational contractors to perform the outsourced job correctly, (2) we guarantee high fraction (e.g., 99.9%) of correct results even in the existence of a relatively large fraction (e.g., 33%) of malicious irrational contractors in the system, (3) and we show that our system achieves these while being almost as efficient as running the job locally (e.g., with only 3% overhead). Such a high correctness guarantee was not known to be achieved with such efficiency.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Outsourced ComputationCloud ComputationCrowdsourcingMalicious ContractorsFair Payments
Contact author(s)
akupcu @ ku edu tr
History
2014-12-18: received
Short URL
https://ia.cr/2014/992
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/992,
      author = {Alptekin Kupcu},
      title = {Incentivized Outsourced Computation Resistant to Malicious Contractors},
      howpublished = {Cryptology ePrint Archive, Paper 2014/992},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/992}},
      url = {https://eprint.iacr.org/2014/992}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.