Paper 2014/178

Verifiable Delegated Set Intersection Operations on Outsourced Encrypted Data

Qingji Zheng and Shouhuai Xu


We initiate the study of the following problem: Suppose Alice and Bob would like to outsource their encrypted private data sets to the cloud, and they also want to conduct the set intersection operation on their plaintext data sets. The straightforward solution for them is to download their outsourced ciphertexts, decrypt the ciphertexts locally, and then execute a commodity two-party set intersection protocol. Unfortunately, this solution is not practical. We therefore motivate and introduce the novel notion of {\em Verifiable Delegated Set Intersection on outsourced encrypted data} (VDSI). The basic idea is to delegate the set intersection operation to the cloud, while (i) not giving the decryption capability to the cloud, and (ii) being able to hold the misbehaving cloud accountable. We formalize security properties of VDSI and present a construction. In our solution, the computational and communication costs on the users are linear to the size of the intersection set, meaning that the efficiency is optimal up to a constant factor.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
qingjizheng @ gmail com
2014-03-06: received
Short URL
Creative Commons Attribution


      author = {Qingji Zheng and Shouhuai Xu},
      title = {Verifiable Delegated Set Intersection Operations on Outsourced Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2014/178},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.