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".
Obviously something needs to be trusted. If there is no prior  trusted something it can't be done.
In one setup used in DNSsec a trusted party signs empty intervals according to some ordering. So when you want to give a negative answer you provide the signed empty interval.
Obviously there is a problem with the validity of such answers when the data changes. You may get a properly signed but obsolete answer. Though people can in many cases commit on a  certain record remaining valid for a significant time frame. Commiting to a range remaining empty is much harder.