Does encryption using PRP mean indistinguishable encryption against an eavesdropper?

Question

I am a student studying cryptography by reading "Introduction to Modern Cryptography". I have some confusion about encryption using PRP (e.g., AES).

Briefly speaking, a keyed deterministic permutation $F_{k}$ is a strong PRP if no efficient adversary (who is given oracle access to $F_k$ and $F_k^{-1}$) can distinguish whether it is interacting with $F_k$ (for uniform $k$) or $f$, where $f$ is chosen uniformly from the set of all permutations having the same domain and range.

I think the definition above says nothing about the relation between two ciphertexts which are generated by a PRP.

Now, I consider the following experiment $PrivK_{\mathcal{A},\Pi}^{eav}(n)$ for any encryption scheme $\Pi= (Gen,Enc,Dec)$.

1. The adversary $\mathcal{A}$ is given input $1^n$, and outputs a pair of messages $m_0$,$m_1$, with $|m_0| = |m_1|$.
2. A key $k$ is generated by running $Gen(1^n)$, and a uniform bit $b \in \{0,1\}^n$ is chosen. Ciphertext $c \gets Enc_k(m_b)$ is computed and given to $\mathcal{A}$.
3. $\mathcal{A}$ outputs a bit $b^{'}$.
4. The output of the experiment is defined to be 1 if $b^{'}=b$, and 0 otherwise.

A private-key encryption scheme has indistinguishable encryptions in the presence of an eavesdropper if for all PPT adversaries $\mathcal{A}$ there is a negligible function $negl$ such that, for all $n$, $Pr[PrivK_{A,\Pi}^{eav}(n)] <= \frac{1}{2} + negl(n)$.

Does the encryption scheme has indistinguishable encryptions in the presence of an eavesdropper if $Enc = F_k$ and $Dec = F_k^{-1}$, where $F_k$ is a strong PRP?

In other word, when I encrypt two messages by using PRP, adversaries can be able to tell whether the two messages are identical since PRP is deterministic. However, can I ensure that it is infeasible for adversaries to learn any partial infomation about the plaintext from the cipertext?

Answer 1

The PRP encryption scheme is secure in your security definition, but this security is very weak. It only achieves "one-time security" and is also weaker than perfect secrecy, i.e., the adversary's advantage is not exactly 1/2.

I think the security can be stronger (but still cannot be IND-CPA for instance). With PRP security, we can view $F_k$ (and hence $Enc_k,Dec_k$) as a real random permutation $f$ (except for a negligible PRP security advantage). Then, even if the adversary knows $p$ message-ciphertext pairs, it still cannot distinguish $m_0,m_1$ if they do not belong to the known $p$ messages.

Answer 2

I think you are confusing PRP security with CPA (chosen plaintext security) security for an encryption scheme.

Does the encryption scheme has indistinguishable encryptions in the presence of an eavesdropper if $Enc=Fk$ and $Dec=F^{−1}_k$, where $F_k$ is a strong PRP?

No, but that is not a problem. If you consider AES to be a good PRP, on its own it is not an encryption scheme. It is merely a building block for one. You need to use the PRP in a mode of operation (such as CTR or CBC) so that it becomes a CPA-secure (or more) encryption scheme.