Best Review for Cryptography

Heisenberg's uncertainty principle decrees that observations of a quantum system, no matter how delicately performed, cannot yield complete information on the system's state before observation. Therefore, if quantum systems are used to carry information, an eavesdropper, or even the intended recipient, may be prevented from getting out all the information that the sender put in. This negative feature of quantum mechanics has recently been put to positive use in the arts of private and discreet communication. 

The goal of privacy is illustrated by two persons wishing to communicate over a public channel such as newspaper ads, via coded messages no one else can understand. The subtler goal of discretion is illustrated by two singles exploring the possibility of a date, who wish to communicate in a way that protects them, not from eavesdroppers, but from each other. For example, if Alice likes Bob, Bob should only be able to learn this fact if he also likes Alice. Both privacy and discretion can be achieved by using quantum uncertainty to do what mathematics alone cannot do. 

Mathematics offers imperfect solutions to these problems, in the form of public key cryptography (PKC) (1). Before the introduction of PKC in 1976, private communication over a public channel was thought to be impossible unless the two users had agreed beforehand on some random secret information that no one else knew. This information would serve as a cryptographic key, enabling Alice to scramble her messages in a way that only Bob, knowing the same key, could unscramble. Such secret key cryptography can assure perfect, unbreakable privacy if the key is truly random, of the same length as the message being sent, and never reused to encrypt another message. Privacy thus appeared to be available to diplomats, spies, and others having the means and foresight to share secret keys with their intended correspondents, but not to ordinary impromptu users of a public communications network. Classical cryptography offered no purely mathematical solution to this "key distribution problem." Meanwhile the only solution to the discreet communications problem appeared to be for Alice and Bob to confide their secrets in a trusted intermediary, who might later choose to blackmail them. 

All this was changed by PKC. The idea of PKC is for each user (Alice, for example) to randomly choose a pair of mutually inverse transformations--a scrambling transformation and an unscrambling transformation--and to publish the directions for performing the former but not the latter. Anyone, including Bob, can then use Alice's public scrambling algorithm to prepare a message that only she can unscramble. Similarly anyone, including Alice, can use Bob's public scrambling algorithm to prepare a message that only he can unscramble. Thus Alice and Bob can exchange secret messages even though they share no secret to begin with. Subsequently Yao (2) and others (3) showed how to use public key techniques for discreet communication without the help of a third party. Unfortunately PKC rests on unproved mathematical assumptions, such as the difficulty of factoring large integers, and the entire edifice of privacy and discretion built upon it could come crashing down tomorrow. 

Both the secret key and public key approaches described above tacitly assume that messages are in some physical form that can be accurately read and copied (though not necessarily understood) by anyone having access to them. With quantum systems, this is no longer so, because measurements on a quantum system cannot extract complete information about the state in which it was prepared. The incomplete accessibility of quantum information is illustrated by the behavior of individual photons of polarized light. 

Photons can be prepared in a continuum of polarization states including in particular the two rectilinear states, horizontal ((Character omitted)) and vertical ((Character omitted)), and the two diagonal states, 45 deg ((Character omitted)) and 135 deg ((Character omitted)). The two rectilinear states (Character omitted) and (Character omitted) can be distinguished by one measurement, and the two diagonal states (Character omitted) and (Character omitted) can be distinguished by another measurement; but if a rectilinear measurement is performed on a diagonal photon, the photon behaves randomly, acting half the time like (Character omitted) and half the time like (Character omitted), and all information about its diagonal polarization is lost. Similarly, a random result is obtained and all information is lost if a diagonal measurement is performed on a rectilinear photon. Such "conjugate" pairs of states exist for any nontrivial quantum system.
One might hope to learn more about a single photon's polarization by not measuring the photon directly, but rather by using a device such as a laser to amplify it into a clone of many photons, then measuring these; but this hope is vain because the uncertainty principle introduces just enough randomness in the polarizations of the daughter photons to nullify any advantage gained by having more photons to measure. Limitations on the accuracy of measuring quantum states thus imply limitations on copying them, and vice versa. 

It can be seen that quantum information has a peculiar kind of conditional readability: a message consisting of rectilinear and diagonal photons can be accurately read or copied, but only by someone who knows some of the information that went into forming the message, namely which of the photons are rectilinear and which are diagonal. 

This conditional readability was first put to use by Wiesner (4) in the impractical invention shown in the figure: quantum money that is physically impossible to copy. Quantum money would not need the warning printed on French money, of life imprisonment for counterfeiters, because the crime would be impossible to commit. A quantum bank note would contain 20 polarized photons in a secret random sequence of polarization states ((Characters omitted)), stored in individual perfectly reflective mirror-lined boxes capable of holding the photons indefinitely without loss (possible in principle, but not in practice). Each bank note would also have a serial number printed in ordinary ink, which would be recorded, along with that bank note's secret list of polarizations, in a book made available to banks but not the general public. The sequence of polarizations can thus be accurately read and checked by banks, who know the secret information, but can neither be read nor copied reliably by a would-be counterfeiter, who does not. 

Quantum money is impractical because of the difficulty of storing photons. However, an invention very similar to quantum money, but using photons in flight, offers a practical solution to the key distribution problem mentioned earlier, and thus a means for two parties who share no secret initially to be assured of the privacy of their subsequent communications (5). To perform quantum key distribution, Alice and Bob use a quantum channel, through which they send polarized photons, in conjunction with a classical public channel, through which they send ordinary messages. The eavesdropper, Eve, is free to tamper with the photons in the quantum channel and can read, but not alter, the messages in the public channel. 

Alice begins by sending Bob a random sequence of the four kinds of photons, (Character omitted), (Character omitted), (Character omitted), and (Character omitted), and Bob decides randomly for each photon whether to measure its rectilinear or diagonal polarization. Of course this spoils half the data, because half the time Bob will have made the wrong type of measurement. But now Bob and Alice use their public channel to locate and discard the bad data, without compromising the remaining good data. To do this, Bob announces publicly which types of measurements he made, rectilinear or diagonal, but not the measurement outcomes; Alice replies, telling him which of his measurements were of the correct type; and both parties agree to keep only those instances, discarding the others. If no eavesdropping has occurred, the result should be a shared secret, which can be interpreted as a binary key by letting (Character omitted) and (Character omitted) represent 0 and (Character omitted) and (Character omitted) represent 1. 

If Eve attempts to intercept one or more photons in flight, measure them, and resend forged copies to Bob, she faces the same problem as the would-be counterfeiter of quantum money: some of her measurements will be wrong, and will result in inaccurate forgeries that behave randomly when later measured by Bob, introducing errors into Bob and Alice's supposedly shared data. The final step of quantum key distribution is therefore for Alice and Bob to test their data for discrepancies, for example, by publicly comparing some of it. If they find discrepancies, they have reason to suspect eavesdropping and should discard all their data and start over with a fresh batch of photons. Otherwise, they can be reasonably sure that those parts of their data not disclosed in the public comparison are indeed a shared secret and can therefore be used as a secret key to encrypt subsequent meaningful messages. 

An improved version of the above scheme, able to cope with practical problems such as detector noise, has been implemented over short distances with a light beam (6), and there is no obstacle other than expense to implementing it over arbitrarily long distances with a light beam, or over a moderate length of optical fiber (a long fiber would require amplifying the quantum signal in transit, which is equivalent to eavesdropping). Although it requires a special and somewhat inconvenient physical channel, quantum key distribution offers a solution to the private communication problem based on fundamental laws of physics, rather than on unproved mathematical assumptions.
During the eighties computer scientists showed that any two-party problem discreetly solvable with the help of an intermediary could be discreetly solved by the two parties alone using PKC. They also showed (7, 8) that all such problems could be reduced to a simple, almost pointless-seeming primitive called oblivious transfer (9) which consists of Alice sending Bob a one-bit message in such a way that it has exactly a half chance of arriving, and only he will know whether it did. This task involves discretion (Alice is not supposed to learn whether the message arrived) and it could of course be performed by an intermediary; but if Alice and Bob could perform it by themselves, they could solve any other two-party problem by themselves with maximum discretion. 

An obvious quantum way to obliviously transfer a bit is for Alice to encode it in a photon and send it to Bob, randomly deciding whether to use a rectilinear photon (where (Character omitted) = 0 and (Character omitted) = 1) or a diagonal one (where (Character omitted) = 0 and (Character omitted) = 1). Bob then chooses randomly whether to measure the photon rectilinearly or diagonally. If he makes the right measurement, he learns Alice's bit; otherwise he gets a random result. Finally Alice tells him whether the photon she sent was rectilinear or diagonal, thereby allowing him (but not her) to learn whether the transfer succeeded. This simple scheme described has various flaws (for example, Bob can get too much partial information by measuring the polarization along an intermediate axis such as 22.5 deg) which can overcome at the cost of making the scheme more complicated and using more photons. 

A fully practical version of quantum oblivious transfer has been described (10) and can be implemented with apparatus similar to that used for quantum key distribution. Quantum oblivious transfer has the advantage of being useful over short distances (discreet decisions are often sought by parties occupying the same room), and the disadvantage of being rather inefficient mathematically, with known practical schemes requiring millions of photons to be individually sent and received to reach even simple decisions. 

We have not yet mentioned the most famous quantum phenomenon involving information: the Einstein-Podolsky-Rosen (EPR) effect, which generates correlated random outcomes simultaneously in two remote places, in a way that cannot be explained ("Bell's inequality") by hypothesizing a common random cause in the past. Although the experimental verification of violations of Bell's inequality are the most celebrated evidence of the correctness of quantum mechanics, the EPR effect has had surprisingly modest consequences so far for quantum cryptography. Some practical quantum key distribution schemes (11, 12) use EPR states as a matter of convenience, and, if it were possible to store photons (or other conjugate states), EPR schemes would offer a secure way to store secret keys after distribution, which non-EPR schemes cannot (13). Thus the EPR effect appears most useful in the positive role of confirming quantum mechanics, while the uncertainty principle is more useful in the negative role of preventing unwanted disclosure of information.

0 komentar:

Posting Komentar

 
Copyright © 2011 Arti, Pengertian, Definisi | Themes by ada-blog.com.