At 02:18 AM 01/03/2003 -0800, Tim May wrote:
On Wednesday, January 1, 2003, at 08:55 PM, Michael Cardenas wrote:People do break cyphers, by finding weaknesses in them. Are you saying that you think that current cyphers are unbreakable?You know not whereof you speak.Breaking RSA or similar systems is very, very, very strongly believed to be related to, for example, factoring large numbers. Hill-climbing and landscape-learning algorithms are of no use.
That's one of the main points of doing mathematical cryptography, as opposed to the traditional "I can make a function too ugly for you to figure out" approaches. You can make definite statements about how hard it is to solve them, as opposed to vague statements about how ugly and unbreakable your functions are.
Yes, if by breakable we are excluding brute force factoring, mathematical breakthroughs that are "deep" (and unexpected) and which have nothing to do with dumb hill-climbing, or some application of Shor's algorithm with quantum computers. Give it up. Neural nets, simulated annealing, support vector machines, etc. are not going to factor a 1000-digit number.
To the extent that there's any use for this sort of stuff, it's in breaking symmetric-key algorithms by trying to imitate the traditional analysis methods of "follow the bits through the matrices and see if you can find a relationship between input and output bits", more likely as a tool to assist a human than as a solution method. It won't find you new principles like differential cryptanalysis or linear cryptanalysis or new principles like showing that some bit-twiddling function has an underlying group structure to it, but it might help you find the values of the objects in the group if you've guessed what the group looks like. Also, if your human analysis is able to find enough bits of the answer by wading through the ugliness of the bit-twiddling functions, a computer can do a brute-force approach to guess the rest of the bits, though it's not clear whether the best computer at that point is a vat of Adleman soup or just a Beowulf cluster of white boxes. Actually, neural nets to have another potential use, which is interpreting the sounds or badly videotaped pictures of the sender or receiver of a message typing the keys into their computers that you got from the bug the Department of Homeland Security planted in their wall. But that's probably not what you were looking for. They may also be useful for guessing human-picked passwords, as opposed to random-noise passwords, if you've got a couple of samples of passwords that your target has picked before. It's not as insightful as human guesses, but if it can guess faster, it can try more guesses.
I favor the more scientific approach, like the quantum many-worlds algorithmWhat if magic wands exist? What if time machines send the decrypted message backward in time?It seems that all of these analyses assume that an instruction is a single mathematical operation in a turing machine. What if each operation was something else? I refuse to believe that the human mind is just a turing machine.
that says "Guess an answer, if it's wrong, blow up the universe,
and if you're still there after the last step, you must be in the
version of the universe that had the correct answer".
But don't try that at home, kiddies.
Most of the algorithms treat each instruction as a single turing op
because the main alternative is to treat some operations as slower than others,
which makes the math a bit tougher without fundamentally changing the result;
it's just a scale factor, and if your argument is that neurons are wired together
more complexly than Turing machines are, as opposed to something about
the difference between minds vs. brains-as-wetware, it's still just a scale factor.
There are a class of problems known as NP-hard, which run on
Turing machines in "Non-deterministic Polynomial" time.
This basically means that instead of every step being deterministic,
there's a "Guess the correct value and input it here" operation,
and if you do that correctly, it only takes polynomial time to verify
that you guessed the correct value. So if you'd like to use the human mind
in ways other than just Turing machine steps, you can be the Oracle,
or go channel the answer from the fly on the recipient's wall,
or get some psychic vibrations from the Universe, and it'll test them for you.
Factoring is not necessarily in NP, but you can still verify in
small-polynomial time that a given answer is correct, while
brute-force guessing is roughly exponential time or slightly slower.
The Quantum Cryptanalysis work by Shor that Tim referred to says that
theoretically it might be possible to build a computer that can solve
some kinds of problems like factoring using electrons that
have a waveform which can be encouraged into collapsing into the
correct state most of the time, and for problems like factoring,
you can quickly verify whether it got the right answer.
The big technical problem is whether you can build a detector with
enough precision to measure the state that the waveform collapsed into
to get enough correct bits out of it to make the effort worthwhile
So far, there has been a quantum computer that was able to factor
the number "15" into "3*5", and I think somebody also built a 7-bit computer,
but until you start to get 500-bit precision out of it, it's not practical.
I'm not convinced it'll be possible to get passed Heisenberg Uncertainty
limits, which are something around 150 bits, but perhaps they
can do something with multiple electrons that are coupled enough that
they all jointly collapse into the correct answer, while each individual
one only needs to provide a small, and hence measurable, amount of precision.
Also, don't mix up Quantum Cryptanalysis with Quantum Cryptography,
which is a much different idea that's somewhat feasible today.
That's a method for transmitting data between a sender and receiver,
using the quantum stuff to make sure that an eavesdropper can't
receive any of the same bits that the receiver does,
because the eavesdropper's observation of any bits disrupts them,
and building enough protocol around it so that the eavesdropper can't
simply get the sender to send everything twice, once for each of them.
The initial versions ran on fiber, though there have been some things
done with free-space optics, but either way, it's only practical if
you're within line-of-sight or can afford to dedicate a fiber between
each sender and recipient; not practical for most people I know.
Bill
