# Zero-knowledge proof of positivity

If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?

My bounty is ending in 4 days and I am unsatisfied with the current answers so I would like to provide more context and also expand the question for the limited time remaining. Consider the following situation:

Paul and Quentin are wealthy and competitive with each other and they frequently settle their account with great variance: one week Paul is ahead by a million dollars, the next week Quentin is ahead by a billion, the next week Paul is ahead by only a thousand. Paul and Quentin have a wealthy rival Raul, whom they shun, but all 3 persons patronize the same accountant Verne. Verne is honest and discreet and frugal and he will never make a payment to a client on credit, but he will pay an owed amount to a client on demand. Raul can profit from information about Paul's account, indirectly costing Paul, and everyone knows this. How can Verne manage his accounts without having to buy insurance against Paul's legal accusation of a conflict of interest?

-
I don't understand why a positive x implies 0 < x mod (p-1) < (p-1)/2. Doesn't (for example) x = p-2 violate this property without necessarily being negative? –  Alexandre Passos Aug 14 '10 at 11:37
If one-way functions exist, every problem in NP has a computational zero-knowledge interactive proof system (Goldreich, Micali and Wigderson, JACM 1991). Therefore, the answer is yes assuming one-way functions. Are you looking for an unconditional result? –  Tsuyoshi Ito Aug 14 '10 at 12:06
Tsuyoshi Ito, thank you for the reference, if you write this as an answer I may accept it. However it seems like to use this fact directly I would first have to transform the discrete-log-based decision problem into Graph 3-Colorability and I'm not sure exactly how to do this nor how practical it would be (e.g. would such a transformation multiply the problem size by a large constant?) I would prefer an answer that describes a simple protocol. –  Dan Brumleve Aug 14 '10 at 23:35
@jdb19937: That sounds like a much more interesting question, but I do not know the answer. (But I am no expert in cryptography, so I may be missing something that is simple to those who work on cryptography.) A straightforward way to reduce your problem to 3-colorability is to compose several reductions including Cook’s reduction, and the reduction constructed this way incurs a polynomial blowup (instead of linear) in the instance size. –  Tsuyoshi Ito Aug 15 '10 at 11:31
This does not seem to answer your question completely, but I found an interesting paper: Oded Goldreich and Eyal Kushilevitz: A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Journal of Cryptology, 6(2):97–116, June 1993 (springerlink.com/content/u567k88h3g5rw31r). In this paper, the authors construct a perfect zero-knowledge interactive proof system for a problem of deciding whether x mod (p−1) is less than (p−1)/2 under the promise that x mod (p−1)/2 is not too close to (p−1)/2. Their result is unconditional. –  Tsuyoshi Ito Aug 22 '10 at 22:38

This answer combines my three comments to the question and expands them a little.

Following [BM84], let’s call the integers gx mod p for 0 < (x mod (p−1)) < (p−1)/2 principal square roots. We call the problem of deciding, given p, g and y, whether an integer y is a principal square root or not the principal square root problem.

For the original question, the answer is positive assuming one-way functions. This is because if one-way functions exist, every problem in NP has a computational zero-knowledge interactive proof system [GMW91]. Note that the principal square root problem is clearly in NP.

As the questioner pointed out, this construction has a drawback that it requires a reduction from the principal square root problem to the 3-colorability problem, which involves Cook’s reduction and blows up the instance size (polynomially). In addition, this construction requires the assumption that one-way functions exist.

I do not know a direct way to construct a zero-knowledge interative proof system for the principal square root problem. However, [GK93] shows an interesting result related to the question: the principal square root problem under a promise that (x mod (p−1)/2) is not too close to (p−1)/2 has a perfect zero-knowledge interactive proof system. The construction is direct and does not use any cryptographic assumptions.

References

[BM84] Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13(4):850–864, Nov. 1984. http://dx.doi.org/10.1137/0213053

[GK93] Oded Goldreich and Eyal Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology, 6(2):97–116, June 1993. http://springerlink.com/content/u567k88h3g5rw31r

[GMW91] Oded Goldreich, Silvio Micali and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):690–728, July 1991. http://doi.acm.org/10.1145/116825.116852

-

It seems the answer to the question is "no", since the positivity of $x$ is a hard predicate for the exponentiation function (on a primitive element) modulo a prime $p$. In other word, being able to compute this positivity is as hard as computing $x$. This is proven by Blum and Micali in "How to generate cryptographically strong sequences of pseudo-random bits", SIAM Journal on Computing, Volume 13 , Issue 4 (November 1984). See also Fact 3.84 in the Handbook of Applied Cryptography: http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf

-
Something can be hard to compute and still have a short witness. The question is whether Dan, who knows what $x$ is, can convince me that $x$ is positive without revealing it; not whether I can determine whether $x$ is positive without computing it. –  David Speyer Aug 19 '10 at 16:44
I think the same is true for any other bit of x as long as p and g are chosen carefully. The lowest bit (parity) has a short witness (g^(x/2)), is the same true for the highest bit (sign)? –  Dan Brumleve Aug 19 '10 at 21:37
Actually I am wrong about that, according to Gerard's reference QR is efficiently solvable for any prime modulus. However, Fact 3.84 confirms that finding the sign of x is just as hard as finding the entirety of x. I was already assuming this so it doesn't really answer the question. –  Dan Brumleve Aug 20 '10 at 7:29

If I understand your expanded question correctly, it is now about Verne the accountant committing to the participants' account balances by publishing them in encrypted form. So Verne can encode all positive balances n as the even number 2n, and all negative balances -n as the odd number 2n+1. And you already know how to commit to a proof that a number is even. Does this fit the bill?

-
Sorry, that is not the interpretation I had in mind. Verne wants to be able to do his job without even knowing Paul's account balance, only that it is positive. Even though Verne is honest and Paul trusts him, there will never arise any situation where Paul accuses Verne of giving information to Raul. [continued] –  Dan Brumleve Aug 22 '10 at 22:59
The idea is that Verne knows g^x_p, g^x_q, and g^x_r and is convinced at all times that they all have positive logarithms. If Paul asks Verne to make a payment y to Quentin, Verne only needs to know g^y, with which he can compute g^(x_p-y) g^(x_q+y). But Verne won't do this unless Paul can prove that g^(x_p-y) has a positive logarithm, because Paul is the only one who knows x_p or y. –  Dan Brumleve Aug 22 '10 at 23:01
... Quentin presumably also knows y in this case, but not x_p. –  Dan Brumleve Aug 22 '10 at 23:02
So P, Q, and R use the same g? That looks wrong. –  TonyK Aug 22 '10 at 23:24
Yes, everybody knows the same g and p. –  Dan Brumleve Aug 22 '10 at 23:28