To which game-based security definition is Perfect Secrecy equivalent?

Question

We all know the classic definitions of perfect secrecy, being $$\Pr[M=m|C=c]=\Pr[M=m]$$ and $$H(M|C)=H(M)$$

But now what I've asked myself:
If we were to remove the polynomial restriction on the attacker, which game-based security definition would be equivalent to perfect secrecy and how would one show this?

---

Of course I've thought about this myself and it's obvious that known- and chosen-plaintext security is a given as we still can't learn anything new about the plaintext if a scheme is perfectly secret.
Even with chosen-ciphertext attacks I don't see how one could deduce more information on a perfectly secret scheme, given that the challenge ciphertexts would still be independently encrypted.
What I kinda can't grasp though is the reverse direction and of course the formal proof of equivalence.

Answer 1

Perfect secrecy corresponds to semantic security. Or rather, semantic security is an adaption of perfect security for computationally limited adversaries, but a variant of the same definition also works for unlimited adversaries.

In other words, consider a game between an adversary and a simulator. The simulator chooses its key material. The adversary may submit messages and get their encryption in return. He then chooses a distribution over plaintext messages (all of equal length) and a binary predicate $f$, such that the probability that $f(m)=0$ is $1/2$. The simulator chooses a message according to the distribution, encrypts it and sends the challenge to the adversary. The adversary must now determine $f$. His advantage is the difference between his probability of guessing $f(m)$ correctly and $1/2$.

You need to be a bit careful with your encryption oracle and challenge ciphertext encryption, so that key material is only used to encrypt once. Once that it done, it is clear, as you say, that the encryption oracle doesn't help an adversary.

With a small amount of work, it now follows from perfect secrecy that any adversary in this game will have advantage exactly $1$. Also, if any unlimited adversary has advantage exactly $1$, it must follow that you have perfect security.

Note that if you try to adapt chosen ciphertext attacks, no reasonable definition will result in the one-time pad being secure, since it isn't secure against these attacks.