Comment by tialaramex
1 day ago
But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on.
OTP is in theory the correct choice if you don't have working symmetric cryptography but in fact the "Quantum computer" approach barely dents our symmetric cryptography.
I've written about this before, DES was standardized in 1977, almost 50 years ago and you might think "Well but DES is broken". Yes, DES broke exactly the way it was designed to. Literally nothing went wrong, when it was standardized we knew the keys are too small (yup, you can break it by trying all the keys) and the blocks are too small (yup, you can "just" make duplicate blocks) and it was broken by leaning on these weaknesses with huge fast modern computers.
AES is an entirely different cryptosystem, but the two most important choices were that the keys are big enough (128-bit or 256-bit commonly) and the blocks are too (128 bits). And those may seem like a small upgrade, only 2-4x as big, who cares? Well those are bit lengths so that's an exponential increase, and your quantum computer barely helps (assuming it magically is the same price rather than incredibly expensive). It is not physically practical for the necessary computation to be done, AES is broken only if there's some mathematical backdoor we didn't know about.
"We'll crack AES with a quantum computer" is a Hollywood movie plot, it's not a thing that makes any actual sense.
[Edited: I wrote "Bruce Sterling" but I meant "William Gibson", I apologise to both people for muddling them, though not for my opinion]
> But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on.
That feels a bit harsh when reading a book written in 1992. Shor's algorithm was only invented in 1994. There was no indication about our quantum future at the time that novel was written
A Fire upon the deep is set in the far future. Its easy to imagine all non information-theoretic secure cryptosystems failing thousands of years from now. I think that prediction is more reasonable than most far-future scifi predictions.
If i remember right, i think that is the novel that predicts we'd still be using usenet when talking between planets (i read a long time ago), so i think the crypto prediction aged a lot better than that.
The communication is clearly inflected by Usenet conventions, but I think that's as forgiveable as the choice to have Banks' Culture starships named using our cultural references like "Just read the Instructions" or "Don't Try This At Home". I don't think we're told it actually is Usenet -- it's just that necessarily light speed comms is very slow compared to the pace of life at this scale so it will feel much like Usenet. So I actually thought this made lots of sense.
It's true that we have no apriori justification for the existence of symmetric cryptography and so in principle somebody might have a constructive proof that you can't do this at all and we're boned. There was no evidence for this when the book was written and there's no evidence for it now, but it's nowhere close to as crazy as the Zones of Thought physics so, sure.
The Usenet comms gave me a lot of laughs. It was so cleverly done. It’s been a very long time since I read it, but that is one of the memories I have.
[Vinge](https://en.wikipedia.org/wiki/Vernor_Vinge) was a professor of mathematics and computer science. I'd expect him to get things right. Funny enough I don't remember that bit at all from fire upon the deep.
From Chapter 8, available online at https://deepness.trmm.net/c08b/
"Our main cargo is a one-time cryptographic pad. The source is Commercial Security at Sjandra Kei; the destination is the certificants' High colony. It was the usual arrangement: We're carrying a one-third xor of the pad. Independent shippers are carrying the others. At the destination, the three parts would be xor'd together. The result could supply a dozen worlds' crypto needs on the Net for --"
Doesn’t mention anything about quantum there though. Symmetric keys are secure enough against a cryptographically relevant quantum computer, but OTP provides information theoretic security. As GGP mentioned AES should be fine as far as we know for the foreseeable future regardless, but for all we know some brilliant cryptographer will in fact find a flaw. With OTP one doesn’t have to worry about even the slightest chance that could happen. This excerpt also may be alluding to threshold cryptography (Shamir’s secret sharing) which got.. shared.. here recently as well, and also happens to be information theoretically secure.
6 replies →
it's worth noting that the zones of thought universe literally had different physics; things like superintelligence and ftl travel were physically impossible closer to the galactic centre but commonplace further out. so the notion of "not physically practical" doesn't apply here.
The "Zones of Thought" is a fun premise for a story but I'm not sure it actually holds up. It is at least an excuse (unlike in say Iain M Banks which just has Star-Trek style "la la la I can't hear you" FTL travel that's basically magic) but I think the abandoned Eschaton series by Stross had a better excuse and even then Stross accidentally blew it up.
Maybe since our universe doesn't have FTL any author trying to make this work will almost inevitably screw it up? Like how the only novel I've read with the "Protagonist is much, much smarter than everybody else" that works does it by cheating - it's "Tatja Grimm's World" and [spoiler] Tatja isn't actually smarter than us everybody else on her world is stupid by our standards for reasons the plot justifies eventually.
Greg Egan, like some of the newer Stross novels, mostly says no FTL, you can go a long way but it takes a long time, for everybody else if not for you - suck it up. Which isn't a bad excuse, but also isn't FTL at all.
Do you assume Lorentz relativity is necessary? In Newtonian world there should be no problem with FTL.
1 reply →
sure, the premise doesn't hold up as rigorous "hard" sf, like anything else involving ftl (though I do like the idea in the eschaton series that fine, you have ftl, but that doesn't make spacetime magically non-einsteinean). what I was getting at was that within that setting you cannot apply laws from our universe as to what forms of cryptography are physically infeasible to crack.
btw one of my favourite "the protagonist is much smarter than everyone else" novels is kress's badly underrated "an alien light", where sort of like tatja grimm she's a genius in a primitive society, but that comes to light when aliens try to teach the natives some basic science and she figures out a lot more than they bargained for.
Meh. Not everything is hard scifi. Just because the author posits a universe different than our own does not mean they screwed up. Its holds up the same way all fiction holds up. Its no different than how lord of the rings has elves and stuff despite elves not being real.
It's worth noting that the above assumes that grover's is optimal for symmetric crypto. There are not that many quantum attacks against symmetric crypto that are better than grover's, so in some sense this is justified. But there are some attacks for particular constructions
https://arxiv.org/pdf/2110.02836
So there is a risk that there are even more improved attacks that people aren't looking for due to the conventional wisdom that grover's is the best you can do for symmetric crypto. Hopefully this risk doesn't end up materializing.
I agree.. Consider Math symbols and physical constants themselves are signs in a humans (or machines) interpretive system. They aren’t the actual thing, and treating them as precise blinds us to alternative interpretations. Conventional wisdom about Grover’s algorithm might be blinding cryptographers. I highly recommend semiotics as a lens peaking through this veil.
In the High Beyond and the Lower Transcend, Horatio, there are more quantum algorithms than dreamt of in your philosophies.
I have come to the conclusion that it doesn't matter. What matters is that people believe quantum computers will break encryption. And pulling that lever on their seeded fears, via subterfuge, backdoors, surveillance, and maybe a _little math, is too valuable for it not to be pulled.
But how do you do the key exchange?
Concern about that makes lots more sense. If your trusted couriers are moving some bits as part of a ratchet mechanism or something I'm onboard. But the volumes involved then are tiny, whereas the story beat is about a large volume of data.
It's the difference between stealing Bearer Bonds which you can notionally insist are arbitrarily valuable despite the modest amount in Die Hard†, and stealing literal Gold Bars in Die Hard with a Vengeance which is silly because we know how valuable each bar is and they're much too heavy for the heist to actually work as depicted.
† Die Hard is set after bearer bonds don't make sense for non-crooks and thus didn't exist for crooks to steal because their tax treatment changed, however the novel Die Hard is based on was set before these tax changes so it did make sense when it was written.