At 1:08 AM -0400 4/13/00, dmolnar wrote: > >Just the other day I received a note from TheoryNet (list-serv of academic >job announcements and calls for papers) on the "6th Annual Conference on >DNA Computing." I may have deleted the announcement, but I bet something >interesting is happening there... Color me very skeptical. Wet computing buys at most a speedup in certain algorithms. If the problems (economic, scalability, I/O, etc) can be solved, wet computers _might_ someday be important for relatively weak ciphers. Not much use for ciphers requiring 10^50 Cray-years. Swimming pools full of DNA computers might cut this to 10^30 years. Going into the third dimension for chips is very interesting, and very expensive. Tanks of partially-assembling, somehow-computing biological elements _could_ be interesting for some problems, but probably not for crypto. (As we all know, cipher-making _always_ wins out over cipher-breaking. Consider pure RSA (not a hybrid RSA and symmetric ciphers combo). Going from 1K keys to 2K keys to 4K keys, and so on, is straightforward. Additional computational power is easy to apply. But factoring the moduli becomes intractable rapidly. Swimming pools, even entire planets, made of DNA computers will be as nothing...) > >Anyone taken a look at what Noam Nisan is doing for "economic mechanisms >in computation" ? >http://www.cs.huji.ac.il/~noam/mkts.html > >The idea seems to be to replace the Byzantine adversary model with one >based on economics. Then design protocols around that to Do Things, >taking advantage of the model. Is this model convincing to you? >Come to think of it, anyone seen interesting applications of econ to >crypto? "_All_ crypto is economics." A phrase I believe Eric Hughes came up with. Defense and counter-defense issues are common economic issues: how thick are the walls of the castle?, can better battering rams be built?, how many ICBMs do we need?, how many firewalls around our financial computer? Economics is applied only very marginally to crypto. Mostly, I think, because the economic issues tend to get abstracted away until the theorists are left with number theory problems they can plausibly hope to attack and resolve, for example. (One can bet that "big picture" looks at crypto certainly involve economic analyses. Costs of deploying crypto, costs of attacking ciphes, costs of black bag jobs, etc.) As far as applying market-based economics to crypto, there are several interesting avenues: * cooperative agents, a la the Agorics project. (Search on agorics, Mark Miller, Dean Tribble, www.erights.org, etc.) * simulations of economically-competing actors. Such simulations will likely be useful for generating robust protocols. (This is more nebulous as a research area. A mix of game theory, evolutionary game theory, actor models of computation, with crypto thrown in certain places.) * some of the basic work on things like "fair division of a pie." We all know how the "Alice cuts, Bob chooses" protocol works (and this protocol is closely related to some important crypto protocols), but how does it extend to N parties? Robin Hanson, a sometime list member, works on issues like this. * the general advantages of free market approaches to distributed systems of mutually suspicious agents and only partially cooperating agents. Crypto tends to only deal with certain subsets of these interactions--often an entire class of papers is written about just _one_ type of interactions (like "bit commitment" between Alice and Bob, or like "oblivious transfer'). Reputations, and the problems they solve, are almost unheard of in the crypto community...partly because they are _engineering_ solutions rather than _mathematical_ solutions. (For example, a third party escrow service who handles the money between two parties. Conventional crypto would reject this, because the escrow party is not provably trustworthy, or reliable, or whichever term one prefers. Yet reputations matter, and they can be blended into crypto situtatons. Read my stuff from the early 90s on using escrow systems for untraceable contract killings for a concrete, if distasteful to some, example.) Reputation markets were discussed by me with Phil Salin, Jim Bennett, Marc Stiegler, Randy Farmer, Chip Morningstar, Robin Hanson, and others in a series of meetings in 1988. Phil Salin had a company called the "American Information Exchange" which was essentially trying to develop online markets, a la EBay. He was a few years too early, for the state of the Net, and, besides that, he died of cancer in 1991. There is much more I could write about these discussions, and crypto anarchy. The Extropians list had a primitive repuation market running in around 1993. An interesting experiment. (I believe that some of the people involved were also involved in the "SLED" key signing system, and that this led to a company (4-1-1 ?), which led to their being acquired, but I could be misremembering. There was also Firefly, a ratings service. A fertile area. The connections with crypto, keys, identities, online markets are all fairly obvious. > >on econ and crypto... > >A while back, Tim had a rant about "neo-Chaumian" approaches to remailers >vs. "market-based" approaches. As I recall (and I hope to be corrected if >wrong), the point was that it was better to enforce compliance by random >audit and reputation service, instead of using logs and "proofs." Less >messy, and less danger in the face of a coercive adversary. Yes, this is closely related to the above discussion. And to issues of monoculture and disease resistance. Again, a subset of "distributed defense." N-out-of-M attacks, And parallel to crypto heuristics, like chaining of ciphers. If M different ciphers (DES, Blowfish, IDEA, Twofish, etc.) are available, use them _all_. Modulo issues of the cost of using M of them in a chain, and issues of compromising through composition, using all of the ciphers means that the breaking of N out of the M ciphers has not broken the composition. (This is really just some basic algebra. As is the math of remailers, the kind we use. Note that the much more sophisticated math for remailer attacks used by Chaum, Pfitzman, et. al. are also laden with economic and even market-related issues.) > >so does it make sense to try to quantify how well a reputation approach >works? does anyone do this (in econ, perhaps)? are they convincing? can a >quantitative approach to reputation ever be convincing? can >they apply it to a protocol and give some evidence that the protocol will >stay "in line"? Yes, I believe this is a "hot" topic. The merger of crypto (as the mathematical underpinning), game theory, and economics is likely to be an important area in the future. Not to beat a dead horse, but this has been obvious for a long, long time. What keeps this synthesis from being done? The obvious: there are only a handful of people in the world doing things, and they are doing other things besides this. The names I don't have to spell out here (and thus risk insulting someone I forget to name). It will take someone doing an analysis and writing a paper for the ideas to start to catch on. And even then most won't think the work is important. Then some bunch out of MIT or Stanford or wherever will form a company to commercialize this "economic trust model" and they'll be the next dot commies. My hunch is that the Dempster-Shafer model of belief propagation is a good starting point for formalizing this. I wrote a long article on this about four or five years ago. (I noticed that Wei Dai is talking about a "belief" element in his recent proposal for a signature server of some sort, so perhaps he has also been influenced by the D-S work.) So, yes, I do indeed think crypto and economics are closely linked. Most cryptographers don't, though. --Tim May -- ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, "Cyphernomicon" | black markets, collapse of governments.
