Standardized digital signature schemes (e.g., Rivest-Shamir-Adleman (RSA), Digital Signature Algorithm (DSA), Elliptical Curve Digital Signature Algorithm (EC-DSA), etc.) may be employed to prove authenticity of a message containing credentials. Proving possession of valid credentials may be performed using a combination of garbled circuits with message authentication codes (MACs) and proof of knowledge protocols (e.g., Sigma protocol, Schnorr protocol, etc.). Such techniques may allow proving entities to prove possession of valid credentials using standardized signature schemes without revealing those credentials directly to a verifying entity.