Methods, systems, and techniques for private identity verification involve obtaining a cryptographically secure commitment that is generated using a first user identifier and a private user identifier associated with the first user identifier; receiving, from an identity verification system, initial zero knowledge proof messages comprising the commitment; sending, to the identity verification system, a set of cryptographically secure known identifier commitments generated using a set of private user identifiers; receiving, from the identity verification system: (i) a zero knowledge proof response generated using the zero knowledge proof challenge; and (ii) proof that the private user identifier used in the initial zero knowledge proof messages comprises part of the set of private user identifiers; and verifying that the private user identifier used in the initial zero knowledge proof messages comprises part of the set of private user identifiers.