Re: [IPsec] Modp-12288 and Modp-16384

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

> -----Original Message-----
> From: Tero Kivinen <[e-mail]>
> Sent: Wednesday, July 18, 2018 11:35 AM
> To: Scott Fluhrer (sfluhrer) <[e-mail]>
> Cc: [e-mail]; [e-mail]
> Subject: Re: [IPsec] Modp-12288 and Modp-16384
> 
> Scott Fluhrer \(sfluhrer\) writes:
> > > That we do not know until we know what those quantum computers can
> > > really do... I have not seen anybody saying how many qbits you need
> > > to break MODP-2048.
> >
> > It's about twice as many as you need to factor a 2048 bit composite;
> > so about 4k (logical) qubits.
> >
> > > Most of the things I have seen talks about factoring RSA, and even
> > > then they do not provide numbers.
> >
> > How about https://arxiv.org/abs/quant-ph/0205095 - to factor an n bit
> > number, you can do it with circa 2n qubits.
> >
> > If you want other references, we have
> > https://arxiv.org/abs/1611.07995 and
> > https://arxiv.org/pdf/1706.07884.pdf both with similar results. We
> > also have https://arxiv.org/abs/quant-ph/0601097 which suggests a way
> > with 1.5n qubits; however that paper makes some assumptions about
> > errors that might not be true.
> 
> It would be good idea to get draft-hoffman-c2pq updated with these
> references.
> 
> > Of course, these papers are focusing in on minimizing the number of
> > qubits; it's quite possible a trade-off that increases the number of
> > qubits, while decreasing the number of (say) T gates, would be
> > advantageous; we don't know enough about the relative costs to know.
> 
> Yep, and how many bits we need more because of error correcting stuff etc.

It multiplies it by a factor of N, whose value depends on the quantum error correction algorithm.

In the quantum computing space, they mostly talk about "logical queue bits", that is, they assume that the error correction problem is already solved (unless, of course, they are specifically working on quantum error correction algorithms).

> 
> > > draft-hoffman-c2pq also says that we might have machines breaking
> > > AES-128 before than we have machines that can break Diffie-Hellman,
> > > i.e., it is most likely easier to make machine running Grover's
> > > algorithm than machine running Shor's algorithm.
> >
> > That work totally ignores the amount of time we're talking about with
> > O(2**64) computations (and parallelization is less helpful than usual;
> > Grover's becomes less efficient the more we parallelize it).
> 
> 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.

> 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.