The intuition is: for a given effort, it may have low probability to find the key (or otherwise attack) for one instance of a cryptosystem, but it may be possible to find one of $p$ keys with good probability and thus attack one of $p$ instances. This matters in situations where an attacker does not care which instance they break; e.g. many users of a single desirable resource each have an access key of their own, thus an attacker that can do what any one of these keys allows gets access to the resource.
The most common reason for this to occur is when the bulk of the work for an attack is common to all instances, yet the probability of success of the attack scales linearly with the number of instances. Within this, the most common reason is when the cost of testing a candidate key can be shared among multiple instances.
To illustrate this in symmetric encryption (as considered in the abstract of the linked article), consider an $\operatorname{IND-CPA}$ encryption scheme built on top of AES-128, e.g. AES-GCM. Modify it by prefixing the ciphertext with the encryption of the all-zero bitstring per AES-128 under the key. The modified scheme remains $\operatorname{IND-CPA}$-secure, but is not $\operatorname{EKR}_p$-secure.
The problem is that the added prefix allows a multi-target key-recovery attack. Given one ciphertext for each of $p$ random keys, we can recover one key and one plaintext with probability $q$ and effort involving about $2^{128}q/p$ encryptions: for incremental keys we encrypt the all-zero bitstring with AES-128, search the result in a table of the first 128 bits of the $p$ ciphertexts, and in the (extremely rare) case of a match we attempt decryption of the rest of the corresponding ciphertext. For $p=2^{32}$ and $q=2^{-8}$ the expected number of encryptions is $2^{88}$, which is expensive but feasible.
Note: the attack is largely theoretical, because for an attack hardware optimized for trillions of trillions of encryptions and searches as required, the energy cost of search exceeds that of encryption for $p$ above some level less than a million.
An attack being facilitated by many instances can happen by other mechanisms. One is when there is an efficient attack in the specific case that the key happens to be in a narrow subclass of the possible keys. An example of this is RSA public-key encryption with proper padding (e.g. RSAES-OAEP) and 960-bit public modulus the product of three random primes each 320-bit.
The best known attack is factoring the public modulus. For a single one of this form, the two algorithms of choice are
- GNFS, but the record is a 829-bit composite, and around that the difficulty about doubles for each additional 25 bits, so 960 bit is >30 times harder. If the adversary has less computing power than this threshold, GNFS is just not an option.
- ECM, which is a strong contender because it's probability of success grows roughly linearly with the effort spent, and as a function of the bit size of the lowest prime factor (once it's found, GNFS with factor the 640-bit remaining part relatively easily). The record is a 274-bit factor of a 947-bit number, and around that the effort about doubles for each additional 7 bits of the factor so we are talking >70 times harder, but it's not hopeless: even though that ECM record was lucky, it used much less computing power than the above GNFS record.
The situation changes when there are many target moduli. Above some number, and for effort below the GNFS threshold, a strategy with better success probability than ECM is sharing the available computing power to run an appropriately parametrized Pollard's $p-1$ on each moduli, hoping that one has a factor $p$ with the two largest factors of $p-1$ below the threshold allowing the method to succeed. Similarly spreading the ECM effort is fruitless, because there is no class of specially weak moduli against ECM. Correspondingly perhaps, some RSA key generation criteria including that kept in FIPS 186-5 require factors $p$ of RSA moduli to have $p-1$ with a large prime factor due to Pollard's $p-1$; same for $p+1$ due to William's $p+1$. However there's consensus that progress of GNFS have made these precautions unnecessary, for bi-prime RSA and modern key size at least.
