Date: Mon, 28 Aug 1995 23:02:01 -0700 To: cypherpunks@toad.com From: tcmay@got.net (Timothy C. May) Subject: Claiming chunks of keyspace... Looking at it from the outside, I thought the latest SSL challenge experiences were highly instructive. Nothing to be ashamed of. An interesting question: Is it a valid approach for J. Random User to "claim" some chunk of keyspace to search? If the "reward" of finding the gold buried in the keyspace (a key that meets the challenge) is high and the cost of claiming the keyspace is low (or nil), then game theory tells us that some folks will be tempted to claim a bigger chunk of keyspace than they can possibly process. What can be done to reduce this effect? On the negative side, ostracize or punish those who bite off more than they can chew. This approach is fraught with dangers. On the positive side, let everyone simply attack the keyspace as they see fit, picking random parts to attack. This should not be "worse" than a factor of several from a "perfectly coordinated" attack. (I haven't spent time calculating this, but my intuition is that a random attack, with overlapping keyspace, is not a lot less efficiently attacked than attempting to arrange for no overlaps...just based on my mental picture of dropping line segments randomly on some interval and figuring coverage of the line segment.) In between, market systems where itermediate agents subcontract out chunks of keyspace. Mechanisms for this are lacking. -Tim May ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 | black markets, collapse of governments. "National borders are just speed bumps on the information superhighway."