For example, generation of key pairs with the at least one first computing device 210 may include an elliptic curve key pair x₁,P₁ where P₁=x₁G and the at least one second computing device 220 may include another elliptic curve key pair x₂,P₂ where P₂=x₂G with the full recovery private key being a function of x₁ and x₂. The at least one first computing device 210 may share a ciphertext ‘c’ encrypting x₁ with public key ‘pk_e’ with the recovery escrow service 230 (e.g., the decision on the release of private key ‘k_e’ may be carried out by the trustee 330). Once ‘k_e’ becomes public, each user may be able to locally decrypt ‘x₁’ on the at least one second computing device 220 and compute the corresponding private key k=f(x₁, x₂). In order to verify proper recovery operation, the system requirements may include verification that ‘c’ encrypts ‘x₁’ and that the recovery escrow service 230 be able to prove possession of the private key ‘k_e’. For encryption, the homomorphic ElGamal “in the exponent” protocol may be used, where the at least a portion of the cryptographic key 206 may be divided into ‘m’ segments such that each segment may be encrypted using the recovery public key 204 ‘Q_k’ such that Q_k=k_eG to achieve (D₁,E_i)=([x_i]_iG+r_iQ_k, r_iG). To prove extractability, the at least one first computing device 210 may send proofs as follows: zero knowledge proof that ‘x₁’ segments are small enough to be recovered. For every encrypted segment Zero knowledge proof of knowledge of segment and randomness used in the encryption scheme. Zero knowledge proof that addition of all encrypted segments results in encryption of ‘x₁’. Proof are sent to the at least one second computing device 220, as. Once the recovery private key 205 becomes public (e.g., published by the trustee 330), the at least one second computing device 220 may decrypt segment [x₁]_i, from D_i?k_eE_i for instance using a “dlog extraction” algorithm over a small space of options.