# how to efficiently prove the query result is empty?

Consider a simplified scenario. Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$.

A client issues a query $b$ to the server and wants to decide if $b\in A$. The server replies a "yes" or "no". Then how can the client verify the correctness of the server's reply?

It is relatively simple if $b$ is indeed in $A$ and the server answers "yes". We can use some siganature- or hash-based schemes. However, what if the server just reply "no"? How can the client verify that $b$ is not in the set?

I know (but not much) some schemes such as Authenticated Set. But the complexity seems rather high.

So I am looking for efficient schemes that can prove that the query result is indeed "empty".

• Any other security requirements? For example, if the server commits to $A$ in advance, then sees the query $b$, the server can just reveal $A$. I'm assuming that the client should learn no additional information about $A$ beyond whether or not $b$ is in the set. Is that a security requirement? – mikeazo Sep 19 '17 at 16:33
• I am mainly considering efficiency issues. Client can be the data owner that owns $A$ and outsources $A$ to the server. And the client does not possess $A$ anymore locally. $A$ could be very big. So reveal $A$ to the client for every single query is very expensive in terms of communication. – Paradox Sep 19 '17 at 16:52
• Have you seen this Q&A? – mikeazo Sep 19 '17 at 17:09