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.
This is exactly the sort of situation where the NSA could be the most useful/helpful to us - but no one in tech will trust them to provide actually secure encryption protocols because of their elliptic curve shenanigans.
#DeleteChrome
RSA factorization using today quantum registers is more than useless; The last year largest number processed was: 56,153. The quantum decoherence is faster when the number of particle increases; And to defeat the RSA some huge quantum registers are required. The only question: is a quantum machine that can process useful computing operation is even possible?
Quantum computers capable of cracking the higher keysizes that we we have now will never exist, and thus this concern is pointless. People who think otherwise aren't aware of the physics involved, and how the only people left researching making this shit don't believe it will ever work the way people want, they just keep going because it is their bread and butter now. Gotta feed the family.
They are not talking about breaking AES or Two Fish encryption. They are worried about breaking the key agreement. Currently when a communication channel is set up the two parties agree on a key for encrypting the communication. This is normally done by Diffie-Helman (D-H) key agreement or one party could select a key and then give it to the other party using the other parties RSA public key. Both RSA and D-H are based on the difficulty of solving math problems that quantum computing should be able to easily solve.
.
Your AES encrypted file on your hard disk is safe. What the NSA is doing is storing your conversations and the key agreement. Years from now they might crack the key agreement and then decrypt your communication..
.
Things like Elliptic curve Diffie Helman are secure. So your Black Berry communications will still be safe, not sure who else widely uses EC (your ZigBee electric meter in the USA and UK)
Right now we have machines with a few cubits, analogous to a 1960 IC. It wouldn't surprise me too much if, in six years, we had machines with 2300 qubits. Maybe it'll be called the Intel Q4004. :)
In six years assuming anyone is still willing to waste their time and money there will very likely be "topological" quantum computers with 2300 qubits and they will be just as useless as desktop computers at cracking RSA. Real machines with 2300 entangled qubits would be able to perform operations that would not even be remotely possible in the current life of countless trillions of universes if every atom in every universe were a transistor operating at a trillion trillion trillion thz. It's completely bullshit.
As you probably know, for decades after, transistor counts doubled every TWO years. If the cubit count doubles every two years, that's going to be a problem for cryptography.
Moores law is a reflection of market forces. Doubling was enabled by halving cost enabled by market pressure to reduce costs enabling people to afford more capabilities for the same cost which fueled a never ending feedback loop.
There is no analogue to QC and BTW number of entangled qubits are NOT doubling every year.
We don't know if that's possible, but we didn't know that 386 was possible in 1970.
Nonsense it was then and mostly continues today to be an engineering problem.
Nobody has any idea how to scale out QC without being drowned out by noise.
Isn't single pad encryption still safe, though less convenient?
One-Time Pads, implemented and used correctly, are provably secure. That can never change, not even given infinitely-fast computers (which Quantum Computers aren't), because the proof demonstrates that the ciphertext gives you NO information about the plaintext. No amount of computation can extract information from an empty set.
However, one-time pads are also pointless. Oh, there are some very isolated contexts in which they can be usefully applied, but they're useless for nearly everything we use cryptography for today. The one-time pad scheme requires securely distributing the pad, which must be as large as the message to be sent. If you have some channel you can use to distribute the pad securely, why not just use that channel to send the message?
Symmetric cryptography (e.g. AES) improves on the one-time pad by reducing the size of the key material from as large as the message (possibly many gigabytes) to something very small. Say, 16 bytes. So you give up provable perfect secrecy in exchange for only needing a way to securely distribute 16 bytes.
Asymmetric cryptography (e.g. RSA) improves on symmetric cryptography by eliminating the need for every pair of potential communications endpoints to securely exchange symmetric keys. Instead, every potential recipient can publish a its "public" key to every potential sender. This distribution of public keys does need to be secure, but the security requirement is weaker. Symmetric keys need to be kept secret, public keys do not; instead we only need to ensure their integrity, that the potential sender got the actual public key of the potential recipient.
Asymmetric cryptography can be used to further reduce the scope of this problem by using its ability to digitally sign certificates, proving the legitimacy of a given public key assuming (a) the recipient of the certificate has securely received the public signing key and (b) the private signing key is not compromised and is only used to sign legitimate public keys. Thus, the key distribution problem is reduced to a "bootstrapping" problem; we just have to get Certificate Authority key(s) securely. In practice we do this by distributing the bootstrapping keys in system software.
However, asymmetric cryptography has a lot of issues compared to symmetric cryptography. One of the largest is that the public/private key pairs must have some particular mathematical relationship with each other and with every message encrypted or signed. Thus, asymmetric cryptography is deeply dependent on the existence of "one-way" mathematical operations: operations that can be efficiently computed in the forward direction but are intractable in the reverse direction. We don't actually know that any such operations exist, though we have a bunch that we know how to compute efficiently in one direction but not the other. These one-way operations tend to be touchy, though; small errors in constructing messages and performing computations can compromise the security (for example, consider the critical importance of correct padding of RSA plaintexts before encryption; do it wrong and you can potentially hand the adversary your private key).
There are also lots of practical issues with asymmetric cryptography. It's relatively slow and expensive (some techniques more than others), and that opens it up to more side channel attacks and other practical attacks. Then there are issues with the CA system; it's awesome that we can reduce the key distribution problem from one that requires secure pairwise exchanges between billions of devices to broad distribution of a few hundred bootstrapping keys... but that means those bootstrapping keys are incredibly important and every link in the bootstrapping chain becomes an extraordinarily tempting target for extra-cryptographic compromise (e.g. "rubber hose cryptanalysis").
Another issue is quantum computing.
Symmetric ciphers are theoret
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.