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 by an equally severe reduction in information content of the measurement. However a more complete analysis would certainly have to consider this possibility. > >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. My result (about error probability 1/2) was wrong, anyway, as I should have realized because the worst case is for Eve to measure at a 45 degree angle, and even then there is a 1/2 probability that the final measurement will be right. In all other cases her axes are offset by less than 45 degrees and so there is a better probability than that. So the average must be greater than 1/2, and in fact with a single measurement there is a 3/4 chance that the final measurement result will be as it should have been. This changes the conclusions of my message, so I will post another version with corrected math. Hal

- The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net John Denker
- Re: The Shining Cryptographers Net Jaap-Henk Hoepman
- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net John Denker
- Re: The Shining Cryptographers Net John Denker
- Re: The Shining Cryptographers Net John Denker

- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net Jaap-Henk Hoepman

- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net Bill Stewart

- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net Ray Dillinger
- Re: The Shining Cryptographers Net John Denker

- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net hal
- Re: The Shining Cryptographers Net hal