[lagolinguini]

Everybody gets a public key certificate, possibly since birth. There needs to be some way of establishing that which keys belong to which person, perhaps via some government registry, and a way to invalidate old/compromised keys. Overkill?

[Aerroon]

Kind of like ID cards in Estonia? You have a chip on the card that holds your private key and the government has a list of people and their public keys. Services and other people can check that. You can even sign and encrypt documents with it.

[netsharc]

China's ID cards also have chips, and they have to scan them to enter train stations or airports (or the center of the old town in Tibet)...