9
$\begingroup$

The first question: what is the exact definition of semantically secure? Basically, a cryptosystem is semantically secure if given the public key and the ciphertext, an adversary cannot learn any partial information of the plaintext.

However, the above statement is quite vague to me. For example, what does it mean by "partial information"? And how to prove that a cryptosystem is semantically secure by showing that no partial information can be learned?

I came across some security definitions (such as IND-CPA) that imply semantic security. Then how to show that the above notion of security (e.g. IND-CPA) implies semantic security?

Then the second question: why is semantic security important?

I came across many cryptosystems ( mostly homomorphic encryption schemes) requiring semantic security. So, why is it important?

A counter example is RSA, which is not semantically secure. But it is so widely used.

$\endgroup$
8
  • 2
    $\begingroup$ Hold on there. RSA with a suitable randomized padding function is IND-CPA, which implies that it is semantically secure. In the random oracle model, anyway. Why do you think RSA is not semantically secure? $\endgroup$
    – pg1989
    Commented Oct 28, 2015 at 2:54
  • $\begingroup$ The exact, precise definition of semantic security is pretty rough, and not used that much anymore. IND-CPA is conceptually simpler and equivalent, so people just use that instead. Here's the paper that introduced semantic security: delivery.acm.org/10.1145/810000/802212/… $\endgroup$
    – pg1989
    Commented Oct 28, 2015 at 2:55
  • 3
    $\begingroup$ I would certainly hope that "textbook RSA" is not so widely used... $\endgroup$
    – poncho
    Commented Oct 28, 2015 at 3:20
  • 1
    $\begingroup$ Two questions in one is somewhat problematic. Maybe you could split this? $\endgroup$
    – otus
    Commented Oct 28, 2015 at 5:24
  • 1
    $\begingroup$ This question is closely related to: definition and meaning of semantic security. $\endgroup$
    – fgrieu
    Commented Oct 28, 2015 at 11:48

1 Answer 1

19
$\begingroup$

Let me try to answer your second question, and hopefully shed some light on the first one in doing so.

When we encrypt a message, it's because we want to keep something about that message secret. But what is it that we actually want to protect?

Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON THE 20TH. Is the secret that we wish to protect the name of the agent, or the number of units, or their destination, or their time of departure? All of those? Something else?

When designing a general-purpose encryption scheme, we really cannot know which aspects of the message being encrypted are sensitive. Perhaps the user of the encryption scheme wants to pass off the message above as a routine weather report, and even just allowing the adversary to detect that it's probably not a weather report would count as an unacceptable security failure. We can't know.

What we really want to do is to prevent an adversary (who does not know the key) from learning anything about the message. That is, seeing the ciphertext should not allow the adversary to guess any property of the message with a better chance of success than if they had not seen the ciphertext.*

In other words, what we really want is perfect secrecy. Unfortunately, as Shannon famously proved, perfect secrecy against an arbitrarily capable adversary is impossible to achieve unless the number of possible keys is at least as large as the number of possible (sequences of) messages encrypted with a single key. In practice, this makes true perfect secrecy all but impossible; in particular, as it requires the key to be as long as all the encrypted messages combined, securely distributing the key becomes (almost) as hard as securely distributing the messages would've been in the first place.** This is true for a simple reason: if there are $N$ possible keys, and $M > N$ possible messages, then the attacker can simply try to decrypt the ciphertext with each key, and thereby rule out those (at least) $M - N$ messages that are not the result of decrypting the ciphertext with any key.

However, in practice, even with the most powerful computers available today, no conceivable attacker can test more than, say, 1,000,000,000,000,000,000,000,000 keys, give or take a few factors of 1,000. So if we just make the keyspace reasonably large (and it's not very hard — a random ten-byte key has more possible values than the huge number given above, and we can always add a few more random bytes for good measure), we can hope to make an encryption scheme that, even if theoretically not perfectly secret, is just as good in practice.

Informally speaking, this notion of "practically perfect secrecy" is just what semantic security is. Or, to quote Goldwasser & Micali (1984)***:

"Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext."

The tricky parts of the formal definition (which I'm not going to give here; look it up in your favorite crypto textbook), involving strange theoretical concepts like asymptotic complexity and probabilistic polynomial-time algorithms, comes from trying to formalize this notion in terms of computational complexity theory, without assuming any specific computer hardware or resources for the attacker.

Basically, the reason for doing this (besides just wanting to make use of the toolkit that complexity theory gives us) is that, in practice, we won't really know just how much computing power the attacker can spare to break our encryption. But we do know that, if the only (or at least the biggest) weakness of our encryption is the limited size of the keyspace, then we can increase the number of possible keys exponentially just by making them a little bit longer, with (typically) little impact on encryption speed, whereas the attacker can only increase their computing power linearly by buying more computers (and in general, only polynomially even by switching to a more powerful model of computation).

Thus, if we can prove (at least, subject to some reasonably plausible assumptions) that the difficulty of breaking our encryption (i.e. learning anything about the message) increases faster than any polynomial function of the key size, then we can safely conclude that we can make the encryption practically unbreakable by any given (or conjectured) adversary just by modestly increasing the key length.

*) Note that there's a hidden "gotcha" in the standard definitions of both perfect secrecy and semantic security: the length of the message is assumed to be public knowledge, and thus not necessary to conceal. The reason for this is simple: the only effective way to fully conceal the length of the message is to pad all messages up to the length of the longest possible message; and if the message length is potentially unbounded, even this is impossible. But this "gotcha" is indeed a practical issue, and can easily translate into real, practical attacks, like the CRIME and BREACH attacks against HTTPS.

**) The one practical advantage of OTP-like schemes with perfect secrecy is that you can distribute the keys before you know what you want to encrypt. Even so, secure key generation and distribution is still the hard part of any such scheme.

***) This paper also contains a nice, and in some sense the archetypical, proof of the (conditional) semantic security of the cryptosystem defined in it. If you want to see an example of how such proofs are done, this is not a bad place to start.

$\endgroup$
1
  • $\begingroup$ nice explanation $\endgroup$ Commented May 26, 2017 at 3:16

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.