A client device that is coupled to a host device sends a parent public key and an associated certificate to the host device. The parent public key, the certificate and a corresponding parent private key are stored in secure persistent storage included in a secure device associated with the client device. The client device receives instructions from the host device for generating a child private and public key pair. In response to receiving the instructions, the client device generates a child private key based on a first random number produced within the secure device, and a child public key associated with the child private key. The client device computes a first signature on the child public key using the parent private key. The client device sends the child public key and the first signature to the host device.