13

EDIT: Now a Major Motion Blog Post at http://messymatters.com/sealedbids

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

I'd like to do something similar for numbers, for an application involving sealed bids. Roughly I want to send someone my number and trust them to pick their own number, uninfluenced by mine, but then they should be able to reveal mine (purely client-side) when they're ready. They should not require further input from me or any third party.

(Added: Note the assumption that the recipient is being trusted not to cheat.)

It's not as simple as rot13 because certain numbers, like 1 and 2, will recur often enough that you might remember that, say, 34.2 is really 1.

Here's what I'm looking for specifically:

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 unseal() should be deterministic -- unseal(seal(x)) should equal x for all x. I don't want seal or unseal to call any webservices or even get the system time (because I don't want to assume synchronized clocks). (Added: It's fine to assume that all bids will be less than some maximum, known to everyone, say a million.)

Sanity check:

> seal(7)
482.2382   # some random-seeming number or string.
> seal(7)
71.9217    # a completely different random-seeming number or string.
> unseal(seal(7))
7          # we always recover the original number by unsealing.
6
  • 1
    You mention that you want to send real numbers to real numbers, but then you post an example solution that uses rot-13 (and thus ASCII strings rather than real numbers). What specifically is the domain and range you are interested in? And how much entropy should these have (as in, how many possible values in the range should correspond to one value in the domain)? Apr 30, 2009 at 21:35
  • 1
    Two decimal places would (more than) suffice. In my rot13-based solution you'd map, say, 3.14 to "three point one four".
    – dreeves
    Apr 30, 2009 at 21:37
  • Are bids limited to integers >= 0?
    – John Rasch
    Apr 30, 2009 at 21:38
  • 1
    Good question. Surprisingly, no, not always; negative bids have special meaning in the mechanism we're using. Though if you have something that works nicely under that constraint I'm interested to see it.
    – dreeves
    May 1, 2009 at 1:20
  • Why display the number at all - say, display a bunch of "xxxxxx" until the user clicks "reveal thyself". (Although, if this is a printed process... Then this does make sense)
    – Arafangion
    Jun 3, 2010 at 0:58

13 Answers 13

7

You can pack your number as a 4 byte float together with another random float into a double and send that. The client then just has to pick up the first four bytes. In python:

import struct, random
def seal(f):
   return struct.unpack("d",struct.pack("ff", f, random.random() ))[0]
def unseal(f):
   return struct.unpack("ff",struct.pack("d", f))[0]

>>> unseal( seal( 3))
3.0
>>> seal(3)
4.4533985422978706e-009
>>> seal(3)
9.0767582382536571e-010
7

Here's a solution inspired by Svante's answer.

M = 9999  # Upper bound on bid.
seal(x) = M * randInt(9,99) + x
unseal(x) = x % M

Sanity check:

> seal(7)
716017
> seal(7)
518497
> unseal(seal(7))
7

This needs tweaking to allow negative bids though:

M = 9999  # Numbers between -M/2 and M/2 can be sealed.
seal(x) = M * randInt(9,99) + x
unseal(x) = 
  m = x % M; 
  if m > M/2 return m - M else return m

A nice thing about this solution is how trivial it is for the recipient to decode -- just mod by 9999 (and if that's 5000 or more then it was a negative bid so subtract another 9999). It's also nice that the obscured bid will be at most 6 digits long. (This is plenty security for what I have in mind -- if the bids can possibly exceed $5k then I'd use a more secure method. Though of course the max bid in this method can be set as high as you want.)

Instructions for Lay Folk

Pick a number between 9 and 99 and multiply it by 9999, then add your bid. This will yield a 5 or 6-digit number that encodes your bid. To unseal 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" or "mod'ing by 9999", respectively.)

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

Again, note that this is on the honor system: there's nothing technically preventing you from unsealing the other person's number as soon as you see it.

1
  • Excellent answer. Us lay folk appreciate it!
    – Geoherna
    Oct 22, 2020 at 2:38
4

If you're relying on honesty of the user and only dealing with integer bids, a simple XOR operation with a random number should be all you need, an example in C#:

static Random rng = new Random();

static string EncodeBid(int bid)
{
    int i = rng.Next();
    return String.Format("{0}:{1}", i, bid ^ i);
}

static int DecodeBid(string encodedBid)
{
    string[] d = encodedBid.Split(":".ToCharArray());
    return Convert.ToInt32(d[0]) ^ Convert.ToInt32(d[1]);
}

Use:

int bid = 500;
string encodedBid = EncodeBid(bid); // encodedBid is something like 54017514:4017054 and will be different each time
int decodedBid = DecodeBid(encodedBid); // decodedBid is 500

Converting the decode process to a client side construct should be simple enough.

4

Is there a maximum bid? If so, you could do this:

Let max-bid be the maximum bid and a-bid the bid you want to encode. Multiply max-bid by a rather large random number (if you want to use base64 encoding in the last step, max-rand should be (2^24/max-bid)-1, and min-rand perhaps half of that), then add a-bid. Encode this, e.g. through base64.

The recipient then just has to decode and find the remainder modulo max-bid.

5
  • There is a maximum bid, and would be for any application I can imagine (eg, for an actual sealed bid auction, world GDP is an upper bound). But I think your scheme has the problem that, eg, a bid of zero will always map to something with the same last character.
    – dreeves
    May 1, 2009 at 3:24
  • No, only if you use a max-bid that has no set bits in the last 6. If this is the case, you should add some small amount to the actual max-bid to get a good number for this scheme.
    – Svante
    May 1, 2009 at 11:59
  • Ah, nice! So seal(x) = 1234567*RandInt(1,100)+x; unseal(x) = x % 1234567; Brilliant. It needs a tweak to handle negative bids though. Should be fixable if maxbid is twice the actual max bid.
    – dreeves
    May 1, 2009 at 15:13
  • Btw, I don't see the value in base64 encoding. See my implementation of your idea below. (Feel free to incorporate that into your answer and I'll delete mine.) Thanks again; this is very clever. I think this is the best approach of all the answers so far.
    – dreeves
    May 1, 2009 at 19:46
  • Svante, can I get your real name so I can give you credit when referring to / implementing / blogging about / etc, your idea? I think it's going to be really handy -- especially since any lay person can do it with just a hand calculator.
    – dreeves
    May 10, 2009 at 1:00
4

What you want to do (a Commitment scheme) is impossible to do client-side-only. The best you could do is encrypt with a shared key.

If the client doesn't need your cooperation to reveal the number, they can just modify the program to reveal the number. You might as well have just sent it and not displayed it.

To do it properly, you could send a secure hash of your bid + a random salt. That commits you to your bid. The other client can commit to their bid in the same way. Then you each share your bid and salt.

[edit] Since you trust the other client:

Sender:
Let M be your message
K = random 4-byte key
C1 = M xor hash(K) //hash optional: hides patterns in M xor K
//(you can repeat or truncate hash(K) as necessary to cover the message)
//(could also xor with output of a PRNG instead)
C2 = K append M //they need to know K to reveal the message
send C2 //(convert bytes to hex representation if needed)

Receiver:
receive C2
K = C2[:4]
C1 = C2[4:]
M = C1 xor hash(K)
2
  • 1
    Absolutely. But note that I'm assuming trust and goodwill, just as in rot13.
    – dreeves
    Apr 30, 2009 at 21:29
  • Ah, that's more like it; thanks! Though in the meantime I think Svante's answer has this beat for sheer simplicity.
    – dreeves
    May 1, 2009 at 19:29
2

Are you aware that you need a larger 'sealed' set of numbers than your original, if you want that to work?

So you need to restrict your real numbers somehow, or store extra info that you don't show.

1
  • I think that's only a problem in theory, not in practice. And even in theory it's probably fine with an infinite domain and range. In any case, I edited the question to allow mapping to an arbitrary string, but I think the best answers aren't doing that.
    – dreeves
    May 2, 2009 at 12:08
2

One simple way is to write a message like:

"my bid is: $14.23: aduigfurjwjnfdjfugfojdjkdskdfdhfddfuiodrnfnghfifyis"

All that junk is randomly-generated, and different every time.

Send the other person the SHA256 hash of the message. Have them send you the hash of their bid. Then, once you both have the hashes, send the full message, and confirm that their bid corresponds to the hash they gave you.

This gives rather stronger guarantees than you need - it's actually not possible from them to work out your bid before you send them your full message. However, there is no unseal() function as you describe.

This simple scheme has various weaknesses that a full zero-knowledge scheme would not have. For example, if they fake you out by sending you a random number instead of a hash, then they can work out your bid without revealing their own. But you didn't ask for bullet-proof. This prevents both accidental and (I think) undetectable cheating, and uses only a commonly-available command line utility, plus a random number generator (dice will do).

If, as you say, you want them to be able to recover your bid without any further input from you, and you are willing to trust them only to do it after posting their bid, then just encrypt using any old symmetric cipher (gpg --symmetric, perhaps) and the key, "rot13". This will prevent accidental cheating, but allow undetectable cheating.

3
  • Wouldn't a symmetric cipher with a static key map the same number to the same string every time?
    – dreeves
    May 1, 2009 at 2:35
  • Yes, I meant (but didn't say) to encrypt a salted message as in the first part of my answer. May 1, 2009 at 2:41
  • Oh yes, and the length of the junk should be chosen to pad the message to a fixed length. A fixed-size salt might be close to a multiple of the block size of the cipher, with the result that bids over $100 output a larger encrypted message :-) May 1, 2009 at 17:56
1

One idea that poped into my mind was to maybe base your algorithm on the mathematics used for secure key sharing.

If you want to give two persons, Bob and Alice, half a key each so that only when combining them they will be able to open whatever the key locks, how do you do that? The solution to this comes from mathematics. Say you have two points A (-2,2) and B (2,0) in a x/y coordinate system.

               |
       A       +
               |
               C
               |
---+---+---+---|---+---B---+---+---+---
               |
               +
               |
               +

If you draw a straight line between them it will cross the y axis at exactly one single point, C (0,1). If you only know one of the points A or B it is impossible to tell where it will cross. Thus you can let the points A and B be the shared keys which when combined will reveal the y-value of the crossing point (i.e. 1 in this example) and this value is then typically used as a real key for something.

For your bidding application you could let seal() and unseal() swap the y-value between the C and B points (deterministic) but have the A point vary from time to time.

This way seal(y-value of point B) will give completely different results depending on point A, but unseal(seal(y-value of point B)) should return the y-value of B which is what you ask for.

PS It is not required to have A and B on different sides of the y-axis, but is much simpler conceptually to think of it this way (and I recommend implementing it that way as well).

With this straight line you can then share keys between several persons so that only two of them are needed to unlock whatever. It is possible to use curve types other then straight lines to create other key sharing properties (i.e. 3 out of 3 keys are required etc).

1

Pseudo code:

encode:

value = 2000
key = random(0..255); // our key is only 2 bytes

// 'sealing it'
value = value XOR 2000;

// add key
sealed = (value << 16) | key

decode:

key = sealed & 0xFF
unsealed = key XOR (sealed >> 16)

Would that work?

1

Since it seems that you are assuming that the other person doesn't want to know your bid until after they've placed their own, and can be trusted not to cheat, you could try a variable rotation scheme:

from random import randint

def seal(input):
    r = randint(0, 50)
    obfuscate = [str(r)] + [ str(ord(c) + r) for c in '%s' % input ]
    return ':'.join(obfuscate)

def unseal(input):
    tmp = input.split(':')
    r = int(tmp.pop(0))
    deobfuscate = [ chr(int(c) - r) for c in tmp ]
    return ''.join(deobfuscate)

# I suppose you would put your bid in here, for 100 dollars
tmp = seal('$100.00') # --> '1:37:50:49:49:47:49:49' (output varies)
print unseal(tmp) # --> '$100.00'

At some point (I think we may have already passed it) this becomes silly, and because it is so easy, you should just use simple encryption, where the message recipient always knows the key - the person's username, perhaps.

3
  • Encode small numbers as base64? Intuitively, that sounds like it wouldn't do anything at all. Is there more to this that I'm not seeing?
    – Michael Myers
    Apr 30, 2009 at 21:29
  • This is a nice and simple solution, but you forgot the constraint that seal(1) shouldn't return the same thing every time.
    – dreeves
    Apr 30, 2009 at 21:30
  • Unless I misunderstand your code, seal('$100'), though always different, would always begin with 'JDEwM...". If I sent that number twice then the recipient might well notice and know it was another '$100'.
    – dreeves
    May 1, 2009 at 1:48
0

If the bids are fairly large numbers, how about a bitwise XOR with some predetermined random-ish number? XORing again will then retrieve the original value.
You can change the number as often as you like, as long as both client and server know it.

4
  • I don't want to assume large numbers (bids will often be 1 or 2 or even 0) and I'd like to avoid the coordination issue, beyond the original code.
    – dreeves
    Apr 30, 2009 at 21:25
  • Funny, this got downvoted while the top two answers are basically suggesting the same thing.
    – Michael Myers
    May 1, 2009 at 3:49
  • I think it's that having a predetermined random-ish number doesn't work unless you have a way to convey it to the recipient when it changes, which it needs to do because the seal function can't map the same number to the same output every time. Your idea probably got people on the right track though. (Though in the meantime, I think Svante's modulus idea beats the XOR method since you don't need to learn the new magic number each time.)
    – dreeves
    May 1, 2009 at 19:42
  • Well, if you look really, really close, my last sentence almost says to transmit the random number along with the encrypted number. ;) But yes, I do think Svante's idea is the best now.
    – Michael Myers
    May 1, 2009 at 19:45
0

You could set a different base (like 16, 17, 18, etc.) and keep track of which base you've "sealed" the bid with...

Of course, this presumes large numbers (> the base you're using, at least). If they were decimal, you could drop the point (for example, 27.04 becomes 2704, which you then translate to base 29...)

You'd probably want to use base 17 to 36 (only because some people might recognize hex and be able to translate it in their head...)

This way, you would have numbers like G4 or Z3 or KW (depending on the numbers you're sealing)...

1
  • This is a good solution if there were some reasonable minimum bid. But in my application, zero will actually be a common bid and I want even that to be obscured.
    – dreeves
    May 1, 2009 at 3:11
0

Here's a cheap way to piggyback off rot13:

Assume we have a function gibberish() that generates something like "fdjk alqef lwwqisvz" and a function words(x) that converts a number x to words, eg, words(42) returns "forty two" (no hyphens).

Then define

seal(x) = rot13(gibberish() + words(x) + gibberish())

and

unseal(x) = rot13(x)

Of course the output of unseal is not an actual number and is only useful to a human, but that might be ok. You could make it a little more sophisticated with words-to-number function that would also just throw away all the gibberish words (defined as anything that's not one of the number words -- there are less than a hundred of those, I think).

Sanity check:

> seal(7)
fhrlls hqufw huqfha frira afsb ht ahuqw ajaijzji
> seal(7)
qbua adfshua hqgya ubiwi ahp wqwia qhu frira wge
> unseal(seal(7))
sueyyf udhsj seven ahkua snsfo ug nuhdj nwnvwmwv

I know this is silly but it's a way to do it "by hand" if all you have is rot13 available.

4
  • 1
    Yeah, but if you're worried about people being able to decode the number by familiarity, then they'll learn what the rot13 of "forty two" looks like, even though it will have some gibberish at the beginning and end. Apr 30, 2009 at 21:27
  • 1
    There is a small but not tiny chance that your bid will be "forty" and the post-gibberish will begin with " two". So you need for example to filter the gibberish to ensure it doesn't contain number words. Apr 30, 2009 at 21:29
  • Great point, Brian. But maybe with a fair amount of gibberish and, importantly, of random length at both beginning and end, you'd have to really comb it, which we're assuming people wouldn't do. (Again, good will is assumed -- I just don't want to be influenced by your number when I pick mine.)
    – dreeves
    Apr 30, 2009 at 21:35
  • @onebyone: Thanks, quite right! I think Svante's idea really nailed this though and has made this whole rot13 hack moot. His idea can also be done by hand.
    – dreeves
    Jul 4, 2009 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.