close
  • Sc chevron_right

    Breaking RSA with a Quantum Computer

    news.movim.eu / Schneier · Tuesday, 3 January - 17:38 · 1 minute

A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it’s not obviously wrong.

We have long known from Shor’s algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what’s possible today. (IBM will announce a 1000-qbit quantum computer in a few months. Others are on their way as well.)

The Chinese group didn’t have that large a quantum computer to work with. They were able to factor 48-bit numbers using a 10-qbit quantum computer. And while there are always potential problems when scaling something like this up by a factor of 50, there are no obvious barriers.

Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics. And there’s the nagging question of why the Chinese government didn’t classify this research.

But…wow…maybe…and yikes! Or not.

“Factoring integers with sublinear resources on a superconducting quantum processor”

Abstract: Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglogN ), which is sublinear in the bit length of the integer N , making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.

SIKE is one of the new algorithms that NIST recently added to the post-quantum cryptography competition.

It was just broken , really badly.

We present an efficient key recovery attack on the Supersingular Isogeny Diffie­-Hellman protocol (SIDH), based on a “glue-and-split” theorem due to Kani. Our attack exploits the existence of a small non-scalar endomorphism on the starting curve, and it also relies on the auxiliary torsion point information that Alice and Bob share during the protocol. Our Magma implementation breaks the instantiation SIKEp434, which aims at security level 1 of the Post-Quantum Cryptography standardization process currently ran by NIST, in about one hour on a single core.

News article .

  • Sc chevron_right

    NIST Announces First Four Quantum-Resistant Cryptographic Algorithms

    news.movim.eu / Schneier · Wednesday, 6 July, 2022 - 16:49 · 1 minute

NIST’s post-quantum computing cryptography standard process is entering its final phases. It announced the first four algorithms:

For general encryption, used when we access secure websites, NIST has selected the CRYSTALS-Kyber algorithm. Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation.

For digital signatures, often used when we need to verify identities during a digital transaction or to sign a document remotely, NIST has selected the three algorithms CRYSTALS-Dilithium , FALCON and SPHINCS+ (read as “Sphincs plus”). Reviewers noted the high efficiency of the first two, and NIST recommends CRYSTALS-Dilithium as the primary algorithm, with FALCON for applications that need smaller signatures than Dilithium can provide. The third, SPHINCS+, is somewhat larger and slower than the other two, but it is valuable as a backup for one chief reason: It is based on a different math approach than all three of NIST’s other selections.

NIST has not chosen a public-key encryption standard. The remaining candidates are BIKE , Classic McEliece , HQC , and SIKE .

I have a lot to say on this process, and have written an essay for IEEE Security & Privacy about it. It will be published in a month or so.

  • Ar chevron_right

    Quantum computing’s also-rans and their fatal flaws

    news.movim.eu / ArsTechnica · Saturday, 30 November, 2019 - 15:00

Extreme closeup of computer chip.

Enlarge / IBM's 16-qubit quantum computer from 2017. (credit: IBM quantum experience )

Last month, Google claimed to have achieved quantum supremacy —the overblown name given to the step of proving quantum computers can deliver something that a classical computer can't. That claim is still a bit controversial , so it may yet turn out that we need a better demonstration.

Independently of the claim, it's notable that both Google and its critics at IBM have chosen the same type of hardware as the basis of their quantum computing efforts. So has a smaller competitor called Rigetti. All of which indicates that the quantum-computing landscape has sort of stabilized over the last decade. We are now in the position where we can pick some likely winners and some definite losers.

Why are you a loser?

But why did the winners win and the losers lose?

Read 22 remaining paragraphs | Comments

index?i=fd8gHgWjzXI:HgzTyADUgOk:V_sGLiPBpWUindex?i=fd8gHgWjzXI:HgzTyADUgOk:F7zBnMyn0Loindex?d=qj6IDK7rITsindex?d=yIl2AUoC8zA