Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  del Apr 26 '12 at 16:00
    
@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. –  D.W. May 1 '13 at 20:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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