In the proposed protocol, a trusted entity interacts with the terminal device of each user to verify the legitimacy of the public keys without having access to the private keys that are generated and kept totally secret by the user. The protocol introduces challenge–response–pair mechanisms enabling the generation, distribution, and verification of cryptographic public–private key pairs in a distributed network with multi-factor authentication, tokens, and template-less biometry. While protocols using generic digital signature algorithms are proposed, the focus of the experimental work was to implement a solution based on Crystals-Dilithium, a post-quantum cryptographic algorithm under standardization. Crystals-Dilithium generates public keys consisting of two interrelated parts, a matrix generating seed, and a vector computed from the matrix and two randomly picked vectors forming the secret key. We show how such a split of the public keys lends itself to a two-way authentication of both the trusted entity and the users.