Signature

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