Single-Round Zero-Knowledge Proof for the Square-Root Problem in Cloud Systems

Zero-knowledge proofs (ZKPs) enable a prover to convince a verifier of knowledge of a secret without revealing it. The ZKP for the square-root problem has many applications in network and cloud security, such as user authentication and privacy-preserving cloud storage auditing. Classical protocols for the quadratic residuosity (square-root) relation require multiple iterations to reach negligible soundness error, incurring latency and communication costs that are critical in cloud settings. This paper proposes a new single-round zero-knowledge proof (SR-ZKP) for the square-root problem that achieves the same soundness as iterative schemes by increasing the challenge length. The protocol requires only one execution of a 4-message protocol (request, commit, challenge, response) and can be transformed into a one-message non-interactive ZKP via the Fiat-Shamir heuristic. The completeness, soundness, and zero-knowledge properties of the proposed scheme are formally proven. The results of this study show that the proposed protocol can achieve approximately reduction in communication overhead and latency, when compared to an 80-round iterative ZKPs with RSA modulus n of size 2048 bits. This provides a substantial advantage for cloud applications.