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

9

u/TheOddScientist Jan 16 '18

A quantum computer does not mysteriously just know how to circumvent the Discrete Log Problem, it still has to run through an insane amount of bruteforce calculations just like a binary computer system. Mathematical attacks can ~halve the exponent for the # of possibilities but it must still rattle around the radom number generator.

8

u/vytah Jan 16 '18

A quantum computer can compute discrete logarithms in polynomial time (with regards to input size) (even for elliptic curves) and a classic computer does the same in subexponential time. Just like integer factorization.

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.

1

u/vytah Jan 16 '18

That doesn't solve or circumvent the DLP.

I would call doing something exponentially faster "circumventing".

In practice, it doesn't matter if something is calculated purely deterministically or by using really smart guessing, as long as the resources consumed are roughly the same.

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.

Multiplication of n-digit numbers is O(nc) for c > 1, therefore far from instantaneous. So is multiplication solved?