International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 12 October 2015

Koh-ichi Nagao
ePrint Report ePrint Report
Semaev shows that under the first fall degree assumption, the complexity

of ECDLP over $\\bF_{2^n}$, where $n$ is the input size, is

$O(2^{n^{1/2+o(1)}})$.

In his manuscript, the cost for solving equations system is $O((nm)^{4w})$,

where $m$ ($2 \\le m \\le n$) is the number of decomposition

and $w \\sim 2.7$ is the linear algebra constant.

It is remarkable that the cost for solving equations system under the

first fall degree assumption, is poly in input size $n$.

He uses normal factor base and the revalance of \"Probability that

the decomposition success\" and \"size of factor base\" is done.

%So that the result is induced.

Here, using disjoint factor base to his method,

\"Probability that the decomposition success becomes $ \\sim 1$ and

taking the very small size factor

base is useful for complexity point of view.

Thus we have the result that states \\\\

\"Under the first fall degree assumption,

the cost of ECDLP over $\\bF_{2^n}$, where $n$ is the input size, is $O(n^{8w+1})$.\"

Moreover, using the authors results,

in the case of the field characteristic $\\ge 3$, the first fall

degree of desired equation system is estimated by $\\le 3p+1$.

(In $p=2$ case, Semaev shows it is $\\le 4$. But it is exceptional.)

So we have similar result that states \\\\

\"Under the first fall degree assumption,

the cost of ECDLP over $\\bF_{p^n}$, where $n$ is the input size and (small) $p$ is a constant, is $O(n^{(6p+2)w+1})$.

Expand

Additional news items may be found on the IACR news page.