TRUESET: Faster Verifiable Set Computations
TRUESET: Faster Verifiable Set Computations
复制标题
TRUESET：更快的可验证集合计算
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Nikos Triandopoulos
中科院分区：
文献类型：
--
作者：
Ahmed E. Kosba;D. Papadopoulos;Charalampos Papamanthou;Mahmoud F. Sayed;E. Shi;Nikos Triandopoulos
可验证计算（Verifiable Computation，VC）使瘦客户机能够有效地验证功能强大的服务器产生的计算结果。虽然风险投资最初被认为主要是理论上的兴趣，但在过去两年中，在实施风险投资方面取得了令人印象深刻的进展。具体来说，我们现在有VC系统的开源实现，可以处理以电路或RAM模型表示的所有计算类。尽管取得了这一令人鼓舞的进展，新的增强，在VC协议的设计和实现需要实现真正实用的VC为现实世界的应用程序。
在这项工作中，我们表明，对于可以有效地表达在集合运算方面的函数（例如，SQL查询的一个子集）VC可以得到增强，变得更加实用：我们提出了一种新的VC方案的设计和原型实现，该方案与现有技术相比实现了数量级的加速。具体而言，我们构建并评估了TRUESET，一个可以验证计算任何多项式时间函数的系统，该函数表示为由“集合门”组成的电路，如并集，交集，差异和集合基数。此外，TRUESET支持混合电路，包括设置门和传统的算术门。因此，它不会失去以前方案的任何表现力-这也允许用户选择最有效的方式来表示计算的不同部分。通过将集合计算表示为多项式运算并引入新颖的二次多项式编程技术，我们的实验表明，与最先进的技术相比，TRUESET实现了30倍至150倍的证明器性能加速，并将评估键大小减少了高达97%。
Verifiable computation (VC) enables thin clients to efficiently verify the computational results produced by a powerful server. Although VC was initially considered to be mainly of theoretical interest, over the last two years impressive progress has been made on implementing VC. Specifically, we now have open-source implementations of VC systems that handle all classes of computations expressed either as circuits or in the RAM model. Despite this very encouraging progress, new enhancements in the design and implementation of VC protocols are required to achieve truly practical VC for real-world applications.
In this work, we show that for functions 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 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, our experiments show that TRUESET achieves prover performance speed-up ranging from 30x to 150x and up to 97% evaluation key size reduction compared to the state-of-the-art.