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
bit values of 0 or 1. In each case we can calculate the probability p(0) and p(1) that the station was emitting a 0 or 1 by using the following integrands: Measured p(0) p(1) - 0 0 cos^2 cos^2cos^2 sin^2 0 1 cos^2 sin^2cos^2 cos^2 1 0 sin^2 cos^2sin^2 sin^2 1 1 sin^2 sin^2sin^2 cos^2 The p(0) and p(1) entries are integrated from 0 to 180 degrees. Note that these are all ignoring a constant factor of proportionality, which won't affect the final results. I calculated these manually but checked them with Mathematica, and the results are: Measured p(0) p(1) - 0 03 pi / 8 1 pi / 8 0 11 pi / 8 3 pi / 8 1 01 pi / 8 3 pi / 8 1 13 pi / 8 1 pi / 8 Since we know that the actual rotation is either the 0 or 1 amount, the ratios between these probabilities are the actual relative probabilities of the two possible outcomes: Measured p(0) p(1) - 0 0 3/4 1/4 0 1 1/4 3/4 1 0 1/4 3/4 1 1 3/4 1/4 This is the final result. If we measure 0 rotations both times, there is a 3/4 probability that the station is emitting a 0 and only 1/4 that it is emitting a 1. The same result is true if we measure a 1 both times. However if we get opposing results on the two measurements, there is a 3/4 chance that the station is emitting a 1. Eve is therefore able to make a good guess about the actual data being emitted by the particular station, with a 3/4 chance of success, when the circulation count is 2. Extending the analysis to larger circulation counts is similar. I will skip the math here, and show the results (along with the ones from above): Circulation countHighest prob Lowest prob - 1 1 0 2 3/4 1/4 3 5/8 3/8 4 9/167/16 517/32 15/32 This is as far as I have calculated it, using Mathematica. However the pattern is clear: the denominator multiplies by 2 each time, and the two alternative numerators are the odd numbers which make the values closest to 1/2. Thus we see that each addition of one to the circulation count reduces Eve's advantage by a factor of 2. At the same time her chance of being caught remains about 1/2 per eavesdropping attempt. By increasing the circulation count, the risk to Eve of gaining any specific amount of information can therefore be made arbitrarily large. Hal
Re: What's Wrong With Content Protection
I will make a partial rebuttal to John Gilmore's article on the problems with content protection schemes. I distinguish between schemes which are enforced by legislation such as the Digital Millennium Copyright Act (DMCA), versus schemes which rely on technological means and market competition to attract customers. John attacks both kinds of mechanisms equally. But there is a fundamental difference between them. The DMCA and similar laws are the real problem in this area. They allow companies to eliminate competition and are running roughshod over free speech rights. I applaud the efforts of John, the EFF, and other parties in working to overturn or limit the range of applicability of these laws. But when we deal with content protection which is provided on a competitive basis in the marketplace, it is another matter. In that case it is ultimately a question of satisfying the desires of the consumer which determines which products will succeed. When DVD players were first released there was an alternative scheme called DIVX which would provide limitations on your viewing of the DVD disks you bought. In exchange, you could purchase the disks for about $5 rather than $20 and up for conventional disks. Nevertheless there was strong consumer backlash against the device and it ultimately failed in the marketplace. Shortly, portable MP3 players will have the option of providing support for the mechanisms designed by the Secure Digital Music Initiative (SDMI). To succeed, SDMI players must convince consumers that they are more useful to them than MP3 players which lack these restrictions. Only if consumers prefer devices which enforce content protection will these devices succeed. The nature of the marketplace means that there will inherently be a competition between the various technologies which can be used. In a free market, if content protection wins, it is because people are more willing to buy it than the alternatives. When companies develop content protection technologies, it is only their own well being which is threatened. The technology may fail, as DIVX did, which only hurts the companies. Or it may succeed, in which case consumers prefer the the new technology to the alternatives. We should not attempt to second guess consumer preferences and say that they are making the wrong decision for themselves. We should respect the rights of the people in the marketplace to make their own decisions. I understand that John and others worry that consumers will not actually be able to make choices and decisions, because all products available to them will have content protection built in. But this amounts to the belief that industry will form a cartel which seeks to sell products which make consumers unhappy, intentionally delivering devices which consumers dislike, smug in their belief that their cartel is 100% effective and that no competition is possible. Without the enforcement of laws like the DMCA, such a situation is highly unstable. There is a huge incentive to produce devices which don't observe the restrictions and which give consumers more power. These devices will be popular with consumers and the cartel will be broken. The key to allowing competition in the marketplace is to eliminate laws like DMCA which allow manufacturers to enforce limitations on their competitors. That is why John's and others' work is so important in fighting these laws. Take away these legal teeth and force the companies to compete in a free and fair market for consumer dollars, and we will see companies supplying devices which consumers want. This is where I believe John should be focusing his energy. Working to oppose technical standards for content protection is a waste of time, by comparison. It dilutes his efforts and muddies the philosophical principles involved. When they judge a technology only on the basis of how much it will restrict what they can do, it makes it appear that opponents of content protection are interested only in getting for free content which others have worked hard to produce. A superior principle says, yes, you can create content protection systems, and you can try to convince consumers that their best interests are served by adopting them. Let all parties compete freely and openly and let the best system win. Judge their activities by the means and not by the ends. If you are truly confident that a world without content protection is the best, trust consumers to come to understand and believe this as well. Don't try to use the legal system yourself to force this outcome. Hal Finney
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
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
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
on 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
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
n a single measurement effectively randomizes the results. Making multiple measurements can't randomize them any further, as you can't get any more random on a two state measurement than 50-50. Therefore, as long as Eve is intervening, she should feel free to bring all the power she can to bear on a single photon, measuring it at every opportunity, to extract the maximum information possible. In a subsequent message I will analyze how much information Eve obtains by doing measurements immediately before and after a target cryptographer has rotated the photon on each circulation. Hal
The Shining Cryptographers Net
The Shining Cryptographers Net Here is a rough idea for a quantum-cryptography variant on the DC Net, the Dining Cryptographers Net invented by David Chaum. It does not provide as much anonymity as the DC Net, but perhaps will inspire others to look for a more powerful design. In a simple version of the DC Net, each pair of cryptographers initially shares a unique, secret random string (or perhaps they share a seed for a stream cipher). A token carrying a bit is passed around the net, and each cryptographer who has nothing to say XORs the bit with the XOR of the next bit of each of his random strings. After passing through all the cryptographers, each random bit has been XORed in twice (once for each of the two cryptographers who share the string holding that bit) and so the bit value has not changed in total. If a cryptographer wants to send a message, when he does his XOR he also XORs in the next bit of the message. At the end the value of the message bit will equal the bit which was sent (as long as two people don't try to talk at once). The source of the message is hidden as each party sees only random data arriving. For the quantum version, a photon is passed around the ring instead of a logical bit. These are thus dubbed the Shining Cryptographers. 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. If the cryptographer has nothing to say he leaves the photon alone. If he wants to say something he uses the next bit of his message to determine whether to rotate the photon 90 degrees or not. 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. The attacker can confirm a guess at the state, but as soon as he guesses wrong, the photon will be destroyed. This will allow the attacker's presence to be detected as soon as he makes a wrong guess. Unfortunately the attacker may be able to get lucky and acquire considerable information before he is detected. Here is a way to strengthen the anonymity. Let the photon go around the ring twice. Each cryptographer randomly chooses whether to rotate the photon or leave it alone. He does the same transformation both times, if he has nothing to say. These will then cancel out. However if he wishes to transmit a 1, he does a different transformation each time, so there is no canceling. In fact with this system, the cryptographers are not restricted to 90 degree rotations, but they can choose any pair of rotations which will add as required. The attacker now has to guess how much his target is going to rotate the beam and put probes before and after, and hope he guessed right. In itself this tells him nothing. He has to further guess whether the target will rotate by the same or different amount on the second pass, adjust his probes accordingly, and again hope for a correct guess. The same principle can be extended by letting the photon go around the ring multiple times. Players must arrange to rotate the photon by varying amounts which add to an even multiple of 90 degrees if they are not sending, or an odd multiple if they are sending a 1. By increasing the number of times through the loop, the chance of an attacker guessing right on every transformation can be reduced to a low level. Hal Finney
Re: Weak user keys, strong servers.
You didn't specify whether q was the same or different for everyone. q must be different for every person, because if it were the same, each user could deduce G^q by knowing p and G^(p+q), and from that they can find other people's p values. You could have a slightly simpler system by just letting G^q be the user's public key, and also retain a password for each user that authenticates him. You don't need a numerical p value, just a password (and use a secure authentication system like SPEKE). This is essentially what DPJ suggested, except that instead of downloading q to the user, your system has the server exponentiate by q upon request, which doesn't reveal q to a possibly insecure client. However if you are worried about this, you still have a problem, as it reveals the password (or the p value in your original system). If stolen, this would still allow thiefs to decrypt future data, by connecting to the server with the stolen password (p) and requesting decryption services. This is a slightly riskier attack as the connection request might be traced if the true owner becomes suspicious. It's a little unclear what your security model is, whether the client is trusted or not. Hal
