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

Question

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?

Answer 1

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).