International Association
for Cryptologic Research

We propose the concept of Zero-Knowledge Password Policy Checks (ZKPPC) to enable remote registration of client passwords without their actual transmission to the server. The ZKPPC protocol executed as part of the client registration process allows the client to prove compliance of the chosen password with the password policy defined by the server. The main benefit of ZKPPC-based password registration is that it guarantees that passwords can never be processed nor stored in clear on the server side. At the end of the registration phase the server only receives and stores some verification information that can later be used for authentication in suitable Verifier-based Password Authenticated Key Exchange (VPAKE) protocols.

To this end, we first formalize the requirements of ZKPPC protocols and propose a general framework for their construction in the standard model using randomised password hashing and set membership proofs. We design a suitable encoding scheme for password characters and show how to express password policies to allow the adoption of set membership proofs. Finally, we present a concrete ZKPPC-based registration protocol that is based on efficient Pedersen commitments and corresponding proofs, and analyse its performance.

To complete the ZKPPC-based registration and authentication framework we propose a concrete VPAKE protocol, where the server can use the obtained verification information from the ZKPPC-based registration phase to subsequently setup secure communication sessions with the client. Our VPAKE protocol follows the recent framework for the construction of such protocols and is secure in the standard model.