Slashdot Mirror
Cryptographers Brace For Quantum Revolution
Tokolosh writes: An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.
Yes, and as far as I know it is still used. But single pad has always been inconvenient enough that it has only been used for the most secret, because it is a huge PITA.
I still like to take Grover's algorithm as an example of a somewhat mind-bending quantum computing application. Its typical use case is the search problem, i.e. searching for a particular value inside some form of storage like a database, and it can do so in O(sqrt(N)), which is quite simply impossible in classical computing since you have to visit every entry at least once (hence O(N)) to perform a full search. Now, Grover's algorithm is probabilistic in nature, so you may need to repeat the algorithm to determine the correct value, but value verification for such problems is generally simple (since the problems are generally at most NP-complete and NP-completion implies a P-space verification algorithm given a solution) and the number of repetitions is expected to be constant.
Of course, you can note that parallelization legitimately can compete with Grover's algorithm for very large datasets and very large thread counts, but on a purely theoretical level I still find it fascinating.
Quantum Computing does _not_ scale, as it cannot subdivide problems. You argument is completely bogus and in fact shows the opposite of what you think it shows.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.