Skip to main content
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
Source Link

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups.

In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ground field, where smoothness is given in terms of irreducibility.

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.

Another approach is to try and decompose points into sums of a special pointset within the elliptic curve group itself. This is the summation polynomial approach of Semaev, but it only seems to work well for curves over extension fields, where the Point Decomposition Problem is tractable. Note also that recent advances have shown that in binary curves index calculus is actually asymptotically feasible.

Apart from direct attacks, there are some other ways to solve elliptic curve discrete logs using index calculus for special curves. The MOV attackMOV attack uses the Weil pairing to map the logarithm to an extension field, where you can use the regular index calculus algorithms. The GHS attack maps the logarithm to a logarithm on a hyperelliptic curve of hopefully low genus, where index calculus attacks are also efficient.

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups.

In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ground field, where smoothness is given in terms of irreducibility.

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.

Another approach is to try and decompose points into sums of a special pointset within the elliptic curve group itself. This is the summation polynomial approach of Semaev, but it only seems to work well for curves over extension fields, where the Point Decomposition Problem is tractable. Note also that recent advances have shown that in binary curves index calculus is actually asymptotically feasible.

Apart from direct attacks, there are some other ways to solve elliptic curve discrete logs using index calculus for special curves. The MOV attack uses the Weil pairing to map the logarithm to an extension field, where you can use the regular index calculus algorithms. The GHS attack maps the logarithm to a logarithm on a hyperelliptic curve of hopefully low genus, where index calculus attacks are also efficient.

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups.

In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ground field, where smoothness is given in terms of irreducibility.

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.

Another approach is to try and decompose points into sums of a special pointset within the elliptic curve group itself. This is the summation polynomial approach of Semaev, but it only seems to work well for curves over extension fields, where the Point Decomposition Problem is tractable. Note also that recent advances have shown that in binary curves index calculus is actually asymptotically feasible.

Apart from direct attacks, there are some other ways to solve elliptic curve discrete logs using index calculus for special curves. The MOV attack uses the Weil pairing to map the logarithm to an extension field, where you can use the regular index calculus algorithms. The GHS attack maps the logarithm to a logarithm on a hyperelliptic curve of hopefully low genus, where index calculus attacks are also efficient.

Source Link
Samuel Neves
  • 13k
  • 47
  • 54

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups.

In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ground field, where smoothness is given in terms of irreducibility.

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.

Another approach is to try and decompose points into sums of a special pointset within the elliptic curve group itself. This is the summation polynomial approach of Semaev, but it only seems to work well for curves over extension fields, where the Point Decomposition Problem is tractable. Note also that recent advances have shown that in binary curves index calculus is actually asymptotically feasible.

Apart from direct attacks, there are some other ways to solve elliptic curve discrete logs using index calculus for special curves. The MOV attack uses the Weil pairing to map the logarithm to an extension field, where you can use the regular index calculus algorithms. The GHS attack maps the logarithm to a logarithm on a hyperelliptic curve of hopefully low genus, where index calculus attacks are also efficient.