December 2003 - cypherpunks-legacy

Re: GUT and P=NP
by jamesd＠netcom.com 17 Dec '03

17 Dec '03

James A. Donald writes: > > The new operator is a unitary transformation on a single bit. Mike McNally writes > Ok, great. So why is it that a description of a process to be > followed by a quantum copmputer in order to produce some desired > result not an algorithm just because it involves this operator? Obviously one could choose to call these algorithms if one wished, but such a name, if adopted, will obfuscate the fact that such things have very different properties, capabilities, and limitations to conventional algorithms. In particular the results of conventional complexity theory obviously are largely irrelevant to quantum complexity theory, which is why I made my original statement that the development of quantum computers with capabilities that are impossible for conventional computers cannot falsify existing complexity theory and existing complexity theory cannot "disprove" the alleged capabilities of quantum computers. Very likely the name will be adopted but with a qualifier "quantum algorithm". In the event that quantum computers become common (which I do not expect to happen for thirty years or so) I expect the phrase "quantum algorithm" will be replaced by something shorter, so that we have one word for algorithms, and another word for quantum algorithms. We have wandered seriously off topic, and I will make future replies in private email. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd(a)netcom.com

1 0

Re: Gore's "new and improved" key escrow proposal
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

Eli writes: > Tim May said: > > Others here will have a clearer idea than I have, but I don't think a > > "software standard" is what is now being planned. Software-only > > solution cannot possibly have the security that's needed [...] > > My reading of the BSA blurb was that software key escrow really is > being planned: "software implementable [and] based on a non-classified > encryption formula". Yes, this sounds pretty silly. I don't see how > you could possibly prevent a rogue phone from interoperating with a > fascistic one. Guess I need to snarf the original document. Whit Diffie gave a talk at a recent Bay Area Cypherpunks meeting about the software-only master-key system that Dorothy Denning and friends are working with. He'd talked about it earlier, and it was discussed at a workshop at Univ.Karlsruhe they went to. Essentially, it's a fairly clean protocol for sending a session key and a master key, encrypted with a keymaster's public key, in a way that the recipient of the message (who knows the separately-negotiated session key) can duplicate the public-key-encrypted access-field chunk to verify it. The wrinkle that was noticed at the workshop was that you can use anybody's ID in the ID field, so there's a need for your master-key (which is already digitally signed by the keymasters) to include some verification; I don't remember the details, though it was fixable after some mild embarassment for the statists. As far as communications between rogue phones and conformist phones, it's actually stronger than Clipper turned out to be - if the conformist receiver *wants* to verify that the access-field is correct, it can, so you have to generate it correctly, while you could generate a fake Clipper checksum in ~2**16 tries and the receiver wouldn't know. For end-to-end communications, that's ok; if you and your friend are both non-conformists, you don't need to check access fields, and you gain a small setup-time advantage by not checking. But your cellular phone company will probably be Conformist, as required by Digital Telephony Initiative #N, and your bank may be as well (assuming the government continues to regulate banks.) Unlike tamperproof secret-design hardware, an open wiretap protocol can't force you to be conformist - but traditional government regulations have worked to keep banks and phone companies conforming in the past. Will they be able to get us to accept this abuse? Maybe. I hope Clipper put a bad enough taste in the public's mouth that they won't get away with it, but a hardware chip is a lot more concrete than "telecommunications software protocol standards" for many people. Depends on whether the government looks like they're "compromising" (which looks good and nice) or "continuing to push this trash even after they've lost" (which looks obnoxious, but they seems to be getting away with it quite well with National ID cards - they're on about their 5th attempt.) Bill # Bill Stewart AT&T Global Information Solutions, aka NCR Corp # 6870 Koll Center Parkway, Pleasanton CA, 94566 Phone 1-510-484-6204 fax-6399 # email bill.stewart(a)pleasantonca.ncr.com billstewart(a)attmail.com # ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465

2 1

X-signatures
by Tommy the Tourist 17 Dec '03

17 Dec '03

I see these postings with X-Signed headers... What program produces those as opposed to begin and end PGP signed message? Thanks in advance, ------------ To respond to the sender of this message, send mail to remailer(a)soda.berkeley.edu, starting your message with the following 8 lines: :: Response-Key: ideaclipper ====Encrypted-Sender-Begin==== MI@```%U_^P;+]AB?X=];G11Z)9;K(Z[;P22_TM9]%$@YRYIS?>+W\7VO<--Y MH#;CYJ#79DJN+`O2)^&8KOPV(V^K7,$(K4J<<8A)<T4L/_5MJZS[+&#EV'(\ (JK\(RJ,,;\H` ====Encrypted-Sender-End====

1 0

Re: My anonymous remailer
by Graham Toal 17 Dec '03

17 Dec '03

[is cypherpunks down again? Haven't seen any traffic in 24 hours...] : From: ghio(a)kaiwan.com (Matthew Ghio) : Newsgroups: alt.anonymous,alt.privacy.anon-server,alt.current-events.net-abuse : Subject: My anonymous remailer : For the second time in one week someone has again mailbombed my remailer. : Last weekend it was the infamous Detweiler, and now some lamer from ysu.edu : just mailbombed someone on one of the freenets by sending copies the same : post from comp.binaries.mac over and over... I guess the freshmen have : arrived early this year. : Maybe it is just coincidence but I am starting to get somewhat pissed off. : I've been running anonymous remailers for quite a while now and have never : had to deal with crap like this. As the remailer is a vaulable service for : many people, I don't want to shut it down or start putting burdensome : restrictions on its use... Suggestions appreciated. I've been pondering this for some time. I think it's time to try a new experiment in anonymous remailing. I think that all remailers should close down, then open up with new addresses and a single shared new policy... the new policy being that each individual remailer will do his best to 'out' all posters - complete disclosure, log files available, posts available, summaries show up via finger etc etc. Give *us* the same access to the info that the LEAs have, and let us try to work out who is posting what. This puts the onus on the posters to use the encryption and chaining features, and on us to generate our spoofing traffic and delay mail and whatever else it takes to foil traffic analysis. Also, we automatically bounce submissions in plaintext at the point of entry - the only cleartext should be at the point of exit (and not even that if it's personal mail rather than news postings). And we should not guarantee service. Postings can get lost for whatever reason. If someone wants to kill postings in cleartext at the point of delivery to newsgroups or mailing lists, let them. That should stop the Detweilers and place the responsibility of abusing the remailers on the shoulders of the remailer operators. If an abusive posting is sent to news from remailer X, it's clear remailer X was the one that passed it on and had the cleartext available. And with a new policy of outing everyone automatically, people *know* we'll read the cleartext at the point of delivery. This seems to me more consistent with the cypherpunk ideal of users securing their own privacy, rather than trusting someone. G

3 2

CEB 7 - its alive! Cypherpunks' Electronic Book.
by Gary Jeffers 17 Dec '03

17 Dec '03

CEB 7 CYPHERPUNKS' ELECTRONIC BOOK - its still alive! Not long ago someone sent me private email volunteering a workstation to handle the CEB. I have stupidly lost the post. After several hours of hunting thru my unindexed Cypherpunk archives - no luck. Will that person please email me again with CEB in the header? Also, I have a very well qualified volunteer to do the editing of CEB. Hopefully, he may know how to program it as well. I am going to maintain a list of people with different skills who would like to work on the CEB. Anybody would would like to help please post either to me or to Cypherpunks with CEB in the header. Also, would the people who have archieved Cypherpunks' lists please respond as well. PUSH EM BACK! PUSH EM BACK! WWWAAAYYY BBBAAACCCK! BBBEEEAAATTTT STATE! Yours Truly, Gary Jeffers

1 0

Re: Travelling ants
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

Tim May writes: > * By the way, there has been little progress in taking known > NP-complete decision/computation problems and making cryptosystems out > of them. I'm not sure why this is, and I get the impression that not > many others understand this either. > > In fact, I'll close with a nagging questio. Except for some work on > elliptic functions, there has been no real alternative to RSA for > public key crypto. Why? One would think that in 16-18 years of work, > some alternatives based on something other than the difficulty of > factoring or taking discrete logs would have been developed. Why not? Good one-way transformations are hard to find. Merkle & Hellman's knapsack-based cryptosystem predated RSA; it depended on transforming an easy subproblem of a NP-hard general problem into the general case. Shamir and others found ways to reverse the transformation that was used, reducing it to the easy problem. In general, a symmetric cryptosystem needs to have one easy path through it (using the key); an asymmetric system needs two (encryption & decryption), and that's much harder to find. The inter-relatedness of NP-complete problems probably doesn't help much. There may be some deep mathematical truth hiding somewhere in here, but I'm more of an applied-math type than a real theoretician :-) A separate problem is that signature and encryption are both useful, and it's hard to find a system that can do both securely. > "National borders are just speed bumps on the information superhighway." Lately they've been more like speed limits... Bill # Bill Stewart AT&T Global Information Solutions, aka NCR Corp # 6870 Koll Center Parkway, Pleasanton CA, 94566 Phone 1-510-484-6204 fax-6399 # email bill.stewart(a)pleasantonca.ncr.com billstewart(a)attmail.com # ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465

2 1

CEB 7 - Cypherpunks' Electronic Book - its still alive!
by Gary Jeffers 17 Dec '03

17 Dec '03

CEB 7 CYPHERPUNKS' ELECTRONIC BOOK - its still alive! Not long ago someone sent me private email volunteering a workstation to handle the CEB. I have stupidly lost the post. After several hours of hunting thru my unindexed Cypherpunk archives - no luck. Will that person please email me again with CEB in the header? Also, I have a very well qualified volunteer to do the editing of CEB. Hopefully, he may know how to program it as well. I am going to maintain a list of people with different skills who would like to work on the CEB. Anybody would would like to help please post either to me or to Cypherpunks with CEB in the header. Also, would the people who have archieved Cypherpunks' lists please respond as well. PUSH EM BACK! PUSH EM BACK! WWWAAAYYY BBBAAACCCK! BBBEEEAAATTTT STATE! Yours Truly, Gary Jeffers

2 1

comments by Ron Rivest on Government crypto policy
by Hal Abelson 17 Dec '03

17 Dec '03

These are some thoughts by Ron Rivest on government crypto policy and the recent statement on Clipper. I'm forwarding them to this list with Ron's permission. -- Hal Abelson ****************************** The original intent of Clipper was to make available government (i.e., NSA) crypto technology (i.e., SKIPJACK) in a way that could not be exploited by criminals or foreign nationals. NIST and NSA wanted to help out by making some of their technology available to US industry, but wanted to do so in a way that didn't hurt other US government operations (intelligence, law enforcement). Key-escrowed clipper is the result. This is what Brent Morris and Mark Unkerholtz of NSA said in a public lecture at MIT in spring '94. They stressed the point that their main goal was not to catch crooks or do foreign intelligence better, but only to help out in a way that was not hurtful to these other operations. They didn't really expect that Clipper would catch a lot of crooks. (As is widely believed, any sensible crook will avoid using Clipper equipment.) The goal is to get their technology out, and a secondary requirement is that it be done in a way that doesn't hurt their other operations. Note that the above position is entirely consistent with an entirely voluntary use of other cryptographic techniques by industry. Trying to force industry to use Clipper, or to use key-escrowed techniques, would be equivalent to an assertion that the primary goal IS to assist law enforcement and foreign intelligence in their operations, and is thus contrary to the above position. I now concerned that the administration's recent announcement represents a serious revision of the above position. Probably the reasoning for NIST and NSA is going something like this: -- Congress (and parts of industry) wants the government to propose crypto standards. -- NIST, the FBI, and the NSA can't push forward with a standard that is non-escrowed, because their jobs are on the line if any significant use of government standards is made by "bad guys". -- They propose Skipjack/Clipper, which attempts to be "helpful" (it has a new algorithm) in a way that doesn't hurt (key escrow). But then, we have -- Significant opposition to escrowed standards by almost everyone except Dorothy Denning. Also, opposition to secret algorithms in standards. So, what do they do? -- Announce that they are reconsidering their policy on Clipper, while keeping their commitment to escrowed crypto standards. Invite proposals from industry for escrowed crypto standards suitable for software. The crypto algorithms could be public, etc. At this point, we have lost the only real contribution of the original proposal (the secret Skipjack algorithm is shelved), and the role of the government is now back just to trying to set some sort of standard. That is, they are no longer contributing technology, but only acting as a standard-setting body. However, the fixation on escrow techniques persists; no bureaucrat wants to have his job on the line for helping some "bad guy" that someday chooses to use the US crypto standard. But at this point, we have a government position that doesn't hang together. (The original position made more sense, although it didn't result in a reasonable policy.) Without government technical contributions to protect (e.g. Skipjack), the only motivations for preserving key-escrow are (1) protecting the jobs of the policy-makers should some fairly visible bad guy use government standard crypto someday, or (2) a reversal of the original policy: catching crooks and assisting foreign intelligence are now elevated from secondary constraints (due to reason (1)) to a primary goal. But it is well-recognized that catching crooks and assisting foreign intelligence in such a manner requires the *mandatory* use of an escrowed standard. Without legal requirements to do so, most manufacturers won't bother with the escrow capability. Moreover, with an adoption of public crypto standards, anyone (e.g. foreign businesses) would be free to produce their own non-escrowed implementations of the adopted crypto algorithms, and sell them in the US. It has been well argued that key escrow technology is not an effective or cost-effective means of law enforcement, etc. I think that mandating the use of key escrow technology would be unacceptable to most of the country (viz the current debate, which is running 1000 to 1 against even voluntary key escrow standards), too expensive, and too much sticky tar spread on our nascent information highway. I think everyone realizes that mandating key escrow is not desirable or realistic. Thus, we have a situation where there are four apparent choices left: (1) No government-approved crypto standards. (2) Government-approved public crypto standards with key-escrow mandatory for government use and voluntary elsewhere. (3) Government-approved public crypto standards with key-escrow voluntary for all users. (4) Government-approved public crypto standards with no key escrow. The other choices, involving secret algorithms, are not viable. I also think that (1) is not viable, although one might suspect that many government actions (and non-actions) were really directed at that goal. This leaves (2)--(4). Policy (2) makes no sense. Given the freedom to easily use the standard algorithms in non-escrowed manners (since they are public); policy (2) is not effective for law-enforcement, etc. It has considerable cost, and no justification other than the attempt of the policy-makers to try to do something that pretends not to hurt other government activities. Policy (3) might be workable. There is no mandated use of escrowed technology (even for government purchases) but manufacturers and users may voluntarily implement escrowing capabilities if they wish. Government agencies (NIST, the FBI, and the NSA) may develop and publish escrowing techniques, and support and encourage escrowing activities, as long as escrowing is not required by standards, government purchases, or routine export control policy. (I haven't mentioned export control policy before, but think that it falls in the same general category as requiring escrow for government purchases---it is an attempt to affect the (foreign) market by limiting what (US) manufacturers can do, rather than by affecting what products are offered through government purchasing power. In both cases, the government's power to affect the market is limited by the activities of other manufacturers and purchasers. Export control in support of specific policies against hostile countries (e.g., Libya?) is, in my opinion, not unreasonable, but telling our information highway manufacturers they can't export crypto is like telling our automobile manufacturers that they can export cars, but only if they contain no bolts, fasteners, or opaque trunk lids: for crypto is the "nuts and bolts" of an information system -- it links together separate components in a secure manner, and is also the means of protecting your information goods from prying eyes.) Finally, there is policy (4) -- no escrowing at all. This is, in the end, the most workable. It makes explicit that trying to achieve law-enforcement and foreign intelligence objectives by affecting government crypto standards is misguided and ultimately, harmful. Comments appreciated.... Cheers, Ron --TAB24284.775191964/cygnus.com--

1 0

Re: GUT and P=NP
by jamesd＠netcom.com 17 Dec '03

17 Dec '03

> James A. Donald writes: > > One can reduce all classical operations to "and", "or", and "not" > > operations on bits. Quantum computers include an additional > > operation that cannot be so reduced. > Mike McNally writes > Could you break the suspense and let us know what this special new > operator is? The new operator is a unitary transformation on a single bit. Note that I am using the word "unitary" in the sense of quantum physics, not in the sense of C language syntax (That is unitary, not unary) Actually this a three dimensional continuous class of transformations. Because it is continuous, quantum computers tend to rapidly lose precision. Just as any classical physical system can be simulated in polynomial time by a Turing machine using only the operations of boolian arithmetic, in the same way any quantum physical system can be simulated in polynomial time using only the operations of boolian arithmetic plus unitary transformations on individual bits. Of course actually building a quantum computer using only these operations would be rather silly. In practice one would need to use unitary three bit operations for reasons of efficiency. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd(a)netcom.com

1 0

(Fwd) Re: GUT and P=NP
by John Young 17 Dec '03

17 Dec '03

Forwarding mail by: sondheim(a)panix.com (Alan Sondheim) on Sun, 24 Jul 3:39 AM ------------------- >From fiction-of-philosophy-approval(a)world.std.com Sun Jul 24 04:08 EDT 1994 Reply-To: fiction-of-philosophy(a)world.std.com I would say that an algorithm is also a rigidly constructed framework consisting of well-defined formula within a stabilized potential well; as such it has limited operability in situations which possess fuzzy heuristics - such situations would include ordinary-language parsing, by the way, if a theoretical full-accountability is to be given. Eliminating indeterminacy and `true randomness' is eliminating the lifeworld itself, with its fuzzy heuristics not always reducible to natural law, even of the trajectory-bundles of chaos theory. So we are thrown back to a quantum computer which is reduced in the quoted text as well to a theoretical positioning; this is suspect since such a computer also functions in the lifeworld. If the brain in Penrose's text functions as _a_ quantum com- puter, what is the source of the singularity (_a_)? It seems to me that there is, in the real, deep fuzziness all the way around. Are we dealing with a group of logicians who have ignored Schutz? I think so, _precisely._ Alan

1 0