I read some similar questions like Simply put, what does “perfect secrecy” mean? (This one defines perfect secrecy as ciphertext conveys no information about the content of the plaintext.

Now, problem 2.3 on this assignment asks:

show that perfect secrecy of $(GEN, ENC, DEC)$ implies $$\Pr [ENC_k(m) = c] = \Pr [ENC_k(m') = c]$$

Isn't the above equation saying that ciphertext $c$ gives no information whether it's $m$ or $m'$?

What is the exact definition of perfect secrecy then?

P.S. the assignment link above contains the solution. In the solution, I don't understand where the definition of perfect secrecy is used, nor what it is.

  • 1
    The perfect secrecy definition is short, given a ciphertext, it should not reveal any information about the plaintext itself. The above says that; given a ciphertext the probability that the plaintext is $m$ or $m'$ are equal. – kelalaka Oct 22 at 7:16

Information-theoretic security (= perfect secrecy) is a cryptosystem whose security derives purely from information theory, so that the system cannot be broken even if the adversary has unlimited computing power. The adversary does not have enough information to break the encryption, and so the cryptosystem is considered cryptanalytically unbreakable.

If we take the One-time pad as example:

The problem of decrypting a ciphertext that has been encrypted using OTP is illustrated in this example. It is possible to decrypt the ciphertext to any value of the same length. You can only know the true plaintext if you have the key.

There are different cryptosystems available that are believed to be extremly secure even though they don't fall in the category of "perfect secrecy", for example AES:

If an attacker has unlimited computing power then AES wouldn't be really a problem to decrypt, because AES's security relies on the "problem" that you had to try every key until you have found the correct one (brute-force attack) and not that a given ciphertext can be decrypted to any value of the same length like OTP.

  • 2
    I was about to ask "If you are attempting to brute force AES, how do you tell if you have found the right key?" The answer is that if your candidate key produces a meaningful message for two blocks, then (with overwhelming probability), it is the correct key. – Martin Bonner Oct 22 at 9:12

The Lindell and Katz, in their book, give the definition as follows;

An encryption scheme $(Gen,Enc,Dec)$ over a message space $\mathcal{M}$ is perfectly secret if for every probability distribution of over $\mathcal{M}$, every every message $m\in\mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which $Pr[C=c]>0$;

$$Pr[M=m|C=c] = Pr[M=m]$$

We can view this definition as the distribution over messages and ciphertext are independent.


The proof used this definition and the equivalent definition of perfect secrecy

$Pr[C=c|M=m] = Pr[C=c]$

and, this can be said, the ciphertext reveals no information about the plaintext other than the size.


On your proof;

On the third P, on the numerator and denominator;

$Pr[Enc_k(m_1)=c] = Pr[Enc_k(M) =c | M=m_1]$

Also known as unconditional security, observation of the ciphertext provides no information about the plaintext and vice versa.

$Pr(c/m) = Pr(c)$ $\&$ $Pr(m/c) = Pr(m)$

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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