Simple Zero-Knowledge Proof of Knowing $\sqrt{X_1}$ or $\sqrt{X_2}$ mod $N$

Abstract

Tompa and Woll constructed a zero-knowledge proof of knowing a square root of $X$ mod $N$, where $N$ is the product of two large, secret primes. In this paper, we construct a zero-knowledge proof of knowing a square root of $X_1$ or $X_2$ mod $N$. Compared with the existing solution to this problem, ours is significantly simpler.