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

[Tero Kivinen <[e-mail]>]

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. 

> > 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. And I understand that
there is also quite big classical computation pre- and post-processing
steps too.

> Also, the interesting algorithms in Quantum Chemical modelling are
> significantly different from Grover's.  It's possible that there are
> some proposed protein folding problems that would use Grover's... 
-- 
[e-mail]