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. Zbl 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. Zbl 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. Zbl 0799.68101

11more comments