deterministic randomness extractor and privacy
I came across this late. Don't know if this question still matters. I am posting this as an answer since it is too long for a comment. 

If n can be 1 but m is not too large (say, at most a small exponential in the min-entropy), a random function will be a good extractor with high probability. It will cost you a factor of something like log m in the min-entropy. 

However, for large values of n, you should be able to find a good deterministic  extractor no matter how large m is since, once you condition on x, the distribution on outputs is IID. In particular, it is symmetric, so you can use as idea like von Neumann's trick or its generalizations to extract a small number of random bits just from the ordering of the elements. That might be enough to get the seed for a strong randomness extractor which could extract the rest of the randomness from the source. You have to be careful, but the idea would be to rely heavily on the IID structure to get a a deterministic extractor. Don't know if that's good enough for the application.