I think you are correct.
First of all, the prover can provide the prime factorization of $n$, so without loss of generality assume $n = p^k$ for some $k$. We have thus reduced the problem to the prime powers.
I am taking the following sets of rules for determining if a number is a quadratic residue or not modulo $p^k$ from this wikipedia page. Be careful in reading the wikipedia page since it uses a different notation than in the question.
If the modulus is $p^k$, then $p^x A$
- is a residue modulo $p^k$ if $x \geq k$
- is a nonresidue modulo $p^k$ if $x < k$ is odd
- is a residue modulo $p^k$ if $x < k$ is even and $A$ is a residue modulo $p$
- is a nonresidue modulo $p^k$ if $x < k$ is even and $A$ is a nonresidue modulo $p$.
And for $p=2$:
All odd squares are $\equiv 1 \pmod 8$ and a fortiori $\equiv 1 \pmod 4$. If $a$ is an odd number and $m = 8, 16$, or some higher power of $2$, then $a$ is a residue modulo $m$ if and only if $a \equiv 1 \pmod 8$.
So a nonzero number is a residue modulo $8, 16$, etc., if and only if it is of the form $4^x(8y + 1)$.
So we are finally reduced to the case of checking whether a given number is a quadratic residue or nonresidue modulo a prime $p$. But as the OP notes, that can be easily done in deterministic polynomial time using Euler's criterion.