SafeComp: Protocol For Certifying Cloud Computations Integrity
This addresses security and trust issues in cloud computing for users relying on remote computations, but it appears incremental as it builds on existing work with specific improvements.
The paper tackles the problem of certifying computation integrity by untrusted remote parties, presenting the SafeComp protocol that reduces proof construction complexity from O(n log n) to O(n) and communication to one round with comparable certificate length.
We define a problem of certifying computation integrity performed by some remote party we do not necessarily trust. We present a multi-party interactive protocol called SafeComp that solves this problem under specified constraints. Comparing to the nearest related work, our protocol reduces a proof construction complexity from $O(n \log{n})$ to $O(n)$, turning a communication complexity to exactly one round using a certificate of a comparable length.