Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

arxiv.org

Post reply on HN
Print view View original

41–50 of 146 posts

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#41

Post by KMag »

hannob wrote: post #32
isolli wrote: post #31

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

Yes and kinda yes. There's a standardization process going on for post quantum cryptography at the US NIST. Results expected before the almighty RSA-breaking quantum computer arrives. There's still a concern about store-and-encrypt-later (i.e. someone can store encrypted communication today and decrypt it once a QC is available), and how relevant that is depends on some unknowns (how many years to you expect your com…

Note, for instance, that Google ran an experiment where Chrome connecting to Google hosts used both conventional elliptic curve Diffie-Hellman over Curve25519 and post-quantum "New Hope" RLWE. A hash of the results of the two key agreements was used for ChaCha20 encryption of the keystream. A store-and-decrypt attack in this case should be required to break both conventional Curve25519 and experimental New Hope.

Note that the best known quantum attacks on ChaCha20 cut the key size in half, so 256-bit ChaCha20 should still be fine, as long as your key agreement protocol is quantum-resistant.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#42

Post by BelenusMordred »

isolli wrote: post #31

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

> Are we ready for that kind of upheaval?

Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though.

Asymmetric public key crypto and signatures being broken is the only real threat, there's no theoretical issues with symmetric crypto, hashing or MAC's.

A quantum break already has a multi-billion dollar bounty on it in the form of cryptocurrency wallets which would be hard to fight against in the form of wages or violent coercion. This is probably the best evidence on Earth that no one actually has this capability.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#43

Post by xucheng »

UncleMeat wrote: post #35
CodesInChaos wrote: post #30

Earlier quoted context omitted.

Rotating keys works for authentication, but not for confidentiality, since nothing stops an attacker from recording the ciphertext and decrypting past messages.

RSA is rarely actually used for doing the message encryption. Instead it is used for negotiating other keys. Perfect-forward-secrecy enables you to get message confidentiality even if your key is leaked after the message is sent.

Perfect-forward-secrecy relies on that you didn’t break the underlying cryptography primitives, which is not true with QC.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#44

Post by isolli »

BelenusMordred wrote: post #42
isolli wrote: post #31

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real…

Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#45

Post by oldgradstudent »

tbabej wrote: post #12

This paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).

So magic computer could be more effective with more magic memory than with more magic processing power, right?

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#46

Post by CodesInChaos »

graderjs wrote: post #28
CodesInChaos wrote: post #10

Earlier quoted context omitted.

Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged…

Jennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factoriz…

> Till we've crypto that's quantum, and daunt 'em.

Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#48

Post by lallysingh »

isolli wrote: post #44
BelenusMordred wrote: post #42

Earlier quoted context omitted.

> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real…

Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)

I think they're saying that we know nobody's using quantum computing to break crypto yet, because nobody's been draining bitcoin wallets.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#49

Post by bdamm »

oldgradstudent wrote: post #45
tbabej wrote: post #12

This paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).

So magic computer could be more effective with more magic memory than with more magic processing power, right?

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#50

Post by dfox »

marcosdumay wrote: post #27
dzdt wrote: post #9

Quantum computers of this scale are probably 5-15 years out. Basically this is a warning that if you have secrets that should still be kept secret over that timeframe, you should not be using RSA today.

> you should not be using RSA today Also, always remember that ECC is believed to be just as weak against quantum computers as RCA. So you'll probably want some fusion of pre and post-quantum algorithms. Or, anyway, get your perfect forward secrecy working and don't rely on asymmetric crypto for confidentiality. Yeah, PFS is very hard to get on some use cases, but it's really the best way to solve this problem.

PFS still involves asymmetric cryptography. And in fact in essentially every modern cryptography stack (ie. (EC)DLP-based) the "PFS primitive" (Diffie-Hellman, ie. scalar multiplication/exponentiation) is the one thing that everything else is derived from.

RSA is in fact somewhat notable for being the only widely used asymmetric cryptosystem where the underlying operation is block cipher-ish encryption primitive and not key agreement primitive.

Post reply on HN