December 2003 - cypherpunks-legacy

Zero Knowledge, Hamiltonian Cycles, and Passwords
by norm＠netcom.com 17 Dec '03

17 Dec '03

Page 85 in Schneier's "Applied Cryptography" begins a good introduction to zero knowledge proofs and such.

1 0

No Subject
by Peter Murphy 17 Dec '03

17 Dec '03

I found Timothy May's post on Hamiltonian cycles in graphs very in- teresting. However, my main reason is due to the relevance between this subject and the P - NP problem. Although I am familiar with the practical aspect of this terminology (through my numerical mathematics subjects), I am a bit hazy on the "pure", theoretical side. Does anyone have any references on this matter. I am especially interested in the "P=NP?" problem. Thanks. Peter Murphy. <pkm(a)maths.uq.oz.au>

1 0

Re: Pseudonyms and Reputations
by Hal 17 Dec '03

17 Dec '03

From: Blanc Weber <blancw(a)microsoft.com> > I'm sure I don't understand, said Alice in Wonderland: cryptology is > to create anonymity sufficient to prevent the identification of a > person; however, it is desireable to have a method/means of verifying > identity such that in games or digicash or whatnot, someone cannot take > advantage of that ability to obfuscate precise references to themselves. > > How could these two opposing needs be simultaneously satisfied? It > sounds like a self-defeating proposition. > > Blanc You don't try to satisfy these simultaneously. Rather, one or the other goal is achieved by the participants voluntarily participating in a protocol. In some contexts, absolute anonymity is desired and achieved. In others, the participants agree to some restrictions on their anonymity in order to allow various kinds of agreements. I may not be willing to loan you money if you are totally anonymous; on the other hand, I might be able to loan it to you if your anonymity would be broken only if you didn't pay it back, for example. If you didn't want to take the chance on breaking your anony- mity, you wouldn't have to. You would just choose not to play my game. The point of a lot of this work with pseudonyms and credentials and such is to create a lot of different possible options along the scale between perfect anonymity and perfect identification. That way people will be able to trade off their various requirements and come as close as possible to their ideal position. Hal

1 0

identity, privacy, & anonymity in cyberspace
by tmp＠netcom.com 17 Dec '03

17 Dec '03

hal finney recently wrote an interesting message taking the position that cypherpunk aims are not so much to pursue total anonymity but to promote systems with a variety of degrees in identity and pseudonymity so that the appropriate level can be achieved in various settings. (for example, borrowing money seems to require that one sacrifice some degree of anonymity and privacy). below is a message i have taken to represent the cypherpunk position from hal finney. this came from chaos.bsu.edu, a fun gopher server with a lot of cypherpunk position papers (i assume they are representative). in it, hal argues against identifying anonymous messages, saying that it would mark them with a `scarlet a' and relegate them to the `ghetto'. his recent comments seem more accommodating and less extremist. >The level of anarchy will >inevitably increase as larger numbers of people acquire net access. it seems to me that the cypherpunks already have a name for the kind of anarchy that can happen when somebody uses pseudonyms to harass and cause trouble. that word is `detweiler'. do you really know what `anarchy' is, cypherpunks? as the old parable goes, be careful what you wish for, you might get it. hal argues below that `you already know nothing about the people you interact with on the net' and that `anonymous remailers introduce no more problems than are already present on the net'. these seem to me to be flawed arguments. here's why. first of all, everyone has the experience of going to a party and knowing nobody there. but the fun of the party is learning about the people who are there! do we really want an online environment where identity is as transitory as a nym on IRC? it seems that what everyone is craving behind the banging on the keyboard is what has been called active, human `interconnection' to contrast it to `interaction' with a computer alone (still generally considered an inanimate object). if we want communities, the places we like to live in, it seems that identity is intrinsic to them. next, `anonymous remailers do not introduce any problems beyond those that already exist'-- aren't we trying to *solve* the problems associated with building an online community, our civilizations in cyberspace? it seems to me that if cypherpunks want the rest of the world to adhere to their ideas, they have to show how they are *superior* to those already present, and how they *solve* nagging problems. yes, remailers solve the problem of trying to post messages without identity, but are we sure this is a `problem' we want to `solve'? for example, hal notes that some system operators completely ignore complaints on the net. but do we really want a community of system operators that simply throw any feedback to /dev/null? what about when someone is mailbombing Usenet from a site? isn't what we *really* want a more basic definition of what is allowed and what is not? besides, under the cypherpunk vision, operators would never censor a user for postings-- but is it the case that all cypherpunks can say they have never tried to censor anyone by notes to sysadmins, i.e. of detweiler? regarding the pseudonymity issue, it seems to me a more basic, fundamental design goal might be this: we wish to make sure that people do not use sensitive private information against us. it is not a problem for our friends to know this information-- in fact it is critical that they do (friendship is based on identity!). the cypherpunk vision seems to split the world into two groups: those people i trust (my friends) and everyone else (whom i completely distrust with intense paranoia). this is a very xenophobic and chauvinistic philosophy at heart. hal argues below that there is `no line dividing the clean from the unclean' (real name vs. pseudonymous vs. anonymous etc.). to the contrary it seems to me to be the case that either `i know who you are' or i don't. what does it mean for me to `know who you are'? i admit there is no basic definition, but it does seem to me that should not prevent us from trying to find one. for example, it seems to me you cypherpunks have a very important agenda, but you seem to be extremists. the important goal is `defining what privacy really means' and cypherpunks seem to take the position, `it means that nobody knows anything about me'. our society simply cannot function under this constraint. if i wish to `interconnect', identity is necessary to minimize risk to the people i `interconnect' with. so what the cypherpunks might consider is a less extremist elucidation of what `privacy' means. for example, cypherpunks, what information should a bank be allowed to have on you when you go in to request a loan? what should companies be allowed to do with credit histories, and what rights does the individual have to influence them? if you continue to insist that `nobody should know who i am' i fear you will be bypassed by more sophisticated groups that have a less polarized view of issues of identity and privacy. and it will ultimately be the least controversial proposals that will shape the future we live in. the recent hal finney message as well as recent considerations of `morality' on the list (albeit quizzical) suggest to me you might be open to a more conciliatory, less dogmatic position on these immensely important issues. i am going to sign off for awhile in an attempt to advance some new meaningful projects (such as set up a gopher server), but i thank you for your stimulating conversations and email, and i apologize to anyone i have ever offended (send me mail if you feel i have personally left something unresolved). hal finney's message follows. pseudonymously yours, --tmp -----BEGIN PGP SIGNED MESSAGE----- I sent mail to Cypherpunks on this a couple of days ago, but it never appeared. There is a problem with the notion that all "anonymous" remailers and news-posting services should label their messages as anonymous so that users can decide whether to read them or not. This approach abandons one of the strongest arguments in favor of anonymous remailers, which is that the net is inherently an anonymous environment. Especially as more public access Unix systems, BBS systems, and so on become part of the net, we are going to see less and less of the strict controls on identity which were possible when the net was restricted to a few government labs and large universities. The level of anarchy will inevitably increase as larger numbers of people acquire net access. Unless massive and universal authentication efforts are undertaken, it is going to be more and more the case that you will know little about the true identity of a poster. Because of this, those who object to having to read the words of an "anonymous" poster are taking an untenable position. They are already reading words of people about whom they know no more than they would about an anonymous poster. And the argument that "non-anonymous" posters are subject to a form of discipline not available to anonymous posters - messages to the system operator - is clearly falsified by the existance of many sysops who care nothing about complaints. As more and more people run their own machines with net access, these cases will only increase. In short, we anonymous remailer operators have every right to be part of the net. We introduce no more problems than are already happening and will continue to occur as the net grows and becomes more universal. The resistance we've seen is from old-time sysops who are unable to adjust to a changing network environment. Rather than placating obsolete beliefs about network identity by agreeing to mark our messages with the scarlett letter A for anonymity, by accepting that we deserve to be in a ghetto set aside for inferior posts, I feel that we should challenge the net with messages that blur the distinction between anonymous and authenticated posts. The sooner people realize that there is no line that divides the clean from the unclean, the sooner anonymity will be widely accepted on the net. Hal Finney 74076.1041(a)compuserve.com -----BEGIN PGP SIGNATURE----- Version: 2.1 iQCVAgUBK7S2oqgTA69YIUw3AQEfagP8DlzINcvUDn7jc351S+hHTBz5NtB3RbRC l+0rgltFcn6QxWaE0GsWFcOa6RcPOe1DOTlwiJejiT6MbnfuDopbUoS98bCiIzLE 0Q2ZVhtsfLs5zFdUj08bRzzU7zyuzSmNoSsCx01O6OiGZB/zs0PEnx/0XqRtXFD2 RM1YTCPIF7Y= =0zw5 -----END PGP SIGNATURE-----

1 0

MacPGP and AOL
by fhalper＠pilot.njin.net 17 Dec '03

17 Dec '03

AOL will not allow me to upload MacPGP on the basis that there is a court case pending against the author, and therefore it should not be allowed. My question is since the court case is pending why can't they allow it on until a verdict has been reached? Is this common for commercial online services or ftp sites to ban it? ThAnks, Reuben Halper Montclair High -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.3 mQCPAi16KosAAAEEAMUwRni4a9+GbuAhHDLcBWK60hCJUYxhr2hYokpELAhx0ejp 2fq61Tu9Hjn051CN8Xy5nu6sv2ODfG/t59l4DJSb5pirQaII3zaX0rMX0ydwGDoW YakL4ow1lNY+d/k14KpIuUW404+fNuNhIGSkdVLQIfbOgh0preK7/P44AKvdABEB AAG0JlJldWJlbiBIYWxwZXIgPGZoYWxwZXJAcGlsb3Qubmppbi5uZXQ+iQCVAgUQ LXorceK7/P44AKvdAQEUxwQAoffTibRlwE5tNQVGvrulh1OQgXNhTRec9vUaUwPy U64FIZ+KnmdfYgiJYXtcItA90EB9MDexazKeqJzMOPShVNOfyiwy2yUlnQs425f8 DxBvM//zuvj6s4/mXDTPUZtG9PP0HVaEGTJY15JdfRqtj/w+HHnsHlgCnj0NnIhX TW8= =D9UX -----END PGP PUBLIC KEY BLOCK-----

2 1

Re: Zero Knowledge, Hamiltonian Cycles, and Passwords
by Hal 17 Dec '03

17 Dec '03

From: tcmay(a)netcom.com (Timothy C. May) > And yet suppose Alice shows you one. In a textbook, for example. How > did she "find" it? She likely didn't. Rather, she took 50 nodes, drew > a path visiting each node once, stored this as her 'Hamiltonian cycle' > and then proceeded to draw in 50 or 70 or whatever "other links," > which are "ringers," as it were (that is, they are never part of the > Hamiltonian she "constructed"). > > The resulting complete graph--50 nodes with maybe 100 or 500 or whatever > links--only she knows a valid Hamiltonian cycle for (there may be > others, which neither she nor anyone else will ever find). I think something like this may be the idea behind "obfuscated computing," which Mike Duvos was writing about here a little while back. The idea is that you do this trick not just with a graph, but with a boolean circuit composed of and, or, not gates, etc. Take your algorithm and express it as such a circuit, then obfuscate it by drawing in extra gates, connections, etc. The resulting circuit has your original circuit embedded in it, but figuring out what the total circuit does can be computationally intractable. Someone could build or emulate this circuit and get a result, but they would not be able to figure out exactly what formula they were computing. I'm not 100% certain that this technique is used, but Tim's posting reminded me that I had read something about this several years ago, and this is how I remember it. Hal

2 1

Re: Zero Knowledge, Hamiltonian Cycles, and Passwords
by Derek Upham 17 Dec '03

17 Dec '03

> A potential use for such systems is for passwords--one can prove one > has the knowledge without actually producing it (by typing in a > password, for example). I don't know that anyone is actually > exploring this application, yet, but I expect it'll come. Look at "Strongbox: A System for Self-Securing Programs" by J. D. Tygar and B. S. Yee in the "CMU Computer Science 25th Anniversary Commemorative" proceedings (from 1991). As the paper describes: ``Strongbox uses an authentication protocol derived from Rabin's observation about the square root operation: if one can extract square roots modulo n where n=p*q , p and q primes, then one can factor n . [That should be `if and only if', i.e., finding the square roots is too hard unless you created n in the first place.] Both our protocol and FFS are *zero-knowledge authentication protocols_* [. . .] And in contrast to Needham and Schroeder's authentication protocol, zero-knowledge authentication protocols require no central authentication server and thus there is no single point of failure that would cripple the entire system.'' In addition to zero-knowledge authentication, the paper provides an algorithm for the secure exchange of sessional symmetric encryption keys, and ways of combining authentication and key-exchange steps. I managed to get the key-exchange working some months back (in C++, using GMP to handle the number-crunching), but it was hampered by my incredibly slow 386 on one side and odd bugs in the Sun4 environment on the other. Contact me if you want to hack around on it. I also know where to find unreleased GMP 1.9 sources for some additional, probably more reliable, functions for calculating the Legendre symbol (which the whole system depends upon). Derek

1 0

Re: Zero Knowledge, Hamiltonian Cycles, and Passwords
by cfrye＠mason1.gmu.edu 17 Dec '03

17 Dec '03

Tim- I'd be interested in seeing your previous posts on this subject. Curt

1 0

talk encryption
by cheney＠hurricane.seas.ucla.edu 17 Dec '03

17 Dec '03

Hi. I was told I could ask you about an encryption system for the unix "talk". Do you know where I might find one? Thanks in advance, -mike

1 0

Day-One trailer
by Black Unicorn 17 Dec '03

17 Dec '03

Monday the 11th on Day One: Have we taken a wrong turn on the information superhighway? Looks like they are going to look into porn on the nets with a real bias media eye. I don't give day one much credit either.... -uni- (Dark)

1 0