In some embodiments, the recovery private key 205 is sent to a recovery escrow service 230 (e.g., by the at least one first computing device 210) and an arbitrary message may be periodically (e.g., monthly) sent to the recovery escrow service 230, with the recovery message signed by the recovery private key 205. For instance, sending a status report or a random text string as the arbitrary message. The signed arbitrary message may be published in a public repository 240 and retrieved by the at least one second computing device 220. Finally, users of the at least one second computing device 220 may verify that the encryption of the signed arbitrary message is compatible with the recovery public key 204 and also verify that the recovery escrow service 230 has the recovery private key 205.