cryptography - 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 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