Does it actually have to process all rows equally? Would a bit of randomisation on search + erasure coding of data could allow both reconstruction of message, and preserving secrecy by querying random places for the same information?
In this academic field the standard for privacy is usually extremely high. Even if you only access half of the rows, that still leaks one bit of information and would not be considered zero-knowledge.