_Posted on September 02, 2024_ _Extended and renamed on September 03, 2024_ ##### Introduction In _The Knowledge Complexity of Interactive Proof Systems_ by Goldwasser, Micali, and Rackoff, which was written in 1985, an [[Interactive Proof Systems|interactive proof system]] was established for the set $QNR = \{(x,y) \mid y \text{ is a quadratic nonresidue mod } x\}.$ > [!definition] > Given integers $x$ and $y$, $y$ is a quadratic residue mod $x$ if $y \equiv z^2 \mod{x}$ for some $z$. Otherwise, $y$ is a quadratic nonresidue mod $x$. This interactive proof system is given in detail as example 1 in the referenced paper, and relies implicitly on the following theorem: > [!theorem] Theorem: If $x$ is a quadratic residue mod $n$ such that $\text{GCD}(x,n)=1$, and $y$ is a non-quadratic residue mod $n$, then $xy$ is a non-quadratic residue mod $n$. #TODO I think it is the case that _all_ quadratic residues mod $n$ are coprime to $n$, for all $n$. Also, there is an additional theorem from PDP at untrusted stores: For p = 2p' + 1 and q = 2q' + 1, N = pq, QR_N is the unique cyclic subgroup of Z_N^* of order p'q'. To express this and related theorems more succinctly, the following notation is introduced: $\mathbb{Z}_x^* = \{n \in \mathbb{Z}_x \mid \text{GCD}(x,n) = 1\}$ The quadratic residuosity predicate is then defined as: $ Q_x(y) = \begin{cases} 0 \text{ if $y$ is a quadratic residue mod $x$} \\ 1 \text{ otherwise} \end{cases}$ We now restate and generalize the above theorem: > [!theorem] Theorem: Let $x \in \mathbb{N}$, $y,z \in \mathbb{Z}_x^*$. Then we have the following: > (a) If $Q_x(y) = Q_x(z) = 0$, then $Q_x(yz)=0$ > (b) If $Q_x(y) \neq Q_x(z)$, then $Q_x(yz) = 1$ In $\S5$ of _The Knowledge Complexity of Interactive Proof Systems_, a [[Zero-Knowledge Interacive Proof Systems|zero-knowledge interactive proof (ZKIP) system]] is constructed for the set $QR = \{(x,y)\mid x \in \mathbb{N}, y\in \mathbb{Z}_x^*, \text{ and } Q_x(y)=0\}$ which relies on the given generalization. ##### Proof Proof: (a) First, lets suppose that $Q_x(y) = Q_x(z) = 0$ so that, by the definition of quadratic residuosity, there exist integers $a$ and $b$ such that $a^2 \equiv y \mod{x}$, and $b^2 \equiv z \mod{x}$. This implies that $yz \equiv a^2b^2 \mod{x}$, and so $yz \equiv (ab)^2 \mod{x}$. By the definition of quadratic residuosity, $Q_x(yz)=0$. (b) Suppose, without loss of generality, that $Q_x(y) = 0$ and $Q_x(z) = 1$. By the definition of quadratic residuosity, there exists an integer $a$ such that $a^2 \equiv y \mod x$, and there exists no integer $b$ such that $b^2 \equiv z \mod x$. Suppose, for the sake of contradiction, that $Q_x(yz) = 0$. This implies that there is some integer $c$ such that $c^2 \equiv yz \mod x$. Thus, $c^2 \equiv a^2z \mod x$, which implies that $(ca^{-1})^2 \equiv z \mod x$. Since $y\in \mathbb{Z}_x^*$, $y$ is coprime to $x$, $a^2$ is coprime to $x$, and $a$ is coprime to $x$. Therefore, $a$ has an integral multiplicative inverse and so $ca^{-1}$ is an integer. If we let $b = ca^{-1}$ then we see that our assumption $Q_x(z)=1$ is a non-quadratic residue is contradicted. $\blacksquare$ It is also the case that if $Q_x(y) = Q_x(z)=1$, then $Q_x(yz) = 0$. A few proofs of this statement can be given, which are more involved than for the theorem under current consideration. Consequently, I have elected to not yet include it in this post.