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?


Yes, this is a property that most randomized public-key encryption schemes have. In fact, every standard public-key encryption scheme you could think of satisfies this property (e.g. RSA-OAEP, ElGamal, Goldwasser-Micali, Paillier...).

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.

| improve this answer | |
  • $\begingroup$ Thank you for your answer! While this answers my question, I do have a small follow-up: I have trouble finding formal proofs for statements such as the first one you made (that these public-key encryption schemes have this property). Since I am interested in using it in a protocol for which I would like formal proofs, and this property is needed for the security of my protocol, I was wondering if I could find something of the sort for a concrete scheme (given some mathematical hardness assumptions). $\endgroup$ – Sven Hammann Apr 11 '18 at 8:36
  • 1
    $\begingroup$ 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). $\endgroup$ – Geoffroy Couteau Apr 11 '18 at 11:45

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.