A method for implementing secure instant messaging comprising: receiving, by an identity service from a mobile device of first user, a request to establish an instant messaging session with a second user, the request including an identification code identifying the second user; determining, by the identity service, whether the second user has one or more mobile devices registered on a network service; if the second user has one or more mobile devices registered, providing, by the identity service to the mobile device of the first user, addressing information identifying the one or more mobile devices of the second user and a public key associated with the second user; providing, by the identity service to a push notification service, a session key comprising a signature generated with identification codes of the first and second users and network information for the mobile devices of the first and second users; receiving, by the push notification service from the mobile device of the first user, an encrypted instant message generated by the mobile device of the first user using the public key of the second user and a private key of the first user;' transmitting, by the push notification service to a secure instant message service, the session key and the encrypted instant message; verifying, by the secure instant message service, the encrypted message using the identification codes of the first and second users, the network information of the first and second users, and the session key; receiving, by the push notification service from the secure instant message service, the verified encrypted message; and transmitting, by the push notification service to the one or more mobile devices of the second user, the verified encrypted instant message, the one or more mobile devices of the second user subsequently decrypting the verified encrypted instant message using a private key of the second user. receiving, by an identity service from a mobile device of first user, a request to establish an instant messaging session with a second user, the request including an identification code identifying the second user; determining, by the identity service, whether the second user has one or more mobile devices registered on a network service; if the second user has one or more mobile devices registered, providing, by the identity service to the mobile device of the first user, addressing information identifying the one or more mobile devices of the second user and a public key associated with the second user; providing, by the identity service to a push notification service, a session key comprising a signature generated with identification codes of the first and second users and network information for the mobile devices of the first and second users; receiving, by the push notification service from the mobile device of the first user, an encrypted instant message generated by the mobile device of the first user using the public key of the second user and a private key of the first user;' transmitting, by the push notification service to a secure instant message service, the session key and the encrypted instant message; verifying, by the secure instant message service, the encrypted message using the identification codes of the first and second users, the network information of the first and second users, and the session key; receiving, by the push notification service from the secure instant message service, the verified encrypted message; and transmitting, by the push notification service to the one or more mobile devices of the second user, the verified encrypted instant message, the one or more mobile devices of the second user subsequently decrypting the verified encrypted instant message using a private key of the second user.