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
  • 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
    Commented Mar 15, 2017 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.
    Commented Mar 15, 2017 at 17:07

1 Answer 1

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$
3
  • $\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
    Commented Mar 16, 2017 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
    Commented Mar 16, 2017 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
    Commented Mar 17, 2017 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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