A method and apparatus for protecting the identities of mobile devices on a wireless network are described. A proxy gateway couples the wireless network to a wired network and maintains data associating a set of service initiators with a set of cryptographic keys. Upon receiving a request from a mobile client device directed to an origin server on the wired network, the proxy gateway identifies the cryptographic key for that origin server and sends to the origin server a proxy request. The proxy request includes an identifier of the mobile device, encrypted using the cryptographic key. When the proxy gateway receives a request from a service initiator on the wired network to push information to a mobile device, it uses the cryptographic key for that service initiator to decode a client identifier in the request and thereby determine whether the request is valid.