1

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".

Paradox
  • 467
  • 3
  • 9
  • 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](https://crypto.stackexchange.com/questions/31914/proof-of-non-membership-on-a-merkle-tree)? – mikeazo Sep 19 '17 at 17:09

1 Answers1

1

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.

Meir Maor
  • 11,497
  • 1
  • 22
  • 52