“IMSI catching is a problem on all generations of mobile telecommunication networks, i.e., 2g (gsm, gprs), 3g (hdspa, edge, umts) and 4g (lte, lte+). currently, the sim card of a mobile phone has to reveal its identity over an insecure plaintext transmission, before encryption is enabled. this identifier (the imsi) can be intercepted by adversaries that mount a passive or active attack. such identity exposure attacks are commonly referred to as ‘imsi catching’. since the imsi is uniquely identifying, unautho-rized exposure can lead to various location privacy attacks. we propose a solution, which essentially replaces the im-sis with changing pseudonyms that are only identifiable by the home network of the sim’s own network provider. con-sequently, these pseudonyms are unlinkable by intermedi-ate network providers and malicious adversaries, and there-fore mitigate both passive and active attacks, which we also formally verified using proverif. our solution is compati-ble with the current specifications of the mobile standards and therefore requires no change in the infrastructure or any of the already massively deployed network equipment. the proposed method only requires limited changes to the sim and the authentication server, both of which are un-der control of the user’s network provider. therefore, any individual (virtual) provider that distributes sim cards and controls its own authentication server can deploy a more pri-vacy friendly mobile network that is resilient against imsi catching attacks.”