- cypherpunks-legacy - lists.cpunks.org

provably hard PK cryptosystems
by Adam Back 17 Dec '03

17 Dec '03

extracting from part of another thread... Dimitri Vulis <dlv(a)bwalk.dm.com> writes: > Adam Back writes: > > [...] I think I remember that you posted some time ago a way to have > > two plausible decryptions for one ciphertext, to enable things like > > duress keys, in terms of RSA. The problem with this, however is > > that RSA is currently very slow to use in its pure form for > > messages. > > I don't recall this one... My feeling about RSA is that one of these > days there will be a breakthrough allowing much faster factorization > (either through a better algorithm on a conventional computer, or by > a practical quantum computer) and then all the codes based on > factorization will become essentially plaintext. It's time to start > looking for other hard problem to base PKC on. 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. RSA has always had problems with two pitfalls in any proof of its hardness: no proof that RSA is as hard as factoring, and no proof that factoring is hard. Rabin and variants of it at least have the proof of being as hard as factoring. You mentioned your opinion that a vastly better factoring algorithm may yet be found. What about the possibility of finding proof of a useful lower bound for the complexity of factoring, do you have any thoughts on the likelihood of this being achieved? That would be a very significant result, and in the absence of a quantum attack would be as good as it gets. It would allow you to make realistic calculations about physical limits of attacking it, in a similar manner to the entropy calculations possible for brute force of symmetric ciphers. (Heat death of the sun before a solution even if every particle was part of hardware key cracking computer type arguments). 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 cypherpunks a short time ago was talking about a researcher who had constructed a crypto system related to the problem of finding paths in a tiling problem (sounded like the same problem). The interesting part was that the researcher was reported as having a proof of hardness. Similarly is this being reported accurately? > E.g., does anyone know of any progress made on public-key > cryptosystems based on the word problem in semigroups, described in > Neal Wagner and Marianne Magyarik, _A public key cryptosystem based > on the word problem_, Advances in Cryptology: Proceedings of Crypto > '84, G. R. Blakley and D. Chaum, eds., Lecture Notes in Computer > Sciences #196, Springer Verlag, 1985, and also mentioned in Wayne > Patterson, _Mathematical Cryptology for Computer Scientists and > Mathematicians_, Rowman and Littlefield, 1987? Not familiar with the problem. Is it something you could explain briefly, or are there any on-line papers on the subject? > >From what I neard, NSA tried very hard to implement it and failed, > and the Soviets actually built a cryptosystem similar to what they > described. I tried to duplicate what the Soviets supposedly did, but > without success. Adam -- #!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj $/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1 lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

1 0

LD
by blanc 17 Dec '03

17 Dec '03

Dr. Dimitri Vulius, you made this remark to someone: ...You really should get to know L.D. better before you repeat the lies Timmy May spreads about him. ......................................................................................... May I recommend that you read the content within these urls: http://www.csn.net/~ldetweil/ and especially: ftp://crvax.sri.com/risks/15/risks-15.27 (and 28) These contain a history which will clarify for you some of the comments made about L.D.'s relationship to the list, Tim May, etc. .. Blanc

1 0

RE: Where to write crypto?
by Will rodger 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- On Sat, 21 Sep 1996, Dan McGuirk wrote: >>| > If I want to go to a country outside the United States to write >>| > cryptographic code that will be freely distributable, what's the best >>| > place to go? >>| >>| Or, on the other hand, is there no way that a U.S. citizen can legally do >>| this? >> To which Adam Shostack replied: >> Thats not clear. The ITARs seem, on their face, to create a >>prior restraint on speech based on its content, and forbid Americans >>the right to leave the country to pursue their livlihoods. The odds >>of geting persecuted seem pretty low. Could be. But prominent crypto atty. Ken Bass told me he thought such actions would be vigorously prosecuted - quicker than you could say "global proliferation." Thing to notice here: no prominent cryptographer in the US has come forth and said "yes, I helped write strong crypto abroad." Which isn't to say most of them aren't traveling abroad frequently these days - take, e.g. the presence of M. Blaze, W. Diffie et al. at the OECD in Paris this week. >> As to the (predictable) comment that I'm not doing this, I'd >>be happy to entertain offers of crypto work that are not in the US, >>possibly leading to me being a test case. >> Call before you do, Adam; I'd kill to have that story first... Will Rodger Washington Bureau Chief Inter@ctive Week -----BEGIN PGP SIGNATURE----- Version: 2.9 iQEVAgUBMkXvQ0cByjT5n+LZAQGLyQf8Ctlf2JVeYI8Ws47YovJ0fhF3nzf9ihLd nHzZNqGpEVGVcOXYw2u84jV68y9Y7M3vdo/BDZCA3G0T8zZopmpiNZHgblh15ndP jPdYRkz4+7NnEn/Tz/1LQS6SVp/LA1G/qoCCNqGuYneSVkZxxsoeoEp9ZdCMhDE9 iq7IEI+pyY44vnSWvo65YNQZXt4thf94E94pspoNWC+DNwRDj8BkK28MpM3vduqD i/cViVUcKOLVg/b31HTVrq0rwWClfD0+J4a4F8AcGcf4SwedGCVaUAdSWRw0FQTJ 6AioCSd5Cs/g9k+xxaqRMzExJcBphwnlCZvA+qpgjY+KdagaEqJwGA== =vyTv -----END PGP SIGNATURE-----

1 0

Re: Bernstein hearing: The Press Release
by jim bell 17 Dec '03

17 Dec '03

At 05:15 PM 9/22/96 -0700, Rich Burroughs wrote: >At 04:39 PM 9/21/96 -0800, Jim Bell wrote: >>At 02:03 PM 9/18/96 -0700, John Gilmore wrote: > >[snip] >>>* Any legal framework that allows a government bureaucrat to >>>censor speech before it happens is an unconstitutional prior restraint. >>>The government is not allowed to set up such a drastic scheme >>>unless they can prove that publication of such information will >>>"surely result in direct, immediate, and irreparable damage to our >>>Nation or its people" and that the regulation at issue is necessary >>>to prevent this damage. >> >>At the risk of being a devil's advocate, let me suggest that you are >>conceding too much even with the preceding paragraph. The 1st amendment >>says nothing about preventing speech which (even admittedly) would result >>in "direct, immediate, and irreparable damage to our nation or its people." >[snip] > >Jim, that's a quote of Potter Stewart from the Pentagon Papers case, if I'm >not mistaken. It's not written in the Constitution, but Supreme Court >precedent is the next best thing as far as con law goes. Under the circumstances, I think it would be wise to actually EXPAND our protections. A lot has happened in the last 25 years. If a reasonably extensive list were made of situations and circumstances where the wool was pulled over the eyes of Americans by government...and how subsequent developments showed that these things were best revealed THEN and not later...it could be reasonably argued that there is no or almost no area where the "direct, immediate, and irreparable damage" exception is likely to realistically exist. You should point out that the Pentagon Papers case was decided notwithstanding an extraordinarily generous set of assumptions common in Cold-War America about the power and authority of government, many if not most of which would be no longer considered valid. Put the opposition on the spot: Insist that they provide a substantial number of examples where speech was expected, was attempted to be restricted by gov't under such an exception, where that speech actually occurred (either by refusal of the court to intervene or by refusal of a party to the case to restrict his speech), and show how this actually caused any "direct, immediate, and irreparable damage." In the absense of such examples, it is reasonable to presume that, generally, they don't exist or are so rare as to be ignorable. (For example, in the Progressive case from the middle 70's, the gov't dropped its case. What harm occurred?) >The government can restrict speech in time, place or manner, according to >the courts. Restricting content is more difficult, and places a much >heavier burden on the gov. > >To expect people writing about and arguing the case to completely ignore >the existing case law is foolish, IMHO. I am _not_ suggesting that case law be "ignored." Rather, point out that the case law, even though it goes in your favor, was still decided in a thoroughly biased atmosphere and therefore further reductions in government authority are appropriate. Jim Bell jimbell(a)pacifier.com

1 0

A daily word of caution in reference Tim C[unt] May
by Dustbin Freedom Remailer 17 Dec '03

17 Dec '03

Tim C[unt] May is not only as queer as a three dollar bill, but he is also into having sex with children.

2 1

Kicking the Furriners out of our Classrooms
by tcmay＠got.net 17 Dec '03

17 Dec '03

At 6:19 AM 9/23/96, Matthew Gream wrote: >Hi there, > >> An anonymous opinion from inside the Defence Dept holds that electronic >> bits on a wire do not constitute goods, and as a result if you ship >> electronically, you are not subject to the regulations. If you ship a >> CD or floppy or other physical media containing software, you violate the >> regulations. > >Watch out for those anonymous opinions; I received exactly the opposite >opinion when I spoke to the Defence Signals Directorate about the issue >(back in 1994) -- after specifically asking about a few hypothetical >cases. Of course, either opinion may be correct, which is the real >problem! Cindy Cohn made the excellent point at the Bernstein hearing that the ITARS are so vague and overbroad that a professor cannot be sure if his lecture is violating the law because foreigners are in the audience (a la the Junger case). As she notes, nearly all college and postgraduate classes are heavily populated by non-U.S. citizens, and the ITARs specifically make illegal the propagation of certain items to non-U.S. citizens. (There is no exemption in the ITARs for university professors teaching their classes. If foreigners are in the classroom, and cryptographic or weapons-related knowledge is imparted, an ITAR violation has probably occurred.) Personally, I'd relish the opportunity to say to my class: "Now, the International Trafficking in Arms Regulations, the ITARs, make it a felony for me to disclose certain methods or techniques to non-U.S. citizens. Accordingly, in this class, I must insist that all non-U.S. citizens, or suspected Israelis, ragheads, Papists, or Marxists, illegal Mexicans, etc., leave the lecture hall immediately. All those remaining must present at least five forms of identification, dating back at least to 1978. Foreign-looking persons should provide at least seven forms of identification, including documentation that they are not in the U.S. illegally. Jew-looking or Jew-sounding names will be subjected to special scrutiny to ensure that they are not dual-citizens with the ITAR-restricted Zionist Entity. "Oh, and since classroom participation counts for 65% of your grade, those I exclude under the ITAR restrictions had better score 155% on the exams I let you into the classroom to take, else you'll flunk. Good luck, you fucking foreigners!" (Cindy Cohn pointed out to the court that their might also be 14th Amendment problems with enforcement of the ITARs with regard to teaching in universities.) --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(a)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."

1 0

Re: Mercenaries
by tcmay＠got.net 17 Dec '03

17 Dec '03

At 4:45 AM 9/23/96, Brian Davis wrote: >On Wed, 18 Sep 1996, Timothy C. May wrote: >> Brian Davis, our former Prosecutor, can tell us how likely it is that any >> person would be charged and brought to trial for being a paid mercenary for >> some small country in the Third World. The CIA is often behind such >> mercenaries, so national security issues could make the issue murky. > >Exceedingly unlikely. A variety of practical problems. If you came up >to a U.S. Attorney to show him your picture on the cover of The Zaire Daily >News as mercenary of the week and spit in his face, you'd get prosecuted. > >For spitting in the prosecutor's face. > >On a slightly more serious note: you'd only get prosecuted in someone at >Main Justice (i.e. in Washington) wanted you prosecuted. This of course matches my expectation. I still think if prosecution is so unlikely, the law ought to actually come to terms with this and remove the "official illegality" of such things. _Almost_ more important to me than "libertarian" ideals are "consistency" ideals: namely, that there oughtn't to be laws which are not enforced, or which are too expensive to enforce, or which can be selectively enforced. And since I know that the full suite of laws, all 25,000 or 45,000 of them (on all 27 linear feet of bookshelf space) cannot possibly be consistently enforced, I favor a "minimalist" or "fallback" position of having relatively few laws, covering mostly "crimes" which are more easily detected and prosecuted (with draconian punishments). >> But the real reason such prosecutions are rare is that the government >> realizes how Orwellian it sounds to say: >> >> "You are being prosecuted because you were a mercenary for Oceania in its I was probably overstating things to say this was "the real reason." The real reason (or the more important reason) is that resources are finite, and, as Brian noted, no prosecutor is much interested in someone being in Zaire's mercenary army. It doesn't register on the public's concern meter, and it probably doesn't get one promotions in the prosecutorial community. But the law should still be changed to reflect this reality. --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(a)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."

2 1

Re: provably hard PK cryptosystems
by tcmay＠got.net 17 Dec '03

17 Dec '03

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(a)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."

6 5

Public Schools
by tcmay＠got.net 17 Dec '03

17 Dec '03

At 4:31 AM 9/23/96, Lucky Green wrote: >On Sun, 22 Sep 1996, snow wrote: >> I would agree that parents can do as good or better at _most_ subjects >> thru about the 3rd or 4th grade, and I do agree that most of todays schools >> are shit, however there is one area--social skills--that homeschooling >> simply can't compete. Children need to learn how to interact with one another >> in groups larger than a family unit. I don't think that homeschooling can >> accomplish this nearly as well as the public (or private) schools could. > >I understand that many parents that homeschool belong to organizations >that provide for meetings twice a week in which the children so educated >in a certain area get together. Homeschooling does not have to stand in >the way of a normal socialization process. Also--and I mean this point completely seriously!--many parents are not altogether convinced that the "public school socialization" is all that beneficial. Do kids really _need_ to learn to wear gang colors, smoke to be cool, get pregnant at age 14, and so on? An awful lot of accomplished persons grew up in isolated areas, on small farms, and were educated in very small classrooms (or at home). I think the "social skills" Snow talks about above are actually the _worst_ part of public schools in fin-de-Siecle America. If I had a kid, I wouldn't want him or her in the local public schools. (And my area is more remote than over in San Jose--San Francisco, which is even worse. And LA is even worse.) --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(a)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."

5 5

Re: Position escrow (triangulation, cell "remailers")
by Austin Hill 17 Dec '03

17 Dec '03

The Navy's Onion Routing project (www.onion-router.net) actual makes reference to anonymous cell phone networks by using encrypted proxies (Onions). The current implementation is IP based, but the briefing documents refer to any public networks including pager and cell networks. -Austin Quoted text from Phil Karn (karn(a)qualcomm.com ) on 4/22/98 12:33 PM >>On cell "remailers": Why resend the cell signal? Why not instead set up a >>generic phone call resender, which could be used by cell users and >>non-users alike? As long as you use the call resender for all of your >>important calls, the feds (and others) will find it very difficult to >>figure out what cell phone ID to triangulate or home phone number to tap > >Exactly. And I think this brings the remailing concept full >circle. Wasn't the basic idea invented for telephones way back in >(alcohol) Prohibition days? As I recall, a device called a "cheesebox" >connected two phone lines. When a call came in on one line, it went >back out on the other. You'd place a cheesebox in some third party's >back room, e.g., a restaurant owner who was paid for the privilege and >to keep his mouth shut. If the cops traced a call, it would lead them >to the restaurant owner, who would tip off the bootleggers. > >Does anyone have any historical references for these things? I think it >would be fun to see how an earlier age made use of anonymous remailers >based on a much simpler technology. > >Phil > > _________________________________________________________________________ Austin Hill Zero-Knowledge Systems Inc. Chief Technical Officer Montreal, Quebec Phone: 514.286.2636 Fax: 514.286.2755 _________________________________________________________________________ "Anonymity represents for many people a liberating even more than a threatening phenomenon." -Harvey Cox, The Secular City

1 0