# How can a public-key encryption scheme be used to construct a commitment scheme in the CRS model?

For a PKE scheme $$(Gen, Enc, Dec)$$, the most 'obvious' idea is to commit to an encryption of a bit and in the reveal phase maybe send $$r_g$$, $$r_e$$ where $$r_g$$ is the randomness of $$Gen$$ and $$r_e$$ is the randomness of $$Enc$$.

However, if the encryption scheme is not perfectly correct, then maybe there is some $$sk, sk'$$ such that $$Dec(sk, c) = 0$$ and $$Dec(sk', c) = 1$$, so binding fails, because we can fiddle with $$r_1$$.

A solution is to only reveal $$r_2$$, and then in revealing one only needs to check that $$Enc(pk, b, r_2) = c$$. Particularly, if the probability over $$Gen$$ that there exists some $$r_2, r_2'$$ with $$Enc(pk, b, r_2) = Enc(pk, 1-b, r_2')$$ is negligible, then this almost works. However since the sender doesn't have to prove what $$sk$$ they used, we can still break binding.

How can we get around this issue in the CRS model?

• Put the public key in the CRS? Apr 23 at 8:54

Particularly, if the probability over $$Gen$$ that there exists some $$r_2, r_2'$$ with $$Enc(pk, b, r_2) = Enc(pk, 1-b, r_2')$$ is negligible, then this almost works.
Actually, if the public key $$pk$$ is a valid public key (that is, corresponds to an actual secret key), the probability is 0.
Here's why: we have $$Dec(sk, Enc(pk, x, r)) = x$$ for all $$x, r$$. Hence, $$Dec(sk, Enc(pk, b, r_2)) = b \ne Dec(sk, Enc(pk, 1-b, r_2')) = 1-b$$, and so $$Enc(pk, b, r_2) \ne Enc(pk, 1-b, r_2')$$
On the other hand, this still leaves open the question of "what if the committer were to pick an invalid public key (which does allow collisions)", for example, RSA with $$e$$ not being relatively prime to $$(p-1)(q-1)$$.
Hence, if we were to use this commitment scheme, we would reveal $$r_g$$ as well; this allows the verifier to construct the public key for himself (and verify that the $$pk$$ in the commitment was done honestly).
• I don’t think this argument is valid when the encryption scheme is not perfectly correct, which is what the OP was concerned about. Just because $pk$ has an $sk$ does not mean that decrypting an encryption of $x$ always yields $x$. There could be some encryption randomness that induces an incorrect decryption. Aug 27 '20 at 12:20