Given two commitments on different values, Can a third party compare those two commitments to know which one is the higher value?

  • 2
    $\begingroup$ Are you asking a) if commitments can be compared for any commitment scheme, b) if someone can devise an interactive proof with the committer to prove the relative ordering, or c) if there exists a commitment scheme where a third party can do the comparison without any interaction with the committer? $\endgroup$ – poncho Mar 24 '17 at 20:29
  • $\begingroup$ Is there any commitment scheme where if two commitments were given by two different people to a third party can compare them to decide which one has the higher value? If so, can that third party prove It? (What may be the possible cases? like a semi-trusted third party) $\endgroup$ – surya Mar 24 '17 at 22:57
  • 3
    $\begingroup$ If commitments by different people can be compared non-interactively, then an attacker can learn the value inside any commitment by performing a binary search based on generating their own commitments and comparing them to the target commitment. $\endgroup$ – Mikero Mar 25 '17 at 2:57
  • $\begingroup$ Yeah. That's correct. $\endgroup$ – surya Mar 25 '17 at 15:37
  • $\begingroup$ So we can't compare any two secret values given to a third party non-interactively. My problem is - given two requests to a third party, it should be convinced by the requesters that those requests are formed correctly and are approved by some trusted party and the third party should be able to compare them to give priority to the higher one. @Mikero $\endgroup$ – surya Mar 25 '17 at 15:55

If there's a trusted third party who needs to do the comparison (and you don't care if the trusted third party knows the committed values), then it's actually quite simple.

Take your favorite public key encryption algorithm; remember that a public key encryption algorithm can be represented by $E_{pub}(x, r)$, where $pub$ is the public key, $x$ is the value being encrypted and $r$ is a random value; this random value makes the encryption nondetermanistic.

Now, have the trusted party generate a public/private key pair, and have him publish the public key.

To commit a value $x$, Alice would select a random value $r$, and publish the value $E_{pub}(x, r)$. Assuming that $E$ is a secure public key encryption system, no one can recover $x$ without the private key (and we assume that only the trusted third party knows that private key).

The open the commitment $E_{pk}(x, r)$, Alice would reveal the values $x$ and $r$; anyone can verify that those values (along with the global public key) generate the commitment.

And, because the trusted third party has the private key, he can examine $E_{pk}(x, r)$, recover $x$, and check if it is a sane value, and check how it compares to another commitment.

| improve this answer | |

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.