Re: Crypto and new computing strategies
Jim Choate writes:
In the latest issue of Scientific American there is an article...
On Seth Lloyd's grain-of-salt computer, actually. I didn't know he was going to build one. Anyway, his technique *may* be useful to make quantum computers, but it's more likely to be useful for making regular deterministic massive single-instruction-multiple-data computers out of fairly simple crystals--"maybe even a grain of salt." His technique would make every repeating unit of the 3D crystal into a computing unit. You lose a couple factors of 10 for addressing, making higher-level modules, and error-correction. Still, that's a lot of compute power. Tim May says-
No need to worry just yet.
There is no convincing evidence that "quantum computers" can calculate in any way differently from "ordinary" computers.
Right. This is just a large power increase using deterministic stuff. It's based on electrons in the shells of atoms in crystals responding to different frequencies of photons depending on their own and neighboring atoms' shells' states.
Devices that are built on a size scale where quantum effects are important, such as quantum-well devices, don't use QM as a computational mechanism per se. The devices are just real small. But not small enough to matter for large RSA moduli--the computations required to factor a 1000-decimal-digit number swamp even a universe _made_ of computers!
Which is what a naive guess would have said about 129-digit numbers. I would love to see some sort of curve of factoring algorithm efficiencies over time. You could show the log of the difficulty for a selection of number sizes over the past hundred years, say. The experts say it's flattening out and will probably stay that way. A sudden jump in the high end of computer power would mean that we would need to use larger keys sooner than we thought. A key length requiring a little bit more work on the user's part means a lot more work on the cracker's part, but I don't know how many more bits of key compensate for a 10^9 increase in cracking power, say. -fnerd quote me - - - - - - - - - - - - - - - blue pill, Pharm. a pill of blue mass, used as an alterative... alterative, adj. tending to alter... -----BEGIN PGP SIGNATURE----- Version: 2.3a aKxB8nktcBAeQHabQP/d7yhWgpGZBIoIqII8cY9nG55HYHgvt3niQCVAgUBLMs3K ui6XaCZmKH68fOWYYySKAzPkXyfYKnOlzsIjp2tPEot1Q5A3/n54PBKrUDN9tHVz 3Ch466q9EKUuDulTU6OLsilzmRvQJn0EJhzd4pht6hSnC1R3seYNhUYhoJViCcCG sRjLQs4iVVM= =9wqs -----END PGP SIGNATURE-----
While I can understand the commen wisdom such QM type machines are not a threat to the present cyrpto-cracking horsepower race I must admit I don't agree with it. First, historicaly (and emotionaly on my part) I have a hard time taking the premise that the status quo will stay the status quo. I have this belief that some bright person is going to come along and blow all our pipe dreams away. It has happened before and it WILL happen again, especially when you consider the resources available to the government. As to the NSA and their resources, they try to stay 5 yrs. ahead of others on specific topics, you can bet this is one. Also, when you throw compartmented security into the mix I see it as completely possible that the vast majority of the NSA itself believes it doesn't exist while in some basement office there is a little super-cooled sugar cube sized widget cranking out numbers at a high rate of speed. As to the computing power of QM, when one considers that electrons shift orbits instantly (otherwise photons would have to have momentum) and the distances are so small the scaling factor is NOT strictly linear. I completely fail to understand the position that it is an extension of a SIMD architecture, at that scale MIMD architectures will be the standard. My .02...
Jim choate writes:
While I can understand the commen wisdom such QM type machines are not a threat to the present cyrpto-cracking horsepower race I must admit I don't agree with it. First, historicaly (and emotionaly on my part) I have a hard time taking the premise that the status quo will stay the status quo. I have this belief that some bright person is going to come along and blow all our pipe dreams away. It has happened before and it WILL happen again, especially when you consider the resources available to the government.
Remember, however, that advances in technology benefit encryptors as well as codebreakers. Unless the "bright person" comes along and proves P == NP, there's still opportunity to develop strong cryptosystems. (Indeed, if a bright person comes along and proves that P != NP, then things look pretty good.) -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Jim choate writes:
While I can understand the commen wisdom such QM type machines are not a threat to the present cyrpto-cracking horsepower race I must admit I don't agree with it. First, historicaly (and emotionaly on my part) I have a hard time taking the premise that the status quo will stay the status quo. I have this belief that some bright person is going to come along and blow all our pipe dreams away. It has happened before and it WILL happen again, especially when you consider the resources available to the government.
Remember, however, that advances in technology benefit encryptors as well as codebreakers. Unless the "bright person" comes along and proves P == NP, there's still opportunity to develop strong cryptosystems. (Indeed, if a bright person comes along and proves that P != NP, then things look pretty good.)
-- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
The problem w/ the whole N - NP approach is that is assumes that the QM model behaves as we would expect it to, it doesn't. I think this is one of those assumptions that are better left un-made. I have worked w/ enough QM projects throug UT and Discovery Hall (Dr. Turner and Dr. Prigogine) that I am not comfortable assuming the QM world even cares about the N or NP issues we are debating.
Jim choate writes:
The problem w/ the whole N - NP approach
P - NP
is that is assumes that the QM model behaves as we would expect it to, it doesn't. I think this is one of those assumptions that are better left un-made. I have worked w/ enough QM projects throug UT and Discovery Hall (Dr. Turner and Dr. Prigogine) that I am not comfortable assuming the QM world even cares about the N or NP issues we are debating.
It sounds as if you're claiming that mathematics as we know it does not apply when dealing with quantum effects. I suggest that this is a strong statement, and I add that I see no reason to believe it. At the same time, I'm neither a mathematician or a physicist. -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Jim choate writes:
The problem w/ the whole N - NP approach
P - NP
is that is assumes that the QM model behaves as we would expect it to, it doesn't. I think this is one of those assumptions that are better left un-made. I have worked w/ enough QM projects throug UT and Discovery Hall (Dr. Turner and Dr. Prigogine) that I am not comfortable assuming the QM world even cares about the N or NP issues we are debating.
It sounds as if you're claiming that mathematics as we know it does not apply when dealing with quantum effects. I suggest that this is a strong statement, and I add that I see no reason to believe it. At the same time, I'm neither a mathematician or a physicist.
-- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Mathematics as you and I use to solve most real-world problem don't always work w/ quantum mechanics. It is one of the problems w/ this field. I am not a physicist but am trying to go to school and get a degree in it.
First, historicaly (and emotionaly on my part) I have a hard time taking the premise that the status quo will stay the status quo. I have this belief that some bright person is going to come along and blow all our pipe dreams away.
When quark theory was invented, it didn't change the conservation of mass-energy. When quantum computers are invented, it won't change the fact that they're still Turing machines. If it does, that's a revolution; I'm not waiting. A single tape Turing machine has the same computational ability--though not the speed--of a multitape Turing machine, of a multihead Turing machine, of a multihead multitape Turing machine, of a register machine, of single/multiple instruction single/multiple data multiple register machine, of the lambda calculus, of recursive function theory, and of pretty much every other rich computational system every invented. If you still don't agree, I can only steer you to pretty much any first year formal logic textbook. Eric
I am not shure that it has been demonstrated that a QM mechanis is necessarily solely of a Turing architecture. When one considers the dependancy of electron spin (for example) over distance (which happens to break the 'speed of light' limit) there is sufficient reason (to my mind) to suspect that there will be some additional funkyness going on here. Also there is the potential to use neural networks at these levels (which are not necessarily reducable to Turing models, the premise has never been proven) which coupled w/ the speed of computation considerations leaves a lot to be said for the security of all the existing 'time to crack' computations that I have seen to date. The bottem line is that this whole area is a unknown and if we persist in carrying unproven assumptions from the macro-world over into the QM model we WILL be in for a nasty surprise. I want to reiterate that I am not saying there is a threat, simply that what we know about it know is not sufficiently strong enough in the 'proof' area to carry the weight of resolution some c-punks would like to assign it. Beware, there be Ogres there...
Jim choate writes:
Also there is the potential to use neural networks at these levels (which are not necessarily reducable to Turing models, the premise has never been proven)
Uhh, gee; given that I've seen neural networks implemented on conventional computer systems, and as far as I know those were perfectly functional (if slow) neural networks, I think that pretty much proves it (as if it needed to be). I'd say that the burden of proof is to demonstrate that there are algorithms implementable on a neural network which are unimplementable on a Turing machine. That'd be a pretty significant breakthrough.
The bottom line is that this whole area is a unknown and if we persist in carrying unproven assumptions from the macro-world over into the QM model we WILL be in for a nasty surprise.
Complexity theory doesn't have anything to do with any world, macro- or micro- or mega- or whatever. It's mathematics. -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Jim choate writes:
Also there is the potential to use neural networks at these levels (which are not necessarily reducable to Turing models, the premise has never been proven)
Uhh, gee; given that I've seen neural networks implemented on conventional computer systems, and as far as I know those were perfectly functional (if slow) neural networks, I think that pretty much proves it (as if it needed to be).
I'd say that the burden of proof is to demonstrate that there are algorithms implementable on a neural network which are unimplementable on a Turing machine. That'd be a pretty significant breakthrough.
The bottom line is that this whole area is a unknown and if we persist in carrying unproven assumptions from the macro-world over into the QM model we WILL be in for a nasty surprise.
Complexity theory doesn't have anything to do with any world, macro- or micro- or mega- or whatever. It's mathematics.
-- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
I use both digital and analog circuits in some of my designs and they are not necessarily reducable. Just because you can use a neural network to solve a problem using conventional architecture machines does not a priori prove anything about the reducability of the technology. I would have to say that 'spin glass' model neural networks might be such a model. However, either way you approach it (yours o r mine) it has not been done and assuming it is the same will lead to some problems. Complexity theory is mathematics so I would have to say your last assertion is total drivel. r
Jim choate writes:
Complexity theory doesn't have anything to do with any world, macro- or micro- or mega- or whatever. It's mathematics.
Complexity theory is mathematics so I would have to say your last assertion is total drivel.
I think you've misunderstood. What I meant was that because it's a purely mathematical set of concepts, it doesn't have anything to do with hardware details. -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Jim choate writes:
Complexity theory doesn't have anything to do with any world, macro- or micro- or mega- or whatever. It's mathematics.
Complexity theory is mathematics so I would have to say your last assertion is total drivel.
I think you've misunderstood. What I meant was that because it's a purely mathematical set of concepts, it doesn't have anything to do with hardware details.
-- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
I have to disagree, the implimentation of such a theory by a physical model will have some hardware dependancy.
I am not shure that it has been demonstrated that a QM mechanis is necessarily solely of a Turing architecture.
The Bekenstein Bound gives limits both on the expected maximum number of quantum states encodable in a given volume of space and on the expected maximum number os transitions between these states. If this bound holds (and it certainly seems to hold for EM fields), then a probabilistic Turing machine will be able to simulate it.
Also there is the potential to use neural networks at these levels (which are not necessarily reducable to Turing models, the premise has never been proven)
If you have infinite precision, the statement is unproven. If you have finite precision, you get a Turing machine. You never get infinite precision in real life, even with quantum superposition. Steve Smale did some work a few years ago where he made Turing-type machines out of real numbers, i.e. infinite precision. P=NP for this model, and the proof is fairly easy. From an information-theoretic point of view, you can encode two real numbers inside of another one and do computations in that encoded form, because a real number encodes an infinite amount of information. If it's finite, it's a Turing machine. If it's expected finite, it's a probabilistic Turing machine. If it's infinite, it cannot be implemented in hardware. Eric
I am not shure that it has been demonstrated that a QM mechanis is necessarily solely of a Turing architecture.
The Bekenstein Bound gives limits both on the expected maximum number of quantum states encodable in a given volume of space and on the expected maximum number os transitions between these states. If this bound holds (and it certainly seems to hold for EM fields), then a probabilistic Turing machine will be able to simulate it.
Also there is the potential to use neural networks at these levels (which are not necessarily reducable to Turing models, the premise has never been proven)
If you have infinite precision, the statement is unproven. If you have finite precision, you get a Turing machine. You never get infinite precision in real life, even with quantum superposition.
Steve Smale did some work a few years ago where he made Turing-type machines out of real numbers, i.e. infinite precision. P=NP for this model, and the proof is fairly easy. From an information-theoretic point of view, you can encode two real numbers inside of another one and do computations in that encoded form, because a real number encodes an infinite amount of information.
If it's finite, it's a Turing machine. If it's expected finite, it's a probabilistic Turing machine. If it's infinite, it cannot be implemented in hardware.
Eric
First off, EM fields are NOT QM. They do have some characteristics which 'bleed' over form the Quark level. Also since EM fields are made of hardons and not leptons (which an electron is) may blow a hole in this approach since leptons do not follow the same sort of charge conservation rules as hadrons. As to infinite precision and its non-presence....Beeep....wrong answer... Electrons change state in zero time, this implies at least some form o f infinite precision (otherwise how does the system know the difference between zero and some small-o value?). I suspect this is another error based on the implied (and incorrect) implication in this line of discussion that hadrons and leptons use the same rules.
The Bekenstein Bound gives limits both on the expected maximum number of quantum states encodable in a given volume of space and on the expected maximum number os transitions between these states. If this bound holds (and it certainly seems to hold for EM fields), then a probabilistic Turing machine will be able to simulate it.
First off, EM fields are NOT QM.
The "EM fields" I was referring to mean electromagnetic interactions, that's all. The argument on the Bekenstein bound does not depend on the nature of the particles mediating the field, but on the existence of non-zero commutators for position and momentum, i.e. Heisenberg uncertainty. Bekenstein uses his argument to try to constrain the possibilities of interaction inside the proton, for example. I'm not sure it works for that, but the argument is pretty clear about states mediated by electromagnetic interaction.
As to infinite precision and its non-presence....Beeep....wrong answer...
You must not understand what the Bekenstein bound says. It says, very clearly, infinite precision does not exist. If you disagree with the applicability of the result, then say so, but you'd better know what the result is before you go haplessly denying it.
Electrons change state in zero time, this implies at least some form o f infinite precision
The second half of the Bekenstein bound says that infinitely fast state changes do not occur. Again, no infinite precision. "Zero time" is a different statement than "almost zero time" or "so small that we can't measure how small." What may be reasonably taken to be instantaneous in one model, with it's own characteristic approximations, need not be instantaneous in another. Eric
hughes@ah.com writes:
The Bekenstein Bound gives limits both on the expected maximum number of quantum states encodable in a given volume of space and on the expected maximum number os transitions between these states. If this bound holds (and it certainly seems to hold for EM fields), then a probabilistic Turing machine will be able to simulate it.
Can you give a reference for this Bekenstein bound? Thanks, Bob Solovay
If the Bekenstein Bound states that no infinitely fast state changes occur then it is proved wrong by the electron orbital shift when it absorbs a photon. On my post yesterday about EM fields, QED, etc.; sorry for the confusion, I read it this morning and groaned. Perhaps it was the glue which permeated the building yesterday (repairing stairwell outside my office) which caused my brain to become stupid. I aplogize and agree that I got it bass-ackwards... The point I was trying to make was that EM fields themselves are NOT QM, their interaction w/ Hadrons ARE. Leptons themselves (which a photon and a electron are) are not constrained by the same rules that limit Hadrons because Hadrons are made from Quarks. Last time I checked Leptons don't care a flip about color, charm, etc. The uncertainties which arise in QM arise from the interactions of Hadrons. If a system does not involve a Hadron then it is pretty deterministic, sorta like a billiard ball. However, there has been some research recently (there was an article in SciAm, had a pool table on the cover) where they were discussing chaos and the pooltable which brings into doubt even the premise that macro-scale interactions are perfectly deterministic.
On Wed, 30 Mar 1994, Jim choate wrote:
it. First, historicaly (and emotionaly on my part) I have a hard time taking the premise that the status quo will stay the status quo. I have this belief that some bright person is going to come along and blow all our pipe dreams away.
However faster cracking means faster encrypting (using larger keys) as well. I don't think the US government can maintain a tech edge over the market for long in any case. The Soviet government couldn't. DCF
On Wed, 30 Mar 1994, Jim choate wrote:
it. First, historicaly (and emotionaly on my part) I have a hard time taking the premise that the status quo will stay the status quo. I have this belief that some bright person is going to come along and blow all our pipe dreams away.
However faster cracking means faster encrypting (using larger keys) as well. I don't think the US government can maintain a tech edge over the market for long in any case. The Soviet government couldn't.
DCF
The point that is being missed is that if a method arrises to crack a n-bit key there is sufficient reason to believe that it can be used to crack a m-bit key, where m>n. I suspect that when the algorithm is worked out that it will NOT be bit length dependant. Also remember where most crypto folks get their funding from...Uncle Sam or his kin.
participants (6)
-
Duncan Frissell -
fnerd＠smds.com -
hughes＠ah.com -
Jim choate -
m5＠vail.tivoli.com -
solovay＠math.berkeley.edu