I'd propose the primary factor is social - when a child is born there is a recorded attestation from the family and care providers about the minting of a new soul. When keys are compromised you similarly seek attestations from your social network (or social worker) that you need to furnish a new key.

The network could be attacked by literal force, blackmail, or deception, but it's very expensive compared the defense (strong legal punishment for attempts to subvert the network)

That last part is why I think the state has to do it, not technologists. There has to be a strong legal and cultural immune system in place to defend the network.