Can you help me understand pairing $e:G \times G \to G_T$ and ( Decision) BDH assumption?
An attack against the signature scheme over some group where DDH is easy, can be turned into a solver for the CDH problem over the same group, as is shown in Section 2.3 in the Asiacrypt paper you refer to.

So what you are really asking is: In what groups where DDH is easy is CDH still hard?

I would not use elliptic curves over extension fields of low characteristic. Using ordinary elliptic curves over prime fields with a relatively small embedding degree seems ok.