4 ms·

Nothing significant until we have many more qubits. With 128 qubits you could crack 128 bit RSA encryption in a few mins.

leecarraher 9y ago
citation? A theoretical understanding of bits in quantum superposition would support the notion of traversing all combinatorially related possibilities however that is not the case for any realizable quantum computer. Realizable machines are based on specific quantum logic gates. otherwise you would have to design at the electron level, a new processor for every problem.
- marcosdumay 9y ago
  Here's the citation: https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm You do need to update yourself. There are standard gates, complete computation theories, and algorithms for lots of interesting problems. Those aren't even new.
  - leecarraher 9y ago
    aes isn't broken by factorization of composites of prime. if the op had said rsa, sure, but they said aes (it was changed you can tell because there was never such a thing as 128bit rsa), but thanks for telling me about that "new" shor's algorithm devised in 1994.
    - marcosdumay 9y ago
      Yes, comment edition sometimes leads to misunderstanding. But there was 128bit RSA, it was in use up to the middle of the 00's.
godelmachine 9y ago
What would be nice book / video / web link that will give a decent intro to a novice like me?
- qubex 9y ago
  http://www.clerro.com/guide/580/quantum-computing-explained http://www.clerro.com/guide/580/quantum-computing-explained
api 9y ago
I've thought for a long time that this explains why the NSA is recording so much encrypted data. When QCs are available they will be able to decrypt all the things. Imagine what they'll learn.
- qubex 9y ago
  That’s a bit conspiracy-theorist-ish but unfortunately in the present climate and given that has transpired from the Snowden leaks not at all implausible. Either they have made a breakthrough in number theory that allows factorisation over finite fields, or they have a quantum computer already, or they are banking on having one soon. In any case, storage is so cheap that it makes sense to just record the traffic (which is useful for sigint anyway) and refer back to it “if and when”. Of course, much of what we consider “public-key encrypted” traffic is actually encrypted with a symmetric cipher whose encryption is impervious to Shor’s Algorithm… it is the key-exchange process that really uses the textbook public-key encryption algorithms. So much of the traffic is technically impervious to whatever advances they have made, but of course once you have captured the key-exchange “handshake” that sets up the session and exchanges the symmetric cipher keys, you’re all set to retrieve the plaintext from the intercept. There are public-key algorithms (particularly those based on lattices) that we currently hold to be secure against attack by quantum computers. I am surprised these are not seeing more adoption amongst the “enlightened paranoid cypherpunk elite”. Here is a primer on such “post-quantum cryptography” approaches, courtesy of the good folks at Wikipedia: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
  - api 9y ago
    In the process they'd get key exchanges too and it's easy to correlate traffic. I thought it was a really straightforward obvious idea. I'd do it if I were them and had such deep pockets. QC is clearly coming. Lots of news lately.
    - qubex 9y ago
      I was agreeing with you, of course if they have intercepted all traffic they have both public-key encryption key exchange and the resulting symmetrically encrypted traffic and that they could correlate it... I’m sorry if I was a bit longwinded and pedantic in my reply, I didn’t realise I was talking to virtual Hacker News nobility (with ten times the karma I do!).

leecarraher 9y ago

citation? A theoretical understanding of bits in quantum superposition would support the notion of traversing all combinatorially related possibilities however that is not the case for any realizable quantum computer. Realizable machines are based on specific quantum logic gates. otherwise you would have to design at the electron level, a new processor for every problem.

marcosdumay 9y ago
Here's the citation: https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm You do need to update yourself. There are standard gates, complete computation theories, and algorithms for lots of interesting problems. Those aren't even new.
- leecarraher 9y ago
  aes isn't broken by factorization of composites of prime. if the op had said rsa, sure, but they said aes (it was changed you can tell because there was never such a thing as 128bit rsa), but thanks for telling me about that "new" shor's algorithm devised in 1994.
  - marcosdumay 9y ago
    Yes, comment edition sometimes leads to misunderstanding. But there was 128bit RSA, it was in use up to the middle of the 00's.

godelmachine 9y ago

What would be nice book / video / web link that will give a decent intro to a novice like me?

qubex 9y ago
http://www.clerro.com/guide/580/quantum-computing-explained http://www.clerro.com/guide/580/quantum-computing-explained

api 9y ago

I've thought for a long time that this explains why the NSA is recording so much encrypted data. When QCs are available they will be able to decrypt all the things. Imagine what they'll learn.

qubex 9y ago
That’s a bit conspiracy-theorist-ish but unfortunately in the present climate and given that has transpired from the Snowden leaks not at all implausible. Either they have made a breakthrough in number theory that allows factorisation over finite fields, or they have a quantum computer already, or they are banking on having one soon. In any case, storage is so cheap that it makes sense to just record the traffic (which is useful for sigint anyway) and refer back to it “if and when”. Of course, much of what we consider “public-key encrypted” traffic is actually encrypted with a symmetric cipher whose encryption is impervious to Shor’s Algorithm… it is the key-exchange process that really uses the textbook public-key encryption algorithms. So much of the traffic is technically impervious to whatever advances they have made, but of course once you have captured the key-exchange “handshake” that sets up the session and exchanges the symmetric cipher keys, you’re all set to retrieve the plaintext from the intercept. There are public-key algorithms (particularly those based on lattices) that we currently hold to be secure against attack by quantum computers. I am surprised these are not seeing more adoption amongst the “enlightened paranoid cypherpunk elite”. Here is a primer on such “post-quantum cryptography” approaches, courtesy of the good folks at Wikipedia: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- api 9y ago
  In the process they'd get key exchanges too and it's easy to correlate traffic. I thought it was a really straightforward obvious idea. I'd do it if I were them and had such deep pockets. QC is clearly coming. Lots of news lately.
  - qubex 9y ago
    I was agreeing with you, of course if they have intercepted all traffic they have both public-key encryption key exchange and the resulting symmetrically encrypted traffic and that they could correlate it... I’m sorry if I was a bit longwinded and pedantic in my reply, I didn’t realise I was talking to virtual Hacker News nobility (with ten times the karma I do!).