MASTERÂ Assignment
zk-SCHNAPS: Enforcing Arbitrary Password Policies in a Zero- Knowledge Password Protocol
Type : Master M-CS
Period: Mar, 2022 - Oct, 2022
Student : Roelink, M.J. (Matthijs, Student M-CS)
Date Final project: Oct 31, 2022
Supervisors:
Abstract:
In this thesis, we introduce zk-SCHNAPS; zero-knowledge Secure Commitment-based Homomorphic Non-interactive Authentication with Passwords using SNARKs. With this password authentication protocol, arbitrary password policies can be enforced by a server, without having the requirement or possibility of inspecting the password. This prevents a server from leaking users' passwords, whether accidentally or on purpose, while still forcing users to choose strong passwords. We do this by using a zk-SNARK to proof compliance of a password during registration, and combining it with a SNARK-friendly encryption scheme (SAVER) to yield an encryption of the password that can be stored by the server. During login, the password is encrypted similar to the SAVER encryption and combined with a zero-knowledge proof, affirming the knowledge of the password that is encrypted. Using the homomorphic property of SAVER, the server can check whether the passwords are equal, without decrypting the individual ciphertexts. We implemented the proposed scheme and show that both proof generation and password verification run in practical time (a few seconds and less than a second respectively) for several real-world password policies, including a blocklist of 100,000 items.