# Does encryption using PRP mean indistinguishable encryption against an eavesdropper?

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?

## 2 Answers

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.

• Yes, I understand my security definition is weak. However, I'd like to know the inclusion relation between the set of strong PRPs and the set of encryption/decryption functions which satisfy the security definition. Are strong PRPs always satisfy the definition? Or are these sets equivalent ? – kkita Nov 7 '18 at 5:40
• @kkita I am not quite sure I understand your question. But yes, I think any PRP satisfies your security definition and can be strengthened as I described. The other direction does not hold because OTP is secure in your definition but not a PRP. – Shan Chen Nov 7 '18 at 5:51

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.

• I know about block cipher modes of operation. Actually, I assume the case in which one block (e.g., 128 bit) message is encrypted with a strong PRP. I am interested in whether the ciphertext generated by a strong PRP will not leak any partial information about the plaintext to adversaries who is not given oracle access. – kkita Nov 7 '18 at 14:32