[attachment=10683]
1. INTRODUCTION
Cryptography is the science of keeping private information from unauthoaccess, of ensuring data integrity and authentication, and other tasks. In this survey will focus on quantum-cryptographic key distribution and bit commitment protocol we in particular will discuss their security. Before turning to quantum cryptograph me give a brief review of classical cryptography, its current challenges and it’s his development.
Two parties, Alice and Bob, wish to exchange messages via some in channel in a way that protects their messages from eavesdropping. An algorithm was called a cipher in this context, scrambles Alice’s message via some rule such restoring the original message is hard—if not impossible—without knowledge secret key. This “scrambled” message is called the cipher text. On the other hand (who possesses the secret key) can easily decipher Alice’s cipher text and obtain original plaintext. Figure 1 in this section presents this basic cryptographic scenario.
2. CLASSICAL CRYPTOGRAPHY
Overviews of classical cryptography can be found in various text books (see, e.g., Rothe [2005] and Stinson [2005]). Here, we present just the basic dentition of a cryptosystem and give one example of a classical encryption method, the one-time pad. Dentition 2.1. A (deterministic, symmetric) cryptosystem is a five-tuple (P, C, K, and E, D) satisfying the following conditions:
• P is a finite set of possible plaintexts.
• C is a finite set of possible cipher texts.
• K is a finite set of possible keys.
• For each k є K, there are an encryption rule ek є E and a corresponding decryption rule dk є D, where ek: P→ C and dk: C→ P are functions satisfying dk (ek (x)) = x for each plaintext element x є P.
In the basic scenario in cryptography, we have two parties who wish to communicate over an insecure channel, such as a phone line or a computer network. Usually, these parties are referred to as Alice and Bob. Since the communication channel is insecure, an eavesdropper, called Eve, may intercept the messages that are sent over this channel. By agreeing on a secret key k via a secure communication method, Alice and Bob can make use of a cryptosystem to keep their information secret, even when sent over the insecure channel. This situation is illustrated in Figure 1.
The method of encryption works as follows. For her secret message m, Alice uses
The key k and the encryption rule ek to obtain the cipher text c = ek (m). She sends Bob the cipher text c over the insecure channel. Knowing the key k, Bob can easily decrypt the cipher text by the decryption rule dk: dk © = dk (ek (m)) = m.
Knowing the cipher text c but missing the key k, there is no easy way for Eve to determine the original message m.
There exist many cryptosystems in modern cryptography to transmit secret messages. An early well-known system is the one-time pad, which is also known as the Verna cipher. The one-time pad is a substitution cipher. Despite its advantageous properties, which we will discuss later on, the one-time pad’s drawback is the costly effort needed to transmit and store the secret keys.
Example 2.2 (One-Time Pad). For plaintext elements in P, we use capital letters and some punctuation marks, which we encode as numbers ranging from 0 to 29, see Figure2. As is the case with most cryptosystems, the cipher text space equals the plaintext space. Furthermore, the key space K also equals P, and we have P =C= K= {0, 1, 29}.
Next, we describe how Alice and Bob use the one-time pad to transmit their messages. A concrete example is shown in Figure 3. Suppose Alice and Bob share a joint secret key k of length n = 12, where each key symbol ki є {0, 1, 29} is chosen uniformly at random. Let m = m1m2. . . mn be a given message of length n, which Alice wishes to encrypt. For each plaintext letter mi, where 1 ≤ i ≤ n, Alice adds the plaintext numbers to the key numbers. The result is taken modulo 30. For example, the last letter of the plaintext from Figure 3, “D,” is encoded by “m12=03.” The corresponding key is
“m12= 28,” so we have c12= 3 + 28 = 31. Since 31 ≡ 1 mod 30, our plaintext letter “D” is encrypted as “B.” Decryption works similarly by subtracting, character by character, the key letters from the corresponding ciphertext letters. So the encryption and decryption can be written as respectively ci= (mi+ ki) mod 30 and mi= (ci− ki) mod 30, 1 ≤ i ≤ n.
2.3. Limitations
Cryptographic technology in use today relies on the hardness of certain mathematical problems. Classical cryptography faces the following two problems. First, the security of many classical cryptosystems is based on the hardness of problems such as integer factoring or the discrete logarithm problem. But since these problems typically are not provably hard, the corresponding cryptosystems are potentially insecure. For example, the famous and widely used RSA public-key cryptosystem [Rivest et al. 1978] could easily be broken if large integers were easy to factor. The hardness of integer factoring, however, is not a proven fact but rather a hypothesis.1.We mention in passing that computing the RSA secret key from the corresponding public key is polynomial-time equivalent to integer factoring [May 2004].
Second, the theory of quantum computation has yielded new methods to tackle these mathematical problems in a much more efficient way. Although there are still numerous challenges to overcome before a working quantum computer of sufficient power can be built, in theory many classical ciphers (in particular public-key cryptosystems such as RSA) might be broken by such a powerful machine. However, while quantum computation seems to be a severe challenge to classical cryptography in a possibly not so distant future, at the same time it offers new possibilities to build encryption methods that are safe even against attacks performed by means of a quantum computer. Quantum cryptography extends the power of classical cryptography by protecting the secrecy of messages using the physical laws of quantum mechanics.
3. QUBITS
The most important unit of information in computer science is the bit. There are two possible values that can be stored by a bit: the bit is either equal to “0” or equal to “1.” These two different states can be represented in various ways, for example by a simple switch or by a capacitor: if not charged, the capacitor holds the value zero; if charged, it holds the value one.
There exist many possibilities to physically represent a qubit in practice, as every quantum system with at least two states can serve as a qubit. For example, the spin of an atom or the polarization5 of a light particle can represent the state of a qubit. Even a cat with its two basic states “dead” and “alive,” introduced by Schrödinger [1935] to visualize fundamental concepts of quantum mechanics, might serve as a representation. The cat’s problem—or fortune from the animal’s point of view—when being used as a quantum system is its sheer size compared to that of an atom or light particle. There is no way to protect such a big quantum instance from interaction with its environment, which in turn will result in decoherence of the superposition of the cat.
3.1. Qubit Representation
In general, a quantum state |ψ) is an element of a finite-dimensional complex vector space (or Hilbert space) H. We denote the scalar product of two states |ψ) and |φ) by (ψ|φ), where (ψ| = |ψ) T is the conjugate transpose of |ψ). It is convenient to deal with normalized states, so we require (ψ|ψ) = 1 for all states |ψ) that have a physical meaning.
The quantum analog of the bit is called qubit, which is derived from quantum bit.
A qubit |ψ) is an element of a two-dimensional Hilbert space, in which we can introduce an orthonormal basis, consisting of the two states |0) and |1). Unlike its classical counterpart, the quantum state can be in any coherent superposition of the basis states:
|ψ) = α|0) + β|1) (1)
where α and β are, in general, complex coefficients. This is due to the fact that the quantum mechanical equation of motion, the Schrödinger equation, is linear: Any linear superposition of its solutions (the quantum states) is also a solution. Since we require quantum states to be normalized, we find that the coefficients in (1) have to fulfill
|α|2 + |β|2 = 1, where | • | denotes the absolute value.
4. QUANTUM CRYPTOGRAPHY
Quantum Cryptography, or Quantum Key Distribution (QKD), uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random bit string known only to them, which can be used as a key to encrypt and decrypt messages. An important and unique property of quantum cryptography is the ability of the two communicating users to detect the presence of any third party trying to gain knowledge of the key. These results from a fundamental part of quantum mechanics: the process of measuring a quantum system in general disturbs the system. A third party trying to eavesdrop on the key must in some way measure it, thus introducing detectable anomalies. By using quantum superposition or quantum entanglement and transmitting information in quantum states, a communication system can be implemented which detects eavesdropping. If the level of eavesdropping is below a certain threshold a key can be produced which is guaranteed as secure (i.e. the eavesdropper has no information about), otherwise no secure key is possible and communication is aborted.
The security of quantum cryptography relies on the foundations of quantum mechanics, in contrast to traditional public key cryptography which relies on the computational difficulty of certain mathematical functions, and cannot provide any indication of eavesdropping or guarantee of key security.
Quantum cryptography is only used to produce and distribute a key, not to transmit any message data. This key can then be used with any chosen encryption algorithm to encrypt (and decrypt) a message, which can then be transmitted over a standard communication channel. The algorithm most commonly associated with QKD is the one-time pad, as it is provably secure when used with a secret, random key.
Quantum cryptography exploits the quantum mechanical property that a qubit cannot be copied or amplified without disturbing its original state. This is the statement of the No-Cloning Theorem [Wootters and Zurek 1982], which is easily proven: Assume there exists a unitary transformation U that can copy two states |ψ1) and |ψ2): where |0) is an arbitrary input state. If we equate the scalar products of the left-hand and right-hand sides, it follows by the unitarity of U that (ψ1|ψ2) = (ψ1|ψ2)2, which implies that (ψ1|ψ2)
equals 0 or 1. This means that we can copy only orthogonal or identical states. In contrast, arbitrary unknown states cannot be perfectly cloned. (Note that orthogonal or identical states are not viewed as “unknown” states, since we do know they are orthogonal, for example.)
The essence of this theorem is the main ingredient of quantum key distribution, where Alice and Bob use a quantum channel to exchange a sequence of qubits, which will then be used to create a key for the one-time pad in order to communicate over an insecure channel. Any disturbance of the qubits, for example caused by Eve trying to measure the qubits’ state, can be detected with high probability. Quantum cryptographic devices typically employ individual photons of light and take advantage of either the Heisenberg Uncertainity principle or Quantum Entanglement.