I think the only way not to leak any information through caching is not to cache anything.
What do you think about my bloom filter idea?
> What do you think about my bloom filter idea?
It sounds interesting, but I suspect that you're right that caching leaks no matter what — I wonder if it's almost like compression in that sense (and we remember how compression impacts HTTPS!).
Conceivably, a server could generate random null resources which are cached by the client and can then be used, as the GP indicates, to identify it — yet another supercookie.