I would like to ask for a clear (but maybe not so deep) explanation of what the
ID: 650449 • Letter: I
Question
I would like to ask for a clear (but maybe not so deep) explanation of what the term "perfect secrecy" means.
As far as I have researched and understood, it has to do with probabilities of assuming that a certain variable will be the key for a certain cipher text. And unless I'm confusing some concepts, the one-time pad is the only cipher known to have perfect secrecy, since no amount of resources would be enough to break it.
My notions of probability are kind of weak, which is why I don't understand most documents that speak of it.
Explanation / Answer
Perfect secrecy is the notion that, given an encrypted message (or ciphertext) from a perfectly secure encryption system (or cipher), absolutely nothing will be revealed about the unencrypted message (or plaintext) by the ciphertext.
A perfectly secret cipher has a couple of other equivalent properties:
+ Even if given a choice of two plaintexts, one the real one, for a ciphertext, you cannot distinguish which plaintext is the real one (perfect message indistinguishability)
+ There is a key that encrypts every possible plaintext to every possible ciphertext (perfect key ambiguity) (* this is true only if the keys used are the same size as the messages)
What perfect secrecy means in practice is that no amount of computation applied to the ciphertext will give you any advantage in knowing anything about the plaintext or key. This is obviously a desirable property of a cipher, and perfectly secret ciphers do exist: e.g. One-time pad.
The downside of perfect secrecy is that it can be shown that no cipher where the keys used are shorter than the plaintext can be perfectly secret, so in effect you've simply changed the problem of transmitting a message securely from the transmission of the plaintext to the transmission of the key. (One-time pad has this problem, and other practical problems as well).
In practice, outside niche applications that can use One-time pad, ciphers tend to have keys much shorter (typically between 128 and a few thousand bits) than the messages we encrypt. These ciphers of course cannot have perfect secrecy (since the key is shorter than the message) and so can (especially when broken) succumb to computational attacks (some practical, some theoretical) that leak information about plaintexts and even keys.
We use the relatively weaker (but still practically very strong) notions of Semantic Security or Ciphertext indistinguishability to evaluate and describe the security of non perfect-secrecy ciphers under various scenarios. The strength of a not-perfectly-secret cipher is generally expressed in terms of the computational complexity (in calculations and/or memory) of the best known attacks that break the cipher.