Vemaque: Approximately verifiable remote computation of k-clique and maximum clique problems
R.G.L.M. Samarawickrama, D. N. Ranasinghe, T. Sritharan · 2016
When a client needs to delegate the computation of a task to another party, there will often be a need to verify the result returned from that party, without re-executing whole of the computation. Recent work on verifiable remote computation has made a significant advancement on this problem by solving it to near practicality. However such works can only handle a restricted class of computation such as linear computations. Towards solving this gap, this paper presents Vemaque, a system to approximately verify two NP-complete computations (the k-clique problem and the maximum clique problem) that are not addressed in prior works. Experimental results show that Vemaque has achieved more than 98% accuracy of verification and reasonable performance using probabilistic proof systems.