A network-based data protection scheme for a mobile device utilizes encryption techniques and a remote key server that stores encryption keys on behalf of the mobile device. The mobile device stores encrypted data, preferably having no unencrypted counterpart stored therewith. On an as-needed basis, the mobile device requests a decryption key (or an encrypted version of a decryption key) from the key server, where the decryption key can be used by the mobile device to decrypt the encrypted information. The key server transmits the decryption key to the mobile device after authenticating the user of the mobile device.