IACR News item: 29 January 2013
anonymized for paper review
ePrint ReportIn 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.
Additional news items may be found on the IACR news page.