Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

Informally,if you intercept a cipher-text from a perfectly secure encryption system, you can find a key that causes that cipher-text to decrypt to any message you want ( of the correct length). So without knowing which key the author actually picked, you never learn anything about the message. This holds even if you try every possible key (because all keys decrypt the cipher-text to a possibly valid message)

share|improve this answer
    
Note this property can only be satisfied if the key space is at least as large as the plaintext space (therefore all modern ciphers except the OTP automatically fail to provide perfect secrecy) –  Thomas Sep 28 '12 at 3:54
    
Thank you! I have a clear idea of what it is now. So if in a certain transposition cipher, each of the blocks of plaintext are assigned to a completely random key... does this achieve perfect secrecy? It would seem the case since you can't possibly learn anything from it with just the ciphertext... and yet, it's different than the one-time pad because of the lack of xor, so it "can't" have perfect secrecy, right? I apologize if I should have made another question instead. –  Emyr Sep 28 '12 at 4:11
    
@Emyr: In a transposition cipher (at least, as I understand the term), no key can map '1111' to '0000', thus when receiving the 0000 ciphertext we know that 1111 wasn't the plain text. So, this can't be a perfect cipher. –  Paŭlo Ebermann Sep 28 '12 at 7:31

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is plaintext to encrypt. In terms of probabilities, it means that the probability distribution of the possible plaintexts is independent of the ciphertext.

We contrast this with semantic security, which I define by quoting the seminar 1984 paper by Goldwasser&Micali:

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

For two examples, I quote my answer to this related question:

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (eg by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.

To illustrate this, consider what happens if one tries to brute force OTP? Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the appropriate plaintext until every key has been tested. Supposing the message was b bits long, this would leave him with 2b possible keys, each of which would generate a unique plaintext, making 2b plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to ever possible bit-string of length b. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0,1,2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.

Most cryptographic methods we use now are computationally secure. There are lots of different ways to do this, and I'll just sketch at a few of them. We might come up with a reduction to a problem conjectured to be hard (eg the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve [hard-problem]", meaning our problem is at least a difficult to solve as [hard-problem]. So, if the problem is indeed hard to solve, so must cracking our encryption be.

share|improve this answer

Perfect secrecy, in the simplest terms, is data that is completely, entirely patternless. Yet, inside of it there is still your secret. ArtofTheProblem offers a good simple explanation.

share|improve this 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.