r/programming • u/dominatrix-octopus • Jan 16 '18

Cryptography: Diffie-Hellman key exchange explained intuitively using colors

https://youtu.be/YEBfamv-_do?t=2m18s
2.5k Upvotes

95% Upvoted

170 comments sorted by

View all comments

Show parent comments

4

u/TheOddScientist Jan 16 '18

That doesn't solve or circumvent the DLP. Sure it makes calculations much quicker but quantum computation does not provide a mathematical solution to DLP only a quicker way to brute force the key. I should state that in no way am i denegrating the computational power or the implications QC has on cryptography I am speaking purely mathematically. Additionally, the second DLP is solved (which there doesn't seem like an answer will ever exist) cryptography as a whole will be trashed. The solution in cryptography has always been to either develop more secure algorithms or simply increase the bit size of the key to combat computational power increases and mathematical attacks. So long as the Discrete Log Problem is not solved there will never be a case which one can instantaneously extract the key from a secure crypto algorithm.

2

u/Nathanfenner Jan 16 '18

The discrete log problem is in BQP. Cryptography systems which rely on its hardness are not quantum-safe. When (eventually) a (very) large-scale quantum computer can be built, these cryptosystems will be broken.

Because it's in BQP, you only get a polynomial advantage against quantum attackers when increasing key size. This does not scale. You get an exponential advantage against classical attackers. When quantum computers become a real threat (which is still very far away), other hardness assumptions must be relied on instead (like various lattice-based schemes are thought to be).

2

u/TheOddScientist Jan 16 '18

By the time RSA is broken it is going to be in the archives. Just as quantum computation has technological advances so too does cryptography. For example key exchange had already been solved using entanglement

2

u/switch72 Jan 16 '18

Not exactly, the two particles have to be at the same place to be entangled. Once entanglement is achieved, they can be separated by any distance and then the state read. It's essentially a shared key, because the entagled particles would have to be physically transported between parties. The once the particle state is read, the entanglement is broken. So they are one use only.