Quantum computing is so powerful it takes two years to understand what happened In 2012 a group of Chinese quantum physicists pulled off an acclaimed success in quantum-based factoring, running an adiabatic quantum algorithm for the number 143, at the time believed to be the largest number ever factored in a quantum computation. It now seems that paper, here, could have overlooked something: in a new …
So, if I understand it correctly (probably not), the method only works to factorise numbers that have two odd factors that differ by a power of 2 (e.g. 56153 = 233 x 241), and so could be easily defeated (for cryptographic purposes) by minor tweaks to the choice of the two large prime numbers used to compute the private key.
Sort of - the reason for that is the fact they used a 4 bit device. If they'd used a (say) 6 bit device then it would have done the same for a different power series.
The risk is that if they used a series of these machines and factorised lots of the series, then many keys would fall, because they would be part of these series. And currently, they are randomly found. If you start saying "That power series isn't allowed" you start reducing the keyspace quite a lot, and you increase the computational power required to make a key.
Part of the "weakening" of the encryption by the TLAs was attacking the randomisation of the salts, meaning that there was a higher likelihood of the factors being in a given series. This means that instead of having to try and work through n log n worth of numbers, they could be sure it was in a subset of that. The smaller the subset, the faster and easier it is to break it by a sort of educated guessing, rather than having to try and brute force all the possible primes.
(e.g. you introduce a subtle* "bug" so that one of the massive primes used ends in 3 or 7. That cuts your workload down massively, as 1, 5, 9 can be ignored, and no-one's ever going to notice unless they *really look*. That cuts your time to break the key from (say) 10 years to 4 years before you've even started. And in fact it is worse than that, because that's for one of the primes. If you did the same to the other, it drops from at best 5^5 = 3125 to 2^2 = 4. Which is quite a big drop! That 10 years becomes 28 days.)
*You can be a lot more subtle than that. This is just to give an example.
factorise numbers that have two odd factors that differ by a power of 2 (e.g. 56153 = 233 x 241)
233 and 241 differ by two powers of 2; that is, they have two bits that are different. 11101001 and 11110001, respectively.
The write-up in that blog is abysmal - the author writes "factors differ by two", then "differ by only two", then "differ by two bits"; then it's back to "differ by two" again. Those are rather different conditions.
The preprint on arxiv.org (PDF) is actually much clearer than the blog post:
In fact, it turns out that the product of any two numbers differing at only 2 bits will lead to the [same three] equations
That's it. If there are two factors that differ by exactly two bit positions (i.e., binary Hamming distance of 2), then these equations apply and you have the same Hamiltonian.
As someone else pointed out, the magic number 2 is due to the number of qubits available. If you have 8 qubits, you can solve the Hamiltonian for products with factors that have binary-Hamming distance 3. If H(p,q) is the binary Hamming distance for two factors of the product, you need 2H(p,q) qubits to perform this operation and solve for p, q.
(Note to Chris: The factors we're interested in are always odd, since we want prime factors, and we can eliminate 2 straight off.)
Am I missing something here? I read that preprint as well as I could, and If the only requirement for the numbers is a hamming distance of 2, it is trivial to come up with MUCH bigger numbers than 56153, for example:
7907 is 1111011100011
7919 is 1111011101111
7907*7919=62615533
Does this mean Xu and co. also accidentally factored 62615533?
"the kind of quantum-based factorisation that would eventually obsolete current cryptography"
From the little in the public domain, it seems fairly evident that Global Terror (tm) and their predecessors have used idiot codes since time immemorial. So the end of cryptography is more a problem for governments than either real world mortals being spied on by their own governments (because back-dooring undoubtedly defeats most of our efforts), and because no amount of computing power will crack an idiot code.
Having had my privacy serially undermined by Western governments, I look forward to the day when they won't be able to keep anything like as much hidden
Think authentication rather than privacy
dont think this is such a big issue for website certificates either as under current CA arrangements its really very easy to get your own root CA if you have some cash to splash in which case you can issue new certs for any website you want to impersonate.
Plus for serious players (APT types) they probably can compromise the client devices of people they are interested in and then HTTPS is utterly irrelevant.
What this is more significant for is if you are using PKI based signing by a fixed key for any kind of validation - that is a big deal. Thats software components (think MS root keys), financial transactions, etc... there is a lot of "infrastructure" that this would completely wreck.
"the kind of quantum-based factorisation that would eventually obsolete current cryptography"
There's a slight error in that quote. It should be "the kind of quantum-based factorisation that might eventually be a problem for the asymmetric cryptographic algorithms commonly in use today, forcing us to gradually switch to any of several so-called 'post-quantum' asymmetric algorithms at a probably negligible increase in processing cost, but has no consequences whatsoever for symmetric encryption".
There, Richard - FTFY.
Nothing special about adiabatic QC here, as far as I can see. If my understanding is correct (and it may not be), the technique should work with other QC implementations.
Shor's is a general-purpose integer-factoring algorithm. This technique works only when you have a pair of factors that have a precise Hamming distance, and you have to do the algebra to enumerate and reduce the system of simultaneous equations, and then compute the Hamiltonian. Then you fire up the QC and let it find the values of the unknown bits. So it's not a magic box for factoring numbers.
To be honest, I don't immediately see how you'd extend this to make factoring hard products (like the kind used in RSA) practical.
I also don't know if it can be extended to attack discrete-log and EC, because I haven't studied in detail how Shor's is extended to do that, and I can't be bothered to right now.
You could tell which of our fighting forces he'd been making cloth for that day by the colour of his skin when he got back. Blue-grey for the RAF, yellow for the desert forces, navy for the Navy, obviously.
He got drunk after work one Friday and fell asleep in a garden hedge on his way home. He'd been dyeing for the army that day; DPM or camo as they used to call it. We didn't find him until Sunday morning.
Not only can quantum computing solve all solutions at once, but now we know that it can do so for more than one value at once.
Only one problem left : extracting the solution that corresponds to the value you were expecting.
Oh well, they'll have that sorted out in the next fifty years, no problem !
Indeed, though that's not really the point though, is it.
Though I'm lost as to the part about being able to verify the work with a classical computer. The whole reason factorisation problems are useful for cryptography is that the factorisation is hard, but the opposite, multiplication, is easy. So it should be trivial to verify the work by multiplying the factors together with a classical computer (or, in the case of 11 and 13, in your head).
They can simulate the factorisation problem with a classical computer running a virtual quantum computer. However the classical computer can only model so many qbits before it becomes infeasibly slow (kinda like trying to model an ipad using an 08086). This means that they can verify the results that a machine is providing by running it through their simulations to see if it comes up with the same answer.
“These have precisely the same form as the equations in the factorisation of 143, except with different variables. Therefore the Hamiltonian is also the same, except the qubits … represent different positions in the corresponding binary strings … Other numbers that we have discovered reduce to the same equations include 3,599, 11,663 and 56,153”.
That's easy for you to say!
I guess the 4-qubit quantum computer is a better intuitive mathematician then those guys... plus maybe it factored more primes but they did not realize it yet (as all this techno mumbo jumbo is far off the coffestain fortune telling scale still)
On another note 42-qubit quantum computer may be needed to compute the answer which we know is 42, then we can work on the x-qubit computer to design the computer which will in turn hopefully provide us with THE QUESTION once and for all!
The impression one gets is that wonks are poking the quantum computers and going "huh? what?".
Case in point: it's still neither clear if the D-Wave computer is a quantum computer or just behaves like one, nor if it is faster (and if so how much) than a conventional computer.
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
