Is there a computational security of public-key encryption which is similar to the one of symmetric key encryption

Question

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?

Answer 1

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:

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

Answer 2

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.