There are schemes where you don't need key pairs for each user (assuming the government has some way of authenticating users). Private State Tokens use blinded tokens for this.

It doesn't prevent tokens from being stolen or sold, but the token issuer only accepts each token once and can limit the rate that tokens are issued and control how fast they expire, giving decent control over how practical using stolen or sold tokens are.