40
$\begingroup$

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.

$\endgroup$

8 Answers 8

29
$\begingroup$

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 seminal 1984 paper of 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 $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ 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.

$\endgroup$
8
$\begingroup$

Perfect Secrecy essentially means these notions:

  1. $P(M=m|C=c) = P(M=m)$ i.e. seeing a ciphertext doesn't give you any extra information about the plaintext. The probability of seeing a message $m$ after the ciphertext has been observed is the same as the probability of the message without the ciphertext.

  2. $P(C=c|M=m_0) = P(C=c|M=m_1)$ i.e. the probability of ciphertext $c$ is equally likely for 2 different messages.

  3. The key is as long as the message and a key should be used uniquely with a probability $1/|K|$ where $|K|$ is the key space.

$\endgroup$
1
  • $\begingroup$ Is property 1 and 2 equivalent? Or is property 1 an implication of property 2? $\endgroup$
    – thyu
    Jan 21, 2022 at 7:34
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$
    – Thomas
    Sep 28, 2012 at 3:54
  • $\begingroup$ 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. $\endgroup$
    – Emyr
    Sep 28, 2012 at 4:11
  • $\begingroup$ @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. $\endgroup$ Sep 28, 2012 at 7:31
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Important note:

  • One-time pad does not "not give any information about the content of the message". This is a fallacy. It still does reveal information. For example, simply knowing that there exists an exchanged message does tell us some information.

  • If the assumptions of the one-time pad are satisfied, what we will have is an encryption method that minimizes the leaked information. This is different than "giving no information" or "zero information".

Please read further on information theory: https://en.wikipedia.org/wiki/Information_theory

$\endgroup$
6
  • 1
    $\begingroup$ Message length (and thus its existence) is usually assumed to be public, because any finite cipher leaks some information about it. OTP hides everything else about the message content. $\endgroup$
    – otus
    Jan 18, 2016 at 16:01
  • 1
    $\begingroup$ Having something "usually assumed" does not eliminate the fact that as such does reveal some information that is greater than 0 bits. $\endgroup$
    – caveman
    Jan 18, 2016 at 23:01
  • 2
    $\begingroup$ If doesn't reveal information if you already know it. However, yes, it is a caveat that is sometimes important to take into account. $\endgroup$
    – otus
    Jan 19, 2016 at 6:57
  • $\begingroup$ Of course, if we know the content, then message's entropy = 0 bits and no information can be gained by doing anything. However, we are discussing the case when the message is "unknown". It is an information-theoritic fact that revealing a message's length does reveal some information that is greater than 0 bits. It is a tiny amount in most cases, but it is greater than 0 nonetheless. The only case when revealing a message's length doesn't reveal information is when all messages in the world are of a constant length (which isn't), therefore reveals. $\endgroup$
    – caveman
    Jan 19, 2016 at 11:01
  • $\begingroup$ What I meant is that the premise is that the attacker knows the message length, but nothing else about its content. (Not that they'd know the content already.) In that case OTP does not give away any additional information about the content. Sometimes that premise is not reasonable, but it is the standard one, because nothing stronger is possible in general. $\endgroup$
    – otus
    Jan 19, 2016 at 15:31
-1
$\begingroup$

In perfect secrecy, one cannot derive any pattern or connection between cipher text and plaintext when provided with the cipher text data.

One Time Pad (OTP) offers such perfect secrecy of message. Where the key size is equal to the plaintext. This results in perfect secrecy.

However this solution is not feasible in real world because:

  1. space limitation : 1gb plaintext == 1 gb key
  2. key sharing : key needs to be shared in person or very trusty courier
$\endgroup$
2
  • $\begingroup$ You probably did not mean "this solution is feasible", did you? $\endgroup$
    – otus
    Jan 3, 2018 at 11:23
  • $\begingroup$ Still voted down as 1. the first part of the answer doesn't contain anything not already posted in other answers and 2. the second part is wrong as OTP is certainly used in specific usage scenarios - not feasible is certainly too strongly worded (I've been criticized for even less strong wording in the past, this is not a personal attack, I've sinned as well ;) ). $\endgroup$ Jan 3, 2018 at 13:09
-3
$\begingroup$

Put quite simply: It means it's impossible to tell if and when the message has been cracked or not.

So you can crack the message but you will never know if it is cracked or not.

$\endgroup$

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