In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $w_0, w_1$ and the encryption keys are in the subgroup but the private values such as $a, b, r_0, s_0$, etc. are not? Does the construction work for any subgroup or is it more typical to use group of quadratic residues modulo prime?

Sorry if this is a bit elementary, any references regarding how subgroups are used in DH-based protocols are also appreciated.

[1] "Efficient oblivious transfer protocols" http://www.pinkas.net/PAPERS/effot.ps


1 Answer 1


The protocol's security comes from the DDH assumption, which is only secure when operating in groups of prime order [1]. The more typical groups, e.g. $\mathbb{Z}_p^*$ is not of prime order, but of order $p - 1$. Fortunately, a subgroup of $\mathbb{Z}_p^*$, namely the set of quadratic residues modulo $p$ doesn't have this problem. This answers the first question.

To answer the second question, the public values such as $x, y$ and so on are in the subgroup. The private values are selected uniformly at random from $\mathbb{Z}_q$, where $q$ is the order of the subgroup (and the generator $g$).

Finally, the set of quadratic residues is one of the simpler subgroups to understand, but others are also possible as long as DDH is hard. Some alternatives are outlined in [2].

[1] Katz and Lindell, Introduction to modern cryptography, Chapter 7.3.3

[2] Dan Boneh, The decision diffie-hellman problem, Section 1.1, http://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf


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.