I've recently looked a bit at pairing based cryptography and I was wondering what properties the groups involved should have in order to be useful for cryptographic purposes? Has anything more exact been formulated? As an example, we could just take the pairing

$\mathbb{Z}_p\times \mathbb{Z}_p\to \mathbb{Z}_p,\;\; (x,y)\mapsto xy,$

where the group is the additive subgroup of $\mathbb{Z}_p$. Clearly, this would not be terribly useful for cryptographic applications, since picking any nonzero $a\in \mathbb{Z}_p$ as a generator, we can trivially solve the discrete logatithm problem in this additive group. Hence any standard formulation of Diffie-Hellman can be solved as $c$ from $ca$ can be solved just by multiplying with the inverse of $a$, which is efficiently computable. How do we differentiate between ''good'' and ''bad'' groups?


1 Answer 1


That depends on the protocol being used, but most pairing-based protocols assume that the Bilinear Diffie-Hellman (BDH) problem is hard: given $P, aP, bP, cP$ for group element $P$ and integers $a, b, c$ it is hard to compute $e(P, P)^{abc}$ for a given pairing $e$.

There are many related problems that, if broken, could be used to break the BDH: the discrete logarithm, the Computational Diffie-Hellman (given $P, aP, bP$ compute $abP$), etc.

  • $\begingroup$ Thanks. My question might have been a bit vague, but I was sort of thinking about whether there's some sort of fuzzy classification of such groups where this is assumed to be hard. In other words, what properties the groups should NOT have for the various Diffie-Hellman problems to be assumed difficult. Knowing how little one knows about complexities of hard problems in general, I assume that this is unknown. $\endgroup$
    – del
    Commented Apr 26, 2012 at 16:00
  • $\begingroup$ @EdvardFagerholm, unless you can somehow narrow down the question somehow, I don't think you're going to get a more useful answer than the characterization "groups where the BDH problem is hard". I don't think we have a complete characterization of what groups the BDH problem is hard in, based solely upon clean/elementary properties of the group. $\endgroup$
    – D.W.
    Commented May 1, 2013 at 20:40

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.