It is possible to avoid square root step of this paper by chosing a different curve type?

The paper works with elliptic curves. But what about using curves in the form of y=x^(6)+Ax^(2)+B^2 or y=x^(2)+Ax+B? Of course in such cases the square root computation would no longer be needed but would it be usefull?

My underlying problem in my case is the Oracle can only return powers in the form of [a^(x)]