1
$\begingroup$

In the Cocks IBE scheme it is required for the hash function, that the Jacobi symbol of its output and the universally available moduls $n = p*q$ is $+1$, so:

$\Big(\frac{H(ID)}{n}\Big) = \Big(\frac{a}{n}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{a}{q}\Big) = +1$

So, either both Jacobi symbols $\Big(\frac{a}{p}\Big)$ and $\Big(\frac{a}{q}\Big)$ are $+1$ or $-1$. In the frist case, $+a$ is a quadratic residue modulo $n$, because its the product of two numbers that are quadratic residue mod $n$. So far its clear to me. However, in the latter case, why is $-a$ a quadratic residue?

In Cocks paper [1] it says: The latter case arises because by construction $p$ and $q$ are both congruent to 3 mod 4, and so $\Big(\frac{-1}{p}\Big) = \Big(\frac{-1}{q}\Big) = -1$

If I try solve it for the case that $-a$ is a quadratic residue mod $n$, and that both $\Big(\frac{a}{p}\Big) = \Big(\frac{a}{q}\Big) = -1$,

I come to the following result:

$\Big(\frac{-a}{n}\Big) = \Big(\frac{-a}{p}\Big) * \Big(\frac{-a}{q}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{-1}{p}\Big) * \Big(\frac{a}{q}\Big) * \Big(\frac{-1}{q}\Big)$

$ = \Big(\frac{a}{p}\Big) * (-1) * \Big(\frac{a}{q}\Big) * (-1) = \Big(\frac{a}{p}\Big) * \Big(\frac{a}{q}\Big) = (-1) * (-1) = +1$

However, in the last step both Jacobi symbols are $-1$, and thus $-a$ cannot be a quadratic residue mod $n$, because it is the product of two quadratic nonresidues?

I must have made a mistake somewhere, but I don't see it.

[1] Clifford Cocks: An Identity Based Encryption Scheme based on Quadratic Residues, 2001.

$\endgroup$
2
  • $\begingroup$ Quoting Wikipedia: modulus some composite not a prime power, the product of two nonresidues may be either a residue, a nonresidue, or zero $\endgroup$ – fgrieu Dec 9 '14 at 17:39
  • $\begingroup$ If the product can be either a residue, a nonresidue or zero, how can it be ensured that $-a$ is a quadratic residue modulo $n$? It could also be a nonresidue potentially? $\endgroup$ – neuteich Dec 9 '14 at 17:46
1
$\begingroup$

If $a$ is a nonresidue mod $p$, then since $-1$ is also a nonresidue mod $p$ by construction, $-a$ is a residue mod $p$. And likewise mod $q$, so $-a$ is a residue mod $pq$.

$\endgroup$
2
  • $\begingroup$ Just to make it clear for me: by construction it is (for case two): $\Big(\frac{a}{p}\Big) = -1$ and $\Big(\frac{-1}{p}\Big) = -1$. So it holds that: $\Big(\frac{-a}{p}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{-1}{p}\Big) = (-1) * (-1) = +1$. But, as fgrieu said, the product of two nonresidues can also be a nonresidue again. Why must $-a$ be a residue mod $p$? $\endgroup$ – neuteich Dec 9 '14 at 18:05
  • $\begingroup$ The product of two nonresidues can be a nonresidue when working modulo a composite. Here, you are modulo a prime. $\endgroup$ – fkraiem Dec 9 '14 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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