Multi-Factor Password-Authenticated Key Exchange via Pythia PRF Service

Multi-factor authentication (MFA) was proposed by Pointcheval et al. [Pointcheval and Zimmer (2008)] to improve the security of single-factor (and two-factor) authentication. As the backbone of multi-factor authentication, biometric data are widely observed. Especially, how to keep the privacy of biometric at the password database without impairing efficiency is still an open question. Using the vulnerability of encryption (or hash) algorithms, the attacker can still launch offline brute-force attacks on encrypted (or hashed) biometric data. To address the potential risk of biometric disclosure at the password database, in this paper, we propose a novel efficient and secure MFA key exchange (later denoted as MFAKE) protocol leveraging the Pythia PRF service and password-to-random (or PTR) protocol. Armed with the PTR protocol, a master password pwd can be translated by the user into independent pseudorandom passwords (or rwd) for each user account with the help of device (e.g., smart phone). Meanwhile, using the Pythia PRF service, the password database can avoid leakage of the local user’s password and biometric data. This is the first paper to achieve the password and biometric harden service simultaneously using the PTR protocol and Pythia PRF.