From: tcmay@got.net (Timothy C. May)
Date: Mon, 23 Sep 1996 20:41:35 +0800
To: cypherpunks@toad.com
Subject: Re: provably hard PK cryptosystems
Message-ID: <ae6b6083050210047554@[207.167.93.63]>
MIME-Version: 1.0
Content-Type: text/plain



I want to say something about "tiling problems," an area I find very
exciting. I ordinarily would not have commented on "quantum computers," but
will make just a couple of comments, since I want to comment later on
tilings.

At 9:58 PM 9/22/96, Adam Back wrote:
...
>I'm not sure about quantum computers, some people who know much more
>about particle physics than I do seemed initially sceptical, and
>didn't think it was doable.  However I have read some optimistic
>sounding news clippings (on the list) which sounded as if things are
>progressing well, with techniques being found using redundancy to get
>around what were earlier problems of reliability.  Is this accurate
>reporting (thinking of garbled stories by over enthusiastic
>journalists)?  I'd be interested to hear opinions from anyone who does
>know about particle physics about the likihood of practical quantum
>computers being practical in the next 20 years or so.

Caveat: I'm a skeptic on quantum computers. I've read a couple of the early
papers, but am not current. And I certainly am not an expert.

For what it's worth:

* I think it's nearly certain that no significant results will be gotten in
the next 20 years, probably not in the next 50 years. (I personally am
skeptical that significant results will be gotten in 200 years, and
probably never, but this is a harder point to make.)

* Sure, there may be demonstrations of a "collapsed quantum state" which is
isomorphic to factoring a number like "42," but not 50-digit numbers
anytime soon. And, I feel, a 300-digit number is probably many, many orders
of magnitude harder.

* Experts may point to partial successes, and maybe they're right. But I'm
skeptical.

The recent post by someone outlining a bunch of "promising approaches" has
got me thinking of spending some more time looking at recent results,
though. I doubt anything will happen in the next 20 years...that just isn't
much time in the high-tech business (which may sound crazy, but it's true).

(A way to "creatively visualize" this point is this: for those of you who
are now 25, when you are 45 the world will probably _not_ be radically
different. Sure, computers will be faster and cheaper, but most things will
look _mostly_ the way they look today. Not a compelling argument, perhaps,
but one which makes sense to me. When I was 25 I suppose I expected
dramatic advances to come...largely, they haven't. I can elaborate on this
if there's sufficient interest.)


>One other area that did sound promising was some kind of mapping
>problem in n dimensional tiling that Tim was discussing at a physical
>meet while I was over in the US.  A news clipping posted to

One of the most interesting books I've read is David Harel's "Algorithmics:
The Spirit of Computing." (Warning: The book came out in a second edition,
which as near as I can tell took out some parts and synopsized the book a
bit. My reading was of the First Edition.)

Harel described Huang's work on "tiling problems." These are easier to
describe with pictures, and I don't have the time to try to generate ASCII
representations of tiles. So, I refer people to Harel's book.

Briefly, imagine a grid in a plane. Imagine a set of "dominoes" or "tiles"
with different edge properties, e.g., some edges are blue, some red, some
green, etc. (or the edges can be numbered, have symbols on them, etc.).
Suppose one has an unlimited supply of, for example, N different type of
tiles.

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)

If the grid area is, say, a finite space, then clearly an exhaustive search
of all legal domino snakes would answer the question. (However, even a
relatively small grid of, say, 8 x 8, generates a truly enormous number of
possible snakes, each of which must be tested. Of course, if a domino snake
is "guessed" (a la the "nondeterministic" language one encounters in
complexity theory), verification that it is answer is nearly instantaneous
(one glances at the solution and verifies it).

If the grid is unlimited, then even if the two initial tiles are located
close together, there are of course an infinite number of possible
snakes....

(Oddly, to me, the domino snake problem is "more undecidable" in the
infinite half-plane that in the full infinite plane....)

Huang proved that the domino tiling problem is formally equivalent to the
standard set of NP problems (consult Harel, or Huang, for more details and
more precise language...I'm just going from recollection here!). I like
this approach because I can easily visualize the domino tiling problem and
can make some points about expansion of knowledge into uncharted areas
(research and tool-building is a kind of domino snake expansion, with local
laws of physics, etc., the constraints on stepping stones (hand wave
inserted here)). I find this easier to understand than more "algebraic" and
"logical" versions, such as the representation problem and the word
problem. (These other NP problems are  also described in Harel (and in
standard complexity books, such as Garey and Johnson, Papadimitrou, etc.).

It has always been a great hope that some of the provably-hard problems be
adapted for use in crypto. And yet factoring remains the core of popular
modern crypto programs (discrete logs, too, for D-H).

I don't think this is a major cause for worry, though. It's not as if
factoring is suddenly going to become "easy." (I think the consensus is
that factoring _is_ hard. Whether RSA is really equivalent to factoring
also hasn't been proved, as folks have noted, but many think it is, loosely
speaking.)

--Tim May

We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@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."