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
