> From: Scott Fluhrer (sfluhrer) > > From: Tero Kivinen <[email protected]> > > > > 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
