1
$\begingroup$

I am currently reading a book called Serious Cryptography written by Aumasson to learn about Security. There was a paragraph talking about the security goal named indistinguishability (attached below), which reads in the section "Security Goals":

I've informally defined the goal of security as "nothing can be learned about the cipher's behavior." To turn this idea into a rigorous mathematical definition, cryptographers defined two main security goals that correspond to different ideas of what it means to learn something about a cipher's behavior:

  • Indistinguishability (IND) Ciphertexts should be indistinguishable from random strings. This is usually illustrated with this hypothetical game: if an attacker picks two plaintext and then receives a ciphertext of one of the two (chosen at random), they shouldn't be able to tell which plaintext was encrypted, even by performing encryption queries with the two plaintexts (and decryption queries, if the model is CCA rather than CPA).

  • Non-mallleability (NM) ...

While I understood that the point is to make it infeasible to point out which plaintext is encrypted when randomly given the ciphertext from one of 2 plaintexts.

I don't know how it is infeasible anymore when the attacker can now perform encryption/decryption queries on the given plaintexts as mentioned in the paragraph. Why can't they just encrypt both given plaintexts and then compare them with the given ciphertext?

$\endgroup$
4
  • 1
    $\begingroup$ Given the attacker a decryption oracle on plaintext doesn't make sense; it's about decrypting arbitrary ciphertext. So that part is just put into the text in in a hurry. Wikipedia indicates that: "... with the caveat that it may not pass the challenge ciphertext for decryption (otherwise, the definition would be trivial)" for both CCA1 and CCA2. $\endgroup$
    – Maarten Bodewes
    Sep 23, 2022 at 9:54
  • 1
    $\begingroup$ This is our canonical Q/A on these subject; Easy explanation of "IND-" security notions? and my advice read the paper di.ens.fr/david.pointcheval/Documents/Papers/1998_crypto.pdf $\endgroup$
    – kelalaka
    Sep 23, 2022 at 20:22
  • $\begingroup$ (Sorry for my late response) Thank you for your resources @MaartenBodewes and kelalaka. So it turned out that the "IND-" phrase must be attached to extra terms (CPA, CCA, etc.) to retrieve a more meaningful context of the requirement. Did i understand it correctly? $\endgroup$
    – John Pham
    Sep 27, 2022 at 14:34
  • 1
    $\begingroup$ Generally we expect the output of ciphers to be indistinguishable, but yes, indicating under which attack(s) the ciphers produce output that is indistinguishable from random in the output domain is important. If a cryptographer would tell me that a cipher is indistinguishable from random I´d assume the normal attack vectors for the kind of cipher. If a developer would tell me the same then I would start asking questions :) $\endgroup$
    – Maarten Bodewes
    Sep 27, 2022 at 15:29

1 Answer 1

1
$\begingroup$

I think you are missing the idea of randomness as part of a cryptographic application. It is not possible to create CPA-IND- order CCA-IND-security with a deterministic encryption scheme. Only by adding randomness, as an additional ephemeral secret key, those level of security can be archived.

Here is a very simple scheme (you can find it in Katz & Lindell's textbook (2nd edition)), which can be proven to be CPA-secure. $r$ is the needed randomness and $k$ is the standard secret key. $F$ is a pseudo random functions (based on $r$ and $k$)

enter image description here

$\endgroup$
3
  • $\begingroup$ (Sorry for my late response) Thank you for your help mate! Although I still cant understand much of your answer since I'm too new to this field :). Maybe this can help me when I reread in the future. $\endgroup$
    – John Pham
    Sep 27, 2022 at 14:31
  • $\begingroup$ So my understanding is that an "IND-" encryption must result in randomly different ciphertext every time it is applied to the same plaintext. Is it right? $\endgroup$
    – John Pham
    Sep 27, 2022 at 14:46
  • 1
    $\begingroup$ Yes, each ciphertext within the output domain must be equally likely for each plaintext. ¨Randomly different" is not a very strict notion. It might even be that some outputs are impossible for a specific key, and providing any random function over the output could hit an impossible value, even if it is in the expected output domain. $\endgroup$
    – Maarten Bodewes
    Sep 27, 2022 at 15:19

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.