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?
I was oversimplifying to convey an intuition on why this is so hard. But yes, this is an active area of research.
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.
In homomorphic systems the server only sees the encrypted result. Since it can not decrypt it, it doesn't gain any information from it. And indeed the encryption is scrambled differently for each query, otherwise you could learn if two values are the same.
