W
wangyong
Guest
Analysis on the Information-Theoretic Proof about Perfect Secrecy of
OTP
Yong WANG
(School of Computer and Control, GuiLin University Of Electronic
Technology, Guilin City, Guangxi Province, China, 541004)
hellowy@126.com
Abstract: This paper analyzes the information-theoretic proofs about
perfect secrecy of OPT and points out that the information-theoretic
proof is not proper to prove OPT is perfectly secure. The sticking
point lies in the values under different conditions are confused and
the condition that ciphertext is a fixed value is not conscious. It is
also pointed out that the similar mistake may take place when
information theory is used to prove other propositions.
Keywords: one-time-pad; cryptography; perfect secrecy; information
theory; probability theory
1. Introduction
Shannon put forward the concept of perfect secrecy and proved that one-
time-pad (one-time system, OTP) was perfectly secure [1, 2]. For a
long time, OPT has been thought to be unbroken and is still used to
encrypt high security information. In literature [3], example was
given to prove that OPT was not perfectly secure. In literature [4],
detailed analyses about the mistake of Shannon's proof were given. It
was proven that more requirements were needed for OTP to be perfectly
secure and homophonic substitution could make OTP approach perfect
secrecy [5]. Literature [6] analyzed the problem and gave ways to
disguise the length of plaintext. In literature [7], the cryptanalysis
method based on probability was presented, and the method was used to
attack one-time-pad. Literature [4] considered an especially
understanding following which OTP could be thought perfectly secure if
some added conditions were satisfied. In literature [8], the
especially understanding was confirmed not to be Shannon's notion. We
know Shannon first proved that OTP was perfectly secure, but his proof
is very simple. Detailed proofs about perfect secrecy of OTP were
given by later scholars who used Shannon's proof for reference. The
detailed proofs were found to be wrong for they took different
conditions as the same [9]. This paper analyzes the mistake of
information-theoric proof about perfect secrecy of OPT.
2. The information-theoric proof about perfect secrecy of OTP
A majority of proofs about perfect secrecy of OPT are based on
probability theory, including Shannon's, but some proofs are based on
information theory [10, 11]. The information-theoric proofs can be
found from textbooks and lectures. Some of the information-theoric
proofs are not very clear-cut. The following is a representative
proof.
Theorem: The OPT is a perfect cipher for every PM.
Proof: Suppose M, C and K are plaintext, ciphertext and key of one-
time pad respectively.
When given the plaintext and the ciphertext, then the key is uniquely
determined, i.e., H(K|MC) = 0. Similarly, we have H(M|CK) = 0 and H(C|
MK) = 0. Suppose N is the block length, then we can get H(K) = N. As M
and K statistically independent, so we have I(M; K) = 0.
I(K; C|M) = H(K)ŁI(M; K)ŁH(K|CM) = N,
So I(M; C) = 0 holds because H(Y) ĄÜlog2 |Y| = N.
OPT is perfect secrecy.
Fig.1 Perfect secrecy of one-time pad
3. Analysis on the proof
The proof is based on information theory, so we should analysis the
problem from the view of information theory. It can be seen from
Shannon's formula and proof that the conditional entropy is gained
from fixed joint probability distributions. The above proof confuses
the probabilities and entropies under different conditions like other
proofs about the perfect secrecy of OPT. As we have pointed out there
were complex and crytic conditions in OTP that influenced the
probability of plaintext, key and ciphertext. The proof did not
realize the crytic condition that ciphertext was a fixed value (even
though unknown) rather than a random variable. One would think it is
not necessary to take that ciphertext was a fixed value (even though
unknown) as a condition. We can see that by the following analysis. In
OPT, when considering the case of encryption, the ciphertext is a
random variable, in that case, the number of the possible values of
cipher is infinite. It is very complex to deal with the probability
distribution and the entropy of ciphertext, but if we set the possible
value of ciphertext as a fixed (certain) value, then the number of the
possible values is finite. When considering the case of intercepting
the ciphertext, the ciphertext is a fixed value, so it is very proper
to set the ciphertext as fixed value. We illustrate to show the
condition that ciphertext is a fixed value influences the probability
distributions of plaintext and key and thus influences the entropies:
The plaintext space, ciphertext space and key space of OPT are all (0,
1) with the keys being equally likely. It is known beforehand that the
prior probability P(M=0) = 0.9 and P(M=1) = 0.1. Then the probability
of plaintext is P(M=0) = 0.9 and P(M=1) = 0.1 under the case of
encryption. When only considering that the ciphertext is fixed (even
though unknown) and all the keys are equally likely, for there is a
one-to-one correspondence between all the plaintexts and keys, so the
probabilities of the corresponding plaintext and key are the same. As
all the keys are equally likely, so all the plaintexts are equally
likely, that is, the probability of plaintext being 1 is 0.5 under
that condition. As the probability distribution obtained above isn't
consistent with the prior probability distribution, when the above
conditions and the prior probability are both considered, the final
probability distribution of plaintext should be a compromise of the
two and unequal to the prior probability distribution. It is similar
to the probability distribution of key when ciphertext as a fixed
value is considered. The probabilities of plaintexts change when the
cipher as a fixed value(even though unknown) is considered, and it is
the same when ciphertext is intercepted, thus OPT is not perfectly
secure as perfect secrecy implies that the posterior probability and
the prior probability of plaintext are the same. We can get different
probability distributions and joint probability distributions of
plaintexts, keys and ciphertexts under the case of encryption and the
case that the ciphertext is a fixed value. Then some of the values of
Fig.1 would be different under the two cases, such as H(M).
The above proof may be correct before the conclusion that OPT is
perfect secrecy is gained if all values such as the entropies,
condition entropies and the joint probability distributions are under
the same case, but we can find that the values relative to M is under
the case of encryption, that is, the case that ciphertext is not fixed
and the values relative to C is obviously under the case of
decryption, that is, the case that ciphertext is intercepted and
fixed, for only under that case can I(M; C) = 0 ensure that OPT is
perfectly secure. All the values in Fig.1 should be under the same
case and the same joint probability distributions. But in the proof,
the values are not under the same case, the covert condition that
ciphertext is fixed is sometimes unconsciously considered and
sometimes ignored. That results in confusion and mistake.
Maybe someone would take the prior probability as the probability
under the consideration that ciphertext is fixed, but we can find from
the proofs about the perfect secrecy of OPT and background that it is
not the view of Shannon. Detailed analysis was given in literature
[8]. The proof analyzed in literature [9] also shows it is not the
view of cryptographists and cryptographic community.
4. Conclusion
This paper gives analysis on the mistake in information-theoric proof
and confirms OPT is not perfect secure. Similar to other proofs, the
mistake lies in the confusion of the different conditions as the same.
Though OPT is not perfectly secure and not completely unimpeachable,
it still has a lot of good statistical properties and can be used in
cases of superior security. The similar mistakes may exist in the
applications of information theory, especially in cryptography. It
should be emphasized that the mistake attributes to the covert
condition and the complexity of the problem, but not the mind of the
famous cryptographist.
Acknowledgements
I would like to take this chance to express my sincere gratitude to
Raymond W. Yeung for pointing out the ref. [11]. My gratitude also
extends to the scholars who gave various opponent views which help me
to give more comprehensive analysis and clearer statement. This work
has been supported by Guangxi Science Foundation under grant 0640171
and Modern Communication National Key Laboratory Foundation under
grant 9140C1101050706.
Reference
[1]. Bruce Schneier, Applied Cryptography Second Edition: protocols,
algorithms, and source code in C[M],John Wiley &Sons,Inc,1996
[2]. C.E.Shannon, Communication Theory of Secrecy Systems [J], Bell
System Technical journal, v.28, n.4, 1949, 656-715.
[3]. Yong WANG, Security of One-time System and New Secure System [J],
Netinfo Security, 2004, (7):41-43
[4]. Yong WANG, Fanglai ZHU, Reconsideration of Perfect Secrecy,
Computer Engineering, 2007, 33Ł¨19ŁŠ
[5]. Yong WANG, Perfect Secrecy and Its Implement [J], Network &
Computer Security,2005(05)
[6]. Yong WANG, Fanglai ZHU, Security Analysis of One-time System and
Its Betterment, Journal of Sichuan University (Engineering Science
Edition), 2007, supp. 39(5):222-225
[7]. Yong WANG, Shengyuan Zhou, On Probability Attack, Information
Security and Communications Privacy, 2007,(8)Łş39Ł40
[8]. Yong WANG, Confirmation of Shannon's Mistake about Perfect
Secrecy of One-time-pad, http://arxiv.org/abs/0709.4420
[9]. Yong WANG, Mistake Analyses on Proof about Perfect Secrecy of One-
time-pad, http://arxiv.org/abs/0709.3334
[10]. Massey, J.L., An introduction to contemporary cryptology,
Proceedings of the IEEE, 1988,76 (5):533 - 549
[11]. Raymond W. Yeung, A First Course in Information Theory,
Springer, 2002: 116
OTP
Yong WANG
(School of Computer and Control, GuiLin University Of Electronic
Technology, Guilin City, Guangxi Province, China, 541004)
hellowy@126.com
Abstract: This paper analyzes the information-theoretic proofs about
perfect secrecy of OPT and points out that the information-theoretic
proof is not proper to prove OPT is perfectly secure. The sticking
point lies in the values under different conditions are confused and
the condition that ciphertext is a fixed value is not conscious. It is
also pointed out that the similar mistake may take place when
information theory is used to prove other propositions.
Keywords: one-time-pad; cryptography; perfect secrecy; information
theory; probability theory
1. Introduction
Shannon put forward the concept of perfect secrecy and proved that one-
time-pad (one-time system, OTP) was perfectly secure [1, 2]. For a
long time, OPT has been thought to be unbroken and is still used to
encrypt high security information. In literature [3], example was
given to prove that OPT was not perfectly secure. In literature [4],
detailed analyses about the mistake of Shannon's proof were given. It
was proven that more requirements were needed for OTP to be perfectly
secure and homophonic substitution could make OTP approach perfect
secrecy [5]. Literature [6] analyzed the problem and gave ways to
disguise the length of plaintext. In literature [7], the cryptanalysis
method based on probability was presented, and the method was used to
attack one-time-pad. Literature [4] considered an especially
understanding following which OTP could be thought perfectly secure if
some added conditions were satisfied. In literature [8], the
especially understanding was confirmed not to be Shannon's notion. We
know Shannon first proved that OTP was perfectly secure, but his proof
is very simple. Detailed proofs about perfect secrecy of OTP were
given by later scholars who used Shannon's proof for reference. The
detailed proofs were found to be wrong for they took different
conditions as the same [9]. This paper analyzes the mistake of
information-theoric proof about perfect secrecy of OPT.
2. The information-theoric proof about perfect secrecy of OTP
A majority of proofs about perfect secrecy of OPT are based on
probability theory, including Shannon's, but some proofs are based on
information theory [10, 11]. The information-theoric proofs can be
found from textbooks and lectures. Some of the information-theoric
proofs are not very clear-cut. The following is a representative
proof.
Theorem: The OPT is a perfect cipher for every PM.
Proof: Suppose M, C and K are plaintext, ciphertext and key of one-
time pad respectively.
When given the plaintext and the ciphertext, then the key is uniquely
determined, i.e., H(K|MC) = 0. Similarly, we have H(M|CK) = 0 and H(C|
MK) = 0. Suppose N is the block length, then we can get H(K) = N. As M
and K statistically independent, so we have I(M; K) = 0.
I(K; C|M) = H(K)ŁI(M; K)ŁH(K|CM) = N,
So I(M; C) = 0 holds because H(Y) ĄÜlog2 |Y| = N.
OPT is perfect secrecy.
Fig.1 Perfect secrecy of one-time pad
3. Analysis on the proof
The proof is based on information theory, so we should analysis the
problem from the view of information theory. It can be seen from
Shannon's formula and proof that the conditional entropy is gained
from fixed joint probability distributions. The above proof confuses
the probabilities and entropies under different conditions like other
proofs about the perfect secrecy of OPT. As we have pointed out there
were complex and crytic conditions in OTP that influenced the
probability of plaintext, key and ciphertext. The proof did not
realize the crytic condition that ciphertext was a fixed value (even
though unknown) rather than a random variable. One would think it is
not necessary to take that ciphertext was a fixed value (even though
unknown) as a condition. We can see that by the following analysis. In
OPT, when considering the case of encryption, the ciphertext is a
random variable, in that case, the number of the possible values of
cipher is infinite. It is very complex to deal with the probability
distribution and the entropy of ciphertext, but if we set the possible
value of ciphertext as a fixed (certain) value, then the number of the
possible values is finite. When considering the case of intercepting
the ciphertext, the ciphertext is a fixed value, so it is very proper
to set the ciphertext as fixed value. We illustrate to show the
condition that ciphertext is a fixed value influences the probability
distributions of plaintext and key and thus influences the entropies:
The plaintext space, ciphertext space and key space of OPT are all (0,
1) with the keys being equally likely. It is known beforehand that the
prior probability P(M=0) = 0.9 and P(M=1) = 0.1. Then the probability
of plaintext is P(M=0) = 0.9 and P(M=1) = 0.1 under the case of
encryption. When only considering that the ciphertext is fixed (even
though unknown) and all the keys are equally likely, for there is a
one-to-one correspondence between all the plaintexts and keys, so the
probabilities of the corresponding plaintext and key are the same. As
all the keys are equally likely, so all the plaintexts are equally
likely, that is, the probability of plaintext being 1 is 0.5 under
that condition. As the probability distribution obtained above isn't
consistent with the prior probability distribution, when the above
conditions and the prior probability are both considered, the final
probability distribution of plaintext should be a compromise of the
two and unequal to the prior probability distribution. It is similar
to the probability distribution of key when ciphertext as a fixed
value is considered. The probabilities of plaintexts change when the
cipher as a fixed value(even though unknown) is considered, and it is
the same when ciphertext is intercepted, thus OPT is not perfectly
secure as perfect secrecy implies that the posterior probability and
the prior probability of plaintext are the same. We can get different
probability distributions and joint probability distributions of
plaintexts, keys and ciphertexts under the case of encryption and the
case that the ciphertext is a fixed value. Then some of the values of
Fig.1 would be different under the two cases, such as H(M).
The above proof may be correct before the conclusion that OPT is
perfect secrecy is gained if all values such as the entropies,
condition entropies and the joint probability distributions are under
the same case, but we can find that the values relative to M is under
the case of encryption, that is, the case that ciphertext is not fixed
and the values relative to C is obviously under the case of
decryption, that is, the case that ciphertext is intercepted and
fixed, for only under that case can I(M; C) = 0 ensure that OPT is
perfectly secure. All the values in Fig.1 should be under the same
case and the same joint probability distributions. But in the proof,
the values are not under the same case, the covert condition that
ciphertext is fixed is sometimes unconsciously considered and
sometimes ignored. That results in confusion and mistake.
Maybe someone would take the prior probability as the probability
under the consideration that ciphertext is fixed, but we can find from
the proofs about the perfect secrecy of OPT and background that it is
not the view of Shannon. Detailed analysis was given in literature
[8]. The proof analyzed in literature [9] also shows it is not the
view of cryptographists and cryptographic community.
4. Conclusion
This paper gives analysis on the mistake in information-theoric proof
and confirms OPT is not perfect secure. Similar to other proofs, the
mistake lies in the confusion of the different conditions as the same.
Though OPT is not perfectly secure and not completely unimpeachable,
it still has a lot of good statistical properties and can be used in
cases of superior security. The similar mistakes may exist in the
applications of information theory, especially in cryptography. It
should be emphasized that the mistake attributes to the covert
condition and the complexity of the problem, but not the mind of the
famous cryptographist.
Acknowledgements
I would like to take this chance to express my sincere gratitude to
Raymond W. Yeung for pointing out the ref. [11]. My gratitude also
extends to the scholars who gave various opponent views which help me
to give more comprehensive analysis and clearer statement. This work
has been supported by Guangxi Science Foundation under grant 0640171
and Modern Communication National Key Laboratory Foundation under
grant 9140C1101050706.
Reference
[1]. Bruce Schneier, Applied Cryptography Second Edition: protocols,
algorithms, and source code in C[M],John Wiley &Sons,Inc,1996
[2]. C.E.Shannon, Communication Theory of Secrecy Systems [J], Bell
System Technical journal, v.28, n.4, 1949, 656-715.
[3]. Yong WANG, Security of One-time System and New Secure System [J],
Netinfo Security, 2004, (7):41-43
[4]. Yong WANG, Fanglai ZHU, Reconsideration of Perfect Secrecy,
Computer Engineering, 2007, 33Ł¨19ŁŠ
[5]. Yong WANG, Perfect Secrecy and Its Implement [J], Network &
Computer Security,2005(05)
[6]. Yong WANG, Fanglai ZHU, Security Analysis of One-time System and
Its Betterment, Journal of Sichuan University (Engineering Science
Edition), 2007, supp. 39(5):222-225
[7]. Yong WANG, Shengyuan Zhou, On Probability Attack, Information
Security and Communications Privacy, 2007,(8)Łş39Ł40
[8]. Yong WANG, Confirmation of Shannon's Mistake about Perfect
Secrecy of One-time-pad, http://arxiv.org/abs/0709.4420
[9]. Yong WANG, Mistake Analyses on Proof about Perfect Secrecy of One-
time-pad, http://arxiv.org/abs/0709.3334
[10]. Massey, J.L., An introduction to contemporary cryptology,
Proceedings of the IEEE, 1988,76 (5):533 - 549
[11]. Raymond W. Yeung, A First Course in Information Theory,
Springer, 2002: 116