We say a symmetric key encryption scheme $\Pi_{1} = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is computational security if for every PPT algorithm $A$ and every $x_{0}, x_{1}$ ($|x_{0}| = |x_{1}|$), $$ \left\vert \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{0})) = 1\right] - \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$

Is there a definition of computational security of public-key encryption as following?

We say a public-key encryption scheme $\Pi_{2} = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is computational security if for every PPT algorithm $A$ and every $x_{0}, x_{1}$ ($|x_{0}| = |x_{1}|$), $$ \left\vert \Pr\left[\mathrm{Gen}(1^{n})= (pk, sk); A (pk, \mathrm{Enc}_{pk}(x_{0})) = 1\right] - \\ \Pr\left[\mathrm{Gen}(1^{n})= (pk, sk); A (pk, \mathrm{Enc}_{pk}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$

Is it equivalence to IND-CPA?

  • $\begingroup$ Intuitively this reads like it just more formally wrote down the IND-CPA game, but of course, intuition is no proof, especially when it comes to potential subtleties being at work here... $\endgroup$
    – SEJPM
    May 7, 2018 at 17:39
  • $\begingroup$ Your definition for symmetric-key encryption is for one-time security only. It is not equivalent to the standard CPA definition. Your definition for public-key encryption doesn't give the public key to the adversary, so it's also very different than the usual CPA definition. $\endgroup$
    – Mikero
    May 11, 2018 at 1:58
  • $\begingroup$ @Mikero I modify it, maybe it dose not make sense if the adversary does not $pk$. But in my opinion, it is little stronger than CPA if $A$ knows $pk$. $\endgroup$
    – Blanco
    May 12, 2018 at 8:44

2 Answers 2


I am sorry, but I think you are misusing the term "computational security". This concept is a much broader than the definition you have written.

We say that a scheme is computational secure if it satisfies some security definition on which the attacker is supposed to have limited resources (typically, the attacker is supposed to run in polynomial time).

This concept must be seen as the opposite of unconditional security, which makes no assumptions about the resources available to an attacker.

That said, the definition you have provided to symmetric key encryption scheme is actually the definition of passive one-time semantic security, which you can find, for instance, on the book Introduction to Modern Cryptography (definitions 3.8 and 3.12 in the second edition. They are proved to be equivalent...)

There is no equivalent definition for public-key schemes because the attacker has the encryption key and knows the encryption algorithm (Kerckhoffs's principle), so one can't impede she/he from generating many pairs of cleartexts and ciphertexts (therefore, no one-time-like definition is possible). This is why we stick with IND-CPA security.

Moreover, this is also why the second security definition you have provided is not equivalent to IND-CPA: you are not supposing the adversary can chose several plaintexts and encrypt.

Considering the definition of IND-CPA on Wikipedia, you skipped the second step:

  1. The adversary may perform a polynomially bounded number of encryptions or other operations.

I wouldn't differentiate them as symmetric and asymmetric. It is just the case in the public/private scheme $k$ has two parts.

There is the slight alteration that the encryption and decryption algorithms use different parts of the key so I guess the second formalisation is necessary.

To calculate the sum, the probabilities will be derived from the likelihood of solving hard problems.


Your Answer

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

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