# Check if $a<b$ in a trustless scenario

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.

• 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?
– tylo
Aug 29 '18 at 3:54
• 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. Aug 29 '18 at 5:13
• "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.
– tylo
Aug 29 '18 at 20:45

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.