In cryptography there are 4 basic attack classifications:

  • Ciphertext-Only Attack
  • Known-Plaintext Attack
  • Chosen-Plaintext Attack
  • Chosen-Ciphertext Attack

In Katz & Lindell's textbook (2nd edition) I only found definitions for COA-,CPA- and CCA-Security. I couldn't find a definition and experiment for KPA-Security. In general I wasn't able to find a good definition.

My questions:

  • Can someone provide me good definition and experiment?
  • Why is KPA-Security so unimportant? (I know that CPA-Sec includes KPA-Sec)
  • Is there a use case for KPA-Security? Does an symmetric encryption scheme exist, that has KPA-Security but not CPA-Security and how would this look like?

1 Answer 1

  • Per Katz and Lindell 3rd ed. section 7.2. "In a known-plaintext attack, the attacker is given pairs of inputs/outputs $\{(x_i,F_k(x_i))\}$ (for an unknown key $k$), with the $\{x_i\}$ outside the attackers control." KPA is the usual attack model for linear cryptanalysis, but is insufficient for differential cryptanalysis where we need each input to match up with another specific fixed input. Take any simple linear analysis of a block cipher and it should only use the KPA property.
  • Per Katz and Lindell 3rd ed. section 1.4.1: "none of them [the threat models] is inherently better than any other; the right one to use depends on the environment in which an encryption scheme is deployed"
  • Yes, one could envision a block cipher that is secure against linear cryptanalysis, but insecure against differential cryptanalysis. If we further assume that insufficient difference data can be acquired simply by generating inputs in an uncontrolled way, the cipher would be KPA secure, but not CPA secure. If deployed somehow that means that adversaries cannot influence the choice of input, the cipher would presumably not be at risk. Most cryptographers would still prefer a cipher that is CPA (or indeed CPA plus CCA) secure.

Note that the above discussion is restricted to symmetric cryptography. With public key encryption, we have to assume CPA at a minimum as the public encryption method automatically allows the adversary a CPA capability.

  • $\begingroup$ With "unimportant" I mean, that there is only little literature about it. Can you provide me some, that explains KPA-security more deeply? $\endgroup$
    – Titanlord
    Commented Oct 28, 2021 at 10:00
  • $\begingroup$ Another question I have: Is the security definition and experiment from Katz & Lindell for multiple encryptions ($PrivK_{A,\Pi}^{mult}(n)$) a definition/experiment for KPA-security? $\endgroup$
    – Titanlord
    Commented Oct 28, 2021 at 11:16
  • 1
    $\begingroup$ In $\mathrm{PrivK}^{\mathrm must}_{A,\Pi}(n)$ in section 3.4.1of K&L: no this is not a KPA experiment. Part 1 of the experiment allows the adversary to generate the inputs and this can be done in a controlled way. $\endgroup$
    – Daniel S
    Commented Oct 28, 2021 at 11:48
  • 1
    $\begingroup$ In re more literature: I'm not sure that I can. As you say, there's not much usage: public key automatically requires the stronger CPA model and modern block ciphers can be designed to meet the CPA/CCA model with little or no downside. I'll search around, but can't promise that I'll find anything. $\endgroup$
    – Daniel S
    Commented Oct 28, 2021 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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