Paper 2017/1145

vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases

Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, and Charalampos Papamanthou

Abstract

Cloud database systems such as Amazon RDS or Google Cloud SQL enable 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 \times 10^6$ rows and $13$ columns. The server overhead in our scheme (which is typically the main bottleneck) is up to $120\times$ lower than previous approaches 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 sometimes smaller than, those of existing customized solutions which only support specific queries.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.2017 IEEE Symposium on Security and Privacy, SP 2017
DOI
10.1109/SP.2017.43
Keywords
verifiable computationinteractive argumentsverifiable database queriesverifiable polynomial delegation
Contact author(s)
dipapado @ cse ust hk
History
2017-11-27: received
Short URL
https://ia.cr/2017/1145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1145,
      author = {Yupeng Zhang and Daniel Genkin and Jonathan Katz and Dimitrios Papadopoulos and Charalampos Papamanthou},
      title = {vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1145},
      year = {2017},
      doi = {10.1109/SP.2017.43},
      note = {\url{https://eprint.iacr.org/2017/1145}},
      url = {https://eprint.iacr.org/2017/1145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.