Posts Tagged ‘Quantum cryptography
A quantum public key is a quantum state drawn from a set of non-orthogonal states. Multiple copies of the same key can be issued and distributed to different participants in a system. Such states can be used to encode classical information privately, because by the principles of quantum theory the states cannot be fully distinguished. The natural way to encode classical information on quantum states is to apply some quantum operation which represents the information on the quantum state.
It is considered to use quantum public key encryption for its direct and natural purpose – secure communication. In this part the emphasis is on the advantages of this method with respect to private key cryptography. Other uses of public keys in quantum cryptography include quantum fingerprinting, quantum digital signatures and quantum string commitment. In each of these cases a choice of the set of non orthogonal states is made suitable for the particular application. In the case of secure communication, discussed in this thesis, the quantum states must have the property that they can easily be used for encoding of classical information by a person without knowing which of the states from the set was chosen.
The contribution of this definition is a rigorous description of the parameters of a quantum public key. We give simple and efficient protocols for distribution of public keys, and of encoding and decoding of classical information using these keys. The protocols are divided into two types – those where the key distribution phase is quantum, but the encodings and decodings of messages are classical, and those where also the encoding and decoding procedures involve quantum communication. Each protocol comes with a thorough analysis of its security.
The good properties of this method of encryption allow us to have a network where the content of the exchanged messages, as well as the identities of senders and receivers of messages, are kept secret from any unauthorized entity. This unauthorized entity (the adversary) is assumed to control an arbitrary fraction (smaller than 1) of the users/players in the network. The network provides
unconditional security in both these two aspects. In terms of communication complexity the main parameter is the number of users of the network. With respect to this parameter we have protocols that require for a delivery of a single message a polylogarithmic number of communication rounds. The total amount of communication per message delivery is also polylogarithmic in this parameter.
Classically, according to what is currently known, tolerating an arbitrary fraction of adversary controlled users can be achieved efficiently only with computational security (to be considered efficient a protocol has to operate with both polylogarithmic number of rounds and polylogarithmic total communication per message). Proving this fact is an open problem; however if unconditional
security is required then the only known classical solutions either limit the power of the adversary to control at most half of the players in the network, or are highly inefficient in terms of communication cost in the network. To be more specific, these solutions require at least a linear number of communication rounds per single message delivery (which is far from being acceptable), and the
total amount of communication per message is polynomial.
Before exploring quantum key distribution, it is important to understand the state of modern cryptography and how quantum cryptography may address current digital cryptography limitations. Since public key cryptography involves complex calculations that are relatively slow, they are employed to exchange keys rather than for the encryption of voluminous amounts of date. For example, widely deployed solutions, such as the RSA and the Diffie-Hellman key negotiation schemes, are typically used to distribute symmetric keys among remote parties. However, because asymmetric encryption is significantly slower than symmetric encryption, a hybrid approach is preferred by many institutions to take advantage of the speed of a shared key system and the security of a public key system for the initial exchange of the symmetric key. Thus, this approach exploits the speed and performance of a symmetric key system while leveraging the scalability of a public key infrastructure.
However, public key cryptosystems such as RSA and Diffie-Hellman are not based on concrete mathematical proofs. Rather, these algorithms are considered to be reasonably secure based on years of public scrutiny over the fundamental process of factoring large integers into their primes, which is said to be “intractable”. In other words, by the time the encryption algorithm could be defeated, the information being protected would have already lost all of its value. Thus, the power of these algorithms is based on the fact that there is no known mathematical operation for quickly factoring very large numbers given today’s computer processing power.
Secondly, there is uncertainty whether a theorem may be developed in the future or perhaps already available that can factor large numbers into their primes in a timely manner. At present, there is no existing proof stating that it is impossible to develop such a factoring theorem. As a result, public key systems are thus vulnerable to the uncertainty regarding the future creation of such a theorem, which would have a significant affect on the algorithm being mathematical intractable. This uncertainty provides potential risk to areas of national security and intellectual property which require perfect security.
In sum, modern cryptography is vulnerable to both technological progress of computing power and evolution in mathematics to quickly reverse one way functions such as that of factoring large integers. If a factoring theorem were publicized or computing became powerful enough to defeat public cryptography, then business, governments, militaries and other affected institutions would have to spend significant resources to research the risk of damage and potentially deploy a new and costly cryptography system quickly.
Quantum cryptography involves a surprisingly elaborate suite of specialized protocols, which we term “QKD protocols.”Many aspects of these protocols are unusual – both in motivation and in implementation – and may be of interest to specialists in communications protocols.
Fig.1 Effects of an unbalanced interferometer on a photon
We have designed this engine so it is easy to “plug in” new protocols, and expect to devote considerable time in coming years to inventing new QKD (Quantum Key Distribution) protocols and trying them in practice. As shown in Fig. 1, these protocols are best described as sub-layers within the QKD protocol suite. Note, however, that these layers do not correspond in any obvious way to the layers in a communications stack, e.g., the OSI layers. As will be seen,they are in fact closer to being pipeline stages.
Sifting is the process whereby Alice and Bob winnow away all the obvious “failed qubits” from a series of pulses. As described in the introduction to this section, these failures include those qubits where Alice’s laser never transmitted,Bob’s detectors didn’t work, photons were lost in transmission,and so forth. They also include those symbols where Alice choose one basis for transmission but Bob chose the other for receiving.
At the end of this round of protocol interaction – i.e. after a sift and sift response transaction – Alice and Bob discard all the useless symbols from their internal storage, leaving only those symbols that Bob received and for which Bob’s basis matches Alice’s. In general, sifting dramatically prunes the number of symbols held in Alice and Bob. For instance, assume that 1% of the photons that Alice tries to transmit are actually received at Bob and that the system noise rate is 0. On average, Alice and Bob will happen to agree on a basis 50% of the time in BB84. Thus only 50% x 1% of Alice’s photons give rise to a sifted bit, i.e.,1 photon in 200. A transmitted stream of 1,000 bits therefore would boil down to about 5 sifted bits.
Error correction allows Alice and Bob to determine all the“error bits” among their shared, sifted bits, and correct them so that Alice and Bob share the same sequence of error-corrected bits. Error bits are ones that Alice transmitted as a 0 but Bob received as a 1, or vice versa. These bit errors can be caused by noise or by eavesdropping.
Error correction in quantum cryptography has a very unusual constraint, namely, evidence revealed in error detection and correction (e.g. parity bits) must be assumed to be known to Eve, and thus to reduce the hidden entropy available for key material. As a result, there is very strong motivation to design error detection and correction codes that reveal as little as possible in their public control traffic between Alice and Bob. Our first approach for error correction is a novel variant of the Cascade protocol and algorithms. The protocol is adaptive,in that it will not disclose too many bits if the number of errors is low, but it will accurately detect and correct a large number of errors (up to some limit) even if that number is well above the historical average.
Our version works by defining a number of subsets (currently 64) of the sifted bits and forming the parities of each subset. In the first message, the list of subsets and their parities is sent to the other side, which then replies with its version of the parities. The subsets are pseudo-random bit strings, from a Linear-Feedback Shift Register (LFSR) and are identified by a 32-bit seed for the LFSR. Once an error bit has been found and fixed, both sides inspect their records of subsets and subranges, and flip the recorded parity of those that contained that bit.This will clear up some discrepancies but may introduce other new ones, and so the process continues.
Since these parity fields are revealed in the interchange of “error correction” messages between Alice and Bob, these bits must be taken as known to Eve. Therefore, the QKD protocol engine records amount of information revealed (lost) due to parity fields, and later requires a compensating level of privacy amplification to reduce Eve’s knowledge to acceptable levels.
Privacy amplification is the process whereby Alice and Bob reduce Eve’s knowledge of their shared bits to an acceptable level. This technique is also often called advantage distillation.
Authentication allows Alice and Bob to guard against “man in the middle attacks,” i.e., allows Alice to ensure that she is communicating with Bob (and not Eve) and vice versa. Authentication must be performed on an ongoing basis for all key management traffic, since Eve may insert herself into the conversation between Alice and Bob at any stage in their communication. The original BB84 paper described the authentication problem and sketched a solution to it based on universal families of hash functions, introduced by Wegman and Carter. This approach requires Alice and Bob to already share a small secret key, which is used to select a hash function from the family to generate an authentication hash of the public correspondence between them. By the nature of universal hashing, any party who didn’t know the secret key would have an extremely low probability of being able to forge the correspondence, even an adversary with unlimited computational power. The drawback is that the secret key bits cannot be re-used even once on different data without compromising the security. Fortunately, a complete authenticated conversation can validate a large number of new,shared secret bits from QKD, and a small number of these maybe used to replenish the pool.
There are many further details in a practical system which we will only mention in passing, including symmetrically authenticating both parties, limiting the opportunities for Eveto force exhaustion of the shared secret key bits, and adapting the system to network asynchrony and retransmissions. Another important point: it is insufficient to authenticate just the QKD protocols; we must also apply the these techniques to authenticate the VPN data traffic.
The concept of quantum cryptography(QC), which utilizes a quantum channel and classical TMs (Turing Machine) (as well as a classical channel) and some protocols such as oblivious transfer based on this concept have also been presented. QC is one of the solutions to the above-mentioned problem when a QTM (Quantum Turing Machine) is realized in the future: that is, QC will be used for key-distribution in place of public-key encryption if a QTM is realized. The major difference between QC and QPKC is that QC employs a quantum channel (and classical channel)while QPKC (Quantum Public Key Cryptosystem) employs only a classical channel. The security assumption for a QC scheme is quantum mechanics (believed by most physicists), while that fora QPKC scheme is a computational assumption (e.g., existence of a one-way function) in the QTM model.
Although several experimental QC systems have been already realized in the current technologies, recently reported security flaws of these systems are due to their realistic restrictions of quantum channels such as channel losses, realistic detection process, modifications of the qubits through channels, and fixed dark count error over long distance channels. In addition, it is likely that much more complicated communication networks will be utilized in the future, and it seems technically very hard and much costly to realize a quantum channel from end to end through such complicated networks even in the future.
Accordingly, the QPKC approach seems much more promising, since in many applications encryption and key-distribution should be realized by end-to-end communication through (classical) complicated communication networks. QC provides no solution to the problem of digital signatures when a QTM is realized: that is, QC cannot be used in digital signatures. Hence, our QPKC approach may be the only possible solution to the problem of digital signatures when a QTM is realized.
The DARPA Quantum Network aims to strengthen QKD’s performance in these weaker areas. In some instances, this involves the introduction of newer QKD technologies; for example, we hope to achieve rapid delivery of keys by introducing a new, high-speed source of entangled photons. In other instances, we rely on an improved system architecture to achieve these goals; thus, we tackle distance- and location independence by introducing a network of trusted relays. Whereas most work to date has focused on the physical layer of quantum cryptography – e.g. the modulation, transmission, and detection of single photons – our own research effort aims to build QKD networks. As such, it is oriented to a large extent towards novel protocols and architectures for highly-secure communications across a heterogenous variety of under lying kinds of QKD links.
Figure 1. A Virtual Private Network (VPN) based on Quantum Key Distribution
Our security model is the cryptographic Virtual Private Network (VPN). Conventional VPNs use both public-key and symmetric cryptography to achieve confidentiality and authentication/integrity. Public-key mechanisms support key exchange or agreement, and authenticate the endpoints. Symmetric mechanisms (e.g. 3DES, SHA1) provide traffic confidentiality and integrity. Thus VPN systems can provide confidentiality and authentication / integrity without trusting the public network interconnecting the VPN sites. In our work, existing VPN key agreement primitives are augmented or completely replaced by keys provided by quantum cryptography. The remainder of the VPN construct is left unchanged; see Fig. 1. Thus our QKD-secured network isfully compatible with conventional Internet hosts, routers, firewalls, and so forth.
At time of writing, we are slightly over one year into a projected five-year effort to build the full DARPA Quantum Network. In our first year, we have built a complete quantum cryptographic link, and a QKD protocol engine and working suite of QKD protocols, and have integrated this cryptographic substrate into an IPsec-based Virtual Private Network. This entire system has been continuously operational since December 2002, and we are now in the process of characterizing its behavior and tuning it. In coming years, we plan to build a second link based on two photon entanglement, and to build various forms of end-to-end networks for QKD across a variety of kinds of links. We expect the majority of our links to be implemented in dark fiber but some may also be implemented in free space, either in the labor outdoors.
Quantum cryptography makes use of the quantum-mechanical behavior of nature for the design and analysis of cryptographic schemes. Optimally (but not always), quantum cryptography allows for the design of cryptographic schemes whose security is guaranteed solely by the laws of nature. This is in sharp contrast to standard cryptographic schemes, which can be broken in principle, i.e., when given sufficient computing power. From a theory point of view, quantum cryptography offers a beautiful interplay between the mathematics of adversarial behavior and quantum information theory. We discuss the traditional application of quantum cryptography, quantum key distribution (QKD), from a modern perspective, and we discuss some recent developments in the context of quantum two-party cooperation (2PC). QKD allows two distant parties to communicate in a provably-secure way in the presence of an outside eavesdropper, whereas 2PC is concerned with protecting information against possibly malicious insiders. We show the basic idea of constructing quantum cryptographic schemes, but we also show some connectionsto quantum information theory as needed for the rigorous security analyses, and we discuss some of the relevant quantum-information-theoretic results.
The security of most of the cryptographic schemes currently used relieson unproven computational complexity assumptions (like the assumed hardness of factoring large numbers), combined with an assumed bound on a potential attacker’s computing power. This complexity-theoretic approach of designing cryptographic schemes leads to very practical solutions but obviously has its downside: one cannot be fully certain about the security of the scheme! Indeed, the underlying computational complexity assumption might be broken from one day to another (e.g. byan efficient factoring algorithm being discovered) since complexity theory is still far from being able to prove some computational problem to be “hard” in the sense as needed. Furthermore, it is known that the standard complexity assumptions used in practice (factoring and computing discrete-logs) break down as soon as a quantum computer can be built. Finally, even if it is computationally infeasible for an attacker to extract sensitive data from the information available to him at the time the cryptographic scheme is used, the attacker can still store, say, an intercepted ciphertext and wait until computer technology has advanced enough so that he eventually can recover the data that was to be protected. This clearly poses a serious threat to long term highly-sensitive data.
Optimally, but not always, quantum cryptography allows for the design of cryptographic schemes that can be proven secure under the sole assumption that the laws of quantum mechanics are correct—or that they at least describe sufficiently well the behavior of certain particles like photons or spin-1/2 particles, which would be used to implement the quantum-cryptographic schemes. For instance, the search for a rigorous analysis of one of the first quantum cryptographic schemes led to important insights into quantum information theory, which in turn proved to be useful for the design of new quantum cryptographic schemes.
On the other hand, we also want to present quantum cryptography as an exact mathematical science that combines elements from classical cryptography, information theory and quantum mechanics. Therefore, besides the quantum-cryptographic schemes we show, we also discuss the theoretical foundations needed to rigorously understand and prove their security. These are quantum-information-theoretic results, specifically developed for the analysis of quantum-cryptographic schemes, but can be appreciated in their own right as providing interesting insight into the theory of quantum information. For instance, we show a meaningful way to measure the uncertainty that some piece of classical (meaning non-quantum) data contains when givena correlated quantum state, and we show that this measure determines the number of nearly-random-and-independent bits that can be extracted from the classical data. Also, we show a variant of the uncertainty principle that expresses the amount of uncertainty in terms of the above measure.
As of specific quantum cryptographic results, we focus in this article on the question of tackling classical (i.e. non-quantum) cryptographic tasks by quantum cryptographic means, like how to securely communicate a classical private message by using a quantum channel. Specifically, we focus on quantum-key distribution(QKD), which is the traditional application of quantum cryptography, and on recent new developments in the context of quantum two-party cooperation (2PC).
QKD allows two parties, Alice and Bob, to agree on a secret key K by public communication, i.e., even if an attacker Eve can access the complete conversation between Alice and Bob. By the laws of quantum mechanics, it is guaranteed that the agreed-upon secret key K is (close to) random-and-independent of Eve’s (quantum) view. As such, K can then be safely used for instance as encryption key for a (possibly perfectly-secure) encryption scheme to securely communicate a private message viathe public communication channel.
2PC, on the other hand, is concerned with protecting information against inside attackers. Unfortunately, quantum cryptographic 2PC schemes whose security is guaranteed by the laws of quantum mechanics alone do not exist (unless one settles for avery low level of security), but in addition, some “technological restriction” needs to be assumed about the attacker: for instance, that he cannot reliably store arbitrarily many, say, photons without affecting their polarization. While the theory of quantum physics permits to store quantum states, doing so in the form of photons, for instance, is technically very challenging and essentially impossible with current technology. Itis thus reasonable to base security upon it.