In this paper, one of the facts stated was that $\text{IND-CPA} \not\implies \text{EKR}_p$, in which $\text{EKR}_p$ is defined as the property that for a polynomial number accessible of oracles p with p keys, an adversary is not able to determine any key and plaintext pairs within polynomial time. Here's how the paper defines this property.

enter image description here

I'm struggling to understand intuitively why this is the case since IND-CPA guarantees key recovery security with one oracle. Does it have to do with the fact that multiple oracles could be dependent in some way and thus give enough information to establish a key and plaintext pair?

  • $\begingroup$ I don't quite understand the definition as described and I also can't currently defeat the paywall. Could you quote the formal definition we're taking about? $\endgroup$
    – Maeher
    Feb 10 at 9:27
  • $\begingroup$ FWIW, one of the authors list her publications, and is still actively publishing (it looks like her work environment cares deeply about metrics of research output). There's a page for the paper, but it lacks a direct, open link to the paper. No more luck with other authors. $\endgroup$
    – fgrieu
    Feb 10 at 9:57
  • 1
    $\begingroup$ A conuter example could be a CPA secure scheme that takes additional randomness for encryption. Like some fix random value other than IV which is independent of the key and is output with each encryption. Then you can split up one of the keys and use it has randomness for the other oracles. For example using Threshold secret sharing. The scheme remains cpa secure but querying enough oracles allows to recover one key. $\endgroup$ Feb 10 at 22:26

1 Answer 1


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.

  • $\begingroup$ So the main issue for the defender arises from the fact that they have p different keys to protect instead of just 1, which gives the attacker much higher chances to get lucky? $\endgroup$
    – chemN00b
    Feb 10 at 18:55
  • $\begingroup$ @chemN00b: yes that's it. However, the weakening due to more keys does not happen for many if not most well-engineered cryptosystems. The expanded answer gives two least rare reasons why it can happen. In fact if probability of success grows appreciably (or worse linearly) with the number of keys to defend, then we say the cryptosystem is broken/vulnerable under multi-target attack and the practitioner may need to do something about it, like fixing the issue, increasing key size, or modifying key generation to avoid weak keys. $\endgroup$
    – fgrieu
    Feb 10 at 20:21

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.