3
$\begingroup$

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.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
3
$\begingroup$

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]$

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Martin Bonner supports Monica
    Commented Oct 22, 2018 at 9:12
2
$\begingroup$

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)$

Improve this answer
$\endgroup$

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.