A pool of public keys, having a pool size, is received from a first device. The pool size reflects a target number of keys to be included in the pool. One of the received public keys included in the pool of keys is designated as a reserve key. A public key is selected from the pool of received public keys for use in conjunction with encrypting a communication to the first device. The selecting includes preferentially selecting a public key that is not designated as a reserve key, if at least one such key is present in the pool in addition to the reserve key. The size of the pool can be dynamically adjusted.