# Randomized public-key encryption as binding commitment / “collision-resistance”?

I am looking to use randomized public-key encryption in a context where it should also serve as a sort of "binding commitment". That is, I want to encrypt a value $x$ with some randomness $rnd$ under a public key $pk$, denoted $enc(x, rnd, pk)$ for short, such that it is infeasible to find a different plaintext $x'$ and randomness $rnd'$ such that $enc(x, rnd, pk) = enc(x', rnd', pk)$ (the ciphertexts are the same).

I want this because a party A should be able to convince a party B that a given ciphertext $c$ is an encryption of a plaintext (known to the parties) $x$. For this, A would send the ciphertext $c$ and the randomness $rnd$ to B, and B would re-compute $enc(x, rnd, pk)$. When this equals $c$, then B should be convinced that $c$ is an encryption of $x$.

Is this a property that randomized public-key encryption schemes usually have, or can be derived from another property?

However, the binding property is not implied by the semantic security of an encryption scheme. In fact, under very strong cryptographic assumptions (the existence of a primitive called indistinguishability obfuscation), there exists public-key encryption schemes which are deniable, in the sense that for any ciphertext $c$ and any plaintext $m$ (possibly different from the one encrypted in $c$), a party can always find a randomness $r$ such that $c = \mathsf{Enc}(m;r)$ (see this paper). Such encryption schemes are interesting objects (intuitively, they would allow to guarantee security even if the government break into your house, point a gun on your head, and asks you to reveal the random coins that you used to encrypt a message - with a deniable encryption scheme, you will always be able to lie and to claim that you encrypted an innocent message). By definition, such encryption scheme are semantically secure but not binding.
• For all standard schemes, you will not even need any mathematical assumption: they are perfectly binding. Take for example ElGamal: given a public key $(g,h)$ and a ciphertext $(c_0,c_1)$, there is a unique pair $(M,r)$ such that $(c_0,c_1) = (g^r, h^rM)$. Therefore, the property that you want is perfectly guaranteed, without any assumption: it is completely impossible to find two different pairs that lead to the same ciphertext. The same is true for RSA, Paillier, etc. And proving this simply amounts to verifying that a ciphertext uniquely defines a pair (message, random coin). – Geoffroy Couteau Apr 11 '18 at 11:45