I recently learned of this interesting paper (published in IEEE Trans. Information Theory, volume 54, number 1, pages 404-406 in 2008). I’m not sure how I missed it back in 2008. But I expect that some other people probably don’t know about it too. Florian Hess told me about it.

First a reminder of the subset-sum problem: Given a set of integers { a1, . . ., an } and a target integer s, to write s as a sum of the integers ai (each used at most once). In other words, find a subset of the given set of integers that sums to s.

There is also a decisional version of subset-sum: Given a set of integers { a1, . . ., an } and a target s, to determine whether or not s can be written as a sum of the integers ai (each used at most once).

Subset-sum is easily seen to be polynomial-time equivalent to the decisional version: To determine whether or not a1 appears in the sum representation of s, just solve the two decisional problems ( { a1, . . ., an } , s ) and ( { a2, . . ., an }, s ). Now repeat this idea for each of the ai.

It is known that the decisional subset-sum is NP-complete (I believe this result is essentially due to Karp). Though there is a huge amount of research on efficient approximation algorithms for it (these are algorithms that try to find a subset that sums to an integer “close” to s).

Cheng’s paper remarks that subset-sum can also be reduced to an elliptic curve version: Let E be an elliptic curve over a finite field and let P be a point of order bigger than twice the sum of all the ai. Set { P1 = [a1]P, . . ., Pn = [an]P } and set S = [s]P. The elliptic curve subset-sum problem (ECSSP) is to write S as a sum of the points Pi (each used at most once). Obviously, if one can solve the ECSSP then one has solved the original subset-sum problem. It is also easy to see that the decisional version of ECSSP is equivalent to the computational version. Since subset-sum is NP-complete it follows that ECSSP is NP-complete.

A simple remark, not made in Cheng’s paper, is that if ECSSP was easy then ECDLP would be easy. This can be seen by considering the ECSSP instance ( { P, [2]P, [4]P, [8]P, . . ., [2^k]P }, S ). Solving the subset-sum leads to a solution to the ECDLP. The converse does not hold (i.e., we cannot deduce that ECDLP is NP-complete). If the approximation algorithms for subset-sum could be adapted to the case of ECSSP then one could solve ECDLP efficiently. The problem is that the non-linear behaviour of the elliptic curve group law seems to mess everything up (as usual). But this could be an interesting topic for further study.

Anyway, the point of Cheng’s paper is to relate ECSSP to the problem of computing the minimal distance of an algebraic-geometry code based on an elliptic curve. The code is the set of n-tuples ( f(P1), . . ., f(Pn) ) where f runs over the Riemann-Roch space L( S + (k-1)(oo) ) for the elliptic curve. The minimum distance of the code is proved in Cheng’s paper to be either n-k or n-k-1, depending on whether or not Q is equal to a sum of the points Pi. So, if there is an efficient algorithm to compute minimum distances of AG codes from elliptic curves, then one can solve ECSSP and hence ECDLP. The main result of Cheng’s paper is therefore that computing the minimal distance is NP-hard even for this special class of codes.

(Please accept my apology for not typesetting this post nicely.)

— Steven Galbraith

Pingback: Elliptic curve discrete logarithm problem in characteristic two | ellipticnews