Verifiable database outsourcing supporting join

We propose a hierarchical authenticated data structure for storing security information, which alleviates the mentioned problems. Our solution handles many different types of queries, including multi-clause selection and join queries, in a dynamic database. We provide a unified formal definition of a secure outsourced database scheme, and prove that our proposed scheme is secure according to this definition, which captures previously separate properties: correctness, completeness, and freshness. The performance evaluation based on our prototype implementation confirms the efficiency of our proposed scheme, showing ∼3x smaller proofs and ∼5x improvement in proof generation time compared to previous works (Devanbu et al. 2002; Pang et al. 2005; Li et al. 2010; Palazzi et al. 2010).