Ecole d'ingénieur et centre de recherche en Sciences du numérique

Publicly verifiable keyword search in outsourced databases

Azraoui, Monir; Elkhiyaoui, Kaoutar; Önen, Melek; Molva, Refik

Research Report RR-15-303

Recent technological developments in cloud computing and the ensuing commercial appeal have encouraged companies and individuals to outsource their storage and computations to powerful cloud servers. However, the challenge when outsourcing data and computation is to ensure that the cloud servers comply with their advertised policies. In this paper, we focus in particular on the scenario where a data owner wishes to (i) outsource its public database to a cloud server; (ii) enable anyone to submit multi-keyword search queries to the outsourced database; and (iii) ensure that anyone can verify the correctness of the server’s responses. To meet these requirements, we propose a solution that builds upon the well-established techniques of Cuckoo hashing, polynomial-based accumulators and Merkle trees. The key idea is to (i) build an efficient index for the keywords in the database using Cuckoo hashing; (ii) authenticate the resulting index using polynomial-based accumulators and Merkle tree; (iii) and finally, use the root of the Merkle tree to verify the correctness of the server’s responses. Thus, the proposed solution yields efficient search and verification and incurs a constant storage at the data owner. Furthermore, we show that it is sound under the strong bilinear Diffie-Hellman assumption and the security of Merkle trees.

Document Bibtex

Titre:Publicly verifiable keyword search in outsourced databases
Mots Clés:Cloud Storage, Verifiability, Keyword Search
Département:Sécurité numérique
Eurecom ref:4540
Copyright: © EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Research Report RR-15-303 and is available at :
Bibtex: @techreport{EURECOM+4540, year = {2015}, title = {{P}ublicly verifiable keyword search in outsourced databases}, author = {{A}zraoui, {M}onir and {E}lkhiyaoui, {K}aoutar and {\"{O}}nen, {M}elek and {M}olva, {R}efik }, number = {EURECOM+4540}, month = {04}, institution = {Eurecom}, url = {},, }
Voir aussi: