= 27d567bc2d48d9f40e9ccc20ea370b15)
Salutator comments on Open Thread, September 1-15, 2012 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (353)
I'm thinking about a fantasy setting that I expect to set stories in in the future, and I have a cryptography problem.
Specifically, there are no computers in this setting (ruling out things like supercomplicated RSA). And all the adults share bodies (generally, one body has two people in it). One's asleep (insensate, not forming memories about what's going on, and not in any sort of control over the body) and one's awake (in control, forming memories, experiencing what's going on) at any given time. There is not necessarily any visible sign when one party falls asleep and the other wakes, although there are fakeable correlates (basically, acting like you just appeared wherever you are). It does not follow a rigid schedule, although there is an approximate maximum period of time someone can stay awake for, and there are (also fakeable) symptoms of tiredness. Persons who share bodies still have distinct legal and social existences, so if one commits a crime, the other is entitled to walk free while awake as long as they come back before sleeping - but how do they prove it?
There are likely to be three levels of security, with one being "asking", the second being a sort of "oh yeah? prove it" ("tell me something only my wife would know / exhibit a skill your cohabitor hasn't mastered / etc."), and the third being... something. Because you don't want to turn loose someone who could be a dangerous criminal just because they were collaborating with a third party to learn information, or broke into the National Database of Secret Person-Distinguishing Passphrases, or didn't disclose all their skills to some central skill registry - but you don't want to lock up innocent people who made bad choices about who to move in with when they were eight, either.
Is there something that doesn't require computers, or human-atypical levels of memorization/computation, or rely critically on a potentially-break-into-able National Database of Secret Person-Distinguishing Passphrases, which will let someone have a permanently private bit of information they can use to verify to arbitrary others who they are? (There is magic, but it is not math-doing magic.)
Can they use quill and parchent?
If so, the usual public key algorithms could be encoded into something like a tax form, i.e. something like "...51. Subtract the number on line 50 from the number on line 49 and write the result in here:__ ...500. The warden should also have calculated the number on line 499. Burn this parchent."
Of course there would have to be lots of error checks. ("If line 60 doesn't match line 50 you screwed up. If so, redo everything from line 50 on.")
To make it practical, each warden/non-prisoner-pair would do a Diffie-Hellman exchange only once. That part would take a day or two. After establishing a shared secret the daily authentication would be done by a hash, which probably could be done in half an hour or less.
Of course most people would have no clue why those forms work, they would just blindly follow the instructions, which for each line would be doable with primary school math.
The wardens would probably spend large parts of their shifts precalculating hashes for prisoners still asleep, so that several prisoners could do their get-out work at the same time. Or maybe they would do the crypto only once a month or so and normally just tell the non-prisoners their passwords for the next day every time they come in.
I don't think that I understand how this works, which has a meta-level drawback...
You might have better expository skills than Salutator, and people love learning esoteric things about mysterious professions in the midst of fiction. Diffie-Helman relies on certain properties of math in prime modulus groups, but understanding those properties isn't necessary just to do DH. It only takes primary-school level math abilities to follow the example on Wikipedia (and note that, if nobody has computers, you don't need a 2048 bit modulus.