Pentashagon comments on Open Thread, September 1-15, 2012 - Less Wrong

6 Post author: OpenThreadGuy 01 September 2012 08:13AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (353)
Tags: open_thread thread open

Comments (353)

You are viewing a single comment's thread. Show more comments above.

Comment author: Alicorn 03 September 2012 02:52:06AM *  12 points [-]

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.)

Comment author: Pentashagon 11 September 2012 04:13:14AM *  1 point [-]

You need to think about one-way functions (hashes) and trapdoor one-way functions (public key algorithms). There are some additional issues that arise like nonces to thwart replay attacks and the level of protection individuals can be expected to give to secret keys.

Also, even without explicit mathematics the universe will presumably have a concept of entropy and conservation of something, even if it's just conservation of magical energy. If you can come up with a plausible problem that magic can solve given a lot of expended magical energy but can be solved much more easily with the knowledge of a secret, then you can build a challenge-response identify proof so long as it's not easy to steal the secret by watching the demonstration. If additionally it's very hard to derive the secret from the demonstration of its knowledge you probably have the power of a public key system.

Not all the following problems require magic to implement, and many of them actually benefit from not having a knowledge of mathematics and algorithms, since most of these are not cryptographically secure.

  • Have each person construct an elaborate puzzle out of oddly shaped objects that can be packed into a small finite volume in only one way (the knapsack problem)
  • Each person constructs a (large) set of sticks (or metal rods, or whatever) of varying lengths, of which a subset add up to a standard length like a meter (the subset sum problem)
  • Society forms a hierarchical tree of secret handshakes so that each person only has to remember, say, 100 secret handshakes and the tree only has to be log_100 (N) tall so the courts can just subpoena a logarithmic number of individuals to verify handshakes between any two arbitrary people. Obviously any one of your 100 acquaintances can impersonate you, so two or more distinct trees would at least require collusion.
  • Any magical item that only functions for its "owner".
  • A magical "hash function", like a petronus or an aura, that is unique to every individual (not body) and can't be faked. Producing it would be an effective identifier.

Lastly, I should point out that very few "normal" people in the situation you describe would be able to achieve cryptographic security anyway. I can (barely) memorize a passphrase with 128-bit entropy (using diceware, so I'm certain it actually has 128 bits), and even that's not quite enough to choose a secure secret key for Elliptic Curve DSA. And it would have to only be memorized and never written down anywhere, and only computed on trusted hardware (who the sleep-twin could modify to their heart's content while I slept). So, yeah, Magic.

Powered by Reddit Powered by Reddit