After reading through Lindell's excellent tutorial (https://eprint.iacr.org/2016/046.pdf), I wonder about the following.

To make a protocol secure against fully-malicious security, it seems that forcing parties to commit to their input and then prove knowledge of that input (using a zero-knowledge proof of knowledge) is a useful tool. Basically, the zero-knowledge proof of knowledge allows the simulator to extract the adversary's input and fabricate data as required.

My question is about the usefulness of the zero-knowledge proof in reality. Is the ZK proof only required to make a proof of security go through?

On Page 43, Lindell states that decommitting is essentially the same as that ZK proof. So for a new protocol, is it sufficient to decommit a commitment at some point in the protocol's real-world implementation, but replace the decommitment by a ZK proof in my protocol's security proof?


1 Answer 1


No, zero-knowledge proofs are not only a trick to prove security: essentially all protocols where zero-knowledge proofs are used would be insecure against malicious adversaries if zero-knowledge proofs are removed, or replaced by "decommitments" as you suggest.

Let me illustrate this on a simple example. Suppose that Alice and Bob have respective inputs $x$ and $y$, which are $n$-bit string. Suppose also that Bob wants to obtain the Hamming distance between $x$ and $y$. For example, Bob could be a server which stores a fingerprint, and it should grant some access rights only to the user which has this fingerprint; hence, the goal of the protocol is to check that Alice's fingerprint is correct (in which case it will be close to $y$ - not necessarily equal due to imperfect measures), but without leaking $x$ or $y$.

A simple solution to the above is as follow: Bob encrypts each bit $y_1, \cdots, y_n$ using, say, the ElGamal encryption scheme "in the exponent" (i.e., an encryption of $y_i$ is of the form $(g^{r}, h^rg^{y_i})$), and sends these $n$ ciphertext to Alice. Now, Alice can homomorphically compute an encryption of the Hamming distance between $x$ and $y$, using the fact that $\mathsf{HD}(x,y) = \sum_{i=1}^n x_i + y_i - 2x_iy_i$, and send back this ciphertext to Bob, who decrypts it and gets $\mathsf{HD}(x,y)$.

Suppose now that Bob is malicious. In this case, he could for example cheat as follow: instead of encrypting $(y_1, \cdots, y_n)$, he encrypts $2, 4, \cdots, 2^n$. It is easy to see that doing so allow him to recover the entire $x$ when decrypting the final ciphertext. To prevent this attack, the natural solution is to use a zero-knowledge proof. With the general commit-and-prove strategy, it would look as follow: Bob commits to $y_1, \cdots, y_n$, proves in zero-knowledge that each commitment commit to the same value that the one encrypted in the corresponding ElGamal ciphertext, and proves in zero-knowledge that each committed value is a bit (i.e., that each $y_i$ satisfies $y_i(1-y_i) = 0$). This guarantees that Bob cannot perform the attack I mentioned. In the proof, this will allow the simulator to indeed extract the $y_i$, but also guarantees that they are bits, and are the value encrypted in the ciphertexts.

Now, if we were simply opening the commitments, all security would break down. Specifically, either Bob commits to the correct $y_i$; but then, when decommitting, he reveals all his private input $y$ to Alice. Or Bob commits incorrect values; but then, Alice has no way to check anything about the encrypted value simply from seeing opening to these incorrect values.

  • $\begingroup$ That's a great explanation, thanks! I think I was limiting myself to the example of coin tossing... Note that there is a small typo in your computation of Hamming distance. I guess it should be $\sum x_i + y_i - x_i\cdot{}y_i$... $\endgroup$ Commented Mar 22, 2018 at 17:24
  • $\begingroup$ I just checked, I think that my formula is correct, it corresponds to $\sum_i x_i \mathsf{xor} y_i$ $\endgroup$ Commented Mar 22, 2018 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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