With the raising trend of outsourcing databases to the cloud server, it is important to efficiently and securely assure that the clients\' queries on the databases are executed correctly. To address this issue, server schemes have been proposed based on various cryptographic tools. However, these existing schemes have limitations in either communication cost or computational cost for verification. Meanwhile, only four types of SQL functional queries are supported in these schemes. It still remains as an open problem to design a verifiable SQL query scheme that provides affordable storage overhead, communication cost, computational cost and more SQL functional queries.
In this paper, we investigate this open problem and propose an efficient verifiable SQL query scheme for outsourced dynamic databases. Different from the previous state-of-the-art schemes, we reduce the complexity of storage overhead from O(mn) to O(n) and move most computation tasks from client side to cloud server side. Compared with the recently proposed scheme that also achieves O(n) storage overhead, we not only cut the communication complexity for verification from O(n) to O(log^n), but also release the client from O(n) exponentiation operations to O(1). In addition, our proposed scheme improves the previous ones by allowing more aggregate queries including variance query, weighted exponentiation sum query of any degrees, etc. Thorough analysis shows the efficiency and scalability of our proposed scheme. The security of our scheme is proved based on Strong Diffie-Hellman Assumption, Bilinear Strong Diffie-Hellman Assumption and Computational Diffie-Hellman Assumption.