In this work, we show that for functionalities that can be expressed efficiently in terms of set operations (e.g., a subset of SQL queries) VC can be enhanced to become drastically more practical: we present the design and prototype implementation of a novel VC scheme that achieves orders of magnitude speed-up in comparison with the state of the art. Specifically, we build and evaluate TRUESET, a system that can verifiably compute any polynomial-time function expressed as a circuit consisting of \set gates" such as union, intersection, difference and set cardinality. Moreover, TRUESET supports hybrid circuits consisting of both set gates and traditional arithmetic gates. Therefore, it does not lose any of the expressiveness of the previous schemes|this also allows the user to choose the most efficient way to represent different parts of a computation. By expressing set computations as polynomial operations and introducing a novel Quadratic Polynomial Program technique, TRUESET achieves prover performance speed-up ranging from 30x to 150x and yields up to 97% evaluation key size reduction.
Category / Keywords: cryptographic protocols / verifiable computation; set SNARKs; quadratic polynomial programs; Date: received 2 Mar 2014, last revised 11 Aug 2014 Contact author: dipapado at bu edu Available format(s): PDF | BibTeX Citation Version: 20140811:202340 (All versions of this report) Short URL: ia.cr/2014/160 Discussion forum: Show discussion | Start new discussion