provably hard PK cryptosystems

[Timothy C. May]

At 4:29 PM 9/23/96, Asgaard wrote:
>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?

No, massive parallelism does not help with the _general_ case. (For any
specific instance, especially for a finite grid, obviously the amount of
CPU power is directly relevant.)

Even assuming Adleman's "DNA computer" works and scales relatively well,
its CPU power only goes up roughly with the volume of the computer. While
it may sound impressive to speak of "moles" of computers, or "swimming
pools" of computers, such volumes are utterly inadequate to solve
combinatorially-explosive problems. (Remember, it doesn't take a very big
RSA product before the 10^75 elementary particles in the Universe are not
enough to factor it in a billion times the age of the Universe even if
every particle were a Cray! So much for a tank full of DNA computers.)

The domino snake or tiling problem is a similarly explosive problem. Try
playing around with some tiles on even a 5 x 5 grid, and then contemplate
how large 25! is. Then think about a 10 x 10 grid, and 100! Then a 100 x
100 grid.

And it may be that the domino snake reaching from tile A to tile B snakes
around and about in a far, far larger grid space than this! (Even if one is
confined to a 100 x 100 grid, easily displayed on a sheet of graph paper,
no intelligence in the universe will ever be able to find a snake reaching
from A to B, except in special situations (e.g., the same tile, etc.).)

This sort of problem is the essence of some "zero knowledge interactive
proof systems" (ZKIPS) sorts of proofs. I present such a snake as proof
that I am who I say I am. (Because I just "made up" some random snake, then
announced only the starting and stopping points, A and B. Nobody else in
the universe could ever find such a snake, but I can display my solution as
proof I generated it in the first place. Of course, once shown I have given
the proof away to everyone. The ZKIPS trick is in twiddling the grid and/or
tiles in such a way that I can give _probabalistic_ information away. I
don't know how to do this for the domino snake problem, but it's easy to
understand the Hamiltonian cycle version.)

--Tim May

(Late News: I just heard (12:30 p.m., PDT) that Seymour Cray is in
extremely critical condition after suffering head injuries in a car crash.
It will be a sad day if he dies, or is permanently disabled. Though he
started working for the Agency in the 1950s, in a precursor to Control Data
Corporation, and worked for them on various contracts in the next couple of
decades, he was a true pioneer. (The CDC 6600, 7600, etc., and the Cray-1
were funded by contracts from the AEC and NSA, and the first few of each
were delivered to Fort Meade, Los Alamos, Livermore, etc.))


We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay at got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1,257,787-1 | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."