Attacking any one in many public keys

Question

The problem of finding private key from public key is typically studied in the one-key setup: what's the expected cost of breaking one key (e.g. by factoring a public modulus, or solving a discrete logarithm in some group).

There is much less work on simultaneously attacking $k>1$ keys. One notable exception is Daniel J. Bernstein and Tanja Lange's Batch NFS, in proceedings of SAC 2014. They conclude that increasing $k$ allows asymptotic savings on the expected cost per factorization.

A different problem is attacking any one in $k>1$ keys. It seems understudied too, although it is of practical concern, especially in setups where there can't be a revocation list. For example, there are deployed systems such that an attacker could gather many thousands public keys of devices that can write in Smart Cards after authentication, and does not care which one is broken: whatever one allows falsifying records made in the Smart Cards. Also, from a public relations perspective, it's hard to convey that indeed, a hacker demonstrated breaking one key in your system, but it is still safe enough since there's no positive evidence that the adversary could attack a particular key.

We can trivially state that the expected difficulty of attacking any one in $k$ public keys is at most that of attacking one key. I conjecture that it is at least $1/k$ that, at least in the case of factorization.

Can we be more precise, in general, or in the special cases of factorization (RSA…), discrete logarithm in $\Bbb Z_p^*$ (DSA…) or elliptic curve group groups (ECDSA, EdDSA…)?

---

Update: Poncho quickly pointed that the problem is settled for the discrete logarithm with shared parameters like public prime modulus or curve, which is customary. The question remains in general, for factorization, and DL with per-key parameters.

Answer 1

Actually, a well known result is that, for any cryptosystem that relies on the hardness of the DLog problem (including ECDlog), there is no such reduction in strength if you have $k$ keys. That is, the problem of "here are $k$ keys, break any one" is essentially as hard as the problem "here is one key, break it".

The proof is straight-forward; first off, we assume that the cryptosystem is based on Dlog, hence breaking the system is equivalent to solving some DLog problem. Further suppose we did have a method of, given $k$ values $a_1G, a_2G, …, a_kG$, of finding $a_i$ for some $i$, and this takes effort $M$ [1].

Then, given $bG$, we can attempt to recover $b$ by selecting $k$ random values $r_1, r_2, …, r_k$; and compute $r_1(bG), r_2(bG), …, r_k(bG)$. We then hand this off to our oracle, which gives us the value $c$ s.t. $cG = r_i(bG)$ for some $i$; we then compute $b = cr_i^{-1}$, and thus recovering $b$, at the cost of $M$ plus the time to do $k$ point multiplications (which is quite feasible assuming $k$ isn't ridiculously large).

Similar proofs would apply to DH-based cryptosystems as well.

---

[1]: I'm using additive notation, mostly because I find it easier to read...