In a credential recovery process, a user is authenticated using an application running on a mobile communications device, and requests recovery of a credential. The application generates a session key encrypted with the public key of a gateway, and sends the encrypted key to the gateway. The gateway recovers the credential from a depository, encrypted using a symmetric key shared with the depository. The gateway decrypts the credential and re-encrypts the credential using the session key. Preferably, the decryption and re-encryption is performed within a hardware secure module within the gateway. The re-encrypted credential is sent to the application, which decrypts the credential and outputs it to the user. In this way, the credential is provided securely to the user and may be made available for use immediately, or nearly so.