Exam F17 A question 2 a

Exam F17 A question 2 a

Amit (guest) 01 Feb 2020 12:47

It sounds from the solution that if G created the same public key for 2 randomnesses then it must create the same public key.

Is it correct? I could not convince myself that it is, but the solution is dependent on it if I understood correctly.

Hope the question is clear, will write it more formally:
if G generates secret and public keys for a public key encryption, and for randomness r_g it created (sk,pk), and for randomness r_g_2 it created (sk^', pk), does it mean that sk^' == sk?

Otherwise I think there is a counter example for the solution described.

Re: Exam F17 A question 2 a

nbitansky 01 Feb 2020 14:24

They don't have to be equal as strings, and the proof in the solution doesn't assume they are, it just invokes the perfect correctness guarantee. In particular, there exist public-key encryption schemes where a single public key may have many corresponding secret keys. As an uninteresting example you can always pad the key with bits that are ignored (there are also interesting examples…).

Amit (guest) 01 Feb 2020 21:51

But doesn't it mean that a cipher text that was encrypted with the same public key can be decrypted to 2 different messages, based on the corresponding secret key?
If so, then the commitment does not have to be binding, the fact that the public key is the same and the cipher text is the same does not mean that the message is the same ( I will be able to open the commitment to 2 different messages).

What do I miss here?

nbitansky 02 Feb 2020 06:47

No, it doesn't. By the correctness of the scheme it must be decrypted under both keys to whichever message was encrypted.

Amit (guest) 02 Feb 2020 07:15

Thanks!
So if I generated a pair of (sk_1,pk) and you generated the pair (sk_2,pk), I will be able to decrypt messages that are sent to you with my secret key?

nbitansky 02 Feb 2020 07:35

Yes. Note that given a public key $pk$ sampling a matching secret key is at least as hard as breaking the encryption.

Last edited on 02 Feb 2020 07:36 by nbitansky Show more