Cryptology ePrint Archive: Report 2014/178

Verifiable Delegated Set Intersection Operations on Outsourced Encrypted Data

Qingji Zheng and Shouhuai Xu

Abstract: 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.

Category / Keywords: cryptographic protocols /

Date: received 5 Mar 2014

Contact author: qingjizheng at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140306:200834 (All versions of this report)

Short URL: ia.cr/2014/178

Discussion forum: Show discussion | Start new discussion