# Finding generators for commutative encryption

The paper Information Sharing Across Private Databases presents a protocol for finding an intersection of two private sets.
They use a commutative encryption that is quite similar to the Diffie–Hellman key exchange and operate in $\mathbb{Z}_p^*$ with $p$ being a safe prime.
Basically they hash each set element $x$ and then encrypt it with their randomly chosen key $k_A$ like this: $h\left(x\right) ^ {k_A} \mod p$.
A practical implementation would use a typical hash function like SHA1 and then square the result before encrypting.

EDIT:

This was my original question, but as it turns out, I missed, that their hashfunction maps to $\mathcal{QR}$. That makes my question dispensable:
Can they just do that? In my understanding they only have a 50% change to "hit" a generator (in $\mathbb{Z}_p^*$ only non quadratic residue are generators). Isn't that "dangerous" in terms of short circles and thus reduced security of the protocol?

Still interested in:
1. Wouldn't it be faster from a computational point of view to multiply $h\left(x\right) \cdot g$ where $g \in \mathcal{NQR}_p$ to get a new generator. (g should probably be chosen to be very small, to reduce calculation overhead)?

EDIT (already solved and basicly the protocol from the paper):
2. or calculate $h\left(x\right)^2$ to obtain a quadratic residue and then operate only in the subgroup $\mathcal{QR}_p$? Today my professor told me, that every element in $\mathcal{QR}_p$ is a generator for that subgroup, but didn't give a proof. Is that theorem true? How is it proven?

Thank you for answers.

-
2) What your professor said s certainly not true in general consider $(\mathbb Z_{17})^\times$. Then $13^2=16$ and $16^2=1$. But if $p=2q+1$ where $q$ is prime, i.e. a safe prime then we have there are (p-1)/2 quadratic residues (not including zero). Thereby there are precisely (2q+1-1)/2=q quadratic residues. So $\mathcal{QR_p}$ is a group of order $q$ and is thereby a cyclic group of prime order. It follows then, for instance from Lagrange's theorem, that any non-identity element generates the group. – JSchlather May 15 '12 at 20:41
Yes, he was talking about safe primes. Thanks, your argument is convincing. – kaidowei May 15 '12 at 20:56