We present and define a privacy-preserving problem called the oblivious set-member decision problem, which allows a server to decide whether a private secret of a user is a member of his private set in an oblivious manner. Namely, if the secret belongs to his private set, he does not know which member it is. We propose a quantum solution to the oblivious set-member decision problem. Compared to classical solutions, the proposed quantum protocol achieves an exponential reduction in communication complexity, since it only needs $O\left(1\right)$ communication cost.

• Received 12 March 2015

DOI:https://doi.org/10.1103/PhysRevA.92.022309