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:
 > 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.

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.

>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

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.

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