TY - GEN
T1 - VSQL
T2 - 2017 IEEE Symposium on Security and Privacy, SP 2017
AU - Zhang, Yupeng
AU - Genkin, Daniel
AU - Katz, Jonathan
AU - Papadopoulos, Dimitrios
AU - Papamanthou, Charalampos
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/23
Y1 - 2017/6/23
N2 - Cloud database systems such as Amazon RDS or Google Cloud SQLenable the outsourcing of a large database to a server who then responds to SQL queries. A natural problem here is to efficiently verify the correctness of responses returned by the (untrusted) server. In this paper we present vSQL, a novel cryptographic protocol for publicly verifiable SQL queries on dynamic databases. At a high level, our construction relies on two extensions of the CMT interactive-proof protocol [Cormode et al., 2012]: (i) supporting outsourced input via the use of a polynomial-delegation protocol with succinct proofs, and (ii) supporting auxiliary input (i.e., non-deterministic computation) efficiently. Compared to previous verifiable-computation systems based on interactive proofs, our construction has verification cost polylogarithmic in the auxiliary input (which for SQL queries can be as large as the database) rather than linear. In order to evaluate the performance and expressiveness of our scheme, we tested it on SQL queries based on the TPC-H benchmark on a database with 6 million rows and 13 columns. The server overhead in our scheme (which is typically the main bottleneck) is up to 120 times lower than previousapproaches based on succinct arguments of knowledge (SNARKs), and moreover we avoid the need for query-dependent pre-processing which is required by optimized SNARK-based schemes. In our construction, the server/client time and the communication cost are comparable to, and sometimessmaller than, those of existing customized solutions which only support specific queries.
AB - Cloud database systems such as Amazon RDS or Google Cloud SQLenable the outsourcing of a large database to a server who then responds to SQL queries. A natural problem here is to efficiently verify the correctness of responses returned by the (untrusted) server. In this paper we present vSQL, a novel cryptographic protocol for publicly verifiable SQL queries on dynamic databases. At a high level, our construction relies on two extensions of the CMT interactive-proof protocol [Cormode et al., 2012]: (i) supporting outsourced input via the use of a polynomial-delegation protocol with succinct proofs, and (ii) supporting auxiliary input (i.e., non-deterministic computation) efficiently. Compared to previous verifiable-computation systems based on interactive proofs, our construction has verification cost polylogarithmic in the auxiliary input (which for SQL queries can be as large as the database) rather than linear. In order to evaluate the performance and expressiveness of our scheme, we tested it on SQL queries based on the TPC-H benchmark on a database with 6 million rows and 13 columns. The server overhead in our scheme (which is typically the main bottleneck) is up to 120 times lower than previousapproaches based on succinct arguments of knowledge (SNARKs), and moreover we avoid the need for query-dependent pre-processing which is required by optimized SNARK-based schemes. In our construction, the server/client time and the communication cost are comparable to, and sometimessmaller than, those of existing customized solutions which only support specific queries.
UR - http://www.scopus.com/inward/record.url?scp=85024489454&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024489454&partnerID=8YFLogxK
U2 - 10.1109/SP.2017.43
DO - 10.1109/SP.2017.43
M3 - Conference contribution
AN - SCOPUS:85024489454
T3 - Proceedings - IEEE Symposium on Security and Privacy
SP - 863
EP - 880
BT - 2017 IEEE Symposium on Security and Privacy, SP 2017 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 22 May 2017 through 24 May 2017
ER -