1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.