Does Index calculus work on secp256k1?

Cerina

2/13/24, 4:29 PM

I did a search but couldn't find answers, Can I use Index calculus to find private key of the elliptic curve secp256k1?

1 + 2

elliptic-curves

Daniel S

2/13/24, 4:48 PM

No it does not.

user93353

2/14/24, 12:31 AM

Index Calculus uses smooth numbers in ${F^*}_p$. Elliptic Curve groups do not have a straightforward notion of smoothness & hence Index Calculus does not work in Elliptic Curve groups.

Score:1

Crypto

Mark

2/13/24, 4:51 PM

No. Index calculus algorithms are more efficient algorithms that make special use of the structure of $(\mathbb{F}_p^\times, \times)$ to solve the discrete logarithm problem in these groups (there are also applications to factoring). This is to say that they do not only use the API of a group, and instead use the special details of the "implementation" of this group.

Algorithms that only use the API of a group are called generic, and discrete log problems in any group are vulnerable to them. For certain groups these generic algorithms are the best (known) algorithms. Elliptic curve groups are the most common class of (thought to be) generic groups used in cryptography.

+ 3

fgrieu

2/13/24, 4:55 PM

Subtitle: this answer's $(\mathbb{F}_p^\times, \times)$ is the [multiplicative group modulo](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) $p$, sometime also noted $\mathbb Z_p^*$ or $(\mathbb Z/p\mathbb Z,*)$.

Geoffroy Couteau

2/13/24, 5:03 PM

Nitpicking, but not all elliptic curve groups are thought to be as hard to attack as generic groups. For example, when a pairing is available, the MOV attack can effectively reduce solving DLOG over the curve to solving DLOG over (the multiplicative subgroup of) a field. Hence, some elliptic curves can actually be attacked by a variant of index calculus (more precisely, MOV + index calculus).

user93353

2/14/24, 12:33 AM

The structure used in Index Calculus is the notion of smooth numbers in ${F^*}_p$, right?. Elliptic Curve groups do not have a straightforward notion of smoothness & hence Index Calculus does not work in Elliptic Curve groups.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does Index calculus work on secp256k1?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.