Vemaque: An Approximate Verifiable Remote Computation Mechanism For K-Clique And Maximum Clique Problem

Abstract

Recently, Devices with relatively limited computational power and memory capacity tend to outsource their computations and data storage to powerful machines: third parties. When a client outsources a job to a third party (e.g. the cloud), how can the client trust the result returned from it ,since many things can go wrong in the third-party computation without knowing the client device. So In the past few years, there is an increasing interest to allow client to verify the correctness of the results returned from the third-party without re-executing the computation in client machine. Recent works based on proof-based verifiable computation have made significant progress on this area by incorporating deep results of theoretical computing and complexity theory into nearly practical built systems. But these systems can handle a restricted class computations: simple straight-line computations with repeated structure. This study describes Vemaque, a practical built system to approximately verify two NP-complete computations: k-clique problem and maximum clique problem. Thus Vemaque takes another step towards practical verifiable real life computations overcoming this limitation. Vemaque uses the power of interactive proofs and the probabilistically checkable proofs to achieve a reasonable client's verification cost. Vemaque allows client to verify the results returned from untrusted server approximately. Our experiment have shown that Vemaque has achieved more than 98% accuracy for verifying both k-clique problem and maximum clique problem. And also, we report the experimental results concerning the performance and efficiency of Vemaque. Finally we present the powers and limitations of Vemaque.