TY - GEN
T1 - TRUESET
T2 - 23rd USENIX Security Symposium
AU - Kosba, Ahmed E.
AU - Papadopoulos, Dimitrios
AU - Papamanthou, Charalampos
AU - Sayed, Mahmoud F.
AU - Shi, Elaine
AU - Triandopoulos, Nikos
N1 - Publisher Copyright:
copyright © 2014 USENIX Security Symposium.All right reserved.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85076320533&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076320533&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85076320533
T3 - Proceedings of the 23rd USENIX Security Symposium
SP - 765
EP - 780
BT - Proceedings of the 23rd USENIX Security Symposium
Y2 - 20 August 2014 through 22 August 2014
ER -