Assume that we are given an element $g\in \mathbb{F}_{p^n}^*$ and $g$ does not belong to any of the smaller subfields contained in $\mathbb{F}_{p^n}$. If the degree of $g$ is some number $q$, how much is the time it takes to solve the DLOG problem in the group generated by $g$ dependent on $n$? I.e. if the order of the group element is small and stays small, but we keep increasing the size of the field that it belongs to, how much will computing the dlog slow down?

The reason why I started thinking about this is the MOV reduction for bilinear pairings. As I understand it, even though we have the index calculus algorithm in the target group, we are somehow able to make sure that the generator $e(g,h)$ in the target sits within a larger field extension of $\mathbb{F}_p$ and this somehow prevents us from translating the ''efficient'' DLOG from the target group to the source groups.

Anyone care to elaborate on the details?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.