Extremely Weak Cryptography: Rot13 for Numbers

Monday, May 31, 2010
By dreeves

Two people giving (encrypted) arguments about various encryption schemes. ... 'EBG13 vf terng!' ... 'Double ROT13 is better!'

The idea of rot13 is to obscure text, for example, to prevent spoilers. It’s not meant to be cryptographically secure but simply to make sure that only people who are sure they want to read something will read it.

We, being pretty extreme nerds, sometimes find ourselves wanting to do something similar for numbers. This is typically in the context of a sealed-bid auction where you want to submit a bid that the other party can unseal whenever they’re ready, with no further coordination needed. Most recently, Sharad and I had to decide who would be presenting our Prediction Without Markets paper at the upcoming ACM Ecommerce conference. To determine who wanted to present more (i.e., who minded least), I sent him my sealed bid (how much I would pay him, at most, to present) and told him to unseal it when he had committed to his own bid. (Eliminating the need for further coordination was especially useful here because Sharad was about to get on a plane. It’s similarly handy when coordinating by text message when one or both parties are about to get on the subway.)

The outcome in that case was that Sharad bid lower and so I paid him that lower bid to be the one to present our paper.

In general what we want is a way for me to send you a number and trust you to pick your own number, uninfluenced by mine. And then you should be able to reveal mine when you’re ready, without requiring further input from me or any third party. Note the assumption that the recipient is being trusted not to cheat.

So how do we do that? It’s not as simple as rot13 because certain numbers, like 1 and 2, will recur often enough that you might remember that, say, “gjb” is really 2.

To be more specific, we seek a function, seal(), that maps a real number to a real number (or a string). It should not be deterministic — seal(7) should not map to the same thing every time. But the corresponding function, reveal(), should be deterministic — reveal(seal(x)) should equal x for all x.

For example:

   > seal(7)              # Some random-seeming
   429964                 # number or string.

   > seal(7)              # A completely different
   749932                 # random-seeming number.

   > reveal(seal(7))      # Revealing always uncovers
   7                      # the original number.

Can you think of a way to implement seal() and reveal()?

How to Seal and Reveal a Secret Number

There are many ways, it turns out, to accomplish this but here, in lay terms, is an elegant scheme that can be carried out easily with a pocket calculator:

Pick a random number (from your head is fine) between 9 and 99 and multiply it by 9999, then add your secret number. This will yield a 5 or 6-digit number that encodes your secret number. To decode it, divide by 9999, subtract the part to the left of the decimal point, then multiply by 9999. (This is known to children and mathematicians as “finding the remainder when dividing by 9999” and “mod’ing by 9999”, respectively.)

This works for nonnegative numbers less than 9999 (if that’s not enough, use 99999 or as many nines as you want). If you want to allow negative numbers, then the magic 9999 number needs to be twice the biggest possible number. And when decoding, if the result is greater than half of 9999, i.e., 5000 or more, then subtract 9999 to get the actual (negative) number.

Again, this is not a true commitment scheme. But for cases where the honor system suffices and the only goal is to not be influenced by each other’s number, we find this quite handy.

Pseudocode

   M = 9999  # Numbers between -M/2 and M/2 can be sealed.

   seal(x): M * randInt(9, 99) + x

   reveal(x): m = mod(x, M); 
              if m > M/2 return m - M else return m

Image by Jeff Moser.

Thanks to Svante v. Erichsen for the idea behind this scheme, and to a dozen other Stack Overflow users for alternative schemes.

Tags: , , , ,

  • http://tombrow.com Tom

    I like this solution because you can unseal with a terse Google query: “[sealed number] % 99999”.

  • http://ai.eecs.umich.edu/people/dreeves dreeves

    Ha, thanks Tom! I hadn’t realized that. For those who don’t know, “a mod b” is commonly abbreviated “a % b”. Google is finicky though — it doesn’t understand if there are spaces around the percent sign and it doesn’t understand if you use “mod” instead of “%”. Both bing.com and wolframalpha.com give the answer however you enter it.

  • http://www.decisionsciencenews.com Dan

    Since people who see numbers, any numbers, make estimates that are influenced by them (so-called “anchoring effects”), a tiny improvement would be getting it to encode as a string, which you say is possible.

    The effect of anchoring may cancel out over repeated plays, but why have it there when it makes it harder for the other person to think clearly? I mean, you wouldn’t sing the Star Spangled Banner at the top of your lungs when the other person is trying to come up with a bid, a distraction is a distraction.

    While no representation is neutral, you can probably do better than a longish number.

  • http://ai.eecs.umich.edu/people/dreeves dreeves

    Thanks Dan, excellent point. I acknowledge that the anchoring effect is significant. Have you actually become so self-aware that you can feel its effect on you, like the equivalent of someone yelling the Star-Spangled Banner while you’re trying to think? At best I can realize in retrospect that I must’ve gotten anchored.

    As for this application, I’m not convinced it’s such an issue. Even in the famous example where subjects anchored on their own social security numbers they first wrote down a portion of their SSN that was within a plausible range for their bids. How do you get anchored by a totally random long-ish string of digits?

  • http://blog.oddhead.com David Pennock

    I like this a lot. Very clever. Adding to Tom’s point, to simplify life for the unsealer, the sealer can send the encoded number as a URL: http://www.bing.com/search?q=429964mod9999

    It might make Dan G happy (and increase the security) to go further and bit.ly that URL, but I agree with Dan R that this seems like overkill.

  • http://blog.oddhead.com David Pennock

    Thinking about this further: Can anyone come up with a simple way to use search engines or wolfram alpha to conduct a true zero-knowledge auction? Something nearly as simple but that doesn’t have to rely on trust?

  • http://blog.oddhead.com David Pennock

    Dan G might be happy with the encoder sending their bid in this form:
    http://www.wolframalpha.com/input/?i=CDXXIX1000%2BCMLXIV+mod9999

  • http://ai.eecs.umich.edu/people/dreeves dreeves

    @David Pennock: Thanks for the idea of turning the unsealing part into a single click; smart. And roman numeralizing as anchor-prevention, ha! I still say you can only get anchored by numbers you entertain as candidate valuations, however briefly. But IANAP (I am not a psychologist).

    Also to Dave: Have you coined “zero-knowledge auction” by analogy to zero-knowledge proof? Does it boil down to a commitment scheme (see link at the end of the post)? I tried having wolframalpha multiply some big random numbers, but for anything not totally unwieldy it seems to factor them as fast as it multiplies them. But you can do this:

    http://www.wolframalpha.com/input/?i=md5+%22my+bid+is+123+and+my+nonce+is+somerandomstring%22

    The hash is in theory unreversible so if you first tell each other the hashes per above, you can then reveal your bids sequentially. The second person has to stick with the bid they committed to because that’s the only thing that will generate the same hash. (Note the need for the nonce otherwise you could find out the bid from the hash just by trying all possible bids.)

  • Pingback: Rot13 for numbers | Ask Programming & Technology

  • Stephen P

    good work here is my version of rot13 its called cicada https://sites.google.com/site/psychocatdemo/cid

  • Pingback: Rot13 for numbers | Questions