Prove count without revealing data
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.