Is it possible to construct a zero knowledge proof that one encrypted number is larger (or not) than another encrypted number without releasing the values of either numbers?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Yes, it is possible. Actually, any statement in NP can be proven in zero knowledge. This means that if something can be proven by releasing some information, it is possible to prove the same without releasing any information, i.e. in zero knowledge.
An efficient proof of "more or equal" statement about integers committed is possible starting from Lagrange 4-squares theorem as follows:
Low probability (like inverse challenge space) of protocol soundness error in a single run is the major difference from general proof for any NP statement.
"Proving knowledge" above holds for a protocol of argument type, on condition that proving party cant find logarithm and cant find order of the group used.
Protocol above is a generalization into proving polynomial identities of degree larger that linear in challenge, doable with Schwartz-Zippel lemma.