Re: quantum hype
[EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Dave Howe Peter Fairbrother may well be in possession of a break for the QC hard problem - his last post stated there was a way to clone photons with high accuracy in retention of their polarization [SNIP] Not a break at all. The physical limit for cloning is 5/6ths of the bits will clone true. Alice need only send 6 bits for every one bit desired to assure Eve has zero information. For a 256-bit key negotiation, Alice sends 1536 bits and hashes it down to 256 bits for the key. I've just discovered that that won't work. Eve can get sufficient information to make any classical error correction or entropy distillation techniques unuseable. See: http://www.gap-optique.unige.ch/Publications/Pdf/9611041.pdf You have to use QPA instead, which has far too many theoretical assumptions for my trust. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
I promised some links about the 5/6 cloning figure. You've had a few experimental ones, here are some theory ones. Cloning machines: http://www.fi.muni.cz/usr/buzek/mypapers/96pra1844.pdf Theoretically optimal cloning machines: http://www.gap-optique.unige.ch/Publications/Pdf/PRL02153.pdf 1/6 disturbance is theoretically optimal, both as a QC interception strategy and it's an optimal cloning machine: http://www.gap-optique.unige.ch/Publications/Pdf/PRA04238.pdf A different approach to the 1/6 figure (2/3 cloned correctly, the 1/3 imperfectly cloned still has a 50% chance of being right): http://arxiv.org/PS_cache/quant-ph/pdf/0012/0012121.pdf That lot is pretty much indisputed... ...except for the optimal part; and that's a sideways argument anyway - the math and physics theory are right as far as they go, just that they didn't consider everything. It may be possible to clone better than those optimal solutions, especially in the classic QC case, or get more information like which photons were cloned correctly, and perhaps to as near perfection as you like, but that is in dispute. Actually it's a pretty friendly dispute, people mostly say I don't know*. I'll post some more links on that later. *unless someone mentions non-linear transformations. Which is a different dispute really. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
I'm always stuck on that little step where Alice tells Bob what basis
she used for each photon sent. Tells him how? They need integrity
protection and endpoint authentication for N bits of basis. Is the
quantum trick converting those N bits to N/2 privacy-protected bits
really as exciting as it's made out to be?
They need integrity and data origin authentication, but not
confidentiality. This is what is referred to as the public channel
in QC papers. The standard approach (in papers) is to use universal
hashing. This is just math, with no quantum aspects. But, it enables
authenticating an arbitrarily long string of bits with a single key,
just like one can MAC a long message with HMAC-SHA1.
The difference is that because of the hash construction there are two
key property changes from an HMAC such as used in IPsec:
One can prove that the odds of a forgery are vanishingly small (1 in
$2^{n-1}$ for n bit keys, or something like that), even with an
adversary with infinite computional power.
You can only use the key once (or perhaps twice). Otherwise, an
adversary can recover it. This results in needing a constant stream
of authentication keying material.
Whether these two properties are a good tradeoff from HMAC in practice
for any particular situation and threat model is an interesting
question.
See Universal Classes of Hash Functions, by Carter and Wegman,
Journal of Computer and System Sciences 18, 143-154 (1979) for the
canonical paper on universal hashing.
--
Greg Troxel [EMAIL PROTECTED]
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
I always understood that QKD is based on a hard problem of which the theory of physics says it is impossible to find a solution (if not, then i'd like to know). Then if QKD breaks, the current theory of physics was wrong. On the other hand, if DH or RSA breaks, factoring or the discrete log turn out to be polynomial. This is earthshattering, but doesn't imply our theory of computing was wrong. Whether one is a stronger foundation than the other is really a philosophical question (and a an interesting one too... ;-) Jaap-Henk On Sun, 21 Sep 2003 16:39:17 +0200 martin f krafft [EMAIL PROTECTED] writes: Has anyone *proven* that there is no way to read a quantum bit without altering it? no. its the underlieing hard problem for QC. If there is a solution to any of the Hard Problems, nobody knows about them. right, so it's no better than the arguable hard problem of factoring a 2048 bit number. -- Jaap-Henk Hoepman | I've got sunshine in my pockets Dept. of Computer Science | Brought it back to spray the day University of Nijmegen |Gry Rocket (w) www.cs.kun.nl/~jhh | (m) [EMAIL PROTECTED] (t) +31 24 36 52710/531532 | (f) +31 24 3653137 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: quantum hype
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Dave Howe Peter Fairbrother may well be in possession of a break for the QC hard problem - his last post stated there was a way to clone photons with high accuracy in retention of their polarization [SNIP] Not a break at all. The physical limit for cloning is 5/6ths of the bits will clone true. Alice need only send 6 bits for every one bit desired to assure Eve has zero information. For a 256-bit key negotiation, Alice sends 1536 bits and hashes it down to 256 bits for the key. -Michael Heyman - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
[EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Dave Howe Peter Fairbrother may well be in possession of a break for the QC hard problem - his last post stated there was a way to clone photons with high accuracy in retention of their polarization [SNIP] Not a break at all. The physical limit for cloning is 5/6ths of the bits will clone true. Alice need only send 6 bits for every one bit desired to assure Eve has zero information. For a 256-bit key negotiation, Alice sends 1536 bits and hashes it down to 256 bits for the key. Agreed. It's not a break, though it does make it harder. Many people think the no-cloning theorem says you can't clone photons at all. Most COTS QC gear only works under that false assumption. Then there's the noise/error rates - in practice it's very hard to get 60% single photon detection rates, even under the most favourable conditions, and low error rates are hard to get too. I tend to the opinion, without sufficient justification and knowledge to make it more than an opinion, that most COTS QC products are probably secure today in practice, but claims for theoretical security are overblown. There may be yet another problem which I should mention. First, I'd like to state that I'm not a quantum mechanic, and I find the math and theory quite hard, so don't rely too much on this. I'm not certain that the 5/6 figure is a universal physical limit. It may just be an artifact of the particular unitary transform used in that specific cloning process. It _may_ be possible for the cloner to get some information about which photons were cloned incorrectly. This is tricky, and I don't know if it's right - it involves non-interactive measurement of virtual states, kind of. Another possibility is to imperfectly clone the photon more than once. The no-cloning theorem per se doesn't disallow these, it only disallows perfect cloning, but other physics might. QC's unbreakability isn't based on a hard problem, it's based on the physical impossibility of perfect cloning. But exactly what that impossibility means in practice, I wouldn't like to say. You can't clone every photon. Can you only clone 5/6 of photons? Or 99.9...% of them? It may be the latter. BTW, you can decrease the wavelength of a photon by bouncing it off moving mirrors. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
BTW, you can decrease the wavelength of a photon by bouncing it off moving mirrors. Sure. To double the energy (halve the wavelength), move the mirror at 70% of the speed of light. And since you don't know exactly when the photon is coming, keep it moving at that speed ... - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
At 6:38 PM -0400 9/18/03, John S. Denker wrote: Yes, Mallory can DoS the setup by reading (and thereby trashing) every bit. But Mallory can DoS the setup by chopping out a piece of the cable. The two are equally effective and equally detectable. Chopping is cheaper and easier. Other key-exchange methods such as DH are comparably incapable of solving the DoS problem. So why bring up the issue? It seems to me that because key-exchange methods such as DH only depend on exchanging bits (as opposed to specifying a physical layer), they can rely on a wide variety of techniques to combat DoS. If Bob and Alice can safeguard their local connections to the Internet, its multi-routing properties provide significant DoS protection. Other options available to them include the switched telephone network, wireless, LEO satellites, cybercafes, steganography, HF radio, and even postal mail. In addition, DH users have no need to call attention to themselves by leasing a fiber-optic line. Arnold Reinhold - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
There are lots of types of QC. I'll just mention two. In classic QC Alice generates polarised photons at randomly chosen either + or x polarisations. Bob measures the received photons using a randomly chosen polarisation, and tells Alice whether the measurement polarisation he chose was + or x, on a authenticated but non-secret channel. Alice replies with a list of correct choices, and the shared secret is calculated according as to whether the + polarisations are horizontal or vertical, similar for the slant polarisations. If the channel is authentic then a MitM is hard - but not impossible. The no-cloning theorem is all very well, but physics actually allows imperfect cloning of up to 5/6 of the photons while retaining polarisation, and this should be allowed for as well as the noise calculations. I don't know of any existing OTS equipment that does that. A lasing medium can in theory clone photons with up to 5/6 of them retaining enough polarisation data to use as above, though in practice the noise is usually high. There is also another less noisy cloning technique which has recently been done in laboratories, though it doubles the photon's wavelength, which would be noticeable, and I can't see ofhand how in practice to half the wavelength again without losing polarisation (except perhaps using changing gravitational fields and the like); but there is no theory that says that that can't be done. In another type of QC Alice and Bob agree on the measurement angles (any angles, not just multiples of 45 deg) they will use, and Alice generates a pair of entangled photons, sending one to Bob. Both measure the individual photons at that angle, and the shared secret is generated according to whether the photons pass the filter. If the agreed-on measurement angles are kept secret, and noise bounds etc are obeyed, then a MitM is hard as before except the theoretical maximum ratio of clonable photons is lower - but it isn't much use, except as an otp key multiplier. There are a zillion variations on these themes, and other types of QC. For instance Alice can send Bob data rather than generating a random shared secret, and without a separate channel, if she generates the quantum string using a preshared secret. Mallory can get 1/2 of the bits, but AONT's can defend against that, and if properly implemented no MitM is possible. And so on. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
On Sun, Sep 21, 2003 at 01:37:21PM +0100, Peter Fairbrother wrote: [cloning photons] There is also another less noisy cloning technique which has recently been done in laboratories, though it doubles the photon's wavelength, which would be noticeable, To get rid of the wavelength change it sounds like you just have to produce a new photon with half the wavelength, clone it and then clone one of the clones and measure whether it matches the intercepted one. If it does, forward its clone, otherwise choose another one. I am a little skeptic though, does this really work? I would expect that measuring one clone would affect its twin just as if it was measured directly. Andreas - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
Date: Fri, 19 Sep 2003 11:57:22 -0400 From: Ian Grigg [EMAIL PROTECTED] If I understand this correctly, this is both an eavesdropping scenario and an MITM scenario. In the above, Eve is acting as Mallory, as she is by definition intercepting the bits and re- sending them on? As Dave Howe pointed out, Eve is acting as a repeater and tries not to alter the bits. This seems a sensible model of eavesdropping for QKD. The threat is that Alice and Bob might incorporate bits that were seen by Eve into their key. If Bob never receives a bit, it won't be used. That is, the Quantum Property is that Eve can be detected because she destroys photos in the act of listening, and Mallory, who can resend the photons, has only a 50% chance of reading each bit correctly in advance, so he can be detected after the fact as well, as 25% of his bits are wrong. The terminology destroy is used a bit loosely. I think the important thing for QKD is that if a photon is measured with the wrong basis, the information it is carrying about the key is lost. Ray - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
QC is currently a one-time pad distribution mechanism - or at lower rates a key establishment mechanism most suitable for symmetric algorithms. You are correct that authentication is not inherent. Then again, this is also true for classical symmetric and PKI schemes. To be usable, all crypto requires some kind of authentication mechanism or scheme. The QC community is well aware of this problem and is working on it. Please don't give up yet ! In the mean time, manual establishment of an authentication secret works as do physical means e.g., optical viewing of a satellite from a ground station. Please remember that it's early days yet; the problems are real and hard. Come join the fun. And watch out for snake oil from early attempts at commercialization ;-) John PS: a small nit. The quantum channel is tamper _detectable_. There is no claim to being untamperable. You can always detect tampering (and throw away those bits) regardless of who you are talking to. Multiple reads of a photon (several approaches have been considered) is either equivalent to tampering or yields no information. Physics is fun ! On 9/16/03 16:03, Hadmut Danisch [EMAIL PROTECTED] wrote: On Sat, Sep 13, 2003 at 09:06:56PM +, David Wagner wrote: You're absolutely right. Quantum cryptography *assumes* that you have an authentic, untamperable channel between sender and receiver. So as a result, Quantum cryptography depends on the known methods to provide authenticity and integrity. Thus it can not be any stronger than the known methods. Since the known methods are basically the same a for confidentiality (DLP, Factoring), and authentic channels can be turned into confidential channels by the same methods (e.g. DH), Quantum cryptography can not be stronger than known methods, I guess. On the other hand, quantum cryptography is based on several assumptions. Is there any proof that the polarisation of a photon can be read only once and only if you know how to turn your detector? AFAIK quantum cryptography completey lacks the binding to an identity of the receiver. Even if it is true that just a single receiver can read the information, it is still unknown, _who_ it is. All you know is that you send information which can be read by a single receiver only. And you hope that this receiver was the good guy. Hadmut - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
martin f krafft wrote: So MagiQ and others claim that the technology is theoretically unbreakable. How so? If I have 20 bytes of data to send, and someone reads the photon stream before the recipient, that someone will have access to the 20 bytes before the recipient can look at the 20 bytes, decide they have been tampered with, and alert the sender. This is not relevant when the technology is correctly used for Q key transmission because the sender would not be in the dark (sorry for the double pun) for so long. So I use symmetric encryption and quantum cryptography for the key exchange... the same situation here. Maybe the recipient will be able to tell the sender about the junk it receives, but Mallory already has read some of the text being ciphered. This should not happen in a well-designed system. The sender sends the random key in the Q channel in such a way that compromises in key transmission are detected before the key is used. That said, Q cryptography is something else and should not be confused with Q key distribution. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
Arnold G. Reinhold wrote: I think there is another problem with quantum cryptography. Putting aside the question of the physical channel, there is the black box at either end that does all this magical quantum stuff. One has to trust that black box. - Its design has to thoroughly audited and the integrity of each unit verified - It has to be shipped securely from some factory or depot to each end point - It has to be continuously protected from tampering. Yes. Several years ago, Adi Shamir presented some fascinating attacks on the implementation of such black boxes at Cryptrec, so it is not something that should be taken for granted. It seems to me one could just as well ship a 160 GB hard drive filled with random keying material to each endpoint. Well, I agree. If we get to use complexity-based crypto that is not proven secure, like AES, RSA, or the like, then we can do much better than quantum crypto. The only real attraction of quantum crypto that I can see is that its security does not rely on unproven complexity-theoretic conjectures. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
martin f krafft wrote: So MagiQ and others claim that the technology is theoretically unbreakable. How so? If I have 20 bytes of data to send, and someone reads the photon stream before the recipient, that someone will have access to the 20 bytes before the recipient can look at the 20 bytes, decide they have been tampered with, and alert the sender. You're absolutely right. Quantum cryptography *assumes* that you have an authentic, untamperable channel between sender and receiver. The standard quantum key-exchange protocols are only applicable when there is some other mechanism guaranteeing that the guy at the other end of the fibre optic cable is the guy you wanted to talk to, and that noone else can splice into the middle of the cable and mount a MITM attack. One corollary of this is that, if we want end-to-end security, one can't stick classical routers or other such equipment in the middle of the connection between you and I. If we want to support quantum crypto, the conventional network architectures just won't work, because any two endpoints who want to communicate have to have a direct piece of glass. Quantum crypto might work fine for dedicated point-to-point links, but it seems to be lousy for large networks. For these reasons, and other reasons, quantum crypto looks pretty impractical to me, for most practical purposes. There is some very pretty theory behind it, but I predict quantum crypto will never replace general-purpose network encryption schemes like SSH, SSL, and IPSec. As you say, there is a lot of hype out there, but as you're discovering, it has to be read very carefully. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: quantum hype
On 09/13/2003 05:06 PM, David Wagner wrote: Quantum cryptography *assumes* that you have an authentic, untamperable channel between sender and receiver. Not true. The signal is continually checked for tampering; no assumption need be made. Quantum crypto only helps me exchange a key with whoever is on the other end of the fibre optic link. How do I know that the person I exchanged a key with is the person I wanted to exchange a key with? I don't ... unless I can make extra assumptions (such as that I have a guaranteed-authentic channel to the party I want to communicate with). If I can't make any physical assumptions about the authenticity properties of the underlying channel, I can end up with a scenario like this: I wanted to exchange a key securely with Bob, but instead, unbeknownest to me, I ended up securely exchanging key with Mallet. I believe the following is an accurate characterization: Quantum provides confidentiality (protection against eavesdropping), but only if you've already established authenticity (protection against man-in-the-middle attacks) some other way. Tell me if I got anything wrong. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
