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?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ Is the encryption public-key? If yes, does the prover know the private key or the randomness used for encryption? $\endgroup$– user991Sep 23, 2014 at 0:25
-
$\begingroup$ use orderpreserving encryption ? $\endgroup$– sashankSep 23, 2014 at 0:42
-
$\begingroup$ I don't care what encryption is used, as long as the values aren't knowable by any but the holder of the value. $\endgroup$– B TSep 23, 2014 at 1:06
-
$\begingroup$ @BT : $\:$ In that case, you need a statistically binding commitment to the key. $\;\;\;\;$ $\endgroup$– user991Sep 23, 2014 at 1:20
-
$\begingroup$ Do you need to compare each number in a pair only once, or multiple times? $\endgroup$– Henrick HellströmSep 23, 2014 at 2:03
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
3
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.
answered Sep 23, 2014 at 3:46
-
$\begingroup$ Very interesting. The article you link to looks like its for-pay only. What is an NP language? Is there somewhere I can read about them that is more understandable than the wikipedia page? $\endgroup$– B TSep 23, 2014 at 4:30
-
$\begingroup$ @BT I replaced the link with a free one. I think the wikipedia article on NP is sufficiently understandable. $\endgroup$ Sep 23, 2014 at 4:39
-
$\begingroup$ Thanks for the answer, if you know, I'd be very curious to see an explanation of how this could be done specifically $\endgroup$– B TSep 23, 2014 at 22:28
$\begingroup$
$\endgroup$
An efficient proof of "more or equal" statement about integers committed is possible starting from Lagrange 4-squares theorem as follows:
- use a group of a hidden order (that is, unknown to proving party), like RSA;
- find four integers such that sum of their squares is the difference of original numbers committed;
- commit that four numbers and send all commitments to verifying party;
- prove knowledge of two original numbers and 4 "witness" numbers with a Schnorr-like protocol.
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.
answered Nov 17, 2014 at 13:13