Example embodiments relate to updating key pairs based on digital signature states. In example embodiments, first credentials that are generated using a first private key may be sent to a user computing device, where the first private key is associated with a first public key. At some stage, second credentials that are generated using the first private key and a second private key are sent to the user computing device, where the second credentials specify that the first private key is deprecated, and where the user computing device authenticates the second credentials using the first public key. In response to receiving confirmation that a firmware upgrade is installed a number of user computing devices such that an upgrade threshold is satisfied, the first private key may be deactivated. The firmware upgrade may be provided in response to receiving a firmware upgrade request from the user computing device.