Slashdot Mirror

← Back to Stories (view on slashdot.org)

Ask Slashdot: Echelon Protection?

Posted by Cliff on from the should-we-worry? dept.

An unidentified submittor had a worthy question and I want to submit it to you all for discussion: "How confidant should we be in private sector encrytion as a defense against ECHELON intercepts. The NSA probably has toys we will never hear about. Can we really trust PGP and FreeSWAN to defend personal and corporate data from the spooks? Should corporations begin hiring encryption experts to defend their data stream?" Slashdot has covered Echelon before, and in the midst of all the recent concern from Congress one can only sit and wonder how long it is before 'privacy' (or if you prefer, the illusion of privacy) becomes a thing of the past.

2 of 197 comments (clear)

  1. Sigint to noise ratio by Anonymous Coward · · Score: 5

    Ever wonder why the US government seems just as afraid of low level encrytion that they can crack fairly easily as of high level stuff that would take them weeks? Its because if PGP keys became common and the use of even light encryption became standard policy, it would bring the Echelon sniffers to a grinding halt.

    Think about the traffic that any sort of large sigint operation like this needs to filter through. If it took even a couple of seconds to descramble each message just to check for any red-flag words the entire system would rapidly backlog.

    Want to fuck with the Echelon project? Put the words "nuclear technology transfer funding" in the subject line of all of your email and encrypt it. It could be fun ...

  2. Re:P != NP by hpa · · Score: 5
    Uh, could you give such an example? It's probably worth a Turing Award at the very least.

    In case you didn't know, P ?= NP is probably the biggest unproven assumption in theoretical computer science today. Although it is widely believed to be true, noone has succeeded in proving it.

    Furthermore, your definition for class NP is wrong (your definition instead most closely applies to a different class often called RP); NP is most easily described in the following way: if you are given a solution, you can verify that it is indeed a true solution in polynomial time.

    In addition, your definition for polynomial time is wrong! Polynomial is time n^k where n is the size of the problem, and k is a constant; not k^n which rather would be exponential time (class EXP). For exponential time, it has been proven that EXP = NEXP; i.e. that nondeterminism buys you nothing when you have exponential time to play with (because you can simply enumerate all the possibilities and try them all.)

    Now, public-key cryptography (but not traditional cryptography) relies on the assumption that P != UP, where UP is the class of problems solvable in polynomial time on something called a unambiguous nondeterministic Turing machine; UP is a subset of NP and a superset of P. The assumption P != UP is actually stronger than P != NP.

    It is widely believed that P != UP != NP, but neither has been proven.

    Reference: Papadimitriou, Christos H.: Computational Complexity, Addison-Wesley, ISBN 0-201-53082-1. Excellent book.