Abstract: User authentication can rely on various factors (e.g., a pass-word, a cryptographic key, biometric data) but should not reveal anysecret or private information. This seemingly paradoxicalfeat can beachieved through zero-knowledge proofs. Unfortunately, naive password-based approaches still prevail on the web. Multi-factor authenticationschemes address some of the weaknesses of the traditional login pro-cess, but generally have deployability issues or degrade usability evenfurther as they assume users do not possess adequate hardware. This as-sumption no longer holds: smartphones with biometric sensors, cameras,short-range communication capabilities, and unlimited data plans havebecome ubiquitous. In this paper, we show that, assuming theuser hassuch a device, both security and usability can be drastically improvedusing an augmented password-authenticated key agreement (PAKE) pro-tocol and message authentication codes.