Re: The Shining Cryptographers Net
John Denker writes: A much better strategy for Eve is to _not_ make so many measurements. Rather, she should preserve the photon in all its analog, quantum-mechanical glory and recirculate it back to Bob, bypassing the other participants in the ring. Then Bob, in blissful ignorance, will decrypt his own signal. We have reduced the problem to the trivial case of the one-person ring; in such a ring it is obvious whether Bob sent a message or not. Yes, that's a very strong attack. I don't think I am going to be able to come up with any straightforward fixes against it. It's back to the drawing board on this one... One could imagine a hybrid scheme: 1) The participants exchange keys, as in the conventional DC net, and 2) The participants process the signal by rotating the polarization, or shifting the quantum phase, or other unconventional, non-Boolean transformations. 3) They could recirculate the signal C1 times if desired. Another such hybrid idea would be to use quantum key exchange to initially share random strings between each pair of participants in step 1, then to run a regular DC net. You can trivially use the regular DC net algorithm with a photon rather than a conventional data packet - where you would toggle the bit in the data packet, you rotate the photon polarization 90 degrees. This provides no more and no less security than a DC net at probably much higher cost, so as you say it is hardly worthwhile on its own. Other ideas I plan to pursue include hybrid schemes where quantum key exchange runs simultaneously with the photon-based DC net algorithm to perhaps provide slightly more efficiency than using two different phases. And I'm still hopeful that some variant on quantum key exchange can work for the information flow required in the SC net. The thing that makes quantum key exchange work is that the eavesdropper sometimes guesses wrong about what basis to use, and the protocol then amplifies her resulting gaps in knowledge. This is harder for a SC net because if Eve gets even partial information about who is transmitting, we can't make her forget it. I'll keep working on it. Thanks again to John and the others who have offered helpful criticism and suggestions. Hal Finney
Re: The Shining Cryptographers Net
This message analyzes the Shining Cryptographers network in terms of how much information Eve the eavesdropper can hope to get by measuring the photon state before and after it is rotated. See earlier messages for more detail about how the SC Net works. This analysis will focus on one particular kind of attack. Eve will make measurements of the photon polarization angle as it travels through the network and attempt to deduce information about the signals being sent by the participants. Her measurements are analyzed as idealized "strong" measurements; weak measurements would reduce the chance of being detected at the cost of providing less information per measurement. We also assume that she is measuring only the linear polarization; measuring circular or elliptical polarization would appear to provide less useful information. We further assume that she is only able to send a single photon through the network; stations may be equipped with mechanisms to prevent multiple-photon attacks. It is conceivable that more subtle attacks are possible using advanced quantum-mechanical mechanisms. Despite these limitations and simplifying assumptions, the data presented here do provide concrete figures on how effective Eve can be with an attack of this kind. Somewhat surprisingly, she can deduce a significant amount of information with low-circulation-count networks. Skip to the bottom to see the results, if you are not interested in the mathematical derivation. If we were using circulation count of 1, meaning that the photon goes around the ring only once, Eve can easily determine whether any given station is rotating the photon polarization, by measuring the photon state before and after that station. The photon will be rotated either by 0 degrees or 90 degrees, and Eve can distinguish these based on whether the second measurement has the same or the perpendicular orientation to the first. Therefore circulation count of 1 is an easy target for Eve (assuming she can tolerate her eavesdropping being detected with probability approximately 1/2, as was shown earlier). With circulation count of 2, her problem is harder. She can make measurements before and after the station on both circulations of the photon. Each measurement yields some information about how much the station is rotating the photon. Combining the information from both rotations, she can use probability theory to estimate the chances that the station's two rotations add to an even or odd multiple of 90. For concreteness, call the orientation into which Eve collapses the photon before the station, vertical, or zero degrees. After the station Eve will either measure the photon as vertical or as horizontal. The former case is a *measured* rotation of 0 degrees, and the latter is a *measured* rotation of 90 degrees. This does not mean that the station has rotated by exactly this amount, but probability theory can allow us to create a probability distribution for how much the rotation probably was. By the physics of polarization, the probability distribution will be proportional to cosine squared of the difference between the measured and actual rotation. This means that if the measured rotation is 0 degrees, the actual rotation can be expressed by a probability distribution proportional to cos^2 of the rotation angle. If the measured rotation is 90 degrees, the actual rotation can be expressed by a probability distribution proportional to sin^2 of the rotation angle. This tells Eve what the probability distribution is after each individual measurement. In the case of a circulation count of 2, she will have two such measurements, each giving a probability distribution for the two angles that were used. She can use these to then calculate the probability that the two angles sum to 90 or to 180 degrees. (An equivalent way to say this is that the sum, modulo 180 degrees, will be 0 or 90.) This will produce relative probabilities for the two possible bit values being emitted by that station. Call the probability distributions for the two measurements f0(w0) and f1(w1), where w0 and w1 are the two rotation angles and f0 and f1 are either cos^2 or sin^2. The probability that a given angle x is the sum of w0 and w1 (mod 180 degrees) will be proportional to the integral from 0 to 180 degrees of f0(w)f1(x-w)dw. That is, for each possible first angle w, the second angle must be x-w in order for them to add to x, and the probabilty of this happening is the product of f0(w) times f1(x-w). We want to evaluate this for x = 90 degrees and x = 0 degrees, and compare the two results. There are a number of symmetries of cos^2 and sin^2 which simplify this: cos^2(0-x) = cos^2(x) sin^2(0-x) = sin^2(x) cos^2(90-x) = sin^2(x) sin^2(90-x) = cos^2(x) Putting all this together, we can consider the four possible cases for the measured rotations. Each rotation is measured as 0 degrees or 90 degrees, which correspond to bit values
Re: The Shining Cryptographers Net
At 10:10 AM 1/20/01 -0800, [EMAIL PROTECTED] wrote: This analysis will focus on one particular kind of attack. Eve will make measurements of the photon polarization angle as it travels through the network and attempt to deduce information about the signals being sent by the participants. This appears to be a correct analysis of this particular attack. However, this is not Eve's strongest attack. So let's move the focus. A much better strategy for Eve is to _not_ make so many measurements. Rather, she should preserve the photon in all its analog, quantum-mechanical glory and recirculate it back to Bob, bypassing the other participants in the ring. Then Bob, in blissful ignorance, will decrypt his own signal. We have reduced the problem to the trivial case of the one-person ring; in such a ring it is obvious whether Bob sent a message or not. The contrast with the conventional Dining Cryptographer's ring is illuminating: In the DC ring, Bob depends on somebody else (indeed everybody else) to undo the transformations that he applies, so that if Eve attempts to spoof, short-circuit, or partition the ring, the results will be cryptologically random. The SC net appears to have a problem at the algorithm level (not at the physics level), namely it doesn't involve the other participants in the right way. It is too easy for Eve to simulate the other participants. This could be patched up by adding macroscopic (i.e. non-quantum) authentication protocols, but the cost of doing this would probably be comparable to the cost of implementing the classical DC network. So it's not clear what is the advantage of the SC network. One could imagine a hybrid scheme: 1) The participants exchange keys, as in the conventional DC net, and 2) The participants process the signal by rotating the polarization, or shifting the quantum phase, or other unconventional, non-Boolean transformations. 3) They could recirculate the signal C1 times if desired. Right now this seems like a solution in search of a problem; that is, I don't know any problems for which the solution requires ideas (2) and (3), but they seem like interesting ideas that should be good for something.
Re: The Shining Cryptographers Net
On Thu, 18 Jan 2001 [EMAIL PROTECTED] wrote: Or does somebody have a good defense against this hyper-active attack? The only thing I can suggest would be if the rotation stations could somehow count or limit the number of photons going through so that they would know when there were extra. I think this is possible in theory; whether it can be done in practice is questionable. Hm? As far as I know there's no way to detect (count) a photon that doesn't affect its quantum state in some way that can be later detected. In this case, that's not an option, because you're trying to use the quantum state to transmit information. If you fiddle with it by trying to count photons, the information will change. Is there a detector that affects some *other* part of the Quantum state, and won't mess with the polarization? Another idea would be for the stations to actually absorb the photon in some manner that preserved its polarization, and then to re-emit it. These could be primed to pass only a single photon. Now you are talking serious voodoo. I don't think that this can be done this year. Maybe not this decade. Bear
Re: The Shining Cryptographers Net
At 02:04 PM 1/18/01 -0800, [EMAIL PROTECTED] wrote: the rotation stations could somehow count or limit the number of photons going through so that they would know when there were extra. I think this is possible in theory; Right, it is. Here's a Gedankenexperiment: temporarily trap the signal in a cylindrical waveguide resonator (organ pipe). The pressure on the end-caps is proportional to photon number and independent of polarization angle. From this we conclude we can measure number in a way that commutes with polarization. I went overboard when previously I said "any" attempt at integrity-checking would mess up the signal. Still, integrity-checking of a single photon would be hard. I don't think she could learn much with a single photon, I'm not so sure about that. Remember, photon counters (which measure A_dagger A) are not the only measuring devices in the world. There are also voltmeters (which measure A_dagger plus A). For low-amplitude analog signals, the voltmeter is vastly more informative. I have not yet cobbled up a believable apparatus for measuring the polarization angle of a single photon, but I don't think it would be terribly hard to do so.
Re: The Shining Cryptographers Net
Ray Dillinger wrote, quoting me: Another idea would be for the stations to actually absorb the photon in some manner that preserved its polarization, and then to re-emit it. These could be primed to pass only a single photon. Now you are talking serious voodoo. I don't think that this can be done this year. Maybe not this decade. Actually there is a report out just today that could be a big step towards this capability. From http://www.aip.org/physnews/update/521-1.html: For the first time, physicists in two separate laboratories have effectively brought a light pulse to a stop. In the process, physicists have accomplished another first: the non-destructive and reversible conversion of the information carried by light into a coherent atomic form. This experiment captures light and transforms it into an excited gas state, in a reversible way, so that the original light pulse can restored at a later time: Usually photons (the quanta of light) are absorbed by atoms, destroying the information carried by the light. With the present method, in principle, no information in the light pulse is lost. If this applies to the polarization information as well then it would be close to what I called for above. Then you'd still need some way to be able to distinguish how many photons' worth of energy you'd caught in your gas, or to limit the emission to only a single photon. If so then this would be a "single photon" filter. So perhaps the idea is not as far-fetched as it sounds. Hal
Re: The Shining Cryptographers Net
In the `traditional' DC Net, how is absence of a message detected? If this is a seperately distinguishable outcome of a round, each round may return three outcomes: `0', `1' and `none'. To represent these quantum mechanically, you need at least a 3-state quantum system (to make the outcomes perfectly distinguishable). In the proposals so far (for using quantum physics to protect the anonymity of the sender), the quarantee is not that the sender is always anonymous. It's merely that any eavesdropping will be detected. This is a weaker guarantee. Moreover, it is not clear how in the current proposal, eavesdropping is distinguished from collisions (ie two cryptographers trying to send simultaneously). Also, using a photon circulation scheme implies that _one_ cryptographer is made responsible for firing the photon. This gives him extra power (eg firing two photons simultaneously...). The idea to use quantum physics to get rid of the shared randomness is nice. I'm not sure that the approach outlined by Hal can be made to work. Jaap-Henk -- Jaap-Henk Hoepman | Come sail your ships around me Dept. of Computer Science | And burn your bridges down University of Twente | Nick Cave - "Ship Song" Email: [EMAIL PROTECTED] === WWW: www.cs.utwente.nl/~hoepman Phone: +31 53 4893795 === Secr: +31 53 4893770 === Fax: +31 53 4894590 PGP ID: 0xF52E26DD Fingerprint: 1AED DDEB C7F1 DBB3 0556 4732 4217 ABEF
Re: The Shining Cryptographers Net
Jaap-Henk Hoepman, [EMAIL PROTECTED], writes: In the `traditional' DC Net, how is absence of a message detected? A practical implementation of a DC Net would require multiple protocol layers. The lowest layer is the "raw" DC net itself, which has the property that each person sends a bit stream all the time, and the net produces the XOR of all their bit streams. To turn this into a practical anonymous transmission net you need a higher level protocol. One approach is to have a reservation phase where someone who wants to transmit outputs a 1 at a random location in a block of reservation bits which is large enough that collision is unlikely. Then the various transmitters send their messages in the order that their 1's appear (they each know which 1 is theirs so they know the order). Chaum's original paper is available online at http://www.nyx.net/~awestrop/crypt/diningcr.htm. The PhD thesis of Jurjen Bos discusses some of the protocol issues in much more detail. There were several papers on the topic published at Eurocrypt 89, including http://www.semper.org/sirene/publ/WaPf1_89DiscoEngl.ps.gz and http://www.semper.org/sirene/publ/Waid_90fail-stopDC.ps.gz. If this is a seperately distinguishable outcome of a round, each round may return three outcomes: `0', `1' and `none'. To represent these quantum mechanically, you need at least a 3-state quantum system (to make the outcomes perfectly distinguishable). Much of the work on higher level protocols would apply to the SC Net as well as to the DC Net so a two state system should be adequate. However if the two state system can be established to be secure, perhaps a three state system could be developed and could avoid the need for higher level protocols to some degree. In the proposals so far (for using quantum physics to protect the anonymity of the sender), the quarantee is not that the sender is always anonymous. It's merely that any eavesdropping will be detected. This is a weaker guarantee. Yes, good point, although we can in principle adjust things so that the eavesdropping will be detected *before* Eve learns anything significant about the sending party. In other words, for each photon she disrupts she learns only a tiny amount of information about where it came from. She could be caught before she had learned enough to break the anonymity. Moreover, it is not clear how in the current proposal, eavesdropping is distinguished from collisions (ie two cryptographers trying to send simultaneously). The higher level protocols are designed to largely prevent collisions. If those are used, Eve would need to do her measurements during a slot reserved for one party to transmit. She would garble the transmitted data, which would be detectable. This would not resemble an accidental collision, but rather intentional disruption by a member of the group. The higher level protocols do have mechanisms to recover from disruption, but I don't think those parts would work on the SC Net since they are cryptographic in nature. More work would be needed on ways of responding to evidence of eavesdropping, but at least it can't go on unnoticed. Also, using a photon circulation scheme implies that _one_ cryptographer is made responsible for firing the photon. This gives him extra power (eg firing two photons simultaneously...). Yes, that could be bad. I think it would be possible in principle for the parties to detect the presence of multiple photons without altering their polarization, but it would present practical difficulties. The idea to use quantum physics to get rid of the shared randomness is nice. I'm not sure that the approach outlined by Hal can be made to work. It is still in the early stages of development. I appreciate the many helpful comments. Hal
Re: The Shining Cryptographers Net
At 11:20 PM 1/17/01 -0800, [EMAIL PROTECTED] wrote in part: The probability that Eve's measurement will leave the result unchanged is 3/4, and therefore the probability that she will perturb the result is 1/4. OK so far. Then, for the case of two measurements, Eve's chances of perturbing the measurement have increased from 1/4 to 3/8 by doing two measurements rather than one. Increasing the number of measurements to three reduces the chance of success to 9/16, with a 7/16 chance of perturbation. That's not the right way to analyze it. My previous remarks on this subject were partly unclear and partly wrong... and in any case there is a better way to look at it. So let me try again from scratch: There is one distinguished participant; call him Arthur because he sits at the head of the Round Table. In broad outline, the procedure is: a) Arthur emits a photon b) The photon circulates around the ring C times c) Arthur catches the photon and publishes the final result. It simplifies the discussion somewhat if Arthur is not one of the participants; he just reaches in to insert the photon at the beginning, and reaches in to extract it at the end. Note that each of the participants is supposed to just rotate the photon. They just choose the settings on their rotators (Kerr-effect cells or whatever) and wait for the photon to whizz through. They cannot do any additional processing without messing up the algorithm. In particular, any attempt at integrity checking, no matter how well-intentioned, would damage the signal the same way eavesdropping would. We can summarize what we know so far: 1) The algorithm uses physics to more-or-less exclude passive attacks; that is its strength. 2) On the other side of the same coin, this introduces a weakness: it limits the ability to detect active attacks. Therefore, if Eve is smart, she will use an active attack. So let's consider an aggressive, hyper-active attack. Eve need not limit herself to snooping "the signal". What she really wants to know is the "state of mind" of the participants, i.e. the settings of their rotators. If she knows that, she knows everything. She can, as a final step, synthesize a mockup of the final result and feed it to Arthur. Eve can mount a known-plaintext attack against each rotator. That is, she can send in a known photon, or if necessary multiple known photons, and see what comes out. It would not be easy for the participants to detect such an attack directly. They could defend against it to some degree by pre-arranging strict timing requirements on their signals... but they would need to keep these arrangements secret from Eve. At this point AFAICT the whole scheme is in danger of losing its elegance, and perhaps of losing its raison d'etre. Or does somebody have a good defense against this hyper-active attack?
Re: The Shining Cryptographers Net
John Denker, [EMAIL PROTECTED], writes: Eve need not limit herself to snooping "the signal". What she really wants to know is the "state of mind" of the participants, i.e. the settings of their rotators. If she knows that, she knows everything. She can, as a final step, synthesize a mockup of the final result and feed it to Arthur. Eve can mount a known-plaintext attack against each rotator. That is, she can send in a known photon, or if necessary multiple known photons, and see what comes out. Yes, this does seem to be a powerful attack. I don't think she could learn much with a single photon, but if she could send multiple photons through while the rotator was still set up she could learn as much as she wanted about the rotation angle. Plus if she were using her own photons, the circulating photon would not be affected and her attack would not be detected. It would not be easy for the participants to detect such an attack directly. They could defend against it to some degree by pre-arranging strict timing requirements on their signals... but they would need to keep these arrangements secret from Eve. At this point AFAICT the whole scheme is in danger of losing its elegance, and perhaps of losing its raison d'etre. Or does somebody have a good defense against this hyper-active attack? The only thing I can suggest would be if the rotation stations could somehow count or limit the number of photons going through so that they would know when there were extra. I think this is possible in theory; whether it can be done in practice is questionable. One idea would be to use strict but public timing for the circulating photon, only opening the gate for long enough to send that one through. Eve knows when the gate opens, but to get hers through she has to send them at the same time as the circulating one. If we then use a nonlinear material that can only handle one photon at a time, it might be noticeable when two or more were present. Another idea would be for the stations to actually absorb the photon in some manner that preserved its polarization, and then to re-emit it. These could be primed to pass only a single photon. I'm sure both of these ideas have serious practical difficulties but perhaps something along these lines could be made to work. Hal
Re: The Shining Cryptographers Net
At 08:35 PM 1/16/01 -0800, [EMAIL PROTECTED] wrote:
To recap, a group of cryptographers wants to communicate anonymously,
without the sender of a message being traced.
To recap in more detail, as I understand it:
1) The desired result is a plain broadcast message, open to the world
(including Eve).
2) Another desired property is that nobody can determine who in the
group originated the message.
3a) For the original dining philosophers, there is a first phase where
participants exchange random keys pairwise in private.
3b) The point of _shining_ philosophers is that this phase is absent.
4) Thereafter there is a second phase wherein open messages are passed
among the participants. Eve can tap these messages in any way permitted by
the laws of physics.
If this is not a correct statement of the problem, please clarify.
In the case of circulation counts greater than 1, each individual rotation
can be chosen in such a way that it is uniformly distributed between 0
and 180 degrees.
Fine. We are using the physics of photons to do modular arithmetic, mod
180 degrees.
Now we asssume that Eve, the eavesdropper, has corrupted some of the
cryptographers and is able to make them behave improperly. She wants
to determine who is sending a given message by making extra measurements
on the photon as it passes through the stations she has corrupted.
IMHO that's an odd threat model. If she has corrupted the actual sender,
the problem is trivial. If she has corrupted all stations except the
actual sender, the problem is trivial. If she has corrupted M out of the N
total stations, she can narrow down the sender to one of the N-M
uncorrupted stations.
Based on Hal's statements below, I assume the threat model also includes
attempts by Eve to tap the phase-2 communications between the
participants. I assume this was just accidentally not mentioned above.
Note that photon polarization is a two-state system. Once a basis has
been chosen for measuring the polarization, any such measurement collapses
the photon into one of the two pure states of that basis. Eve has the
power to choose the basis she will use for her measurement, but she cannot
avoid collapsing the photon state.
That is not a fully correct statement of the physics. We agree that there
exist a class of measurement operators ("strong" measurements) which do
behave as described above. However, there also exist "weak" measurements
which couple only weakly to the signal being measured. They return less
information than a strong measurement, and perturb the signal to a lesser
degree.
This is important because any real-world quantum computer would have to
make allowances for imperfections in its own apparatus. A skillful
eavesdropper could conceal her actions by making them look like only a
small increase in the natural noise.
Classical algorithms do not share the same vulnerability, since they can
make sure that each piece of the apparatus is very reliable.
Eve's effect on the photon does not depend on where
she makes the measurement, and for simplicity we can consider the case
where the measures the photon immediately before it is measured by the
final cryptographer.
This seems to overlook the possibility of multiple weak
measurements. Beware, the laws of physics do not exclude this.
The first result I have is that ...
The aforementioned quibbles about the physics, and about the threat model,
somewhat undermine the conclusions. It may be possible to re-establish the
main conclusions, but it appears a more detailed argument is necessary.
Re: The Shining Cryptographers Net
John Denker writes:
At 08:35 PM 1/16/01 -0800, [EMAIL PROTECTED] wrote:
To recap, a group of cryptographers wants to communicate anonymously,
without the sender of a message being traced.
To recap in more detail, as I understand it:
1) The desired result is a plain broadcast message, open to the world
(including Eve).
2) Another desired property is that nobody can determine who in the
group originated the message.
3a) For the original dining philosophers, there is a first phase where
participants exchange random keys pairwise in private.
3b) The point of _shining_ philosophers is that this phase is absent.
Yes, this is the idea.
4) Thereafter there is a second phase wherein open messages are passed
among the participants. Eve can tap these messages in any way permitted by
the laws of physics.
I did not intend to incorporate an extra phase, except possibly in
response to an indication that someone is tapping the network. In normal
operation no extra phase is needed.
With DC Nets there needs to be a similar "damage response" phase,
although in that model the threat is that someone is not cooperating
by sending noise when they aren't supposed to. There has been various
work done on tracing disruptors. Similar extensions to the simple
Shining Cryptographers net would be needed once actual evidence of
Eve's manipulation is detected. (In addition the SC Net is equally as
vulnerable to disruptors as the DC Net, of course.)
Now we asssume that Eve, the eavesdropper, has corrupted some of the
cryptographers and is able to make them behave improperly. She wants
to determine who is sending a given message by making extra measurements
on the photon as it passes through the stations she has corrupted.
IMHO that's an odd threat model. If she has corrupted the actual sender,
the problem is trivial. If she has corrupted all stations except the
actual sender, the problem is trivial. If she has corrupted M out of the N
total stations, she can narrow down the sender to one of the N-M
uncorrupted stations.
This is the same threat model as in the DC Net. As you say, obviously
if she has corrupted M out of N stations she knows if the sender is in
the remainder. The question is, can she learn more? In many cases she
can.
For example some variants of the DC Net do not have every pair of
cryptographers sharing a secret string. A simplified version positions
the cryptographers in a ring and has each cryptographer share a secret
only with his two neighbors. In that case corrupting the two neighbors
will reveal his secrets. Generally, if the cryptographers are vertexes
in a graph, and edges are drawn between any two cryptographers who
share a secret, then when Eve corrupts some set of cryptographers she
partitions the graph into what is left if we erase the edges coming from
the corrupted cryptographers. The remaining sub-graphs each represent
a set of cryptographers among whom Eve cannot distinguish the originator
of a message, although she can tell which sub-graph it is coming from.
This is the flavor of the DC Net analysis in the literature, and I am
adopting the same threat model to consider what Eve can learn beyond
the brute facts of whether her corrupted cryptographers are sending.
In fact she can learn more than this.
Based on Hal's statements below, I assume the threat model also includes
attempts by Eve to tap the phase-2 communications between the
participants. I assume this was just accidentally not mentioned above.
I'm not clear what is meant by phase-2 communication.
Note that photon polarization is a two-state system. Once a basis has
been chosen for measuring the polarization, any such measurement collapses
the photon into one of the two pure states of that basis. Eve has the
power to choose the basis she will use for her measurement, but she cannot
avoid collapsing the photon state.
That is not a fully correct statement of the physics. We agree that there
exist a class of measurement operators ("strong" measurements) which do
behave as described above. However, there also exist "weak" measurements
which couple only weakly to the signal being measured. They return less
information than a strong measurement, and perturb the signal to a lesser
degree.
This is important because any real-world quantum computer would have to
make allowances for imperfections in its own apparatus. A skillful
eavesdropper could conceal her actions by making them look like only a
small increase in the natural noise.
That's a good point, which I am nevertheless going to ignore for now
(because I'm having enough problems getting good answers in the case
of perfect measurements). By weakening her coupling with the measured
system Eve can reduce her perturbation, at the cost of also reducing
the quality of the information she learns. My guess is that she cannot
exploit this tradeoff, that any reduction in perturbation will be met
Re: The Shining Cryptographers Net
At 10:35 PM 1/15/01 -0800, [EMAIL PROTECTED] wrote: Here is a rough idea for a quantum-cryptography variant on the DC Net, the Dining Cryptographers Net invented by David Chaum. The photon starts off with vertical polarization. Each cryptographer manages a station through which the photon passes, which can be configured to either rotate the photon polarization 90 degrees, or to leave it alone. At the end, the photon polarization is measured by attempting to pass it through a vertical polarizer. If it passes, the photon has not been rotated, while if it is absorbed, it was rotated. In this way the message bit is recovered. Anonymity derives from the inability of an attacker to measure the photon without destroying it, unless he can guess its state. Hmmm. This seems like a mistake in the physics. If the attacker, Eve, knows that a photon has either vertical (0 degrees) or horizontal (90 degrees) polarization, she can measure it at any point in the ring without destroying any information, and therefore without risk of detection. In fancy physics language, these two measurements are "compatible". Measurement operators can be compatible a) if they are completely unrelated, or b) if they are completely correlated. Case (b) applies here; they are 100% anti-correlated. One can write the operator equation for projection onto the two polarization states: P_0 + P_90 = 1 and one can implement this in practice to high accuracy using e.g. a Brewster-angle beam splitter. Quantum cryptography relies on measurements of _incompatible_ variables. In this case polarization along a 45-degree axis would be an example of something incompatible with measurements along the vertical and horizontal axes. It may or may not be possible to salvage the underlying idea of "shining cryptographers" by using 45-degree rotations (not just 90-degree rotations). Alas I don't immediately see how.
Re: The Shining Cryptographers Net
John Denker, [EMAIL PROTECTED], writes: At 10:35 PM 1/15/01 -0800, [EMAIL PROTECTED] wrote: Here is a rough idea for a quantum-cryptography variant on the DC Net, the Dining Cryptographers Net invented by David Chaum. Hmmm. This seems like a mistake in the physics. If the attacker, Eve, knows that a photon has either vertical (0 degrees) or horizontal (90 degrees) polarization, she can measure it at any point in the ring without destroying any information, and therefore without risk of detection. Yes, I see that John is right. A conceptually simple method is to measure the photon using a polarizer. If the photon is absorbed, the eavesdropper knows its polarization state and can simply emit a new photon with the required state. In either case the measurement is not detected. The version with random orientations should still be somewhat resistant to such measurements. Eve would not know how to orient her measuring apparatus and so would likely perturb the photon. The effect would largely be to introduce noise into the output, which should be detectable by the participants at some level. Hal
Re: The Shining Cryptographers Net
Let me follow up on the Shining Cryptographers idea with a more careful analysis of the last proposal I made in my earlier posting. To recap, a group of cryptographers wants to communicate anonymously, without the sender of a message being traced. They do so by circulating a photon around a ring which passes through stations controlled by each cryptographer. Within the station the cryptographers control equipment which can rotate the photon's polarization by a desired amount. The photon is injected with some particular polarization, and at the end the polarization is measured. If the polarization has not changed the group is sending a 0 (which includes the possibility of sending nothing at all). If the polarization is turned by 90 degrees someone in the group is sending a 1. In some variants the photon travels around the group multiple times before it is measured. Let us call this number of times the "circulation count". We assume that each cryptographer can rotate the photon by separate amounts each circulation. The proposal is that if a cryptographer wants to send a 0, he rotates the photon by amounts which add up to an even multiple of 90 degrees, and if he wants to send a 1 he rotates the photon by amounts which add to an odd multiple of 90 degrees. If the circulation count is 1 this means that he rotates the photon by exactly 90 degrees to send a 1, and not at all to send a 0. (Note that rotating a photon by 180 degrees is the same as not rotating it at all.) In the case of circulation counts greater than 1, each individual rotation can be chosen in such a way that it is uniformly distributed between 0 and 180 degrees. With a circulation count of n, the first n-1 rotations can be chosen independently, and the last one is then determined by the requirement to add to the proper multiple of 90 degrees. Because all the others are chosen uniformly, the result is that the nth rotation amount is also uniformly randomly distributed in the 0-180 range. Hence each individual rotation considered on its own will be unbiased, when the circulation count is greater than 1. This is the algorithm the cryptographers use. Henceforth we will assume circulation count is greater than 1 except where noted. Now we asssume that Eve, the eavesdropper, has corrupted some of the cryptographers and is able to make them behave improperly. She wants to determine who is sending a given message by making extra measurements on the photon as it passes through the stations she has corrupted. Note that photon polarization is a two-state system. Once a basis has been chosen for measuring the polarization, any such measurement collapses the photon into one of the two pure states of that basis. Eve has the power to choose the basis she will use for her measurement, but she cannot avoid collapsing the photon state. The first result I have is that any such measurement by Eve (where she does not already know the input) will change the final measured photon state with probability 1/2. This is true regardless of how she chooses her basis. Once the photon has been rotated by an agent not controlled by Eve, she does not have any information about its polarization state. As noted above, the individual rotations are completely random. Hence any such measurement will collapse the wave function into the basis state chosen by Eve. Once she makes such a measurement, subsequent rotations will be based on the new state into which the photon was collapsed by Eve, rather than the state before it was measured. When the photon reaches the end and is measured, it will be rotated compared to what it was supposed to be, and the amount of rotation is exactly the amount by which Eve perturbed the photon by measuring. It follows, then, that Eve's effect on the photon does not depend on where she makes the measurement, and for simplicity we can consider the case where the measures the photon immediately before it is measured by the final cryptographer. In that case the photon enters Eve's apparatus in a pure state for the final cryptographer measurement. Eve measures it into a randomly rotated state, and it is then measured by the cryptographer. It is simple to show that in this case the chance that the proper result will occur is 1/2. Therefore any measurement made by Eve will perturb the result with probability 1/2. Essentially this means that the final cryptographer measurement might as well be made on a random photon. In effect, all of the information carried by the photon is lost. This is good news and bad news for Eve. The bad news is that any attempt she makes to measure the photon state will be detected with probability 1/2. She will therefore not be able to make very many measurements without being caught. (In the sequel we will see how effective her measurements can be.) The good news for Eve is that she can make as many measurements as she wants without making things worse for herself. Making even a single
