<story><title>NSA seeks to build quantum computer that could crack most types of encryption</title><url>http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_print.html</url></story><parent_chain><item><author>tptacek</author><text>1. $80MM isn&amp;#x27;t even in the ballpark of what it would cost to build a quantum-theoretic machine that could break IFP (RSA) or DLP (DH, DSA) crypto.&lt;p&gt;2. $80MM is way, way past the threshold believed to be required to break the most widely deployed public-key crypto, RSA-1024. Put differently: there are venture capitalists who could successfully fund an effort to break the most widely-deployed public key crypto.&lt;p&gt;3. If it is feasible to build a quantum-theoretic machine to break RSA, it is vitally important that the NSA attempt to do so; such work is at the very core of their mission.&lt;p&gt;I have no insight into what&amp;#x27;s actually happening behind this disclosure, but the price tag on it suggests to me that it&amp;#x27;s just a research project.&lt;p&gt;Since NSA is the kind of organization that historically spends $80MM on paper clips, the number suggests to me that quantum-theoretic attacks on IFP and DLP crypto aren&amp;#x27;t currently a serious thing. But that&amp;#x27;s a wild guess.</text></item></parent_chain><comment><author>scythe</author><text>Hi! I do research in quantum error correction and topological quantum memory.&lt;p&gt;There is absolutely no way that the NSA or anyone else is going to build a quantum computer in the next twenty years.&lt;p&gt;The reason is that the overhead of error correction is, while feasible to meet long term, too large. The number of physical qubits that must exist in a system that can work with K logical qubits is O(K log(E)^c), where E is the logical error rate, which must be inversely proportional to the total runtime of the maximal feasible algorithm, and c is a constant that depends on the memory architecture (quantum error-correcting code, in general a subsystem of a degenerate ground state of an effective Hamiltonian on the qubits).&lt;p&gt;Shor&amp;#x27;s algorithm requires ~3N logical qubits and O(N^3) steps, where N is the length of the number to be factored. The minimum feasible size for a computer that could perform this calculation on a typical 2048-bit semiprime is several hundred thousand physical qubits.&lt;p&gt;By contrast, the largest quantum computer thus far constructed has less than ten qubits. Even if we double every 18 months (not at all likely), that&amp;#x27;s a good 22 years away with the most optimistic outlook for quantum stability.&lt;p&gt;Far more than 80 million dollars has already been invested into quantum computing research. I think it&amp;#x27;s money well spent, but it&amp;#x27;s not going to change the nature of the problem.</text></comment>
<story><title>NSA seeks to build quantum computer that could crack most types of encryption</title><url>http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_print.html</url></story><parent_chain><item><author>tptacek</author><text>1. $80MM isn&amp;#x27;t even in the ballpark of what it would cost to build a quantum-theoretic machine that could break IFP (RSA) or DLP (DH, DSA) crypto.&lt;p&gt;2. $80MM is way, way past the threshold believed to be required to break the most widely deployed public-key crypto, RSA-1024. Put differently: there are venture capitalists who could successfully fund an effort to break the most widely-deployed public key crypto.&lt;p&gt;3. If it is feasible to build a quantum-theoretic machine to break RSA, it is vitally important that the NSA attempt to do so; such work is at the very core of their mission.&lt;p&gt;I have no insight into what&amp;#x27;s actually happening behind this disclosure, but the price tag on it suggests to me that it&amp;#x27;s just a research project.&lt;p&gt;Since NSA is the kind of organization that historically spends $80MM on paper clips, the number suggests to me that quantum-theoretic attacks on IFP and DLP crypto aren&amp;#x27;t currently a serious thing. But that&amp;#x27;s a wild guess.</text></item></parent_chain><comment><author>philipn</author><text>If you&amp;#x27;re curious (as I was) about the estimated cost of breaking RSA-1024 check out this paper:&lt;p&gt;&lt;a href=&quot;http://tau.ac.il/~tromer/papers/cbtwirl.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;tau.ac.il&amp;#x2F;~tromer&amp;#x2F;papers&amp;#x2F;cbtwirl.pdf&lt;/a&gt;&lt;p&gt;tl;dr - estimate is ~$10M</text></comment>