- cypherpunks-legacy - lists.cpunks.org

Re: O(f(x))
by Jonathan Rochkind 17 Dec '03

17 Dec '03

> The way *I* learned it was like this: g(x) = o(f(x)) means that > g(x)/f(x) -> 0 (as x goes to some specified limit) g(x) = O(f(x)) > means that |g(x)/f(x)| is bounded (as x goes to some limit) > > In other words: a function that is o(f(x)) is of lower order than > f(x), while a function that is O(f(x)) is of no higher order than > f(x). Well, close anyway. Okay, here's straight out of my Discrete math textbook: "A useful way to check whether f [is a member of] O(g), is to look at the limit: Lim(as n->infinity) (f(n)/g(n)) In other words, we look at the _asymptotic_ behavior of f and g. If this limit exists (in practice it usually does) and is a finite number (possibly 0), we can conclude taht f [is a member of] O(g). If this limit is infinity, then f [is not a member of] O9g). For example, 7n**3 + 100n -3 [is a member of] O(n**3), because the limit of the ratio of these functions, as n->infinity, is the finite number 7. In fact, if the limit is a _nonzero_ number, as in this case, then O(f)=O(g). Okay, end of the quote. What all this stuff is used for is just comparing the running time of different algorithms. If you've got an algorithm whose running time varies with size of input n, according to the function 7n**3 + 100n -3, then this is _basically_ the same as if it varied according to n**3. Now, according to the definition of "big -oh notation ", which is what this is called, we could also say that function was an element of O(n**4), or O(n**20), or even O(3**n). So what big-oh notation really means is that function f is basically the same as, or better then, function g. But in practice we pick the "quickest" simple function g. So we call the functions (5n**4 + 4) (32n**4 +43n) and (n**4 +n**3 +n**2) elements of O(n**4). Which means that algorithms whose running times were described by those functions are all about the same speed, and are all about the same speed as n**4 too. Furthermore, any function which is O(n**k) for any k, is called _polynomial_. A polynomial algorithm is slow. Better is one which is an element of O(n log(n)), or even O(n), which is called _linear_. There ends the lesson. :)

1 0

(None)
by Jeff Gostin 17 Dec '03

17 Dec '03

Dan Harmon <harmon(a)tenet.edu> writes: > What do they know that we do not? Makes you wonder about all of PKP's > claims. Has PKP ever sued anyone over their patents or have they just > threatened? Very curious. They know that they have deep pockets. AT&T has some of the deepest pockets in the country, and could out-money PKP/RSA in yesterday's heartbeat. PKP fights little guys... that's all they've HAD to fight, so far. Now that they have a real opponent, who can meet (and surpass) their level of gameplaying, it'll be interesting to see what happens. --Jeff -- ====== ====== +----------------jgostin(a)eternal.pha.pa.us----------------+ == == | The new, improved, environmentally safe, bigger, better,| == == -= | faster, hypo-allergenic, AND politically correct .sig. | ==== ====== | Now with a new fresh lemon scent! | PGP Key Available +---------------------------------------------------------+

2 1

Re: L.J. Freeh and the Opposition
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

> Check out sunday's _Parade_ magazine for an article on Louis J. Freeh, the > director of the F.B.I. "Tough on crime", "man of the streets", and ruthless > eliminator of directors :-) If he ever throws his weight behind Clipper, the > battle will get *MUCH* tougher. Yeah. On the other hand, his weight *is* strongly, if quietly, behind Clipper - he's pushing the Digital Tele-phony Initiative to prevent the phone companies from offering real crypto, so that if one of them *does* decide to offer real non-Clipper encrypted service (e.g. cellphones), they won't be able to. If he were officially on the side of Clipper, then the Clipper forces wouldn't be able to say "it's purely voluntary"; for now they can pretend to be totally separate efforts.

1 0

Re: "The Virtual Hand": Free-market Internet guide
by Richard Johnson 17 Dec '03

17 Dec '03

> > >The Competitive Enterprise Institute is pleased to announce: > > > > > > THE VIRTUAL HAND > > > > > > CEI'S FREE-MARKET GUIDE TO THE > > > INFORMATION SUPERHIGHWAY > > >... > > > Alright, who let the spammer in? I subscribe to net-resources for this > > sorta crud; I don't need to see it here in cypherpunks. > > Didn't look like a spam to me. It looked like a very targeted ad > to a receptive audience. Cypherpunks contains, after all, a high... This part of the audience is certainly not receptive. I'm here to discuss crypto and its implications, not to have my mailbox filled with adverts. Keep the spam off. Unordered e-mail advertising (beyond a pointer to where to find more info) is indeed bad. If I wanted to read that guff in its entirety, I would have checked the Web, gophers, or FTP sites, etc. Richard

2 1

Re: Position Escrow System
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

But for now, the auxiliary Portable Position Escrow Devices (cellphones, to mix in the OJ thread) augment the satellite support. Under no circumstances shoudl citizen-units be permitted to put their PPEDs in moving vehicles driven by other people; fortunately, existing littering laws prevent people from tossing their cellphones into moving pickup trucks, and the forthcoming ban on Gun Transportation Devices should eliminate pickup trucks before the population as a whole notices. Meanwhile, plans to restrict citizen-units to their Position Escrow Zones unless carrying PPEDs are being evaluated, and a cost-benefit analysis versus enhancing the planned SmartCard systems will be forthcoming. ... And they think we're just working for the Post Office....

1 0

Andy Grove on Clipper
by Duncan Frissell 17 Dec '03

17 Dec '03

T >Denning, Andy Grove, and others. In this campaign, the second T >approach mentioned above will be dominant: a focus on pedophiles who T >"encrypt their list of victims," a focus on "terrorists who form T >virtual networks around the world," and a focus on "money launderers T >who use crypto anarchy to spread their poison." I agree of course that technological fixes are superior to political argument. In fact, I *use* technological fixes as a political argument. For example, "While you might like to censor video nasties, you should know that censorship is no longer technologically feasible. There are so many different communications channels that you can't possibly block all of them." It can be convenient to work on some anti Clipper/DTI soundbites though. Since coding sentences are more my specialty than coding software... "The administration wants us to spend $300 million of our own money to help them perform just a few wiretaps a year. It isn't worth it." "Yeah, and we could use torture to catch pedophiles too. Do you favor torture?" "Strong cypyto *prevents* crime by protecting people from criminals." "The government didn't think we needed strong crypto until the market demanded it. Why should we trust their judgement as to what kind we need?" "How does the government think that it can compete in a software and hardware market that will frustrate the brightest marketers around." "I guess the government thinks that forcing Microsoft, Novell, and IBM overseas so that they can incorporate strong crypto into their products is a good idea." DCF "Do you suppose the Feds can completely upgrade their hardware/software crypto system every 6 months to keep up with the market?" "In 1946, Soviet and U.S. electronics technology was approximately equal and the U.S. had a 10-year lead in nuclear weapons technology. By 1986, U.S. and Soviet nuclear weapons technology was approximately equal but the U.S. had a more than 10-years lead in electronic technology." Trust the market. --- WinQwk 2.0b#1165

1 0

RE: Beware of Roman Catho
by Duncan Frissell 17 Dec '03

17 Dec '03

N >It looks like Ralph Stokes has finally learned about Internet and N >Usenet gateways and is now spreading his prenicious religious N >bigotry beyond the borders of Fido-land. (He spammed several At least he's using PGP. We are making progress. Nothing wrong with a strong expression of religious opinion (as long as it was limited to the religious USENET groups and mailing lists). At least he's not asking for a new government program. Must be a lot of papists out there if they fear hearing the "truth" once in a while. DCF "If the language of the Authorized Version (1611) was good enough for our Lord Jesus Christ -- it's good enough for me." -- actually, not a bad read. --- WinQwk 2.0b#1165

1 0

Re: Having your own computer means never having....
by smb＠research.att.com 17 Dec '03

17 Dec '03

I can't think of any real security risks introduced by allowing employees the use of encryption, that weren't present already. Certainly none mentioned thus far fit the bill. Have a look at Matt Blaze's paper from Usenix last week. He describes a smart-card based key escrow system for file encryption -- the risk to the company is that an employee will quit, forget a password, walk in front of a truck, etc. -- at which point they're unable to get at the files that this person created -- files that the company owns in accordance with the provision of the free-market contract willingly agreed to by this employee.

1 0

Cell phone tracking
by die＠pig.jjm.com 17 Dec '03

17 Dec '03

Mike McNally writes: > > Jef Poskanzer writes: > > It looks like at least some switches in Amerika are already equipped > > to read out locations for individual phones. > > This is not actually that surprising. All they need is to know which > phones are using a band on a cell site, and they narrow the search > down to a relatively small area. I seriously doubt that they can do > triangulation (I mean, they *could*, but there's not much likelihood > that the cellular operators would incorporate something complicated A company I am familiar with which does specialized classified interception systems for the NSA and other TLA's has built just such a system for the TLAs. It can locate a cellphone to within a few feet just as soon as it starts transmitting - it uses time of arrival techniques to triangulate the cell phone's position. How many of these are installed and where I do not know, but the technology has been developed and is in use. The system is multi-channel and can keep track of many cellphones at once - but as a practical matter it isn't hard to monitor the control channels and paging channels to locate the phone of interest and identify which of the 866 channels it is transmitting on so even simple doppler DF technology might work. Considering that the LA area is the biggest cellular market in the country it wouldn't surprise me that some of the these systems are installed there. And in the future Phil Karn's company Qualcomm's CDMA digital cellphones will provide few feet accuracy position as a byproduct of the spread spectrum receive correlator operation on every transmitting phone within range of more than one cell receiving site unless they actually aviod trying to make the measurement. Most of the time more than one cell site tracks a given phone so they can vote on which one has the stronger signal - given that each of these sites has a precise estimate of the time of arrival of transissions from each phone it takes little more than netting of the time base (with GPS ?) between the cell sites to detemine cellphone positions since the positions of the cell site antennas are well known. I suspect that if the hardware and software to do this (mostly software) is not part of the current base station that certain TLAs will pay to have it developed and implemented. Dave Emery die(a)pig.jjm.com

2 1

Magic O(logn) RSA decryption algorithms
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

Complexity theory often uses the concept of an oracle, which is a function that gives you a correct answer in constant time; some oracles only hand out one bit at a time, while others give you more data than that. One reason that oracles are useful is that they give you lower bounds on how much work is required to do something - if a job requires O(f(x)) time with an oracle doing the hard parts, you know the whole job is at least that complex. NP completeness uses Non-Deterministic Turing Machines, which are one formalization of oracles - an NP complete problem requires polynomial time to solve if the Turing machine is allowed to make O(p(n)) correct non-deuerministic steps (e.g. gets the bits from an oracle), where p(n) is some polynomial or smaller function of the input size. (NP complete problems are normally formalized as a function that returns 0 or 1 depending on whether the input is a correct solution to the problem, so solving is equivalent to demonstrating that a given solution is correct.) So, if you've got an oracle around (and oracles cost more than the $10,000 Perry bet Jim, if you buy good ones :-), how much work does it require to demonstrate that the oracle just handed you a correct key? Public Key: n = pq, where p and q are secret, e relatively prime to (p-1)(q-1) Privatekey: d = e**-1 mod (p-1)(q-1), which is about logn bits long. Encrypting: c = m**e mod n Decrypting: m = c**d mod n n, d, c, and m are all about logn bits long; d may be a couple bits shorter. p and q may be shorter, but logp + logq = logn. One way to demonstrate that the oracle handed you a correct key is to encrypt a piece of data and then decrypt it. This requires two exponentiations, and two or more modulo steps. My copy of Knuth is buried somewhere, so I don't remember the complexity of mod n, but it's got to be at least log n or so. Encryption is fast, since e is a constant (fast is log n in this case), but decryption requires O(logn) multiplies, and each multiply takes at least logn steps since the answer has 2logn bits (it may be slower, I forget; it's probably logn * logn single-bit adds plus carries.) So the time required is >= logn**2, which is too slow for Jim. The other way to demonstrate that the oracle handed you a correct key is to show that de = 1 mod (p-1)(q-1), which requires knowing p and q, and is thus equivalent to factoring n, as Perry said. I suppose the oracle could hand you (p-1)(q-1) = pq-p-q+1 = n-p-q+1 without handing you p and q, but that's asking a lot from an oracle. Bill

2 1