Analysis on the Information-Theoretic Proof about Perfect Secrecy of OTP
wangyong
OTP
Yong WANG
(School of Computer and Control, GuiLin University Of Electronic
Technology ,Guilin City, Guangxi Province , China, 541004)
hel...@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 conditions [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 in OTP
there were complex and crytic conditions 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. If we consider the
ciphertext is fixed(even though unkown), 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
condition 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 unkown) 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.
The above proof is 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 relatived to M is under the case
of encryption, that is, the case that ciphertext is not fixed and the
values relatived 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. The mistake similar to other
proofs 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 problems may exist in the
applications of information theory.
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
Phil Carmody
> not the view of Shannon. Detailed analysis was given in literature
> [8]. The proof analyzed in literature [9] also shows it is not the
> [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
That's not 'literature', that's just more of your own rambling.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
wangyong
wrote:
> wangyong <hell...@126.com> writes:
> > not the view of Shannon. Detailed analysis was given in literature
> > [8]. The proof analyzed in literature [9] also shows it is not the
> ...
> > [8]. Yong WANG, Confirmation of Shannon's Mistake about Perfect
> > [9]. Yong WANG, Mistake Analyses on Proof about Perfect Secrecy of One-
>
> That's not 'literature', that's just more of your own rambling.
>
> Phil
> --
> Dear aunt, let's set so double the killer delete select all.
> -- Microsoft voice recognition live demonstration
That's not 'literature', that's just more of your own rambling.
--------------no other people doubt OPT ecept me.
rossum
Point of clarification. Does this mean "I am the only person who
doubts the OTP" or does it mean "I am just one of a number of people
who doubt the OTP". As written it could mean either depending on
whether your initial "no" refers to Phil's post or to "other people".
rossum
Phil Carmody
Yes, yes, the whole world's mad, and you're the only sane one.
Good luck with your OPTs.
Wheeeeee....
What's that sound?
*PLONK*
Ah, that's the sound of you landing at the bottom of the killfile.
wangyong
Good luck with your OPTs.
Wheeeeee....
What's that sound?
*PLONK*
Ah, that's the sound of you landing at the bottom of the killfile.
Phil
-----------------------you are unreasonable.
If I am right, what can you do?
wangyong
> On Tue, 23 Oct 2007 01:54:24 -0700, wangyong <hell...@126.com> wrote:
> >On 10 22 , 6 ±56· , Phil Carmody <thefatphil_demun...@yahoo.co.uk>
------------------------------------as we find, I am the only person
who doubts the OTP" or does it mean .
If you find other ,tell me
Peter Pearson
> If I am right, what can you do?
If you are right, you can accept my offer to help you
demonstrate a weakness in the One-Time Pad, said offer made
Sun, 21 Oct 2007 18:20:45 -0000
in post <13hn63t...@news.supernews.com>.
Sci.crypt occasionally gets posts from people who claim to
have discovered wonderful ways to factor huge numbers, but
who never actually factor huge numbers. If you don't
want to be classified as that kind of nut case, you need
to change your strategy.
--
To email me, substitute nowhere->spamcop, invalid->net.
wangyong
demonstrate a weakness in the One-Time Pad, said offer made
-----------you can introduce yourself.
My paper is not windbaggary, there is analysis about the mistake.
What can you help me?
Peter Pearson
[excertping from a previous post from me:]
> If you are right, you can accept my offer to help you
> demonstrate a weakness in the One-Time Pad, said offer made
[then proceeding:]
>
> -----------you can introduce yourself.
> My paper is not windbaggary, there is analysis about the mistake.
Maybe. But every crackpot inventor of a magical
factorization algorithm similarly insists on discussing his
algorithm, rather than demonstrating it. The fact that he
wants the community to spend a huge amount of their time on
the difficult job of proof-reading his opaque ramblings,
rather than spending his own time to produce a simple
demonstration, suggests either a poor sense of economics or
a lack of confidence in his supposed results.
> What can you help me?
Why did you cut off the part of my previous post in which
I identified the message containing the specifics of my offer?
If you can't take the time to consider and respond to that
offer, then I can do nothing to help you.
wangyong
> demonstrate a weakness in the One-Time Pad, said offer made
[then proceeding:]
> -----------you can introduce yourself.
> My paper is not windbaggary, there is analysis about the mistake.
Maybe. But every crackpot inventor of a magical
factorization algorithm similarly insists on discussing his
algorithm, rather than demonstrating it. The fact that he
wants the community to spend a huge amount of their time on
the difficult job of proof-reading his opaque ramblings,
rather than spending his own time to produce a simple
demonstration, suggests either a poor sense of economics or
a lack of confidence in his supposed results.
---your suggestion? It is not so hard to understand my analysis.
> What can you help me?
Why did you cut off the part of my previous post in which
I identified the message containing the specifics of my offer?
If you can't take the time to consider and respond to that
offer, then I can do nothing to help you.
-----------------------you avoid the answer and seem windbaggary, I
just ask you what to see whether you are windbaggary. If i am wrong, I
would not need your help.
--