Recovery of Encrypted Mobile Device Backups from Partially Trusted Cloud Servers

Including electronic identities (eIDs), such as passports or driving licenses in smartphones transforms them into a single point of failure: loss, theft, or malfunction would prevent their users even from identifying themselves e.g. during travel. Therefore, a secure backup of such identity data is paramount, and an obvious solution is to store encrypted backups on cloud servers. However, the critical challenge is how a user decrypts the encrypted data backup if the user's device gets lost or stolen and there is no longer a secure storage (e.g. smartphone) to keep the secret key. To address this issue, Password-Protected Secret Sharing (PPSS) schemes have been proposed which allow a user to store a secret key among n servers such that the user can later reconstruct the secret key. Unfortunately, PPSS schemes are not appropriate for some applications. For example, users will be highly unlikely to remember a cryptographically strong password when the smartphone is lost. Also, they still suffer from inefficiency. In this paper, we propose a new secret key reconstruction protocol based recently popular PPSS schemes with a Fuzzy Extractor which allows a client to recover secret keys from an only partially trusted server and an auxiliary device using multiple key shares and a biometric identifier. We prove the security of our proposed protocol in the random oracle model where the parties can be corrupted separately at any time. An initial performance analysis shows that it is efficient for this use case.