2
$\begingroup$

I found some foundations of crypto course notes that mention that these two are equivalent statements of their own degrees of security and was given the following definitions:enter image description here

I was always under the impression that the second definition (the one on the bottom) was the prescribed one for Semantic Security, and that computational indistinguishability was a completely separate thing? I do not understand the necessity or intuition behind the need for a "simulator" as it is called. Can someone shed some light?

$\endgroup$
  • $\begingroup$ Course notes are meant to be used in a classroom setting, where an instructor is available to fill in such gaps. It sounds like a self-contained textbook would be a more appropriate source for you. $\endgroup$ – fkraiem Nov 7 '17 at 5:35
  • $\begingroup$ @fkraiem thanks for the advice, you're right that asking about course notes would be better directed at the teacher writing them, but all I have access to is the textbook the notes are based off, Foundations of Crypto, which doesn't offer information on the equivalency of semantic security and indistinguishability. If you have something to add to K.D.'s answer, or an interpretation of your own it would be much appreciated. $\endgroup$ – z.karl Nov 7 '17 at 20:08
3
$\begingroup$

The definition of semantic security has its origins in the definition of perfect security, where the adversary's information about the message is the same after seeing the ciphertext. Semantic security is exactly the same thing in a computational setting: the adversary's "practically available" information about the message is the same after seeing the ciphertext.

This is formalised by simplifying the problem: the adversary chooses an "interesting" predicate $f$ on the message space and a way to choose messages such that the predicate holds with probability $1/2$. Then we must prove that the adversary cannot determine the value of the predicate with probability significantly different from $1/2$. (You can define a variant of perfect security in exactly the same way.)

Then it turns out that there is a simpler notion - indistinguishability - that is equivalent to semantic security. This notion is easier to work with, so everyone uses that one, to the extent that semantic security is often identified with indistinguishability.

$\endgroup$
  • $\begingroup$ thanks for the response, it seems I might not understand the definition of an "interesting predicate" because if the adversary chooses the predicate wouldn't he/she be able to determine its value on any input (i.e. with probability 1)? $\endgroup$ – z.karl Nov 7 '17 at 19:58
  • $\begingroup$ The situation is that the adversary sees an encryption of an unknown message, and the message must be chosen in such a way that the value of the predicate is non-obvious (probability 1/2). So yes, the adversary chooses the "interesting predicate", but subject to rules disallowing trivial "attacks". $\endgroup$ – K.G. Nov 8 '17 at 12:00

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.