How does challenge-response with asymmetric cryptography (signature variant) work — and how is it different from the symmetric version?

Alice signs the challenge with her private key; Bob verifies with her public key. Bob never holds anything that lets him impersonate Alice.

The protocol:

1. Setup: Alice has a key pair (sk, pk). Bob gets a copy of her public key pk (only).
2. Login:
   • Alice → Bob: "I'm Alice"
   • Bob → Alice: challenge
   • Alice → Bob: response = SIGN(sk, challenge)
   • Bob: VERIFY(pk, challenge, response) → ok / not ok.

Why it's a strict upgrade on the symmetric version:

• Bob can't impersonate Alice. He only has Alice's public key — useless for signing.
• A server compromise leaks public keys, which are public anyway. The attacker learns nothing useful.
• This solves a deep trust problem with symmetric crypto in big systems: with n users, the bank doesn't need n impersonation-capable secrets sitting in one database.

The certificate variant adds: Alice sends her certificate (a signed binding of her name + public key by a trusted CA) along with the response. Bob then doesn't need to pre-know Alice — he trusts the CA's signature on the certificate.

Tip: This is the same idea underneath TLS client certificates, SSH keys, FIDO2 / passkeys, and PIV/CAC smart cards.