3
$\begingroup$

Suppose I maintain a proprietary database and claim that it has N records. Before subscribing to my database a client wants a proof that the database is indeed this large. What theoretical protocol can I employ to prove my database size with possibly revealing only a small number of records?

$\endgroup$
  • 2
    $\begingroup$ Do you want to prove that the records satisfy some particular property? Which one? Otherwise, even if you could prove you have $N$ records, all of those could just be zeros. $\endgroup$ – chi Mar 15 '17 at 12:42
  • $\begingroup$ Welcome to CS.SE! Please edit the question to provide more context. Does the client know what the records should be? If the clients was shown one or more records, could the client verify that those records are valid? What's the threat model for how a malicious server might behave? Can you tell us what your actual, real-world problem is? Whether this is solvable is likely to be dependent on specific details of your goals, your threat model, and domain-specific assumptions, so maybe we can be more helpful if you can tell us the real-world situation you have. $\endgroup$ – D.W. Mar 15 '17 at 17:07
3
$\begingroup$

I think the usual way of doing this is that you hash each record (with a known cryptographically secure hash) and provide the client with $N$ hash values. The client chooses $k$ out of those hash values and you reply with the corresponding $k$ records. The client can then verify that the hash values match up correctly with the provided records plus whatever record validation they'd like to do. Note that if you have duplicate records in your DB, those duplicates could be inferred from provided hash values (e.g.: the client could get a pretty good estimate of the number of distinct records in your DB). If this is undesirable, then you can salt the hashes.

$\endgroup$
  • $\begingroup$ But what is the procedure to set up the hash so that the client can trust he is not cheated? Could you point to some names / literature? $\endgroup$ – Valentas Mar 16 '17 at 6:53
  • $\begingroup$ I guess you're going to have to be a little more explicit about your threat model -- namely, can you be very specific about the ways in which the client can be cheated? $\endgroup$ – mhum Mar 16 '17 at 17:04
  • $\begingroup$ Sorry, this is really the answer - it is really as simple as choosing any good hash function for both owner and client. $\endgroup$ – Valentas Mar 17 '17 at 9:31

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.