1
$\begingroup$

Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need Alice to be able to check whether $a<b$ holds, like a relaxed version of the Yao's Millionaire Problem, given that one of them knows both values. The challenge is that the comparison result cannot be trusted if done by Bob, as he may be biased.

Therefore, I thought of two approaches for this problem:

  • Check whether Bob was honest in his evaluation of $a<b$, maybe by using ZK-proof; or
  • Somehow enable Alice to do the comparison herself without exposing $b$, so that: $$a < enc_{pk}(b) \iff a<b $$

Which one do you think it would be better to tackle and how?


EDIT: You can assume that both $a$ and $b$ are well defined by a commitment scheme before the evaluation is done.

$\endgroup$
3
  • $\begingroup$ Neither. There is no way to force Bob to actually use the correct value b and not some other value, regardless what kind of protocol you run. Any protocol will give Alice the result Bob wants her to know, there is no difference in Bob just saying 0 or 1. Is there maybe more context for this question? $\endgroup$
    – tylo
    Aug 29 '18 at 3:54
  • $\begingroup$ You're right, there is no way of forcing Bob to produce a honest result, but there should be a way of detecting a dishonest one with some high probability. That's the principle of zk-proofs. $\endgroup$ Aug 29 '18 at 5:13
  • $\begingroup$ "but there should be a way of detecting a dishonest one with some high probability" If Bob can choose $b$ in dependence of $a$ (and indirectly the result of the comparison), then no there is no such way - because there is nothing to define what is actually the correct value of $b$. If there are commitments to both $b$ and $a$ public, then Bob can just run Yao's protocol with himself using the Fiat Shamir heuristic, and afterwards give the transcript to Alice. $\endgroup$
    – tylo
    Aug 29 '18 at 20:45
2
$\begingroup$

This is a common misunderstanding of zero knowledge. In order to prove something in zero knowledge (in fact, in order to prove anything in a way that is non-trivial), there must a well defined statement. See https://crypto.stackexchange.com/a/60633/25354 for an explanation of this.

Note that in your context, it is always true that there exists some $b$ such that $a<b$ (over the integers). Thus, without having some commitment or encryption of $b$ before the proof starts, this is trivially always true.

$\endgroup$
1
  • $\begingroup$ I see your point. In this case both a and b are well defined and previously committed. I'll make sure to add that to the description. $\endgroup$ Aug 29 '18 at 6:07

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.