Answering to give some info about what we know about the likely capabilities of Quantum Computers.
> -----Original Message----- > From: Tero Kivinen <[email protected]> > Sent: Tuesday, July 17, 2018 5:17 PM > To: Scott Fluhrer (sfluhrer) <[email protected]> > Cc: [email protected] > Subject: RE: [IPsec] Modp-12288 and Modp-16384 > > Scott Fluhrer (sfluhrer) writes: > > If the requirement for AES-256 is to handle the scenario "someone gets > > a quantum computer", then in that scenario, there is no realistic DH > > group size that is secure. > > 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. 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. > > 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). 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... _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec
