Extremely Weak Cryptography: Rot13 for Numbers
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.
