Thanks Scott, it was extremely helpful. So, as far as I understand, it is not feasible for QC to break 2K or larger MODP groups in real time (say in few seconds), and this restriction seems hard to overcome (at least with our current understanding).
What about ECDH groups? Can you estimate how long would it take for QC to break Ed448 or 521-bit groups? Regards, Valery. > > > Any idea how many computations needs to be done for the shor's > > > algorithm, i.e., breaking 2048 bit Diffie-Hellman. I have just seen > > > text saying it is polynominal time, but I have not really seen any > > > guesses what the actual numbers are going to be. > > > > Very good question; the references I find all essentially say "cubic"; > > however > > they don't immediately talk about the constant factor. I suspect that this > > constant factor won't be that large; however that most certainly merits > > further investigation. > > Ok, I went through the literature, and while the short answer is "it's > complex", I do have some partial answers, > including what I believe is a defensible time estimate. > > I went through a number of academic papers, and came to the conclusion that > factoring 2kbit numbers on a > Quantum Computer with circa 4700 qubits available could reasonably be done in > time circa 8 billion times the > time taken by a single quantum gate (details on how I came to that conclusion > are listed below); increasing > the size of the numbers to 16k would increase the attack time by a factor of > perhaps 60 to 100. > > The other factor to address is the actual gate speed. One result is > http://www.nature.com/articles/nature25737 which gives a high fidelity (but > not error corrected) gate speed > of 1.6usec (using trapped ion qubits). Adding error correction logic to that > would add some overhead, if we > take the guess that it slows things down by a factor of 10 (which is the > approximate speed of the original Shor > error correction code), then that gives us an error corrected speed of 16usec > (or 60k gate operations per > second). > > Combining those two results would give an estimate of less than 2 days to > factor a 2k integer. As for > computing a discrete log for a 16k modulus (which is what the original > discussion was about), a somewhat > larger quantum computer (circa 250k qubit) that ran at the same speed would > take several months to > compute the discrete log. > > Of course, this time estimate is based on current published literature; this > is quite an active field, and future > work (especially in the realm of gate speed) could easily shrink these > numbers significantly. > > As a side note, if we look at the time it would take Grover's algorithm to > break AES-128, we have > https://www.researchgate.net/publication/287249961_Applying_Grover%27s_algorithm_to_AES_quantum_ > resource_estimates where they estimate a time of 1.16 2^81 = 2.8E24 circuit > depth, or about 300 trillion > times longer than our estimate for factoring a 2k integer. Now, this isn't > quite an apples-to-apples > comparison (for one, with Grover's, you could do some parallelism with > independent Quantum Computers, > however that costs more in terms of parallel units than you'd naively > expect); however the fact remains that > Grover's algorithm appears to be vastly more expensive than Shor's. The only > thing in favor of Grover's is that > attacking AES-128 would take circa 1000 qubits (same paper), while factoring > a 2k integer could be done with > about 4 times more. > > Also, while I did go through a number of papers, I cannot pretend that I did > anything close to a full literature > search. If someone spots a relevant result that I missed (or one that I > misinterpreted, or two results that I > combined incorrectly), please correct me. > > > Further details on my assumptions and the research: > > For one, I assumed that what we care about is "time taken", not "number of > operations performed"; that is, > our quantum hardware is able to perform some level of parallelism for > independent operations; the Quantum > Computing literature refers to this as the "Circuit Depth" (as opposed to > "Circuit Size", which is the number of > gate operations performed). > > In addition, the vast majority of the computation is done performing the > modular exponentiation; the other > quantum operation, the quantum Fourier transform, is comparatively > inexpensive (ref: > https://arxiv.org/abs/quant-ph/0006004 ); the other operations are the > classical pre- and post-computations, > which are also comparatively cheap. > > The most aggressive result I found for performing the modular exponentiation > is > https://arxiv.org/abs/1207.0511 ; this gives us a concrete result of 2000 n^2 > operations (where n is the size > of the modulus in bits). This result is quadratic (meaning that doubling the > modulus size only increases the > attack time by a factor of 4); however, it is a comparatively expensive > alternative (requiring about 9n qubits), > and for 2k modulii, it would appear we can actually do better. It does show > that going to, say, a 16k modulus > might not give us as much security as we would have hoped. > > In the other extreme (how few resources do we need), there are a number of > papers examining that, in > particular, how we can solve the problem while minimizing the number of > qubits used. The results I cited > earlier were all from this stream of research. These results use 2n+epsilon > qubits, where epsilon may be as > small as 1. Unfortunately, they use algorithms such as ripple addition, > which is just as slow in the quantum > realm as it is in the classical. This algorithms result in a Shor's > implementation that takes time cn^3 for some > c; if we hit a hard bound on the number of qubits we can afford, that appears > to be the best we can do. > Unfortunately, none of the papers I've seen actually give a concrete value > for 'c'; on the other hand, we can do > better anyways. > > As an intermediate result, I did find > https://pdfs.semanticscholar.org/a1dc/59b51794cf9737a7985da38a7230db89740a.pdf > , which shows how > to do moderately fast addition (they claim 30 log n circuit depth) using > 3n/log n additional qubits (these are > referred to as "ancillary" in the literature). My opinion is that if you > need to factor a 2048 bit number, then > having 4700 qubits isn't that much more difficult than having 4100, and the > additional 600 qubits allows you > to speed up your computation by over an order of magnitude, which is likely > to make it worth it. If we take > this adder, and use it to replace the serial adder within > https://arxiv.org/abs/1611.07995, this would give you > an implementation of Shor's algorithm with a depth of approximately 180 n^2 > log n). If this estimate is right, > for a 2048 bit modulus, this would give us a depth of about 8 billion, which > is approximately the same as the > more aggressive implementation, but using far fewer qubits. > > In addition, I referred to a 'gate time'; actually, there are a number of > different types of quantum gates, > including some that have no classical analogue, and it is certainly > reasonable to expect them to take different > amounts of time. On the other hand, according to > https://arxiv.org/abs/1202.5872, the speed difference is > not drastic, most of the papers ignore this difference (the AES paper is the > only one I could find that doesn't), > and so I ignored this difference as well. > > Note on the discrete log problem: I previously stated that you would need > approximately double the number > of qubits required to factor a modulus of the same size, and the time would > approximately remain the same. > Digging further into this, it appears that the time might increase somewhat > (but less than a factor of 2); that's > because for factoring, you select a value 'a' and compute a^b (for entangled > values of b); it turns out that > using a=2 will yield a factorization (various strategies to select p and q in > a manner to frustrate Shor with a=2 > turn out not to work), and can (depending on the algorithm) make it more > efficient. Against the discrete log, > you compute both g^b and h^b, where h is the value you're taking the discrete > log of; this is a large value, and > so the optimization you could take advantage of during factorization isn't > available. On the other hand, this > doesn't increase the amount of time drastically. > > Also, again, all the qubit numbers I quoted were "logical qubits", that is, > qubits that have error correction logic > applied. Each "logical qubit" is made up of a number of "physical qubits"; > the exact number depends on the > quantum error correction algorithm used. > > > > > > And I understand that there is also quite big classical computation > > > pre- and post-processing steps too. > > > > Not really; there is computation needed there, but it is quite straight- > > forward. > > > > Shor's algorithm gives you a value k where a^x = a^(x+k) mod n; once you > > have that value k, factoring n is a well understood (and fairly easy) > > problem, > > solvable by, say, Miller's algorithm. > > > > _______________________________________________ > IPsec mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/ipsec _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec
