How to use a secret to allow the generation of public keys, where the private keys can be calculated later

Alice has a secret S and publishes some public information P, about S which is insufficient to recreate S.

Is there a way that Bob can use P, and an arbitrary integer I to create an (EC?) public key for which Alice can subsequently calculate the private key, given I?

Does this requirement already have a name?

Bob was a bad name. Bob is anyone other than Alice. Alice knows nothing of specific Bobs.

The point of the question is that I want all the Bobs of the world to be able to generate public keys, for which Alice can later calculate the corresponding private key, given the identifying integer I. (Where I could be a random 256bit integer, if it's more secure.)

This is Alice saying to the world: 'Here's some information P, now all of you can make different public keys, for which I can later calculate the private keys, if and when I need to'.

The requirement is to get around the issue that Alice might be offline when a Bob requests a public key from her. I do not what the world to know which public keys are owned by Alice, so she can't just publish 100 public keys for general use.

This problem would be solved if P could be an array of 2^256 public keys (for which she has stored the 2^256 private keys that were used to generate the public keys) but this is not feasible for computational and storage reasons. I'm looking for something possible which will achieve the same ends.

• Yes. $\;$ – user991 Nov 2 '15 at 8:40
• @RickyDemer Could you elaborate in an answer? – Thomas Von Panom Nov 2 '15 at 8:53

To expand on Ricky's comment, assuming Alice and Bob are the only participants, they can use an identity-based encryption scheme where Alice also acts as the trusted third-party ("Private Key Generator" in the Wikipedia article). Namely:

1. Alice puts on her PKG hat, and generates the public parameters of the system and a secret which will be used later.
2. Alice removes her PKG hat, she broadcats the public parameters and says: anybody who wishes to send me messages, just use any string you want as your public key and send it to me along with your ciphertexts.
3. All the Bobs of the world encrypt messages using their chosen public keys and send the ciphertexts and the public keys to Alice.
4. When Alice wants to decrypt a message, she puts on her PKG hat and obtains the private key associated with the public key which was used to encrypt the message.
5. Alice removes her PKG hat and uses the private key to decrypt the message. Optionally, she may store the private key so that she does not have to do step 4 again if she receives another message encrypted with the same public key.

The only requirement is that when Alice wants to decrypt a message, she must know which public key it was encrypted with. There is no requirement on the public keys themselves, including how or by whom they are generated. In any case, Alice is the only one who can decrypt since she is the only one who knows the secret. Matching a specific Bob to a specific public key seems to make it more or less equivalent to a regular cryptosystem.

• The problem with this answer (due to my ill-specified question) is that Alice must be online to interact with Bob. I'm looking for a solution where Alice can be offline. – Thomas Von Panom Nov 2 '15 at 9:13
• @ThomasVonPanom No, Alice does not need to interact with Bob (other than Bob sending her his ciphertext, of course). I have updated the answer for your updated question. – fkraiem Nov 2 '15 at 9:27
• Does this also work where I need the public key for signing, rather than for encrypting? – Thomas Von Panom Nov 2 '15 at 11:01
• Not as far as I know. (Also, public keys are normally used for verifying, not digning.) – fkraiem Nov 2 '15 at 11:02
• Turned my last comment into a question: crypto.stackexchange.com/questions/30248/… – Thomas Von Panom Nov 2 '15 at 11:16