In my opinion the most important development in cryptography in the last 30 years is the precise definition of semantic security of a cipher. This definition captures the intuitive ideas of Martin Hellman, Ralph Merkle, and Whitfield Diffie of the mid-1970's tying cryptography to complexity theory that gave rise to the new cryptography with all its beautiful applications, multiple use of a key for file encryption, digital signatures, digital payment systems, one-way functions, one-way trapdoor functions, collision-resistant hashing, message digest codes, and so on.

My question is who came up with the precise definition of semantic security? Can you provide the reference to the paper that first defined semantic security precisely?

  • 1
    $\begingroup$ Isn't semantic security just IND-CPA? So why do you mention so many other unrelated areas of cryptography? $\endgroup$ – CodesInChaos Apr 25 '17 at 13:17
  • $\begingroup$ [1], here: en.wikipedia.org/wiki/Semantic_security $\endgroup$ – DrLecter Apr 25 '17 at 13:18
  • $\begingroup$ What research have you done? And reference requests in general are off-topic. $\endgroup$ – tylo Apr 25 '17 at 13:37
  • 3
    $\begingroup$ @tylo Well, as this one can have only one (or maybe two contested) answers I guess the reasons why reference requests are off topic are not directly applicable. $\endgroup$ – Maarten Bodewes Apr 25 '17 at 13:40

The source is the paper by Goldwasser and Micali on probabilistic encryption. The definition is of primary importance even though it is rarely used to prove security of encryption. The reason for this is that indistinguishability is much easier to use. However, indistinguishability is not a good intuitive definition in the sense that it is not immediately clear that it means that nothing can be learned about a plaintext from the ciphertext (beyond the length and any existing a priori knowledge). Since this latter notion is what we want to formalize, and this is exactly what is formalized in the definition of semantic security, this is the definition of encryption. Of course, by its equivalence to indistinguishability we can happily use the simpler definition, with the knowledge that nothing is revealed beyond what is already known (and the length).

  • $\begingroup$ Thank you Yehuda Lindell for your excellent answer. I will look up the Goldwasse & Micali paper $\endgroup$ – Istvan Simon Apr 26 '17 at 10:24

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.