5 ms·

People often mention quantum computing will break all encryption. Would that be a non-matter computer?

by aw3c2 14y ago

noselasd 14y ago
That's because quantum computers are still a pipe dream, so people assume it can do anything. Anyway, no - http://security.stackexchange.com/questions/25375/why-not-use-larger-cipher-keys http://security.stackexchange.com/questions/25375/why-not-us... tells us that you'd need the energy of all the output of our own sun for 32 years to even just count to 2^192
- Bakkot 14y ago
  Quantum computers have a fairly well-studied mathematical abstraction about which we can reason quite well. Algorithms for quantum computers exist which will break RSA; no similar algorithms exist to break AES. And the link actually only applies to traditional computers; quantum computers have no analogue of destructively setting a bit, because all operations on a quantum computer are fundamentally reversible, and hence do not entail any inherent energy loss to entropy.
Devilboy 14y ago
Public key crypto schemes (RSA, elliptic curve etc.) are vulnerable to some variation of Shor's algorithm. We'll have to move to quantum crypto when this happens. Hell for all I know D-Wave's machines can already break RSA for the DHS. http://www.infosecisland.com/blogview/19707-The-Emerging-Threat-to-Public-Key-Encryption.html http://www.infosecisland.com/blogview/19707-The-Emerging-Thr... The 256 bit key size is still the recommended maximum since no increase will help against quantum computers.
Scaevolus 14y ago
Not all. Academics refer to it as "post-quantum cryptography", see http://pqcrypto.org/ http://pqcrypto.org/ From a talk by D. J. Bernstein http://cr.yp.to/talks/2008.10.18/slides.pdf http://cr.yp.to/talks/2008.10.18/slides.pdf : RSA: Dead. DSA: Dead. ECDSA: Dead. ECC in general: Dead. HECC in general: Dead. Buchmann–Williams: Dead. Class groups in general: Dead. Still alive: Hash-based cryptography. Example: 1979 Merkle hash-tree public-key signature system. Code-based cryptography. Example: 1978 McEliece hidden-Goppa-code public-key encryption system. Lattice-based cryptography. Example: 1998 “NTRU.” Multivariate-quadraticequations cryptography. Example: 1996 Patarin “HFE^V-” public-key signature system. Secret-key cryptography. Example: 1998 Daemen–Rijmen “Rijndael” cipher, aka “AES"
- stcredzero 14y ago
  So, basically, we won't have any means of key exchange which isn't quantum crypto.
  - marcosdumay 14y ago
    I don't realy like rocking a boat... but quantum cryptography can't realy be used in practice. Or, better, any practical implementation of quantum cryptography is succeptible to attacks. And the entire thing still needs an authentication method, guess what we use for authentication nowadays.
    - fjorder 14y ago
      It is being used in commercial systems (e.g. idquantique). Practical implementations are prone to vulnerabilities, but none have been found that cannot be remedied. Some techniques such as device independent or measurement device independent QKD offer to make it far more difficult to come up with attacks in the future too. The #1 advantage of QKD is not that the methods being used today will be immune to all attacks found in the future. It's that quantum states are unclonable, so there's no way to archive cipher-text for future attacks, as can be done with classically encrypted messages. e.g. If you send encrypt a message and send it via email today, the encryption method has to stand up to advances in algorithms and computational hardware for as long as the information remains sensitive. If you send something via QKD, an eavesdropper must break the protocol at the moment you send the message or it will be safe for all time. Authenticating strangers, as in credit card transactions, is something that quantum computing may disrupt. QKD can be used safely by people who have met at some point in the past, but we probably have a bit of time before CC transactions need to be encrypted by QKD. i.e. While you should probably not send medical records or state secrets via many classical encryption protocols now, your CC info will change in a couple years so it's not as big of an issue if your transactions are cracked a few years after that.
  - Scaevolus 14y ago
    No. One of the most promising is NTRU, an asymmetric cryptosystem which isn't broken by quantum computers. Many key exchange protocols treat the asymmetric operations as black boxes, so you can replace RSA with any other asymmetric cipher.

People often mention quantum computing will break all encryption. Would that be a non-matter computer?

by aw3c2 14y ago

People often mention quantum computing will break all encryption. Would that be a non-matter computer?

That's because quantum computers are still a pipe dream, so people assume it can do anything. Anyway, no - http://security.stackexchange.com/questions/25375/why-not-use-larger-cipher-keys http://security.stackexchange.com/questions/25375/why-not-us... tells us that you'd need the energy of all the output of our own sun for 32 years to even just count to 2^192

Bakkot 14y ago
Quantum computers have a fairly well-studied mathematical abstraction about which we can reason quite well. Algorithms for quantum computers exist which will break RSA; no similar algorithms exist to break AES. And the link actually only applies to traditional computers; quantum computers have no analogue of destructively setting a bit, because all operations on a quantum computer are fundamentally reversible, and hence do not entail any inherent energy loss to entropy.

Devilboy 14y ago

Public key crypto schemes (RSA, elliptic curve etc.) are vulnerable to some variation of Shor's algorithm. We'll have to move to quantum crypto when this happens. Hell for all I know D-Wave's machines can already break RSA for the DHS. http://www.infosecisland.com/blogview/19707-The-Emerging-Threat-to-Public-Key-Encryption.html http://www.infosecisland.com/blogview/19707-The-Emerging-Thr... The 256 bit key size is still the recommended maximum since no increase will help against quantum computers.

Scaevolus 14y ago

Not all. Academics refer to it as "post-quantum cryptography", see http://pqcrypto.org/ http://pqcrypto.org/ From a talk by D. J. Bernstein http://cr.yp.to/talks/2008.10.18/slides.pdf http://cr.yp.to/talks/2008.10.18/slides.pdf : RSA: Dead. DSA: Dead. ECDSA: Dead. ECC in general: Dead. HECC in general: Dead. Buchmann–Williams: Dead. Class groups in general: Dead. Still alive: Hash-based cryptography. Example: 1979 Merkle hash-tree public-key signature system. Code-based cryptography. Example: 1978 McEliece hidden-Goppa-code public-key encryption system. Lattice-based cryptography. Example: 1998 “NTRU.” Multivariate-quadraticequations cryptography. Example: 1996 Patarin “HFE^V-” public-key signature system. Secret-key cryptography. Example: 1998 Daemen–Rijmen “Rijndael” cipher, aka “AES"

stcredzero 14y ago
So, basically, we won't have any means of key exchange which isn't quantum crypto.
- marcosdumay 14y ago
  I don't realy like rocking a boat... but quantum cryptography can't realy be used in practice. Or, better, any practical implementation of quantum cryptography is succeptible to attacks. And the entire thing still needs an authentication method, guess what we use for authentication nowadays.
  - fjorder 14y ago
    It is being used in commercial systems (e.g. idquantique). Practical implementations are prone to vulnerabilities, but none have been found that cannot be remedied. Some techniques such as device independent or measurement device independent QKD offer to make it far more difficult to come up with attacks in the future too. The #1 advantage of QKD is not that the methods being used today will be immune to all attacks found in the future. It's that quantum states are unclonable, so there's no way to archive cipher-text for future attacks, as can be done with classically encrypted messages. e.g. If you send encrypt a message and send it via email today, the encryption method has to stand up to advances in algorithms and computational hardware for as long as the information remains sensitive. If you send something via QKD, an eavesdropper must break the protocol at the moment you send the message or it will be safe for all time. Authenticating strangers, as in credit card transactions, is something that quantum computing may disrupt. QKD can be used safely by people who have met at some point in the past, but we probably have a bit of time before CC transactions need to be encrypted by QKD. i.e. While you should probably not send medical records or state secrets via many classical encryption protocols now, your CC info will change in a couple years so it's not as big of an issue if your transactions are cracked a few years after that.
- Scaevolus 14y ago
  No. One of the most promising is NTRU, an asymmetric cryptosystem which isn't broken by quantum computers. Many key exchange protocols treat the asymmetric operations as black boxes, so you can replace RSA with any other asymmetric cipher.