Hacker News Reader

Comment by jedberg | Hacker News Reader

We're living in an interesting time. The first group to get a working qbit based computer will be able to break all current encryption. We will very rapidly have to switch to quantum encryption to protect ourselves.

You can be damn sure that the NSA and the other three letter agencies are working hard on this problem, and definitely would not share if they get there first (if they haven't already).

View on HN

You don't need quantum cryptography to defend against attacks that employ quantum computers.

There was an interesting talk on classical encryption algorithms that resist quantum attacks by djb and Tanja Lange at 32c3 last year, see [1,2,3].

TL;DR:

- Shor's algorithm kills factorization-based algorithms like RSA, DSA and including elliptic-curves-based DSA,

- Grover's algorithm allows faster (O(sqrt(N) instead of O(n)) brute-force searches, which means for the same level of security, one needs to double AES key size,

- there exist classical encryption algorithms that have so far resisted quantum-based attacks, e.g. hash-based signatures, Goppa code-based asymmetric crypto,

[1] https://www.youtube.com/watch?v=6XeBvdm8vao

[2] https://media.ccc.de/v/32c3-7210-pqchacks#video (in German)

[3] https://www.reddit.com/r/privacy/comments/3yppbz/post_quantu...

EDIT: formatting

There's been some good work in Merkle Signatures in recent times. I posted a bunch on Schneier's blog here:

https://www.schneier.com/blog/archives/2015/03/friday_squid_...

My understanding is that it is not enough to just be a "qbit based computer" to be able to solve QBP (i.e. perform shors algorithm to break RSA).

These computers are quantum adiabatic computers which are indeed quantum in that they use qbits, but it is not clear that they can perform some operations required for QBP problems. See scott aaronson's blog for more info [1].

1. http://www.scottaaronson.com/blog/?p=1400

In Scott Aaronson's book Quantum Computing Since Democritus, he off-handedly mentions the need for quantum-hard crypto and that perhaps something based on Wolfram's cellular automata would do the trick. Wolfram says he used one of his own cellular automata rules as the PRNG in Mathematica. Which makes me wonder, why don't we already use something like this in modern crypto? And, how exactly would we implement this if we wanted to do so?

I'm not nearly well versed enough to speak intelligently on the subject, but my understanding is that only quantum computers can do a "perfect" key exchange, because the detection of interference by a third party can only be detected by a quantum computer.

Kind of, quantum key exchange is based on the uncertainty principle. By encoding the key exchange in quantum properties of particles, any mitm observer will change those properties, thus breaking the exchange. You don't need a quantum computer to do QKE, just the right kind of detector. There's already a bunch of people that do this without quantum computers.

> The first group to get a working qbit based computer will be able to break all current encryption.

All you have to do is increase the key-size faster than quantum can break it. Also there are many new algorithms being studied that quantum doesn't work on.

https://en.wikipedia.org/wiki/Post-quantum_cryptography

Reply on news.ycombinator.com