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?



Zero-knowledge proof of positivity
This answer combines my three comments to the question and expands them a little.


Following [BM84], let’s call the integers $g^x \bmod p$ for $0 < (x \bmod (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 \bmod (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. [DOI 10.1137/0213053](https://doi.org/10.1137/0213053). [Zbl 0547.68046](https://zbmath.org/?q=an:0547.68046)


[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. [DOI 10.1007/BF02620137](https://doi.org/10.1007/BF02620137). [Zbl 0783.68039](https://zbmath.org/?q=an:0783.68039)


[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. [DOI 10.1145/116825.116852](https://doi.org/10.1145/116825.116852). [Zbl 0799.68101](https://zbmath.org/?q=an:0799.68101)


