A message is signed as where the signature depends on and private key Ideally, anyone can check whether is valid signature using a public key, but nobody can sign without knowing Example Elgamal Signature Scheme