Data integrity verification scheme with designated verifiers for dynamic outsourced databases

ABSTRACT In order to verify the integrity of the query results in outsourced database model, we first present a new authenticated data structure by combining skip lists with polynomial functions and accumulators and then construct a data integrity verification scheme for range query. Our scheme can verify the integrity of the query results with constant time verification and constant size proof and support dynamic maintenance with constant computational cost. Compared with that of previous schemes, the communication cost in our scheme is independent of the size of the authenticated dataset and is lower. When dataset size gets larger enough, our scheme outperforms previous schemes in terms of the computational cost and verification cost. In addition, we introduce the designated verifier idea into our scheme, so our scheme achieves the result that none but subscribers can verify the integrity of the query results and then meets the practical demands such as the payment service. The proof of security and analysis of experiment performance show that our scheme is secure and efficient for larger outsourced databases. Copyright © 2013 John Wiley & Sons, Ltd.