2
$\begingroup$

The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an interactive proof system.

Example 1: Let $Z_m^*$ denote the set of integers between $1$ and $m$ that are relatively prime with $m$. An element $a \in Z_m^*$ is a quadratic residue mod $n$ [sic] if $ a = x^2 \mod{m}$ for some $x \in Z_m^*$, else it is a quadratic nonresidue. Now let $L = \{(m, x) | x \in \mathbb{Z}_m^* \text{is a quadratic nonresidue\}}$. Notice that $L \in \textbf{NP}$: a prover needs only to compute the factorization of $m$ and send it to the verifier without any further interaction.

Given that $n$ is not defined in the context of the example, I assume this to be a typo and that the authors meant $m$. My question is about the last sentence. The authors provide no further detail afterwards about what the verifier would do with this factorization to verify quadratic nonresiduosity. In pursuit of more details, I cracked open Arora-Barak where the following treatment of the above is given in section 8.1 example 8.9.

Here is another example for an interactive proof for a language not known to be in $\textbf{NP}$. We say that a number $a$ is a quadratic residue mod $p$ if there is another number $b$ such that $a \cong b^2 \mod{p}$. Such a $b$ is called the square root of $a \mod{p}$. ... the language QNR of pairs $(a, p)$ such that $p$ is a prime and $a$ is not a quadratic residue modulo $p$ has no natural short membership proof and is not known to be in $\textbf{NP}$. But it does have a simple interactive proof if the verifier is probabilistic.

Now if the language QNR described in Arora-Barak is not in $\textbf{NP}$, how could its "superset" the language $L$ described in the paper be in $\textbf{NP}$? If the paper is correct then we could easily construct a verifier which would prove that QNR is in $\textbf{NP}$: for any $(a, p)$ the certificate would consist of the certificate of the membership of $(p, a)$ in $L$ in addition to a certificate for the primality of $p$.

$\endgroup$
2
  • $\begingroup$ I am currently reading Goldwasser's paper on Zero Knowledge proofs (GMR85) & there it's clearly said that both QR & QNR are in NP & I can't find where exactly Borak-Arora says it's not in NP - can you tell me the page/chapter number? $\endgroup$
    – user93353
    Mar 6, 2023 at 11:15
  • $\begingroup$ @user93353. That is a mistake in the Barak-Arora book. See my comment to the reply below for a link to an article with a proof of containment in NP. $\endgroup$
    – EGME
    Jul 29, 2023 at 8:58

1 Answer 1

4
$\begingroup$

When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$.

When the modulus is a prime power $p^\alpha$, then you can do the same: I believe $x$ is a quadratic residue mod $p^\alpha$ iff $(x|p)=1$ or $0$. I believe this can be proven using Hensel lifting.

When the modulus is a number $n$ with known prime factorization $n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, you can use the Chinese remainder theorem: $x$ is a quadratic residue mod $n$ iff it is a quadratic residue mod $p_i$ for all prime factors $p_i$ of $n$.

This means that quadratic nonresiduosity mod $n$ can be computed in polynomial time when the factorization of $n$ is known or given. This also means that, as far as I can see, the language QNR should be in NP: a natural certificate is a prime $p$ that divides $n$, and such that $(a|p)=-1$. The verifier can verify that $p$ is prime in polynomial time and compute the Legendre symbol $(a|p)$ in polynomial time. At least, that's how it seems to me.

I don't know why Arora-Barak say that QNR is not known to be NP. This makes me suspect that I may have misunderstood something, as they know way more about computational complexity than I do.

$\endgroup$
7
  • $\begingroup$ So Arora-Barak is wrong? $\endgroup$
    – Johnny
    May 25, 2021 at 22:49
  • 2
    $\begingroup$ @kotu, I don't know. Arora and Barak know way more than me, so if my impression is contrary to them, I'm inclined to think it's more likely that I've misunderstood something than that they got something wrong. Depending on how old your copy of the book is, perhaps it was written before the proof that PRIMES is in P, in which case everything they write makes sense; my answer basically argues that the problem is in NP, and relies upon the fact that PRIMES is in P: the witness is a prime $p$ that divides $n$, and the verifier must verify that $p$ is a prime. $\endgroup$
    – D.W.
    May 25, 2021 at 23:03
  • 1
    $\begingroup$ @kotu, got it, thank you. I'm confused, too. I hope someone here who knows more computational complexity than I will be able to help us clear this up. $\endgroup$
    – D.W.
    May 26, 2021 at 0:10
  • 1
    $\begingroup$ I just sent an email to an account that the authors maintain for improvements to the book. I'll provide an update here if they ever respond. $\endgroup$
    – Johnny
    May 26, 2021 at 1:04
  • 2
    $\begingroup$ In communication with B. Barak, he points out that this is a mistake in their book (example 8.9). Both QR and QNR are in NP. A nice proof of this appears in Cai and Threlfall’s paper (you can google it to find the non-paywall version): sciencedirect.com/science/article/pii/S0020019004001991 $\endgroup$
    – EGME
    Jul 29, 2023 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.