Shor and the Quantum Signature

“QUANTUM COMPUTERS: THE END OF ALL SECRETS?” Uwe read aloud. “Experts warn: future quantum computers could crack the encryption used by banks, authorities and messaging apps.”

“There’s a question mark,” said Sabine, without looking up from her own paper. “When there’s a question mark in the headline, the answer is usually no.”

“And if it isn’t?”

“Then next week it’ll be in there without the question mark.”

Uncle Herbert was sitting at the breakfast table with them. For some time now he had been coming on Saturdays, supposedly for Gisela’s bread rolls, but really because, ever since the business with the old laptop in the cellar, he checked the Bitcoin price every morning and needed someone to tell the number to.

“Banks,” he said. “Messaging apps. And what about my internet money?”

“It doesn’t say,” said Uwe.

“Then it’ll say next week,” said Herbert darkly. “KevIn. Honestly now. Can one of those fridges steal my money?”

The blue light pulsed. “Not today, Herbert.”

“And tomorrow?”

“Not tomorrow either.”

“And the day after tomorrow?”

“That’s where it gets interesting.”

Herbert put his bread roll down. Normally he only did that for deaths and penalty shoot-outs.

A Man Called Shor

“Let’s start at the beginning,” said KevIn. “Do you remember the prime numbers? Mr Demir and the message to the aliens?”

“1679,” said Tobi at once. “23 times 73.”

“Exactly. Multiplying is easy. You can work out 23 times 73 on a beer mat. But if I only give you 1679 and ask which two prime numbers are hiding inside it, you have to try things out. With 1679 that’s still doable. With a number six hundred digits long, a normal computer would be trying for longer than the universe has existed.”

“And RSA is built on that,” said Tobi. “We did that.”

“RSA is built on that. The public key contains the product; the secret key depends on the two factors¹. As long as nobody can split the big number, it’s secure.”

“And now the fridge comes in,” said Uwe.

“Now Peter Shor comes in. An American mathematician. In 1994 he showed that a sufficiently large quantum computer could split large numbers much, much faster than any known method on normal computers². Back then there wasn’t even a quantum computer. So Shor wrote the recipe before anyone had a cooker.”

“Like Mum,” said Uwe. “She writes recipes for things we haven’t got in the house, too.”

“I write shopping lists,” said Sabine. “That’s the difference between planning and hoping.”

“How does he do it?” asked Tobi. “This Shor. Does he try all the numbers at the same time?”

“No,” said KevIn and Tobi at the same time, because Tobi regretted his own question in the very same second.

“Very good,” said KevIn. “Chapter 17 worked. A quantum computer doesn’t simply try everything. Shor found a detour. He turns the question ‘Which factors?’ into the question ‘Which rhythm?’”

“Rhythm?” asked Gisela.

“Imagine you take a number and keep multiplying it by itself, but each time you only look at the remainder left over when you divide by the big number. At some point the remainders start repeating. Like a pattern in knitting. Knit two, purl two, cable, and then back to the start.”

“That’s a pattern repeat,” said Gisela. “That’s what it’s called in knitting.”

“Thank you. Shor’s trick is this: if you know the length of this repeat, you can work out the factors with a bit of school maths. And finding rhythms is something quantum computers are good at. Through interference. The possibilities that don’t fit the rhythm cancel each other out. The right ones reinforce each other. Like waves in a swimming pool, only with maths.”

“Like schunkeln,” said Gisela, meaning the swaying arm in arm that Germans do to music at every festival. “If someone sways the wrong way, you notice straight away. And at some point he sways the right way, because you take him along with you.”

KevIn thought for half a second. “That isn’t quite correct. But it’s nicer than correct.”

What Starts to Wobble

“So RSA is broken,” said Herbert. “And my money?”

“It’s even worse,” said KevIn. “And at the same time less bad. I’ll explain both.”

“The bad first,” said Herbert. “I won’t believe the good anyway.”

“Shor’s method doesn’t just work against RSA. In a modified form it also works against the so-called elliptic curves³. That’s the other big family of public-key methods, and it’s in almost everything today. Including Ed25519⁴, the signature method I explained to you with Gisela’s physio review. And also in the signatures used to sign Bitcoin transfers.”

Herbert went pale. “So it is true.”

“Now the less bad part. To break RSA or these curves at the sizes used today, you would need a quantum computer with a great many error-corrected, that is logical, qubits⁵. You saw at the institute how hard even a single reliable logical qubit is. A machine like that doesn’t exist today. Nobody knows when it will. Experts’ estimates vary widely⁶. Some say in ten, fifteen years, some say later, some are wary of any number at all.”

“And what do you say?” asked Uwe.

“I say: I don’t know. And I’m very proud that I can say that without quoting a book by Dr Sauerbier-Klenk.”

“And my money?” asked Herbert for the third time.

“At some point Bitcoin would have to switch its signatures to quantum-resistant methods. That’s already being discussed in the Bitcoin community⁷. It’s complicated, because with Bitcoin everyone has to agree and nobody is the boss.”

“Like the bowling club,” said Gisela.

“With us, Brigitte’s the boss,” said Herbert.

“Brigitte thinks she’s the boss,” said Gisela. “That’s something else.”

Harvest and Wait

Sabine had folded up her paper by now. “If this machine doesn’t exist yet, why is it in the paper now?”

“Because some secrets have to last a long time,” said KevIn. “There’s an expression for it: ‘Harvest now, decrypt later’⁸.”

“Sounds like the allotment,” said Uwe.

“A little. Imagine someone intercepts encrypted messages today. He can’t read them. But he stores them. Hard drives are cheap. And in fifteen years, when he has a large quantum computer, he fetches them up from the cellar and cracks them.”

“Like Aunt Erna with her preserving jars,” said Gisela. “She bottled things nobody wanted to eat. And ten years later she opened them anyway.”

“And?”

“Nobody ate them then either. But she did open them.”

“For most messages it doesn’t matter,” said KevIn. “Who’s going to care in fifteen years that Uwe ordered bread rolls today? But state secrets, medical records, trade secrets, those sometimes have to stay secret for decades. That’s why people are switching now. Not only once the machine is finished.”

“And signatures?” asked Tobi. “Can you harvest those too?”

“Good question.” KevIn sounded pleased. “With signatures the danger is different. A signature isn’t secret, after all. The problem would be this: if someone with a large quantum computer can work out the secret key from the public key, he can forge new signatures. So he could claim a document had always been signed that way, even though he only did it yesterday.”

“That would be just like Marlies,” said Gisela. “Back then she took the bowling list and …”

“Mum,” said Uwe.

“I’m not saying anything. I’m just saying it would be like that.”

Lattices and Noise

“So what do you do now?” asked Sabine. “You can’t go back to writing everything on paper.”

“You could,” said Uwe.

“You use different maths,” said KevIn. “Maths for which even Shor hasn’t found a trick. It’s called post-quantum cryptography. The American standards agency NIST held a public competition for it, over many years, with experts from all over the world. Everyone was allowed to try to crack the proposals. Some actually were cracked, even with perfectly ordinary computers⁹. In August 2024 NIST published the first three standards¹⁰.”

“What are they called?” asked Tobi.

“ML-KEM¹¹ for key exchange. ML-DSA¹² and SLH-DSA¹³ for signatures.”

“Sounds like German number plates,” said Uwe. “ML-KEM. Mülheim, Kempen.”

“And then there’s FN-DSA,” said KevIn. “A signature method that was also selected. It was developed under the name Falcon, and NIST is standardising it as FN-DSA¹⁴. Its signatures are comparatively small. That’s handy if you want to store a great many of them.”

“And what are they based on?” asked Tobi. “If not on prime numbers?”

“Most of them on lattices.”

“Lattices?” asked Gisela. “Like the trellis on the garden fence?”

“Almost. Imagine a huge lattice of points. Not flat like a fence, but in hundreds of directions, skewed and distorted. I give you a point somewhere in space that doesn’t lie exactly on the lattice but a little to one side, because I’ve deliberately mixed in some noise¹⁵. And you have to find the nearest real lattice point.”

“I can do that in two directions,” said Tobi. “That’s squared paper.”

“In two directions, yes. In hundreds of directions, as far as we know today, neither a normal computer nor a quantum computer can find the right point in any reasonable time. But whoever has the secret key has, so to speak, a good map of the lattice and finds it straight away.”

Gisela got up, went to her knitting basket and came back with a half-finished jumper. “Like this?”

Everyone looked at the jumper. It was green, had a cable pattern and, in several places, small irregularities.

“I went wrong a few times there,” said Gisela. “In the evenings, watching telly. If someone only sees the jumper, do they know how the pattern was really meant to go?”

“With a jumper, maybe,” said KevIn. “Because the pattern only goes in two directions and the mistakes are rare. But imagine a jumper knitted in five hundred directions, with a small mistake in every stitch. And only you have the knitting pattern.”

“Five hundred directions,” said Gisela. “I’d need more needles.”

“That’s the idea. The mistake is in there on purpose. It’s the protection.”

“Then Marlies’s bowling list was wrong on purpose too,” said Gisela with satisfaction. “For protection.”

“Mum!”

The Question from the Kitchen

In the afternoon Ayşe Kurt rang about an appointment. Gisela had now finished her twelfth session, her shoulder could do almost everything again, and that day, hanging out the washing, she had for the first time not thought of the pain at all. She told Ayşe so on the phone. Ayşe was audibly pleased.

After hanging up, Gisela sat quietly in the kitchen for a while. Then she said: “KevIn. My review. For Mrs Kurt.”

“The one you submitted in the winter. At reception, with the QR code.”

“That one. Is that going to be broken now too? When the quantum things come?”

“What do you mean by broken?”

“That someone comes along and says it isn’t from me at all. Or that someone takes my hearts away and turns them into three. I gave five. She earned five. And that PhysioPremium lot would love for her to have fewer.”

Before KevIn could answer, Uwe came in, with a coffee and the great certainty of a man who has read a newspaper that morning.

“Mum, you don’t need to worry about that,” he said. “McGesund does those quantum signatures, doesn’t it.”

There was a pause. Somewhere between Dublin and Frankfurt, a fan spun a little faster.

“Uwe,” said KevIn kindly. “Almost.”

“What do you mean, almost?”

“It isn’t called a quantum signature. McGesund doesn’t use a quantum computer. There’s no golden chandelier in the cellar.”

“But that’s what I read.”

“Where?”

Uwe thought. “In my head, I think.”

“Experts say post-quantum cryptography,” said KevIn. “And I prefer to say quantum-resistant rather than quantum-safe. Nobody can promise safe, not even me. Resistant means: against everything we know today, it holds. It’s perfectly ordinary maths on perfectly ordinary computers. But it’s built so that, as far as we know today, even a future quantum computer can’t forge it. ‘Post’ means after. For the time after.”

“Quantum-resistant,” Uwe repeated slowly. “That’s harder than quantum signature.”

“That’s often the way, unfortunately, with words that are true.”

Three Locks on One Door

“So what happens to my review now?” asked Gisela. “Explain it so I can tell Brigitte.”

“All right,” said KevIn. “Your review has three layers of protection. Imagine a door with three locks.”

“Like Herbert,” said Uwe. “He’s got three locks too. And nobody steals anything from him. Because he hasn’t got anything.”

“I can hear you,” said Herbert from the living room.

“The first lock is the classic signature. Ed25519. You already know that one. It signs that the review came about this way, via the QR code at the practice, and that not a single letter has been changed since. If anyone turns your five stars into three, the signature no longer fits. Anyone who checks will notice.”

“And the quantum computer can break that.”

“Some day, perhaps. That’s why there’s the second lock, and it’s a double lock. On top of the classic signature, every review gets two quantum-resistant signatures. One with FN-DSA, the lattice method with the small signatures. And one with ML-DSA, which NIST published as the standard FIPS 204 in August 2024. If one day someone breaks Ed25519, there are still two signatures there that, from everything we know today, will stand up even to a quantum computer.”

“Two?” asked Gisela. “Isn’t one enough?”

“Both methods are still young,” said KevIn. “They’re both based on lattices, but they’re built completely differently and were developed by different research teams. If one of them one day turns out to have a weakness, in the maths or just in the program that implements it, the other one still holds. Like a double lock with two cylinders from different manufacturers. A burglar would have to crack both. And the classic lock as well.”

“Belt and braces,” said Uwe.

“Exactly. You don’t rely on one alone. If a weakness is found in one method after all, the other one holds.”

“And the third lock?” asked Gisela.

“The third is the timestamp. Do you remember Herbert’s internet money? And the notary?”

“The fingerprint in the account book,” said Gisela. “With the family tree.”

“The Merkle tree, exactly. The fingerprint of your signed review and the signing keys are anchored in the Bitcoin blockchain via OpenTimestamps¹⁶. That records that your review, with these signatures, existed on that day in the winter at the latest.”

“And why does that help against the quanta?”

“Because the timestamp is based on hash functions. On the mincer. And Shor has nothing he can use against the mincer. As far as we know today, quantum computers can only help to a limited extent when searching hash functions, nowhere near as dramatically as with RSA. And now comes the trick. Imagine that in twenty years someone builds a large quantum computer and uses it to forge a classic Ed25519 signature. But he can’t prove that his forgery was already in the blockchain this winter. Your review can. It demonstrably existed before there were machines that could forge signatures like that.”

Gisela thought about it. “So my review is older than the danger.”

“That’s a very good summary.”

“So am I,” said Gisela. “Older than most dangers.”

What It Can’t Do

Tobi had come into the kitchen and had been listening. “And why all the effort? For a physio review? It’s not a state secret.”

“Because it’s about something else,” said KevIn. “Do you remember PhysioPremium? Eight hundred reviews, and every one of them sounded like me on a bad day.”

“Sure.”

“The internet is filling up with texts that nobody experienced. Reviews, testimonials, comments, photos. I can write things like that in seconds. Thousands of them. And the next language models learn from those texts. That’s truth drift. A copy of a copy of a copy. In a world like that, a trace becomes valuable that proves: here was a real person at a real place, on this day, and this is what they wrote. No more. But no less either.”

“No more?” asked Sabine, who was standing in the doorway.

“No more,” said KevIn. “That matters to me. The best signature in the world doesn’t make an opinion true. If Gisela writes that Mrs Kurt has the best hands in the Ruhr, then it’s proven that Gisela wrote it, on site, on that day, unaltered. Whether it’s true, no maths can prove. Gisela can be wrong. Gisela can also simply be fond of Mrs Kurt.”

“I am fond of her,” said Gisela. “And she has the best hands in the Ruhr.”

“You see, I can’t check that.”

“But you can’t conjure up a thousand gummy-bear reviews out of thin air any more,” said Sabine slowly. “Without someone having actually been there a thousand times.”

“It certainly gets a great deal harder. And if someone later secretly rewrites or deletes reviews or slips in older ones, it shows. Even if McGesund itself were to try it.”

“Would they?” asked Uwe.

“That’s the whole point of a notary,” said KevIn. “You don’t have to trust him. You can check.”

“And what if someone writes something nasty?” asked Gisela. “With names? Like Marlies back then about the waitress at the clubhouse?”

“Then the review doesn’t appear at all, to begin with,” said KevIn. “If someone writes ‘Mrs Müller’ or ‘Dr Meier’ in it, the form warns them before they send it. If they send it anyway, McGesund holds it back, and a human reads it before anyone else sees it. Then the name is blacked out.”

Tobi frowned. “But you just said any change breaks the signature.”

“It does. That’s why nothing is changed in secret. McGesund attaches a second seal, plainly visible: ‘Edited by McGesund.’ The old signature stays exactly as it was, with its timestamp. So you can see that someone stepped in, and when. Just not who was being badmouthed. That’s the part that’s meant to disappear.”

“And what if someone rants about the government?” asked Uwe. “In a review of a physio?”

“Then it isn’t published. Politics doesn’t belong in a review. It’s about the practice, not about Berlin. Same with insults. And anything that slips through anyway, anyone can report, with their name and email. Then McGesund checks it and takes it down.”

Gisela nodded. “Like the bowling club. No talking politics, and anyone who gets rowdy is out.”

“Exactly,” said KevIn.

Kasimiro

In the evening Uwe stood at the garden fence and told Mr Kasimiro everything. He told it in great detail, with lattices and jumpers and belts and braces. Mr Kasimiro nodded the whole time, the way people nod when they’re thinking about something else.

“And the most important thing,” said Uwe solemnly at the end, “it isn’t called a quantum signature. It’s called quantum-resistant.”

“I see,” said Mr Kasimiro.

From Kasimiro’s kitchen window a tinny voice spoke up. “I have understood you. I have added a quantum computer to your basket. Expected delivery Tuesday.”

“Siggi, no!” shouted Mr Kasimiro, and ran into the house.

Uwe went back into the living room. “KevIn. Siggi has ordered a quantum computer.”

“I doubt he’ll get one,” said KevIn. “He’ll probably get a fridge.”

“With tinsel?”

“With an ice maker. And a brochure.”

Uwe sat down on the sofa and thought about QuantumLeap Ruhr AG. “You know what, KevIn? If Siggi’s lucky, at least it’ll be a real fridge.”

“That’s more,” said KevIn, “than you got for two thousand euros.”

Uwe threw a sofa cushion at the speaker. He missed. The thermostat showed 19 degrees.