The killer thing is the performance penalty for doing FHE on any dataset of meaningful size. This is because if you want to do an operation on one member of the set you need to do an operation on all members of the set otherwise you leak which member you care about. For sets of a very small size this performance penalty might be ok. For sets of a large size, like the set of all users of a service, the performance penalty will grow at least linearly to the size of the set.

This is the problem at the core of ZK-style proving systems. You can push the proof construction work into the client and have a sub-linear verification time relative to the proof, but the proof construction in the first place is going to be slow and expensive (and slower as the size of the set increases!).

The edge of research here is being done by cryptography labs all around the world. If someone does manage to solve this in a purely-software based manner with a performance penalty that is acceptable for a monotonically increasing set, that’s the holy grail. I remain unconvinced that this will be solved in a reasonable fashion for this use case in my lifetime (but I would be thrilled to be proven wrong!!). If you know of research which makes inroads on this problem, please point me at it.