Analyses on the Origins of Shannon's Blemish about OTP
hel...@126.com
Yong WANG
(School of Computer and Control, GuiLin University Of Electronic
Technology ,Guilin City, Guangxi Province , China, 541004)
hel...@126.com
Abstract: This paper further analyzes the origin of Shannon's proof
that one-time-pad is perfectly secure based on the prior analyses. The
limitations of information theory and probability theory are analyzed.
The key lies in that the two theories take probability as fixed value
and the conditions are not carefully recognized. It is pointed out
they are the origins of the blemish.
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. It
was pointed out that the conditions in OPT could not coexist, when all
the conditions were considered, some of the conditions must change, so
it was not proper to use these conditions when computing the final
posterior probability. The above works provoked extensive debates, so
the problem and its origins should be further analyzed in detail.
2. Debate and Analysis on Perfect Secrecy of OTP
As the works relate to Shannon's mistakes, our analyses should be
prudent and long-tested. We have sent the papers to a lot of scholars
and released some of the papers in the internet, and discussed the
problem with some scholars, carefully analyzed all the opposite views
and replied all of them. Some opposite views owed to misapprehend my
papers, such as confusion of proof and reduction to absurdity,
confusion of my conclusion and Shannon's conclusion, taking the
probability when only considering partial conditions as the posterior
probability. Even some observers are of demoralization, or. They gave
some unreasonable and self-contradictory reasons with a precondition
that I must promise to withdraw my claims with distrustful motive as I
yearned for detailed opposite views. Some opposite views cited the
proofs about perfect secrecy of OTP. It was found the proofs were
largely identical but with minor differences and were wrong for they
took different conditions as the same conditions [9].
There is a kind of opposite view that directly and erroneously
believes that the probability is unchanged, that is to say, since
plaintexts having had a prior probability distribution, its
probability distribution changes not any longer. it is proved that the
statement would bring about contradiction finally when ciphertext as a
fixed value and equiprobable keys are considered, and that is also
inconsistent with Shannon argumentation for he got the result that
posterior probability is equiprobable[2]. But there is still necessary
for in-depth analyses on the problem.
Firstly, if this argument is proved to be established, we do not have
to prove and can directly get the conclusion that after the ciphertext
is intercepted the posterior probability of each plaintext is equal to
its prior probability for the probability unchanges. Namely the
cryptosystem is automatically perfectly secure.
Secondly, we can also understand it from the view of the probability.
Because the prior probability we call P(x) is gained from the
condition when only the context of communications is known, and
subsequently when gaining the ciphertext and cryptography interrelated
conditions we call all of them as y, the final probability can be seen
as conditional probability P (x | y), the final conditional
probability is not the same as prior probability unless the two events
are independent. It seems Shannon have proven that two events are
independent. But Shannon only took the value of ciphertext as y and
ignored the existence of the condition that ciphertext is a fixed
value, but not a random variable. It is just this condition that
influences the probabilities of plaintexts in company with the
cryptosystem.
Thirdly, our knowledge to events is often unreliable and incomplete.
Although sometimes the event is certain, if our knowledge to the event
is incomplete, we may get random results [9]. For example, it is
certain whether it rained or not in some place yesterday, but when we
do not hold complete conditions and information about that, we can
only get randomly uncertain result. The result cannot be taken as the
probability of rain yesterday. Strictly speaking, it should be taken
as the probability of rain under all the grasped conditions and
information. As a stopgap, we expediently take the probability as the
probability of rain yesterday for the moment when no more information
is given. The probability under this condition is seldom equal to the
probability under that condition. In the case of OTP, based on
communication contexts, we can gain a prior probability distribution
of the plaintexts. As we have no further understanding and no further
related information about the plaintext, we have to use the prior
probability distribution for the moment [10]. After gaining the
ciphertext, we can try to get more information according to the
ciphertext and probability distribution of keys. At that time the
information is still incomplete, but cryptanalyst will not abandon the
use of such information and make full use of such information and
conditions to obtain more reliable probability. When only considering
that the ciphertext is given, there is a one-to-one correspondence
between all the keys and plaintexts and all keys are equally likely,
we can educe that the plaintexts are equally likely. That is
inconsistent with the prior probability and hence the fusion and
compromise of the probabilities is needed. The compromise probability
may be more perfect and reliable, but it is not equal to the prior
probability.
Fourthly, we can illustrate the problem that we can get different
probabilities under different conditions and the probability of an
event changes with the corresponding conditions from a new
perspective, we want to determine the probability of an event m in the
situation that certain conditions occur together. These conditions may
be relevant or irrelevant with the probability. We can select all of
the influencing conditions; assume to be c1, c2... cn. We can assume
that the probability can be determined by the n influencing conditions
c1, c2... cn, then probability can be expressed as
P(m)＝f（c1, c2, ..., cn）
For a sophisticated case, P(m) may be a random variable. In order to
be convenient for the analysis, we consider the value of the above
function is fixed. When certain conditions are still unknown, the
probability P(m) itself is not fixed, we may get the expectation of
P(m) under the imperfect conditions. But the expectation (probability)
gained from the imperfect conditions is not reliable and seldom equal
to the probability gained from the complete conditions. The more
conditions we know, the more reliable the corresponding probability
is. Due to the imperfect conditions, the probability gained from those
conditions does not mean the probability gained from complete
conditions. And therefore the conflicts under these imperfect
conditions are understandable that they do not perfectly represent the
probability under complete conditions. In fact the conditions are
usually imperfect in probability theory. It is not strict to take the
probability in that case as the probability in complete conditions. In
practice, it is prone to ignore the existence of unequal substitution,
thereby confusion and absurdity may appear.
Another kind of opposite views argued the plaintext and ciphertext in
the OPT are completely independent, and thus OPT is perfectly secure.
It argued that any ciphertext might be regarded as the same for OTP
and then the plaintext and ciphertext in the OPT are completely
independent. The independence can be explained from the angles of
probability theory and usual understanding. The kind of opposite views
confused the angles of probability theory and usual understanding.
>From the angle of probability theory, the plaintext and ciphertext in
the OPT are completely independent, and thus OPT is perfectly secure.
But from the angle of probability theory, that any ciphertext may be
regarded as the same for OTP does not mean the plaintext and
ciphertext in the OPT are completely independent as probability theory
gives a strict definition of independent. The above conclusion may be
correct when it is considered from the angle of usual understanding.
For example, any ciphertext changes the probability of plaintext in
the same way. In this case, any ciphertext may be regarded as the same
for the gives the same influence on the probability of plaintext. But
this does not mean perfect secrecy for the probability changes. It is
the same in OTP.
3. Origin analyses of probability theory and information theory
The mistakes in Shannon's proof have certain relations with the
limitations of probability theory. Moreover, Shannon did not realize
the limitations of probability theory when studying his information
theory.
>From the view of probability theory, he realized the random
uncertainty of event, and expressed this uncertainty with probability,
but ignored the random uncertainty of probability itself. Though it
was not directly stated that the probability was a fixed value [11].
But it can be seen from a lot of formals in probability theory and
information theory that probability is always taken as a fixed value,
otherwise, the formals may be impossible to compute, for example, the
formal of entropy would be impossible to compute if probability is a
random variable. The case that probability is a random variable is
universal as fixed value is only a special case of random variable.
For instance, the probability that comes from the incomplete or
unreliable conditions has more than one possible value, it is not
fixed, so the probability is a random variable and has random
uncertainty correspondingly [10]. The expectation of the probability
as a random variable is a simple static token, with merely local
significance, but its concrete probability distribution and its
concentrative degree are of great significance to the compromise of
probabilities and and the reliability of information. As probability
is always treated as fixed value in probability theory and information
theory, it caused the limitation of the two theories that they can not
solve the problems when the probability is a random variable. It also
caused a few scholars to believe that once the probability was given,
the probability would not change any more for the probability is
fixed. Generally speaking, for fixed probability, neither the analysis
of the reliability of information itself nor the fusion of unreliable
and incomplete information is doable. Most information in reality is
not absolutely reliable or perfect, we should compromise and fuse
different information. As information is expressed by probability, so
information is unchangeable if the corresponding probability is
considered as fixed value. To take probability as a fixed value is one
of the fundamental reasons why information theory can not be used to
research the reliability of information itself and information fusion,
while it can merely be used to research authentic communication.
We usually get information from the imperfect conditions we know and
take information under imperfect conditions as information under
complete conditions as a stopgap. When imperfect information under
imperfect conditions is taken as information under complete
conditions, the information is unreliable for the information is not
the same as the information under complete conditions, so the
imperfect information can be taken as unreliable information. When
utterly knowing nothing about the event, we cannot know how many
possible random values there are, not to mention the corresponding
probabilities of the possible values. Therefore, the prior probability
we obtained is based on the known conditions and and it is also a
conditional probability. Therefore the information and probability is
relative to our known conditions. But the unequal substitution is
never pointed out directly in probability theory and information
theory. In practice, it is prone to ignore the existence of the
unequal substitution of the imperfect one and the perfect one, thereby
confusion and absurdity may appear. When a lot of conditions that
influence the probability of an event are considered and the
conditions are parallel but not in series, there may be more than one
prior probability or posterior probability according to nowadays
probability theory. For example, some conditions can influence birth
gender of baby. Under condition A, the probability of male baby P(M︱A)
is c and under condition B, the probability of male baby P(M︱B) is d.
Now a question occurs: if both of the above conditions exist, how can
we gain the probability of male baby P(M︱A, B)? Other than problems in
nowadays probability theory, in this case the two conditions are
parallel for when A occurs, B is not considered and when B occurs, A
is not considered. and we do not know the conditional probability P(A︱
B) or P(B︱A). It is the same in the example of one-time pad, if the
final posterior probability is considered, it is the compromise of the
two probabilities under two conditions. The problem of compromise is
not settled in nowadays probability theory and is very complex. When
there are some parallel conditions, there may be more than one
probability and the probabilities may be conflicting. The uncertainty
theory and information fusion theory attempts to solve the problem,
but they are not strict and their algorithms are approximate but not
accurate algorithms, what's more, there are absurdities in some
algorithms. It is necessary to develop relevant accurate theory from
the perspective of probability theory.
In addition, probability theory does not realize the complexity of the
conditions, some conditions may be cryptic and interactional, so to
carefully recognize and strictly distinguish each condition is
necessary, and it should be realized that the probabilities under
different conditions are not the same, for example, the probability is
very easy to calculate when only condition x or y exists , but when
both the condition x and y coexist , the calculation of the
corresponding probability is difficult. This causes difficulty in
using the ready-made formulas of probability theory when conditional
probability is unknown. In the information theory, these problems
issues are not under consideration as well, so information theory can
not be used in some fields such as information fusion and artificial
intelligence. Due to the problem, Shannon failed to discover and
distinguish these different conditions in his proof [10].
>From Shannon's result PE(M) =1/n in his example, we can find Shannon
confused the posterior probability under all the conditions with the
imperfect probability when only the ciphertext and OPT were considered
(the prior probability as a condition was not considered, otherwise,
the result is impossible unless the prior probability P(M) =1/n
uncommonly happens). That may owe to the limitation of probability
theory that ignore the discrimination and recognition of different
conditions.
In the case of OTP, the uncertainty of plaintext is increased after
the compromise and fusion, but the conditional entropy was not
increased in information theory. It seems to be contradictory with
information theory. In fact, Shannon's conditional entropy is just one
kind of weighted average of a series of conditional entropies. It was
pointed out that Shannon's conclusion is not absolutely correct [12].
>From the above examples, we can find that the reliability and
completeness of the information are not considered in information
theory. However, the reliability and completeness are very important.
Information is valuable only when it is reliable at a certain extent,
otherwise it would be worthless. However, the relevant theories about
information reliability and completeness (such as uncertainty theory,
information fusion) are far from perfect and systematic, and there are
only approximate algorithms. Some of them even have absurdities.
Probability theory lags behind the study of the relevant theories yet.
4. Conclusion
This paper gives further and profound analyses on the blemish in
Shannon's proof and points out the root. Also, the debates about the
problem with a few experts and scholars are analyzed. This means that
the OPT is not as commonly thought to be perfectly secure and
unbreakable. However, it still has good statistical property and
superior security. At the same time, it analyzes the origin of
Shannon's mistakes in probability theory and information theory for
the probability in the two theories is always taken as fixed value,
but not random variable. This also provides a good direction for the
development of the probability theory and information theory and helps
the two theories to expand so as to solve more problems in reality.
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]. Yong WANG, On Relativity of Probability, www.paper.edu.cn, Aug,
27, 2007.
[11]. Yong WANG, On Relativity of Information, presented at First
National Conference on Social Information Science in 2007, Wuhan,
China, 2007.
[12]. Yong Wang. Question on Conditional Entropy. arXiv:
http://arxiv.org/pdf/0708.3127.
The Project Supported by Guangxi Science Foundation (0640171) and
Modern Communication National Key Laboratory Foundation (No.
9140C1101050706)
Biography：
Yong WANG (1977－) Tianmen city, Hubei province, Male, Master of
cryptography, Research fields: cryptography, information security,
generalized information theory, quantum information technology. GuiLin
University of Electronic Technology, Guilin, Guangxi, 541004 E-mail:
hel...@126.com wang197...@sohu.com
Mobile 13978357217 fax: (86)7735601330(office)
School of Computer and Control, GuiLin University Of Electronic
Technology, Guilin City, Guangxi Province, China, 541004
Guy Macon
hel...@126.com wrote:
Translation: various exerts have examined Yong Wang's arguments
and have not been convinced by them. From this, Yong Wang concludes
that he and he alone is right, everybody else is wrong, and that
all the experts are too stupid to understand his arguments.
--
Guy Macon
<http://www.guymacon.com/>
wangyong
> Translation: various exerts have examined Yong Wang's arguments
> and have not been convinced by them. From this, Yong Wang concludes
> that he and he alone is right, everybody else is wrong, and that
> all the experts are too stupid to understand his arguments.
>
> --
> Guy Macon
>
Translation: various exerts have examined Yong Wang's arguments
and have not been convinced by them. From this, Yong Wang concludes
that he and he alone is right, everybody else is wrong, and that
all the experts are too stupid to understand his arguments.
--
===========================
your arguments just prove you are unreasonable and talentless to tell
why I am wrong.
you are too impuissant to give any reason.
wangyong
i do not want any one just windbaggary.
tell the reason.