Hi, a timeline question, and some math about encryption

[Roger]

Today has turned out to be busy and unexpectedly tiring. Have some thoughts re both encryption and your other ideas, but going to head to bed now as starting to doze off.

Will aim to post in the next day or so.

Thanks!

Todd

EDIT: Actually, a couple of quick questions that had come to mind and that I can post quickly regarding the issue of encryption:

1) How does the use of quantum computing - particularly high powered quantum computing - impact the encryption issues you raise?

2) How does the use of quantum encryption impact the encryption issues you raise?

Are these two (currently nascent or theoretical) technologies already addressed (apologies if they are mentioned in the papers you cite, haven't had a chance to look at them yet) or would they have the effect of blowing all of this out of the water? Or not impacting it at all?

Thanks!

Todd

Neither -- it's more that quantum computers add some complexities and twists, while keeping the main structure intact. P =? NP has a quantum equivalent version, which for historical reasons is called MQP =? QMA. If P = NP, then I think it's extremely likely that MQP = QMA -- and similarly if MQP = QMA then I think it's extremely likely that P = NP (though proving either of these might be hard). It definitely is the case that P < MQP and NP < QMA -- a quantum computer can always act as a classical computer and run a classical algorithm if it wants to, so it's always at least as strong as its classical equivalent, and (even if P = NP, i.e. even if the classical computer is actually far stronger than we think) there provably are some things a quantum computer can do exponentially faster. The set of possibilities for average cases, one-way functions, and trapdoor functions in the quantum computing case is likely to similar to what the paper I linked to outlined for the classical case, but there could be more wrinkles in the details, and the proofs are likely to be even harder (at least to a non quantum intellect).

While most currently known forms of public-key encryption are trivially breakable on a quantum computer, that's thought to be due to rather special properties of the widely used public-key algorithms -- specifically, that they are based on the difficulty either of factoring or Abelian subgroup finding, both of which unfortunately for the codemakers are in the rather small set of problems where MQP (i.e. problems only polynomially difficult on a quantum computer) is (assuming P != NP) exponentially stronger than P (i.e. the same for a classical computer). [The difference mostly boils down to "quantum computers can do the Fourier transform to any accuracy in constant time, unlike classical computers which take O(n^2) in the desired accuracy" -- so if you have a problem where doing a Fourier Transform once or repeatedly is useful, this provides a massive speedup, and if you don't, it doesn't. Between that and Grover's algorithm (a much more widely usable trick, but only giving an O(n) to O(sqrt(n)) speedup), quantum computers are almost a two-trick pony -- a lot of the quantum speedup algorithms are some sort of mutated version of one, the other, or both of those.] There are other, not-yet widely used public key algorithms that don't suffer from this problem since they dont involve factoring or Abelian subgroup finding (they tend to be a good deal slower and/or have much bigger key/certificate sizes, and are newer so their security is less well understood) and so are thought not to be significantly easier to attack on a quantum computer than on a classical one (other than the n -> sqrt(n) speedup from Grover's algorithm, which basically just requires you to double your key or hash length to counterballance it -- not a big deal). The same is believed to be the case for almost all private-key encryption (since none of that is dependent on factoring) -- assuming that P != NP, i.e. assuming that "encryption" is a valid concept.

[Interestingly, if you switch from Quantum Mechanics to a Hidden Variables Theory and allow gates in your computer to peek at the Hidden Variables (i.e, it's a Not-Entirely-Hidden Variables Theory, and your computronium can make use of this) then this gives an even stronger version of computation tan a  quantum computer, which lets you crack not just factoring and Abelian subgroup finding, but also at least most of the other problems that people have figured out how to base public key encryption on -- so if that were actually physically true it might turn out to rule out the Cryptomania scenario. So again, that's an example of the sort of level of change to the physics of computation that would definitely alter the allowed set of Toposophics, for the better -- but it's a lot more drastic than just rearranging the Standard Model or tweaking the values of a few constants. Also there are a lot bigger problems with Hidden Variable Theories than that -- they pretty much explode as soon as you try to combine them with Special Relativity.]

Quantum encryption is an entirely different thing -- it's not breakable by cryptanalysis, no matter how strong, and it's protected by a combination of the structure of quantum mechanics and the sensitivity of whatever eavesdropping detection you have built into it (which needs to be single-quantum-sensitive, though there have been badly-engineered laboratory attempts to implement it where that failed -- at least if deliberately dazzled -- so it wasn't secure). Probably the closest classical encryption equivalent would be a one-time-pad (though the logic of why each is uncrackable no matter what computational resources you have is rather different)