Correctness Verification in Outsourced Databases: More Reliable Fake Tuples Approach

摘要

Enterprises outsource data to storage service providers in order to avail resources at lower costs and for ensuring economy of scale. Prime concerns of organizations are privacy of data and quality of service provided, which include correctness of query results and integrity of data. In earlier works, integrity of data is verified by preserving hash of tuple data as header attribute and completeness is assured by inserting and retrieving fake tuples. In this work, we propose a secret sharing based approach for deterministic generation of fake tuples used for verifying completeness and integrity of data, where we eliminate the dependency on header attribute. Our integrity check mechanisms work faster than existing approaches in this direction as depicted in our experimental results. Furthermore, we show that our approach is information theoretically secure, where an adversary without knowledge of underlying security parameters can never be able to break the scheme.