Multi-target attacks of ECC 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?

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.