Would it be possible to store subscription data without actually linking it to the account that is affected? Sort of like a one way encryption.
Perhaps a better model is the client stores the necessary data, and presents it when trying to connect?
If Eve can determine the basis for which an account is identified, and there is a small number of subscriptions,[1] then the namespace may be exhaustively searched.
Mind that even if the resulting hash space is large, if the key space is small, the search is tractable. Just look for a resulting valid hash.
Even if a payment is required, if $0.01 is accepted, the cost for testing 1 million keys is $10,000. For a sufficiently high-value target, potentially reasonable. More so if you can create your own money.
________________________________
Notes:
1. For computers, any value < 10 billion is arguably small, and quite possibly somewhat larger than that. The present human population is < 10 billion. The Mulvad subscription list is all but certainly <<<10 billion, where '<<<' -> "very much smaller than".
All the ways I come up with (giving out keys) have the problem of how do you renew the key, and how do you cancel it, without knowing which is which.
e.g.
1. Connect to Mullvad over Tor, authenticate with real-world user ID
2. Use this to sign a blinded token
3. Use this to connect to Mullvad anonymously after some delay
The first run would be kind of dodgy, but after that you could get new session keys on a fixed schedule and switch them out at a random interval.
If they see that user A authenticates and 10 minutes later, key A comes online, that can be traced, but if you then wait a week, authorize key B, and then wait a few more days to start using it, you should be good.
In practice, this has way too many issues to work in practice. It still requires you to trust them not to e.g. log IPs and correlate it that way, so it's all just snake oil.