A first device with a changing identity establishes a secure connection with a second device in a network by acting as its own certificate authority. The first device issues itself a self-signed root certificate that binds an identity of the first device to a long-term public key of the first device. The root certificate is digitally signed using a long-term private key, where the long-term public key and the long-term private key form a public/private key pair. The first device provides its root certificate to the second device in any trusted manner. The first device can then create a certificate for one or more short-term identities acquired by the first device and sign the newly-created certificate using the long-term private key. The first device can authenticate itself to the second device by sending the newly-created certificate to the second device.