New computation method which could endanger used cryptosystems (?)

[dud...@gmail.com]

Let's take some NP-problem: we have a verifier which can quickly say
that given input is correct or not, but there is huge number of
possible inputs and we want to tell if there is a correct one (find
it).
Such problem can be for example finding a divisor (RSA breaking) or
finding a key that if we use it to decrypt the beginning of the file,
there will be significant correlations (brute force attack).

Imagine we have a chip with 'input' and 'output' in which is
implemented (e.g. FPGA):

IF 'input' verifies the problem
- THEN send 'input' to 'output'
- ELSE send next possible 'input' (cyclically) to 'output'

such that this chip uses only basic logic gates - computations are
made in some small number of layers - IT DOESN'T USE CLOCK (we can do
it for some universal NP problems like 3SAT).

Now connect it's 'output' and 'input' to make a loop.

Such loop will be stable if it has found a solution (which can be
transferred out).
If there would be a clock, in each cycle there would be checked one
input.
If not, it's no longer classical computer: while removing the clock/
synchronization we are destroying the order and releasing all it's
statistical, quantum properties to make what physics do the best:
solve its partial differential equations. Now it became continuous and
so it can go with energy gradient to some local minimum, but the only
local minimals are stable states (solutions). Every other is extremely
unstable - electron fluid won't rest until it find a solution. The
statistics, differences between propagation times will create
extremely fast chaotic search for it.

I'm not sure, but it could find solution qualitatively faster than
classical computer.

[Gordon Burditt]

>Let's take some NP-problem: we have a verifier which can quickly say
>that given input is correct or not, but there is huge number of
>possible inputs and we want to tell if there is a correct one (find
>it).
>Such problem can be for example finding a divisor (RSA breaking) or
>finding a key that if we use it to decrypt the beginning of the file,
>there will be significant correlations (brute force attack).
>
>Imagine we have a chip with 'input' and 'output' in which is
>implemented (e.g. FPGA):
>
>IF 'input' verifies the problem
>- THEN send 'input' to 'output'
>- ELSE send next possible 'input' (cyclically) to 'output'
>
>such that this chip uses only basic logic gates - computations are
>made in some small number of layers - IT DOESN'T USE CLOCK (we can do
>it for some universal NP problems like 3SAT).
>
>Now connect it's 'output' and 'input' to make a loop.

I have severe problems believing that this will work. For example,
if you connect the input of a TTL NOT gate to its own output, you
tend to get an intermediate-level DC voltage that might represent
falue or trse logic levels. It's been a while since I tried this,
so more modern circuits might oscillate. It may depend on the
amount of stray capacitance around. Gates do have a maximum
frequency of operation; oscillations above that will damp out.

>Such loop will be stable if it has found a solution (which can be
>transferred out).

It is not guaranteed that the loop will be unstable if it has NOT
found a solution.

[dud...@gmail.com]

It would have huge amount of chaotic properties, so it's difficult for
me to imagine that if there would be a solution, it could create
stable behavior which wouldn't be a solution...?

I believe that it would strongly depend on technology used...
What if some of them would allow to make it work?
Could it be qualitative faster, take a short path to stabilize?

This idea comes from the idea of time-loop computers: there are some
reasons to believe that that physics can allow to make a prediction in
microscale. If we could predict that in let say nanosecond will be
absorbed a photon, we could transfer data back in time. If we would
use it to close such causality loop, physics should stabilize if it
can, to prevent paradoxes. If it's not possible it should break the
weakest link - make that the prediction would go wrong.
http://groups.google.com/group/sci.physics.foundations/browse_thread/thread/a236ada29c944ebb#

[MisterE]

> Such loop will be stable if it has found a solution (which can be
> transferred out).
> If there would be a clock, in each cycle there would be checked one
> input.
> If not, it's no longer classical computer: while removing the clock/
> synchronization we are destroying the order and releasing all it's
> statistical, quantum properties to make what physics do the best:
> solve its partial differential equations. Now it became continuous and
> so it can go with energy gradient to some local minimum, but the only
> local minimals are stable states (solutions). Every other is extremely
> unstable - electron fluid won't rest until it find a solution. The
> statistics, differences between propagation times will create
> extremely fast chaotic search for it.

Sounds like absolute non-sense. The clocking really means nothing, you can
build complicated systems without a clock. What means everything is the
propogation delay through the logic gates (because of it, clocks are used to
sync). There is no way you can cycle the input and put input to output
without some finite delay, and the maximum clock speed would be set very
very close to this delay, so the advantage of not having a clock would be
almost zero, as the propogation delay would still exist. The time it took to
reach a steady state would match the time of a clocked conventional computer
system, so long as the clocking was done right at the same speed as
propogation delay. Any talk about 'quantum' computing is complete non-sense
at the moment.

[dud...@gmail.com]

Probably You are right, but I'm far from being sure of it.
Without the clock it shouldn't longer be imagined through local
propagation times, but rather as continuous river of electrons, which
goes around because of pumps in logic gates and stabilizing means
something like minimizing energy of 'turbulences'.
Classically it would be done using discrete steps. But when it's
continuous, it could do it through continuous evolution of the state
of the whole circuit.

[dud...@gmail.com]

We could also manipulate voltage to make something like simulated
annealing to speedup stabilizing.
Or eventually use it for quantum computers. In standard approach the
only really practical improvement I've heard of is the Shor's
algorithm. Imagine we would make a loop of it (or maybe using some
molecular computer practically without resistance). Now after feeding
it with entangled all possible inputs, unstable wavefuctions should
vanish faster. If there is only one stable, like in brute-force
attack, we should be able just to read it after a while.

Generally there are many new approaches to computation, like quantum
computing, DNA computers, (time-)loop computers ... They looks to be
rather hypothetical in this moment. But ... we wouldn't even know if
someone would already use them...

We should think how to protect cryptostystems against such
eventualities.
The approach that after taking a key we just start to decrypt is
vulnerable to all brute force and so to such attacks. I think that
much better is making most of calculations while initialization -
completely different for each key and which can be enforce to need
some large time, like 100ms. Thanks of this such attacks would became
a few orders of magnitude more difficult ... and because most
calculations was already done, processing the data can be much
faster.
For example cryptosystem based on asymmetric numeral systems (which
was lately shown to be simpler alternative for arithmetic coding),
using a pseudorandom number generator initialized with the key,
generates large coding table. The coder has a state - hidden variable
which chooses one of behaviors (bits to produce and new state) from
the table. It uses short blocks, but of various, completely
unpredictable lengths.

[Unruh]

dud...@gmail.com writes:

>We could also manipulate voltage to make something like simulated
>annealing to speedup stabilizing.
>Or eventually use it for quantum computers. In standard approach the
>only really practical improvement I've heard of is the Shor's
>algorithm. Imagine we would make a loop of it (or maybe using some
>molecular computer practically without resistance). Now after feeding
>it with entangled all possible inputs, unstable wavefuctions should
>vanish faster. If there is only one stable, like in brute-force
>attack, we should be able just to read it after a while.

Sorry your above paragraph simply indicates you have no idea what quantum
computation is all about.

>Generally there are many new approaches to computation, like quantum
>computing, DNA computers, (time-)loop computers ... They looks to be
>rather hypothetical in this moment. But ... we wouldn't even know if
>someone would already use them...

>We should think how to protect cryptostystems against such
>eventualities.

Yes, and people do.

>The approach that after taking a key we just start to decrypt is
>vulnerable to all brute force and so to such attacks. I think that
>much better is making most of calculations while initialization -
>completely different for each key and which can be enforce to need
>some large time, like 100ms. Thanks of this such attacks would became
>a few orders of magnitude more difficult ... and because most
>calculations was already done, processing the data can be much
>faster.
>For example cryptosystem based on asymmetric numeral systems (which
>was lately shown to be simpler alternative for arithmetic coding),
>using a pseudorandom number generator initialized with the key,
>generates large coding table. The coder has a state - hidden variable
>which chooses one of behaviors (bits to produce and new state) from
>the table. It uses short blocks, but of various, completely
>unpredictable lengths.

Since the decryption must be able to take place as well, the lengths MUST
be predictable.

[earlcolby...@sympatico.ca]

Why not try out your idea on a simple model to see if it works?

Example, a simple substitution cypher. Every byte in gets a value of
one added to it, then ouputted.

Thus A=>B, B=>C ......

Easy and simple to model in hardware.

But no matter what you do, if you feed the output back to the input
you will find it NEVER get a stable state (ie solution). And yes,
this is true even in a clockless system.

In a clocked system you can expect to see the states switched in a
very predictable way, on a clockless system you will see the output
jumping all over the place, but it never will become stable to a
single state.

[dud...@gmail.com]

Unruch, quantum computing is about feeding with entangled all possible
inputs(Hadamar gates), making something looking like classical
computation and recover some information from entangled all outputs.
The last step is so difficult that we don't know (now??) how to do it
for NP-complete problems.
So the main part of its computation is kind of classical computer
which doesn't make decohenrece - sustains the superposition of
processes for all inputs. Standard electronics couldn't make it
because of large thermal noise.
If we would make loop computer from such non-decoherating electronics,
the wave functions for all inputs would create loops. But those not
fulfilling verifier would be unstable and should quickly vanish. If
there would be only one that solves the problem, after a while we
should be able just to read it.

The unpredictability of the length of block means that the coder has
some internal state - hidden variable, which covers statistically some
large space of states and the length of block is chosen according to
it. It's reversible but practically unpredictable for someone who
would like to break it.
http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/

Earlcolby, Your example doesn't have fixed point, so it would
fluctuate forever. The question is: if there is a stable one, can such
loop computer find it and would it be qualitative faster?

[Unruh]

dud...@gmail.com writes:

>Unruch, quantum computing is about feeding with entangled all possible
>inputs(Hadamar gates), making something looking like classical
>computation and recover some information from entangled all outputs.
>The last step is so difficult that we don't know (now??) how to do it
>for NP-complete problems.
>So the main part of its computation is kind of classical computer
>which doesn't make decohenrece - sustains the superposition of
>processes for all inputs. Standard electronics couldn't make it
>because of large thermal noise.
>If we would make loop computer from such non-decoherating electronics,
>the wave functions for all inputs would create loops. But those not
>fulfilling verifier would be unstable and should quickly vanish. If
>there would be only one that solves the problem, after a while we
>should be able just to read it.

Again, a garble that has some of the right words, but fit together in a way
that makes no sense. The wave function for the wrong inputs cannot vanish.
And what make loop computer means is simply unknown.

[dud...@gmail.com]

This thread is about loop computers, so please look at the first post
before answering.
The wave function for wrong input would have to make extremely fast
time oscillations - isn't preferable energetically - should somehow
release its energy or find a solution.
The wave function for a solution should be in stable energetic
minimum. So if there would be only one solution, after some time we
should be able just to read it classically.

[Unruh]

dud...@gmail.com writes:

Again, no idea what quantum computation is about.
Also no idea what a "loop" computer is. In the first post you talked about
quantum computers, jumbled together with the word loop in a completely
incomprehensible way.
Since all computations change in time on a single time stop, all have
roughly the same energy.

[dud...@gmail.com]

This thread is about changing NP problem into solving some
differential equation - physical problem. For me intuitively quickly
oscillating state/wave should have larger energy than a stationary
one.

You are right - standard approach to QC - using e.g. external magnetic
field to make some unitary transformations won't work because it
divides time into discrete steps. I thought about molecular
electronics in very low temperature, practically without resistance -
it should also be able to sustain superposition of calculations.
There could be a problem with that in QC all operations have to be
reversible. So while starting some calculation, we have to fill some
large number of auxiliary inputs with constants and they don't make
the loop. Maybe with proper treatment of these variables on the end of
calculation, we wouldn't destroy the entanglement.

[dud...@gmail.com]

I coudn't find anything about such approach to QC, perhaps because it
has to decoherent quickly?
Standard QC makes all cmputation using some sequence of externally
controlled operations. It would be much simpler if the computations
would be stored in the structure of the computer as in standard
computers.
Observe that as benzene is in superposition of a few states, for
example a sequence like (-CH=CH-) should be able to sustain quantum
superposition with (=CH-CH=) : it should work as a wire for qbits.
There are known molecular transistors:
http://en.wikipedia.org/wiki/Single_molecule_electronics
They are no reversible - would destroy superposition, but some
molecules should be able to work as quantum gates.
(-CH=CH-) has some small resistance, but there are also known
superconductors made this way:
http://en.wikipedia.org/wiki/Conductive_polymers

Have You heard about such approach to QC?
What is the problem with it? They has to decohere quickly?