1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – mikeazo Sep 19 '17 at 16:33
  • $\begingroup$ 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. $\endgroup$ – Paradox Sep 19 '17 at 16:52
  • $\begingroup$ Have you seen this Q&A? $\endgroup$ – mikeazo Sep 19 '17 at 17:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.