In the paper Zero-Knowledge Proofs of Identity (by Feige, Fiat, and Shamir) a ZK protocol is described that leverages quadratic residues. Section 3 describes an "Efficient Identification Scheme," but (to my understanding) the PK algorithm seems to be broken (in the "does not work" sense, not in terms of "poor security").
The key generation protocol is (steps 1-3 are quoted from the paper, using the same notation as the paper):
Setup: Let $n$ be a Blum integer (the product of two primes, $p$ and $q$, where both $p$ and $q$ are congruent to 3 mod 4). Let $Z_n$ denote the ring of residues under the mod operation.
- Choose $k$ random numbers $S_1, ..., S_k$ in $Z_n$.
- Choose each $I_j$ (randomly and independently) as $\pm 1 / S_j^2$ (mod n).
- Publish $I = I_1, ..., I_k$ and keep $S = S_1, ..., S_k$ secret.
Without the notation, to get the public key we need to compute the square of each secret $S_j$ and then find either the modular inverse of this square, or $(n-1)$ times the this inverse. (I.E. $S_j^2 \cdot I_j = 1 (\text{mod}n)$ or $S_j^2 \cdot I_j = -1 (\text{mod}n)$).
The issue is that in Step 2, $Z_n$ is not a field which means that $I_j$ is not guaranteed to exist. Namely, any $g \in Z_n$ will not have an inverse if either $p | g$ or $q | g$. For a very large $n$ this is unlikely to happen, but it's easy to prove that it always happens.
Proof of existence: without loss of generality, let $p < q$. Then $p^2 \in Z_n$. Because $\text{gcd}(p^2, n) = p > 1$, we see that $p^2$ has no inverse in $Z_n$.
Small example: when $n = 21$, none of the members of this set have an inverse in $Z_n$ $\{0, 3, 6, 7, 9, 12, 14, 15, 18\}$. Some of them are valid candidates to result in an impossible $I_j$ (as above, is $S_j = 3$ then $S^2_j = 9$).
What are you supposed to do if you get one of these "broken" numbers? Draw again? For large $n$ the probability is small (it's easy to compute the number of "broken" numbers in $Z_n$ as $1 + (p-1) + (q-1) = p+q-1$, which vanishes in $pq$ for large $p$ and $q$) but at least in test implementations with small $n$ (like $n = 21$) it breaks any code trying to get that inverse.
