> -----Original Message-----
> From: Valery Smyslov <[email protected]>
> Sent: Monday, July 30, 2018 4:05 AM
> To: Scott Fluhrer (sfluhrer) <[email protected]>; 'Tero Kivinen'
> <[email protected]>
> Cc: [email protected]; [email protected]
> Subject: RE: [IPsec] Modp-12288 and Modp-16384
>
> 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).
Note that this estimates were based on currently published results; it is
extremely likely that these will be improved on, and it would be difficult to
guess by how much.
It would appear that the speed of a Quantum Gate would need to increase by
perhaps a factor of 1000 (along with some algorithm improvements) in order to
make breaking MODP in real time feasible; I would personally be uncomfortable
in making the implausibility of this to be a security assumption.
>
> What about ECDH groups? Can you estimate how long would it take for QC to
> break Ed448 or 521-bit groups?
Well, I didn't see any papers talking about a Quantum attack of ECDH. However,
based on what I've seen:
- The DLOG approach of performing two parallel modular exponentiations would
certainly appear to be applicable to ECC; hence the time would essentially be
bounded by twice the time taken to perform a point multiplication (note: we
assume that the two point multiplies are done in parallel; the twice mentioned
is the amount of data that Shor's algorithm needs to do its QFFT).
- From the previous results, we should be able to perform an n-bit modular
multiply in 90n log n gate delays time (log is base 2).
- Constant time ECC algorithms would appear to translate directly into the
Quantum realm; these take circa 10 modular multiplies (and some modular
adds/subtracts, but they're cheap) per bit of the multiplier; however if we
allow parallel multiplies (which uses a few more qubits), we might be able to
manage with as few as 3 modular multiplies (or might not; in Quantum Computing,
all operations need to be invertible, and the parallel multiplies might make
this difficult; if we can't get to this level of parallelism, this estimate
might be off by a factor of 2). We also have to do a modular inversion at the
end (as the QFFT algorithm at the end will need equivalent points to have the
same bit pattern).
- Adding everything together (and assuming we can go with the full parallel
multiply option), we get around 600 n^2 log n gate delays (where I'm using n
to mean both the characteristic of the field and the curve group size; they're
close enough that the difference doesn't matter for this crude estimate).
With n=448, we get circa 1 billion, a fraction of the time we estimated to
break RSA-2048, with our 60,000 gate operations per second, that's about 5
hours. If we count Qubits, it would appear that ECC also uses considerably
fewer; however coming up with an exact number is nontrivial (the parallel
multiples may share sources, and so some additional ancillary qubits may be
needed)
So, with this rather crude (and off-the-cuff) analysis, ECC looks to be
noticeably weaker against a Quantum Computer. Of course, this is a such a
crude estimate, it's not clear if it ought to be used to make any real security
decisions...
>
> 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%27
> s
> > _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/59b51794cf9737a7985da38a7230db89
> > 740a.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
