Re: provably hard PK cryptosystems

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

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?

Asgaard

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?

This is starting to sound like Wired magazine.

I fail to see *any* (non educational) use for these DNA "computers", let
alone a cryptographic use - sure, they may be massively parallel, but
what's the big deal?  I can now perform a calculation a million times
faster than I could yesterday? (something I personally doubt, but will
agree to for sake of the argument).  I could get the same results
writing a cycle stealing Internet java app, so what's all the fuss
about?

L8r d00d2

DNA Mutant
--
pub  1024/C001D00D 1996/01/22  Gary Howland <gary@systemics.com>
Key fingerprint =  0C FB 60 61 4D 3B 24 7D  1C 89 1D BE 1F EE 09 06

On Tue, 24 Sep 1996, Gary Howland wrote:

> I fail to see *any* (non educational) use for these DNA "computers", let
> alone a cryptographic use - sure, they may be massively parallel, but
> what's the big deal?  I can now perform a calculation a million times
> faster than I could yesterday? (something I personally doubt, but will
> agree to for sake of the argument).  I could get the same results
> writing a cycle stealing Internet java app, so what's all the fuss
> about?

It sounds to me like your argument abstracts thusly:

"Personally, I fail to see the point to the development of more powerful
computers, since I can always steal time from other people's current
technology computers."

One could make this statement about _all_ advances in processor
technology. And it boils down to this: you're not paying for it, so you
don't see the point in getting more bang for the buck. People who are
paying for it, and have neither the inclination nor the ability to steal,  
do see the point of getting more bang for the buck. And eventually even
you'll benefit, when you find yourself writing a java applet to freeload
processor time on someone else's DNA computer. Meanwhile, processor
technology will have advanced because many people went out and paid for
faster (Intel/PowerPC/PowerDNA/Whatever) CPU's. Not because you freeloaded
off of someone else. 

> --
> pub  1024/C001D00D 1996/01/22  Gary Howland <gary@systemics.com>
> Key fingerprint =  0C FB 60 61 4D 3B 24 7D  1C 89 1D BE 1F EE 09 06
> 

Phil Fraering          The above is the opinion of neither my internet
pgf@acadian.net        service provider nor my employer.
318/261-9649           "Pinky, your brain waves are giving The Amazing    
                        Kreskin a pounding headache."

Gary Howland wrote:
> writing a cycle stealing Internet java app...

And remember, you can do that simply by putting your applet in an
HTML document and then spam-mailing the document with appropriate 
MIME header information to zillions of people.  Everybody who's
reading mail with Netscape (and maybe IE) will see your little
HTML document (which needn't be anything special), and your applet
will be able to fire up and start stealing cycles.

In fact, it'd be cool to set up a mail sender that would construct
such a page automatically with each outgoing mail message.  That
way, ordinary postings to mailing lists would go out with that spiffy
HTML look, and you'd get all those CPU cycles without angering the
community (much).
-- 
______c_________________________________________________________________
Mike M Nally * IBM % Tivoli * Austin TX  * How quickly we forget that
mailto:m5@tivoli.com mailto:m101@io.com  * "deer processing" and "data
http://www.io.com/~m101/                 * processing" are different!

Asgaard <asgaard@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