3
$\begingroup$

Imagine a situation where there are many high-value public keys around, using the same Elliptic Curve group, say $k$ in the millions public keys¹. Can an adversary reasonably find one of the matching private key at much lower cost that finding the private key for a particular one?

What's the best feasible² method? What's it's cost relative to the best known feasible method for one key (that is, I believe, distributed Polard's rho with distinguished points), as a function of $k$ and perhaps the Elliptic Curve group order $n$?

¹ Imagine Bitcoin with secp224k1, and the corresponding ponzi had similar market value.

² Assuming known existing technologies, including supercomputers, GPUs, FPGAs, ASICs, but not quantum computers usable for cryptanalysis.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I know Kuhn and Struik proved in 2001 (section 4) that Pollard's rho method can compute $k$ discrete logs in $\sqrt k$ time. The first takes the full expected time, the second less, the next even less, etc. $\endgroup$
    – SAI Peregrinus
    Commented Jun 25, 2021 at 14:31
  • 2
    $\begingroup$ The issue with that is that it's from 2001. I expect there's new research, or that new attacks might be cheaper. So I don't really want to answer it with that alone, since it's a 20-year old paper. I just remembered that it's cited in the "Batch discrete logarithms" section of Bernstein's Curve25519 paper and looked it up. Certainly it's an upper-bound on the difficulty though. $\endgroup$
    – SAI Peregrinus
    Commented Jun 25, 2021 at 14:36
  • 1
    $\begingroup$ This is basically the same as this answer $\endgroup$
    – Samuel Neves
    Commented Jun 25, 2021 at 16:04
  • $\begingroup$ @Samuel Neves: thanks for pointing that. Not quite the same maybe: precomputation is not the same as multi-target, because the target(s) are not known when a precomputation starts. In RSA at least, that makes a significant difference: I know no precomputation attack to factor RSA moduli, but there are some (borderline useful) multi-target attacks, like Pollard's p-1. $\endgroup$
    – fgrieu ♦
    Commented Jun 25, 2021 at 16:06
  • 2
    $\begingroup$ No; finding all $k$ private keys costs $O(\sqrt{kn})$, that is, you save a $\sqrt{k}$ factor compared to solving each log separately. This has been explicitly proved by Yun, but was already the cost of the best attack since 1997 or so (Silverman). $\endgroup$
    – Samuel Neves
    Commented Jun 25, 2021 at 16:16

1 Answer 1

Reset to default
2
$\begingroup$

Can an adversary reasonably find one of the matching private key at much lower cost that finding the private key for a particular one?

No, and that's provable (and is independent of the technology employed)

Suppose that we had a black box that could take $k$ different public keys $a_1G, a_2G, ..., a_kG$, and recover $a_iG$ (for some $i$) in $o(\sqrt{n})$ time.

Then, here is how we could use that black box to, given one public key $aG$, recover the private key $a$ in $o(\sqrt{n})$ time. We would:

  • Select $k$ random values $r_1, r_2, ..., r_k$, and compute the sequence $r_1(aG), r_2(aG), ..., r_k(aG)$, which (by defining $b_i = r_i a$) can be viewed as $b_1G, b_2G, ..., b_kG$

  • Give the sequence $b_1G, b_2G, ..., b_kG$, which will recover $b_i$

  • We compute $a = r_i^{-1}b_i$, and thus recover the key.

The steps in addition to the invocation of the black box takes $O(k)$ time, which can be ignored for reasonablely sized $k$.

Note that the sequence $b_1G, b_2G, ..., b_kG$ is uniformly distributed, and hence even if the black box is probabilistic, it'll still allow us to recover the public key.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's a variation of something you already told me, and spot on! $\endgroup$
    – fgrieu ♦
    Commented Jun 25, 2021 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.