Changing Public keys

I have seen some discussion of policy on changing public and private keys without being clear what problem was being solved. Ignoring the nature of the problem and merely resolving to change keys periodically can lead to policies that are worse than not chaning keys. I shall start with the problems that I am aware of.

Here are the requirements for “public keys cryptography” to work:

Just the key owner knows the private key of the pair.
Others, who care, must be assurred of having the correct public key.

If that is the correct characterization then it immediately follows that these things that can go wrong are:

What can go wrong Consequences
The owner looses the private key. Inconvenient, A new key required. Public key redistributed without benefit of signature. With foresight a new key along with message ready for distribution, announcing the new public key which is signed by the old key, stored on more stable storage.
Someone else learns the private key. Especially serious because damage beyond inconvenience may occur. Even suspicion of this case requires attention.
Everyone forgets the public key of the pair. Inconvenient; seems unlikely because the public key can usually be stored redundantly, and in all the cases that we consider here. Further public key can be regenerated by owner from the private key.
Some legitimate holder of a public key is misinformed about public key value. Potentially serious. This may indicate fraud.

What can go wrong	Consequences
The owner looses the private key.	Inconvenient, A new key required. Public key redistributed without benefit of signature. With foresight a new key along with message ready for distribution, announcing the new public key which is signed by the old key, stored on more stable storage.
Someone else learns the private key.	Especially serious because damage beyond inconvenience may occur. Even suspicion of this case requires attention.
Everyone forgets the public key of the pair.	Inconvenient; seems unlikely because the public key can usually be stored redundantly, and in all the cases that we consider here. Further public key can be regenerated by owner from the private key.
Some legitimate holder of a public key is misinformed about public key value.	Potentially serious. This may indicate fraud.

I think that a frequently overlooked problem with new keys is establishing that the new key is for the same person that the old key is for. This is merely an obtuse way of saying that flaws in the redistribution of keys may exceed flaws stemming from excessively old keys. If the opponent finds a weakness in key distribution, then he has more opportunities to try.

Credit cards expire in part so as to limit the length of “lost and stolen” card lists. These were once in paper form! Does that reason apply here?

Unlike conventional keys, the obvious brute force attack on a public key may commence upon publishing of the public key, whereas traffic is required for the conventional symmetric key. (Some brute force attacks on conventional keys require very little traffic.) This means that limiting traffic on a public key by frequent key changes is pointless.

On the otherhand: The Number Field Sieve is currently the most efficient factoring algorithm known and it has the property that it never produces an early answer. This is in contrast to brute force on a DES key where the probability of finding the key is nearly as great the first day as the nth day.