Techniques are disclosed relating to authentication using public key encryption. In one embodiment, a computing device includes a secure circuit, a processor, and memory. The secure circuit is configured to generate a public key pair usable to authenticate a user of the computing device. The memory has program instructions stored therein that are executable by the processor to cause the computing device to perform operations including authenticating the user with a server system by sending authentication information supplied by the user. The operations further include, in response to the server system verifying the authentication information, receiving a first token usable to register the public key pair with the server system and sending, to the server system, a request to register the public key pair for authenticating the user. In such an embodiment, the request includes the first token and identifies a public key of the public key pair.