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 2


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.

  • $\begingroup$ 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 ? $\endgroup$
    – kkita
    Nov 7, 2018 at 5:40
  • 1
    $\begingroup$ @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. $\endgroup$
    – Shan Chen
    Nov 7, 2018 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.

  • $\begingroup$ 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. $\endgroup$
    – kkita
    Nov 7, 2018 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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