a r
X
i
v
:q u
a
n
t
为为-
p
h
/
0
鼻翼肥大怎么办
6
3
2
6
3
v
5
2
7
S
山东有什么山
e p
2
6
Quantum Noi Randomized Ciphers Ranjith Nair ∗,Horace P.Yuen,Eric Corndorf,Takami Eguchi,and Prem Kumar Center for Photonic Communication and Computing Department of Electrical Engineering and Computer Science Northwestern University,Evanston,IL 60208February 1,2008PACS:03.67.Hk,42.50.Ar Abstract We review the notion of a classical random cipher and its advantages.We sharpen the usual description of random ciphers to a particular mathematical characterization suggested by the salient feature responsible for their incread curity.We describe a concrete system known as αηand show that it is equivalent to a random cipher in which the required randomization is effected by coherent-state quantum noi.We describe the currently known curity features of αηand similar systems,including lower bounds on the unicity dis-tances against ciphertext-only and known-plaintext attacks.We show how αηud in conjunction with any standard stream cipher such as AES (Advanced Encryption Standard)provides an additional,qualitatively different layer of curity from physical encryption against known-plaintext attacks on the key.We refute some claims in the literature that αηis equivalent to a non-random
stream cipher.
1Introduction
The possibility of achieving greater crecy by introducing additional randomness into the plaintext of a cipher before encryption was known,according to [1],already to Gauss,in the form of the so-called ‘homophonic substitution’.Such a procedure is
an example of a random cipher[1,2].The advantage of a random cipher not prent in standard nonrandom ciphers is that it can provide information-theoretic curity of the key against statistical attacks,and possibly known-plaintext attacks(See Ap-pendix A and also[2]).A somewhat detailed description of the possibilities is one of the goals of this paper.In spite of the potential advantages of random ciphers,a large obstacle in their deployment is the bandwidth expansion,or more accurately data rate reduction,that is needed to operate all previous random ciphers.Also, it is not currently possible to generate true random numbers at speeds high enough for random ciphers to operate at sufficiently high data rates(∼Mbps is the current upper limit for random number generation).The quantum noi in optical coherent-state signals may be utilized for this purpo,and quantum optical effects em to be the only technologically feasible way to generate>Gbps true rand
om numbers.A particular quantum noi-bad random cipher,calledαη,that also does not entail data rate reduction,has already been propod and implemented[3,4]at North-western University.In a previous preprint[2],αηwas discusd concomitantly with that of the cloly related key generation system calledαη-KG.Since the features ofαηdirect encryption are subtle and complex enough,we take the approach in this paper of discussing just theαηencryption system in its own right,and analyze quantitatively its random cipher feature.Doing so will hopefully also avert many possible confusions withαη-Key Generation,such as tho in[5,6].In particular, we will t up in detail the proper framework to understand and analyze the curity issues involved.Note that the prent paper can be understood independently of ref.
白色运动鞋网面黑了怎么清洗[2],the relevant terminology and results from which are summarized in Section2.1 and Appendix A of this paper.
Following our discussion of random ciphers in general and theαηcryptosystem, we show thatαηcurity is equivalent to that of a corresponding classical random cipher.We show how quantum noi allows some degree of randomization inαηwith-out sacrificing data rate,and quantify the randomization by two different parameters corresponding to ciphertext-only and known-plaintext attacks.We also show how αηcan be operated on top of a standard cipher like AES to provide additio
nal,qual-itatively different,curity bad on quantum noi against known-plaintext attacks on the key.However,information-theoretically,ciphertext-only attack on the key is possible with the originalαη.We will indicate what additional techniques can alleviate this problem,without going into any detailed analysis to be prented at a later time.Generally,only arch-complexity bad curity will be quantitatively described in this paper.Finally,we rebut the claims in[5,6]thatαηcurity is equivalent to that of a standard stream cipher and thatαηis nonrandom.
The plan of this paper is as follows:In Section2,we provide the necessary
2
review of standard cryptography.In addition,we define the random cipher concept quantitatively and point out the available results on random cipher curity.This ts the stage for our definitions in Section3that characterize a quantum cipher and a quantum random cipher,which are both ciphers in which the ciphertext is in the form of a quantum state.In Section4,we describe theαηsystem in detail,show its quantum random cipher characteristics,and highlight its advantages.In Section 5,we respond to the criticisms onαηmade by Nishioka et al[5,6]in a further elaboration of the quantitative random cipher character ofαη.
新闻概念
2Standard Cryptography and Random Ciphers 2.1Standard Symmetric-Key Cryptography
We review the basics of symmetric-key data encryption.Further details can be found ,[1,7].Throughout the paper,random variables will be denoted by upper-ca letters such as K,X1etc.It is sometimes necessary to consider explicitly quences of random variables(X1,X2,...,X n).We will denote such vector random variables by a boldface upper-ca letter X n and,whenever necessary,indicate the length of the vector(n in this ca)as a subscript.Confusion with the n-th component X n of X n should not ari as the latter is a boldface vector.Particular values taken by the random variables will be denoted by similar lower-ca alphabets.Thus,particular values taken by the key random variable K are denoted by k,k′etc.Similarly,a particular value of X n can be denoted x n.The plaintext alphabet will be denoted X,the t of possible key values K and the ciphertext alphabet Y.Thus,for example, the quences x n∈X n.In most nonrandom ciphers,X is simply the t{0,1}and Y=X.
对心理咨询的认识With the above notations,the n-symbol long ,the message quence that needs to be encrypted)is denoted by the random vector X n,the , the output of the encryption mechanism)is denoted by Y n and the cret key ud for encryption is denoted by K.In this paper,we will often call the legitimate nder of the message‘Alice’,the legitimate receiver‘Bob’,and t
he attacker(or eavesdropper)‘Eve’.Note that although the cret key is typically a quence of bits,we do not u vector notation for it since the bits constituting the key will not need to be singled out parately in our considerations in this paper.In standard cryptography,one usually deals with nonrandom ciphers.The are ciphers for which the ciphertext is a function of only the plaintext and key.In other words,there is an encyption function E k(·)such that:
y n=E k(x n).(1)
3
There is a corresponding decryption function D k(·)such that:
x n=D k(y n).(2)
In such a ca,the X i and Y i,i=1,...,n are usually taken to be from the same alphabet.
In contrast,a random cipher makes u of an additional random variable R called the private randomizer[1],generated by Alice while encrypting the plaintext and known only to her,if at all.Thus the ciphertext is determined as follows:
y n=E k(x n,r).(3)
Becau of the additional randomness in the ciphertext,it typically happens that the ciphertext alphabet Y needs to be larger than the plaintext alphabet X(or el, Y is a longer quence than X,as in homophonic substitution).It may even be a continuous infinite an analog voltage value.However,we still require, as in[1],that Bob be able to decrypt with just the ciphertext and ,without knowing R),so that there exists a function D k(·)such that Eq.(2)holds.We note that random ciphers are called‘privately randomized ciphers’in Ref.[1]–we will however u the shorter term‘random cipher’(Note that‘random cipher’is ud in a completely different n by Shannon[8]).
We note that the prence or abnce of the private randomizer R may be in-dicated using the conditional Shannon entropy(We assume a basic familiarity with Shannon entropy and conditional entropy.See any information theory , [9].).For nonrandom ciphers,we have from Eq.(1)that
H(Y n|K X n)=0.(4) On the other hand,a random cipher satisfies
H(Y n|K X n)=0,(5) due to the randomness supplied by the private randomizer R.The decryption con-dition Eqs.(2)for both random and nonrandom ciphers has the entropic characteri-zation:
H(X n|K Y n)=0.(6) Note that this characterization of a random cipher is problematic when the cipher-
text alphabet is continuous,as could be the ca withαη,becau then the Shannon entropy is not defined.It may be argued that thefinite precision of measurement
4
forces the ciphertext alphabet to be discrete.Indeed,in Sec.2.2,we define a parame-terΛthat characterizes the“degree of randomness”of a random cipher.In any ca, the definition makes n,similar to Eq.(5),only when the ciphertext alphabet is finite,or at most discrete.
一颗心的距离In the cryptography literature,the characterization of a general random cipher is limited to that given by Eqs.(3)and(5).,[1].In the next ction,we will e that the purpos of cryptographic curity suggest a sharper quantitative definition of a random cipher involving a pertinent curity parameterΓ.This new definition, unlike(5),will be meaningful irrespective of whether the ciphertext alphabet is discrete or continuous.Before we discuss the above new definition of random ciphers, we conclude this ction with some important cryptographic terminology.
By standard cryptography,we shall mean that Eve and Bob both obrve the same ciphertext random ,Y E n=Y B n=Y n.Thus,standard cryptogra-phy includes usual mathematical private-key(and also public-key)cryptography but excludes quantum cryptography and classical-nois
e cryptography[10].For a stan-dard cipher,random or nonrandom,one can readily prove from the above definitions the following result known as the Shannon limit[1,8]:
H(X n|Y n)≤H(K).(7) This result may be thought of as saying that no matter how long the plaintext quence is,the attacker’s uncertainty on it given the ciphertext cannot be greater than that of the key.This condition is of crucial importance in both direct encryption and key generation,as brought out in refs.[4,2,14,16,21],but was misd in previous criticisms ofαη[5,6,11].
By information-theoretic curity(or IT curity)on the data,we mean that Eve cannot,even with unlimited computational power,pin down uniquely the plaintext from the ,
H(X n|Y n)=0.(8) The level of such curity may be quantified by H(X n|Y n).Shannon has defined perfect curity[8]to mean that the plaintext is statistically independent of the ,
H(X n|Y n)=H(X n).(9) With the advent of quantum cryptography,the term‘unconditional curity’has come to be ud,unfortunately in many possible ns.By unconditional curity, we shall mean near-perfect information-theoretic curity against all attacks consis-tent with the known laws of quantum physics.江苏警官学院学报
5
Incidentally,note that the Shannon limit Eq.(7)immediately shows that perfect
curity can be attained only if H(X n)≤H(K),so that,in general,the key needs
to be as long as the plaintext.
2.2Random Ciphers–Quantitative Definition
As mentioned in the previous ction,the characterization of a general random cipher
merely using Eq.(3)or(5)is perhaps not well-motivated.The reason for studying random ciphers is in fact the belief that they enhance the curity of the cipher
against various attacks.By bringing into focus the intuitive mechanism by which a
random cipher may provide greater curity than a nonrandom counterpart against known-plaintext attacks,we will propo one possible quantitative characterization
of a general random cipher(or more exactly,a general random stream cipher.See below.).For a description of known-plaintext and other attacks on ciphers,together
with the known results on their curity,we refer the reader to Appendix A.
We now discuss the intuitive mechanism of curity enhancement in a random ci-pher.To this end,a schematic depiction of encryption and decryption with a random
cipher is given in Fig.1.For a binary alphabet X={0,1},let X n={a1,...,a N} be the t of N=2n possible plaintext n-quences.Let k be a particular key value.
One can view the key k as dividing the ciphertext space Y n into N parts,denoted
by the A k a
j
,j∈{1,...,N},in thefigure.Encryption of plaintext a j proceeds by first determining the relevant region A k a
j
and randomly lecting(this is the function of the private randomizer)as ciphertext some y∈A k a
j
.The decryption condition
Eq.(2)is satisfied by virtue of the regions A k a
j being disjoint for a given k.Also
shown in Fig.1is the situation where a different key value k′is ud in the system.
The associated partition of Y n consists of the ts A′k a
j that are shown with shaded
boundaries in Fig.1.The important point here is that the respective partitions of
the ciphertext space for the key values k and k′should be sufficiently‘intermixed’.
More precily,for any given plaintext a j,and any obrved ciphertext y n,we require that there exist sufficiently many key values k(and hence a sufficiently large prob-
ability of the t of possible keys corresponding to a given plaintext and obrved
ciphertext)for which y n∈A k a j.In other words,a given plaintext-ciphertext pair can be connected by many possible keys.This is the intuitive basis why random ciphers
offer better quantitative curity(as measured either by Eve’s information on the key or her complexity infinding it;e Sec.4.2-4.4for a discussion ofαηcurity) than nonrandom ciphers against known-plaintext attacks.
While the above arguments hold for any type or random cipher whatsoever,we will restrict our scope to the so-called stream ciphers.Most ciphers in current u
6
