# Prove count without revealing data

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?

• 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. – chi Mar 15 '17 at 12:42
• 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. – D.W. Mar 15 '17 at 17:07

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.