Auto-Recoverable and Auto-certifiable cryptosystems with RSA or factoring based keys

A method and apparatus for a key recovery agent to recover the user's private key, where said public key is based on a composite number, that uses at least one of the certified public key of said user available in the public key directory, information contained in said user's certificate of recoverability retained by certification authority, and public parameters, comprising of the following steps:

• the key recovery agent reading the user's certified public key from the public key directory;
• running an information recovery algorithm based on the following inputs:
• said user's certified public key, the public system parameters, and the private key of said recovery agent;
• running said information recovery algorithm resulting in the secret information of said user.

A method and apparatus for a plurality of key recovery agents to recover the user's private key or information encrypted under said user's corresponding public key, where said public key is a composite, that uses at least one of the certified public key of said user available in the public key directory, information contained in said users certificate of recoverability, and public parameters, comprising of the following steps:

• a subset of said plurality of key recovery agents obtain said user's public key;
• each member of said subset runs a key recovery algorithm based on the following inputs:
• said user's certified public key, the public system parameters, and the private key of said member of said subset;
• running said key recovery algorithm resulting in a partial result of member of said subset;
• all said partial results of said members of said subset are combined using a software algorithm or a tamper-proof hardware implementation of it, to generate said private key of said user or said information encrypted under said user's public key.

An apparatus for generating public keys which can be used in a public key encryption algorithm to encrypt data and a proof that the keys were generated by a specific algorithm comprising one or more of the following steps:

• generating a seed s which is used in conjunction with a hash function F s.t. F(s) contributes to half of the entropy in the generation of n;
• generating a composite n and a public exponent e;
• generating M quadratic residues Q1,Q2, . . . , QM mod n;
• computing two ambivalent roots ri,1 and ri,2 for each quadratic residue Qi;
• committing to each of the 2M roots by preprocessing it and by raising the result to the Eth power mod N;
• generating the challenge bits bi using a hash function H, the Qi and the Ci,j;
• setting Zi to be either ri,1 or ri,2 based on challenge bit bi;
• outputing the Qi, Ci,j, Zi;
• outputing s;
• where the user's public key is n and the user's private key is p, or the inverse of the users public exponent e mod (p−1) (q−1) and where the proof P that the public key n is known and recoverable is the string P=((Q1,C1,1,C1,2), . . . , (QM,CM,1,CM,2),Z1, . . . , ZM) and where the proof P may also include s.

An apparatus for generating public keys which can be used in a public key encryption algorithm to encrypt data and proving that the keys were generated by a specific algorithm comprising of one or more of the following steps performed in an arbitrary order:

• generating a seed s which is used in conjunction with a hash function F s.t. F(s) contributes to half of the entropy in the generation of n;
• generating a composite n and a public exponent e;
• generating M quadratic residues Q1, Q2, . . . , QM mod n;
• computing two ambivalent roots ri,1 and ri,2 for each quadratic residue Qi;
• committing to each of the 2M roots by raising each root after a possible preprocessing to the Eth power mod N;
• sending n and the Qi to the verifier;
• sending s to the verifier;
• the verifier sends the prover M randomly chosen challenge bits bi;
• the prover sends to the verifier the M roots corresponding to the M challenge bits;
• the verifier verifies that s correctly contributes to half of the entropy of n;
• the verifier verifies that the roots are indeed valid roots of the Qi;
• the verifier verifies that the roots are indeed the plaintexts in the M commitments that are opened;
• the verifier verifies that no pair of commitments corresponding to Qi contain two non-ambivalent roots of Qi;
• the verifier verifies other facts about the values, including that the values that the prover sends lie in the correct sets, and that n<N;
• where the user's public key is n and e, and the user's private key is p, or the inverse of the users public exponent e mod (p−1)(q−1).