provably hard PK cryptosystems

[Jim McCoy]

Asgaard <asgaard at Cor.sos.sll.se> writes:

>On Sun, 22 Sep 1996, Timothy C. May wrote:
>> Suppose a tile is placed at some place on the grid, and another tile
>> (possibly a different tile, possibly the same type of tile) is placed some
>> distance away on the grid. The problem is this: Can a "domino snake" be
>> found which reaches from the first tile to the second tile, with the
>> constraint that edges must match up on all tiles? (And all tiles must be in
>> normal grid locations, of course)
>
>Intuitively (but very well not, I'm not informed enough to know)
>this might be a suitable problem for Hellman's DNA computer, the
>one used for chaining the shortest route including a defined
>number of cities?

Solving such a problem is easy to break down into parallel steps, but
the advantage of using the infinite plane (or even a plane with "really
large" boundaries) which Tim mentioned is that you can make the search
space larger than anything which can possibly be solved in a reasonable
amount of time by these methods.  For example, factoring composites of
very large primes can also be done by such massively parallel systems, but
othe individual parts are no faster (actually they are almost always slower)
than regular computing elements.  Given a large enough search space even
a parallel system runs out of processing elements.

jim