6
$\begingroup$

Consider an encryption scheme $(Gen,Enc,Dec)$ where $Gen$ is the key generation algorithm, $Enc$ is the encryption algorithm, where $c \leftarrow Enc_{k}(m) $ is taken to mean that the message $m$ in some message space $M$ encrypted with a key $k$ generated from some keyspace $K$ using $Gen$ produces the ciphertext $c$ which belongs to some cipherspace $C$, and where $Dec_{k}(c) = m$ is the decryption algorithm which is always deterministic.

In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic?

i.e. is it impossible that there exist two different ciphertexts $c_{1},c_{2} \in C$ that are both produced by encrypting the same (message, key) pair? It seems once you restrict the three spaces to have equal cardinality, the encryption algorithm must be deterministic, but I cannot seem to prove this formally.

$\endgroup$
8
$\begingroup$

In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic

Actually, the standard definition doesn't actually imply that. It is necessary that $|K| \ge |M|$ and $|K| \ge |C|$, however in neither case does equality have to hold.

In any case, I'll proceed with the assumption that we have $|M| = |C|$ (the length of the key turns out not to matter for your question)

Does this imply that $Enc$ is deterministic?

Yes; the pigeon-hole principal is your friend.

Consider any fixed key $k$, and all plaintexts of length $n$ (there are $2^n$ of them). If you encrypt any one of them with the key, it will result in a ciphertext of length $n$ (and, again, there are $2^n$ possible ciphertexts).

We assume that the encryption process is invertible (that is, $Dec_k(Enc_k(m)) = m$ for any $m$), and so two different plaintexts must result in different ciphertexts.

There are $2^n$ plaintexts mapping to $2^n$ ciphertexts, and so each plaintext must map to precisely one ciphertext (pigeon-hole principle; if there was a plaintext that could map to two different ciphertexts, there must be a plaintext that doesn't map to any, and we assume that doesn't happen).

Hence, the encryption for any specific key is deterministic; that means that encryption for all keys is deterministic.

$\endgroup$
  • 2
    $\begingroup$ It's also a nice way to see clearly that for perfect secrecy, the strength of the scheme comes exclusively from the randomness in the key. This then supports the logical foundation of Kerchoff's principle. $\endgroup$ – kodlu Feb 13 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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