5 ms·
This article is pretty inaccurate in a number of ways. The whole D-Wave thing is mostly irrelevant for cryptography, which the article doesn't mention. Even if
by hannob 11y ago
This article is pretty inaccurate in a number of ways.
The whole D-Wave thing is mostly irrelevant for cryptography, which the article doesn't mention. Even if the D-Wave devices turn out to be useful for some special algorithms, they can't run Shor's algorithm, which is what endangers crypto.
Also calling 1024 bit a "really long key" is a bit strange. They are already endangered by classical computers, no need for quantum computing here.
That said: The call for postquantum crypto is right.
- murbard2 11y agoThey might be able to run Grover's algorithm, which would effectively require the doubling of key lengths to preserve security in symmetric ciphers.
- khed 11y agoI am not so sure. I don't understand work well but there have been a couple papers saying they can get a quantum speed up on factorizing using adiabatic quantum computers [1]. Further, Geordie Rise himself said that they have an algorithm that can run on a dwave system that can beat shors algorithm [2]. A more skeptical take is here [3]. [1]. http://www.diva-portal.org/smash/get/diva2:680572/FULLTEXT01.pdf http://www.diva-portal.org/smash/get/diva2:680572/FULLTEXT01... [2]. https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/#comment-22008 https://dwave.wordpress.com/2011/05/11/learning-to-program-t... [3]. https://www.newscientist.com/article/dn21699-controversial-quantum-computer-beats-factoring-record/ https://www.newscientist.com/article/dn21699-controversial-q...
- petra 11y agoIt's not clear whether Gordie Rise said the truth or not: https://www.reddit.com/r/crypto/comments/3ig0xf/does_anyone_know_if_dwaves_quantum_computers_are/ https://www.reddit.com/r/crypto/comments/3ig0xf/does_anyone_...
- Estragon 11y agoIf you read further in the thread, you'll see that Rose created a false impression with [2].
- khed 11y agoI don't see where in that thread it indicates Rose gave a false impression.
- gradi3nt 11y agoScot Aaronson does understand this work very well, and he mentions several times (with citations) that there is no widely accepted proof or disproof that a quantum speedup will ever exist for quantum annealers. http://www.scottaaronson.com/blog/?p=2555 http://www.scottaaronson.com/blog/?p=2555
- imaginenore 11y ago1024 bit keys are endangered? Only in some broken encryption schemes. You can't even break 256 bits, as the number of possibilities exceeds the number of atoms in the universe.
- brillenfux 11y agoThey'll all break eventually ;-) — We know that, that's why encryption progresses. The question is only: How fast do we have to progress in the future?
- witty_username 11y agoRSA 1024 bit keys are endangered. AES nope.
- baldfat 11y ago2 ^ 255 = 57896044618658097711785492504343953926634992332820282019728792003956564819968 The issue IS not 256-bit it is the password you used to encrypt it with. Using letters, caps, symbols and numbers with 12 that would be an incredibly large budget to get your password.
- gherkin0 11y agoYou're comparing keys from two different cryptosystems, which is a mistake. A RSA key ("1024 bit keys") needs to be longer than a AES key ("256 bits") to provide a given amount of security, since more conditions are placed on an RSA key in order to get its favorable properties. In 1999 you could break a 512-bit RSA key with a supercomputer, in 2015 you can do it with 4 hours and $75 on EC2: http://arstechnica.com/security/2015/10/breaking-512-bit-rsa-with-amazon-ec2-is-a-cinch-so-why-all-the-weak-keys/ http://arstechnica.com/security/2015/10/breaking-512-bit-rsa... A 768-bit RSA keys has been factored in a large academic effort: https://eprint.iacr.org/2015/1000.pdf https://eprint.iacr.org/2015/1000.pdf When you pick a key length, you want it to be long enough to provide security for your communications as far into the future as practicable, and the classical efforts to break RSA are getting uncomfortably close to 1024-bits. Maybe in a few decades it would be practical for some adversaries to break even perfectly made 1024-bit keys. However, I'm not a cryptographer, so someone please correct me if I'm wrong.
- fonosip 11y agoThe definitive test for Quantum computer arrival is the claim of Satoshi's 1 million bitcoins. Those coins were mined and paid paid to the pubkey, not the pubkey-hash. Thus they are quantum computer vulnerable. So there is a $500 million price ready for the first operational Quantum computer. http://ba.net/util/bitcoin/design1.html#quantum http://ba.net/util/bitcoin/design1.html#quantum
- exelius 11y agoI don't know about that; the moment those coins are suspected to be compromised, you'd get a near-immediate run on BTC. So yes, there are a lot of Bitcoins available, but stealing them would undermine the entire system their value is based on, rendering them worthless.
- droffel 11y agoThey wouldn't be rendered worthless, but the security would take a hit for sure. Any coins mined (and not moved) before 2012 would be at risk, in addition to any address that has been reused since then (revealing the pubkey, instead of just the pubkey hash). Addresses created post-2012 that have not been spent from (spending reveals the pubkey) would still be 100% secure.
- andrewla 11y agoEh -- "secure-ish" at best. Spending those utxo's requires revealing the pubkey, at which point someone with a quantum computer can just break your pubkey and offer a new transaction with a higher fee while your transaction is still in the mempool.
- khed 11y agoOr an even bigger prize for keeping it secret. If you could break asymmetric encryption at will you could plunder much bigger prizes than Satoshi's coins.
- DickingAround 11y ago
- jtmarmon 11y agocan someone explain why it can't run Shor's? I thought Shor's was an algorithm designed to be run on QC, and D-Wave is a QC. What makes D-Wave different from the intended hardware?
- reikonomusha 11y agoD-Wave doesn't have typical quantum logic gates. They are a different kind of quantum computer called "adiabatic quantum computers". Instead it solves optimization problems by using a technique called "quantum annealing". In essence, it's a tool that can very quickly find maxima and minima of certain cost functions you can program in (albeit tediously).
- krastanov 11y agoThis is slightly inaccurate. Adiabatic quantum computing is not the term you want. Adiabatic quantum computing is equivalent to the more traditional quantum-gates based computing model (both of them are efficient at the same class of problems). D-Wave can solve one particular problem (that can also be solved by classical computers in similar time), the problem is related to annealing, and is not the problem of adiabatic quantum computing (which is much more general). The component they lack is that they can not preserve any non-trivial information between their qubits.
- gaze 11y agoTechnically it can be. Seth Lloyd has a paper on a way to run gate based algorithms on an adiabatic computer by adding a clock degree of freedom.
- selimthegrim 11y agoIs this on the arXiv?
- krastanov 11y agoHere is one version of the proof: http://arxiv.org/abs/quant-ph/0405098 http://arxiv.org/abs/quant-ph/0405098 This is the original I think: http://arxiv.org/abs/quant-ph/0403090 http://arxiv.org/abs/quant-ph/0403090